A matematikai logika alkalmazásszemléletű tárgyalása

Főoldal > TAMOP 4.2.5 Pályázat könyvei > Könyvek > Természettudományok > Matematika

A matematikai logika alkalmazásszemléletű tárgyalása

Pásztorné Varga Katalin, Várterész Magda, Sági Gábor

Panem Kft.

Beágyazás

Ítéletlogikai törvények

Legyen $A \in ℒ_{0}$ és $ℐ$ $ℒ_{0}$ egy interpretációja. Jelölje $ℐ ⊨_{0} A$ azt, hogy a $ℬ_{ℐ}$ Boole-értékelés $A$ -hoz az $i$ igazságértéket rendeli. Az $ℐ ⊨_{0} A$ jelölést úgy olvassuk, hogy az $A$ formula az $ℐ$ interpretációban igaz, vagy $ℐ$ kielégíti $A$ -t.

4.3.1. DEFINÍCIÓ. Az $ℒ_{0}$ nyelv egy $A$ formulája kielégíthető, ha van $ℒ_{0}$ -nak olyan $ℐ$ interpretációja, hogy $ℐ ⊨_{0} A$ . Egy ilyen interpretációt $A$ modelljének nevezünk. Ha nincs $A$ -nak modellje, az $A$ formulát kielégíthetetlennek mondjuk.

Könnyen eldönthető, hogy egy formula kielégíthető-e vagy sem. Ha a formula igazságtáblájában találunk olyan sort, ahol a formula oszlopában $i$ igazságérték található, a formula kielégíthető, egyébként – azaz ha a formula oszlopában csak $h$ igazságérték található – kielégíthetetlen. Másképp ha egy $A$ formula esetén van olyan interpretáció, mely a $φ A^{i}$ feltételeket teljesíti, azaz $A^{i}$ nem üres, a formula kielégíthető, ellenkező esetben kielégíthetetlen.

4.3.2. PÉLDA. A $(Y \lor Z) \land (Z \supset \neg X)$ formula kielégíthető, mert az igazságtáblájában (4.3. táblázat) a formula oszlopában található $i$ igazságérték. Másképp a 4.2.7. példában láthattuk, hogy a formula igazhalmaza nem üres. Ugyanakkor az $X \land \neg X$ formula kielégíthetetlen, hiszen az igazságtáblájában a formula alatt csupa $h$ igazságérték van. Másképp kifejezve, a $φ {(X \land \neg X)}^{i}$ feltételeket egyetlen interpretáció sem teljesíti: ${(X \land \neg X)}^{i}$ üres.

Table 4.9. Az $X \land \neg X$ formula igazságtáblája

X	$\neg X$	$X \lor \neg X$
$i$	$h$	$h$
$h$	$i$	$h$

Ha egy formula kielégíthetetlen, az azt jelenti, hogy minden interpretációban hamis, így a negáltja olyan formula, amelyik minden interpretációban igaz. Az ilyen formulák logikai igazságokat (törvényeket) fejeznek ki.

4.3.3. DEFINÍCIÓ. Az $A$ formula ítéletlogikai törvény vagy másképp tautológia, ha $ℒ_{0}$ minden $ℐ$ interpretációjára $ℐ ⊨_{0} A$ . Jelölése: $⊨_{0} A .$

A definíció alapján nyilvánvaló, hogy egy $A$ formula pontosan akkor tautológia, ha $\neg A$ kielégíthetetlen, azaz a $φ {(\neg A)}^{i}$ feltételeket egyetlen interpretáció sem elégíti ki. Hogy egy formula kielégíthetetlen-e, eldönthető. Nyilván így eldönthető az is, hogy tautológia-e. A formula tautológia, ha igazságtáblájában a formula alatt csupa $i$ igazságérték található, vagy a $φ {(\neg A)}^{i}$ feltételeket egyetlen interpretáció sem teljesíti.

4.3.4. PÉLDA. A $(Y \lor Z) \land (Z \supset \neg X)$ formula bár kielégíthető, de nem tautológia, mert az igazságtáblájában (4.3. táblázat) a formula alatt nem csak $i$ igazságértéket találhatunk. Az alábbi igazságtábla pedig azt bizonyítja, hogy az $X \lor \neg X$ formula tautológia.

