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.

Az ítéletlogika nyelve – szemantika

Az ítéletlogika nyelve – szemantika

Az előző fejezetben megadtuk az ítéletlogikai formula fogalmát. Most szeretnénk megadni ezeknek a formuláknak a logikai jelentését. A legegyszerűbb formulák – a prímformulák – ítéletváltozók. Az ítéletváltozók az állítások halmazát futják be. Ha minden ítéletváltozóhoz megmondjuk, hogy épp melyik állítást jelöli, akkor azt is meghatároztuk egyúttal, hogy az ítéletváltozó milyen igazságértékű, azaz igaz vagy hamis állítást jelent. Ennek az információnak a rögzítését nevezzük interpretációnak. Egy interpretáció az X ítéletváltozóhoz az épp általa jelölt állítás igazságértékét rendeli. Legyen Vv az ítéletlogika nyelvében az ítéletváltozók halmaza.

4.2.1. DEFINÍCIÓ. 0 interpretációján egy :Vv{i,h} függvényt értünk.

Az ítéletváltozók jelentésének megadása után a logikai összekötőjelek értelmezésével foglalkozunk. Ezeket a jeleket logikai összekötők jelölésére szántuk, a 1. fejezetben pedig ezen összekötők értelmezésével megegyező logikai műveleteket is kiválasztottunk. A logikai összekötőjelek az interpretációkban ezek szerint az {i,h} halmazon értelmezett logikai műveleteket fognak jelenteni (hivatkozhatunk is logikai műveletként rájuk). Azt, hogy milyen igazságértéket rendelünk egy formulához a közvetlen részformulák igazságértékének függvényében, kiolvashatjuk a logikai műveletek művelettábláiból, amelyeket – mivel igazságértékeken hajtjuk végre a műveleteket – igazságtábláknak (4.2. táblázat) nevezünk.

Table 4.2. A logikai műveletek közös igazságtáblája

A

B

¬ A

A B

A B

A B

i

i

h

i

i

i

i

h

h

h

i

h

h

i

i

h

i

i

h

h

i

h

h

i


A logikai összekötőjelek jelentésének megadásával egy-egy interpretációban meghatározhatjuk minden formula igazságértékét (helyettesítési értékét), azaz az interpretációbeli logikai jelentését.

4.2.2. DEFINÍCIÓ. (0 SZEMANTIKÁJA.) 0-beli formulák interpretációbeli Boole-értékelése[7] a következő – a szerkezeti rekurzió elve szerint definiált – :0{i,h} függvény:

  1. ha A prímformula, akkor (A) legyen (A),

  2. ( ¬ A ) legyen ¬(A),

  3. ( A B ) legyen (A)(B),

  4. ( A B ) legyen (A)(B),

  5. ( A B ) legyen (A)(B).

4.2.3. MEGJEGYZÉS. Fel szeretnénk a figyelmet hívni arra, hogy a ¬, , és a definícióban ,,bal oldalon” az ítéletlogika nyelve ábécéjének szimbólumai, ,,jobb oldalon” pedig logikai műveletek.

4.2.4. TÉTEL. Ha az 1 és az 2 interpretációk ugyanazt az igazságértéket rendelik ítéletváltozók egy S halmazához, akkor a 1 és a 2 Boole-értékelések ugyanazt az igazságértéket rendelik minden olyan formulához, amelyben csak S-beli ítéletváltozók fordulnak elő.

BIZONYÍTÁS. Legyen S ítéletváltozók tetszőleges halmaza, és legyenek az 1 és az 2 interpretációk olyanok, hogy minden XS esetén 1(X)=2(X). Nevezzük a bizonyítás során most is jó formuláknak 0 azon formuláit, melyben nem csak S-beli ítéletváltozók fordulnak elő, illetve azokat amelyekben csak S-beli ítéletváltozók fordulnak elő, viszont 1 és a 2 ugyanazt az igazságértéket rendeli hozzájuk. A szerkezeti indukció elve segítségével igazolni fogjuk, hogy minden 0-beli formula jó. Mutassuk meg tehát, hogy a szerkezeti indukció alaplépésében és indukciós lépéseiben megfogalmazott feltételek teljesülnek:

