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.

Szemantikus következményfogalom

Szemantikus következményfogalom

4.4.1. DEFINÍCIÓ. Legyen Γ az 0 nyelv formuláinak tetszőleges halmaza és B egy tetszőleges formula. Azt mondjuk, hogy a B formula tautologikus következménye a Γ formulahalmaznak (vagy a Γ-beli formuláknak), ha Γ minden modellje modellje a B formulának is. A Γ-beli formulákat feltételformuláknak (premisszáknak), a B formulát következményformulának (konklúziónak) nevezzük. Arra pedig, hogy a Γ formulahalmaznak tautologikus következménye B, a Γ0B jelöléssel hivatkozunk.

Ha a definíció alapján el akarjuk dönteni, hogy egy B formula egy véges formulahalmaznak tautologikus következménye-e, meg kell vizsgálnunk, hogy a formulahalmazt kielégítő interpretációk mindegyike kielégíti-e B-t is.

4.4.2. PÉLDA.

a) A {¬Y,XY,XZ} formulahalmaz tautologikus következménye Z, ahogy azt közös igazságtáblájuk mutatja.

X

Y

Z

¬ Y

X Y

X Z

Z

i

i

i

h

i

i

i

i

i

h

h

i

h

h

i

h

i

i

i

i

i

i

h

h

i

i

h

h

h

i

i

h

i

i

i

h

i

h

h

i

i

h

h

h

i

i

h

i

i

h

h

h

i

h

i

h

Csak a -gal jelölt sorbeli interpretáció elégíti ki a feltételformulák halmazát és a következményformula ebben az interpretációban igaz.

b) Most a szemantikán alapuló ,,lusta” módszerrel fogjuk belátni, hogy a {¬Z,XV,XY,YZ,VWZ} formulahalmaz tautologikus következménye ¬X. A közös igazságtáblának 32 sora lenne, ezért az igazságtábla helyett a feltételformulák halmazát kielégítő interpretációk megkereséséhez a szemantika által megadott igazzá válási feltételeket vizsgáljuk. Tegyük fel, hogy olyan interpretáció, mely minden feltételformulát kielégít.

  1. Mivel ¬Z feltételformula, ezért (Z)=h lehet csak.

  2. ( Z ) = h mellett az YZ feltételformula csak akkor lehet igaz, ha (Y)=h.

  3. ( Z ) = h és (Y)=h mellett az XY pedig csak (X)=h választás esetén lesz igaz.

  4. Ha (Z)=(Y)=(X)=h, akkor az XV igazzá válásához (V)=i szükséges.

  5. A rögzített (Z)=(Y)=(X)=h és (V)=i igazságértékek esetén a VWZ formula igazzá válásához az (W)=h kell.

A fenti lépéseket végigvihetjük a közös igazságtábla-sémán is. Látjuk, hogy csak egy interpretáció elégíti ki a feltételformulák halmazát, és hogy ebben az interpretációban a következményformula is igaz.

X

Y

Z

V

W

¬ Z

X V

X Y

Y Z

V W Z

¬ X

-

-

h

-

-

i

-

h

h

-

-

i

i

h

h

h

-

-

i

i

i

i

h

h

h

i

-

i

i

i

i

i

h

h

h

i

h

i

i

i

i

i

i

c) Most igazságértékeléssel mutatjuk meg, hogy az {XY,¬X¬Y} formulahalmaznak tautologikus következménye a ¬Y¬X formula.

A 4.3.14. lemma szerint a feltételformulák halmazát éppen azok az interpretációk elégítik ki, melyek a φ((XY)(¬X¬Y))i feltételeket teljesítik.

A feltételformulák halmazát kielégítő interpretációk az (X)=(Y)=i és az (X)=(Y)=h. Mindkét interpretációban a ¬Y¬X formula igaz, tehát a formula tautologikus következménye a premisszáknak.

4.4.3. TÉTEL. Legyen Γ ítéletlogikai formulák tetszőleges halmaza, A,B,C pedig tetszőleges ítéletlogikai formulák. Ha Γ0A, Γ0B és {A,B}0C, akkor Γ0C.

BIZONYÍTÁS. A következményfogalom definíciója szerint azokban az interpretációkban, amelyek kielégítik Γ-t, az A is, és a B is igaz. A C igaz minden olyan interpretációban, amelyben az A is, és a B is igaz. Tehát C igaz minden, a Γ-t kielégítő interpretációban, azaz Γ0C.

