Az informatika logikai alapjai 1

Az informatika logikai alapjai

1

1.1. Az alábbi idézetek1 közül melyek fejeznek ki állítást? Miért, illetve miért nem? (a) „Ez volt ám az ember, ha kellett, a gáton.” (b) „Szép öcsém, miért állsz ott a nap tüzében? ” (c) „Hej! ha én is, én is köztetek mehetnék, Szép magyar vitézek, aranyos leventék! ” (d) „Toldi György nagy úr volt.” (e) „Add ki, bátya, tüstént, ami engem illet; Add ki a jussomat: pénzt, paripát, fegyvert.” 1.2. Az alábbi kijelentő mondatok közül melyek állítások? (a) A hét páratlan szám. (b) A tíz nem osztható öttel. (c) Prímnek nevezzük azokat a természetes számokat, amelynek pontosan két osztójuk van (maga a szám és 1). (d) Minden ötnél nagyobb páratlan szám előáll három prímszám összegeként. (Goldbach-sejtés) (e) x ≥ 0. 1.3. Mi a probléma a logikában az alábbi kijelentő mondatokkal? (a) Fiam, aki Budapesten él, biológus. (b) A Tisza mellékfolyója árad. (c) Ez az állítás hamis. (d) A jelenleg uralkodó egyiptomi fáraó kopasz. 1.4. Vannak-e az alábbi mondatok között olyanok, amelyek ugyanazt az állítást fejezik ki? (a) Anna Béla férje. (b) Béla Anna felesége. (c) Csaba Anna unokája. (d) Van olyan gyermeke Annának, aki szülője Csabának. (e) Csaba valaki olyannak a gyermeke, akinek egyik szülője Anna. (f) Itt van a kutya elásva. (g) Ezen a helyen hantolták el az ebet. 1.5. Írjuk át a természetes nyelven megfogalmazott negációkat a ’¬’ jel használatával a következő mondatokban! A negációjel argumentumát határoljuk zárójelekkel. (a) A tíz osztható öttel. (b) A tíz nem osztható öttel. (c) Nem igaz, hogy a tíz nem osztható öttel. (d) Az ébenfa nem fehér. (e) Az ébenfa fekete. 1 Arany:

Toldi


2

(f) Tévedés, hogy az ébenfa nem fekete. (g) A csokoládét Péter megette. (h) A csokoládét nem Péter ette meg. (i) Nem igaz, hogy a csokoládét Péter megette. (j) Nincs igaza annak, aki tagadja, hogy a csokoládét Péter megette. (k) A probléma megoldható. (l) A probléma megoldhatatlan. (m) Tévedés az, hogy a probléma megoldhatatlan. 1.6. Írjuk át a természetes nyelven megfogalmazott negációkat a ¬, a konjunkciókat ∧ jelek használatával a következő mondatokban! Az argumentumokat határoljuk zárójelekkel. (a) „Hervad már ligetünk, s díszei hullanak.”

2

(b) „Egy kálomista pap s Csokonai Egymásnak voltak jóbarátai.”

3

(c) „Elment, nem látom többé már soha, Elment, nem látom többé már soha.”

4

(d) „Tán csodállak, ámde nem szeretlek . . . ”

5

(e) „Sem utódja, sem boldog őse, Sem rokona sem ismerőse nem vagyok senkinek.” 6 1.7. A köznyelvben a „vagy” kötőszót többféle értelemben használjuk: megengedő, kizáró és összeférhetetlen értelemben. Az alábbi mondatokban döntsük el, milyen értelemben használtuk a kötőszót. (a) Zoltánt vagy Gábort magammal viszem. (b) Vagy Zoltánt viszem magammal, vagy Gábort. (c) Egy angolul vagy németül beszélő idegenvezető kíséri a látogatókat. (d) Melyik állomás következik most? – kérdezi az egyik utas a másiktól. Vagy Téglás, vagy Újfehértó – feleli az. (e) Kérlek, Tomi, tedd le most a könyvet – mondta az apja. Vagy eszik az ember, vagy olvas. 1.8. Írjuk át a természetes nyelven megfogalmazott negációkat a ¬, a konjunkciókat ∧, a diszjunkciókat ∨ jelek használatával a következ* mondatokban! Az argumentumokat határoljuk zárójelekkel. (a) Elutazhatunk a Balatonra vagy a Mátrába, de nem utazhatunk a Balatonra is és a Mátrába is. (b) Anna elmegy és Bella itt marad, vagy mind a ketten elmennek, és Anna vissza sem jön, de Bella vagy visszajön, vagy mégsem jön vissza. (c) Kizárt, hogy nem vizsgázom le logikából vagy diszkrét matematikából elsőre, mégis izgulok. 1.9. Írjuk át a természetes nyelven megfogalmazott negációkat a ¬, a konjunkciókat ∧, a diszjunkciókat ∨, az implikációkat ⊃ jelek használatával a következő mondatokban! Az argumentumokat határoljuk zárójelekkel. 2 Berzsenyi:

A közelítő tél Csokonai 4 Ady: Egyedül a tengerrel 5 Petőfi: Az Alföld 6 Ady: Szeretném, ha szeretnének 3 Petőfi:


3

(a) „Ha meghalunk, hát meghalunk. . . ” 7 (b) „Ha egy úri lócsiszárral találkoztam s bevert sárral: Nem pöröltem, Félreálltam, letöröltem.” 8 (c) „Csak akkor születtek nagy dolgok, Ha bátrak voltak, akik mertek.” 9 (d) „Ó ha cinke volnék, útra kelnék, hömpölygŽ sugárban énekelnék - ” 10 1.10. Mely állítások fejezik ki ugyanazt? (a) Ha Julcsinak sikerül a dolgozata, megkapja a jelest. (b) Ha Julcsinak nem sikerül a dolgozata, nem kapja meg a jelest. (c) Ha Julcsi megkapta a jelest, sikerült a dolgozata. (d) Ha Julcsi nem kapta meg a jelest, nem sikerült a dolgozata. (e) Csak akkor kapja meg Julcsi a jelest, ha sikerül a dolgozata. (f) Csak akkor nem kapja meg Julcsi a jelest, ha nem sikerül a dolgozata. 1.11. „Reginam occidere nolite timere bonum est si omnes consentiunt ego non contradico.” – írta Merániai János esztergomi érsek híres levelében dodonai kétértelműséggel. Magyarul: „A királynőt megölni nem kell félnetek jó lesz ha mindnyájan beleegyeztek én nem ellenzem.” Adjuk meg a lehetséges jelentéseket, melyeket alább formalizáltunk: (a) ¬(a királynőt meg kell ölni)∧(félnetek jó lesz)∧(mindnyájan beleegyeztek ⊃ ¬(én beleegyeztem)) ∧ (én ellenzem) (b) ¬(a királynőt megölni félnetek kell)∧(jó lesz)∧(mindnyájan beleegyeztek ⊃ ¬(én ellenzem))

7 Ady:

Hadak útján Epilógus 9 Ady: A Tűz csiholója 10 Weöres: Buba éneke 8 Arany:


4

2.1. Legyenek X, Y és Z ítéletváltozók. Döntsük el, hogy az alábbi jelsorozatok (teljesen zárójelezett) formuláke, azaz olyan formulák, melyek megadásakor nem használunk a zárójelek elhagyásával kapcsolatos megállapodásokat és nem vezetünk be jelöléseket. (a) ((X ∧ Y )¬Z)

