3. Az ítéletlogika szemantikája (4.2)
3.1
Formula és jelentése
minden ítéletváltozó ( Vv) ha AJFF akkor AJFF ha A,BJFF akkor (A○B)JFF minden formula előáll az előző három eset véges sokszori alkalmazásával.
Egyszerű állítás
Összetett állítás
interpretáció {i,h}
Boole-értékelés {i,h}
Formula jelentése mindig igazságérték!
3.2
Formula változószáma
Formulában szereplő ítéletváltozók száma
3.3
Formula bázisa
Ítéletváltozók halmazának egy rögzített sorrendje.
3.4
Interpretáció
I: Vv { i , h }
3.5
L0-beli formulák I interpretációbeli Boole-értékelése
BI: L0 {i,h} függvény: 1. ha A prímformula, akkor BI(A) legyen I(A) 2. BI(A) legyen BI(A) 3. BI(A ○ B) legyen BI(A) ○ BI(B) stb.
3.6
Egy adott bázishoz tartozó összes interpretáció megadásának módjai
a) szemantikus fa b) igazságtábla
3.6.1 Szemantikus fa Legyenek X1, X2, …, Xn logikai változók. Az X1, X2, …, Xn összes interpretációját tartalmazó bináris teljes szemantikus fa, egy olyan n szintű bináris fa, melyben a szintek és a logikai változók közt 1-1 egyértelmű megfeleltetés van. Teljes fa: a fa az összes lehetséges leképezést tartalmazza. Bináris fa: a fa mindig 2-felé ágazik. Az Xi-hez rendelt szinten az élpárokban az egyik élhez Xi, a másikhoz Xi címkét írunk. Egy ág egy interpretáció. Példa: Írjunk az ABCA formulához tartozó szemantikus fát! G A A A1 B
A2
B
B
B B1 B2 C C C
C C1
C2
C3
C4
C
B3 C
C5
C6
B4 C C7
C C8
3.6.2 Igazságtábla (1) Alaptípus 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: 1-n-ig az i. oszlop fejlécében a formula i. bázisváltozója van az (n+1). oszlopban maga a formula van az egyes sorok az összes lehetséges interpretáció szisztematikus felsorolását tartalmazzák az (n+1). oszlop a formula Boole-értékét tartalmazza. (2) Kiterjesztett igazságtábla Olyan igazságtábla, mely ki vannak bővítve az egyes részformuláknak megfelelő oszlopokkal. Példa: A(BC) A i i
B i i
C i h
B h h
BC i h
A(BC) i h
i i h h h h
h h i i h h
i h i h i h
i i h h i i
i i i h i i
i i i i i i
(3) Kiterjesztett egyszerűen A kiterjesztett igazságtábla egy olyan egyszerűsítése, melyben csak az egyes logikai jeleknek ill. ítélet változóknak megfelelő oszlopok vannak, és minden logikai jel alá a hatáskörébe tartozó részformula igazság értéke kerül bejegyzésre (ahol ő a fő logikai összekötő jel). Példa: A(BC) A i i
i
( h i
B i h
i i
I. MOHÓ kiértékelési mód - mechanikusan II. LUSTA kiértékelési mód - egyes dolgokat felesleges kiértékelni - ha C igaz, akkor B-t nem kell kiértékelni - ha A hamis, akkor az implikáció mindig igaz. ig 2. csoport
3.7
Formula igazságtáblájának értelmezése
b: { i , h }n { i , h } b igaz halmaza ( Ai ) -{ i , h }n azon részhalmaza, melyhez b az igaz értéket rendeli. b hamis halmaza - { i , h }n azon részhalmaza, melyhez b a hamis értéket rendeli. Példa: A(BC) Ai = { (i,i,i);(i,h,i);(i,h,h);(h,i,i);(h,i,h);(h,h,i);(h,h,h) } Ah = { (i,i,h) } A 2 halmaz diszjunkt! Házi feladat: Írd fel a következő formulák igazságtábláját és i/h halmazát! (1) ((AB)B)A (2) (AB)AD
C) i i
3.8
Az igazságértékelés függvény
Ai: AAi Ah: AAh Ai / Ah megadása a gyakorlatban az igazságértékelés fával történik. Az igazságérétkelés fát a szerkezeti fa segítségével állítjuk elő: gyökér: a formula maga és i/h halmaz keresése gyerekek: a formula közvetlen részformulái a következő formában. a) (A)i
b) (A)h
a) (AB)i
Ai
Ai
b) (AB)h
Bi a) (AB)i
Ah
a) (AB)i Ai
Bi
Ah
b) (AB)h Ah
Ah
b) (AB)h
Bi
Ai
Bh
Bh
Megjegyzés: léteznek ellentmondásos ágak és fák is!
Példa: Határozzuk meg az XYZX formula jelentését igazságértékeléssel! (XYZX)i Ai (X)
h
(YZX) (YZ)i (Y)
i
i
(X)i (X)
Bh
X
Y
Z
h
-
-
-
i
i
h
-
-
h
(Z)i
(XYZX)h (X)i
Ah
(YZX)
X
Y
Z
i
h
-
i
-
h
h
(YZ)h (X)h (Y)h
(Z)h
(X)i
(X)i
Házi feladat: Adjuk meg szerkezeti fa (igazságértékelés fa) segítségével ((PQ)(P(QP)))h (azaz a formula hamis feltételét) ((P(QP))(PR))h (azaz a formula hamis feltételét)
4. Ítéletlogikai törvények (4.3) 4.1
Tautológia, kielégíthetőség, kielégíthetetlenség
Legyen I: Lo egy interpretációja, A egy Lo beli formula. I kielégíti A-t (I |=o A), ha BI(A)=igaz I modellje A-nak, ha BI (A)=igaz „A”
kielégíthető: ha Lo-nak van olyan I interpretációja, melyre I |= o A. kielégíthetetlen: ha A-nak nincs modellje. tautológia: - ha Lo minden I interpretációjára I |= o A. - ha A kielégíthetetlen.
1) Kielégíthetőség eldöntése: a. igazságtáblával Ha van olyan sor A igazságtáblájában, ahol a Boole-értéke „i”. b. igazságértékelés fával Ha Ai nem üres, azaz (A)i fában nem minden ág ellentmondásos. 2) Kielégíthetetlenség eldöntése: a. igazságtáblával Ha A igazságtáblájában minden sor Boole-értéke „h”. b. igazságértékelés fával Ha (A)i fában minden ág ellentmondásos, tehát Ai üres. 3) Tautológia tulajdonság eldöntése: a. igazságtáblával Ha A igazságtáblájában minden sor Boole-értéke „i”. b. igazságértékelés fával Ha (A)h fa minden ága ellentmondásos, tehát Ah üres. Házi feladat: Igazolja, hogy az alábbi formula kielégíthető: A=((PQ)(QP)) - igazságtáblával - igazságértékelés fával Ha kielégíthető, akkor adjon meg egy a formulát kielégítő interpretációt!
4.2
igazságkiértékelés
Jelentése: egy formulában szereplő ítéletváltozók rögzített -igazságkiértékelése mellett keressük a formula helyettesítési értékét. Jelölések:
kielégíti A-t: |=o A A kielégíthető : |=o A A azonosan igaz : |=o A A kielégíthetetlen: nem létezik , hogy |=o A
Példa: (XYZX)i fa alapján döntsük el, hogy a formula helyettesítési értéke a = ( h, i, i ) igazságkiértékelés esetében az ( X, Y, Z ) bázist használva mi lesz . (A) i (X)h
Ai (YZX)i (YZ)i
(X)i
(Y)i (X)h
X
Y
Z
h
-
-
-
i
i
h
-
-
(Z)i Mivel Ai-ben van illeszkedő ág, így az A formula helyettesítési értéke a megadott helyen: igaz.
4.3
Formulahalmazok
Egy = { F1, ... , Fn } formulahalmaz kielégíthető: ha van Lo-beli I / , hogy I |=o { F1, ... , Fn }, tehát I |=o F1 és ... és I |=o Fn. I modellje a formulahalmaznak, ha I kielégíti -t. kielégíthetetlen: ha -nak nincs modellje. TÉTEL: Bármely I-re I |=o { F1, ... , Fn } I |=o F1...Fn. Példa: Bizonyítsuk be, hogy a = { AB, AB} formulahalmaz kielégíthető! a) igazságtáblával: van olyan sor, ahol minden formulája igaz. A B AB i i i i h i h i i h h h
AB i h i i
b) igazságértékeléssel: ((AB)(AB))i nem minden ága ellentmondásos. ((AB)(AB))i (AB)i (AB)i (A)i (A)h
(B)i
(B)i (A)h (B)i
Házi feladat: Bizonyítsuk be, hogy = { PQ, PQ } formulahalmaz kielégíthetetlen, és a = { QQ, R(RQ) } formulahalmaz azonosan igaz.
4.4
Kielégíthetőségi tulajdonságok kapcsolata
4.5
Nevezetes Ítéletlogikai törvények
4.6
Tautológikusan ekvivalens formulák
1. Szemantikus következményfogalom Definíció:Tautológikus következmény ( formula hamaznak a B formula ): |=o B, ha I: I |=o , akkor I |=o B ( vagyis minden modellje B-nek is modellje ). Speciális esetek: - B tautológia: -nak következménye B - kielégíthetetlen: nem beszélünk következmény fogalomról.
Lemma 1: I: I |=o { A1, ... , An } I |=o A1...An Lemma 2: { A1, ... , An } |=o B A1...AnB kielégíthetetlen
5.1
Helyes Következtetési formák
Def.: Az ( { A1, ... , An }, B ) helyes következtetési forma, ha { A1, ... , An } kielégíthető és { A1, ... , An } tautológikus következménye B.
Példa: Bizonyítsuk be, hogy az ( { AB, A }, B ) helyes következtetési forma! a) igazságtábla: van = (AB)A-t kielégítő sor ( Lemma 1 ). A B i i i h h i h h
A i i h h
AB i h i i
i h h h
*
B következmény I h I h
b) lusta kiértékelés ”A” feltételformula I(A)=i Mivel AB feltételformula és I(A)=i I(B)=i, tehát van -t kielégítő interpretáció. És B következmény, hiszen minden -t kielégítő I-re: I(B)=i. c) igazságértékelés: van -t kielégítő interpretáció és B következmény, tehát helyes a következtetési forma. ((AB)A)i (AB)i (A)i (A)h
x
(B)i
5.2
Visszafele következtetés
Lemma 2: { A1, ... , An } |=o B A1...AnB kielégíthetetlen
5.3
Előre Következtetés
5.3.1 Legszűkebb következmény:
Hf.: Tk. 85. o. 4.4.2. feladat a), b)
MÓDSZER( def. ) - igazságtábla ( Tk. 77. old. ) - lusta kiértékelés ( Tk. 77. old. ) - igazságértékelés ( Tk. 78. old. ) VISSZAKÖVETKEZTETÉS 1) def. szerint a. igazságtábla b. lusta kiértékelés c. igazságértékelés 2) tétel szerint ( Lemma 2 ) a. igazságtábla ( Tk. 83. old. ) b. lusta kiértékelés ( Tk. 83. old. ) c. igazságértékelés ( Tk. 84. old. ) ELŐREKÖVETKEZTETÉS( tétel ) - igazságtábla ( Tk. 85. old. ) - lusta kiértékelés ( Tk. 85. old. ) - igazságértékelés