(alaplépés:) Nyilvánvaló, hogy 0 minden prímformulája jó, hisz vagy nem eleme S-nek, akkor azért, vagy eleme S-nek, akkor pedig a feltevésünk miatt.

(indukciós lépések:) Ha feltesszük, hogy egy A0 jó és nem csak S-beli ítéletváltozók fordulnak benne elő, akkor ¬A-ban sem csak S-beli ítéletváltozók fordulnak elő, tehát jó. Továbbá ha A jó és csak S-beli ítéletváltozók fordulnak benne elő, akkor 1(A)=2(A), azaz A-hoz mindkét Boole-értékelés ugyanazt a vagy i, vagy h igazságértéket rendeli. Ha A-hoz mindkét Boole-értékelés i-t rendelt, akkor ¬A-hoz mindkettő h-t fog és fordítva, ha A-hoz mindkét Boole-értékelés h-t rendelt, akkor pedig ¬A-hoz mindkettő i igazságértéket fog rendelni, azaz ¬A is jó. Hasonlóan bizonyítható, hogy ha feltesszük, hogy A,B0 jók, akkor (AB) is jó. Ennek igazolását az olvasóra bízzuk.

A szerkezeti indukció elve szerint tehát minden 0-beli formula jó, azaz tetszőleges olyan A0 formula esetén, amelyben csak S-beli ítéletváltozók fordulnak elő, 1(A)=2(A).

Ezek szerint különböző interpretációkban a Boole-értékelés egy formulához különböző igazságértékeket rendelhet ugyan, de csak azokban az interpretációkban, amelyekben legalább egy, a formulában előforduló ítéletváltozóhoz más igazságérték tartozik. Egy formula igazságértéke csak a benne előforduló ítéletváltozók interpretálásától függ, meghatározásához tehát elegendő csak a kérdéses formula változóihoz rendelt igazságértékeket ismerni, azaz a formula egy interpretációját megadni. n különböző ítéletváltozót 2n különböző módon lehet interpretálni, azaz egy n-változós formulának 2n különböző interpretációja van.

Egy formula különböző interpretációit szemantikus fa segítségével szemléltethetjük. Nevezzük a formula ítéletváltozóinak egy rögzített sorrendjét bázisnak. A szemantikus fa egy olyan bináris fa, amelynek i-edik (i1) szintszámú csúcsa a bázis i-edik ítéletváltozójához tartozik, és egy-egy szint minden csúcsából pontosan két él indul, az egyik a szinthez rendelt ítéletváltozóval, a másik ennek negáltjával címkézve. Az X ítéletváltozó esetén jelentse az X címke azt, hogy az interpretáció i, a ¬X címke pedig azt, hogy h értéket rendel X-hez. Egy n-változós formula szemantikus fájában minden ág n élt tartalmaz, melyek a formula egy-egy interpretációját szemléltetik. A fának 2n különböző ága lesz, melyek a formula összes lehetséges interpretációját bemutatják.

4.2.5. PÉLDA. Az X,Y,Z. ítéletváltozókat tartalmazó formula szemantikus fája a következő:

4.2.6. DEFINÍCIÓ. Egy n-változós formula igazságtáblája egy olyan n+1 oszlopból és 2n sorból álló táblázat, melynek elemei igazságértékek. A táblázat fejlécében az i-edik (1in) oszlophoz a formula bázisának i-edik ítéletváltozója, az n+1-edik oszlophoz maga a formula van hozzárendelve. Az első n oszlopban az egyes sorokban az ítéletváltozókhoz megadjuk rendre a formula különböző interpretációit, majd a formula oszlopába minden sorba beírjuk a formula – a sorhoz tartozó interpretációbeli Boole-értékeléssel kapott – igazságértékét.