(g) (¬X)

(b) ((X ∧ Y ) ⊃ ¬Z)

(h) (X ⊃ ∨Y )

(c) ¬(X ∨ Y (i) ((¬X ⊃ Y ) ⊃ ¬(X ∨ Z)) (d) ¬(X ∨ Y )) (e) (Z ∨ XY )

(j) (X ⊃ Y ⊃ Z)

(f) (Z ∨ X ∧ Y )

(k) ¬(X ∨ Y ⊃ ¬¬Z)

2.2. Hagyjuk el a lehető legtöbb zárójelet a formulákból. (f) ((X ⊃ Y ) ≡ (¬X ∨ Y ))

(a) ((X ∨ Y ) ⊃ Z) (b) (¬(X ∨ Y ) ⊃ Z)

(g) (((X ∨ Y ) ⊃ ¬Z) ≡ (X ∧ ¬Z))

(c) ((¬(¬X ∨ Y ) ∧ Z) ⊃ (X ∨ Z)) (d) (((X ⊃ Y ) ∧ (Y ⊃ Z)) ⊃ (¬X ∨ Z)) (e) ¬(((X ⊃ Y ) ⊃ (Y ∨ Z)) ⊃ (¬X ∨ Z))

(h) ((X ∧ Y ) ⊃ Z) (i) (X ∧ (Y ⊃ Z))

2.3. Adjuk meg az alábbi formulák teljesen zárójelezett alakját. (a) X ∧ ¬Y ⊃ Z

(e) ¬X ∨ ¬¬Y

(b) ¬X ⊃ Y ∨ ¬Z

(f) Y ⊃ X ∧ ¬Z

(c) ¬X ∨ Y ⊃ ¬Y ∧ Z

(g) ¬¬X ∧ Y ⊃ Z

(d) ¬¬X ∨ Y ⊃ ¬Y ∧ Z

(h) ¬ (¬X ∧ Y ) ⊃ Z

2.4. Milyen (teljesen zárójelezett) formulát rövidítenek az alábbiak?

(A ≡ B) * ) ((A ⊃ B) ∧ (B ⊃ A)) (a) X ≡ Y

(c) X ∨ Y ⊃ ¬Z ≡ X ∧ ¬Z

(b) X ⊃ Y ≡ ¬X ∨ Y

(d) ¬ (X ≡ Y ) ⊃ Z ∨ ¬X

2.5. Jelentse E, hogy „esik az eső”, S, hogy „strandolok ”, N, hogy „napozok ”, O, hogy „otthon maradok ”. Mit jelentenek természetes nyelven az alábbi formulák? (a) (E ⊃ ¬(S ∨ N )) (b) ((O ⊃ E) ∧ (E ⊃ O)) (c) (S ⊃ ¬E) (d) ((E ∧ O) ∨ (¬E ∧ S)) (e) (¬O ⊃ ((N ∧ ¬E) ∨ S)) 2.6. Formalizáljuk az ítéletlogika nyelvén a következő mondatokat! (a) Jancsi eltévedt az erdőben, és nem talált haza.


5

(b) Jancsi eltévedt az erdőben, de Juliska nem. (c) Jancsi eltévedt az erdőben, bár jól ismerte az utat. (d) Egészségtelenül táplálkozik, vagy keveset mozog. (e) Saját autójával megy, vagy hív egy taxit. (f) Ha holnap süt a nap, akkor 10-kor várlak az uszodában. (g) Csak akkor fejezzük be a gyakorlatot, ha már mindenki volt a táblánál. (h) Elmegyek moziba, feltéve, hogy van pénzem. (i) Akkor és csak akkor süt a nap, ha holnap kimegyek az uszodába. 2.7. Írjuk fel ítéletlogikai nyelven az alábbi állításokat. (a) Nincs jó idő. (b) Ha jó az idő, kirándulni megyünk. (c) Nincs jó idő, és nem megyünk kirándulni. (d) Csak akkor megyünk kirándulni, ha jó az idő. (e) Nem fordulhat elő, hogy kirándulni megyünk, és nincs jó idő. (f) Ha esik az eső vagy fúj a szél, akkor nincs jó idő. (g) Esik az eső, pedig süt a Nap. (h) Ha esik az eső és süt a Nap, akkor szivárványt lehet látni, kivéve ha éppen a városban vagyunk. (i) Ha várakozás nélkül kapok reggelit, akkor - föltéve hogy nem alszom el - nyolc órára megérkezem. (j) Ha elalszom, nem kapok várakozás nélkül reggelit. (k) Ha nem alszom el, akkor reggelit is várakozás nélkül kapok, és meg is érkezem nyolc órára. (l) Ha ünnepély lesz, a tanítás délben véget ér. (m) Ha osztályfőnöki óra lesz, a tornaóra elmarad. (n) A tanítás nem ér véget délben, pedig ünnepély vagy osztályfőnöki óra lesz. (o) Ha a szemtanú megbízható, és az írásszakértő véleménye helytálló, úgy a bűncselekményt akkor és csak akkor követték el előre megfontolt szándékkal, ha a talált ujjlenyomatok a tettestől vagy esetleges bűntársától származnak. (p) Ha a szemtanú megbízható, az írásszakértő véleménye helytálló, és a talált ujjlenyomatok a tettestől származnak, akkor a bűncselekményt előre megfontolt szándékkal követték el. 2.8. Írjuk le az ítéletlogika nyelvén. (a) Nemcsak X, hanem Y is. (b) X abban az esetben, ha Y . (c) Nem igaz, hogy ha X, akkor egyúttal Y . (d) X, feltéve, hogy Y . (e) Bár nem X, mégis Y . (f) Csak akkor X, ha Y . (g) Legfeljebb akkor X, ha Y . (h) X, kivéve, ha nem Y .

Az informatika logikai alapjai (i) Akkor X, ha Y , de csak akkor. (j) Ha nem X, hát legalább Y . (k) Vagy X, vagy Y , de nem mind a kettő. (l) Ha X, akkor Y , feltéve hogy nem Z. (m) Pontosan akkor X, ha nem Y.

6


7

3.1. Adjuk meg az alábbi formulák közvetlen részformuláit, részformuláik halmazait és állapítsuk meg a logikai összetettségüket. (a) X

(h) ¬ (X ⊃ Y ∨ ¬Z) ∧ ¬Y ⊃ Z

(b) ¬¬X

(i) ¬ (¬¬X ⊃ Y ∨ ¬¬Z)

(c) X ∨ X

(j) ¬X ∧ X ⊃ Y

(d) ¬X ∨ Y

(k) ¬X ∨ Y ⊃ ¬Z

(e) X ∨ Y ⊃ Z

(l) ¬((X ⊃ Y ) ⊃ ((X ⊃ ¬Y ) ⊃ ¬Y ))

(f) ¬ (X ∨ Y )

(m) X ∨ Y ⊃ ¬Z ∧ ¬(X ⊃ ¬Z)

(g) (¬ (X ∧ ¬Y ) ⊃ (Z ∨ ¬X))

(n) (X ⊃ Y ) ∧ (Y ⊃ Z) ⊃ ¬X ∨ Z

