Logika feladatgyűjtemény - Lengyel Zoltán

Országok listájaHungaryDebreceni EgyetemInformatikai KarProgramtervező informatikusAz Informatika Logikai AlapjaiJegyzetekLogika feladatgyűjtemény - Lengyel Zoltán

Debreceni Egyetem Informatikai Kar

Logika feladatgyjtemény

2005. március 18.

Készítette: Lengyel Zoltán lengyelz@inf.unideb.hu

1.
a) b) c) d) e) f) g) h) i)

Ítéletlogika
¬X (¬X) (¬X Y ) ¬(X Y ) ¬(X Y Z) ¬(X Y Z) (X Y ) (Y X) (¬X¬Y ) XY Z Megoldás: Az a), c), d) formulái az ítéletlogika nyelvének, míg a többi nem.

1.1. feladat. Formulái-e az ítéletlogika nyelvének az alábbi jelsorozatok?

1.2. feladat. Mennyi az alábbi formulák logikai összetettsége? a) b) c) d) e) f) g) h) i) ((¬X Y ) ¬Z) (¬X ¬¬Y ) (¬X ¬¬¬Y ) ¬(X Y ) ¬(X ¬(Y Z)) ¬(¬X (Y ¬Z)) ¬((X Y ) (Y X)) (¬X (Y Z)) (X (Y Z)) (ahol a kizáró-vagyot jelöli) Megoldás: a) 4, b) 4, c) 5, d) 2, e) 4, f) 5, g) 4, h) 3, i) 2. 1.3. feladat. Soroljuk fel az alábbi formulák összes részformuláit! Húzzuk alá a közvetlen részformulákat! a) b) c) d) e) f) g) (((X Y ) (Y Z)) (¬X Z)) ((X Y ) ((X ¬Y ) ¬Y )) ((¬X Y ) ¬Z) ¬((X Y ) ¬X) ¬((X Y ) Z) ¬((X Y ) (X Y )) ((X Y ) (Y X))

1

Megoldás: a) {(((X Y ) (Y Z)) (¬X Z)), ((X Y ) (Y Z)), (¬X Z),
:::::::::::::::::::::::: ::::::::::

(X Y ), (Y Z), ¬X, Z, X, Y } b) {((X Y ) ((X ¬Y ) ¬Y )), (X Y ), ((X ¬Y ) ¬Y ),
::::::::: ::::::::::::::::::::

X, Y, (X ¬Y ), ¬Y } c) {((¬X Y ) ¬Z), (¬X Y ), ¬Z , ¬X, Y, Z, X}
::::::::::: :::

d) {¬((X Y ) ¬X), ((X Y ) ¬X), (X Y ), ¬X, X, Y }
::::::::::::::::::

e) {¬((X Y ) Z), ((X Y ) Z), (X Y ), Z, X, Y }
::::::::::::::::

f) {¬((X Y ) (X Y )), ((X Y ) (X Y )), (X Y ), (X Y ), X, Y }
::::::::::::::::::::::::

g) {((X Y ) (Y X)), (X Y ), (Y X), X, Y }
::::::::: :::::::::

1.4. feladat. Formalizáljuk az ítéletlogika nyelvén az alábbi állításokat! a) b) c) d) Némelyik emls tud repülni. Némelyik emls nem tud repülni. Minden prókátor hazudik. Semelyik prókátor sem hazudik.
(Forrás: Pólos L. ­ Ruzsa I. A logika elemei)

Megoldás: a) b) c) d) némelyik emls tud repülni némelyik emls nem tud repülni minden prókátor hazudik semelyik prókátor sem hazudik

Az elemi állítás egy ítéletváltozót jelöl, melyet az elemi állítás formalizálásával kaptunk.

