MestersegesIntelligenciaZhLogikAgensPeldak2

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

76. Hogyan lehet megvizsgálni igazságtábla módszerrel, hogy egy állítás érvényes? Adjon rá egy példát.

Táblázatos formában felírjuk az állítást, és minden ítéletszimbólum-kombinációját. Az egyes kombinációkra kiszámítjuk az állítás értékét.Ha minden sorban IGAZ szerepel, akkor az állítás érvényes. Pl.:

P	Q	(P [math]\lor[/math] Q) [math]\lor[/math] (¬P [math]\land[/math] ¬Q)
HAMIS	HAMIS	IGAZ
HAMIS	IGAZ	IGAZ
IGAZ	HAMIS	IGAZ
IGAZ	IGAZ	IGAZ

77. “Az egzisztenciális kvantor eltüntetése” deduktív lépés párja “az egzisztenciális kvantor bevezetése”, miért azonban nincs párja “az univerzális kvantor eltüntetése” lépésnek?

A predikátum kalkulus, és az ítéletlogika képtelen az általánosításra. (pl.: kutya(A), kutya(B), kutya(C) nem implementálja hogy [math]\forall[/math]x kutya(x), mert lehet, hogy ¬kutya(D) ).

78. Lássa be, hogy a rezolúciós lépés egy deduktív lépés!

((¬A[math]\lor[/math]B) [math]\land[/math] (A[math]\lor[/math]B))[math]\Rightarrow[/math]B - (ezt kell levezetni, vagy igazságtáblával belátni – könnyű)

A kifejezés megfelel a [math]B \Rightarrow B [/math] kifejezésnek, ami mindig igaz.

79. Milyen az itélet logikai következtetés komplexitása és miért? Vonatkozik-e ugyanaz a predikátum kalkulus esetére is?

Nem praktikus, mert általában exponenciális n-ben(a szimbólumok száma), és a kielégíthetőség NP-teljes (lsd.: Gödel). Kivéve: Horn-klózok (polinomiális)

80. Itélet logika eldönthetõ-e? Indokolja a válaszát!

Igen, mert igazságtábla módszerrel bármilyen mondatról belátható igaz vagy hamis volta.

81. Alakítsa át klóz formára az alábbi állítást:

[math]\forall[/math]x Romai(x) [math]\Rightarrow[/math] (Lojalis(x, Cezar) [math]\land[/math] ¬Gyulol(x, Cezar)) [math]\lor[/math] (¬Lojalis(x,Cezar) [math]\land[/math] Gyulol(x,Cezar)))

