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

5.4.1. DEFINÍCIÓ. Legyen Γ az [Vν] nyelv formuláinak tetszőleges halmaza és B tetszőleges formulája. Azt mondjuk, hogy a B formula logikai következménye a Γ formulahalmaznak (vagy a Γ-beli formuláknak), ha minden olyan [Vν]-beli interpretáció és változókiértékelés, amely kielégít minden Γ-beli formulát, az kielégíti a B formulát is. Jelölése: ΓB.

Próbáljuk meg először a fenti definíció alapján eldönteni, hogy egy adott formula valamely véges formulahalmaznak logikai következménye-e.

5.4.2. PÉLDA.

  1. Az p1 nyelvben a {P(c),x(P(x)x˜Q(x,x˜))} formulahalmaznak logikai következménye a x˜Q(c,x˜) formula. Ugyanis ha olyan interpretáció, amelyben |P(c)|=i és |x(P(x)x˜Q(x,x˜))|=i, akkor bármely x-variáns κ változókiértékelés mellett |P(x)x˜Q(x,x˜)|,κ=i. Legyen κ(x)=|c|. Az 5.2.15. tétel szerint |P(x)|,κ=|P(c)| és |x˜Q(x,x˜)|,κ=|x˜Q(c,x˜)|, így világos, hogy |P(x)|,κ=i miatt |x˜Q(x,x˜)|,κ=i, tehát |x˜Q(c,x˜)|=i. Azaz tetszőleges, a {P(c),x(P(x)x˜Q(x,x˜))} formulahalmazt kielégítő interpretáció kielégíti a x˜Q(c,x˜) formulát is.

  2. Ugyanakkor a xx˜R(f(x,x˜),x˜) formulának nem logikai következménye a x˜R(x˜,x˜) formula, hisz az p1 interpretációban a xx˜R(f(x,x˜),x˜) formula i, de a x˜R(x˜,x˜) formula h igazságértékű.

Az elsőrendű logika következményfogalmát is hasznos lenne alkalmas formulák szemantikai jellemzésével leírni. Ehhez nyújtanak lehetőséget az ítéletlogikában megismerthez nagyon hasonló tételek.

5.4.3. TÉTEL. Legyen Γ az [Vν] nyelv formuláinak tetszőleges halmaza és B tetszőleges formulája. ΓB pontosan akkor, ha a Γ{¬B} formulahalmaz kielégíthetetlen.

BIZONYÍTÁS.

  1. Legyen ΓB. Ekkor az 5.4.1. definíció szerint minden olyan interpretáció és változókiértékelés, amely kielégíti Γ-t, kielégíti B-t is. Ezekben az interpretációkban és változókiértékelések mellett tehát ¬B hamis, továbbá ezek az interpretációk és változókiértékelések nem elégítik ki Γ{¬B}-t. Azok az interpretációk, melyek már nem elégítik ki Γ-t sem, nyilván nem elégíthetik ki a bővebb Γ{¬B} formulahalmazt sem.

  2. Legyen most a Γ{¬B} formulahalmaz kielégíthetetlen. Ekkor vagy már Γ is kielégíthetetlen, ekkor nyilván ΓB. Ha viszont Γ kielégíthető, akkor rögzítsük egy tetszőleges interpretációt és κ változókiértékelést, melyre |A|,κ=i minden AΓ-ra. De Γ{¬B} kielégíthetetlen, tehát |¬B|,κ=h, azaz |B|,κ=i, így most is ΓB.

Ezzel a tételt bebizonyítottuk.

Ennek a tételnek a felhasználásával könnyen bizonyítható a következő két állítás.

5.4.4. TÉTEL. Legyenek A1,A2,,An,B(n1) az [Vν] nyelv tetszőleges formulái. {A1,A2,,An}B pontosan akkor, ha

  1. az A1A2An¬B formula kielégíthetetlen,

  2. az A1A2AnB formula logikai törvény.

