6
Kapitola 2
Pˇ r´ıklady z predik´ atov´ e logiky 2.1
Formule predik´ atov´ e logiky
2.1.1 Pˇ r´ıklad. Napiˇste formule predik´atov´e logiky odpov´ıdaj´ıc´ı n´asleduj´ıc´ım vˇet´ am. Pouˇzijte k tomu predik´atov´ ych symbolu uveden´ ych v textu. a) Nˇekdo m´ a hudebn´ı sluch (S) a nˇekdo nem´a hudebn´ı sluch. b) Nˇekter´e dˇeti (D) nerady ˇcokol´adu (C). c) Nikdo, kdo nebyl pouˇcen o bezpeˇcnosti pr´ace (P ), nesm´ı pracovat v laboratoˇr´ıch (L). d) Ne kaˇzd´ y talentovan´ y mal´ıˇr (T ) vystavuje obrazy v N´arodn´ı galerii (G). e) Pouze studenti (S) maj´ı n´arok na studen´e veˇceˇre (V ). f) Ne kaˇzd´ y ˇclovˇek (C), kter´ y m´a drah´e lyˇze (D), je ˇspatn´ y lyˇzaˇr (S). V´ ysledek: a) (∃x S(x)) ∧ (∃x ¬S(x)); b) ∃x (D(x) ∧ ¬C(x)); c) ∀x (¬P (x) ⇒ ¬L(x)); d) ¬(∀x (T (x) ⇒ G(x))); e) ∀x (V (x) ⇒ S(x)); f) ¬[∀x ((C(x) ∧ D(x)) ⇒ S(x))]. 2.1.2 Pˇ r´ıklad. Pro n´ asleduj´ıc´ı vˇety popiˇste jazyk predik´atov´e logiky (tj. predik´ aty, konstantn´ı symboly a funkˇcn´ı symboly), kter´ y potˇrebujete k formalizaci a napiˇste formule odpov´ıdaj´ıc´ıch vˇet. a) Karel vidˇel Shakespearovu hru Hamlet. b) Karel vidˇel nˇekterou Shakespearovu hru. c) Nˇekdo vidˇel Shakespearovu hru Hamlet. d) Nˇekdo vidˇel nˇekterou Shakespearovu hru. Marie Demlov´ a: Pˇr´ıklady k pˇredmˇetu Logika a grafy
6. dubna 2014, 21:52
2.1. Formule predik´ atov´e logiky
[140406-2152 ]
7
e) Ne kaˇzd´ y vidˇel nˇekterou Shakespearovu hru. f) Karel vidˇel pouze hry od Shakespeara. g) Lucernu nenapsal Shakespeare. V´ ysledek: Naˇse universum U tvoˇr´ı lid´e a hry. Pro prvn´ı ˇctyˇri vˇety by staˇcil tento jazyk L: Pred = {V }, kde V je tern´arn´ı predik´atov´ y symbol, kde V (x, y, z) m´ a v´ yznam: osoba x vidˇela hru y od autora z“. (Tj. na druh´em ” m´ıstˇe trojice (x, y, z) mus´ı b´ yt hra, na prvn´ım a tˇret´ım mus´ı b´ yt osoba.) D´ale Konst = {k, h, s}, kde k je osoba Karel, h je hra Hamlet a s je Shakespeare. Formule maj´ı tvar: a) V (k, h, s); b) ∃y V (k, y, s); c) ∃x V (x, h, s); d) ∃x ∃y V (x, y, s). Chceme-li popsat vˇsechny vˇety, zavedeme jin´e predik´atov´e symboly: Naˇse universum U je stejn´e. Pred = {H, O, V, N }, kde H a O jsou un´arn´ı predik´aty, H znamen´ a b´ yt hrou“, O znamen´ a b´ yt osobou“, V (x, y) a N (x, y) jsou bin´arn´ı ” ” predik´ aty: V (x, y) znamen´ a osoba x vidˇela hru y“ a N (x, y) znamen´a osoba ” ” x napsala hru y“. D´ ale Konst = {k, h, s, l}, kde k je Karel“, h je Hamlet“, s ” ” je Shakespeare“ a l je Lucerna“. Formule maj´ı tvar: ” ” a) N (s, h) ∧ V (k, h); b) ∃x (H(x) ∧ V (k, x) ∧ N (s, x)); c) ∃x (O(x) ∧ V (x, h) ∧ N (s, h)); d) ∃x ∃y (O(x) ∧ H(y) ∧ V (x, y) ∧ N (s, y)); e) ¬[∀x (O(x) ⇒ (∃y (H(y) ∧ V (x, y) ∧ N (s, y)))]; f) ∀x [(H(x) ∧ V (k, x)) ⇒ N (s, x)]; g) ¬N (s, l). 2.1.3 Pˇ r´ıklad. Popiˇste interpretaci, kterou potˇrebujete, abyste zformalisovali n´ asleduj´ıc´ı vˇety jako sentence predik´atov´eho poˇctu. ˇ a) Ctverec lich´eho ˇc´ısla je vˇzdy lich´e ˇc´ıslo. b) Je-li libovoln´e ˇc´ıslo dˇeliteln´e ˇsesti, je dˇeliteln´e i tˇremi. c) Existuj´ı ˇc´ısla a, b, c takov´ a, ˇze souˇcet druh´ ych mocnin a a b je roven druh´e mocninˇe c. V´ ysledek: a) U = Z, Pred = {L}, kde L znamen´a b´ yt lich´ y“, Func = {o}, ” kde o(x) je ˇctverec ˇc´ısla x. Formule m´a tvar ∀x (L(x) ⇒ L(o(x))). b) U = Z, Pred = {P, Q}, kde P znamen´a b´ yt dˇeliteln´ y 6“, Q znamen´a ” b´ yt dˇeliteln´ y 3“. Formule m´ a tvar ∀x (P (x) ⇒ Q(x)). ” c) U = Z, Pred = {R}, R je bin´ arn´ı predik´atov´ y symbol a m´a v´ yznam rovnosti, Func = {o, s}, kde o(x) je un´arn´ı a znamen´a ˇctverec ˇc´ısla x a s(x, y) je bin´ arn´ı a znamen´ a souˇcet ˇc´ısel x a y. Formule m´a tvar ∃x ∃y ∃z R(s(o(x), o(y)), o(z)). (Kdybychom zavedli rovnost jako predik´atov´ y symbol =, kter´ y m´a vˇzdy v´ yznam rovnosti, mohli bychom formuli ps´ at ve tvaru: ∃x ∃y ∃z s(o(x), o(y)) = o(z).) 2.1.4 Pˇ r´ıklad. V n´ asleduj´ıc´ıch formul´ıch oznaˇcte vˇsechny v´azan´e v´ yskyty promˇenn´ ych a vˇsechny voln´e v´ yskyty promˇenn´ ych. Kter´e z formul´ı jsou sentence a kter´e otevˇren´e formule? a) ∀x ∃y Q(x, y); Marie Demlov´ a: Pˇr´ıklady k pˇredmˇetu Logika a grafy
6. dubna 2014, 21:52
ˇ ´IKLADY Z PREDIKATOV ´ ´ LOGIKY [140406-2152 ] KAPITOLA 2. PR E
8
b) Q(f (a, b), y) ⇒ (∃y P (s(y))); c) Q(a, b) ∨ (∀x Q(a, x)); d) Q(x, y) ⇒ Q(y, x); e) Q(a, b) ∧ (∃x ∃y Q(x, y)); f) (∀x Q(a, x)) ⇒ (∀x ∃y Q(y, x)).
2.2
S´ emantika predik´ atov´ e logiky
2.2.1 Pˇ r´ıklad. Speci´ aln´ı symboly jazyka L predik´atov´e logiky jsou tyto: Pred = {P, Q}, kde P je un´arn´ı a Q je bin´arn´ı predik´atov´ y symbol, Func = {f, g}, kde f je un´ arn´ı a g je bin´arn´ı funkˇcn´ı symbol, Konst = {a, b, c}. Je d´ ana interpretace hU, [[−]]i, kde U je mnoˇzina pˇrirozen´ ych ˇc´ısel; [[a]] = 0, [[b]] = 1, [[c]] = 3, [[f ]]: n 7→ n2 , tj. f odpov´ıd´a pov´ yˇsen´ı na druhou, [[g]]: (m, n) 7→ m + n, tj. g odpov´ıd´a souˇctu, [[P ]] = {2n | n ∈ N}, tj. P odpov´ıd´a vlastnosti b´ yt sud´ ym“, ” [[Q]] = {(m, n) | m je dˇelitelem n}, tj. Q odpov´ıd´a relaci dˇelitelnosti“. ” Rozhodnˇete o pravdivosti nebo nepravdivosti n´asleduj´ıc´ıch sentenc´ı: a) P (c); b) P (f (a)); c) P (g(a, f (b))); d) Q(a, f (b)); e) Q(f (b), a); f) ∀x Q(x, x); g) ∃x Q(f (x), x); h) ∀x (Q(c, x) ⇒ Q(b, x)); i) ∀x (Q(b, x) ⇒ Q(c, x)); j) ∃x (P (f (x)) ∧ P (x)); k) ∃x ∃y (P (x) ∧ P (y) ∧ P (g(x, y))); l) ∃x ∃y (¬P (x) ∧ ¬P (y) ∧ P (g(x, y))). V´ ysledek: a) Nepravdiv´a; b) pravdiv´a; c) nepravdiv´a; d) nepravdiv´a; e) pravdiv´ a; f) nepravdiv´ a (protoˇze 0 nedˇel´ı 0); g) pravdiv´a; h) pravdiv´a; i) nepravdiv´ a; j) pravdiv´ a; k) pravdiv´a; l) pravdiv´a. Marie Demlov´ a: Pˇr´ıklady k pˇredmˇetu Logika a grafy
6. dubna 2014, 21:52
2.2. S´emantika predik´ atov´e logiky
[140406-2152 ]
9
2.2.2 Pˇ r´ıklad. Pro n´ asleduj´ıc´ı sentence rozhodnˇete, zda se jedn´a o tautologie, kontradikce nebo splniteln´e sentence, kter´e nejsou tautologie. (P je un´arn´ı predik´ atov´ y symbol, Q je bin´ arn´ı predik´atov´ y symbol.) a) (∃x P (x)) ∨ (∃x ¬P (x)); b) ∀x (P (x) ∨ ¬P (x)); c) (∃x P (x)) ⇒ (∀x P (x)); d) (∀x P (x)) ∧ (∃x ¬P (x)); e) ∀x [∃y Q(x, y) ∨ ∀z ¬Q(x, z)]. V´ ysledek: a) Tautologie. b) Tautologie. c) Splniteln´ a formule, kter´ a nen´ı tautologie. Zduvodnˇen´ı: Sentence (∃x P (x)) ⇒ (∀x P (x)) je pravdiv´ a kdykoli je nepravdiv´a sentence ∃x P (x). Uvaˇzujme interpretaci: U je mnoˇzina re´ aln´ ych ˇc´ısel, predik´atov´ y symbol P odpov´ıd´a vlastnosti b´ yt odmocninou z −1“. Protoˇze ˇz´adn´e re´aln´e ˇc´ıslo vlastnost [[P ]] nem´a, ” je naˇse sentence pravdiv´ a v hU, [[−]]i. Na druh´e stranˇe uvaˇzujme interpretaci: U 0 je mnoˇzina pˇrirozen´ ych ˇc´ısel, P odpov´ıd´a vlastnosti b´ yt sud´ y“. Pak formule ” ∃x P (x) je pravdiv´ a v t´eto interpretaci, protoˇze existuje sud´e pˇrirozen´e ˇc´ıslo. Formule ∀x P (x) ovˇsem pravdiv´ a nen´ı, protoˇze ne vˇsechna pˇrirozen´a ˇc´ısla jsou sud´ a. Tedy formule (∃x P (x)) ⇒ (∀x P (x)) nen´ı pravdiv´a v t´eto interpretaci. d) Kontradikce. e) Tautologie. 2.2.3 Pˇ r´ıklad. K formuli ϕ naleznˇete formuli ψ tautologicky ekvivalentn´ı s formul´ı ¬ϕ a takovou, ˇze ψ m´ a negace pouze tˇesnˇe pˇred atomick´ ymi formulemi. (P je un´ arn´ı predik´ atov´ y symbol, R je bin´arn´ı predik´atov´ y symbol a a je konstantn´ı symbol.) a) ∀x [P (x) ⇒ (∃y (P (y) ∧ R(x, y)))]; b) P (a) ∨ [∃z (P (z) ∧ ∀y (R(y, z) ⇒ ¬P (y)))]. V´ ysledek: a) ∃x [P (x) ∧ ∀y (¬P (y) ∨ ¬R(x, y))]; b) ¬P (a) ∧ [∀z (¬P (z) ∨ (∃y(R(y, z) ∧ P (y))))]. 2.2.4 Pˇ r´ıklad. Rozhodnˇete, zda n´asleduj´ıc´ı mnoˇziny sentenc´ı jsou splniteln´e nebo nesplniteln´e. Zduvodnˇete. (P a R jsou un´arn´ı predik´atov´e symboly, Q je bin´ arn´ı predik´ atov´ y symbol.) a) S = {∀x ∃y Q(x, y), ∀x ¬Q(x, x)}; b) M = {∃x ∀y Q(x, y), ∀x ¬Q(x, x)}; c) N = {∀x (P (x) ∨ R(x)), ¬∃x R(x), ¬P (a)}. V´ ysledek: a) S je splniteln´ a. Jej´ı model je napˇr. tato interpretace: U = N, [[Q]] je relace < na mnoˇzinˇe N, tj. [[Q]] = {(m, n) | m < n}. Pak pro kaˇzd´e pˇrirozen´e ˇc´ıslo n existuje ˇc´ıslo vˇetˇs´ı (napˇr. n + 1) a ˇz´adn´e pˇrirozen´e ˇc´ıslo nen´ı vˇetˇs´ı neˇz ono samo. b) M je nesplniteln´ a. Pˇreˇctˇeme si“ prvn´ı formuli: Existuje prvek, ˇreknˇeme ” ” d, takov´ y, ˇze pro kaˇzd´ y prvek y dvojice (d, y) m´a vlastnost Q.“ Dosad´ıme-li za y Marie Demlov´ a: Pˇr´ıklady k pˇredmˇetu Logika a grafy
6. dubna 2014, 21:52
ˇ ´IKLADY Z PREDIKATOV ´ ´ LOGIKY [140406-2152 ]KAPITOLA 2. PR E
10
prvek d, m´ a dvojice (d, d) tak´e vlastnost Q. Tud´ıˇz nen´ı moˇzn´e aby byla pravdiv´a druh´ a formule mnoˇziny M , kter´a ˇr´ık´a: Pro ˇz´adn´ y prvek x dvojice (x, x) nem´a ” vlastnost Q.“ Form´ alnˇe: Vezmˇeme libovolnou interpretaci hU, [[−]]i, v n´ıˇz je pravdiv´a formule ∃x ∀y Q(x, y). Pak existuje prvek d ∈ U , tak, ˇze pro kaˇzd´ y prvek d0 ∈ U 0 dvojice (d, d ) ∈ [[Q]]. Proto tak´e (d, d) ∈ [[Q]]. To ovˇsem znamen´a, ˇze sentence ∀x ¬Q(x, x) nen´ı pravdiv´a v hU, [[−]]i. c) N je nesplniteln´ a. Pˇreˇctˇeme si“ prvn´ı a tˇret´ı sentenci: Kaˇzd´ y prvek m´a ” ” vlastnost P nebo vlastnost R.“ Prvek a nem´a vlastnost P .“ Jsou-li obˇe tyto ” sentence pravdiv´e v nˇekter´e interpretaci, pak v t´eto interpretaci mus´ı prvek a ˇ adn´ m´ıt vlastnost R. To ovˇsem znamen´a, ˇze nen´ı pravdiv´a druh´a sentence: Z´ y ” prvek nem´ a vlasntost R.“ Form´ alnˇe: Vezmˇeme libovolnou interpretaci hU, [[−]]i, v n´ıˇz je pravdiv´a prvn´ı a tˇret´ı sentence. Pak existuje prvek d ∈ U (d = [[a]]) takov´ y, ˇze d 6∈ [[P ]]. Protoˇze je pravdiv´ a sentence ∀x (P (x) ∨ R(x)), mus´ı b´ yt pravdiv´a sentence P (a) ∨ R(a). To ale znamen´ a, ˇze je pravdiv´a i R(a) a tud´ıˇz d = [[a]] ∈ [[R]]. Tedy sentence ∀x ¬R(x) je nepravdiv´ a v hU, [[−]]i.
2.3
Rezoluˇ cn´ı metoda v predik´ atov´ e logice
2.3.1 Pˇ r´ıklad. Pro kaˇzd´e dva n´asleduj´ıc´ı liter´aly rozhodnˇete, zda existuje substituce, po n´ıˇz se stanou stejn´ ymi liter´aly. V kladn´em pˇr´ıpadˇe najdˇete nejobecnˇejˇs´ı takovou substituci. a) (P (x, y), P (t, f (z)); b) Q(a, y, f (y)), Q(z, z, u); c) R(x, g(x)), R(y, y); d) F (a, x), F (y, b); e) Q(x, f (y), z), Q(g(w), u, g(w)); f) P (g(x), y), P (u, f (w)). V´ ysledek: a) Po substituci θ = {x/t, y/f (z)} z obou liter´alu vznikne liter´al P (t, f (z)). b) Po substituci θ = {z/a, y/a, u/f (a)} z obou liter´alu vznikne liter´al Q(a, a, f (a)). c) Takov´ a substituce neexistuje. d) Po substituci θ = {y/a, x/b} z obou liter´alu vznikne liter´al F (a, b). e) Po substituci θ = {x/g(w), u/f (y), z/g(w)} z obou liter´alu vznikne liter´al Q(g(w), f (y), g(w)). f) Po substituci θ = {u/g(x), y/f (w)} z obou liter´alu vznikne liter´al P (g(x), f (w)). 2.3.2
Pˇ r´ıklad. Najdˇete vˇsechny rezolventy n´asleduj´ıc´ıch klausul´ı.
a) ∀x ∀y ∀z (P (x, y) ∨ Q(y, z)), ∀u ¬P (u, f (u)); b) ∀x (P (x, x) ∨ ¬Q(x, f (x))), ∀x ∀y ∀z (Q(x, y) ∨ R(y, z)); Marie Demlov´ a: Pˇr´ıklady k pˇredmˇetu Logika a grafy
6. dubna 2014, 21:52
2.3. Rezoluˇcn´ı metoda v predik´ atov´e logice
[140406-2152 ]
11
c) ∀x ∀y (P (x, y) ∨ ¬Q(y, x)), ∀x ∀y (Q(x, x) ∨ P (y, f (x))); d) ∀x ∀y ∀y(P (x, y)∨¬S(x, x)∨T (x, f (x), z)), ∀x ∀z (¬T (f (x), x, z)∨S(x, z)); e) ∀x ∀y ∀z (¬Q(x, y, z) ∨ ¬Q(y, y, y)), ∀x ∀z ∀t (Q(x, f (x), z) ∨ Q(z, t, t)). V´ ysledek: a) ∀z ∀u Q(f (u), z); b) ∀x ∀z (P (x, x) ∨ R(f (x), z)); c) ∀x ∀z (P (x, x) ∨ P (z, f (x))), uvˇedomte si, ˇze jsme nejprve pˇrejmenovali promˇenn´e tak, ˇze naˇse klauzule jsou ∀x ∀y (P (x, y) ∨ ¬Q(y, x)) a ∀z ∀t (Q(t, t) ∨ P (z, f (t))), pak hledan´ a substituce je θ = {y/x, t/x} ; d) ∀x ∀y ∀z (P (x, y) ∨ T (x, f (x), z) ∨ ¬T (f (x), x, x)) (z liter´alu T (x, f (x), z) a ¬T (f (x), x, z) ˇz´ adnou substituc´ı nevzniknou komplement´arn´ı liter´aly). Zase si je dobr´e uvˇedomit, ˇze nejprve mus´ıme pˇrejmenovat promˇenn´e tak, abychom v obou klauzul´ıch mˇeli ruzn´ a jm´ena promˇenn´ ych; e) ∀x ∀z ∀t (¬Q(f (x), f (x), f (x))∨Q(z, t, t)), ∀y ∀t ∀v (¬Q(y, y, y)∨Q(t, f (t), v)), ∀x ∀y ∀z ∀t (¬Q(x, y, z)∨ Q(t, f (t), y)). 2.3.3
Pˇ r´ıklad. N´ asleduj´ıc´ı formule pˇreved’te na klaus´aln´ı tvar.
a) ∀x [∃y (Q(x, y) ∨ ¬P (x, y)) ∧ ∃y (¬Q(y, x) ∨ P (y, x))]; b) ∀x [(∃y (P (x, y) ∧ ¬Q(y, x))) ∨ ∀y ∃z R(x, y, z)]; c) ¬∀x [∃y Q(x, y) ⇒ ∀y ∃z ¬P (x, y, z)]; d) ∃x S(x) ⇒ [∀x (P (x) ∨ Q(x)) ⇒ ∀x ∃y T (x, y)]. V´ ysledek: a) Formule je splniteln´a pr´avˇe tehdy, kdyˇz je splniteln´a formule: [∀x (Q(x, f (x)) ∨ ¬P (x, f (x)))] ∧ [∀x (¬Q(g(x), x) ∨ P (g(x), x))] a to je pr´avˇe tehdy, kdyˇz je splniteln´ a tato mnoˇzina klausul´ı: {∀x (Q(x, f (x)) ∨ ¬P (x, f (x))), ∀x (¬Q(g(x), x) ∨ P (g(x), x))}. Zde f a g jsou un´ arn´ı skolemizaˇcn´ı funkˇcn´ı symboly. b) Formule je splniteln´ a pr´ avˇe tehdy, kdyˇz je splniteln´a formule: ∀x ∀t [(P (x, f (x)) ∨ R(x, t, g(x, t))) ∧ (¬Q(f (x), x) ∨ R(x, t, g(x, t)))] a to je pr´ avˇe tehdy, kdyˇz je splniteln´a tato mnoˇzina klausul´ı: {∀x ∀t (P (x, f (x)) ∨ R(x, t, g(x, t))), ∀x ∀t (¬Q(f (x), x) ∨ R(x, t, g(x, t)))}. Zde f je un´ arn´ı a g je bin´ arn´ı skolemizaˇcn´ı funkˇcn´ı symbol. Tento v´ ysledek odpov´ıd´ a pˇreveden´ı na formuli: ∀x ∃y ∀t ∃z [(P (x, y) ∨ R(x, t, z)) ∧ (¬Q(y, x) ∨ R(x, t, z))]. c) Formule je splniteln´ a pr´ avˇe tehdy, kdyˇz je splniteln´a formule: Q(a, b) ∧ ∀z P (a, c, z) a to je pr´ avˇe tehdy, kdyˇz je splniteln´a tato mnoˇzina klausul´ı: {Q(a, b), ∀z P (a, c, z)}. Zde a, b a c jsou skolemizaˇcn´ı konstantn´ı symboly. d) Formule je splniteln´ a pr´ avˇe tehdy, kdyˇz je splniteln´a formule: ∃y ∀z ∃t ∀x [(¬S(x)∨T (z, t)∨¬P (y))∧(¬S(x)∨T (z, t)∨¬Q(y))] a tak´e formule: ∀z ∀x [(¬S(x) ∨ T (z, f (z)) ∨ ¬P (a)) ∧ (¬S(x) ∨ T (z, f (z)) ∨ ¬Q(a))] a to je pr´ avˇe tehdy, kdyˇz je splniteln´a tato mnoˇzina klausul´ı: {∀x ∀z (¬S(x) ∨ T (z, f (z)) ∨ ¬P (a)), ∀x ∀z (¬S(x) ∨ T (z, f (z)) ∨ ¬Q(a))}. Zde f je un´ arn´ı skolemizaˇcn´ı funkˇcn´ı symbol a a je skolemizaˇcn´ı konstanta. Marie Demlov´ a: Pˇr´ıklady k pˇredmˇetu Logika a grafy
6. dubna 2014, 21:52
ˇ ´IKLADY Z PREDIKATOV ´ ´ LOGIKY [140406-2152 ]KAPITOLA 2. PR E
12 2.3.4
Pˇ r´ıklad. Rezoluˇcn´ı metodou rozhodnˇete, zda plat´ı:
a)
∀x (P (x) ∨ Q(x)) ∃x ¬P (x) ∃x Q(x)
b)
∃x ∀y P (x, y) ∀x ∀y (¬P (x, y) ∨ Q(x, y)) ∃x ∀y Q(x, y)
c)
(∃x P (x)) ⇒ Q(a) ∀x (P (x) ⇒ Q(a))
´ V´ ysledek: a) Usudek je spr´avn´ y: Mnoˇzina klausul´ı S = {∀x (P (x) ∨ Q(x)), ¬P (a), ∀y ¬Q(y)} je nesplniteln´a, nebot’ F ∈ R2 (S). ´ b) Usudek je spr´ avn´ y: Mnoˇzina klausul´ı S = {∀y P (a, y), ∀x ∀z (¬P (x, z) ∨ Q(x, z)), ∀t ¬Q(t, f (t))} je nesplniteln´a, nebot’ F ∈ R2 (S). ´ c) Usudek je spr´ avn´ y: Mnoˇzina klausul´ı S = {∀x (¬P (x)∨Q(a)), P (b), ¬Q(a)} je nesplniteln´ a, nebot’ F ∈ R2 (S). 2.3.5 Pˇ r´ıklad. Rezoluˇcn´ı metodou ovˇeˇrte spr´avnost u ´sudku: P (b) ⇒ V (a) (∀x V (x)) ∨ (∀x ¬V (x)) P (b) ∀x V (x) kde P je un´ arn´ı predik´atov´ y symbol, V je un´arn´ı predik´atov´ y symbol a a, b jsou konstantn´ı symboly. ´ V´ ysledek: a) Usudek je spr´avn´ y: Mnoˇzina klausul´ı S = {¬P (b)∨V (a), ∀x ∀y (V (x)∨ ¬V (y)), P (b), ¬V (b)} je nesplniteln´a, nebot’ F ∈ R3 (S). 2.3.6 Pˇ r´ıklad. N´ asleduj´ıc´ı u ´sudek zformalizujte a rezoluˇcn´ı metodou rozhodnˇete, zda je spr´ avn´ y. a)
ˇ adn´ Z´ y ˇz´ ak t´eto tˇr´ıdy nen´ı hudebn´ık. Vˇsichni hudebn´ıci jsou umˇelci. ˇ adn´ Z´ y ˇz´ ak t´eto tˇr´ıdy nen´ı umˇelec.
b)
ˇ adn´ Z´ y atlet nem´ a ˇspatnou fyzickou kondici. Nˇekteˇr´ı pˇr´ıtomn´ı jsou atleti. Nˇekteˇr´ı pˇr´ıtomn´ı nemaj´ı ˇspatnou fyzickou kondici.
c)
ˇ adn´ Z´ y atlet nem´ a ˇspatnou fyzickou kondici. Nˇekteˇr´ı pˇr´ıtomn´ı nejsou atleti. Nˇekteˇr´ı pˇr´ıtomn´ı maj´ı ˇspatnou fyzickou kondici.
d)
Vˇsechny kopce jsou zdolateln´e. Nˇekter´e hory nejsou zdolateln´e. Nˇekter´e hory nejsou kopce.
Marie Demlov´ a: Pˇr´ıklady k pˇredmˇetu Logika a grafy
6. dubna 2014, 21:52
2.3. Rezoluˇcn´ı metoda v predik´ atov´e logice e)
[140406-2152 ]
13
Vˇsichni ˇsimpanzi mohou vyˇreˇsit kaˇzd´ y probl´em. Existuje aspoˇ n jeden probl´em. Vyˇreˇs´ı-li ˇsimpanz probl´em, dostane ban´an. Alex je ˇsimpanz. Alex dostane ban´ an.
V´ ysledek: a) Znaˇc´ı-li Z(x) . . . x je ˇz´ak t´eto tˇr´ıdy, H(x) . . . x je hudebn´ık, U (x) . . . x je umˇelec, u ´sudek odpov´ıd´a: ∀x (Z(x) ⇒ ¬H(x)) ∀x (H(x) ⇒ U (x)) ∀x (Z(x) ⇒ ¬U (x)) ´ Usudek nen´ı spr´ avn´ y: Mnoˇzina klausul´ı S = {∀x (¬Z(x)∨¬H(x)), ∀y (¬H(y)∨ U (y)), Z(a), U (a)} je splniteln´ a. (Plat´ı R? (S) = S ∪ {¬H(a)}.) b) Znaˇc´ı-li A(x) . . . x je atlet, K(x) . . . x nem´a ˇspatnou fyzickou kondici, P (x) . . . x je pˇr´ıtomen, u ´sudek odpov´ıd´a: ∀x (A(x) ⇒ K(x)) ∃x (P (x) ∧ A(x)) ∃x (P (x) ∧ K(x)) ´ Usudek je spr´ avn´ y, protoˇze mnoˇzina klausul´ı S = {∀x (¬A(x)∨K(x)), P (a), A(a), ∀y (¬P (y)∨ ¬K(y))} je nesplniteln´ a. (Plat´ı F ∈ R2 (S).) c) Pˇri stejn´em znaˇcen´ı jako v minul´em pˇr´ıkladˇe, u ´sudek odpov´ıd´a: ∀x (A(x) ⇒ K(x)) ∃x (P (x) ∧ ¬A(x)) ∃x (P (x) ∧ ¬K(x)) ´ Usudek nen´ı spr´ avn´ y: Mnoˇzina klausul´ı S = {∀x (¬A(x)∨K(x)), P (a), ¬A(a), ∀y (¬P (y)∨ K(y))} je splniteln´ a. (Plat´ı R? (S) = S ∪ {¬K(a), ∀x (¬A(x) ∨ ¬P (x))}.) d) Znaˇc´ı-li K(x) . . . x je kopec, Z(x) . . . x je zdolateln´ y, H(x) . . . x je hora, u ´sudek odpov´ıd´ a: ∀x (K(x) ⇒ Z(x)) ∃x (H(x) ∧ ¬Z(x)) ∃x (H(x) ∧ ¬K(x)) ´ Usudek je spr´ avn´ y, protoˇze mnoˇzina klausul´ı S = {∀x (¬K(x)∨Z(x)), H(a), ¬Z(a), ∀y (¬H(y)∨ K(y))} je nesplniteln´ a. (Plat´ı F ∈ R2 (S).) e) Oznaˇcme a konstantn´ı symbol s v´ yznamem . . . Alex, a vlastnosti: M (x) . . . x je ˇsimpanz, P (x) . . . x je probl´em, B(x) . . . x dostane ban´an a V (x, y) ´ . . . ˇsimpanz x vyˇreˇs´ı probl´em y. Usudek m´a tvar: ∀x (M (x) ⇒ ∀y (P (y) ⇒ V (x, y)) ∃x P (x) ∀x ∀y ((M (x) ∧ P (y) ∧ V (x, y)) ⇒ B(x)) M (a) B(a) ´ Usudek je spr´ avn´ y, protoˇze mnoˇzina klausul´ı S = {∀x ∀y (¬M (x)∨¬P (y)∨V (x, y)), P (b), ∀z ∀t (¬M (z)∨¬P (t)∨¬V (z, t)∨B(z)), M (a), ¬B(a)} je nesplniteln´ a. (Plat´ı F ∈ R4 (S).)
Marie Demlov´ a: Pˇr´ıklady k pˇredmˇetu Logika a grafy
6. dubna 2014, 21:52
