Kehtestatav valem

Lausearvutuse valemit nimetatakse kehtestatavaks, kui ta on vähemalt ühel väärtustusel tõene. Sellised valemid on näiteks formula_1, formula_2 või formula_3. 
On selge, et iga samaselt tõene valem on kehtestatav, kuid vastupidine järeldumine alati ei kehti. Üks näide kehtestatavast lausearvutuse valemist on valem, mis ei ole samaselt tõene ega samaselt väär. Uuritava valemi on kehtestatavuse kontrollimiseks on mitu võimalust, näiteks tõeväärtustabel või tõesuspuu.
Definitsioon.
Lausearvutuse valemit formula_4 nimetatakse kehtestatavaks, kui ta on vähemalt ühel väärtustusel tõene.
Mõiste "kehtestatav valem" asemel kirjutatakse sageli ekslikult "kehtestav valem", kuid õige kirjapilt on neist vaid esimene.
Kontrollimine tõeväärtustabeliga.
Kontrollimaks, kas lausearvutuse valem formula_5 on kehtestatav, koostame tõeväärtustabeli. Kirjutame esmalt päisesse lausemuutujad formula_6 ja formula_7 ning seejärel lausearvutuse tehted prioriteedi järjekorras (tehete prioriteet kõrgeimast madalaimani on: formula_8). Kahe muutuja korral on neli võimalikku tõeväärtuste kombinatsiooni, kolme muutuja puhul kaheksa. Need sisestamegi muutujate formula_6 ja formula_7 tõeväärtuste veergudesse ning seejärel täidame tabeli ülejäänud veerud, arvestades lausearvutustehteid.
Näeme, et ainult tabeli esimeses reas, kuuendas veerus on valemil formula_5 tõeväärtus 0 ehk väär. Antud veeru ülejäänud kolmes reas on väärtus 1 ehk tõene. Saime, et valem formula_12 on vähemalt ühel väärtustusel tõene ehk tegu on kehtestatava valemiga.
Kontrollimine tõesuspuuga.
Kehtestatavuse kontrollimiseks kirjutame tõesuspuu algusse formula_13 (formula_4 tähistab uuritavat lausearvutuse valemit). Kui leidub haru, kus vastuolu ei teki, siis valem on kehtestatav.
Koostame tõesuspuu tingimusest formula_5 lähtudes. Tõesuspuu algusesse paneme kirja rea formula_16 ja hakkame uurima, millistel juhtudel selline asi on võimalik. Esmalt leiame valemis üles peatehte ja osavalemid, mida see peatehe seob. Antud juhul on peatehteks disjunktsioon (formula_17) ning osateheteks eitused (formula_18) ning implikatsioon (formula_19). Leiame toodud osavalemite tõeväärtused, mille korral formula_4 on tõene. Lausearvutuse osatehete analüüsimisel kasutame elementaarsamme. Kui selliseid tõeväärtuste komplekte on üks, siis kirjutame need üksteise alla. Kui neid on mitu, siis tekib meil puule kaks allapoole hargnevat haru. Edasi jätkame harude analüüsimist sama skeemi alusel, kuni jõuame välja lausemuutujateni formula_6ja formula_7. Kui puu mingis harus tekib vastuolu (s.t. selles harus esineb mingi valem tõese ja väärana), siis ütleme, et see haru on vastuoluline ehk suletud ja kirjutame selle alla märgi ×. Vastasel korral ütleme, et haru on avatud.
Antud tõeväärtuspuus on kõik tehteid sisaldavad osavalemid elementaarsamme kasutades läbi vaadatud ja mitte kummaski harus me ei jõudnud vastuoluni ehk mõlemad harud on avatud. Kuna leidub haru, milles vastuolu ei teki, siis valem formula_5 on kehtestatav.
Teoreem kehtestatava valemi eitusest.
Teoreem 1. Valem formula_4 on kehtestatav parajasti siis, kui tema eitus formula_25 ei ole samaselt tõene.
Tõestus. Kui formula_4 on kehtestatav, siis väärtustusel, kus formula_4 on tõene, on valem formula_28 väär ja ei saa seetõttu olla samaselt tõene. Ja vastupidi: kui formula_28 ei ole samaselt tõene, siis leidub väärtustus, kus formula_28 on väär ja formula_4 järelikult tõene.
Näide. Jaotises "kontrollimine tõeväärtustabeliga" näitasime, et valem formula_5 on kehtestatav. Kontrollime nüüd tõeväärtustustabeliga väidet, kas selle lause eitus formula_33on samaselt tõene.
Valem formula_33oleks samaselt tõene kui tõeväärtustabelis oleks seitsmenda veeru kõigis ridades tõeväärtus 1. See nii ei ole ning oleme saanud, et valem formula_33 ei ole samaselt tõene, mis on kooskõlas teoreemiga 1.