Table 4.3. Az (YZ)(Z¬X) formula igazságtáblája

X

Y

Z

(YZ)(Z¬X)

i

i

i

h

i

i

h

i

i

h

i

h

i

h

h

h

h

i

i

i

h

i

h

i

h

h

i

i

h

h

h

h


A 4.3. táblázatban láthatjuk az (YZ)(Z¬X) formula igazságtábláját. A táblázat fejléce mutatja, hogy a bázis, azaz a változók sorrendje X,Y,Z. Vegyük észre, hogy egy n-változós formula igazságtáblája egy b:{i,h}n{i,h}n-változós logikai művelet művelettáblája. A b műveletet szokás a formulával leírt műveletnek is nevezni. A b művelet az {i,h}n halmazt két diszjunkt részre osztja. A bigazhalmazán{i,h}n azon részhalmazát értjük, mely elemeihez b az i igazságértéket rendeli, hamishalmazán pedig azt, mely elemeihez bh igazságértéket rendel. Rögzített bázis esetén a formulához ilyen módon megadható művelet egyértelmű, a művelet igaz-, illetve hamishalmazát ezért nevezhetjük egyúttal a formula igaz-, illetve hamishalmazának.

4.2.7. PÉLDA. Ha a bázis X,Y,Z, akkor a 4.3. igazságtáblával definiált háromváltozós logikai művelet és egyúttal az (YZ)(Z¬X) formula igazhalmaza az

{ ( i , i , h ) , ( h , i , i ) , ( h , i , h ) , ( h , h , i ) }

halmaz, hamishalmaza pedig az

{ ( i , i , i ) , ( i , h , i ) , ( i , h , h ) , ( h , h , h ) }

halmaz.

Megállapíthatjuk tehát, hogy egy An-változós formula jelentése – rögzített bázis esetén – a formulával leírt bA:{i,h}n{i,h}n-változós logikai művelet, ahol az ítéletváltozókat interpretáló igazságérték n-esek a formula Ai-val jelölt igaz- vagy Ah-val jelölt hamishalmazába tartoznak. Az ítéletlogikai formulák szemantikája ezek után megadható úgy is, hogy megadunk egy olyan függvényt, amelyik minden formulához a formula igazhalmazát, vagy épp minden formulához a formula hamishalmazát rendeli. Ez az igazságértékelés[8] függvény, ami a logika modern tárgyalásában az ítéletlogika szemantikája. Ezt a függvényt úgy adjuk meg, hogy a különböző alakú formulák esetére rögzítjük közvetlen részformuláikon keresztül azokat a feltételeket, amelyeket teljesítő interpretációkban az illető formula igazságértéke i vagy éppen h lesz.

4.2.8. DEFINÍCIÓ. Legyen A tetszőleges ítéletlogikai formula. Határozzuk meg A-hoz az interpretációira vonatkozó φAi és φAh feltételeket a szerkezeti rekurzió elve szerint:

  1. Ha A prímformula, a φAi feltételt pontosan azok az interpretációk teljesítik, amelyekben (A)=i, a φAh feltételt pedig pontosan azok, amelyekben (A)=h.

  2. A φ(¬A)i feltételek pontosan akkor teljesülnek, ha teljesülnek a φAh feltételek.

  3. A φ(AB)i feltételek pontosan akkor teljesülnek, ha a φAi és a φBi feltételek együttesen is teljesülnek.

  4. A φ(AB)i feltételek pontosan akkor teljesülnek, ha a φAi vagy a φBi feltételek teljesülnek.

  5. A φ(AB)i feltételek pontosan akkor teljesülnek, ha a φAh vagy a φBi feltételek teljesülnek.

4.2.9. TÉTEL. Tetszőleges A ítéletlogikai formula esetén φAi feltételeket pontosan az Ai-beli interpretációk teljesítik.

