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.

Elsőrendű logikai törvények

Elsőrendű logikai törvények

5.3.1. DEFINÍCIÓ. Az [Vν] nyelv egy A formulája kielégíthető, ha van [Vν]-nek olyan interpretációja és -ben van olyan κ változókiértékelés, amelyre |A|,κ=i, egyébként Akielégíthetetlen. Ha az interpretáció és a κ változókiértékelés olyanok, hogy |A|,κ=i, azt mondjuk, hogy a κ változókiértékelés mellett kielégítiA-t.

Amennyiben az A formula zárt, igazságértékét egyedül az interpretáció határozza meg. Ha |A|=i, azt mondjuk, hogy az interpretáció kielégítiA-t vagy másképp, a interpretáció az A formula modellje.

5.3.2. PÉLDA.

  1. Az p2 nyelv P(x)xP(x) formulája kielégíthető, mert például p2 interpretációban egy olyan κ változókiértékelés mellett, amelyben κ(x)=c, |P(x)|p2,κ=h, és így

| P ( x ) x P ( x ) | p 2 , κ = | P ( x ) | p 2 , κ | x P ( x ) | p 2 , κ = i .

  1. Ugyanakkor a xP(x)¬P(x) formula kielégíthetetlen, hiszen ha rögzítünk egy tetszőleges interpretációt és -ben egy tetszőleges κ változókiértékelést, akkor |xP(x)|,κ

    1. vagy h igazságértékű, így

| x P ( x ) ¬ P ( x ) | , κ = | x P ( x ) | , κ | ¬ P ( x ) | , κ = h ,

  1. vagy i igazságértékű, de ekkor az 5.2.9. definíció szerint κ minden x-variánsa, tehát maga κ mellett is |P(x)|,κ=i, így |¬P(x)|,κ=h, ezek szerint most is

| x P ( x ) ¬ P ( x ) | , κ = | x P ( x ) | , κ | ¬ P ( x ) | , κ = h .

Így egyetlen interpretáció egyetlen változókiértékelése sem elégítheti ki a xP(x)¬P(x) formulát.

Egy elsőrendű formula kielégíthetetlensége azt jelenti, hogy a formula minden interpretációban minden változókiértékelés mellett h igazságértékű, így a negáltja olyan formula, amelyik minden interpretációban minden változókiértékelés mellett i igazságértékű. Az ilyen formulák elsőrendű logikai igazságokat (törvényeket) fejeznek ki.

5.3.3. DEFINÍCIÓ. Az [Vν] nyelv egy A formulája logikailag igaz (másképp logikai törvény), ha [Vν] minden interpretációjában és minden κ változókiértékelése mellett |A|,κ=i. Jelölése: A.

A definíció alapján nyilvánvaló, hogy egy A formula pontosan akkor logikai törvény, ha minden interpretáció minden változókiértékeléssel kielégíti. Ha A zárt, egyszerűbben is fogalmazhatunk: A pontosan akkor logikai törvény, ha minden interpretáció kielégíti, azaz minden interpretáció modellje.

5.3.4. PÉLDA.

  1. A P(x)xP(x) formula bár kielégíthető, de nem logikai törvény, mert például az p2 interpretációban egy olyan κ változókiértékelés mellett, amelyben κ(x)=a, |P(x)|p2,κ=i, de |xP(x)|p2,κ=h, mivel a κ*(x)=c változókiértékelés mellett |P(x)|p2,κ*=h. Ezért

| P ( x ) x P ( x ) | p 2 , κ = | P ( x ) | p 2 , κ | x P ( x ) | p 2 , κ = h .

  1. Alább pedig azt bizonyítjuk be, hogy a xP(x)P(x) formula viszont logikai törvény. Rögzítsünk tetszőlegesen egy interpretációt és egy κ változókiértékelést. Két eset lehetséges:

    1. Ha kielégíti a xP(x)-et, akkor minden változókiértékelése mellett, tehát κ mellett is |P(x)|,κ=i, azaz

| x P ( x ) P ( x ) | , κ = | x P ( x ) | , κ | P ( x ) | , κ = i .

  1. Ha pedig nem elégíti ki a xP(x)-et, azaz |xP(x)|=h, akkor szintén

| x P ( x ) P ( x ) | , κ = | x P ( x ) | , κ | P ( x ) | , κ = i .

Hasonlóan az ítéletlogikához, egy elsőrendű logikai nyelv formuláit is osztályozhatjuk szemantikai tulajdonságuk alapján az 5.3. ábra szerint:

Figure 5.3.  [ V ν ] -beli formulák besorolása

ℒ [ V ν ] -beli formulák besorolása

Most néhány fontos elsőrendű logikai törvényt adunk meg. Ezen törvények közül több is implikáció. Felhívjuk a figyelmet arra, hogy ha egy implikációs formulában az implikáció bal és jobb oldali közvetlen részformuláit felcseréljük, ugyanazon interpretációban és változókiértékelés mellett az eredetitől különböző igazságértékű formulát is nyerhetünk. Az alább bizonyítandó implikációs logikai törvényekben felcserélve az implikáció két oldalán álló részformulákat, ugyan kielégíthető, de nem logikai törvényformulákat nyerünk. Javasoljuk az olvasónak ezen formulák vizsgálatát.

5.3.5. TÉTEL. Legyenek A és B az [Vν] nyelv tetszőleges formulái. Ekkor

