Kehtestatav valem

Lausearvutuse valemit nimetatakse kehtestatavaks, kui ta on vähemalt ühel väärtustusel tõene.  Sellisteks valemiteks on näiteks ,   või . On selge, et iga samaselt tõene valem on kehtestatav, kuid vastupidine järeldumine alati ei kehti. Üks näide kehtestavast lausearvutuse valemist on valem, mis ei ole samaselt tõene ega samaselt väär. Kontrollimaks, kas uuritav valem on kehtestav on mitmeid võimalusi– näiteks tõeväärtustabel või tõesuspuu.

Definitsioon

Lausearvutuse valemit  nimetatakse kehtestatavaks, kui ta on vähemalt ühel väärtustusel tõene.
Sõna "kehtestatav valem" kirjutamisel üks tüüpilisemaid vigu on kirjutada "kehtestav valem", kuid sõna õige kirjapilt on neist vaid esimene.

Kontrollimine tõeväärtustabeliga

Kontrollimaks kas lausearvutuse valem  on kehtestatav koostame tõeväärtustabeli. Kirjutame esmalt päisesse lausemuutujad  ja  ning seejärel lausearvutuse tehted prioriteedi järjekorras (tehete prioriteet kõrgeimast madalaimani on: ). Kahe muutuja korral on neli võimalikku tõeväärtuste kombinatsiooni, kolme muutuja puhul kaheksa. Need sisestamegi muutujate  ja  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  tõeväärtus 0 ehk väär. Antud veeru ülejäänud kolmes reas on väärtus 1 ehk tõene. Saime, et valem  on vähemalt ühel väärtustusel tõene ehk tegu on kehtestatava valemiga.

Kontrollimine tõesuspuuga

Kehtestatavuse kontrollimiseks kirjutame tõesuspuu algusse  ( tähistab uuritavat lausearvutuse valemit). Kui leidub haru, kus vastuolu ei teki, siis valem on kehtestatav.
Koostame tõesuspuu tingimusest  lähtudes. Tõesuspuu algusesse paneme kirja rea  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 () ning osateheteks eitused () ning implikatsioon (). Leiame toodud osavalemite tõeväärtused, mille korral  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 ja . 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  on kehtestatav.

Teoreem kehtestatava valemi eitusest

Teoreem 1. Valem   on kehtestatav parajasti siis, kui tema eitus  ei ole samaselt tõene.
Tõestus. Kui  on kehtestatav, siis väärtustusel, kus  on tõene, on valem  väär ja ei saa seetõttu olla samaselt tõene. Vastupidiselt, kui  ei ole samaselt tõene, siis leidub väärtustus, kus  on väär ja   järelikult tõene.
Näide.  Jaotises "kontrollimine tõeväärtustabeliga" näitasime, et valem  on kehtestatav. Kontrollime nüüd tõeväärtustustabeliga väidet, kas selle lause eitus on samaselt tõene.
Valem  oleks 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  ei ole samaselt tõene, mis on kooskõlas teoreemiga 1.