1. [math]\forall[/math]x R(x) [math]\Rightarrow[/math] (L(x, C) [math]\land[/math] ¬G(x, C)) [math]\lor[/math] (¬L(x,C) [math]\land[/math] G(x,C)))
2. [math]\forall[/math]x ¬R(x) [math]\lor[/math] (L(x, C) [math]\land[/math] ¬G(x, C)) [math]\lor[/math] (¬L(x,C) [math]\land[/math] G(x,C)))
3. [math]\forall[/math]x (L(x, C) [math]\land[/math] ¬G(x, C)) [math]\lor[/math] (¬L(x,C) [math]\land[/math] G(x,C))) [math]\lor[/math]¬R(x)
4. (L(x, C) [math]\land[/math] ¬G(x, C)) [math]\lor[/math] (¬L(x,C) [math]\land[/math] G(x,C))) [math]\lor[/math]¬R(x)
5. ((¬L(x,C) [math]\land[/math] G(x,C)) [math]\lor[/math] L(x, C) [math]\lor[/math] ¬R(x)) [math]\land[/math] ((¬L(x,C) [math]\land[/math] G(x,C)) [math]\lor[/math] ¬G(x, C)) [math]\lor[/math]¬R(x))
6. (¬L(x,C) [math]\lor[/math] L(x, C) [math]\lor[/math] ¬R(x)) [math]\land[/math] (G(x,C) [math]\lor[/math] L(x, C) [math]\lor[/math]¬R(x)) [math]\land[/math] (¬L(x,C) [math]\lor[/math] ¬G(x, C) [math]\lor[/math]¬R(x)) [math]\land[/math] (G(x,C) [math]\lor[/math] ¬G(x, C) [math]\lor[/math]¬R(x))
7. (Igaz [math]\lor[/math] ¬R(x)) [math]\land[/math] (G(x,C) [math]\lor[/math] L(x, C) [math]\lor[/math]¬R(x)) [math]\land[/math] (¬L(x,C) [math]\lor[/math] ¬G(x, C)) [math]\lor[/math]¬R(x)) [math]\land[/math] (Igaz [math]\lor[/math]¬R(x))
8. Igaz [math]\land[/math] (G(x,C) [math]\lor[/math] L(x, C) [math]\lor[/math]¬R(x)) [math]\land[/math] (¬L(x,C) [math]\lor[/math] ¬G(x, C)) [math]\lor[/math]¬R(x)) [math]\land[/math] Igaz
9. (G(x,C) [math]\lor[/math] L(x, C) [math]\lor[/math]¬R(x)) [math]\land[/math] (¬L(x,C) [math]\lor[/math] ¬G(x, C)) [math]\lor[/math]¬R(x))
   1. G(x1,C) [math]\lor[/math] L(x1, C) [math]\lor[/math]¬R(x1)
   2. ¬L(x2,C) [math]\lor[/math] ¬G(x2, C)) [math]\lor[/math]¬R(x2)

82. Tekintsük a már megismert példát: “Városban vásárolunk. Vezetni csak Anna és Barbara tud. Anna nem megy Csaba vagy Dávid nélkül. Csaba követeli, hogy Erzsébet és Fanni is jöjjön. Ha Fanni megy, de Dávid marad, akkor Erzsébet is marad vele. És Dávid nem tud menni. Ki fog vezetni?”

_Itélet szimbólumok:

A	Anna megy (azaz vezethet)
B	Barbara megy
C	Csaba megy
D	Dávid megy
E	Erzsébet megy
F	Fanni megy

A történet leírása:

1. A [math]\lor[/math] B
2. A [math]\Rightarrow[/math] (C [math]\lor[/math] D)
3. C [math]\Rightarrow[/math] (E [math]\land[/math] F)
4. (F [math]\land[/math] ¬D) [math]\Rightarrow[/math] ¬E
5. ¬D

Lássa be rezolúcióval, hogy Barbara fog vezetni. Milyen rezolúciós stratégiát használt? A megoldás: klózok

• A [math]\lor[/math] B
• ¬A [math]\lor[/math] C [math]\lor[/math] D
• ¬C [math]\lor[/math] E
• ¬C [math]\lor[/math] F
• ¬F [math]\lor[/math] D [math]\lor[/math] ¬E
• ¬D
• ¬B

és a rezolúció (egy lehetséges lefolytatása):

• A [math]\lor[/math] B, ¬B = A
• ¬A [math]\lor[/math] C [math]\lor[/math] D, A = C [math]\lor[/math] D
• C [math]\lor[/math] D, ¬D = C
• ¬C [math]\lor[/math] E, C = E
• ¬C [math]\lor[/math] F, C = F
• ¬F [math]\lor[/math] D [math]\lor[/math] ¬E, ¬D = ¬F [math]\lor[/math] ¬E
• ¬F [math]\lor[/math] ¬E, E = ¬F
• ¬F, F = üres klóz

a jelen megoldásban használt rezolúciós stratégia: Set of Support

84. Melyike az alábbi mondatoknak érvényes, kielégíthetetlen, vagy egyik sem es miert?