1.5. feladat. Formalizáljuk az ítéletlogika nyelvén az alábbi állításokat! a) b) c) d) e) f) Minden emls tud repülni. Nem minden emls tud repülni. Semelyik emls nem tud repülni. Van olyan emls, amelyik tud repülni. Van olyan emls, amelyik nem tud repülni. Nincs olyan emls, amelyik nem tud repülni. Megoldás: M : Minden emls tud repülni. S: Semelyik emls nem tud repülni. a) M , b) ¬M , c) S, d) ¬S, e) ¬M , f) ¬¬M (vagy egyszeren M ). 2

1.6. feladat. Fordítsuk le (formalizáljuk) az ítéletlogika nyelvére az alábbi állításokat! a) b) c) d) Esik az es, bár süt a nap. Ha esik az es, és süt a nap, akkor szivárvány van, kivéve, ha éppen dél van. Nem áll, hogy nem igaz, hogy éppen dél van, és mégsem süt a nap. Ha esik az es, de nincs szivárvány, akkor nem süt a nap, vagy éppen dél van.

e) Ha nem kell várnom a reggelire, akkor ­ föltéve, hogy nem alszom el ­ idben beérek a munkahelyre. f) Ha elalszom, várnom kell a reggelire. g) Ha várnom kell a reggelire, pedig nem alszom el, akkor nem érek be idben a munkahelyre. h) Ha nem alszom el, a reggelire sem kell várnom, és idben be is érek a munkahelyre. i) Ha a szemtanú megbízható, és az írásszakért véleménye helytálló, úgy a bncselekményt akkor és csak akkor követték el elre megfontolt szándékkal, ha a talált ujjlenyomatok a tettestl vagy esetleges bntársától származnak. j) Ha a szemtanú megbízható, az írásszakért véleménye helytálló, és a talált ujjlenyomatok a tettestl származnak, akkor a bncselekményt elre megfontolt szándékkal követték el. k) Feltételezve, hogy a bncselekményt elre megfontolt szándékkal követték el, a talált ujjlenyomatok nem a tettestl származnak, sem pedig annak lehetséges bntársától, ezért ezesetben az írásszakért véleménye nem helytálló. l) De ha a bncselekményt nem elre megfontolt szándékkal követték el, akkor az írásszakért véleménye helytálló, annak ellenére, hogy a szemtanú nem megbízható. Megoldás: Formailag több megoldás is lehetséges, ezek szemantikai jelentése azonban megegyezik. a) (E S) b) (¬D ((E S) Sz)), vagy (((E S) ¬D) Sz) c) ¬¬(D ¬S) d) ((E ¬Sz) (¬S D)) e) (¬R (¬A I)), vagy ((¬R ¬A) I) f) (A R) g) ((R ¬A) ¬I) h) (¬A (¬R I)) i) j) k) l) ((M H) (B (UT UB ))) (((M H) UT ) B) (B ((¬UT ¬UB ) ¬H)) (¬B (H ¬M )) E: S: Sz: D: Esik az es. Süt a nap. Szivárvány van. Éppen dél van.

R: Várnom kell a reggelire. A: Elalszom. I: Idben beérek a munkahelyre. M : A szemtanú megbízható. H: Az írásszakért véleménye helytálló. B: A bncselekményt elre megfontolt szándékkal követték el. UT : A talált ujjlenyomatok a tettestl származnak. UB : A talált ujjlenyomatok a tettes esetleges bntársától származnak.

3

1.7. feladat. Logikai következménye-e a premisszáknak a konklúzió?
1.7.1. részfeladat.

P1 ) Éva szke, kivéve, ha barnára festeti a halyát. P2 ) Ádámnak csak akkor tetszik Éva, ha nem festeti barnára a halyát. K) Éva szke, vagy nem tetszik Ádámnak. Megoldás: P1 ) (¬B S) P2 ) (T ¬B) K) (S ¬T ) S: Éva szke. B: Éva barnára festeti a halyát. T : Éva tetszik Ádámnak.

S B T i i i i h h h h i i h h i i h h i h i h i h i h

(¬ B S ) (T ¬ B ) h h i i h h i i i i h h i i h h i i i i i i h h i i i i h h h h i h i h i h h i i i h i h h i i h h i i h h i i

