IBOOO Úvod do informatiky -- příklady na procvičení
Sada 8 -- Zadání
Téma
Vhodně definované vlastnosti relací, uzávěry relací. Výroky. Výroková logika, valuace,
normální tvar výrokových formulí, negace výrokových formulí, pravdivost a splnitelnost
výrokových formulí. Predikátová logika, negace formulí predikátové logiky.
Příklad 1.
a) Určete reflexivní uzávěr relace {(x,y) \ xy = 0} C No x Nob)
Určete symetrický uzávěr relace {(x,y) \ xy = 0} C No x Noc)
Určete tranzitivní uzávěr relace {(x,y) \ xy = 0} C No x Nod)
Určete reflexivní, symetrický a tranzitivní uzávěr relace {(x,y) \ xy = 0} C No x Noe)
Určete reflexivní uzávěr relace {(2i + 1, li + 3) | i E No}.
f) Určete symetrický uzávěr relace {(2i + 1, li + 3) | i E No}.
g) Určete tranzitivní uzávěr relace {(2i + 1, li + 3) | i E No}.
h) Určete reflexivní, symetrický a tranzitivní uzávěr relace {(2i + 1, 2i + 3) | i E No}.
i) Nechť R = {(x, y) \ x < 2y A y < 2x} C M x R , kde ÍR značí množinu všech reálných
čísel. Určete R o R.
Příklad 2.
Nechť A, B, C, D jsou atomické propozice. Nechť v je valuace, která splňuje v(Ä) =
= ľ{B) = true a v(C) = v(D) = false. Podle definice Sv určete Sv(<p), je-li
a) <p = (C V D) => -.(> A (A => S))
b) (p = (-.A => (S A -.B)) => -.-.A
c) (p = (-.C => - ( - A ^ ^ -iß)) A ((Ľ => B) V (-.B => C))
Příklad 3.
Nechť A, B, C, D jsou atomické propozice. Znegujte následující formule. (Protože znegováním
se myslí i převedení do normálního tvaru, máte za úkol pro formuli <p vypočítat
J7
(-up) pomocí příslušných funkcí T a Q definovaných na přednášce.)
a) (p = (C V D) => ->(> A (A => S))
b) ^ = (-.C => - ( - A ^ ^ -iß)) A ((Ľ => S) V (-.B => C))
c) Vx G No- x > 0 =/- 3y, z E No- y | x A z | x =>- 3u> G No- W > X A Z | W A J / | W J
Příklad 4.
Formalizujte (tj. zapište jako formule výrokové, resp. predikátové logiky) a negujte následující
tvrzení. Pokud se tvrzení týká čísel, vyjádřete vlastnosti pomocí aritmetických
operací. Formule zapisujte v normálním tvaru.
a) Když budu hodný, Ježíšek mi nadělí hezké dárky.
b) Ne každý čaj mi chutná.
c) Rostlina, která u mne přežije rok, je plevel.
d) Když je přes den zataženo a v noci jasno, bude ráno mrznout nebo přijde obleva.
e) Nechť n je sudé přirozené číslo. Potom pro každé přirozené číslo m platí, že když
m je sudé, potom m + n je sudé, a když m je liché, potom m + n je liché.
f) Přirozené číslo p je prvočíslo, jestliže není dělitelné jiným přirozeným číslem kromě
čísla 1 a sebe samého.
g) Když je přirozené číslo a větší než 8, nebo když je dělitelné přirozeným číslem b,
potom a je větší než b a a ˇ b je větší než b.
Příklad 5.
V následujících příkladech máte za úkol znegovat definiční podmínky různých pojmů.
Definice pojmů zapište jako formule výrokové, resp. predikátové logiky a znegujte je.
a) Nechť n je přirozené číslo. Co znamená, že n není liché?
b) Nechť R je relace. Co znamená, že R není antisymetrická?
c) Nechť / C A x B je parciální funkce. Co znamená, že / není minimální prvek
uspořádané množiny {T, C), kde T je množina všech parciálních funkcí z A do B?
d) Nechť / C A x B je parciální funkce. Co znamená, že / není nejmenší prvek uspořádané
množiny {T, C), kde T je množina všech parciálních funkcí z A do B?
e) Řekneme, že přirozené číslo m je šťastné a veselé, jestliže pro žádné přirozené číslo n
větší než m neplatí, že m dělí n a m + n je liché. Co znamená, že číslo m není šťastné a
veselé?
f) Řekneme, že přirozené číslo k je odvážné, jestliže existují přirozená čísla a, b taková,
že a i b je různé od čísla 1 a zároveň k2
= o?b2
. Co znamená, že číslo k není odvážné?
g) Nechť i ž C M x M j e binární relace na množině M. Řekneme, že relace R je přitažlivá,
jestliže pro každé x,y E M platí: pokud (x,y) E R, potom existuje z E M takové, že
(x, z) E R a (y, z) E R. Co znamená, že relace R C M x M není přitažlivá?
h) Nechť / : M --ˇ M je funkce. Řekneme, že / má trojúhelník, jestliže pro každé x E
E M platí f (x) 7^ x a existují navzájem různá xi,X2,xs E M taková, že f(x\) = X2,
f(x
2) = ^ a 7(^3) = x\. Co znamená, že funkce / : M --ˇ M nemá trojúhelník?
Příklad 6.
Mějme výrokovou formuli <p = (A =^> B) =^> (B =^> A).
a) Najděte všechny valuace v, pro něž Sv{^) = true. Kolik jich je?
b) Najděte všechny valuace v, pro něž SU(LP) = false. Kolik jich je?
Příklad 7.
Rozhodněte, zda následující formule výrokové logiky jsou splnitelné. Pokud ano, nalezněte
valuaci, která to dosvědčuje.
a) (((A => B) A (B => C)) AÄ)A^C
b) (D ^ ^ (-. V D)) A -.((> A ^ ^ A )
c) ( ^ S A i ) ^ ((-.A => B) A (-.B => A))
Příklad 8.
Označme V množinu všech valuaci. Uvažujme uspořádanou množinu (U, C), kde W =
= {/ C At x {true, false} | / je parciální funkce} (jedná se opět o množinu parciálních
funkcí uspořádaných množinovou inkluzí).
a) Dokažte, že platí V C W .
b) Charakterizujte valuace v pojmech uspořádané množiny (U, C) a dokažte, že je podaná
charakterizace správná.
c) V uspořádané množině (U, C) určete všechny maximální dolní závory množiny {v G
G V | ^ ( . B A (C =>- A)) = true}. Jsou to valuace?
d) Co musí splňovat výroková formule tp, aby v uspořádané množině (U, C) měla množina
{/ G U | 3Í/ G V./ C z/ A Sv(r
tp) = true} infimum? Bude infimum valuace?
Příklad 9.
Nechť pro i G N je Ai G ^4í atomická propozice. Pro všechna n G No definujme formule
ipn takto:
* ipo = true
* fn+l =fn A 4
(Tedy například ^3 = ((true A Ai) A A2) A A3, přičemž na uzávorkování zřejmě nezáleží.)
a) Pro každé n G N nalezněte valuaci vn takovou, že
Q / \ _ f true pro i < n
^ n W ; - \ faige jinak
b) Nalezněte valuaci ß takovou, aby pro všechna n G No platilo S^{ipn) = false.
c) Nalezněte valuace rj takovou, aby pro všechna n e N o platilo Sv(<^n) = true.