a. Fûst [math]\Rightarrow[/math] Fûst a. Fûst [math]\Rightarrow[/math] Tûz a. (Fûst [math]\Rightarrow[/math] Tûz) [math]\Rightarrow[/math] (¬Fûst [math]\Rightarrow[/math] ¬Tûz) a. Fûst [math]\lor[/math] Tûz [math]\lor[/math] ¬Tûz a. (Fûst [math]\Rightarrow[/math] Tûz) [math]\Rightarrow[/math] ((Fûst [math]\land[/math] Hõ) [math]\Rightarrow[/math] Tûz) a. Nagy [math]\lor[/math] Buta [math]\lor[/math] (Nagy [math]\Rightarrow[/math] Buta)

Megoldások:

1. F [math]\Rightarrow[/math] F = ¬ F [math]\lor[/math] F = Igaz érvényes állítás
2. F [math]\Rightarrow[/math] T = ¬ F [math]\lor[/math] T egyik sem (kielégíthetõ)
3. (F [math]\Rightarrow[/math] T) [math]\Rightarrow[/math] (¬F [math]\Rightarrow[/math] ¬T) = F [math]\lor[/math] ¬T egyik sem
4. F [math]\lor[/math] T [math]\lor[/math] ¬T = F [math]\lor[/math] Igaz = Igaz érvényes állítás
5. (F [math]\Rightarrow[/math] T) [math]\Rightarrow[/math] ((F [math]\land[/math] H) [math]\Rightarrow[/math] T) = (F [math]\lor[/math] ¬F [math]\lor[/math] ¬H [math]\lor[/math] T) [math]\land[/math] (¬T [math]\lor[/math] ¬F [math]\lor[/math] ¬H [math]\lor[/math] T) = Igaz [math]\land[/math] Igaz = Igaz érvényes állítás
6. N [math]\lor[/math] B [math]\lor[/math] (N [math]\Rightarrow[/math] B) = N [math]\lor[/math] B [math]\lor[/math] ¬N [math]\lor[/math] B = Igaz érvényes állítás

85. Mitõl függ egy formális állítás logikai értéke?

A valóság állítás által reprezentált részének Igaz vagy Hamis voltától. (RIZSA!!!)

86. Mikor mondjuk, hogy egy állítás érvényes? Adjon rá példát.

Egy állítás érvényes, ha minden interpretációban, a világ minden állapotában igaz (magyarán, ha igaz attól függetlenül, hogy a benne szereplõ szimbólumoknak mi a szándékolt jelentése). Pl. ¬A[math]\lor[/math]A (tautológia)

87. Mikor mondjuk, hogy egy állítás kielégíthető? Adjon rá példát.

Egy állítás kielégíthető, ha létezik valamely interpretációja, amely valamely világban igaz. Egyébként kielégíthetetlen. Pl. A[math]\lor[/math]B

88. Mikor kielégíthetetlen egy állítás? Adjon rá példát.

Egy állítás kielégíthetetlen, ha minden interpretációban, a világ minden állapotában hamis, vagyis, ha nem létezik olyan világ, amelyben valamely interpretációja igaz lenne. Pl. ¬A[math]\land[/math]A

89. Mit jelent, hogy egy logika eldönthetõ, és mit az, hogy teljes? Milyenek ilyen szempontból az elsõrendû logika tulajdonságai?

• Eldönthető: Kimutatható, hogy egy állítás értéke hamis, vagy igaz (az algoritmus mindíg lefut)
• Teljes: Minden megoldást megtalál
• (elsőrendű log. – teljes, félig eldönthető, azaz a hamis álltásról nem mindig látható be, hogy hamis)

90. Milyen problémák lehetnek az itélet logikai ágenssel?

Túl sok szabály szükséges egy egyszerű probléma megoldásához is, nem képes kezelni a világban bekövetkező változásokat, és a relációkat.

91. Az elsőrendű logikában az apparátus milyen elemeibe épül be a világra vonatkozó tudás?

A logikai konstansokba, a függvény- és predikátum-nevekbe.

92. Milyenek az elsőrendű logika tulajdonságai?