3.2. Mely formula(ák) részformulája(i) az alábbi formuláknak? (a) X ∨ Y ⊃ ¬Z ≡ X ∧ ¬Z i. ¬Z ≡ X

iii. Y ⊃ ¬Z

ii. ¬Z ≡ X ∧ ¬Z

iv. X ∨ Y

(b) X ⊃ ¬Y ∧ Z ≡ Y ∨ ¬X i. ¬Y ∧ Z

iii. X ⊃ ¬Y

ii. Z ≡ Y

iv. ¬Y ∧ Z ≡ Y

(c) X ⊃ Y ∧ ¬Z ≡ ¬X ⊃ ¬Y ∧ Z i. X ⊃ Y

iii. Y ∧ ¬Z

ii. ¬Z ≡ ¬X ⊃ ¬Y

iv. Y ∧ Z

3.3. Adjuk meg a megjelölt logikai összekötőjel hatáskörét az alábbi formulákban, majd keressük meg a fő logikai összekötő jelet!

¬

¬X ∧ Z ⊃ Y ∨ ¬W

±

X ⊃¬ Y

²

⊃¬ (Y ⊃ Z)

®

¬ (X ∧ Z) ⊃ Y ¯ ° X ⊃ Y ∨ ¬Z ∧ ¬Y ⊃ Z

³

X ∨ Y ⊃ ¬Z

´

µ

⊃ ¬Y ∧ Z

3.4. Legyenek X, Y , Z ítéletváltozók. Hányféleképpen lehet zárójelekkel ellátni az alábbi jelsorozatokat úgy, hogy (teljesen zárójelezett) formulákat kapjunk? (a) X ⊃ ¬Y ∨ Y ∧ Z (b) X ⊃ Y ⊃ Z ⊃ ¬X ⊃ ¬Y 3.5. Bizonyítsuk be, hogy egy formulában a nyitó- és zárójelek száma megegyezik. 3.6. Legyen egy formulában n helyen logikai összekötőjel. Hány részformulája lehet maximum a formulának?


8

3.7. Igazoljuk, hogy egy formula valamelyik részformuláját másik formulával helyettesítve ismét formulát kapunk. 3.8. Adjuk meg a következő formulák értékét a megadott interpretációban: I1

I1 (X) = i

I2

I2 (X) = h

I3

I3 (X) = i

I4

I4 (X) = h

|X ∨ ¬X|

|X ∨ ¬X|

|X ∧ ¬X|

|X ∧ ¬X|

I5

|X ⊃ ¬X|

I5 (X) = i

I6

|X ⊃ ¬X|

I6 (X) = h I7

|X ∧ ¬Z ⊃ ¬Y |

|(¬ (X ∧ ¬Y ) ⊃ (Z ∨ ¬X))|

I8 I9

|¬ (X ⊃ Y ∨ ¬Z) ∧ ¬Y ⊃ Z| |¬ (¬¬X ⊃ Y ∨ ¬¬Z)|

I10

I11

|¬X ∧ X ⊃ Y |

I12

|X ⊃ (Y ⊃ X)|

|¬(Y ⊃ X) ∧ (X ∨ ¬Y )|

I13

|¬(¬Y ∨ ¬X ⊃ ¬X ∧ Y )|

I14

I7 (X) = h

I7 (Y ) = h

I7 (Z) = h

I8 (X) = h

I8 (Y ) = i

I8 (Z) = i

I9 (X) = i

I9 (Y ) = i

I9 (Z) = h

I10 (X) = h

I10 (Y ) = i

I10 (Z) = h

I11 (X) = i

I11 (Y ) = i

I11 (Z) = i

I12 (X) = h

I12 (Y ) = i

I13 (X) = i

I13 (Y ) = h

I14 (X) = h

I14 (Y ) = h

3.9. Határozzuk meg az alábbi formulák értékét a megadott interpretációban!

I(X) = i,

I(Y ) = h,

I(Z) = h,

I(W ) = h

(a) ¬(¬(X ⊃ Y ∨ ¬Z) ∧ ¬W ⊃ Z) (b) ¬(X ∧ ¬Y ) ⊃ Z ∨ ¬X (c) ¬X ∧ Z ⊃ Y ∨ ¬W (d) ¬ (X ∧ Z) ⊃ Y (e) (X ⊃ ¬Y ) ⊃ ¬ (Y ⊃ Z) (f) (X ∨ Y ⊃ ¬Z) ⊃ ¬Y ∧ Z 3.10. Tegyük fel, hogy egy formula igazságértékét ismerjük valamely interpretációban. Meg tudjuk-e határozni ezen ismeret birtokában egy másik, alább megadott formula igazságértékét? (a) X ≡ ¬Y , ha |X ≡ Y | = i (b) X ≡ ¬Y , ha |X ≡ Y | = h (c) (X ⊃ Y ) ⊃ Z, ha |Y | = i (d) (X ⊃ Y ) ⊃ (¬Y ⊃ ¬X), ha |Y | = i (e) X ∧ Y ⊃ X ∨ Z, ha |X| = i és |Z| = h (f) ¬X ∧ Y ⊃ X ∨ Y , ha |X ⊃ Y | = i (g) ¬X ∧ Y ≡ X ∨ Y , ha |X ⊃ Y | = i


9

4.1. Mely állítások igazak az alábbiak közül? (a) Minden kielégíthető formula logikai törvény. (b) Van olyan kielégíthető formula, mely törvény. (c) Minden logikai törvény kielégíthető. (d) Csak az a formula logikai törvény, mely kielégíthető. (e) Ha egy formula ellentmondás, akkor kielégíthetetlen. (f) Ha egy formula kielégíthetetlen, akkor negáltja kielégíthető. (g) Ha egy formula kielégíthető, akkor negáltja ellentmondás. (h) Egy formula akkor és csak akkor kielégíthető, ha negáltja ellentmondás. (i) Egy formula pontosan akkor törvény, ha negáltja ellentmondás. (j) Ha egy formula negáltja kielégíthető, akkor az ellentmondás. (k) Minden formula vagy kielégíthető, vagy ellentmondás. (l) Minden formula vagy nem logikai törvény vagy ellentmondás. 4.2. Milyen szemantikai tulajdonságokkal rendelkeznek az alábbi formulák, azaz melyik kielégíthető, törvény, ellentmondás? Döntsük el a kérdést igazságtáblával! (a) ¬X ∧ ¬Y ⊃ (X ∨ Y ) (b) ¬ (X ⊃ Y ) ⊃ ¬ (X ∧ ¬Y ) (c) ¬ (X ⊃ ¬Y ) ∧ (¬Z ⊃ Y ) (d) ¬ (X ∧ ¬ (Y ∧ ¬(Z ∨ ¬X))) (e) X ⊃ (Y ⊃ (Z ⊃ ¬X)) 4.3. Adjunk meg (amennyiben lehetséges) egy-egy olyan interpretáció, melyben az alábbi formulák igazak! (a) (X ⊃ Y ∨ Z) ∧ ¬ (¬X ∨ Y ) ∧ (Z ⊃ W ∨ Y ) (b) ¬ (X ∧ Y ⊃ Z) ∧ (¬W ⊃ ¬Z) ∧ (Y ⊃ ¬W ) (c) (X ∨ Y ⊃ ¬Y ∧ Z) ∧ (Z ⊃ X) ∧ (Z ∨ Y ) (d) ¬ (X ∨ Y ⊃ Z) ∧ (Z ∨ Y ) ∧ (W ∨ X) ∧ (Y ∨ Z ⊃ ¬W ) 4.4. Határozzuk meg a szemantikai definíciók mentén (igazságtábla nélkül), hogy az alábbi formulák közül melyek törvények! (a) ¬(X ⊃ Y ) ⊃ X ∧ ¬Y (b) X ⊃ (¬Y ⊃ (Z ⊃ (¬U ⊃ (W ⊃ ¬X)))) (c) ((X ⊃ Y ) ∧ (X ⊃ ¬Y )) ⊃ ¬X (d) ¬X ∨ (Y ∧ Z) ⊃ (¬X ∨ Y ) ∧ (¬X ∨ Z) 4.5. Határozzuk meg a szemantikai definíciók mentén (igazságtábla nélkül), hogy az alábbi formulák közül melyek ellentmondások! (a) (¬X ⊃ ¬Y ) ⊃ ¬(Y ⊃ X)


