Klasikinė logika jungia tiesos vertes turinčius teiginius apibrėžtomis loginėmis jungtimis.
Esminės žinios
Klasikinėje dvireikšmėje logikoje teiginys yra teisingas arba klaidingas. Neiginys pakeičia jo tiesos vertę į priešingą; konjunkcija yra teisinga, kai abi jos dalys teisingos, neišskiriamoji disjunkcija – kai bent viena dalis teisinga, o implikacija yra klaidinga tik tada, kai jos antecedentas teisingas, o konsekventas klaidingas.
Sąlygos ir taikymo ribos
Tai klasikinės reikšmės, apibrėžiamos tiesos funkcijomis; kitose loginėse sistemose taikoma kitokia semantika.
Vien loginė implikacija neteigia fizinio priežastinio ryšio.
Šaltiniai · 3
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Dvireikšmės logikos teiginių ir loginių jungčių apibrėžtys.
2026-10-10 · Patikrintos teisingumo sąlygos ir neišskiriamojo „arba“ vartojimo susitarimas.
Pagrindinių žinių peržiūra
2026-10-10 · Fresh primary-source inspection of the complete compact record, including every statement, equation, quantity and material condition, followed by independent AI editorial review. This check does not certify all linked lessons or every passage of every cited publication.
Šaltiniai iš kitų vietų
Sutampa nurodytose ribose
Classical negation, conjunction, inclusive disjunction and material implication.
The inspected truth table agrees; other logical semantics are outside this comparison.
Teiginys, kad P(x) galioja kiekvienam x iš nurodytos srities, yra klaidingas, jei bent vienam tos srities elementui P(x) negalioja. Kelių teiginį patvirtinančių pavyzdžių patikrinimas neįrodo teiginio begalinei sričiai.
Aksiomos yra matematinėje sistemoje priimtos prielaidos. Įrodymu teiginys išvedamas iš šių prielaidų ir anksčiau nustatytų rezultatų, taikant leistinus loginius išvedimus.
Klasikinėje pirmosios eilės logikoje ∀x φ yra teisinga, kai φ yra teisinga kiekvienam srities elementui; ∃x φ yra teisinga, kai ji teisinga bent vienam elementui. Laisviesiems kintamiesiems būtinas reikšmių priskyrimas.
3CNF formulėje su m klauzulių kiekvienam literalo pasirodymui sukurkite viršūnę. Sujunkite pasirodymus iš skirtingų klauzulių, jeigu jų literalai nėra vienas kito neiginiai. Formulė yra patenkinama tada ir tik tada, kai grafas turi m dydžio kliką: iš kiekvienos klauzulės pasirinkite vieną teisingą literalo pasirodymą; atvirkščiai, klikos suderinamus literalus galima išplėsti iki kintamųjų reikšmių priskyrimo.
DFA kalba yra tuščia tada ir tik tada, kai iš jo pradinės būsenos nepasiekiama jokia priimančioji būsena. Du DFA yra ekvivalentūs tada ir tik tada, kai jų sandaugos automato simetrinio skirtumo kalba yra tuščia. Sandaugos būsenų priėmimo taisyklės taip pat leidžia konstruoti reguliariųjų kalbų sankirtas ir sąjungas; sukeitus priimančiąsias ir nepriimančiąsias pilnojo DFA būsenas, gaunamas jo kalbos papildinys.
NL=coNL: nedeterministine logaritmine atmintimi sprendžiamų kalbų papildiniai taip pat priklauso NL. Pasiekiamumu grindžiamame įrodyme patvirtinamas pasiekiamų viršūnių skaičius, todėl nepasiekiamumą galima tikrinti naudojant nedeterministinę logaritminę darbinę atmintį.
Būlio formulių įvykdomumo uždavinys SAT yra NP pilnas pagal polinominio laiko daugelio į vieną redukcijas. Kiekvienai kalbai A∈NP ir įvesčiai x polinominio dydžio formulė koduoja polinominio laiko priimančio skaičiavimo lentelę taip, kad x∈A tada ir tik tada, kai ši formulė yra įvykdoma; pats formulę tenkinantis reikšmių priskyrimas yra NP liudijimas.
Įveskite kintamuosius Bulio subformulių loginiams elementams, ne daugiau kaip trijų literalų klauzulėmis užtikrinkite, kad kiekvieno loginio elemento reikšmė atitiktų jo įėjimus, ir reikalaukite, kad išėjimo loginio elemento reikšmė būtų teisinga. Taip sudaroma tiesinio dydžio 3CNF formulė, tenkinama tada ir tik tada, kai tenkinama pradinė formulė; tai parodo, kad SAT≤ₚ3SAT, taigi 3SAT yra NP-pilnas.
IR grąžina 1 tada ir tik tada, kai abu įėjimai yra 1; neišskirtinis ARBA grąžina 1, kai bent vienas įėjimas yra 1; NE sukeičia 0 ir 1. Dviejų įėjimų išskirtinis ARBA grąžina 1 tada ir tik tada, kai įėjimų vertės skiriasi. Teisingumo lentelėje nurodomi visi įėjimų verčių deriniai; IR, ARBA ir NE pakanka bet kuriai Bulio funkcijai su baigtiniu įėjimų skaičiumi išreikšti.
Boolean gate AND, inclusive OR and NOT implement conjunction, disjunction and negation on truth values.