X	$\neg X$	$X \lor \neg X$
$i$	$h$	$i$
$h$	$i$	$i$

Egy tautológiának minden interpretáció modellje. Tehát egy $ℒ_{0}$ -beli formula lehet olyan, hogy nincs modellje, tehát kielégíthetetlen, ellenkező esetben van modellje, azaz kielégíthető, és ilyen esetben lehet, hogy minden interpretáció modellje, vagyis tautológia. Az ítéletlogikai formulák szemantikai tulajdonságuk alapján az alábbi ábra szerint osztályozhatók:

A formulahelyettesítés során minden tautológiából újabb tautológiákat állíthatunk elő.

4.3.5. TÉTEL. Legyenek $A, B_{1}, B_{2}, \dots, B_{n}$ , $(n \geq 1)$ tetszőleges ítéletlogikai formulák. Ha $⊨_{0} A$ , akkor $⊨_{0} A (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n})$ .

BIZONYÍTÁS. Legyen $A$ tautológia. Vizsgáljuk az

$A (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n})$

formula igazságértékét egy tetszőlegesen rögzített $ℐ$ interpretációban. A 4.2.16. lemma szerint ha $J$ olyan interpretáció, hogy

$J (X) = {\begin{array}{l} ℐ (X) & ha X \notin {X_{1}, X_{2}, \dots, X_{n}}, \\ ℬ_{ℐ} (B_{i}) & ha X = X_{i} valamely i = 1,2, \dots, n - re, \end{array}$

akkor

$ℬ_{ℐ} (A (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n})) = ℬ_{J} (A) .$

De mivel $A$ tautológia, $ℬ_{J} (A) = i$ , tehát

$ℬ_{ℐ} (A (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n})) = i .$

Tehát az $A (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n})$ formula tetszőleges interpretációban igaz, így tautológia. $⋄$

Ez a tétel alapozza meg, hogy az alább felsorolt formulák mind tautológiák.

4.3.6. TÉTEL. Ha $A, B, C$ tetszőleges ítéletlogikai formulák, a következő formulák ítéletlogikai törvények:

bővítés előtaggal	$⊨_{0} A \supset (B \supset A)$
implikációlánc-törvény	$⊨_{0} (A \supset (B \supset C)) \supset ((A \supset B) \supset (A \supset C))$
	$⊨_{0} A \supset (B \supset A \land B)$
	$⊨_{0} A \land B \supset A$ és $⊨_{0} A \land B \supset B$
	$⊨_{0} (A \supset C) \supset ((B \supset C) \supset (A \lor B \supset C))$
	$⊨_{0} A \supset A \lor B$ és $⊨_{0} B \supset A \lor B$
reductio ad absurdum	$⊨_{0} (A \supset B) \supset ((A \supset \neg B) \supset \neg A)$
a kétszeres tagadás törvénye	$⊨_{0} \neg \neg A \supset A$
a kizárt harmadik törvénye	$⊨_{0} A \lor \neg A$
ellentmondás törvénye	$⊨_{0} \neg (A \land \neg A)$
az azonosság törvénye	$⊨_{0} A \supset A$
tranzitivitás	$⊨_{0} (A \supset B) \land (B \supset C) \supset (A \supset C)$
ellentmondásból bármi következik	$⊨_{0} A \supset (\neg A \supset B)$
Peirce-törvény	$⊨_{0} ((A \supset B) \supset A) \supset A$

BIZONYÍTÁS. Ezek a formulák az $(X, Y, Z ∥ A, B, C)$ formulahelyettesítés eredményeképp adódtak néhány egyszerű formulából, melyek tautológia voltát igazságtáblával könnyű igazolni. Például a kizárt harmadik törvényét bizonyítja a 4.3.4 példabeli igazságtábla és a 4.3.5. tétel alkalmazása. $⋄$

Már láttunk példát olyan formulapárokra a korábbiakban, melyek minden interpretációban azonos igazságértékűek voltak. Ilyen formulák például az $X$ és a $\neg \neg X$ . Ezek a formulák, mivel logikai jelentésük mindig ugyanaz, logikailag egyenértékűek.

4.3.7. DEFINÍCIÓ. Azt mondjuk, hogy az $A$ és $B$ ítéletlogikai formulák tautologikusan ekvivalensek, és ezt a tényt úgy jelöljük, hogy $A \sim_{0} B$ , ha minden $ℐ$ interpretációban $ℬ_{ℐ} (A) = ℬ_{ℐ} (B)$ .