(S ¬ T ) i i i h i i h i i i i h h i i h

Minden Boole-kombináció estén, melyekre a premisszák igazak, a konklúzió is igaz, ezért az logikai következménye a premisszáknak. Megjegyzés: Ha egy interpretáció esetén az egyik premissza hamis, akkor ezzel az interpretációval nem kell tovább foglalkozni. Ezért hiányoznak bizonyos sorok a fenti igazságtáblából.
1.7.2. részfeladat.

P1 ) Süt a nap, feltéve, hogy nem esik az es. P2 ) Nem süt a nap. P3 ) Vagy esik az es, vagy nem. K) Esik az es. Megoldás: P1 ) (¬ esik az es süt a nap ) P2 ) ¬ süt a nap P3 ) ( esik az es ¬ esik az es ) (A kizáró-vagy és a megenged-vagy jelentése ezesetben megegyezik.) K) esik az es A konklúzió következménye a premisszáknak. 4

1.7.3. részfeladat.

P1 ) Akkor és csak akkor csillagos az ég, ha éjjel hideg van. P2 ) Vagy csillagos az ég, vagy pedig felhs. P3 ) Ha nincs éjjel hideg, felhs az ég, és nem pedig csillagos. K) Nem igaz, hogy a felhs ég ellenére éjjel hideg van. Megoldás: P1 ) ( csillagos az ég éjjel hideg van ) P2 ) (( csillagos az ég felhs az ég ) (¬ csillagos az ég ¬ felhs az ég )) P3 ) (¬ éjjel hideg van ( felhs az ég ¬ csillagos az ég )) K) ¬( felhs az ég éjjel hideg van ) A konklúzió következménye a premisszáknak.

1.7.4. részfeladat.

P1 ) Van olyan emls, amely tud úszni, feltéve, hogy minden madár tud repülni. P2 ) Van olyan emls, amely nem tud úszni. K) Nem minden madár tud repülni. Megoldás: P1 ) (R U ) P2 ) ¬N K) ¬R U : Van olyan emls, amely tud úszni. N : Van olyan emls, amely nem tud úszni. R: Minden madár tud repülni.

A konklúzió nem következménye a premisszáknak.

1.7.5. részfeladat.

P) Kék is az ég, meg nem is. K) Esik az es. Megoldás: P) ( kék az ég ¬ kék az ég ) K) esik az es A konklúzió következménye a premisszának. (Logikai ellentmondásból bármi következik.)

1.7.6. részfeladat.

P) Péternek is tetszik Éva. 5

K) Vagy esik az es, vagy nem. Megoldás: P) Péternek tetszik Éva K) ( esik az es ¬ esik az es ) A konklúzió következménye a premisszának. (Logikai törvény bármibl következik.) 1.8. feladat. Ekvivalensek-e a feladatban szerpl állítások?
1.8.1. részfeladat.

a) Jancsi fiú, és Juliska lány, kivéve, ha rossz nevet adtak nekik. b) Csak akkor teljesül, hogy Jancsi fiú, és Juliska lány, ha nem adtak nekik rossz nevet. Megoldás: a) (¬R (F L)) b) ((F L) ¬R) F : Jancsi fiú L: Juliska lány R: Rossz nevet adtak nekik

F i i i i h h h h

L R i i h h i i h h i h i h i h i h

( ¬ R ( F L )) (( F L ) ¬ R ) h i h i h i h i i h i h i h i h i i i h i h i h i i i i h h h h i i h h h h h h i i h h i i h h i i i i h h h h i i h h h h h h i i h h i i h h h i i i i i i i h i h i h i h i i h i h i h i h

Igazságértékük nem egyezik meg minden Boole-kombináció estén, ezért nem ekvivalensek. (A továbbiakban az igazságtáblák elkészítését az olvasóra bízom.)

1.8.2. részfeladat.

