KREDIT
VADÁSZ

Az informatika logikai alapjai (Feladatok) - Mihálydeák Tamás

Országok listájaHungaryDebreceni EgyetemInformatikai KarProgramtervező informatikusAz Informatika Logikai AlapjaiJegyzetekAz informatika logikai alapjai (Feladatok) - Mihálydeák Tamás

Az informatika logikai alapjai
(Feladatok)
[email protected]
2006. november 27.

Mihálydeák Tamás

1.

Állításlogika
1. Bizonyítsa be, hogy az állításlogika minden formulájában a kezdo- és végzárójelek száma megegyezik! 2. Adja meg annak a függvénynek az induktív denícióját, amely minden formula esetén megadja a formulában szereplo zárójelek számát! 3. Adja meg annak a függvénynek az induktív denícióját, amely minden formula esetén megadja a formulában szereplo valódi logikai konstansok

(LC r = LC \ {(, )}) számát!
logikai összetettségét.)

(A deniálandó függvény adja meg a formula

4. Adja meg annak a függvénynek az induktív denícióját, amely minden formula esetén megadja, hogy a formulának legfeljebb hány részformulája lehet! 5. Adja meg annak a függvénynek az induktív denícióját, amely minden formula esetén megadja, hogy a formula szerkezeti fájának hány csúcsa van! 6. Legyen

RF(A) az A formula részformuláinak RF(A) halmaz induktív denícióját!

a halmaza.

Adja meg az

7. Készítsen egy olyan algoritmust, amely minden szóról eldönti, hogy formula-e! 8. Adja meg a kizáró vagy igazságtáblázatát!

LC Con mint abc feletti

9. Adja meg a következo formulák igazságtáblázatát: (a) (b)

((p q) ¬p) ((p (q r)) ((p q) (p r)))

10. Adja meg az alábbi formulák rövidített igazságtáblázatát: (a) (b)

((p q) p) ((p ¬r) q)
1

11. Adja meg a következo állítások állításlogikai szerkezetét ( az állításparamétereket csak atomi állítások rövidítésére használja): (a) Annak, hogy x páratlan elegendo feltétele az, hogy x prím legyen. (b) Az

s sorozat konvergenciájának szükséges feltétele az, hogy s korlátos

legyen. (c) Pistike csak akkor megy moziba, ha jó lmet adnak. (d) A sejk boldogságának szükséges és elégséges feltétele az, hogy sok pénze legyen. 12. Döntse el az alábbi formulahalmazokról, hogy kielégíthetoek-e! Ha valamelyik kielégíthetonek bizonyul, akkor adja meg a formulahalmaz egy modelljét is! (a) (b)

{¬p, (p ¬q), (p q)} {(p ¬q), p, q}

13. Bizonyítsa be, hogy egy kielégíthetetlen formulahalmazban mindig van hamis elem! 14. Bizonyítsa be, hogy egy kielégíthetetlen formulahalmaznak bármely bovítése kielégíthetetlen! 15. Igaz-e, hogy minden kielégíthetetlen formulahalmaznak van kielégítheto része? 16. Igaz-e, hogy minden kielégíthetetlen formulahalmaznak van nem üres kielégítheto része? 17. Igaz-e, hogy minden kielégítheto formulahalmaznak van kielégíthetetlen bovítése? 18. Igaz-e, hogy minden kielégítheto formulahalmaznak van kielégítheto bovítése? 19. Igaz-e, hogy egy kielégíthetetlen formulahalmaznak minden része kielégíthetetlen? 20. Kielégítheto vagy kielégíthetetlen az üres formulahalmaz? 21. Adjon példát kielégítheto, illetve kielégíthetetlen formulahalmazra! 22. Döntse el, hogy az alábbi formulák érvényes formulák-e (azaz logikai igazságok, tautológiák): (a) (b) (c) (d) (e) (f ) (g)

(((p q) q) q) ((p q) (p (q p))) ((p (¬(q r))) ((p r) q)) (((q r) (p q)) (p q)) (p (q (q p))) ((p q) (p r)) (((p q) p) p)

2

(h)

((p q) (q p))

23. Igazolja vagy cáfolja az alábbi állításokat: (a) A

(p q) (¬p q) ¬(p q)

formula logikailag ekvivalens a

((p q) (q p)) (¬q p)
formulával. formulával.

for-

mulával. (b) A (c) A formula logikailag ekvivalens a formula logikailag ekvivalens a

(p ¬q)

24. Bizonyítsa be, hogy esetén

AB

akkor és csak akkor, ha minden

interpretáció

|A| = |B|

.

25. Tegyük fel, hogy

A, B

olyan formulák, amelyekre teljesül, hogy

A B!

akkor és csak akkor, ha 26. Bizonyítsa be, hogy ha

B.

Bizonyítsa be, hogy ekkor

A B!

A B , akkor

A akkor és csak akkor, ha

27. Bizonyítsa be, hogy a logikai ekvivalencia a formulák halmazán értelmezett ekvivalencia-reláció! 28. Bizonyítsa be, hogy nek! 29. Bizonyítsa be, hogy

A

és

igazságtáblázataikban az

B logikailag ekvivalens akkor és csak akkor, ha A-hoz, illetve B -hez tartozó oszlopok megegyez-

A

olyan interpretáció, amely

B (A, B F orm) akkor és csak akkor, ha minden A-t igazzá teszi, igazzá teszi B -t is! A A
minden modellje modellje

30. Bizonyítsa be, hogy annak, hogy elégséges feltétele az, hogy 31. Bizonyítsa be, hogy amelyben

B (A, B F orm) szükséges B -nek is!

és

A

igaz és

A B

B

akkor és csak akkor, ha van olyan interpretáció,

hamis!

32. Bizonyítsa be, hogy egy kielégíthetetlen formulahalmaznak minden formula következménye! 33. Bizonyítsa be, hogy egy érvényes formula minden formulahalmaznak következménye! 34. Bizonyítsa be, hogy esetén

A

akkor és csak akkor, ha minden

interpretáció

A! AB A B
akkor és csak akkor, ha

35. Bizonyítsa be, hogy 36. Bizonyítsa be, hogy

(A B)! (A B)! A
és

akkor és csak akkor, ha

37. Bizonyítsa be, hogy a következményreláció monoton, azaz ha

F orm,

akkor



A!

38. Bizonyítsa be a dedukciótételt! 39. Bizonyítsa be a dedukciótétel megfordítását! 40. Bizonyítsa be a metszet tételt! 41. Igazak-e az alábbi állítások?

3

(a) Minden

A

formula esetén ha az

halmaz kielégítheto), akkor a (b) Ha (c) Ha (d) Ha (e) Ha