Könnyen eldönthető, hogy két formula tautologikusan ekvivalens-e egymással vagy sem. Ha közös igazságtáblájukban a formulákhoz tartozó oszlopokban minden sorban ugyanaz az igazságérték található, a két formula tautologikusan ekvivalens, egyébként – azaz ha van olyan sor, ahol ezek az értékék különböznek – nem. Vegyük észre, hogy két formula akkor és csak akkor tautologikusan ekvivalens, ha az általuk leírt logikai művelet ugyanaz.

4.3.8. PÉLDA. Az $X \supset Y$ formula például tautologikusan ekvivalens a $\neg X \lor Y$ formulával, amit mutat a közös igazságtáblájuk.

Table 4.10. Az $X \supset Y$ és a $\neg X \lor Y$ formulák közös igazságtáblája

X	Y	$X \supset Y$	$\neg X \lor Y$
$i$	$i$	$i$	$i$
$i$	$h$	$h$	$h$
$h$	$i$	$i$	$i$
$h$	$h$	$i$	$i$

Világos, hogy minden $A, B, C$ ítéletlogikai formula esetén $A \sim_{0} A$ , ha $A \sim_{0} B$ , akkor $B \sim_{0} A$ és ha $A \sim_{0} B$ és $B \sim_{0} C$ , akkor $A \sim_{0} C$ , azaz az ítéletlogikai formulák közötti binér $\sim_{0}$ reláció ekvivalenciareláció. Ez a reláció az $ℒ_{0}$ elemeinek egy osztályozását generálja, az egymással tautologikusan ekvivalens formulák jelentése az ítéletlogikában ugyanaz.

4.3.9. LEMMA. $A \sim_{0} B$ pontosan akkor, ha $⊨_{0} (A \supset B) \land (B \supset A)$ .

BIZONYÍTÁS.

Ha $A \sim_{0} B$ , akkor $A$ és $B$ minden interpretációban azonos igazságértékű. Rögzítsünk most tetszőlegesen egy interpretációt. Ebben az interpretációban akár igaz, akár hamis a két formula, mindkét esetben igaz $A \supset B$ és $B \supset A$ is, tehát a konjunkciójuk is.
Ha pedig azt tudjuk, hogy az $(A \supset B) \land (B \supset A)$ formula tautológia, azaz minden interpretációban igaz, ehhez az $A \supset B$ és a $B \supset A$ formuláknak is minden interpretációban igazaknak kell lenniük. Rögzítsünk most tetszőlegesen egy interpretációt. Ha ebben $A$ igaz, akkor $A \supset B$ igaz volta miatt $B$ is igaz kell legyen, ha pedig $A$ hamis, akkor $B \supset A$ igaz volta miatt $B$ is hamis kell legyen.

Ezzel a lemmát bebizonyítottuk. $⋄$

A 4.2.15. példában az $(Y \lor Z) \land (Z \supset \neg X)$ formulában az $X$ helyére a tautologikusan ekvivalens $Y$ -t és $\neg \neg Y$ -t helyettesítve tapasztaltuk, hogy a helyettesítések után előálló formulák is tautologikusan ekvivalensek maradtak.

4.3.10. TÉTEL. Legyenek $A, A^{'}, B_{1}, B_{2}, \dots, B_{n}, C_{1}, C_{2}, \dots, C_{n}$ , $(n \geq 1)$ ítéletlogikai formulák. Ha $A \sim_{0} A^{'}$ és $B_{i} \sim_{0} C_{i}$ minden $i = 1,2, \dots, n$ -re, akkor

$\begin{array}{l} A (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n}) \sim_{0} \\ \sim_{0} A^{'} (X_{1}, X_{2}, \dots, X_{n} ∥ C_{1}, C_{2}, \dots, C_{n}) . \end{array}$

BIZONYÍTÁS.

A 4.3.9. lemma szerint $A \sim_{0} A^{'}$ pontosan akkor, ha $⊨_{0} (A \supset A^{'}) \land (A^{'} \supset A)$ . Ekkor viszont a 4.3.5. tétel miatt

$⊨_{0} ((A \supset A^{'}) \land (A^{'} \supset A)) (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n}) .$

A 4.1.15. definíciónak megfelelően elvégezve a formulahelyettesítéseket kapjuk, hogy

$\begin{array}{l} ⊨_{0} ((A (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n}) \supset A^{'} (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n})) \land \\ \land (A^{'} (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n}) \supset A (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n}))) . \end{array}$