a) Nincs sár, kivéve, ha esik az es. b) Csak akkor van sár, ha esik az es. Megoldás: a) (¬ esik az es ¬ sár van ) b) ( sár van esik az es ) A két formula ekvivalens. 6

1.8.3. részfeladat.

a) Szívesen sétálok, feltéve, hogy süt a nap, de nem fúj a szél. b) Csak akkor nem sétálok szívesen, ha nem süt a nap, vagy fúj a szél. c) Nem igaz, hogy nem sétálok szívesen, holott süt a nap, és a szél sem fúj. Megoldás: a) (( süt a nap ¬ fúj a szél ) szívesen sétálok ) b) (¬ szívesen sétálok (¬ süt a nap fúj a szél )) c) ¬(¬ szívesen sétálok ( süt a nap ¬ fúj a szél )) Mindhárom formula ekvivalens.
1.8.4. részfeladat.

a) Esik az es, kivéve, ha nincs felh az égen. b) Esik az es, vagy nincs felh az égen. Megoldás: a) (¬¬ van felh az égen esik az es ) b) ( esik az es ¬ van felh az égen ) A két formula ekvivalens. 1.9. feladat. Szemantikailag mit lehet mondani az alábbi formulákról? (tautológia | kielégíthet | ellentmondás) a) ((A B) (¬A B)) b) ((A B) ¬(A ¬B)) c) (((A B) C) (A (B C)) d) ((A (B C)) ((A B) C)) e) ((A (B C)) ((A B) (A C))) f) ((A (¬C B)) (¬A (B A))) g) (((A B) ¬C) (C ¬(A ¬B))) h) ((C A) ((B ¬A) A)) i) ((¬A B) (C (A B))) Megoldás: a) (( A B ) ( ¬ A B )) h h i i h i i i h i h i i i i i i i h h h h i i h i i i h i h i

Mivel a foperátor alatt csupa i szerepel (azaz minden interpretáció esetén igaz), a formula tautológia. Az a), b), d), e), f), h) és i) tautológia, a c) kielégíthet, míg a g) ellentmondás. 7

1.10. feladat. Az alábbi formulahalmazok közül melyek ellentmondásosak? a) b) c) d) e) f) g) h) {A B ¬C, A, {A B ¬C, A, {A B ¬C, A, {A B ¬C, A, {¬(A ¬B C), {¬(A ¬B C), {¬(A ¬B C), {¬(A ¬B C), Megoldás: a) AB¬C A ¬B C h h h h i i i i i i i i i h i i h h i i h h i i i h i i i h i i i h i h i h i h h i h i h i h i h h h h i i i i i i h h i i h h h h i i h h i i h i h i h i h i ¬B, C} ¬B, A ¬B} ¬B, A ¬B ¬C} ¬B, ¬¬A ¬B} B, A} B, A B ¬C} B, A ¬B} B, ¬A B}

Mivel bármely interpretáció esetén legalább egy formula hamis, a formulahalmaz kielégíthetetlen, azaz ellentmondásos. Az a) és h) halmazok ellentmondásosak, míg a többi kielégíthet.

1.11. feladat. Kielégíthetk-e az alábbi formulahalmazok. a) {¬Y, X Y, X Z} b) {¬Y, X Y, X Z, ¬Z} c) {¬Z, X V, X Y, Y Z, V W Z}
(Forrás: Pásztorné Varga K. ­ Várterész M. A matematikai logika alkalmazásszemlélet tárgyalása)

8

Megoldás: a) ¬Y i i h h i i h h h h i i h h i i X Y h h h h i i i i h h i i i i i i h h i i h h i i X Z h h h h i i i i i i i i h i h i h i h i h i h i