10

(b) (X ∧ Y ⊃ Z) ∧ ¬(Y ⊃ (X ⊃ Z)) (c) ((X ⊃ Y ) ∧ (Y ⊃ Z)) ∧ (X ∧ ¬Z) 4.6. Ekvivalensek-e az alábbi formulák? Bizonyítsuk igazságtáblával! ?

(a) (X ∨ Y ) ∧ X

∼0 X

(b) (X ∧ Y ) ∨ X

∼0 X

(c) X ∨ Y ⊃ Z

?

?

∼0 (¬X ∧ ¬Y ) ∨ Z ?

(d) (X ⊃ Y ) ⊃ Z

∼0 (Y ⊃ X) ⊃ Z ?

(e) X ⊃ (Y ⊃ Z) ∼0 X ⊃ (Z ⊃ Y ) ?

(f) X ⊃ (Y ⊃ Z) ∼0 (X ⊃ Y ) ⊃ Z 4.7. Ekvivalensek-e az alábbi formulák? Bizonyítsuk a szemantikai definíciók segítségével! (a) X ∨ Y ⊃ Z

?

∼0 Z ∨ Y ⊃ X ?

(b) (X ⊃ Y ) ∨ (Z ⊃ W ) ∼0 ¬(X ∧ Z) ∨ ¬(¬Y ∧ ¬W ) 4.8. Létezik-e olyan interpretáció, melyben az alábbi formulahalmaz minden formulája igaz? Indokoljon!

{X ∨ Y ∨ Z, ¬X ⊃ ¬Z, X ∨ Y ⊃ ¬X ∧ Z}


11

5.1. Legyenek P1 , P2 , valamint K egy következtetés premisszáit illetve konklúzióját leíró formulák. Mely állítások igazak az alábbiak közül? (a) Ha a következtetés helyes akkor P1 ∧ P2 ⊃ K logikai törvény. (b) Ha P1 ∧ P2 ⊃ K logikai törvény, akkor a következtetés helyes. (c) A következtetés pontosan akkor helyes, ha P1 ∧ P2 ∧ ¬K ellentmondás. (d) A következtetés pontosan akkor helyes, ha {P1 , P2 , ¬K} formulahalmaz formuláji egyetlen interpretációban sem lesznek egyszerre igazak. (e) Ha a következtetés helytelen, P1 ∧ P2 ⊃ ¬K logikai törvény. (f) Ha a következtetés helytelen, P1 ∧ P2 ⊃ ¬K kielégíthető. (g) Ha P1 ∧ P2 ellentmondás, akkor a következtetés helyes. (h) Ha K ellentmondás, akkor a következtetés helyes. (i) Ha K ellentmondás, akkor a következtetés csak akkor helyes, ha P1 ∧ P2 ellentmondás. 5.2. Található-e olyan interpretáció, mely az alábbi formulahalmazok valamelyikének minden formuláját kielégíti? (a) { X ⊃ Y ∨ Z, ¬ (¬X ∨ Y ) , Z ⊃ U ∨ Y } (b) { ¬ (X ∧ Y ⊃ Z) , ¬U ⊃ ¬Z, Y ⊃ ¬U } 5.3. Döntsük el táblázat segítségével, hogy az alábbi következtetések helyesek-e! Premisszál: P1

(X ∨ ¬Y ) ⊃ Z

P2

¬X ∨ ¬Z

Következtetések: a.)

Y ∨Z

b.)

¬Y ⊃ ¬Z

5.4. Formalizáljuk az alábbi mondatokat! Döntsük el táblázat segítségével, hogy az alábbi következtetések helyesek-e! Premisszál: P1

Ha Zoltán hazudik, akkor János csak akkor füllent, ha Imre igazat mond.

P2

János füllent, de ha Zoltán hazudik, akkor Imre nem mond igazat.


Ha Imre nem mond igazat, akkor János füllent.

b.)

Ha János füllent, akkor Imre nem mond igazat.

5.5. Döntsük el a szemantikai definíciók segítségével, hogy az alábbi következtetések helyesek-e! Premisszál: P1

(X ∨ ¬Y ) ∧ (Z ⊃ W )

P2

¬(Y ∨ Z ⊃ X ∨ U )


K⊃X

b.)

¬W ⊃ Z


12

5.6. Formalizáljuk az alábbi mondatokat! Döntsük el a szemantikai definíciók segítségével, hogy az alábbi következtetések helyesek-e! Premisszál: P1

Csak akkor megyek boltba, ha elfogyott a tej vagy kevés a kenyér.

P2

Nem igaz az, hogy nem megyek boltba vagy elfogyott a tej.

P3

Amennyiben kevés a kenyér, úgy liszt sincs már vagy elfogyott a tej.


Csak abban az esetben megyek boltba, amennyiben liszt már nincs, de nem fogyott el a tej.

b.)

Ha nem fogy el a tej, akkor kevés a kenyér.

c.)

Ha elmegyek a boltba, akkor liszt már nincs.

5.7. Formalizáljuk az alábbi mondatokat! Döntsük el a szemantikai definíciók segítségével, hogy az alábbi következtetések helyesek-e! Premisszál: P1

Nem igaz az, hogy ha rossz időt jósoltak mára de süt a nap, akkor esik az eső.

P2

Ha nem fúj a szél, nem is esik az eső.

P3

Csak akkor süt a nap, ha a szél nem fúj.


Ha rossz időt jósoltak mára, akkor nem fúj a szél, és az eső sem esik.

b.)

Csak akkor nem fúj a szél, ha nem jósoltak rossz időt mára.


13

6.1. Tekintsük az aritmetika (Ar) nyelvét és természetes interpretációját informálisan a következőképpen: Ar = h{szt}, {P }, {f, g, h}, {nulla}i Jelentse szt a nemnegatív egész számokat! A nyelv szinbólumai és az interpretáció informális leírása: Pr

ν1

P

(szt, szt)

Fn

ν2

f

(szt, szt)

g

(szt, szt, szt)

összeadás

h

(szt, szt, szt)

szorzás

Cnst

ν3

nulla

(szt)

interpretáció egyenlőség predikátum interpretáció rákövetkező egész

interpretáció 0

Vezessük be a következő jelöléseket: * ) nulla x=y * ) P (x, y) * sx ) f (x) 0