A következményfogalmat hasznos lenne egy alkalmas formula szemantikai jellemzésével leírni. Ehhez nyújtanak lehetőséget a következő tételek.

4.4.4. TÉTEL. Legyenek A1,A2,,An,B(n1) tetszőleges ítéletlogikai formulák. {A1,A2,,An}0B pontosan akkor, ha az {A1,A2,,An,¬B} formulahalmaz kielégíthetetlen, vagy – ami ugyanazt fejezi ki másképp – az A1A2An¬B formula kielégíthetetlen.

BIZONYÍTÁS.

  1. Legyen {A1,A2,,An}0B. Ekkor a következményfogalom definíciója szerint minden olyan interpretáció, amely kielégíti a feltételformulák halmazát, kielégíti a B következményformulát is. Ezekben az interpretációkban tehát ¬B, illetve A1A2An¬B is hamis, továbbá ezek az interpretációk nem elégítik ki {A1,A2,,An,¬B}-t. Azok az interpretációk, melyek már nem elégítik ki a feltételformulák halmazát sem, nyilván nem elégíthetik ki a bővebb {A1,A2,,An,¬B} formulahalmazt, illetve ezen formulák konjunkcióját sem.

  2. Legyen most az {A1,A2,,An,¬B} formulahalmaz, vagy az A1A2An¬B formula kielégíthetetlen. Ekkor vagy már az {A1,A2,,An} is kielégíthetetlen, ekkor nyilván {A1,A2,,An}0B. Ha viszont az {A1,A2,,An} kielégíthető, akkor rögzítsük egy tetszőleges modelljét. Ez a modell sem elégítheti ki a kielégíthetetlen {A1,A2,,An,¬B} formulahalmazt, tehát ¬B hamis, azaz B igaz benne, így modellje B-nek is.

Ezzel a tételt bebizonyítottuk.

4.4.5. MEGJEGYZÉS. A 4.4.4. tétel egy részét általánosabban is megfogalmazhatjuk: Legyen Γ ítéletlogikai formulák tetszőleges halmaza és B tetszőleges formula. Γ0B pontosan akkor, ha a Γ{¬B} formulahalmaz kielégíthetetlen. A bizonyítást az olvasóra bízzuk.

4.4.6. TÉTEL. Legyenek A1,A2,,An,B(n1) tetszőleges ítéletlogikai formulák. {A1,A2,,An}0B pontosan akkor, ha 0A1A2AnB.

BIZONYÍTÁS.

  1. Legyen {A1,A2,,An}0B. Ekkor minden olyan interpretáció, amely kielégíti a feltételformulák halmazát, kielégíti a B következményformulát is. Rögzítsünk most tetszőlegesen egy interpretációt. Két eset lehetséges. Ha az interpretáció nem modellje {A1,A2,,An}-nek, akkor az A1A2An formulának sem, azaz ebben az interpretációban A1A2An hamis, tehát A1A2AnB igaz. Ha viszont az interpretáció modellje {A1,A2,,An}-nek, akkor a feltételek miatt B-nek is, tehát ezekben az interpretációkban is igaz A1A2AnB.

  2. Most legyen 0A1A2AnB. Ekkor A1A2AnB minden interpretációban igaz. Tehát azokban az interpretációban, melyek az {A1,A2,,An} formulahalmazt, azaz a A1A2An formulát kielégítik, B-nek is is igaznak kell lennie.

A tétel tehát bizonyítást nyert.

4.4.7. TÉTEL. (DEDUKCIÓS TÉTEL.) Legyenek A1,A2,,An,B(n1) tetszőleges ítéletlogikai formulák. {A1,A2,,An1,An}0B pontosan akkor, ha {A1,A2,,An1}0AnB.

BIZONYÍTÁS. Jelölje Γ az {A1,A2,,An1,An}, Γ pedig az {A1,A2,,An1} formulahalmazt.

  1. Először azt bizonyítjuk, hogy ha Γ0B, akkor Γ 0AnB. Azt kell megmutatni, hogy Γ modelljei kielégítik AnB-t is. Γ modelljeit két csoportba oszthatjuk: az egyikben azok az interpretációk vannak, amelyek Γ-nak is modelljei, a másikban a többi Γ -t kielégítő interpretáció van. Világos, hogy Γ minden modellje modellje Γ -nek is. Nyilván Γ modelljeiben mind An, mind B és így AnB is igaz. Γ -nek pedig azon modelljeiben, melyek Γ-nak nem modelljei, An hamis, ezért az AnB most is igaz.

  2. Most pedig azt bizonyítjuk, hogy ha Γ 0AnB, akkor Γ0B. A Γ formulahalmazt kielégítő interpretációk kielégítik Γ -t is. A feltétel miatt ezekben az interpretációkban AnB és An is igaz, következésképpen B is igaz.