x A x B x ( A B ) .

BIZONYÍTÁS. Legyen [Vν]-nek tetszőleges interpretációja és κ az interpretációban tetszőleges változókiértékelés. A xAxBx(AB) formula igazságértékét kell megvizsgálnunk -ben κ mellett. Két eset lehetséges:

  1. Ha |x(AB)|,κ=i, akkor a formulánk i igazságértékű.

  2. Ha |x(AB)|,κ=h, akkor van κ-nak olyan κ*x-variánsa, hogy |AB|,κ*=h, azaz |A|,κ*=h és |B|,κ*=h. Ez viszont azt jelenti, hogy |xA|,κ=h és |xB|,κ=h, vagyis

| x A x B | , κ = h .

Tehát a formulánk ebben az esetben is i igazságértékű.

Ezzel beláttuk, hogy a xAxBx(AB) formula logikai törvény.

5.3.6. TÉTEL. Legyenek A és B az [Vν] nyelv tetszőleges formulái. Ekkor

x ( A B ) x A x B .

BIZONYÍTÁS. Legyen [Vν]-nek tetszőleges interpretációja és κ az interpretációban tetszőleges változókiértékelés. Vizsgáljuk most meg a

x ( A B ) x A x B

formula igazságértékét -ben κ mellett. Két eset lehetséges:

  1. Ha |x(AB)|,κ=h, akkor a formula i igazságértékű.

  2. Ha |x(AB)|,κ=i, akkor van κ-nak olyan κ*x-variánsa, hogy |AB|,κ*=i. Ez azt jelenti, hogy |A|,κ*=i és |B|,κ*=i, azaz |xA|,κ=i és |xB|,κ=i. Ebből közvetlenül adódik, hogy |xAxB|,κ=i, tehát a formulánk most is i igazságértékű.

Tehát bebizonyítottuk, hogy x(AB)xAxB logikai törvény.

5.3.7. TÉTEL. Legyen A az [Vν] nyelv tetszőleges formulája. Ekkor

y x A x y A .

BIZONYÍTÁS. Legyen [Vν]-nek tetszőleges interpretációja és κ az interpretációban tetszőleges változókiértékelés. Vizsgáljuk most meg, hogy mi lehet a yxAxyA formula igazságértéke -ben κ mellett. Két eset lehetséges:

  1. Ha |xyA|,κ=i, akkor |yxAxyA|,κ=i.

  2. Ha |xyA|,κ=h, akkor van κ-nak olyan κ*x-variánsa, amely mellett |yA|,κ*=h. Ez viszont azt jelenti, hogy κ* minden κ**y-variánsa esetén |A|,κ**=h. Mivel κ** olyan változókiértékelés, hogy |A|,κ**=h, ezért |xA|,κ**=h. Továbbá azt is tudjuk, hogy κ* minden κ**y-variánsa ilyen, tehát |yxA|,κ*=h. Mivel x nem paraméter a yxA-ban, és κ és κ* csak az x-hez rendelt értékben különböznek, így |yxA|,κ=h. Ezzel bebizonyítottuk, hogy ebben az esetben is |yxAxyA|,κ=i.

Tehát a yxAxyA formula is logikai törvény.

5.3.8. DEFINÍCIÓ. Legyen A az [Vν] nyelv tetszőleges formulája és x1,x2,,xn tetszőleges változók a nyelvben. Ekkor a x1x2xnA formulát az Aformula általánosításának nevezzük.

5.3.9. LEMMA. Legyen A az [Vν] nyelv formulája és x tetszőleges változó a nyelvben. A akkor és csak akkor, ha xA.

BIZONYÍTÁS.

  1. Tegyük fel, hogy A. Rögzítsünk tetszőlegesen egy interpretációt és -ben egy κ változókiértékelést. Határozzuk meg a |xA|,κ igazságértéket. Ez pontosan akkor i, ha κ minden κ*x-variánsára |A|,κ*=i. De mivel A, ez fennáll.

  2. Tegyük most fel, hogy xA, azaz minden interpretáció és κ változókiértékelés mellett |xA|,κ=i. Ez azt jelenti, hogy minden -re és minden κ-ra |A|,κ=i is fennáll, tehát A.

Ezzel a lemmát bebizonyítottuk.

5.3.10. TÉTEL. Legyen A az [Vν] nyelv egy formulája és x1x2xnA ennek általánosítása. A akkor és csak akkor, ha x1x2xnA.

BIZONYÍTÁS. A-ra n-szer alkalmazva az 5.3.9. lemmát egyik irányban, és x1x2xnA-ra n-szer alkalmazva a lemmát visszafelé, a tétel mindkét irányú állítása könnyen adódik.

5.3.11. MEGJEGYZÉS. Hasonló állítást fogalmazhatunk meg a kielégíthetetlen formulákkal kapcsolatban is. Ha A formula és x1,x2,,xn változók az [Vν] nyelvben, A pontosan akkor kielégíthetetlen, ha x1x2xnA is kielégíthetetlen.

5.3.12. TÉTEL. Legyen A formula, t az x változóval megegyező fajtájú term [Vν]-ben. Ha A, akkor [A(xt)].

BIZONYÍTÁS. Legyen [Vν]-nek tetszőleges interpretációja és κ-ben egy változókiértékelés. Az 5.2.15. tétel szerint |[A(xt)]|,κ=|A|,κ ahol