BIZONYÍTÁS. A tétel bizonyításához a szerkezeti indukció elvét alkalmazzuk. Rögzítsük tetszőlegesen ítéletváltozóknak egy {X1,X2,,Xn} nemüres, véges halmazát. Vizsgáljuk azokat a formulákat, melyekben csak az X1,X2,,Xn ítéletváltozók fordulnak elő. Ezen formulák interpretációi – rögzített bázis mellett – az {i,h}n halmaz elemei. A 4.2.4. tétel miatt ha a j-edik ítéletváltozó nem fordul elő a formulában, akkor az (e1,e2,,ej1,i,ej+1,,en) és az (e1,e2,,ej1,h,ej+1,,en) interpretációkban azonos a formula igazságértéke, azaz vagy mindkét igazságérték n-es a formula igazhalmazának, vagy mindkettő a formula hamishalmazának eleme.

(alaplépés:) Ha A prímformula, akkor valamely 1kn-re A éppen Xk. Ekkor a φAi feltételt kielégítő interpretációk azok, melyben (Xk)=i, a többi ítéletváltozó pedig tetszőleges. Pontosan ezek az interpretációk elemei Ai-nek is.

(indukciós lépések:)

(i1) Tegyük fel, hogy a φAi feltételeket pont az Ai-beli interpretációk teljesítik. A definíció szerint a φ(¬A)i feltételek a φAh feltételekkel egyeznek meg. A φAh feltételeket éppen az Ah-beli interpretációk kell teljesítsék, hisz Ah={i,h}nAi. Az Ah-beli interpretációk pedig pontosan a (¬A)i-beli interpretációk. Azaz a φ(¬A)i feltételeket pont a (¬A)i-beli interpretációk teljesítik.

(i2) Az indukciós feltevésünk szerint a φAi feltételeket pont az Ai-beli, a φBi feltételeket pont az Bi-beli interpretációk teljesítik. A definíció szerint pedig a φ(AB)i feltételek pontosan akkor teljesülnek, ha a φAi és a φBi feltételek együttesen is teljesülnek. Az együttes feltételeket az AiBi-beli interpretációk fogják teljesíteni. Ezek az interpretációk az (AB)i-beli interpretációk. A φ(AB)i feltételek pontosan akkor teljesülnek, ha a φAi vagy a φBi feltételek teljesülnek. Legalább az egyik feltételrendszert az AiBi-beli interpretációk mindegyike (és csak ezek) teljesítik. Ezek az interpretációk az (AB)i-beli interpretációk. A φ(AB)i feltételek pontosan akkor teljesülnek, ha a φAh vagy a φBi feltételek teljesülnek. Legalább az egyik feltételrendszert az AhBi-beli interpretációk mindegyike (és csak ezek) teljesítik. Ezek az interpretációk pedig az (AB)i-beli interpretációk.

A szerkezeti indukció elve szerint tehát egy nemüres, véges ítéletváltozóhalmaz esetén a csak ezeket az ítéletváltozókat tartalmazó formulákra a φAi feltételeket pontosan az Ai-beli interpretációk teljesítik. Mivel az ítéletváltozóhalmazt tetszőlegesen rögzíthetjük, az állítás minden ítéletlogikai formulára fennáll.

Egy A formula φAi vagy φAh feltételeket kielégítő interpretációit az igazságértékelés-fa segítségével szemléltethetjük. Az igazságértékelés-fát a formula szerkezeti fájának felhasználásával állítjuk elő. A gyökérhez hozzárendeljük, hogy A melyik igazságértékre való igazságértékelés-feltételeit keressük, majd a gyökér alá A közvetlen részformulái kerülnek a megfelelő feltétel-előírással – egy ágon megjelenő egy vagy két csúcsba, illetve két ágon megjelenő egy-egy csúcsba – az alábbiak szerint:

Majd a gyökérhez a ✓ (feldolgozott) jelet rendeljük. Az eljárást rekurzívan folytatjuk, amíg egy ágon a fel nem dolgozott formulák

  1. mind ítéletváltozók nem lesznek, vagy

  2. ugyanarra a formulára egymásnak ellentmondó előírás nem jelenik meg.