Az elsőrendű logikában is érvényes a dedukciós tétel és a dedukciós tételen alapuló eldöntésprobléma-tétel. Bizonyításukat az olvasóra hagyjuk, mert az ítéletlogikai esethez nagyon hasonlók.

5.4.5. TÉTEL. (DEDUKCIÓS TÉTEL.)

Legyenek A1,A2,,An,B(n1) az [Vν] nyelv tetszőleges formulái. { A 1 , A 2 , , A n 1 , A n } B pontosan akkor, ha

{ A 1 , A 2 , , A n 1 } A n B .

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

Legyenek A1,A2,,An,B(n1) az [Vν] nyelv tetszőleges formulái. { A 1 , A 2 , , A n 1 , A n } B pontosan akkor, ha

A 1 A 2 A n 1 A n B .

A tétel természetesen kimondható úgy is, hogy {A1,A2,,An1,An}B akkor és csak akkor, ha Ai1Ai2AinB, ahol i1,i2,in az 1,2,,n számok tetszőleges permutációja.

5.4.7. TÉTEL. Legyen Γ az [Vν] nyelv formuláinak tetszőleges halmaza, B tetszőleges formula és x olyan változó, hogy xPar (A), ha AΓ. Ha ΓB, akkor ΓxB.

BIZONYÍTÁS. Ha ΓB, akkor minden olyan [Vν]-beli interpretáció és változókiértékelés, amely kielégít minden Γ-beli formulát, az kielégíti a B formulát is. Legyen tehát és κ tetszőlegesen rögzített olyan interpretáció és változókiértékelés, melyre |A|,κ=i minden AΓ-ra. Ekkor mivel xPar (A), ha AΓ, κ minden κx-variánsa esetén is |A|,κ=i minden AΓ-ra. Mivel ΓB, így κ minden κx-variánsára |B|,κ=i is, tehát az 5.2.9. definíció miatt |xB|,κ=i. Ez pedig azt jelenti, hogy ΓxB.

Az előző fejezetben Quine-táblázat segítségével is jellemeztük az elsőrendű formulákat, tehát az elsőrendű következményfogalmat is megvizsgálhatjuk ezzel az eszközzel.

5.4.8. DEFINÍCIÓ. Legyen Γ az [Vν] nyelv formuláinak véges halmaza és B tetszőleges formulája. Azt mondjuk, hogy Btautologikus következményeΓ-nak, ha a Γ formulahalmaz és B közös Quine-táblázatában azon sorokban, ahol minden Γ-beli formula alatt i igazságérték található, B oszlopában is csupa i igazságérték van. Jelölése: a Γ0B.

5.4.9. PÉLDA.

  1. A {xx˜Q(x,x˜)xP(x),¬xP(x)} formulahalmaznak tautologikus következménye a ¬xx˜Q(x,x˜) formula:

x x ˜ Q ( x , x ˜ )

x P ( x )

x x ˜ Q ( x , x ˜ ) x P ( x )

¬ x P ( x )

¬ x x ˜ Q ( x , x ˜ )

i

i

i

h

h

i

h

h

i

h

h

i

i

h

i

h

h

i

i

i

  1. Az 5.4.2. (a) példájában pedig a következményformula nem tautologikus következménye a feltételformulák halmazának, hisz ezen formuláknak a prímkomponensei éppen saját maguk, így ha elkészítjük a közös Quine-táblázatot, abban nyilván lesz olyan sor, ahova mindkét feltételformula alá i-t, a következményformula alá pedig h-t írunk. Persze az 5.4.2. (a) példa gondolatmenete alapján világos, hogy ilyen interpretáció valójában nincs.

5.4.10. LEMMA. Legyenek A1,A2,,An,B(n1) az [Vν] nyelv tetszőleges formulái. Ha {A1,A2,,An}0B, akkor {A1,A2,,An}B.