x+y * ) g(x, y) x∗y * ) h(x, y) Formalizáljuk az Ar nyelv természetes interpretációjában az alábbi mondatokat! Vezessünk be új jelöléseket ahol ez szükséges. 1. Az x és y számok nem egyenlőek. 2. Az x szám kisebb vagy egyenlő, mint az y. 3. Az x szám kisebb, mint az y. 4. Az x szám osztja az y számot. 5. Az x prím szám. 6. Végtelen sok prím szám van. 7. Véges sok prím szám van. 8. Az ikerprímek száma végtelen. 9. Minden nem negatív szám felírható négy nem negatív szám négyzetének összegeként! 10. Ha x > y, akkor x + z > y + z. Tekintsük az aritmetika (Ar) nyelvének olyan interpretációját, mely az előbbitől csak annyiban különbözik, hogy az szt fajtához az egész számok halmazát rendeli! Hogyan formalizálhatók ekkor a fenti mondatok?


14

6.2. Tekintsük a geometria (Geom) nyelvét és természetes interpretációját informálisan a következőképpen: Geom = h{pt, et, st}, {P, Q, R}, ∅, ∅i Legyen a fajták jelentése a következő: Srt

változók

interpretáció

pt

A, B, C, . . .

a 3 dimenziós euklideszi tér pontjai

et

e, f, g, . . .

a 3 dimenziós euklideszi tér egyenesei

st

a, b, c, . . .

a 3 dimenziós euklideszi tér síkjai

A nyelv szinbólumai és az interpretáció informális leírása: Pr

ν1

P

(pt, pt)

két pont egyebeesik

Q

(pt, et)

az egyenes tartalmazza a pontot

R

(pt, st)

a sík tartalmazza a pontot

interpretáció

Vezessük be a következő jelöléseket: A=B * ) P (A, B) A∈e * ) Q(A, e) A∈a * ) R(A, a) Formalizáljuk a geometria (Geom) nyelvének természetes interpretációjában az alábbi mondatokat! Vezessünk be új jelöléseket, ahol ez szükséges. 1. Az e egyenes az a síkban van. 2. Az e és f egyenesek egybeesnek. 3. Az a és b síkok egybeesnek. 4. Az e és f egyenesek párhuzamosak. 5. Az e és f egyenesek kitérőek. 6. Az e és f egyenesek pontosan egy pontban keresztezik egymást. 7. Az e egyenes egy pontban döfi az a síkot. 8. Az a és b síkok párhuzamosak. 9. Bármely két nem egybeeső pontra pontosan egy egyenes illeszthető. 10. Bármely ponton át pontosan egy, a pontot nem tartalmazó egyenessel párhuzamos egyenes húzható.


15

Legyen L1 elsőrendű logikai nyelv definiálva a következőképpen: L1 = h{π1 } , {P, Q, R} , {f, g} , {c}i • x, y, z, . . . változók π1 fajtájúak • ν1 (P ) = (π1 ),

ν1 (Q) = (π1 , π1 ),

• ν2 (f ) = (π1 , π1 ),

ν1 (R) = (π1 , π1 )

ν2 (g) = (π1 , π1 )

• ν3 (c) = (π1 )

7.1. Az alábbi kifejezések közül melyek π1 fajtájú termjei az L1 nyelvnek? (a) c

(e) c(x)

(i) P (x)

(b) x

(f) f (c)

(j) Q(x)

(c) F (x)

(g) f (g(x))

(k) ¬f (c)

(d) f (c, x)

(h) f (g(x, y), z)

(l) g(c, f (x))

7.2. Az alábbi kifejezések közül melyek formulái az L1 nyelvnek? (a) P (c)

(e) ∃xf (x)

(i) P (x) ⊃ ∃xQ(x, x)

(b) Q(x)

(f) ∀¬P (x) ∧ f (x)

(j) ∃f (x)P (f (x))

(c) ¬P (¬f (x))

(g) ∃c(P (c) ∨ R(f (c), y))

(k) ¬f (c) ∧ ∀yQ(y, y)

(d) R(f (x), g(x))

(h) ¬∃xR(P (c), f (x))

(l) P (x ∧ y)


16

Legyen L2 elsőrendű logikai nyelv definiálva a következőképpen: L2 = h{π1 , π2 } , {P, Q, R} , {f, g, h} , {c, }i • x, y, z, . . . változók π1 fajtájúak, α, β, γ, . . . változók π2 fajtájúak • ν1 (P ) = (π1 ),

ν1 (Q) = (π1 , π2 ),

• ν2 (f ) = (π1 , π2 ), • ν3 (c) = (π1 ),

ν1 (R) = (π2 , π2 )

ν2 (g) = (π1 , π1 , π2 ),

ν2 (h) = (π2 , π2 , π1 )

ν3 () = (π2 )

7.3. Keressük ki az alábbi kifejezések közül az L2 nyelv π1 valamint π2 fajtájú termjeit! (a) f (c, x)

(d) f (h(, ))

(g) g(f (x), f (c))

(b) h(f (x), g(x, y))

(e) f ()

(h) f (f (g(x, y)))

(c) f (g(x, x))

(f) g(Q(c), R())

(i) g(c, f (x))

7.4. Az alábbi kifejezések közül melyek formulái az L2 nyelvnek? (a) ∃R(, α)

(e) ¬Q(x, Q(x))

(b) ∃xQ(x, f (x)) ⊃ ∀xP (h(f (x), ))

(f) ∃¬xP (x)

(c) ¬P (x) ∨ f (x)

(g) f (x, g(c, x))

(d) Q(f (x), ) ⊃ ¬R(, α)

(h) ∀Q(x, α) ⊃ P (x)

7.5. Legyenek az alábbi kifejezések valamely alkalmas elsőrendű nyelv elemei! (P, Q, R, . . . predikátum szimbólumok, f, g, h, . . . függvény szimbólumok, a, b, c, . . . konstansok szimbólumok és x, y, z, . . . változók.) • határozzuk meg a formulák logikai- és a termek funkcionális összetettségét, • adjuk meg a közvetlen részkifejezéseiket! (a) P (x) ∨ Q(x, y) ⊃ P (f (x)) ∧ Q(f (x), y) (b) ∀x(P (x) ∨ Q(x, y) ⊃ P (x) ∧ Q(x, y)) (c) f (g(x, y)) (d) g(f (x), f (x)) (e) ¬P (g(f (x), f (x))) 7.6. Legyenek az alábbi kifejezések (a megelőző feladathoz hasonló módon) valamely alkalmas elsőrendű nyelv formlái! • határozzuk meg az egyes változó előfordulások státuszát, • készítsük el (ha szükséges) a formulák változóiban tiszta alakját! (a) P (x) ∨ Q(x, y) ⊃ P (f (x)) ∧ Q(f (x), y) (b) P (x) ∨ Q(x, y) ⊃ P (z) ∧ Q(z, y) (c) ∀x∃y(P (x) ∨ Q(x, y) ⊃ P (f (x))) ∧ Q(f (x), c)