Mivel létezik olyan interpretáció (I(X) = i, I(Y ) = h, I(Z) = i), mely esetén mindegyik formula igaz, a formulahalmaz kielégíthet. c) 5 változó esetén az igazságtábla 32 sorból áll. Ennek vizsgálata már körülményes, viszont rövid formulák esetében létezik egy másik megközelítés. Ahhoz, hogy a formulahalmaz adott interpretáció esetén igaz legyen, minden formulának igaznak kell lennie. Keressünk egy ilyen interpretációt: I(¬Z) = 1 I(Z) = 0; I(Y Z) = 1 I(Y ) = 0; I(X Y ) = 1 I(X) = 0; I(X V ) = 1 I(V ) = 1; I(V (W Z)) = 1 I(W Z) = 1 I(W ) = 0. Ezen interpretáció esetén a formulahalmaz igaz, tehát kielégíthet. Az a) és c) halmazok kielégíthetek, míg a b) ellentmondásos. 1.12. feladat. Az alábbi formulák közül melyek KNF illetve melyek DNF formulák? a) b) c) d) e) f) ((A B) (¬A B)) ((A B ¬C) ¬A B) (¬A B) (¬(A B C) ¬B) (¬A B ¬C) (A (¬B ¬C) C) Megoldás: A b), c), e) formulák KNF, míg a c), e) és f) formulák DNF formulák. Megjegyzés: A c) illetve az e) formulák egyszerre KNF illetve DNF formulák is, ugyanis a literálok konjunkciója egyaránt tekinthet elemi konjunkciónak vagy egyelem diszjunkciók konjunkciójának (és ugyanez igaz a diszjunkcióra is). 1.13. feladat. KNF illetve DNF megfeleltetés.
1.13.1. részfeladat. A ¬(A ¬(B ¬(C ¬A))) formulának az alábbi formulák közül

melyek KNF formulái? 9

a) b) c) d)

(A C) (¬B C) (¬A B C) (¬A ¬B C) (¬A ¬B ¬C) ¬(A B) C A (C ¬B) Megoldás: Két tulajdonságot kell megvizsgálni: a formula KNF formula-e, és hogy ekvivalens-e az eredeti formulával. A b) és c) formulák nem KNF formulák, így ezekkel nem is kell tovább foglalkozni. ¬ ( A ¬ ( B ¬ ( C ¬ A ))) h h h h i i h i h h h h i i i i i i i i h h i h h h i i h h i h h h i i h h i i i i h h i i h i h h h h h i h i h i h i h i h i i i i i i h i h i i i i h h h h h h h h i i i i (A C )(¬ B C ) h h h h i i i i h i h i i i i i h i h i h i h i h i h i i i h i i i h h i i h h h h i i h h i i i i h i i i h i h i h i h i h i A (C ¬ B ) h h h h i i i i h h h h i i h i h i h i h i h i i i h i i i h i i i h h i i h h h h i i h h i i

Az igazságtábla alapján csak a d) formula ekvivalens az eredetivel, így csak ez a formula lehet az eredeti KNF formulája.

1.13.2. részfeladat. A ¬(C ¬(A ¬(B C))) formulának mely formulák DNF formulái?

a) b) c) d)

(A ¬B ¬C) (¬A B C) (¬A ¬B ¬C) C ¬(A B) (A ¬C) (¬B ¬C) ¬C (¬A ¬B) Megoldás: A b) és d) formulák nem DNF formulák, míg az a) formula nem ekvivalens az eredetivel. Így csak a c) formula az eredeti DNF formulája.

1.14. feladat. Hozzuk KNF és DNF formára a következ formulákat! a) b) c) d) e) ¬(X Y ¬X) ¬(X Y ¬Y ) (Z X) (¬(Y Z) X) ((X Y ) (Z ¬X)) (¬Y ¬Z) ((((X Y ) ¬X) ¬Y ) ¬Z) Z (X (Y Z)) ((X ¬Z) (X ¬Y ))
(Forrás: Pásztorné Varga K. ­ Várterész M. A matematikai logika alkalmazásszemlélet tárgyalása)

10