Az (a) esetben az ágon előforduló ítéletváltozóknak az ágon rögzített igazságértékeit és az ágon nem szereplő ítéletváltozók tetszőleges igazságértékeit tartalmazó n-esek mind elemei φAi gyökér esetén a formula igazhalmazának, φAh gyökér esetén a formula hamishalmazának. A (b) esetben az ágon nem áll elő az igaz- vagy épp a hamishalmazba tartozó igazságérték n-es.

4.2.10. MEGJEGYZÉS. Előfordul, hogy az igazságértékelés-fában egy formula ,,feldolgozása” nem közvetlenül a formula alatti közvetlen szinten történik. Ekkor a formula alatti részfa minden levele alá odakerül a ,,feldolgozás eredménye”.

4.2.11. PÉLDA. Határozzuk meg az (YZ)(Z¬X) formula jelentését igazságértékeléssel.

Ehhez tekintsük a 4.4. ábrát. Az ábrán a × azt jelenti, hogy az ágon a feltételek teljesíthetetlenek. A formula igazhalmazába tartozó interpretációk:

X

Y

Z

-

i

h

h

i

-

h

-

i

vagyis az {(i,i,h),(h,i,i),(h,i,h),(h,h,i)} halmaz.

Figure 4.4. Az (YZ)(Z¬X) formula igazságértékelés-fája

Az (Y∨Z)∧(Z⊃¬X) formula igazságértékelés-fája

Az igazságértékelés mint eszköz megkönnyíti a formulák igazságértékének adott interpretációban való meghatározását is. Az igazságértékelés megmutatja azokat az eseteket, amikor a formula valamelyik közvetlen részformulájának igazságértéke egyedül is meghatározza a formula igazságértékét. Továbbá azt is megadja, hogy mely ítéletváltozók igazságértéke szükséges a formula igazságértékének meghatározásához. A formula igazságérték-meghatározásának ezt a módját szokás ,,lusta” módszernek is nevezni.

4.2.12. PÉLDA. Nézzük meg az {(i,i,h)} interpretációban a fenti formula igazságértékét. Ahogy haladunk az igazságértékelés-fában lefelé, azt kapjuk az egyik ágon, hogy az olyan interpretációk lehetnek az igazhalmaz elemei, ahol Y igazságértéke i, Z igazságértéke h, az X igazságértéke pedig tetszőleges. Mivel a vizsgált interpretáció pont ilyen, ezért a formula igazságértéke ebben az interpretációban i.

Sok esetben az igazságtábla még megfelelő eszköz, ezért részletesebben foglalkozunk az igazságtáblák technikai kérdéseivel. Egy igazságtáblában a formula igazságértéke kiszámításának megkönnyítésére vezették be a kiterjesztett igazságtáblát. Ez egy olyan igazságtábla, melyben az ítéletváltozókhoz és a formulához tartozó oszlopok mellett rendre a formula további részformuláihoz tartozó oszlopok is megjelennek. Tulajdonképpen a szerkezeti fában megjelenő részformulák vannak itt felsorolva. Az egyes sorokban az ítéletváltozókhoz most is megadjuk az összes különböző interpretációt, majd beírjuk a megfelelő oszlopokba – az ahhoz a sorhoz tartozó interpretációbeli igazságértékelés alapján – a formula részformuláihoz rendelt igazságértékeket.

Table 4.5. Kiterjesztett igazságtábla

X

Y

Z

Y Z

¬ X

Z ¬ X

( Y Z ) ( Z ¬ X )

i

i

i

i

h

h

h

i

i

h

i

h

i

i

i

h

i

i

h

h

h

i

h

h

h

h

i

h

h

i

i

i

i

i

i

h

i

h

i

i

i

i

h

h

i

i

i

i

i

h

h

h

h

i

i

h


