Matematika | Logika » Logika zárthelyi dolgozat megoldással

Logika évfolyam zárthelyi dolgozat 2002. V 24 A csoport Ponthatárok (%-ban): 0 - 30: elégtelen (1) 31 - 47: elégséges (2) 48 - 64: közepes (3) 65 - 81: jó (4) 82 - kb. 120: jeles (5) 1. feladat: ∃x∀yQ( x, y ) ∃x∃z∀vR( x, y, z , v ) nem formula / zárt / nyitott - melyek a kötött változók? A B C ∧ ¬B B nem formula / diszjunkciós / konjunkciós / implikáció - melyik a fő műveleti jel? Igaz-e, hogy a ∀x(P( x ) ∧ Q( x )) ∀xP( x ) ∧ ∀xQ( x ) formula logikailag igaz? - Sorolja fel a prímkomponenseit! Írja fel a formula értéktábláját és ennek alapján indokolja a válaszát! Megoldás: - nyitott, a kötött változók: x, z, v; implikációs, a fő műveleti jel az első ; igen; - a prímkomponensek: ∀x(P( x ) ∧ Q( x )), ∀xP( x ), ∀xQ( x ). - az értéktábla és az indoklás: ∀x(P( x ) ∧ Q( x )) ∀xP( x ) ∀xQ(x ) ∀x(P( x ) ∧ Q( x )) ∀xP( x ) ∧ ∀xQ( x ) i h h h i i h h i h i h i i i i Ha a

lehetséges interpretációkat nézzük, csak ez a négy értékkombináció lehetséges, ezekben az esetekben viszont a formula értéke i. 2. feladat: Formalizálja az alábbi feltételeket: - Ha az órám jól jár, akkor beérek a gyakorlatra, de csak akkor. - Ha nem, jön időben a busz, akkor a gyakorlatra sem érek be. - Az biztos nem igaz, hogy a busz is időben jön és az órám is jól jár. - Ha nem igaz, hogy az órám jól jár, akkor a busz időben jön. Mi a legszűkebb következmény, mint leképezés és mint formula? Levonhatjuk-e azt a következtetést a feltételekből, hogy a busz időben jön? Ennek megmutatására használja a rezolúciós kalkulust! Oldja meg lineáris input rezolúciós levezetéssel! Adja meg a feltételformulákat olyan alakban, hogy azok a bizonyítás-elméleti levezetéshez felhasználhatók legyenek! Megoldás: O - jól jár az órám, B - a busz időben jön, G - beérek a gyakorlatra. O ↔ G ≡ (O G ) ∧ (G O ) ≡ (¬O ∨ G

) ∧ (¬G ∨ O ), - ¬ B ¬G ≡ B ∨ ¬ G , ¬(B ∧ O ) ≡ ¬B ∨ ¬O ≡ B ¬O ≡ O ¬B, ¬O B ≡ O ∨ B. Legszűkebb következmény: B G O O↔G ¬B ¬G ¬(B ∧ O ) i i i i h h h h i i h h i i h h i h i h i h i h i h h i i h h i i h i h i i i i h ¬O B A klózhalmaz: {¬O ∨ G , ¬G ∨ O, B ∨ ¬G , ¬B ∨ ¬O, O ∨ B} ∪ {¬B}. Egy lineáris input levezetés: 1. ¬B 2. B ∨ ¬G 3. ¬G rez(1,2) 4. ¬O ∨ G 5. ¬O rez(3,4) 6. O ∨ B 7. B rez(5,6) 8. ¬B 9. □ rez(7,8). A feltételformulák megadása bizonyítás-elméleti levezetéshez: O G, G O, ¬B ¬G, B ¬O, O ¬B, ¬O B. legszűkebb köv. (leképezés) h h h i h h h h legszűkebb köv. (formula) B ∧ ¬G ∧ ¬O 3. feladat: Adott a következő {i, h} {i, h} leképezés: X Y Z i i i i i i h h ¬X ∨ ¬Y ∨ Z i h i h ¬X ∨ Y ∨ ¬Z i h h i h i i h X ∨ ¬Y ∨ ¬Z h i h h X ∨ ¬Y ∨ Z h h i h X ∨ Y ∨ ¬Z h h h i 3 Adja meg a leképezést leíró KKNF-et!