Megoldás: Egy formulának számtalan formailag különböz KNF (illetve DNF) formája lehet. Az alábbiakban egy-egy lehetséges megoldás található. (Más megoldás esetén meg kell vizsgálni, hogy megfelel-e a formai követelményeknek, valamint, hogy ekvivalens-e az eredeti formulával.) a) ¬(X Y ¬X) ¬(X Y ¬Y ) 0 / implikációk eltávolítása ¬(¬(X Y ) ¬X) ¬(¬(X Y ) ¬Y ) 0 / negációk bevitele ¨ ¬¬(X Y ) ¨¨ ¨¨ Y ) ¨¨ ¬¬X ¬¬(X ¬¬Y 0 / egyszersítés ¨ X Y egyszerre KNF és DNF $ $$ Y Z X b) $$$¬X) (Z DNF és KNF c) ((¬X Y ) Z X) Y ¬Z 0 / De Morgen azonosság @ @ @@ @@ X)) @@ X) @@@Z @ Y ¬Z (@@@ Z (¬X (Y DNF és KNF d) Z DNF és KNF e) (X Y ¬Z) (X Z) ¬X ¬Y DNF (X ¬X ¬Y ) (X Z ¬X ¬Y ) (Y X ¬X ¬Y ) (Y Z ¬X ¬Y ) (¬Z X ¬X ¬Y ) (¬Z Z ¬X ¬Y ) KNF (egyszersítés után azonosan igaz( ) formulát kapunk)

1.15. feladat. Írjuk fel a teljes zárójelezett alakját az alábbi formuláknak! a) b) c) d) e) f) (X Y Z ¬X) ¬Y ¬Z (X Y Z) (X ¬Z) X ¬Y X ¬Y Z Y X Y Z Z X ¬(Y Z) X ¬(X Y ¬X) ¬(X Y ¬Y ) (X ¬Y ) (¬X Y Z) X Y ¬Z Megoldás: a) b) c) d) e) f) ((X (Y (Z ¬X))) (¬Y ¬Z)) ((X (Y Z)) ((X ¬Z) (X ¬Y ))) ((X (¬Y (Z Y ))) (X (Y Z))) (Z (X (¬(Y Z) X))) (¬((X Y ) ¬X) ¬((X Y ) ¬Y )) ((X ¬Y ) ((¬X (Y Z)) (X (Y ¬Z))))

1.16. feladat. Hagyjuk el az alábbi formulákból a felesleges zárójeleket! a) b) c) d) e) ((X ¬Z) ((¬X Z) X) (Y ¬Z)) ((((X Y ) Z) ¬X) ¬Y ) ¬(X (Y (Z ¬(X ¬Y )))) (((X Y ) ¬Z) ((¬X Y ) ¬(¬Y Z))) (((¬X Y ) ¬Z) ((¬Y Z) (X (Y ¬Z)))) 11

Megoldás: a) b) c) d) e) (X ¬Z) (¬X Z) X (Y ¬Z) (((X Y ) Z) ¬X) ¬Y ¬(X Y Z ¬X ¬Y ) (X Y ) ¬Z (¬X Y ) ¬(¬Y Z) (¬X Y ¬Z) (¬Y Z) (X Y ¬Z)

Megjegyzés: A zárójelek a logikai összekötjelek közötti precedencia sorrend valamint a ill. a asszociatív tulajdonsága miatt hagyhatóak el.

12



Hasonló témájú dokumentumok

Hozzászólások

19. század 2009 2009. május 21. 9. a1 agresszió algoritmus antropológia barta ferenc bogarak definíciók elte ttk épszerk etikett eu szakképzési rendszerek eupol flaubert forgó mozgás gazdasági jog gazdaságpszichológia házi doga hidraulika hulladékkezelés inverz és összetett függvény kibernetika konfiguraciokonformacio. kosztolányi közigazgatás közoktatási rendszerek kurzusleírás leppelés lm görbe magyar barok magyar premodern mikro öko 1 reakció sejt statek gyakorlat számvitel ii. szervezes társadalombiztosítás tektonika természetvédelmi biológia toxikológia védett területek vezgazd word zh zh feladat