κ ( y ) { κ ( y ) ha y x , | t | , κ ha y = x .

De mivel A, így |A|,κ=i tetszőleges interpretációban tetszőleges κ változókiértékelés mellett, tehát |[A(xt)]|,κ=i tetszőleges interpretációban tetszőleges κ változókiértékelés mellett, azaz [A(xt)].

5.3.13. TÉTEL. Legyen A tetszőleges formula és t az x változóval megegyező fajtájú tetszőleges term [Vν]-ben. Ekkor xA[A(xt)].

BIZONYÍTÁS. Legyen [Vν]-nek tetszőleges interpretációja és κ az interpretációban tetszőleges változókiértékelés. Vizsgáljuk most meg, hogy mi lehet a xA[A(xt)] formula igazságértéke -ben κ mellett. Két eset lehetséges:

  1. Ha |xA|,κ=h, akkor |xA[A(xt)]|,κ=i.

  2. Ha |xA|,κ=i, akkor κ minden κ*x-variánsa mellett |A|,κ*=i. Viszont az 5.2.15. tétel szerint |[A(xt)]|,κ=|A|,κ, ahol

κ ( y ) { κ ( y ) ha y x , | t | , κ ha y = x .

Világos, hogy κ a κ változókiértékelés egy lehetséges x-variánsa, így |A|,κ=i, azaz |[A(xt)]|,κ=i. Tehát |xA[A(xt)]|,κ=i ebben az esetben is.

Ezzel sikerült belátni, hogy a xA[A(xt)] formula logikai törvény.

5.3.14. TÉTEL. Legyen A tetszőleges formula és t az x változóval megegyező fajtájú tetszőleges term az [Vν] nyelvben. Ekkor [A(xt)]xA.

BIZONYÍTÁS. Legyen [Vν]-nek tetszőleges interpretációja és κ az interpretációban tetszőleges változókiértékelés. Vizsgáljuk az [A(xt)]xA formula igazságértékét -ben κ mellett. Két eset lehetséges:

  1. Ha |xA|,κ=i, akkor |[A(xt)]xA|,κ=i.

  2. Ha |xA|,κ=h, akkor κ minden κ*x-variánsa mellett |A|,κ*=h. Az 5.2.15. tétel szerint |[A(xt)]|,κ=|A|,κ, ahol

κ ( y ) { κ ( y ) ha y x , | t | , κ ha y = x .

Mivel κ a κ változókiértékelés egy lehetséges x-variánsa, így |A|,κ=h, azaz |[A(xt)]|,κ=h. Tehát |[A(xt)]xA|,κ=i ebben az esetben is.

Ezzel beláttuk, hogy az [A(xt)]xA formula logikai törvény.

5.3.15. MEGJEGYZÉS. Az 5.3.13. és az 5.3.14. tételek következményeként adódik, hogy tetszőleges A formula esetén xAxA is logikai törvény. Ugyanis tetszőleges interpretáció és κ változókiértékelés mellett

  1. ha |xA|,κ=h, akkor |xAxA|,κ=i,

  2. ha pedig |xA|,κ=i, akkor mivel tetszőlegesen rögzített t term esetén xA[A(xt)], ezért |[A(xt)]|,κ=i. Továbbá mivel [A(xt)]xA, így |xA|,κ=i is.

Tehát xAxA.

5.3.16. TÉTEL. Legyen A formula, x és y pedig azonos fajtájú, de különböző változók az [Vν] nyelvben. Ekkor xyAx[A(yx)].

BIZONYÍTÁS. Legyen [Vν]-nek tetszőleges interpretációja és κ az interpretációban tetszőleges változókiértékelés. Vizsgáljuk meg a xyAx[A(yx)] formula igazságértékét -ben κ mellett:

  1. Ha |x[A(yx)]|,κ=i, akkor |xyAx[A(yx)]|,κ=i.

  2. Ha |x[A(yx)]|,κ=h, akkor van κ-nak olyan κ*x-variánsa, hogy |[A(yx)]|,κ*=h. Mivel y nem paraméter az [A(yx)] formulában, így κ* minden y-variánsa, így

κ * * ( u ) { κ * ( u ) ha u y , κ * ( x ) ha u = y

mellett is |[A(yx)]|,κ**=h. Mivel pedig κ**x-hez és y-hoz ugyanazt az individuumot rendeli, |[A(yx)]|,κ**=|A|,κ**. Ezzel beláttuk, hogy |xyA|,κ=h, tehát |xyAx[A(yx)]|,κ=i ebben az esetben is.

Ez azt jelenti, hogy a xyAx[A(yx)] formula logikai törvény.

5.3.17. TÉTEL. Legyen A formula, x és y pedig azonos fajtájú, de különböző változók az [Vν] nyelvben. Ekkor x[A(yx)]xyA.

BIZONYÍTÁS. Legyen [Vν]-nek tetszőleges interpretációja és κ az interpretációban tetszőleges változókiértékelés. Megvizsgáljuk, mi lesz a x[A(yx)]xyA formula igazságértéke -ben κ mellett. Két eset lehetséges:

  1. Ha |x[A(yx)]|,κ=h, akkor |x[A(yx)]xyA|,κ=i.

  2. Ha |x[A(yx)]|,κ=i, akkor van κ-nak olyan κ*x-variánsa, hogy |[A(yx)]|,κ*=i. Mivel y nem paraméter az [A(yx)] formulában, így κ* minden y-variánsa, így

κ * * ( u ) { κ * ( u ) ha u y , κ * ( x ) ha u = y

mellett is |[A(yx)]|,κ**=i. Mivel pedig κ**x-hez és y-hoz ugyanazt az individuumot rendeli, |[A(yx)]|,κ**=|A|,κ**. Ez azt jelenti, hogy |xyA|,κ=i, tehát |x[A(yx)]xyA|,κ=i ebben az esetben is.

Ezzel beláttuk, hogy a x[A(yx)]xyA formula logikai törvény.

Az előző fejezetben egy elsőrendű formula különböző interpretációkban és változókiértékelések mellett lehetséges igazságértékeit – prímkomponensei lehetséges igazságértékeinek függvényében – az ún. Quine-táblázatban gyűjtöttük össze. Jellemezzük most a Quine-táblázat segítségével az elsőrendű formulákat.

5.3.18. DEFINÍCIÓ. Az [Vν] nyelv egy A formulája tautologikusan igaz, ha a formula Quine-táblázatában A oszlopában csupa i igazságérték található. Jelölése: 0A.

5.3.19. LEMMA. Legyen A az [Vν] nyelv tetszőleges formulája. Ha A tautologikusan igaz, akkor logikailag is igaz, azaz ha 0A, akkor A.

BIZONYÍTÁS. Legyen A az [Vν] nyelv formulája, és A legyen tautologikusan igaz. Ekkor a Quine-táblázatnak a formulához tartozó oszlopában csupa i igazságérték található. Ha most tetszőleges interpretációban tetszőleges változókiértékelés mellett kiszámoljuk A prímkomponensei igazságértékeit, ezeket az igazságértékeket rendre megtalálhatjuk a Quine-táblázat valamely sorában az egyes prímkomponensek oszlopaiban. Ezért az A formula igazságértéke bármelyik interpretációban bármelyik változókiértékelés mellett csak i lehet, tehát A logikailag igaz.

Természetesen egy formula Quine-táblázatában lehetnek olyan sorok is, melyekben szereplő igazságértékeket az egyes oszlopokhoz tartozó prímkomponensek egyszerre egyetlen interpretációban egyetlen változókiértékelés mellett sem vehetik fel. Az ilyen formula bár nem tautologikusan igaz, elsőrendű logikai törvény még lehet.

Figure 5.4. Logikailag és tautologikusan igaz elsőrendű formulák

Logikailag és tautologikusan igaz elsőrendű formulák

5.3.20. PÉLDA.

  1. A (xP(x)xP(x))¬xP(x)xP(x) formula prímkomponensei xP(x) és xP(x). A formula Quine-féle táblázata a következő:

x P ( x )

x P ( x )

( x P ( x ) x P ( x ) ) ¬ x P ( x ) x P ( x )

i

i

i

i

h

i

h

i

i

h

h

i

A formula oszlopában csupa i igazságérték található, tehát a formula tautologikusan igaz, azaz logikailag is igaz.

  1. Az 5.2.16. példában pedig láttuk, hogy a ¬x¬P(x)xP(x) nem tautologikusan igaz formula, pedig logikailag igaz. Egy tetszőlegesen rögzített interpretációban ugyanis

    1. vagy |¬x¬P(x)|=h, így |¬x¬P(x)xP(x)|=i,

    2. vagy |¬x¬P(x)|=i, ekkor viszont |x¬P(x)|=h. Ez pedig azt jelenti, hogy minden κ változókiértékelés mellett |¬P(x)|,κ=h, azaz |P(x)|,κ=i, tehát |xP(x)|=i. Így viszont ebben az esetben is |¬x¬P(x)xP(x)|=i,

tehát a ¬x¬P(x)xP(x) formula logikai törvény.

Legyenek az A[Vν] formula prímkomponensei az A1,A2,,An prímformulák, és legyenek B1,B2,,Bn tetszőleges [Vν]-beli formulák. Írjuk most be egyidejűleg A-ban az Ai prímkomponens minden előfordulása helyére a Bi formulát (i=1,2,,n). Ez is formulahelyettesítés (a különböző prímkomponensek az ítéletlogikában különböző ítéletváltozók voltak), aminek az eredménye [Vν] egy formulája. Jelölje ezt a formulát a megszokott módon

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

5.3.21. LEMMA. Ha 0A, akkor 0A(A1,A2,,AnB1,B2,,Bn).

BIZONYÍTÁS. Legyen A tautologikusan igaz. Ekkor Quine-táblázatának A-hoz tartozó oszlopában csupa i igazságérték található.

  • Ha most a táblázat oszlopaiban az A1,A2,,An prímkomponensek helyett beírjuk rendre a B1,B2,,Bn formulákat, olyan igazságtáblát kapunk, melynek sorai azt mutatják, hogy különböző interpretációkban és változókiértékelések mellett az A(A1,A2,,AnB1,B2,,Bn) formula igazságértéke hogyan függhet B1,B2,,Bn igazságértékeitől. A táblázatból kiderül, hogy a formula igazságértéke a B1,B2,,Bn formulák igazságértékeitől függetlenül i.

  • Készítsük most el az A(A1,A2,,AnB1,B2,,Bn) formula Quine-táblázatát. E táblázat egy tetszőlegesen rögzített sorában az

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

formula prímkomponensei lehetséges igazságértékei alapján először ki kell számítani B1,B2,,Bn igazságértékeit. Az előbbi igazságtábla alapján viszont tudjuk, hogy ezek bármilyenek, az

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

formula oszlopába i igazságérték fog kerülni.

Tehát A(A1,A2,,AnB1,B2,,Bn) tautologikusan igaz.

5.3.22. TÉTEL. Legyenek A,B és C tetszőleges elsőrendű logikai formulák az [Vν] nyelvben. A következő formulák elsőrendű logikai törvények:

bővítés előtaggal

A ( B A )

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

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

A ( B A B )

A B A  és ABB

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

A A B  és BAB

reductio ad absurdum

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

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

¬ ¬ A A

a kizárt harmadik törvénye

A ¬ A

ellentmondás törvénye

¬ ( A ¬ A )

az azonosság törvénye

A A

tranzitivitás

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

ellentmondásból bármi következik

A ( ¬ A B )

Peirce-törvény

( ( A B ) A ) A

BIZONYÍTÁS. Többet fogunk belátni: a felsorolt formulák tautologikusan igazak; az 5.3.19. lemma alapján ekkor azt mondhatjuk, hogy a formulák logikailag is igazak. Ha az A,B,C formulák rendre egy elsőrendű logikai nyelv atomi formulái, tautologikus igazságukat Quine-táblával könnyű igazolni. Majd az atomi formulák helyére rendre tetszőleges elsőrendű formulákat helyettesítve az 5.3.21. lemma ezen formulák tautologikus igazságát is bizonyítja.

Az elsőrendű logikában nem csak prímformulákat helyettesíthetünk más formulákkal. Az 5.1.37. definícióban definiáltuk egy predikátumszimbólum formális predikátummal való helyettesítését. Egy elsőrendű formulában a helyettesítés szabályos elvégzésének eredménye egy újabb elsőrendű formula. Be lehet látni, hogy logikai törvényekből a predikátumszimbólumok formális predikátumokkal való szabályos helyettesítése során újabb logikai törvényeket állíthatunk elő. Az ezzel kapcsolatos tételt most is bizonyítás nélkül közöljük.

5.3.23. TÉTEL. Legyen A egy elsőrendű formula, F egy (π1,π2,,πk) alakú x1x2xkF formális predikátum, P pedig egy (π1,π2,,πk) alakú predikátumszimbólum. Ha A, akkor A(PF).

5.3.24. DEFINÍCIÓ. Legyenek A és B az [Vν] nyelv tetszőleges formulái. Azt mondjuk, hogy az A és a B elsőrendű formulák logikailag ekvivalensek, és ezt a tényt úgy jelöljük, hogy AB, ha minden interpretációban és κ változókiértékelés mellett |A|,κ=|B|,κ.

5.3.25. PÉLDA.

  1. A ¬xP(x) és a x¬P(x) formulák logikailag ekvivalensek, ugyanis tetszőlegesen rögzített interpretációban és κ változókiértékelés mellett két eset lehetséges:

    1. Ha |¬xP(x)|=i, akkor |xP(x)|=h, azaz van κ-nak olyan κ*x-variánsa, hogy |P(x)|,κ*=h, tehát |¬P(x)|,κ*=i, azaz |x¬P(x)|=i.

    2. Ha pedig |¬xP(x)|=h, akkor |xP(x)|=i, azaz κ-nak minden κ*x-variánsa olyan, hogy |P(x)|,κ*=i, tehát |¬P(x)|,κ*=h, azaz |x¬P(x)|=h.

    Ezek szerint |¬xP(x)|,κ=|x¬P(x)|,κ minden interpretációban minden változókiértékelés mellett.

  2. A xyQ(x,y) formula viszont nem ekvivalens a yxQ(x,y) formulával. Vizsgáljuk meg ugyanis a formulák igazságértékét az p2 nyelv p2 interpretációjában.

    1. | x y Q ( x , y ) | p 2 = i , mert ,,mindhárom” x-variáns változókiértékeléshez van olyan y-variáns változókiértékelés, hogy mellette Q(x,y)i igazságértékű. Legyen ugyanis κ1 olyan, hogy κ1(x)=a, κ1(y)=a, κ2 olyan, hogy κ2(x)=b, κ2(y)=b és κ3 olyan, hogy κ3(x)=c, κ3(y)=a. Ekkor

| Q ( x , y ) | p 2 , κ 1 = | Q ( x , y ) | p 2 , κ 2 = | Q ( x , y ) | p 2 , κ 3 = i .

  1. | y x Q ( x , y ) | p 2 = h , mert ,,mindhárom” y-variáns változókiértékeléshez van olyan x-variáns változókiértékelés, hogy mellette Q(x,y)h igazságértékű. Legyen ugyanis κ1 olyan, hogy κ1(y)=a, κ1(x)=b, κ2 olyan, hogy κ2(y)=b, κ2(x)=a és κ3 olyan, hogy κ3(y)=c, κ3(x)=a. Ekkor

| Q ( x , y ) | p 2 , κ 1 = | Q ( x , y ) | p 2 , κ 2 = | Q ( x , y ) | p 2 , κ 3 = h .

5.3.26. LEMMA. Legyenek A és B az [Vν] nyelv tetszőleges formulái. AB pontosan akkor, ha (AB)(BA).

BIZONYÍTÁS.

  1. Tegyük fel, hogy AB, azaz minden interpretációban és κ változókiértékelés mellett |A|,κ=|B|,κ. Rögzítsünk most tetszőlegesen egy interpretációt és egy κ változókiértékelést. Az 5.2.9. definíció miatt ekkor

| ( A B ) ( B A ) | , κ = ( | A | , κ | B | , κ ) ( | B | , κ | A | , κ ) .

Így akár |A|,κ=|B|,κ=i, akár |A|,κ=|B|,κ=h, |A|,κ|B|,κ=i és |B|,κ|A|,κ=i, tehát a konjunkciójuk is i igazságértékű, így |(AB)(BA)|,κ is i igazságértékű. Mivel -t és κ-t tetszőlegesen rögzítettük, (AB)(BA) logikailag igaz.

  1. Tegyük fel, hogy (AB)(BA), azaz minden interpretációban és κ változókiértékelés mellett |(AB)(BA)|,κ=i, tehát az 5.2.9. definíció miatt minden interpretációban és κ változókiértékelés mellett (|A|,κ|B|,κ)(|B|,κ|A|,κ)=i is. Ez azt jelenti, hogy ha rögzítünk tetszőlegesen egy interpretációt és egy κ változókiértékelést, akkor |A|,κ|B|,κ=i és |B|,κ|A|,κ=i.

    1. Ha |A|,κ=i, akkor |A|,κ|B|,κ=i miatt |B|,κ=i.

    2. Ha |A|,κ=h, akkor |B|,κ|A|,κ=i miatt |B|,κ=h.

Tehát |A|,κ=|B|,κ.

Ezzel a lemmát bebizonyítottuk.

Most néhány – kvantált formulákkal kapcsolatos – logikai ekvivalenciát sorolunk fel. Az első kettőt könnyű belátni az 5.2.12. lemma segítségével. A többi igazolása egymáshoz nagyon hasonló módon történik, így De Morgan kvantoros törvényei és az egyoldali kvantorkiemelési szabályok közül is csak egyet-egyet bizonyítunk.

5.3.27. TÉTEL. Ha A az [Vν] nyelv olyan formulája, hogy xPar (A), akkor

x A A és x A A .

5.3.28. TÉTEL. Legyen A az [Vν] nyelv tetszőleges formulája. Ekkor

x y A y x A é s x y A y x A .

5.3.29. TÉTEL. (DE MORGAN KVANTOROS TÖRVÉNYEI)

Legyen A az [Vν] nyelv tetszőleges formulája. Ekkor

¬ x A x ¬ A és ¬ x A x ¬ A .

BIZONYÍTÁS. Legyen [Vν]-nek tetszőleges interpretációja és κ az interpretációban tetszőleges változókiértékelés. Vizsgáljuk meg a ¬xA formula igazságértékét -ben κ mellett. Két eset lehetséges:

  1. Ha |¬xA|,κ=i, akkor |xA|,κ=h, tehát κ minden κx-variánsa esetén |A|,κ=h. Ez azt jelenti, hogy κ minden κx-variánsa esetén |¬A|,κ=i, azaz az 5.2.9. definíció szerint |x¬A|,κ=i.

  2. Fordítva, ha |¬xA|,κ=h, akkor |xA|,κ=i, tehát van κ-nak olyan κ'x-variánsa, hogy |A|,κ'=i, azaz |¬A|,κ'=h. Ez pedig az 5.2.9. definíció szerint azt jelenti, hogy |x¬A|,κ=h.

Mivel tetszőleges interpretációban és κ változókiértékelés mellett

| ¬ x A | , κ = | x ¬ A | , κ ,

beláttuk, hogy a két formula logikailag ekvivalens. A ¬xAx¬A hasonlóan bizonyítható.

5.3.30. TÉTEL. (KVANTOROK EGYOLDALI KIEMELÉSE.)

Legyenek A és B az [Vν] nyelv tetszőleges formulái. Ha xPar (A), akkor

A x B x ( A B )

A x B x ( A B )

A x B x ( A B )

A x B x ( A B )

A x B x ( A B )

A x B x ( A B )

x B A x ( B A )

x B A x ( B A )

BIZONYÍTÁS. Egyedül a xBAx(BA) ekvivalenciát bizonyítjuk, a többit az olvasóra hagyjuk. Legyen [Vν]-nek tetszőleges interpretációja és κ az interpretációban tetszőleges változókiértékelés. Vizsgáljuk meg a xBA formula igazságértékét -ben κ mellett. Két eset lehetséges:

  1. Ha |xBA|,κ=i, akkor vagy |xB|,κ=h, vagy |A|,κ=i.

  • Ha |xB|,κ=h, akkor van κ-nak olyan κx-variánsa, hogy |B|,κ=h. Ez azt jelenti, hogy |BA|,κ=i, tehát |x(BA)|,κ=i.

  • Ha pedig |A|,κ=i, akkor nyilván |BA|,κ=i, tehát most is |x(BA)|,κ=i.

  1. Másrészt ha |xBA|,κ=h, akkor |xB|,κ=i és |A|,κ=h. Ez azt jelenti, hogy κ minden κx-variánsa esetén |B|,κ=i, és mivel xPar (A), |A|,κ=h továbbra is. Tehát κ minden κx-variánsa esetén |BA|,κ=h, azaz |x(BA)|,κ=h.

Mivel tetszőleges interpretációban és κ változókiértékelés mellett

| x B A | , κ = | x ( B A ) | , κ ,

beláttuk, hogy a két formula logikailag ekvivalens.

5.3.31. TÉTEL. (KVANTOROK KÉTOLDALI KIEMELÉSE.)

Legyenek A és B az [Vν] nyelv tetszőleges formulái. Ekkor

x A x B x ( A B ) és x A x B x ( A B ) .

5.3.32. TÉTEL. Legyenek A és B az [Vν] nyelv tetszőleges formulái. Ha AB, akkor AB.

BIZONYÍTÁS. Nevezzük a bizonyítás során az A formulát jónak, ha minden olyan B formula esetén, melyre AB, AB is. A szerkezeti indukció elve segítségével igazolni fogjuk, hogy minden [Vν]-beli formula jó.

(alaplépés:) Legyen A atomi formula. Ekkor az 5.1.21. definíció szerint minden B formulára, ha AB, akkor B=A, így nyilván AB is. Tehát az atomi formulák jók.

(indukciós lépések:) A negációs, konjunkciós, diszjunkciós és implikációs formulák esetén a bizonyítást az olvasóra bízzuk.

Most vizsgáljunk egy kvantált formulát: QxA-t. A QxA-val kongruens formulák azok a QyB alakú formulák, melyekre A(xz)B(yz) minden olyan z változó esetén, amely különbözik a QxA-ban és a QyB-ben előforduló összes változótól. Az indukciós feltevésünk miatt A, és így a vele azonos szerkezetű A(xz) is jó, tehát A(xz)B(yz). Ez azt jelenti, hogy tetszőleges interpretációban és κ változókiértékelés mellett |A(xz)|,κ=|B(yz)|,κ. De az 5.2.15. tétel szerint ha

κ ( u ) { κ ( u ) ha u x , κ ( z ) ha u = x ,

akkor |A(xz)|,κ=|A|,κ, és ha

κ ( u ) { κ ( u ) ha u y , κ ( z ) ha u = y ,

akkor |B(yz)|,κ=|B|,κ, tehát |A|,κ=|B|,κ. Világos, hogy κ egyik x-variánsa, κ pedig egyik y-variánsa κ-nak. Továbbá ha κz-variánsaihoz az előzőekhez hasonlóan megkonstruáljuk κ-t és κ-t, megkapjuk κ összes x-variánsát és y-variánsát. Tehát κ minden κx-variánsa és κy-variánsa esetén |A|,κ=|B|,κ, ez pedig azt jelenti, hogy |QxA|,κ=|QyB|,κ. Mivel az igazságértékek egyenlősége tetszőleges és κ esetén fennáll, QxAQyB. Ezzel beláttuk, hogy QxA is jó.

Tehát a szerkezeti indukció elve szerint minden [Vν]-beli formula jó.

5.3.33. TÉTEL. Legyenek A és B az [Vν] nyelv tetszőleges formulái, x tetszőleges változó és t az x változóval megegyező fajtájú tetszőleges term. Ha AB, akkor [A(xt)][B(xt)].

BIZONYÍTÁS. Ha AB, akkor az 5.3.26. lemma szerint (AB)(BA). Ekkor viszont az 5.3.12. tétel miatt tetszőleges (xt) termhelyettesítés esetén [((AB)(BA))(xt)]. A termhelyettesítés szabályos végrehajtása szerint

[ ( ( A B ) ( B A ) ) ( x t ) ] = ( [ A ( x t ) ] [ B ( x t ) ] ) ( [ B ( x t ) ] [ A ( x t ) ] ) .

Ekkor pedig az 5.3.26. lemmát újból alkalmazva azt kapjuk, hogy [A(xt)][B(xt)].

5.3.34. DEFINÍCIÓ. Legyenek A és B az [Vν] nyelv tetszőleges formulái. Azt mondjuk, hogy az A és a B elsőrendű formulák tautologikusan ekvivalensek, és ezt a tényt úgy jelöljük, hogy A0B, ha a formulák közös Quine-táblázatában A és B oszlopában minden sorban azonos igazságérték található.

5.3.35. PÉLDA. A xP(x)xP(x) és a ¬xP(x)xP(x) formulák tautologikusan ekvivalensek. A közös Quine-féle táblázat a következő:

x P ( x )

x P ( x )

x P ( x ) x P ( x )

¬ x P ( x ) x P ( x )

i

i

i

i

i

h

h

h

h

i

i

i

h

h

i

i

5.3.36. LEMMA. Legyenek A és B az [Vν] nyelv tetszőleges formulái. Ha A0B, akkor AB.

BIZONYÍTÁS. Ha A0B, közös Quine-táblázatukban az A és B formulákhoz tartozó oszlopban minden sorban azonos igazságérték található. Készítsük el az (AB)(BA) formula Quine-táblázatát. (AB)(BA) prímkomponensei A vagy B prímkomponensei is. Tehát ha az (AB)(BA) Quine-táblázatában a prímkomponensek alá rendre egy sorba igazságértékeket írunk, ezek az igazságértékek megtalálhatók A és B közös Quine-táblázatában is a megfelelő prímkomponensek alatt rendre egy sorban. Mivel A-hoz és B-hez ebben a sorban (is) azonos igazságérték tartozik, így (AB)(BA) alá i igazságérték kerül. Tehát a Quine-táblázatban (AB)(BA) alatt csak i igazságérték lehet, így 0(AB)(BA). De ekkor 5.3.19. szerint (AB)(BA). Innen az 5.3.26. lemma alapján adódik az állítás.

5.3.37. MEGJEGYZÉS. Ezzel igazoltuk, hogy a tautologikus ekvivalencia erősebb a logikai ekvivalenciánál. Ez várható volt, hiszen a tautologikus ekvivalenciához a formulák ,,durvább”, ítéletlogikai szerkezetének is azonos jelentésűnek kell lennie.

5.3.38. LEMMA. Legyenek A,A,B1,B2,,Bn,C1,C2,,Cn, (n1) elsőrendű logikai formulák. Ha A0A és Bi0Ci minden i=1,2,,n-re, akkor

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

A lemmát a 4.3.10. tétel mintájára nem nehéz bizonyítani.

5.3.39. TÉTEL. Ha A,B,C elsőrendű logikai formulák, elsőrendű logikai törvény, pedig kielégíthetetlen formula, akkor az alább felsorolt formulák rendre logikailag ekvivalensek egymással:

asszociativitás

A ( B C ) ( A B ) C

A ( B C ) ( A B ) C

kommutativitás

A B B A

A B B A

disztributivitás

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

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

idempotencia

A A A

A A A

negáció az implikációban

A ¬ A ¬ A

¬ A A A

elimináció (elnyelés)

A ( B A ) A

A ( B A ) A

De Morgan törvényei

¬ ( A B ) ¬ A ¬ B

¬ ( A B ) ¬ A ¬ B

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

A A

A

A

A A

A

A ¬ A

A A

A

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

A B ¬ ( ¬ A ¬ B )

A B ¬ ( A ¬ B )

A B ¬ ( ¬ A ¬ B )

A B ¬ A B

A B ¬ ( A ¬ B )

A B ¬ A B

kétszeres tagadás

¬ ¬ A A

kontrapozíció

A B ¬ B ¬ A

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

A ( B C ) B ( A C )

implikáció konjunktív előtaggal

A B C A ( B C )

az implikáció öndisztributivitása

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

esetelemzés

A B C ( A C ) ( B C )

BIZONYÍTÁS. Többet fogunk most is belátni: a felsorolt formulapárok formulái tautologikusan ekvivalensek; ekkor az 5.3.36. lemma alapján azt mondhatjuk, hogy a formulák logikailag is ekvivalensek. Ha az A,B,C formulák rendre egy elsőrendű logikai nyelv atomi formulái, a felsorolt tautologikus ekvivalenciákat Quine-táblával könnyű igazolni. Majd az atomi formulák helyére rendre tetszőleges elsőrendű formulákat helyettesítve az 5.3.38. lemma bizonyítja ezen formulák tautologikus ekvivalenciáját.

Már tapasztaltuk (5.3.23. tétel), hogy az elsőrendű logikában nem csak prímformulákat helyettesíthetünk más formulákkal úgy, hogy a formula szemantikai tulajdonságát megtartsa. Be lehet látni, hogy ha logikailag ekvivalens formulákban egy predikátumszimbólumot egymással ekvivalens formulákból származtatott azonos alakú formális predikátumokkal szabályosan helyettesítünk, a nyert formulák egymással ekvivalensek maradnak. Az ezzel kapcsolatos tételt bizonyítás nélkül közöljük.

5.3.40. TÉTEL. Legyenek A és A elsőrendű formulák, F és F(π1,π2,,πk) alakú x1x2xkF, illetve x1x2xkF formális predikátumok, P pedig egy (π1,π2,,πk) alakú predikátumszimbólum. Ha AA és FF, akkor A(PF)A(PF).

Végül hasznos lesz, ha kiterjesztjük a kielégíthetőség, illetve a kielégíthetetlenség fogalmát elsőrendű formulahalmazokra is.

5.3.41. DEFINÍCIÓ. [ V ν ] formuláinak egy tetszőleges Γ halmaza kielégíthető, ha van [Vν]-nek olyan interpretációja és -ben olyan κ változókiértékelés, hogy |A|,κ=i minden AΓ-ra. Egyébként Γkielégíthetetlen.

Feladatok

5.3.1. FELADAT. Bizonyítsuk be, hogy az alábbi formulák kielégíthetők, de nem logikai törvények.

  1. x P ( x ) x P ( x )

  2. x P ( x ) P ( x )

  3. x ( P ( x ) R ( x ) ) x P ( x ) x R ( x )

  4. x P ( x ) x R ( x ) x ( P ( x ) R ( x ) )

  5. x Q ( x , x ) x y Q ( x , y )

  6. x y Q ( x , y ) x Q ( x , x )

  7. x y Q ( x , y ) y x Q ( x , y )

5.3.2. FELADAT. Kielégíthetők-e a következő formulák?

  1. x y ( Q ( x , x ) ¬ Q ( x , y ) )

  2. x y ( Q ( x , x ) z R ( x , y , z ) )

  3. x y z ( Q ( x , y ) ¬ ( Q ( y , z ) Q ( z , z ) ) )