Szokás a kiterjesztett igazságtáblát egyszerűbb formában is felírni: a formulában előforduló betűkhöz tartoznak a táblázat oszlopai, az ítéletváltozók interpretációbeli igazságértékeit minden ítéletváltozó alá beírjuk, az összetett részformulák igazságértékei pedig közvetlenül a részformulák fő logikai összekötőjelei alá kerülnek.

Table 4.6. Kiterjesztett igazságtábla egyszerűen

(Y

Z)

(Z

¬

X)

i

i

i

h

i

h

h

i

i

i

h

i

h

i

h

i

h

i

i

h

i

h

h

i

h

h

h

h

h

i

h

i

i

i

i

i

i

i

i

h

i

i

h

i

h

i

i

h

h

i

i

i

i

i

i

h

h

h

h

h

h

i

i

h


További egyszerűsítésre ad lehetőséget – mint azt a szemantika definiálásánál láttuk –, hogy a formula különböző interpretációbeli igazságértékeinek kiszámításához nem feltétlenül szükséges tudni minden részformulájának igazságértékét. Az igazságtábla lusta módszerrel történő készítése során ha egy formula – mondjuk bal oldali – közvetlen részformulájának igazságértéke egyedül is meghatározza a formula igazságértékét, a másik közvetlen részformula igazságértékének meghatározását elhagyjuk.

Table 4.7. Kiterjesztett igazságtábla lusta módszerrel

X

Y

Z

Y Z

¬ X

Z ¬ X

( Y Z ) ( Z ¬ X )

i

i

i

i

h

h

h

i

i

h

i

i

i

i

h

i

i

h

h

h

i

h

h

h

h

h

i

i

i

i

i

i

h

i

h

i

i

i

h

h

i

i

i

i

i

h

h

h

h

h


Table 4.8. Kiterjesztett igazságtábla lusta módszerrel egyszerűen

(Y

Z)

(Z

¬

X)

i

i

h

i

h

h

i

i

i

i

h

i

h

i

i

h

i

h

h

i

h

h

h

h

i

i

i

i

i

i

h

i

i

i

h

i

h

i

i

i

i

i

i

h

h

h

h

h


4.2.13. TÉTEL. Legyenek A,B1,B2,,Bn,C1,C2,,Cn, (n1) tetszőleges ítéletlogikai formulák, és legyen 0 egy interpretációja. Ha minden i=1,2,,n-re (Bi)=(Ci), akkor

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

= ( A ( X 1 , X 2 , , X n C 1 , C 2 , , C n ) ) .

BIZONYÍTÁS. Rögzítsük most tetszőlegesen a B1,B2,,Bn,C1,C2,,Cn formulákat és -t úgy, hogy legyen (Bi)=(Ci) minden i=1,2,,n-re. Nevezzünk a bizonyítás során megint jónak egy A formulát, ha teljesül, hogy

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

= ( A ( X 1 , X 2 , , X n C 1 , C 2 , , C n ) ) .

(alaplépés:) Tegyük fel, hogy A prímformula. Ekkor ha A épp Xi, akkor az

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

éppen a Bi formula, az

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

formula pedig a Ci formula. Ha pedig A{X1,X2,,Xn}, akkor minkét formulahelyettesítés változatlanul hagyja A-t. Tehát 0 minden prímformulája jó.

(indukciós lépések:) Ha egy A0 jó, akkor

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

= ( A ( X 1 , X 2 , , X n C 1 , C 2 , , C n ) ) ,

így a 4.1.15. definíció miatt

( ¬ A ( X 1 , X 2 , , X n B 1 , B 2 , , B n ) ) =

= ( ¬ A ( X 1 , X 2 , , X n C 1 , C 2 , , C n ) ) ,

azaz ¬A is jó. Hasonlóan bizonyítható, hogy ha feltesszük azt, hogy A,B0 jók, akkor (AB) is jó. Ennek igazolását az olvasóra bízzuk.

A szerkezeti indukció elve szerint tehát minden 0-beli formula jó, amit végül is szerettünk volna bizonyítani.