Majd egyszerűsítse! Megoldás: A leképezést leíró KKNF: (¬X ∨ ¬Y ∨ Z ) ∧ (¬X ∨ Y ∨ ¬Z ) ∧ ( X ∨ ¬Y ∨ ¬Z ) ∧ ( X ∨ ¬Y ∨ Z ) ∧ ( X ∨ Y ∨ ¬Z ) A lehetséges egyszerűsítések: a) ¬Y ∨ Z (1.,4) b) Y ∨ ¬Z (2.,5) c) X ∨ ¬Y (3.,4) d) X ∨ ¬Z (3.,5) Nincs több egyszerűsítés! Az egyszerűsítés eredménye: (¬Y ∨ Z ) ∧ (Y ∨ ¬Z ) ∧ ( X ∨ ¬Y ) ∧ ( X ∨ ¬Z ). 4. feladat: Írja át az alábbi formulát - Prenex formába, - Skolem normál formába! Írja fel a formulát elsőrendű klózok konjunkciójaként! Adja meg az elsőrendű klózhalmazt! A formula: ∀x∃y (Q ( x, y ) ↔ ¬∃z (T ( x, z ) ∧ T ( z , y ))). Adja meg a Herbrand univerzumot! Adja meg a Herbrand bázist! Megoldás: Prenex: ∀x∃y (Q( x, y ) ↔ ¬∃z (T ( x, z ) ∧ T ( z , y ))) ∀x∃y ([Q( x, y ) ¬∃z (T ( x, z ) ∧ T ( z , y ))] ∧ [¬∃z (T ( x, z ) ∧ T ( z , y )) Q( x, y )]) ∀x∃y ([¬Q( x, y ) ∨ ¬∃z (T ( x, z )

∧ T ( z , y ))] ∧ [∃z (T ( x, z ) ∧ T ( z , y )) ∨ Q( x, y )]) ∀x∃y ([¬Q( x, y ) ∨ ∀z (¬T ( x, z ) ∨ ¬T ( z , y ))] ∧ [∃z (T ( x, z ) ∨ Q( x, y )) ∧ (T ( z , y ) ∨ Q( x, y ))]) ∀x∃y∀z ([¬Q(x, y ) ∨ (¬T ( x, z ) ∨ ¬T ( z , y ))] ∧ [∃v(T ( x, v ) ∨ Q( x, y )) ∧ (T (v, y ) ∨ Q( x, y ))]) ∀x∃y∀z∃v([¬Q( x, y ) ∨ ¬T ( x, z ) ∨ ¬T ( z , y )] ∧ [T ( x, v ) ∨ Q(x, y )] ∧ [T (v, y ) ∨ Q( x, y )]). Skolem: (y helyett f(x), v helyett g(x,z) Skolem függvények bevezetése után) ∀x∀z ([¬Q( x, f ( x )) ∨ ¬T ( x, z ) ∨ ¬T (z , f ( x ))] ∧ ∧ [T (x, g (x, z )) ∨ Q( x, f ( x ))] ∧ [T (g (x, z ), f ( x )) ∨ Q( x, f ( x ))]). A formula, mint elsőrendű klózok konjunkciója: ∀x∀z[¬Q( x, f ( x )) ∨ ¬T ( x, z ) ∨ ¬T ( z , f ( x ))] ∧ ∧ ∀x∀z[T (x, g ( x, z )) ∨ Q(x, f ( x ))] ∧ ∧ ∀x∀z[T (g ( x, z ), f (x )) ∨ Q( x, f ( x ))] Az elsőrendű klózhalmaz: {¬Q(x, f (x )) ∨

¬T (x, z ) ∨ ¬T (z, f (x )), T ( x, g ( x, z )) ∨ Q(x, f ( x )), T ( g ( x, z ), f (x )) ∨ Q( x, f ( x ))}. H ∞ = {a, f (a ), g (a, a ), f ( f (a )),.} H B = {Q(a, a ), T (a, a ), Q(a, f (a )),.} 5. feladat: Állapítsa meg, hogy a ∀x∃yP( y , x ) és a ∃y∀xP( y, x ) formulákat leíró nyelvnek mi a típusa! Hány lehetséges interpretációja lehet ennek a nyelvnek az {a, b} univerzumon? Legyen három lehetséges interpretáció P(a, a ) P(a, b ) P(b, a ) P(b, b ) σ1 σ2 σ3 i i h h h h i h i h i h σ 1 ,σ 2 ,σ 3 : Értékelje ki a formulákat mindhárom interpretációban! Adja meg a szemantikus fát, és jelölje be rajta a fenti három interpretációt! Van-e olyan interpretáció, amelyben (∀x∃yP( y , x )) = h és (∃y∀xP( y, x )) = i ? σ σ σ Megoldás: A formulákat leíró nyelv típusa: (2,-). A lehetséges interpretációk száma az {a, b} univerzumon: 16. A formulák kiértékelése a különböző interpretációkban:

