Felment´esek • Ha valaki tan´ ar szakos, akkor mivel neki elvileg a h´al´ oban nincs logika
r´esz, felment´est kaphat a logika gyakorlat ´es vizsga al´ ol. Az eredm´enye, ezek ut´an a sz´am´ıt´asel´elet r´eszb˝ ol el´ert eredm´eny lesz. • Ha valakinek m´ ar megvan P´asztorn´e Tan´arn˝ on´el a Logikai alapok a
˝ is felment´est kaphat, a jegye programoz´ashoz gyak/vizsga, akkor O u ´gy alakul mint fent. • Ha valakinek Sz´ am´ıt´aselm´eletb˝ol van meg a gyakjegy/vizsga, akkor
´ertelemszer˝ uen neki csak logik´ab´ol kell teljes´ıteni. A sz´am´ıt´aselm´elet r´esz kezdete a kurzusf´orumon id˝ oben megh´ırdet´esre ker¨ ul. FONTOS! A felment´es alapj´aul szolg´al´o gyakorlati jegyet legk´es˝ obb a vizsgaid˝ oszak 3. het´en be kell mutatni, k¨ ul¨onben a gyakorlati jegyhez ”Nem vizsg´azhat” ker¨ ul az ETR-ben bejegyz´esre. Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
1 / 1
´ ekel´es, jav´ıt´ Ert´ as, p´otl´as
Mindk´et r´eszb˝ ol 1-1 z´arthelyi dolgozat lesz, melyeken 50-50 pontot lehet szerezni. Egyik r´eszb˝ol felmentetteknek a pontsz´am´at dupl´azom. Tervezett ´ert´ekel´es: Valamelyik r´eszb˝ ol < 20 pont 40 − 54 55 − 69 70 − 84 85 − 100
el´egtelen(1) el´egs´eges(2) k¨ozepes(3) j´o(4) jeles(5)
P´ ot- ´es jav´ıt´ oz´arthelyi v´arhat´oan a vizsgaid˝oszak 1., a gyakorlati ut´ ovizsga a vizsgaid˝ oszak 3. het´en ker¨ ul lebonyol´ıt´asra.
Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
2 / 1
Seg´edanyagok 1. Gyakorlatf´ oli´ak, egy´eb online seg´edanyagok: http://www.cs.elte.hu/˜tichlerk ´ azlat a logika r´eszb˝ol Dr. P´asztor Endr´en´e honlapj´an: 2. Orav´ http://people.inf.elte.hu/pkata/ 3. Jegyzet a sz´am´ıt´aselm´elet r´eszb˝ol Dr. Gazdag Zsolt honlapj´an: http://people.inf.elte.hu/gazdagzs/ 4. P´asztorn´e Varga Katalin, V´arter´esz Magda: A matematikai logika alkalmaz´asszeml´elet˝ u t´argyal´asa (2003, Panem) 5. Christos H. Papadimitriu: Sz´am´ıt´asi bonyolults´ag, Egyetemi tank¨ onyv, Novadat, 1999. (Eredeti: Computational Complexity, Addison-Wesley Publ. Comp., Inc., 1994) 6. Demetrovics J´anos, Jordan Denev, Anton Pavlov: A sz´am´ıt´astudom´any matematikai alapjai, Tank¨ onyvkiad´ o, Budapest, 1985. Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
3 / 1
A nulladrend˝ u logika (´ıt´eletlogika) szintaktik´aja Logika ´es sz´ am´ıt´ aselm´elet, 1. gyakorlat
2009/10 II. f´el´ev
Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
4 / 1
A logika t´ argya A gondolkod´as egyik k¨ozismert form´aja a k¨ovetkeztet´es. Gondolkod´asforma vagy k¨ovetkeztet´esforma egy F = {A1 , A2 , . . . , An } ´all´ıt´ashalmazb´ ol ´es egy A ´all´ıt´asb´ol ´all´o (F, A) p´ar. Egy ´all´ıt´as a kontextust´ol f¨ uggetlen¨ ul vagy igaz (i) vagy hamis (h). Ezt az ´ert´eket az ´all´ıt´as igazs´ag´ert´ek´enek nevezz¨ uk. Az egyszer˝ u ´all´ıt´as egy olyan kijelent˝o mondat, mely egy individuumr´ ol ´all´ıt valamit. ¨ Osszetett ´all´ıt´as egy egyszer˝ u ´all´ıt´asokb´ol ´all´o ¨osszetett mondat, amelynek az igazs´ag´ert´eke csak az egyszer˝ u ´all´ıt´asok igazs´ag´ert´ekeit˝ ol f¨ ugg. Ez´ert az osszetett ´all´ıt´asok csak olyan nyelvtani ¨osszek¨ot˝ ¨ oszavakat tartalmazhatnak amelyek logikai m˝ uveleteknek feleltethet˝ok meg. Helyes k¨ ovetkeztet´esforma egy (F, A) p´ar, ha minden olyan esetben, amikor az F -ben minden ´all´ıt´as igaz, a k¨ovetkezm´eny ´all´ıt´as is igaz, A logika t´argya az egyszer˝ u ´all´ıt´asok ´es a bel˝ol¨ uk logikai m˝ uveletekkel kapott ¨ osszetett ´all´ıt´asok vizsg´alata, az ¨osszef¨ ugg´esek felt´ar´asa. A helyes gondolkod´asform´ak kiv´alaszt´asa ´es u ´jak keres´ese. Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
5 / 1
Egyszer˝ u´ all´ıt´ asok ´ ıt´as-e? 1. Feladat: All´ 1 K´ etszer kett˝ o az ¨ot. Igen. 2 Holnap meg´ ırom a leck´em. Nem. J¨ ov˝ o idej˝ u. 3 A vil´ agbajnok magyar labdar´ ug´ov´alogatott kapusa a Real Madridhoz igazolt. Nem. Nem l´etez˝o szem´elyr˝ol sz´ol. 4 Iskol´ ank tan´ara 50 ´eves. Nem. Nem meghat´arozott alany. 5 x nagyobb, mint 3, ahol x eleme a term´ eszetes sz´amoknak. Nem. Nem meghat´arozott alany. 6 ,,Minden kr´ etai hazudik”. Mondta az ´altalam ismert egyetlen kr´etai. Nem. Nem meghat´arozhat´o az igazs´ag´ert´eke. 7 Mi ´ ertelme ennek a feladatnak? Nem. Nem kijelent˝o mondat. Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
6 / 1
¨ Osszetett all´ıt´ ´ asok, k¨ovetkeztet´esi form´ak 2. Feladat: Helyes-e az al´abbi okoskod´as? Mi az okoskod´as s´em´aja? 1
Ha n´alam van a kapukulcs, akkor ki tudom nyitni a kaput. N´alam van a kapukulcs. Ki tudom nyitni a kaput. Ha A akkor B. A. Teh´at B. Helyes.
2
Ha a benzin elfogyott az aut´ob´ol, akkor az aut´ o meg´all. Nem fogyott el a benzin. Teh´at az aut´o nem ´all meg. Ha A akkor B. Nem A. Teh´at nem B. Helytelen. Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
7 / 1
´ eletlogikai formul´ak It´ Az ´ıt´eletlogika le´ır´ o nyelve (L0 )
Adott (megsz´aml´alhat´oan) v´egtelen sok u ´n. ´ıt´eletv´altoz´ o: X ; Y ; Z ; X1 ; X2 ; . . . , (ezek halmaz´at jel¨olje Vv ), tov´abb´a a ¬; ∧; ∨; ⊃; (; ) szimb´olumok. Az ´ıt´eletlogikai formul´ ak rekurz´ıv defin´ıci´ oja • Az ´ıt´ eletv´altoz´ok ´ıt´eletlogikai formul´ak. • Ha A ´ es B ´ıt´eletlogikai formul´ak, akkor ¬A, (A ∧ B), (A ∨ B), (A ⊃ B)
is ´ıt´eletlogikai formul´ak. • Csak az els˝ o k´et pont v´eges sokszori alkalmaz´as´aval kapott (v´eges)
sorozatok az ´ıt´eletlogikai formul´ak. Az ´ıt´eletv´altoz´ ok az egyszer˝ u ´all´ıt´asok halmaz´at futj´ak be. Az ¨ osszetett ´all´ıt´asokat fel´ep´ıt˝ o egyszer˝ u ´all´ıt´asokat ´ıt´eletv´altoz´ okra cser´elve formul´at nyer¨ unk. Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
8 / 1
´ eletlogikai formul´ak It´ Logikai ¨ osszetetts´eg, k¨ ozvetlen r´eszformula
Az ´ıt´eletlogikai formul´ ak logikai ¨ osszetetts´eg´enek rekurz´ıv defin´ıci´ oja • Az X ´ıt´ eletv´altoz´o logikai ¨osszetetts´ege 0, azaz `(X ) = 0. • `(¬A) = `(A) + 1. • `(A ◦ B) = `(A) + `(B) + 1, ahol ◦ ∈ {∧, ∨, ⊃}.
K¨ ozvetlen r´eszformula rekurz´ıv defin´ıci´ oja • Az X ´ıt´ eletv´altoz´onak nincs k¨ozvetlen r´eszformul´aja. • ¬A k¨ ozvetlen r´eszformul´aja A. • A ◦ B k¨ ozvetlen r´eszformul´aja A ´es B, ahol ◦ ∈ {∧, ∨, ⊃}.
Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
9 / 1
´ eletlogikai formul´ak It´ R´eszformula, logikai m˝ uveletek hat´ ask¨ ore
R´eszformula rekurz´ıv defin´ıci´ oja • Maga a formula r´ eszformul´aja ¨onmag´anak. • Formula r´ eszformul´aj´anak k¨ozvetlen r´eszformul´ai r´eszformul´ai a
formul´anak. • Csak ezek a formula r´ eszformul´ai.
Logikai m˝ uveletek hat´ ask¨ ore A logikai m˝ uveletek hat´ask¨ore a formula r´eszformul´ai k¨ oz¨ ul az a legkisebb logikai ¨ osszetetts´eg˝ u, amelyben az adott logikai ¨ osszek¨ ot˝ ojel el˝ ofordul.
Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
10 / 1
´ eletlogikai formul´ak It´ F˝ o logikai o ¨sszek¨ ot˝ o, szerkezeti fa
Formula f˝ o m˝ uveleti jele (logikai ¨ osszek¨ o˝ oje) Formula f˝ o m˝ uveleti jele az a logikai m˝ uvelet, melynek hat´ask¨ ore az eg´esz formula. A f˝ o logikai ¨ osszek¨ ot˝o alapj´an megk¨ ul¨onb¨oztet¨ unk neg´aci´ os (¬), konjunkci´ os (∧), diszjunkci´os (∨), implik´aci´os (⊃) formul´akat. Formula szerkezeti f´ aja Olyan gy¨ okeres, cs´ ucsc´ımk´ezett, bin´aris fa, ahol a gy¨ ok´er c´ımk´eje maga a formula, a cs´ ucsok c´ımk´ei pedig a formula r´eszformul´ai. Egy cs´ ucs gyerekeinek c´ımk´ei a cs´ ucsnak megfelel˝o r´eszformula k¨ ozvetlen r´eszformul´ai.
Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
11 / 1
´ eletlogikai formul´ak It´ ´ It´eletlogikai formul´ ak szerkezete
3. Feladat: K´esz´ıts¨ unk ´ıt´eletlogikai formul´akat az X , Y ´es Z ´ıt´eletv´altoz´ ok felhaszn´al´as´aval ´es hat´arozzuk meg a logikai ¨osszetetts´eg¨ uket. Rajzoljuk fel egy legal´abb 3 ¨ osszetetts´eg˝ u formula szerkezeti f´aj´at ´es hat´arozzuk meg az ¨osszes r´eszformul´aj´at! X ; ¬X ; (X ∨ Z ); (¬X ∨ Z ); ¬(¬X ∨ Y ); ((¬X ∨ X ) ⊃ ¬(Y ∧ Z )) Logikai ¨ osszetets´eg: 0;1;1;2;3;5 ((¬X ∨ X ) ⊃ ¬(Y ∧ Z )) (¬X ∨ X ) ¬X
X
X
¬(Y ∧ Z ) (Y ∧ Z ) Y
Logika (1. gyakorlat)
Z
A cs´ ucsok c´ımk´ei a r´eszformul´ak.
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
12 / 1
´ eletlogikai formul´ak It´ Z´ ar´ ojelelhagy´ as
Priorit´ asi sorrend: ¬, ∧, ∨, ⊃ Z´ar´ ojelelhagy´as c´elja egy formul´ab´ol a legt¨obb z´ar´ ojel elhagy´asa a formula szerkezet´enek megtart´asa mellett. • a formula k¨ uls˝ o z´ar´ojel p´arj´anak elhagy´asa (ha m´eg van ilyen) • egy bin´ er logikai ¨osszek¨ot˝o hat´ask¨or´ebe es˝ o r´eszformul´ak k¨ uls˝ o
z´ar´ ojelei akkor hagyhat´ok el, ha a r´eszformula f˝ o logikai ¨ osszek¨ ot˝ ojele nagyobb priorit´as´ u n´ala. L´ancformul´ak z´ar´ ojelelhagy´asa: • Konjunkci´ o illetve diszjunkci´ol´anc eset´en minden bels˝ o z´ar´ ojel
elhagyhat´ o. • Implik´ aci´ ol´anc: (X1 ⊃ (X2 ⊃ (X3 ⊃ . . . Xn ))) a default z´ar´ ojelez´es.
Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
13 / 1
´ eletlogikai formul´ak It´ Feladatok
4. Feladat: Jel¨ olj¨ uk be az al´abbi formul´akban az egyes logikai ¨ osszek¨ ot˝ ok hat´ask¨ or´et! a. ( ( ( ( X ⊃ Y ) ∧ ( Y ⊃ Z ) ) ⊃ ¬X ) ∨ Z )
b.
( ( ( P ∨ Q ) ∧ ¬R ) ∧ ( R ⊃ ( ¬R ⊃ Q ) ) )
Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
14 / 1
´ eletlogikai formul´ak It´ Feladatok 2.
5. Feladat: Adjuk meg, hogy mennyire ¨osszetettek az al´abbi formul´ak! Hagyjuk el a lehet˝ o legt¨obb z´ar´ojelet az al´abbi formul´akb´ ol! 1
(((X ⊃ Y ) ∧ (Y ⊃ Z )) ⊃ (¬X ∨ Z ))
2
((P ⊃ Q) ⊃ (Q ⊃ P))
3
(((X ⊃ (¬Y ∧ Z )) ∨ (X ∧ Y )) ∨ Z )
4
((Q ⊃ (P ∧ R)) ∧ ¬((P ∨ R) ⊃ Q))
6. Feladat: Jel¨ olj¨ uk be az al´abbi formul´akban az egyes logikai ¨ osszek¨ ot˝ ok hat´ask¨ or´et! 1
(X ⊃ Y ∧ (Y ⊃ Z ) ⊃ ¬X ) ∨ Z
2
P ⊃ Q ∧ ¬R ∨ ¬P ⊃ Q
Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
15 / 1
´ eletlogikai formul´ak It´ Feladatok
7. Feladat: D¨ onts¨ uk el, hogy mi igaz az al´abbi karaktersorozatokra! 1
P ⊃ Q ⊃ R ∧ ¬(P) ⊃ P nem formula/ neg´aci´os / konjunkci´os/ diszjunkci´ os/ implik´aci´ os
2
(P ∨ Q) ∨ R ∧ (¬P ⊃ P) nem formula/ neg´aci´os /konjunkci´ os/ diszjunkci´ os/ implik´aci´ os
3
P ∧ Q¬(Q ∨ R) ∧ ¬(P ⊃ P) nem formula/ neg´aci´os / konjunkci´ os/ diszjunkci´ os/ implik´aci´ os
4
(P ⊃ R) ⊃ ((Q ⊃ R) ⊃ (P ∨ Q ⊃ R) nem formula/ neg´aci´os / konjunkci´ os/ diszjunkci´ os/ implik´aci´ os
5
Q ⊃ (P ∧ R) ∧ ¬(P ∨ R) ∨ Q nem formula/ neg´aci´os / konjunkci´ os/ diszjunkci´ os/ implik´aci´ os
Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
16 / 1
´ eletlogikai formul´ak szemantik´aja It´ Defin´ıci´ o
L0 interpret´aci´ oja: I : Vv → {i, h} f¨ uggv´eny. Formul´ ak igazs´ agki´ert´ekel´es´enek rekurz´ıv defin´ıci´ oja Egy I interpret´aci´ oban egy A formula BI (A) igazs´ag´ert´ek´et (helyettes´ıt´esi ´ert´ek´et) a k¨ ovetkez˝ ok´eppen kapjuk meg: • ha A ´ıt´ eletv´altoz´o, akkor BI (A) := I(A), • BI (¬A) := ¬BI (A), • BI (A ◦ B) := BI (A) ◦ BI (B), ahol ◦ ∈ {∧, ∨, ⊃}
A logikai m˝ uveletek k¨oz¨os igazs´agt´abl´aja: A B ¬A A ∧ B A ∨ B A ⊃ B i i h i i i i h h h i h h i i h i i h h i h h i Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
17 / 1
Igazs´agt´abla Egy formula igazs´ag´ert´eke csak a benne szerepl˝ o ´ıt´eletv´altoz´ ok ki´ert´ekel´es´et˝ ol f¨ ugg. Legyenek X1 , . . . , Xn az A formul´aban szerepl˝ o ´ıt´eletv´altoz´ ok. B´ azis Az ´ıt´eletv´altoz´ ok egy sorrendje. 2n lehets´eges interpret´aci´o van (ha nem t¨or˝od¨ unk a formul´aban nem szerepl˝ o ´ıt´eletv´altoz´ ok ki´ert´ekel´es´evel). Igazs´ agt´ abla Egy A ´ıt´eletlogikai formula igazs´agt´abl´aja egy 2n × (n + 1)-es t´abl´azat, ha X1 , . . . , Xn az A formul´aban szerepl˝o ´ıt´eletv´altoz´ ok. A sorok megfelelnek a lehets´eges interpret´aci´oknak. Az els˝o n oszlop tartalmazza az ´ıt´eletv´altoz´ ok ki´ert´ekel´es´et. Az I interpret´aci´ohoz tartoz´ o sor n + 1. oszlopa pedig BI (A)-t. Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
18 / 1
´ eletlogikai formul´ak szemantik´aja It´ Feladatok
8. Feladat: ´Irjuk fel a ,,kiz´ar´o vagy” igazs´agt´abl´aj´at! A B A⊕B i i h i h i h i i h h h 9. Feladat: K´esz´ıts¨ uk el az al´abbi formul´ak igazs´agt´abl´aj´at! (B´azis: az ´ıt´eleletv´altoz´ ok ´ab´ec´esorrendj´eben.) P Q P ⊃Q ∧P 1 P ⊃Q ∧P i i i 2 X ∨ ¬Y ∧ X i h h 3 X ⊃ ¬Y ⊃ Z h i i 4 P ⊃ Q ⊃ R ∧ ¬(R ⊃ P) h h h Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
19 / 1
´ eletlogikai formul´ak szemantik´aja It´ Feladatok2
Szemantikus fa X1 , . . . , Xn b´azis. Az A ´ıt´eletlogikai formula szemantikus f´aja: Teljes ´elcimk´ezett bin´aris fa, az i. szinten az ´elek c´ımk´eje felv´altva Xi ´es ¬Xi . Minden lev´el megfelel egy I interpret´aci´onak. Xi ´ag: I(Xi ) = i, ¬Xi ´ag: I(Xi ) = h. A levelek al´a ´ırjuk BI (A)-t. 10. Feladat: K´esz´ıts¨ uk el az el˝oz˝o feladat formul´ainak szemantikus f´ait. X ⊃ ¬Y ⊃ Z X ¬X Y
¬Y
Z
¬Z
Z
¬Z
i
i
i
h
Logika (1. gyakorlat)
Y
¬Y
Z
¬Z
Z
¬Z
i
i
i
i
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
20 / 1
´ eletlogikai formul´ak szemantik´aja It´ Feladatok3
11. Feladat: Fejezz¨ uk ki az ⊃-t ´es a kiz´ar´o vagyot csak a ¬, ∧, ∨ logikai m˝ uveletek seg´ıts´eg´evel! X Y X ⊃ Y ¬X ∨ Y X ⊕ Y ¬X ∧ Y ∨ X ∧ ¬Y i i i i h h i h h h i i h i i i i i h h i i h h 12. Feladat: Bizony´ıtsuk be igazs´agt´abl´aval, hogy az ({A ⊃ B, ¬A}, ¬B) k¨ ovetkeztet´esi forma nem helyes! A B A ⊃ B ¬A ¬B i i i h h i h h h i h i i i h h h i i i Logika (1. gyakorlat)
0-adrend˝ u szintaktika
2009/10 II. f´ el´ ev
21 / 1
