Ugrás a tartalomhoz

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

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

Panem Kft.

Ítéletlogikai törvények

Ítéletlogikai törvények

Legyen A0 és 0 egy interpretációja. Jelölje 0A azt, hogy a Boole-értékelés A-hoz az i igazságértéket rendeli. Az 0A jelölést úgy olvassuk, hogy az A formula az interpretációban igaz, vagy kielégítiA-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 0A. Egy ilyen interpretációt Amodelljé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 φAi feltételeket teljesíti, azaz Ai nem üres, a formula kielégíthető, ellenkező esetben kielégíthetetlen.

4.3.2. PÉLDA. A (YZ)(Z¬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¬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¬X)i feltételeket egyetlen interpretáció sem teljesíti: (X¬X)i üres.

Table 4.9. Az X¬X formula igazságtáblája

X

¬ X

X ¬ 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 0A. Jelölése: 0A.

A definíció alapján nyilvánvaló, hogy egy A formula pontosan akkor tautológia, ha ¬A kielégíthetetlen, azaz a φ(¬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 φ(¬A)i feltételeket egyetlen interpretáció sem teljesíti.

4.3.4. PÉLDA. A (YZ)(Z¬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¬X formula tautológia.

X

¬ X

X ¬ 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,B1,B2,,Bn, (n1) tetszőleges ítéletlogikai formulák. Ha 0A, akkor 0A(X1,X2,,XnB1,B2,,Bn).

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

A ( X 1 , X 2 , , X n B 1 , B 2 , , 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 ) = { ( X ) ha X { X 1 , X 2 , , X n } , ( B i ) ha X = X i valamely i = 1,2, , n re ,

akkor

( A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) ) = J ( A ) .

De mivel A tautológia, J(A)=i, tehát

( A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) ) = i .

Tehát az A(X1,X2,,XnB1,B2,,Bn) 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 ( B A )

implikációlánc-törvény

0 ( A ( B C ) ) ( ( A B ) ( A C ) )

0 A ( B A B )

0 A B A  és 0ABB

0 ( A C ) ( ( B C ) ( A B C ) )

0 A A B  és 0BAB

reductio ad absurdum

0 ( A B ) ( ( A ¬ B ) ¬ A )

a kétszeres tagadás törvénye

0 ¬ ¬ A A

a kizárt harmadik törvénye

0 A ¬ A

ellentmondás törvénye

0 ¬ ( A ¬ A )

az azonosság törvénye

0 A A

tranzitivitás

0 ( A B ) ( B C ) ( A C )

ellentmondásból bármi következik

0 A ( ¬ A B )

Peirce-törvény

0 ( ( A B ) A ) A

BIZONYÍTÁS. Ezek a formulák az (X,Y,ZA,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 ¬¬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 A0B, 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 XY formula például tautologikusan ekvivalens a ¬XY formulával, amit mutat a közös igazságtáblájuk.

Table 4.10. Az XY és a ¬XY formulák közös igazságtáblája

X

Y

X Y

¬ X 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 A0A, ha A0B, akkor B0A és ha A0B és B0C, akkor A0C, azaz az ítéletlogikai formulák közötti binér 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 0 B pontosan akkor, ha 0(AB)(BA).

BIZONYÍTÁS.

  1. Ha A0B, 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 AB és BA is, tehát a konjunkciójuk is.

  2. Ha pedig azt tudjuk, hogy az (AB)(BA) formula tautológia, azaz minden interpretációban igaz, ehhez az AB és a BA 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 AB igaz volta miatt B is igaz kell legyen, ha pedig A hamis, akkor BA igaz volta miatt B is hamis kell legyen.

Ezzel a lemmát bebizonyítottuk.

A 4.2.15. példában az (YZ)(Z¬X) formulában az X helyére a tautologikusan ekvivalens Y-t és ¬¬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,B1,B2,,Bn,C1,C2,,Cn, (n1) ítéletlogikai formulák. Ha A0A és Bi0Ci minden i=1,2,,n-re, akkor

A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) 0 0 A ( X 1 , X 2 , , X n C 1 , C 2 , , C n ) .

BIZONYÍTÁS.

A 4.3.9. lemma szerint A0A pontosan akkor, ha 0(AA)(AA). Ekkor viszont a 4.3.5. tétel miatt

0 ( ( A A ) ( A A ) ) ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) .

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