(∀x∃yP( y, x ))σ (∀x∃yP( y, x ))σ (∀x∃yP( y, x ))σ 1 2 3 = h és (∃y∀xP( y, x )) 1 = h, σ = i és (∃y∀xP( y, x )) σ2 = h és (∃y∀xP( y, x )) = h, σ2 = h. (∃y∀xP( y, x ))σ = i σ P(a, a ) = P(a, b ) = P(b, a ) = P(b, b ) = i interpretációban lehet, itt azonban (∀x∃yP( y, x )) = i. A kérdéses σ interpretáció nem létezik, ugyanis csak a A szemantikus fa: P(a, b ) ¬P(a, b ) P(a, a ) ¬P(a, a ) M P(b, a ) P(b, b ) ¬P(b, a ) ¬P(b, b ) σ1 P(b, b ) P(b, a ) ¬P(b, b ) σ2 P(b, b ) ¬P(b, a ) ¬P(b, b ) σ3 M 6. feladat: Jelölje: AF (a, f M (c, d ) B(h, g ) ) - a apja f-nek, - d magasabb c-nél, - h-nak barátja g relációkat. Feltételek: - A fiúk magasabbak apjuknál. - János apja Péternek. - Péternek van olyan barátja, aki magasabb, mint ő. - János nem apja Péter egyetlen barátjának sem. - A magasabb reláció tranzitív. Következmény: - Van olyan személy, aki magasabb Jánosnál

és János nem apja neki. Formalizálja a megadott relációkat, és adja meg azt az elsőrendű klózhalmazt, amelyet használni kell, ha rezolúciós kalkulussal dolgozunk! Lássa be elsőrendű rezolúcióval (szorgalmi feladat: alaprezolúcióval Herbrand univerzumon), hogy a megadott feltételeknek a megadott következmény valóban következménye! Megoldás: A feltételek: ∀x∀y ( AF ( x, y ) M ( x, y )), - AF ( János, Péter ), ∃x(B(Péter , x ) ∧ M (Péter , x )), ∀x(B(Péter , x ) ¬AF ( János, x )), ∀x∀y∀z (M ( x, y ) ∧ M ( y, z ) M (x, z )). A következmény: ∃x(M ( János, x ) ∧ ¬AF ( János, x )). Az elsőrendű klózhalmaz: {¬AF (x, y ) ∨ M (x, y ), AF ( János, Péter ), B(Péter , C ), M (Péter , C ), ¬B(Péter , x ) ∨ ¬AF ( János, x ), ¬M ( x, y ) ∨ ¬M ( y, z ) ∨ M ( x, z )} ∪ {¬M (János, x ) ∨ AF ( János, x )}. H ∞ = {János, Péter , C}. Egy lehetséges rezolúciós levezetés: 1. ¬M ( János, x ) ∨ AF (

János, x ) ¬B(Péter , x ) ∨ ¬AF ( János, x ) 3. ¬B(Péter , x ) ∨ ¬M ( János, x ) 4. ¬M ( x1 , y1 ) ∨ ¬M ( y1 , z1 ) ∨ M ( x1 , z1 ) 5. ¬B(Péter , x ) ∨ ¬M ( János, y1 ) ∨ M ( y1 , x ) 6. B (Péter , C ) 7. ¬M ( János, y1 ) ∨ ¬M ( y1 , x ) 8. M (Péter , C ) 9. ¬M ( János, Péter ) 10. ¬AF ( x, y ) ∨ M ( x, y ) 11. ¬AF ( János, Péter ) 12. AF ( János, Péter ) 2. 13. □ rez(1,2) rez(3,4) {x1 / János, z1 / x} rez(5,6) {X / c} rez(7,8) {y1 / Péter} rez(9,10) {x / János, y / Péter} rez(11,12). Alaprezolúció Herbrand univerzumon: 1. ¬M ( János, C ) ∨ AF ( János, C ) ¬B(Péter , C ) ∨ ¬AF ( János, C ) 3. ¬B(Péter , C ) ∨ ¬M ( János, C ) rez(1,2) 4. B (Péter , C ) 5. ¬M ( János, C ) rez(3,4) 6. ¬M ( János, Péter ) ∨ ¬M (Péter , C ) ∨ M ( János, C ) 7. ¬M ( János, Péter ) ∨ ¬M (Péter , C ) rez(5,6) 8. M (Péter , C ) 9. ¬M ( János, Péter ) rez(7,8) 10. ¬AF ( János, Péter ) ∨ M ( János,

Péter ) 11. ¬AF ( János, Péter ) rez(9,10) 12. AF ( János, Péter ) 2. 13. □ rez(11,12)