BIZONYÍTÁS. Az olvasóra bízzuk annak belátását, hogy {A1,A2,,An}0B, pontosan akkor, ha az A1A2AnB formula tautologikusan igaz. Ekkor az 5.3.19. lemma szerint a formula logikailag is igaz, ahonnan az 5.4.4. tétellel adódik az állítás.

Megjegyezzük, hogy az 5.4.10. lemma megfordítása nem igaz.

5.4.11. LEMMA. Legyenek A1,A2,,An,B(n1) az [Vν] nyelv tetszőleges formulái. Jelölje az {A1,A2,,An} formulahalmazt Γ. Legyenek továbbá a B[Vν] formula prímkomponensei a B1,B2,,Bn prímformulák, és legyenek C1,C2,,Cn tetszőleges [Vν]-beli formulák. Ha Γ0B, akkor

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

BIZONYÍTÁS. Ha Γ0B, könnyű belátni, hogy az A1A2AnB formula tautologikusan igaz. Az 5.3.21. lemma szerint ekkor az

( A 1 A 2 A n B ) ( B 1 , B 2 , , B n C 1 , C 2 , , C n ) ,

azaz az

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

formula is tautologikusan igaz. Ekkor viszont Γ(B1,B2,,BnC1,C2,,Cn)0B(B1,B2,,BnC1,C2,,Cn).

Ezzel a lemmát bebizonyítottuk.

Ha a feltételformuláknak egy formula logikai következménye volt, a formulahelyettesítés során nyert feltételformuláknak is logikai 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.

5.4.12. DEFINÍCIÓ. Legyenek A1,A2,,An,B(n1) az [Vν] nyelv tetszőleges formulái. Az ({A1,A2,,An},B) párt elsőrendű 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}B.

5.4.13. TÉTEL. Legyenek A,B és C tetszőleges elsőrendű logikai formulák az [Vν] nyelvben. Az alábbiakban felsorolt elsőrendű 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}, AB)

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

( { A , B } , A B )

( { A B } , A ) é s ({AB},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. Többet fogunk belátni: a felsorolt elsőrendű következtetésformákban a formulahalmaznak minden esetben tautologikus következménye a formula; az 5.4.10. lemma alapján ekkor azt mondhatjuk, hogy a formulák helyes elsőrendű következtetésformák. Ha az A,B,C formulák rendre egy elsőrendű logikai nyelv atomi formulái, Quine-táblával könnyű igazolni, hogy a felsorolt következtetésformákban a formulahalmaznak tautologikus következménye a formula. Majd az atomi formulák helyére rendre tetszőleges elsőrendű formulákat helyettesítve az 5.4.11. lemmából adódik, hogy ezen következtetésformákban is a formulahalmaznak tautologikus következménye a formula.

Természetesen vannak olyan elsőrendű következtetésformák is, amely következtetésformákban a formulahalmaznak logikai (de nem tautologikus) következménye a formula. Néhány ilyen jellegzetes helyes következtetésformát a teljesség igénye és bizonyítás nélkül felsorolunk:

az univerzális kvantor elhagyása

( { x A } , [ A ( x t ) ] )

az egzisztenciális kvantor bevezetése

( { [ A ( x t ) ] } , x A )

szillogizmusok

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

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

Feladatok

5.4.1. FELADAT. Logikai, esetleg tautologikus következménye-e a xQ(x,x) formula az alábbi formulahalmazoknak:

  1. { x y Q ( x , y ) }

  2. { x y ( Q ( x , y ) Q ( y , x ) ) , x y Q ( x , y ) , x y z ( Q ( x , y ) Q ( y , z ) Q ( x , z ) ) }

  3. { x y ( Q ( x , y ) Q ( y , x ) ) x Q ( x , x ) }

5.4.2. FELADAT. Bizonyítsuk be, hogy a

( { x Q ( x , x ) , x y z ( Q ( x , y ) Q ( x , z ) Q ( y , z ) ) } , x y ( Q ( x , y ) Q ( y , x ) ) )

elsőrendű következtetésforma helyes.