3   Třetí cvičení
3.1 Normální fořmy
Q Příklad 3.1 Necht' y, V a £ jsou formule výrokové logiky. Dokažte, že platí:
a) (y — V) « (—y V V)
b) — (y A V) « (—y V —V)
c) —(y V V) ~ (—y A —V)
d) (y A (V V £)) « ((y A V) V (y A £))
e) (y V (V A £)) « ((y V V) A (y V £))
£i0       Příklad 3.2 Mejme formule £ a £' takove, že £ « £'. Dokažte, že pro libovolnou formuli y a pro formuli V, kterou žískame nahražením vsech výskytů £ ža £' ve formuli y, platí y « V.
$ Příklad 3.3 Preveďte formuli (A — B) A ((C — E) — — (C A —D)) do DNF.
$ Příklad 3.4 Preveďte formuli (A — B) V ((C — E) — —(C A —D)) do CNF.
3.2 Logické systémy
$0       Příklad 3.5 Pro formuli y « A — (B — (C — (D — E))) naležnete ekvivalentní formuli v logickem systemu       kde | je Shefferuv operátor, tedy y | V ~ —(y A V).
£1$       Příklad 3.6 Rožhodnete a dokažte, žda jsou nýsledující logicke systemy plnohodnotne.
a) L(—)
b) L(A, V)
c) L(—, —)
3.3 Dokazatelnost
Mejme logicky system L(—, —) a Lukasiewicžuv odvožovací system:
• A1: y — (V — y)
• A2: (y — (V — £)) — ((y — V) — (y — £))
• A3: (—y — —V) — (V — y)
• MP: ž y a y — V odvod' V
Příklad 3.7 Necht' P a Q jsou vyrokove promenne. Rožhodnete a dokažte, žda jsou ^sledující formule dokažatelníe.
a) P — (Q — P)
b) P — P
c) P — Q
1