4.2.14. PÉLDA. Legyenek most A az (YZ)(Z¬X), B1 a ¬Z és C1 a ZY formulák. Helyettesítsünk A-ban X helyére először B1-et, majd C1-et, és foglalkozzunk a kapott formulákkal abban az interpretációban, melyben (Y)=h, (Z)=i. Ekkor nyilván (B1)=(C1)=h. Ha kiszámoljuk a formulahelyettesítés során kapott formulák igazságértékeit -ben, láthatjuk, hogy ezek szintén azonosak.

Y

Z

¬ Z

( Y Z ) ( Z ¬ ¬ Z )

h

i

h

i

Y

Z

Z Y

( Y Z ) ( Z ¬ ( Z Y ) )

h

i

h

i

A 4.2.13. tétel következményeként adódik, hogy ha minden interpretációban rendre megegyeznek a helyettesítő formula igazságértékei, akkor minden interpretációban megegyeznek a formulahelyettesítés eredményeképp adódó formulák igazságértékei is.

4.2.15. PÉLDA. Legyen A most is az (YZ)(Z¬X) formula, és mondjuk B1 az Y, C1 pedig a ¬¬Y formulák. Az A-ban helyettesítsünk X helyére megint B1-et, majd C1-et. Világos, hogy minden interpretációban B1 és C1 azonos igazságértékű, az összevont igazságtáblából pedig láthatjuk, hogy a formulahelyettesítés során kapott formulák is azonos igazságértékűek lesznek.

Y

Z

Z Y

( Y Z ) ( Z ¬ Y )

( Y Z ) ( Z ¬ ¬ ¬ Y )

i

i

i

h

h

i

h

i

i

i

h

i

h

i

i

h

h

h

h

h

A fejezet végén bebizonyítunk egy érdekes lemmát:

4.2.16. LEMMA. Legyenek A,B1,B2,,Bn(n1) tetszőleges ítéletlogikai formulák, és legyen 10 egy interpretációja. Ha 20 olyan interpretációja, hogy

2 ( X ) = { 1 ( X ) h a X { X 1 , X 2 , , X n } , 1 ( B i ) h a X = X i v a l a m e l y i = 1,2, , n r e ,

akkor

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

BIZONYÍTÁS. Legyen b az A formula által leírt {i,h}n{i,h} logikai művelet az X1,X2,,Xn bázisban. Ekkor 2(A)=b(2(X1),2(X2),,2(Xn)) és

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

= b ( 1 ( B 1 ) , 1 ( B 2 ) , , 1 ( B n ) ) ,

Az 2 interpretációra vonatkozó feltételek miatt a jobb oldalon álló igazságértékek pedig egyenlőek.

A lemma lehetővé teszi a 4.2.13. tétel egyszerűbb bizonyítását is, amit meghagyunk az olvasónak.

Feladatok

4.2.1. FELADAT. Szemléltessük a következő formulák interpretációit szemantikus fával.

  1. ( X Y ) Z

  2. ( X Y ) ( ¬ Z V )

4.2.2. FELADAT. Határozzuk meg igazságtáblával a következő formulák igazságértékeit. Adjuk meg az igazságtábla által rögzített bázisban igaz-, illetve hamishalmazukat.

  1. X Y Z

  2. ( X Y ) ¬ Z

  3. ¬ X Y ¬ ( X ¬ Y )

4.2.3. FELADAT. Adjuk meg a következő formulák logikai jelentését igazságértékeléssel.

  1. X ¬ ( Y ¬ Z )

  2. ¬ ( X ( X Y ) )

  3. ( X ¬ Y ) Z

4.2.4. FELADAT. Legyenek A,B,C formulák. Határozzuk meg, hogy az alábbi formuláknak mi az igazságértéke A,B és C igazságértékének függvényében.

  1. ( A B ) ( B A )

  2. ( A B ) ¬ ( A B )



[7] Igazságkiértékelés, angolul truth evaluation.

[8] Angolul truth valuation.