Az informatika logikai alapjai (d) ∀y∃x(P (y) ∨ Q(y, x) ⊃ P (f (y))) ∧ Q(f (x), c) (e) ∀x(P (x) ⊃ ∃xQ(x, f (x))) ∨ Q(x, c) (f) ∀y(P (y) ⊃ ∃xQ(y, f (y))) ∨ Q(y, c) (g) P (x) ⊃ ∃xP (x) ∨ Q(x, y) (h) P (x) ⊃ ∃yP (y) ∨ Q(y, x) • Található-e a fenti formulák közt olyan, mely kongruens az alábbiak egyikével? i. Kongruens-e (a) vagy (b) formulávak: P (y) ∨ Q(y, x) ⊃ P (f (y)) ∧ Q(f (y), x) ? ii. Kongruens-e (c) vagy (d) formulávak: ∀y∃x(P (y) ∨ Q(y, x) ⊃ P (f (y))) ∧ Q(f (y), c) ? iii. Kongruens-e (e) vagy (f) formulávak: ∀x(P (x) ⊃ ∃yQ(y, f (y))) ∨ Q(y, c) ? iv. Kongruens-e (g) vagy (h) formulávak: P (x) ⊃ ∃yP (y) ∨ Q(y, x) ?

17


18

Legyen L2 elsőrendűlogikai nyelv definiálva a következőképpen: L2 = h{π1 , π2 } , {P, Q, R} , {f, g, h} , {c, }i • x, y, z, . . . változók π1 fajtájúak, α, β, γ, . . . változók π2 fajtájúak • ν1 (P ) = (π1 ),

ν1 (Q) = (π1 , π2 ),

• ν2 (f ) = (π1 , π2 ), • ν3 (c) = (π1 ),

ν1 (R) = (π2 , π2 )

ν2 (g) = (π1 , π1 , π2 ),

ν2 (h) = (π2 , π2 , π1 )

ν3 () = (π2 )

8.1. Készítsünk interptetációt L2 elsőrendű logikai nyelvhez, amely eleget tesz az alábbiaknak! • π1 fajtájú individuumok halmaza: {1, 2} • π2 fajtájú individuumok halmaza: {a, b} 8.2. Készítsünk olyan interpretációt az Ar nyelvhez, mely a természetes interperetációtól annyiban különbözik, hogy univerzumát az egész számok adják! 8.3. Formalizáljuk alkalmas elsőrendű nyelven az alábbi mondatokat. Készítsük el a nyelvek egy-egy interpretációját! (a)

• Mindenki, aki az első padban ül, kabátot visel. • Csak azok nem ültek az ablak mellé, akiknek kék szemük van. • Senki nem ül ablak mellett, aki kabátot visel.

(b)

• Minden olyan nap, amikor esik az eső, és hideg van, fáradt vagyok. • Minden téli hónapra eső nap hideg van. • Van olyan hideg nap, mely nem téli hónapra esik.

Legyen L elsőrendű logikai nyelv definiálva a következőképpen: L3 = h{π} , {P, Q} , {f, g} , {c}i • x, y, z, . . . változók π fajtájúak • ν1 (P ) = (π), • ν2 (f ) = (π, π),

ν1 (Q) = (π, π) ν2 (g) = (π, π, π)

• ν3 (c) = (π) Legyen I az L3 elsőrendű logikai nyelv alábbi interpretációja: I = hISrt , IP r , IF n , ICnst i • ISrt (π) = {1, 2, 3, 4} I

f I (α) = 5 − α I

• IP r (P ) = P ,

IP r (Q) = Q

• IF n (f ) = f I ,

IF n (g) = g I

• ICnst (c) = 2