A formula kielégítheto ¬A is kielégítheto.

(azaz a

{A}

¬A ¬A A A

érvényes, akkor

A

nem kielégítheto.

kielégítheto, akkor

A

érvényes formula.

érvényes formula, akkor kielégítheto, akkor

A

kielégítheto.

A

érvényes formula.

(f ) Minden

A A A A

formula esetén létezik olyan

A-tól

különbözo

B

formula,

amelyre teljesül, hogy (g) Minden lens

A

B. A-val nem A B. A-tól
logikailag ekviva-

formula esetén létezik olyan

B

formula, amelyre teljesül, hogy

(h) Minden

formula esetén létezik olyan

különbözo

B

formula,

amelyre teljesül, hogy (i) Minden lens

B

A. A-val nem B A. A B A A
logikailag ekviva-

formula esetén létezik olyan

B

formula, amelyre teljesül, hogy

(j) Minden

A, B A, B A, B A A

formula esetén teljesül, hogy

vagy

B

A. B B A. A.

(k) Létezik olyan formula, amely minden formulának következménye. (l) Minden (m) Minden formula esetén teljesül, hogy ha formula esetén teljesül, hogy ha

B, B, A.

akkor akkor

(n) Létezik olyan (o) Ha (p) Ha (q) Ha (r) Ha (s) Ha (t) Ha (u) Ha (v) Ha

A, B

formula, hogy

A

B,

de

B



vagy és

B, B,

akkor



(A B). (A B). B. , A , C (B C). (A B). C. B. B.



akkor



A B,

akkor és és és és és



A

vagy

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



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

akkor akkor akkor akkor akkor

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

42. Bizonyítsa be az alábbiakat! (a) Ha (b) Ha (c) Ha (d) Ha (e) Ha (f ) Ha



A A A, A

és és


és

(A B), B, , B , A
akkor

akkor



B. C.



(A B). , (A B) ¬A. B.

, A , A

C B
és

C,

akkor

akkor és

A B. ¬B ,
akkor akkor



(A B),

43. Bizonyítsa be az alábbi logikai ekvivalenciákat, illetve a következményrelációk helyességét! (a) A negáció: i. A kettos negáció törvénye.

4

(b) A konjunkció és a diszjunkció: i. A konjunkció kommutatív, asszociatív, idempotens. ii. A diszjunkció kommutatív, asszociatív, idempotens. iii.

(A B)

A, (A B)

B.

iv. Az ellentmondás törvénye. v. vi.

A (A B). {(A B), ¬A}

B.

vii. A kizárt harmadik törvénye. viii. A konjunkció disztributív a diszjunkcióra nézve. ix. A diszjunkció disztributív a konjunkcióra nézve. x. Elnyelési tulajdonságok [(A (B A)) xi. De Morgan törvények. (c) Az implikáció: i.

A, (A (B A)) A].

AA

ii. Modus ponens (leválasztási szabály). iii. Modus tollens (indirekt cáfolás sémája). iv. Láncszabály. v. Redukció ad abszurdum [{(A vi. vii.

B), (A ¬B)}

¬A].

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

viii. Áthelyezési törvény. ix. A kontrapozíció törvénye. x. xi. xii. xiii. xiv.

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

(d) Materiális ekvivalencia: i. ii.

(e) Kifejezhetoség: i. ii. iii. iv. v. vi. vii.

44. Milyen formulákhoz létezik velük ekvivalens kitüntetett diszjunktív, illetve konjunktív normálforma? 45. Bizonyítsa be a természetes levezetés technikájának használatával, hogy helyes az alábbi szekvencia-átalakítás:

, A , ¬B

B ¬A

5

46. Adja meg a természetes levezetését az alábbi szekvenciáknak! (a) (b) (c) (d) (e)

AA A BA A ¬A AB AB
i. ii. iii. iv.

BA BA

(f ) Disztributivitási törvények:

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

(g) De Morgan törvények: i. ii. iii. iv. (h) (i) (j) (k) (l) (m) (n) (o) (p) (q) (r) (s)

A, ¬A ¬A

A (¬A B) AB B ¬A AB [A, A B B] A B, A A B, ¬B ¬B ¬A

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

2.

Elsorendu logika
1. Bizonyítsa be az alábbiakat, ha az

x

változó nem fordul elo szabadon az

A

formulában:

(a) (b)

xA A xA A

2. Bizonyítsa be az alábbiakat: (a) (b)

xyA yxA xyA yxA

6

3. Bizonyítsa be az alábbiakat: (a) (b)

xA xA yxA xyA

4. Bizonyítsa be a kvantikáció De Morgan törvényeit: (a) (b)

¬xA x¬A ¬xA x¬A

5. Bizonyítsa be az alábbiakat: (a) (b)

xA ¬x¬A xA ¬x¬A x
változó nem fordul elo szabadon az

6. Bizonyítsa be az alábbiakat, ha az

A

formulában:

(a) (b) (c) (d) (e) (f ) (g) (h)

A xB x(A B) A xB x(A B) A xB x(A B) A xB x(A B) A xB x(A B) A xB x(A B) xB A x(B A) xB A x(B A)

7. Bizonyítsa be az alábbiakat: (a) (b) (c) (d)

xA xB x(A B) xA xB x(A B) x(A B) xA xB xA xB x(A B)

7



Hasonló témájú dokumentumok

Hozzászólások

... 1. előadás 11.05-2 18. század 3. óra 4. állatrendszertan andorka bibó biogeográfia civilizáció deindividuáció deklaratív programozás dimat éghajlat építészet fmea gazdaságszociológia gepalap hrabal inverz és összetett függvény ipar jog kaffka kiefer ferenc kötődés közig közoktatási rendszer logika mikro német felvilágosodás objektum orientált őstörténet pár apróság platón politikatudomány rejtett dimenziók standardizálás számvitel szemiotika szervezes szív tartály tematika tétel valószínűségszámítás vám vésés zrínyi zsidó kultúra