0 ( ( A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) ) ( A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) ) ) .

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

A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) 0 A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) . (*)

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

A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) 0 A ( X 1 , X 2 , , X n C 1 , C 2 , , C n ) . (**)

( * ) és (**)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 ( B C ) 0 ( A B ) C

A ( B C ) 0 ( A B ) C

kommutativitás

A B 0 B A

A B 0 B A

disztributivitás

A ( B C ) 0 ( A B ) ( A C )

A ( B C ) 0 ( A B ) ( A C )

idempotencia

A A 0 A

A A 0 A

elimináció (elnyelés)

A ( B A ) 0 A

A ( B A ) 0 A

De Morgan törvényei

¬ ( A B ) 0 ¬ A ¬ B

¬ ( A B ) 0 ¬ A ¬ B

kiszámítási törvények

A 0 A

A 0

A 0

A 0 A

A 0

A 0 ¬ A

A 0 A

A 0

logikai jelek közötti összefüggések

A B 0 ¬ ( ¬ A ¬ B )

A B 0 ¬ ( A ¬ B )

A B 0 ¬ ( ¬ A ¬ B )

A B 0 ¬ A B

A B 0 ¬ ( A ¬ B )

A B 0 ¬ A B

kétszeres tagadás

¬ ¬ A 0 A

kontrapozíció

A B 0 ¬ B ¬ A

negáció az implikációban

A ¬ A 0 ¬ A

¬ A A 0 A

implikációs előtagok felcserélése

A ( B C ) 0 B ( A C )

implikáció konjunktív előtaggal

A B C 0 A ( B C )

az implikáció öndisztributivitása

A ( B C ) 0 ( A B ) ( A C )

esetelemzés

A B C 0 ( A C ) ( B C )

BIZONYÍTÁS. A tételben szereplő formulák szintén az (X,Y,ZA,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 0A minden AΓ-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,XY,¬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,XY,¬Y} formulahalmaz kielégíthetetlen

X

Y

X Y

¬ 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 {A1,A2,,An}(n2) formulahalmaznak pontosan azok az interpretációk a modelljei, mely interpretációk az A1A2An formulának is modelljei. Másképp fogalmazva: az {A1,A2,,An} formulahalmaz pontosan akkor kielégíthetetlen, ha az A1A2An formula is kielégíthetetlen.

BIZONYÍTÁS.

  1. Ha az interpretáció az {A1,A2,,An} 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.

  2. Ha az interpretáció az A1A2An formulának modellje, akkor -ben A1A2An igaz, tehát minden i=1,2,,n-re Ai 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.

  1. ( A B C ) ¬ ( ( A B ) ( A C ) )

  2. ( A B C ) ¬ ( ( ¬ A B ) ( ¬ A C ) )

  3. ¬ ( A B ) A

  4. A B ( A B )

  5. ( ( A B ) B ) A B

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

  1. ( ( X Y ) Y Z ) ( ( Y Z ) X ¬ V ) ( ( X Y ) X ¬ V )

  2. ( X Y Z V ) ( ¬ ( Y Z V ) ¬ X )

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

  1. ¬ X ( ( X Y ) Z ) és (¬X(XY))(¬XZ)

  2. X ¬ ¬ Y Z ¬ Z és ¬X¬Y

4.3.4. FELADAT. Kielégíthetők-e az alábbi formulahalmazok?

  1. { ¬ Y , X Y , X Z }

  2. { ¬ Y , X Y , X Z , ¬ Z }

  3. { ¬ Z , X V , X Y , Y Z , V W Z }