g I (α, β) = |α − β| + 1 ( i ha α = 1 vagy α = 4 I P (α) = h egyébként ( i ha α > β QI (α, β) = h egyébként


19

8.4. Határozzuk meg az alábbi L3 nyelvű termek értékét I interpretációban a megadott változókiértékelés mellett! • κ(x) = 1, κ(y) = 3 (a) |c|I,κ

(d) |f (g(c, c))|I,κ

(b) |y|I,κ

(e) |g(f (x), f (y))|I,κ

(c) |f (c)|I,κ

(f) |f (g(x, g(y, c)))|I,κ

• κ(x) = 2, κ(y) = 4 (a) |y|I,κ

(c) |f (g(x, g(y, c)))|I,κ

(b) |g(f (x), f (y))|I,κ 8.5. Határozzuk meg az alábbi L3 nyelvű formulák értékét I interpretációban κ változókiértékelés mellett! κ(x) = 1, κ(y) = 3 (a) |P (y)|I,κ

(f) |∃y(Q(f (c), y) ⊃ ¬Q(c, f (y)))|I,κ

(b) |∀xP (x)|I,κ

(g) |∃xP (x) ⊃ ∀x¬Q(x, f (x))|I,κ

(c) |Q(x, y)|I,κ

(h) |∀x∃y¬Q(x, f (y))|I,κ

(d) |Q(x, y) ⊃ ¬Q(f (x), f (y))|I,κ

(i) |∃x∀y¬Q(x, f (y))|I,κ

(e) |∀x(Q(f (x), y) ⊃ ¬Q(x, f (y)))|I,κ

(j) |∀x∀y(Q(x, f (y)) ∨ Q(f (y), x))|I,κ


20

9.1. Készítsünk olyan változókiértékeléseket L3 nyelv I interpretációjához, melyben az alábbi formulák igazak, vagy igazoljuk, hogy nincs ilyen változókiértékelés! (a) |∃xQ(x, f (y))|I,κ1 = i (b) |∀x(Q(x, f (y)) ∨ P (y))|I,κ2 = i (c) |∃x¬(Q(x, f (y)) ∨ P (y))|I,κ3 = i (d) |¬Q(y, f (c)) ∧ ¬Q(f (c), y)|I,κ4 = i (e) |¬Q(x, f (x)) ∧ ¬Q(f (x), x)|I,κ5 = i 9.2. Konstruáljuk meg (ha ez lehetséges) az L3 nyelv olyan interpretációit és ezekben olyan változókiértékelést, melyen az alábbi formulák igazak! (a) ∀x∀y(Q(x, y) ⊃ ¬Q(y, x))

(f) ¬∀x∀y(Q(x, y) ⊃ ¬Q(y, x))

(b) ∀x(P (x) ∨ Q(x, c)) ⊃ ∃x¬Q(x, c)

(g) ¬(∀x(P (x) ∨ Q(x, c)) ⊃ ∃x¬Q(x, c))

(c) ∀x∀y(P (x) ∧ Q(y, x) ⊃ ¬P (y))

(h) ∃x∃y¬(P (x) ∧ Q(y, x) ⊃ ¬P (y))

(d) Q(x, f (x)) ∧ ¬Q(y, f (y))

(i) Q(x, f (x)) ∨ ¬Q(y, f (y))

(e) ∀x∃yQ(y, x) ∧ ¬∃y∀xQ(y, x)

(j) ∀x∃yQ(y, x) ∨ ¬∃y∀xQ(y, x)

9.3. Legyenek az alábbi kifejezések valamely alkalmas egy fajtájú elsőrendű nyelv formulái! (P, Q, R, . . . predikátum szimbólumok, f, g, h, . . . függvény szimbólumok, a, b, c, . . . konstansok szimbólumok és x, y, z, . . . változók.) Mely formulák tautologikusan igazak az alábbiak közül? (a) Q(x, c) ∨ ¬Q(y, c) (b) ∀xP (x) ⊃ ∀yP (y) (c) ¬(∀xP (x) ∨ ∃yQ(y, c)) ⊃ (¬∀xP (x) ∧ ¬∃yQ(y, c)) (d) ¬∀xQ(x, c) ⊃ ∃x¬Q(x, c) (e) (∀xP (x) ⊃ ∃yR(y)) ∨ ∃x¬P (x) (f) (∀xP (x) ⊃ ∃yR(y)) ∨ ¬∀xP (x) 9.4. Legyenek az alábbi kifejezések valamely alkalmas egy fajtájú elsőrendű nyelv formulái! (P, Q, R, . . . predikátum szimbólumok, f, g, h, . . . függvény szimbólumok, a, b, c, . . . konstansok szimbólumok és x, y, z, . . . változók.) Mely szemantikai tulajdonságoknak tesznek eleget az alábbi formulák? • logikai törvény, • kielégíthető, • ellentmondás. (a) ¬∀xQ(x, c) ⊃ ∃x¬Q(x, c)

(h) ∃x¬Q(x, c) ⊃ ¬∀yQ(y, c)

(b) P (c) ⊃ ∃xP (x)

(i) ∀xP (x) ⊃ ∃y(Q(y, y) ∨ P (y))

(c) ∀x∃yQ(x, y) ⊃ ∃y∀xQ(x, y)

(j) ∃y∀xQ(x, y) ⊃ ∀x∃yQ(x, y)

(d) ∀x∃yQ(x, y) ⊃ ∃y∀xQ(y, x)

(k) ∃y∀xQ(y, x) ⊃ ∀x∃yQ(x, y)

(e) ∀xP (x) ∨ ∀xR(x) ⊃ ∀x(P (x) ∨ R(x))

(l) ∃xP (x) ∨ ∃xR(x) ⊃ ∃x(P (x) ∨ R(x))

(f) ∃xP (x) ∧ ∃xR(x) ⊃ ∃x(P (x) ∧ R(x))

(m) ∃x(P (x) ∧ R(x)) ⊃ ∃xP (x) ∧ ∃xR(x)

(g) ∀x(P (x) ⊃ R(x)) ⊃ (¬∀xP (x) ∨ ∀xR(x))

(n) (∃xP (x) ⊃ ∀xQ(x)) ⊃ ∀x(P (x) ⊃ R(x))


21

10.1. Legyenek az alábbi kifejezések valamely alkalmas egy fajtájú elsőrendű nyelv formulái! (P, Q, R, . . . predikátum szimbólumok, f, g, h, . . . függvény szimbólumok, a, b, c, . . . konstansok szimbólumok és x, y, z, . . . változók.) Mely formulák ekvivalensek az alábbi formulasorozatokban? (a)

i. ∀x((P (x) ⊃ Q(x)) ∧ (Q(x) ⊃ R(x))) ii. ∀x(P (x) ⊃ R(x)) iii. ∀x(P (x) ⊃ Q(x)) ∧ ∀x(Q(x) ⊃ R(x))

(b)

i. ∀xP (x) ∧ ∀xQ(x) ii. ∀x(P (x) ∧ Q(x)) iii. ¬∃x(¬P (x) ∨ ¬Q(x))

(c)

i. ∃xP (x) ∧ ∀xQ(x) ii. ∃x(P (x) ∧ Q(x)) iii. ¬∀x(P (x) ⊃ ¬Q(x))

(d)

i. ∀xP (x) ∨ ∀xQ(x) ii. ∀x(P (x) ∨ Q(x)) iii. ¬∃xP (x) ⊃ ¬∃x¬Q(x)

(e)

i. ∃xP (x) ∨ ∀xQ(x) ii. ∃x(P (x) ∨ Q(x))

10.2. Formalizáljuk alkalmas elsőrendű logikai nyelven az alábbi kijelentéseket, és keressük meg az ekvivalens állításokat! (a)

i. Mindenki aki alaposan felkészül, jó jegyet fog szerezni. ii. Csak azok szereznek jó jegyet, akik alaposan felkészültek. iii. Csak azok készültek fel alaposan, akik jó jegyet fognak szerezni.

(b)

i. Minden nap esett az eső, vagy egyetlen nap sem volt szél. ii. Nem igaz az, hogy ugyan volt nem esős nap, de nem minden nap telt el szél nélkül. iii. Ha volt szeles nap, akkor nem volt esős nap sem.

(c)

i. Minden kosaras apja sportol. ii. Nem igaz, hogy nincs olyan kosaras akinek nem sportoló az apja. iii. Akinek az apja nem sportoló az nem kosaras.


22

11.1. Mely alábbi tulajdonságokkal rendelkeznek a megadott ítéletlogikai formulák? • literál • elemi konjunkció • elemi diszjunkció • konjunktív normál forma • diszjunktív normál forma (a) ¬¬X

(h) (X ⊃ ¬Y ) ⊃ Z

(b) ¬X ∨ ¬Y

(i) X

(c) X ⊃ ¬Y

(j) (X ∨ Y ) ∧ Z

(d) ¬Y (e) (X ∨ Y ) ∨ Z

(k) (X ⊃ Y ) ∧ Z

(f) (X ∧ Y ) ∧ ¬Z

(l) ¬(X ∨ Y ) ∨ ¬(Y ∨ Z)

(g) ¬(X ∧ Y ) ∧ Z

(m) (¬X ∨ Y ) ∧ (¬Y ∨ Z)

11.2. Készítsen az alábbi formulával ekvivalens ugyanakkor kisebb logikai összetettségű formulát (alkalmazza az egyszerűsítési szabályokat)! (a) ¬¬¬X

(f) ¬(¬X ∨ ¬Y )

(b) (X ∨ ¬Y ∨ ¬X) ⊃ Y

(g) ¬(¬X ∧ ¬Y )

(c) (X ∧ ¬Y ∧ ¬X) ⊃ Y

(h) ¬X ⊃ ¬Y

(d) (X ∨ Y ) ∧ (Z ∧ Y )

(i) ¬X ⊃ ¬Y

(e) (X ∧ Y ) ∨ (Z ∨ Y )

(j) ¬(X ∧ Y ) ⊃ (X ∧ Y )

11.3. Határozza meg a következő ítéletlogikai formulák diszjunktív normál formáját (alkalmazza a disztributivitási szabályokat)! (a) X ∧ (Y ∨ Z) (b) (X ∨ ¬Y ∨ ¬Z) ∧ (U ∨ ¬W ) (c) (X ∨ ¬Y ) ∧ (¬Z ∨ ¬U ∨ W ) ∧ (S ∨ ¬T ) 11.4. Határozza meg a következő ítéletlogikai formulák konjunktív normál formáját (alkalmazza a disztributivitási szabályokat)! (a) X ∨ (¬Y ∧ ¬Z) (b) (X ∧ (¬Y ∨ ¬Z)) ∨ (U ∧ ¬W ) (c) (X ∨ ¬Y ) ∨ ((¬Z ∨ ¬U ∨ W ) ∧ (S ∨ ¬T )) 11.5. Határozza meg a következő ítéletlogikai formulák konjunktív és diszjunktív normál formáját! Egyszerűsítsen ahol ez lehetséges! (a) X ⊃ (Y ⊃ (Z ⊃ U )) (b) ((X ⊃ Y ) ⊃ Z) ⊃ U (c) ¬(X ∨ Y ) ⊃ ¬(X ∧ ¬Z)


23

(d) ¬(X ∨ ¬Y ∨ ¬Z) ∧ (U ∨ ¬W ) (e) (X ∧ (¬Y ∨ ¬Z)) ⊃ ¬(U ⊃ ¬W ) (f) (X ∨ Z) ∧ (Z ⊃ ¬X) (g) ¬((X ∨ Z) ⊃ (Z ⊃ ¬X)) (h) (X ∧ ¬Y ) ∨ ¬((¬Z ⊃ ¬U ∨ W ) ⊃ (S ∨ ¬T )) 11.6. Legyenek az alábbi kifejezések valamely alkalmas egy fajtájú elsőrendű nyelv formulái! (P, Q, R, . . . predikátum szimbólumok és x, y, z, . . . változók.)! Adja meg a formulák prenex alakját! (a) ¬∃xP (x) ∧ ¬∀xQ(x) (b) ¬∃xP (x) ⊃ ¬∀xQ(x) (c) ∃xP (x) ⊃ ¬∀x¬Q(x) (d) ∀x(P (x) ∧ ¬∃xQ(x)) ∨ (∀xQ(x) ⊃ R(x)) (e) ¬∀x(P (x) ∧ ¬∃xQ(x)) ∨ (∀xQ(x) ⊃ R(x)) (f) ∀xP (x) ⊃ (∀xR(x) ⊃ ∃xQ(x)) (g) ¬∃x¬∀y¬T (x, y) (h) ¬∀x(∃yT (x, y) ⊃ ∀xR(x) ∨ P (x)) (i) ∀x∃yT (x, y) ⊃ Q(x) ∨ R(y) (j) P (x) ⊃ (∀yQ(y) ⊃ ¬∃xT (x, y))

Az informatika logikai alapjai 12.1. Formalizálja a következő állításokat alkalmas elsőrendű logikai nyelven! • Ha akad, aki elvégezze a munkát, akkor mindenki elégedett lehet. • Aki elégedett lehet, az nyugodtan alszik. • János elvégzi a munkát. Az előbbi állításokat premisszaként tekintve, mely következtetések helyesek az alábbiak közül? (a) Mindenki nyugodtan alszik. (b) Ha János nem végzi el a munkát, nem alhat nyugodtan. 12.2. Formalizálja a következő állításokat alkalmas elsőrendű logikai nyelven! • Ha egy részecske nyugalmi tömege 0 és a részecske bozon, akkor ez a részecske foton. • A Higgs részecske nem foton, de bozon. • Nem minden 0 nyugalmi tömegű részecskére igaz, hogy foton. Az előbbi állításokat premisszaként tekintve, mely következtetések helyesek az alábbiak közül? (a) Léteznek nem 0 nyugalmi tömegű részecskék és nem minden részecske bozon. (b) Nem igaz az, hogy minden részecske 0 nyugalmi tömegű és bozon. 12.3. Formalizálja a következő állításokat alkalmas elsőrendű logikai nyelven! • Nem igaz az, hogy ha van, aki nem kelt korán, akkor van olyan is, aki nem tanult. • Mindenki, aki hamar nyugovóra tért, korán kelt. Az előbbi állításokat premisszaként tekintve, mely következtetések helyesek az alábbiak közül? (a) Nem igaz az, hogy ha mindenki tanult, akkor mindenki hamar nyugovóra is tért. (b) Nem mindenki tért hamar nyugovóra.

24


25

13.1. Adjon meg az alábbi szekventekkel ekvivalens formulákat! Egyszerűsítsen, ahol ez lehetséges! (a) → (X ⊃ Y )

(d) (X ⊃ Y ) →

(b) X → Y

(e) X ∨ Y → Y ∨ Z

(c) X ∧ Y → Y ∧ Z

(f) X, Y → Y, Z

13.2. Bizonyítsuk be Gentzen-kalkulus segítségével hogy az alábbi ítéletlogikai formulák logikai törvények! (a) Predikátumkalkulus axiómája (X ⊃ (Y ⊃ Z)) ⊃ ((X ⊃ Y ) ⊃ (X ⊃ Z)) (b) De’Morgan törvényei i. ¬X ∧ ¬Y ⊃ ¬(X ∨ Y )

iii. ¬X ∨ ¬Y ⊃ ¬(X ∧ Y )

ii. ¬(X ∨ Y ) ⊃ ¬X ∧ ¬Y

iv. ¬(X ∧ Y ) ⊃ ¬X ∨ ¬Y

(c) Implikáció átalakítás i. (X ⊃ Y ) ⊃ ¬X ∨ Y

iii. ¬(X ⊃ Y ) ⊃ X ∧ ¬Y

ii. ¬X ∨ Y ⊃ (X ⊃ Y )

iv. X ∧ ¬Y ⊃ ¬(X ⊃ Y )

(d) Peirce törvénye ((X ⊃ Y ) ⊃ X) ⊃ X (e) Reduktio ad absurdum (X ⊃ Y ) ∧ (X ⊃ ¬Y ) ⊃ ¬X (f) Előtag felcserélése implikációban (X ⊃ (Y ⊃ Z)) ⊃ (Y ⊃ (X ⊃ Z)) (g) Az implikáció öndisztributivitása i. (X ⊃ (Y ⊃ Z)) ⊃ ((X ⊃ Y ) ⊃ (X ⊃ Z)) ii. (X ⊃ Y ) ⊃ (X ⊃ Z)) ⊃ (X ⊃ (Y ⊃ Z)) (h) Az implikáció tranzitivitása ((A ⊃ B) ∧ (B ⊃ C)) ⊃ (A ⊃ C) (i) Kontrapozíció i. (X ⊃ Y ) ⊃ (¬Y ⊃ ¬X) ii. (¬Y ⊃ ¬X) ⊃ (X ⊃ Y ) (j) Konjunkció disztributivitás i. (X ∨ Y ) ∧ Z ⊃ (X ∧ Z) ∨ (Y ∧ Z) ii. (X ∧ Z) ∨ (Y ∧ Z) ⊃ (X ∨ Y ) ∧ Z (k) Diszjunkció disztributivitás i. (X ∧ Y ) ∨ Z ⊃ (X ∨ Z) ∧ (Y ∨ Z) ii. (X ∨ Z) ∧ (Y ∨ Z) ⊃ (X ∧ Y ) ∨ Z

Az informatika logikai alapjai 13.3. Bizonyítsuk be Gentzen-kalkulus segítségével hogy az alábbi elsőrendű formulák logikai törvények! (a) De’Morgan kvantoros törvényei i. (¬∀xP (x) ⊃ ∃x¬P (x)) ∧ (∃x¬P (x) ⊃ ¬∀xP (x)) ii. (¬∃xP (x) ⊃ ∀x¬P (x)) ∧ (∀x¬P (x) ⊃ ¬∃xP (x)) (b) Kétoldali kvantorkiemelés i. ∃xP (x) ∨ ∃xQ(x) ⊃ ∃x(P (x) ∨ Q(x)) ii. ∃x(P (x) ∨ Q(x)) ⊃ ∃xP (x) ∨ ∃xQ(x) iii. ∀xP (x) ∧ ∀xQ(x) ⊃ ∀x(P (x) ∧ Q(x)) iv. ∀x(P (x) ∧ Q(x)) ⊃ ∀xP (x) ∧ ∀xQ(x)

26

Az informatika logikai alapjai 1

Recommend Documents