Tehát a 4.3.9. lemma szerint (visszafelé)

$A (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n}) \sim_{0} A^{'} (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n}) .$ (*)

Másrészt a 4.2.13. tétel miatt

$A (X_{1}, X_{2}, \dots, X_{n} ∥ B_{1}, B_{2}, \dots, B_{n}) \sim_{0} A^{'} (X_{1}, X_{2}, \dots, X_{n} ∥ C_{1}, C_{2}, \dots, C_{n}) .$ (**)

$(*)$ és $(* *)$ $\sim_{0}$ tranzitivitását használva adja az állítást. $⋄$

4.3.11. TÉTEL. Ha $A, B, C$ ítéletlogikai formulák, $⊤$ tautológia, $⊥$ pedig kielégíthetetlen formula, akkor a túloldalon felsorolt formulák rendre tautologikusan ekvivalensek egymással:

asszociativitás
$A \land (B \land C) \sim_{0} (A \land B) \land C$	$A \lor (B \lor C) \sim_{0} (A \lor B) \lor C$
kommutativitás
$A \land B \sim_{0} B \land A$	$A \lor B \sim_{0} B \lor A$
disztributivitás
$A \land (B \lor C) \sim_{0} (A \land B) \lor (A \land C)$	$A \lor (B \land C) \sim_{0} (A \lor B) \land (A \lor C)$
idempotencia
$A \land A \sim_{0} A$	$A \lor A \sim_{0} A$
elimináció (elnyelés)
$A \land (B \lor A) \sim_{0} A$	$A \lor (B \land A) \sim_{0} A$
De Morgan törvényei
$\neg (A \land B) \sim_{0} \neg A \lor \neg B$	$\neg (A \lor B) \sim_{0} \neg A \land \neg B$
kiszámítási törvények
$A \land ⊤ \sim_{0} A$	$A \land ⊥ \sim_{0} ⊥$
$A \lor ⊤ \sim_{0} ⊤$	$A \lor ⊥ \sim_{0} A$
$A \supset ⊤ \sim_{0} ⊤$	$A \supset ⊥ \sim_{0} \neg A$
$⊤ \supset A \sim_{0} A$	$⊥ \supset A \sim_{0} ⊤$
logikai jelek közötti összefüggések
$A \land B \sim_{0} \neg (\neg A \lor \neg B)$	$A \land B \sim_{0} \neg (A \supset \neg B)$
$A \lor B \sim_{0} \neg (\neg A \land \neg B)$	$A \lor B \sim_{0} \neg A \supset B$
$A \supset B \sim_{0} \neg (A \land \neg B)$	$A \supset B \sim_{0} \neg A \lor B$
kétszeres tagadás	$\neg \neg A \sim_{0} A$
kontrapozíció	$A \supset B \sim_{0} \neg B \supset \neg A$
negáció az implikációban
$A \supset \neg A \sim_{0} \neg A$	$\neg A \supset A \sim_{0} A$
implikációs előtagok felcserélése	$A \supset (B \supset C) \sim_{0} B \supset (A \supset C)$
implikáció konjunktív előtaggal	$A \land B \supset C \sim_{0} A \supset (B \supset C)$
az implikáció öndisztributivitása	$A \supset (B \supset C) \sim_{0} (A \supset B) \supset (A \supset C)$
esetelemzés	$A \lor B \supset C \sim_{0} (A \supset C) \land (B \supset C)$

BIZONYÍTÁS. A tételben szereplő formulák szintén az $(X, Y, Z ∥ A, B, C)$ formulahelyettesítés eredményeképp adódtak néhány egyszerű formulából. Ekvivalenciájuk igazolását a közös igazságtábla segítségével az olvasóra hagyjuk. Majd hivatkozva a 4.3.10. tételre, a felsorolt formulák egymással való tautologikus ekvivalenciáit bizonyítottuk. $⋄$

Hasznos lesz a későbbiekben, ha kiterjesztjük a kielégíthetőség, illetve a kielégíthetetlenség fogalmát formulák tetszőleges halmazára is. A kielégíthetőség a formulahalmaz azon tulajdonságát fejezi ki, hogy formulái valamely interpretációban lehetnek együttesen igazak. A kielégíthetetlenség viszont azt, hogy a halmaz formulái nem lehetnek együttesen igazak egyetlen interpretációban sem.

4.3.12. DEFINÍCIÓ. $ℒ_{0}$ formuláinak egy tetszőleges $Γ$ halmaza kielégíthető, ha van $ℒ_{0}$ -nak olyan $ℐ$ interpretációja, hogy $ℐ ⊨_{0} A$ minden $A \in Γ$ -ra. Egy ilyen interpretációt $Γ$ modelljének nevezünk. Ha nincs $Γ$ -nak modellje, akkor $Γ$ kielégíthetetlen.

4.3.13. PÉLDA. Az ${X, X \supset Y, \neg Y}$ formulahalmaz például kielégíthetetlen, hisz közös igazságtáblájukban nincs olyan sor, melyben mindhárom formula $i$ értékű lenne.

Table 4.11. Az ${X, X \supset Y, \neg Y}$ formulahalmaz kielégíthetetlen

X	Y	$X \supset Y$	$\neg Y$
$i$	$i$	$i$	$h$
$i$	$h$	$h$	$i$
$h$	$i$	$i$	$h$
$h$	$h$	$i$	$i$

Végtelen formulahalmaz esetén nem mindig tudjuk igazságtáblával eldönteni, hogy a formulahalmaz kielégíthető-e.

4.3.14. LEMMA. Egy ${A_{1}, A_{2}, \dots, A_{n}}$ $(n \geq 2)$ formulahalmaznak pontosan azok az interpretációk a modelljei, mely interpretációk az $A_{1} \land A_{2} \land \dots \land A_{n}$ formulának is modelljei. Másképp fogalmazva: az ${A_{1}, A_{2}, \dots, A_{n}}$ formulahalmaz pontosan akkor kielégíthetetlen, ha az $A_{1} \land A_{2} \land \dots \land A_{n}$ formula is kielégíthetetlen.

BIZONYÍTÁS.

Ha az $ℐ$ interpretáció az ${A_{1}, A_{2}, \dots, A_{n}}$ formulahalmaz modellje, akkor $ℐ$ -ben a formulahalmaz minden formulája igaz, de ekkor $ℐ$ -ben a konjunkciójuk is igaz, tehát $ℐ$ a konjunkciónak is modellje.
Ha az $ℐ$ interpretáció az $A_{1} \land A_{2} \land \dots \land A_{n}$ formulának modellje, akkor $ℐ$ -ben $A_{1} \land A_{2} \land \dots \land A_{n}$ igaz, tehát minden $i = 1,2, \dots, n$ -re $A_{i}$ is igaz, tehát ezen formulákból álló formulahalmaznak $ℐ$ modellje.

Ezzel az állítást bebizonyítottuk. $⋄$

Feladatok

4.3.1. FELADAT. Legyenek $A, B, C$ tetszőleges ítéletlogikai formulák. Döntsük el, hogy a következő formulák kielégíthetőek-e, és ha igen, tautológiák-e.

$(A \supset B \lor C) \land \neg ((A \supset B) \lor (A \supset C))$
$(A \supset B \lor C) \land \neg ((\neg A \supset B) \lor (\neg A \supset C))$
$\neg (A \supset B) \supset A$
$A \land B \supset (A \supset B)$
$((A \supset B) \supset B) \supset A \lor B$

4.3.2. FELADAT. Igazoljuk, hogy az alábbi formulák tautológiák.

$((X \supset Y) \supset Y \supset Z) \land ((Y \supset Z) \supset X \lor \neg V) \supset ((X \supset Y) \supset X \lor \neg V)$
$(X \supset Y \land Z \supset V) \supset (\neg (Y \land Z \supset V) \supset \neg X)$

4.3.3. FELADAT. Döntsük el, hogy tautologikusan ekvivalensek-e a következő formulapárok.

$\neg X \lor ((X \supset Y) \land Z)$ és $(\neg X \lor (X \supset Y)) \land (\neg X \lor Z)$
$X \lor \neg \neg Y \supset Z \land \neg Z$ és $\neg X \land \neg Y$