A dedukciós tételt bebizonyítottuk.

4.4.8. TÉTEL. (AZ ELDÖNTÉSPROBLÉMA TÉTELE.)

Legyenek A1,A2,,An,B ítéletlogikai formulák. {A1,A2,,An1,An}0B pontosan akkor, ha 0A1A2An1AnB.

BIZONYÍTÁS. {A1,A2,,An1,An}0B-re n-szer alkalmazva a dedukciós tételt egyik irányban, 0A1A2An1AnB-re n-szer alkalmazva a dedukciós tételt visszafelé, a tétel mindkét irányú állítása bizonyítást nyer.

4.4.9. MEGJEGYZÉS. Az eldöntésprobléma tétele bizonyítható úgy is, hogy megmutatjuk, hogy A1A2An1AnB0A1A2AnB, és alkalmazzuk a 4.4.6. tételt.

Mivel egy formulahalmazban a formulák sorrendje tetszőleges, a tétel kimondható úgy is, hogy {A1,A2,,An1,An}0B akkor és csak akkor, ha 0Ai1Ai2AinB, ahol i1,i2,in az 1,2,,n számok tetszőleges permutációja. Az eldöntésprobléma tétele azt fejezi ki, hogy B a Γ-nak pontosan akkor tautologikus következménye, ha az Ai1Ai2AinB implikációs lánc tautológia. Tehát azt kell eldönteni, hogy egy ítéletlogikai formula rendelkezik-e egy bizonyos szemantikus tulajdonsággal. Ha egy implikációs lánc tautológia, akkor a lánc utolsó formulája tautologikus következménye az implikációs láncban őt megelőző formulák halmazának, más szóval tétel az őt megelőző formulák mint feltételek mellett.

Legyenek Γ tetszőleges formulahalmaz, C1,C2,,Cn(n1) pedig tetszőleges ítéletlogikai formulák. Jelölje

Γ ( X 1 , X 2 , , X n C 1 , C 2 , , C n )

azt a formulahalmazt, melyet úgy kaptunk, hogy Γ minden formulájában végrehajtjuk az (X1,X2,,XnC1,C2,,Cn) formulahelyettesítést.

4.4.10. TÉTEL. Ha Γ0B, akkor

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

BIZONYÍTÁS. Tegyük fel, hogy modellje Γ(X1,X2,,XnC1,C2,,Cn)-nek. Ekkor tetszőleges AΓ-ra (A(X1,X2,,XnC1,C2,,Cn))=i. Legyen