• teljes (minden igaz állítás belátható annak)
• félig eldönthető (hamis állítás hamis volta nem mutatható ki)

93. Mi a [math]\forall[/math]és [math]\exists[/math] kapcsolata?

• ¬[math]\forall[/math] x P(x) = [math]\exists[/math] x ¬ P(x)
• ¬ [math]\exists[/math] xP(x) = [math]\forall[/math] x ¬ P(x)

94. Írja le predikátum kalkulus formalizmusával: Emberek sűrűn lakják a Földet. Jancsi is ember.

arra ügyelve, hogy az alkalmazott logikai átírásból ne következzen, hogy: Jancsi is sûrûn lakja a Földet. Lehet pl.

• ember(Jancsi)
• [math]\forall[/math]x[math]\forall[/math]y ember(x) [math]\land[/math] ember(y) [math]\Rightarrow[/math] kozellakik(x,y)

de lehet számtalan más módon is. A lényeg, hogy ne alakuljon a helyzet pl. az alábbi módon:

• [math]\forall[/math] x ember (x) [math]\Rightarrow[/math] sürûnlakja-a-földet (x)
• ember (Jancsi)

mert a Modus Ponens-bõl következik, hogy:

• sürûnlakja-a-földet (Jancsi)

=95. Lássa be (levezetéssel), hogy a Modus Ponens egy deduktív lépés!

A	B	((A[math]\Rightarrow[/math]B) [math]\land[/math] A)[math]\Rightarrow[/math]B
0	0	1
0	1	1
1	0	1
1	1	1

1. [math]((A \Rightarrow B) \land A)\Rightarrow B[/math]
2. [math]((\neg A \lor B) \land A)\Rightarrow B[/math]
3. [math]\neg ((\neg A \lor B) \land A) \lor B[/math]
4. [math]\neg (\neg A \lor B) \lor \neg A \lor B[/math]
5. [math](A \land \neg B) \lor \neg A \lor B[/math]
6. [math](A \lor \neg A) \land (\neg B \lor \neg A) \lor B[/math]
7. [math]\neg B \lor \neg A \lor B[/math]
8. igaz

96. Hogyan néz ki az elsõrendû logikai Modus Ponens? Milyen lényegi lépéssel bõvült az itélet logikához képest?

[math]\begin{tabular}{r} $E_1$ \\ $E_1 \Rightarrow E_2$ \\ \hline $E_2$ \end{tabular}[/math] vagy [math]\begin{tabular}{r} $P(A)$ \\ $\forall x P(x) \Rightarrow Q(x)$ \\ \hline $Q(A)$ \end{tabular}[/math]

(bővült : ÉS-bevezetés, UNIVERZÁLIS-elimináció)

100. Lássa be, hogy a rezolúció következtetési lépést: [math]\begin{tabular}{r} $A \lor B$ \\ $\neg A \lor C$ \\ \hline $B \lor C$ \end{tabular}[/math] egy tautológia.

1. [math](A \lor B) \land (\neg A \lor C) \Rightarrow (B \lor C)[/math]
2. [math]\neg((A \lor B) \land (\neg A \lor C)) \lor (B \lor C)[/math]
3. [math]\neg(A \lor B) \lor \neg(\neg A \lor C) \lor (B \lor C)[/math]
4. [math](\neg A \land \neg B) \lor (A \land \neg C) \lor (B \lor C)[/math]
5. [math](\neg A \land \neg B) \lor ((A \lor C) \land (\neg C \lor C)) \lor B[/math]
6. [math]\neg C \lor C[/math]
7. igaz

Belátható az igazságtábla módszerrel:

A	B	C	(A [math]\lor[/math] B)[math]\land[/math]( ¬A [math]\lor[/math] C)	B [math]\lor[/math] C
0	0	0	0	0
0	0	1	1	1

0	1	0	1	1
0	1	1	1	1
1	0	0	0	0
1	0	1	1	1
1	1	0	1	1
1	1	1	1	1