Kehtestatav valem

Lausearvutuse valemit nimetatakse kehtestatavaks, kui ta on vähemalt ühel väärtustusel tõene^[1]. Sellised valemid on näiteks $A\lor B$ ^[2], $A\land \neg B$ ^[1] või $A\Rightarrow B$ .

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 muuda

Lausearvutuse valemit ${\mathcal {F}}$ nimetatakse kehtestatavaks, kui ta on vähemalt ühel väärtustusel tõene^[1].

Mõiste "kehtestatav valem" asemel kirjutatakse sageli ekslikult "kehtestav valem", kuid õige kirjapilt on neist vaid esimene^[3].

Seosed muuda

Iga samaselt tõene lausearvutuse valem on kehtestatav.
Kui lausearvutuse valem ei ole samaselt tõene ega samaselt väär, siis on tegu kehtestatava valemiga^[2].
Lausearvutuse valem on kehtestatav parajasti siis, kui tal leidub täielik disjunktiivne normaalkuju^[2].
Kui lausearvutuse valem ei ole kehtestatav, siis ta on samaselt väär – kui lausearvutuse valem ei ole kehtestatav, siis ta ei ole tõene mitte ühelgi väärtustusel ehk valem on väär igal väärtustusel.

Kontrollimine tõeväärtustabeliga muuda

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

Kontrollimine tõesuspuuga muuda

Kehtestatavuse kontrollimiseks kirjutame tõesuspuu algusse ${\mathcal {F}}=1$ ( ${\mathcal {F}}$ tähistab uuritavat lausearvutuse valemit). Kui leidub haru, kus vastuolu ei teki, siis valem on kehtestatav.

Koostame tõesuspuu tingimusest $\neg A\lor \neg (A\Rightarrow B)$ lähtudes. Tõesuspuu algusesse paneme kirja rea $\neg A\lor \neg (A\Rightarrow B)=1$ 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 ( $\lor$ ) ning osateheteks eitused ( $\neg$ ) ning implikatsioon ( $\Rightarrow$ ). Leiame toodud osavalemite tõeväärtused, mille korral ${\mathcal {F}}$ 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 $A$ ja $B$ . 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^[2].

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 $\neg A\lor \neg (A\Rightarrow B)$ on kehtestatav.

Teoreem kehtestatava valemi eitusest muuda

Teoreem 1. Valem ${\mathcal {F}}$ on kehtestatav parajasti siis, kui tema eitus $\neg {\mathcal {F}}$ ei ole samaselt tõene^[1].

Tõestus. Kui ${\mathcal {F}}$ on kehtestatav, siis väärtustusel, kus ${\mathcal {F}}$ on tõene, on valem $\neg {\mathcal {F}}$ väär ja ei saa seetõttu olla samaselt tõene. Ja vastupidi: kui $\neg {\mathcal {F}}$ ei ole samaselt tõene, siis leidub väärtustus, kus $\neg {\mathcal {F}}$ on väär ja ${\mathcal {F}}$ järelikult tõene^[1].

Näide. Jaotises "kontrollimine tõeväärtustabeliga" näitasime, et valem $\neg A\lor \neg (A\Rightarrow B)$ on kehtestatav. Kontrollime nüüd tõeväärtustustabeliga väidet, kas selle lause eitus $\neg (\neg A\lor \neg (A\Rightarrow B))$ on samaselt tõene.

Valem $\neg (\neg A\lor \neg (A\Rightarrow B))$ 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 $\neg (\neg A\lor \neg (A\Rightarrow B))$ ei ole samaselt tõene, mis on kooskõlas teoreemiga 1.

Vaata ka muuda

Viited muuda

↑ ^1,0 ^1,1 ^1,2 ^1,3 ^1,4 Reimo Palm, Rein Prank (2014). Sissejuhatus matemaatilisse loogikasse. Tartu: Tartu Ülikooli Kirjastus. Lk 14.
↑ ^2,0 ^2,1 ^2,2 ^2,3 Tartu Ülikooli kursuse "Diskreetse matemaatika I" loengukonspekt, lektor Valdis Laan.
↑ Reimo Palm. "Tüüpilisi kirjavigu". Vaadatud 07.05.2019.

[:0-1] 1,0 ^1,1 ^1,2 ^1,3 ^1,4 Reimo Palm, Rein Prank (2014). Sissejuhatus matemaatilisse loogikasse. Tartu: Tartu Ülikooli Kirjastus. Lk 14.

[:1-2] 2,0 ^2,1 ^2,2 ^2,3 Tartu Ülikooli kursuse "Diskreetse matemaatika I" loengukonspekt, lektor Valdis Laan.

[3] Reimo Palm. "Tüüpilisi kirjavigu". Vaadatud 07.05.2019.

[1]

[2]

[3]