J ( X ) = { ( X ) ha X { X 1 , X 2 , , X n } , ( C i ) ha X = X i valamely i = 1,2, , n re .

A 4.2.16. lemma szerint ekkor J(A)=i, azaz J modellje Γ-nak, de Γ0B miatt B-nek is, azaz J(B)=i. újra a lemma miatt ekkor

( B ( X 1 , X 2 , , X n C 1 , C 2 , , C n ) ) = i ,

azaz modellje B(X1,X2,,XnC1,C2,,Cn)-nek is.

Ha a feltételformuláknak egy formula tautologikus következménye volt, a formulahelyettesítés során nyert feltételformuláknak is tautologikus következménye lesz a kapott formula. Tehát ha egyszer kiderült, hogy helyesen következtettünk, olyan formában más formulákkal is helyesen lehet következtetni.

4.4.11. DEFINÍCIÓ. Legyen {A1,A2,,An} tetszőleges formulahalmaz, és B egy formula. Az ({A1,A2,,An},B) párt következtetésformának nevezzük. Az ({A1,A2,,An},B) pár helyes következtetésforma, ha {A1,A2,,An} kielégíthető és {A1,A2,,An}0B.

Nem tekintjük helyes következtetésformának, ha a premisszák halmaza kielégíthetetlen. Ugyanis így a következményformula számára nincs előírva, hogy milyen interpretációkban kell igaznak lennie, tehát a következményformula bármilyen formula lehet. Továbbá nyilván helyes, de nem túl érdekes következtetésforma, amikor a konklúzió tautológia, hiszen a logikai törvények feltétel nélkül igazak.

A 4.4.2. példában vizsgált helyes következtetésformák speciálisak, valamilyen probléma megoldása során alakultak ki. Vannak természetesen olyan következtetésformák, amelyek felhasználása általánosabb, ezek a logikai műveletekkel hozhatók kapcsolatba.

4.4.12. TÉTEL. Legyenek A,B,C tetszőleges ítéletlogikai formulák. Az alábbiakban felsorolt következtetésformák helyesek:

a leválasztási szabály vagy modus ponens

( { A B , A } , B )

a kontrapozíció vagy modus tollens

( { A B , ¬ B } , ¬ A )

reductio ad absurdum

( { A B , A ¬ B } , ¬ A )

az indirekt bizonyítás

( { ¬ A B , ¬ A ¬ B } , A )

feltételes szillogizmus

( { A B , B C } , A C )

következtetés esetszétválasztással

( { A B , A C , B C } , C )

modus tollendo ponens

( { A B , ¬ A } , B )

modus ponendo tollens

( { A B , A } , ¬ B )

a -ra vonatkozó következtetésformák

( { A } , A B ) é s ( { B } , A B )

a -re vonatkozó következtetésformák

( { A , B } , A B )

( { A B } , A ) é s ( { A B } , B )

az -ra vonatkozó következtetésforma

( { B } , A B )

a ¬¬-re vonatkozó következtetésformák

( { ¬ ¬ A } , A ) é s ( { A } , ¬ ¬ A )

BIZONYÍTÁS. A tételben szereplő következtetésformák az (X,Y,ZA,B,C) formulahelyettesítés eredményeképp adódtak néhány egyszerű következtetésformából. Annak igazolását, hogy ezek az egyszerű következtetésformák helyesek, a 4.4.2. példában mutatott módon az olvasóra hagyjuk. Majd hivatkozunk a 4.4.10. tételre, amivel a felsorolt következtetésformák helyességét bebizonyítottuk.

Következtetési módok

A következményfogalom alapján el lehet tehát dönteni, hogy egy formulahalmaz és egy formula párosa helyes következtetésforma-e. Megmutatjuk, hogy milyen – szemantikai eszközöket használó – következtetési módok ismertek a döntés meghozatalára.

Az egyik következtetési mód a visszakövetkeztetés, ami azt jelenti, hogy az {A1,A2,,An} formulahalmaz és a B formula együttes ismerete alapján döntünk. Szemantikai alapon működő döntést hozhatunk közös igazságtáblával, amit a 4.4.2. példában már láthattunk. Alkalmas a 4.4.4. tételre alapozott módszer is, ahol az A1A2An¬B formuláról vagy az {A1,A2,,An,¬B} formulahalmazról kell eldönteni, hogy kielégíthetetlen-e. A közös igazságtáblával feldolgozott példákon bemutatjuk ezt a módszert is.

4.4.13. PÉLDA.

  1. Igazolni fogjuk azt, hogy {¬Y,XY,XZ}0Z úgy, hogy közös igazságtáblával belátjuk a {¬Y,XY,XZ,¬Z} formulahalmaz kielégíthetetlenségét.

X

Y

Z

¬ Y

X Y

X Z

¬ Z

i

i

i

h

i

i

h

i

i

h

h

i

h

i

i

h

i

i

i

i

h

i

h

h

i

i

h

i

h

i

i

h

i

i

h

h

i

h

h

i

i

i

h

h

i

i

h

i

h

h

h

h

i

h

i

i

Nincs olyan sor, melyben mind a négy jobb oldali oszlopban i lenne, ezért nincs olyan interpretáció, mely kielégítené a {¬Y,XY,XZ,¬Z} formulahalmazt, tehát Z következmény.

  1. A szemantikán alapuló ,,lusta” módszerrel látjuk be, hogy a {¬Z,XV,XY,YZ,VWZ,X} kielégíthetetlen, azaz {¬Z,XV,XY,YZ,VWZ}0¬X. Keressük a következményformula negáltját (¬¬X-et) kielégítő olyan interpretációkat, amelyek a feltételhalmazt is kielégítik.

    1. Az 0¬¬X interpretációkban (X)=i. A ¬Z feltételformula csak (Z)=h mellett lehet igaz.

    2. ( X ) = i és (Z)=h mellett az YZ feltételformula csak (Y)=h igazságértékre, viszont az XY csak (Y)=i értékre lehet igaz. Ezek egymásnak ellentmondó feltételek, így {¬Z,XV,XY,YZ,VWZ,X} kielégíthetetlen. Tehát ¬X tétel.

A fenti lépéseket végigvihetjük a közös igazságtábla-sémán is:

X

Y

Z

V

W

¬ Z

X V

X Y

Y Z

V W Z

¬ ¬ X

i

-

h

-

-

i

i

i

h !

h

-

-

i

h

i

i

i

i !

h

-

-

i

i

h

i

  1. Következménye-e a ¬Y¬X formula az {XY,¬X¬Y} formulahalmaznak? Lássuk be a 4.4.4. tételnek megfelelően, hogy az (XY)(¬X¬Y)¬(¬Y¬X) kielégíthetetlen.

Tehát nincs olyan interpretáció, mely igazzá tenné az (XY)(¬X¬Y)¬(¬Y¬X) formulát.

A másik következtetési mód az előrekövetkeztetés. Ilyenkor az {A1,A2,,An} formulahalmaz lehetséges következményeit keressük. Ha egy B formuláról el kell dönteni, hogy következménye-e ennek a formulahalmaznak, akkor azt ellenőrizzük, hogy a lehetséges következmények között van-e. A szemantikai alapon működő döntési módszerünk alapja a legszűkebb következmény fogalma lesz.

4.4.14. DEFINÍCIÓ. Az {A1,A2,,An} formulahalmaz formuláiban előforduló ítéletváltozók legyenek X1,X2,,Xm. {A1,A2,,An} legszűkebb következménye – rögzített bázis mellett – az az {i,h}m{i,h} logikai leképezés, amely pontosan azokhoz az interpretációkhoz rendel igaz értéket, amelyek kielégítik az {A1,A2,,An} formulahalmazt.

Világos, hogy az {A1,A2,,An} formulahalmaz következménye minden olyan formula, amely igaz az {A1,A2,,An} legszűkebb következményét kielégítő interpretációkban.

4.4.15. PÉLDA.

  1. Keressük meg közös igazságtáblával a {¬Y,XY,XZ} legszűkebb következményét.

X

Y

Z

¬ Y

X Y

X Z

lszköv

i

i

i

h

i

i

h

i

i

h

h

i

h

h

i

h

i

i

i

i

i

i

h

h

i

i

h

h

h

i

i

h

i

i

h

h

i

h

h

i

i

h

h

h

i

i

h

i

h

h

h

h

i

h

i

h

A legszűkebb következményt az (X)=i,(Y)=h,(Z)=i interpretáció elégíti ki.

  1. Keressük meg a szemantikán alapuló ,,lusta” módszerrel a {¬Z,XV,XY,YZ,VWZ} legszűkebb következményét.

A 4.4.2. példában láttuk, hogy a formulahalmazt csak az (Z)=(Y)=(X)=(W)=h, (V)=i interpretáció elégíti ki. A legszűkebb következmény csak ehhez az interpretációhoz rendel igaz értéket.

Feladatok

4.4.1. FELADAT. Bizonyítsuk be, hogy

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

  2. { ( X Y ) ( Z U ) , ( U V ) W } 0 X W

Használjuk a közös igazságtáblát, a ,,lusta” módszert és az igazságértékelést.

4.4.2. FELADAT. Ellenőrizzük a következtetés helyességét előre- és visszakövetkeztetéssel.

  1. Ha a lóversenyek eredményeit az összeesküvők előre eldöntik, vagy a játéktermeket kezükbe veszik a hamis játékosok, akkor a turizmus kevesebb bevételt hoz, és a város kárt szenved. Ha a turizmus kevesebb bevételt hoz, a rendőrség meg lesz elégedve. A rendőrség sohasem elégedett. Következésképp a lóversenyek eredményeit nem az összeesküvők döntik el.

  2. Ha hideg van, akkor bekapcsolom a fűtést, és nem megyek ki a szobából. Nem kapcsolom be a fűtést, vagy nem fázom. Ha nem vacsorázom, vagy nem alszik ki a villany, akkor fázom. Ha bekapcsolom a fűtést, akkor hideg van, és vacsorázom. Tehát ha bekapcsolom a fűtést, akkor kialszik a villany.

  3. Ha vonattal megyek, akkor ha a vonat késik, lekésem a találkozót. Ha lekésem a találkozót, és rossz kedvem lesz, akkor nem megyek holnap kirándulni. Ha nem kapom meg az állást, akkor rossz kedvem lesz, és elmegyek holnap kirándulni. Tehát ha vonattal megyek, akkor ha a vonat késik, megkapom az állást.