2   Druhé cvičení
2.1 Syntax
Definice 2.1 Abecedu výrokové logiky tvoří následující symboly:
• znaky pro výrokové proměnné A, B, C,..., kterách je spoCetne mnoho;
• logické spojky A, V, —, — a
• závorky ( a ).
Formule výrokové logiky je slovo y nad abecedou vyrokove logiky, pro ktere existuje vytvoěujécé posloupnost, tj. koneCná posloupnost slov //i,..., , kde k > 1, = y a pro kazde 1 < i < k ma slovo /j jeden z následujících tvaru:
• vyroková promenná
• —//j pro nejake 1 < j < i,
• (/j o     ) pro nejaká 1 < j, j' < i, kde o je jeden ze symbolu A, V, —.
d) (Ai AVA2) 2.2 Sémantika
Definice 2.3 Pravdivostní ohodnocení (valuace) je zobrazení v, ktere kazde várokove premenne priradí hodnotu 0 nebo 1. Metamatematickou indukcí k delce vytvorující posloupnosti jed-noznacne rozsnáme v na vsechny vyrokove formule:
• v(A) jiz definovano;
• v(—///) definujeme jako 0, pokud v(//) = 1, jako 1 jinak;
• v(//i A ///2) definujeme jako 1, pokud v(//i) = 1 a v(///2) = 1, jako 0 jinak;
• v(///i V ///2) definujeme jako 1, pokud v(/i) = 1 nebo v(///2) = 1, jako 0 jinak;
• v(//i — ///2) definujeme jako 1, pokud v(//i) = 0 nebo v(///2) = 1, jako 0 jinak.
Dále rekneme, ze vyrokova formule y je
• pravdivá (resp. nepravdivé) pri valuaci v, pokud v(y) = 1 (resp. 0);
• je splnitelné, pokud existuje valuace v takova, ze v(y) = 1;
• tautologie, jestlize v(y) = 1 pro kazdou valuaci v.
Soubor T výrokových formulí je splnitelné, jestlize ex. v takova, ze v (y) = 1 pro kazde y z T. Formule y a /// jsou ekvivalentné (y k ///), práve kdyz pro kazdou valuaci v platí, ze v(y) = v(//).
00
Příklad 2.2 Jsou nasledující slova formulemi vyrokove logiky? Rozhodnete a dokazte.
a)
b)
O
o
Příklad 2.5 Dejte príklad formulí y a /// takovych, ze
• y — /// je tautologie a zároven
• /// — y je kontradikce.
00
Příklad 2.6 Necht' A je vyrokova promenna. Rozhodnete a dokazte, zda existuje formule y takováa, ze
a) y — (y — A) k A
b) y — (y — A) k —A
1
c) 92 — (A — y) K, A
d) (y — A) — y k -A
0 Příklad 2.7 (SAT solver) Najdete co nejrychleji splňující valuaci.
(A V B V -D) A (-B V C V -D) A (D V -A V -B) A (-A V B V C)A (-A V -B V -C) A (-A V -C V D) A (B V A V C) A (-D V -B V -C)A (B V -B V -C) A (-A V B V A) A (C V -B V D) A (A V -B V C)
00 Příklad 2.8 Mejme tri domorodce, Argh, Bhee a Cshou, z Ostrova poctivců a padouchu.1 Každý obyvatel tohoto ostrova je bud' poctivec nebo padouch, poctivci mluví vždy pravdu, padousi vždy lžou. Domorodci Argh a Bhee pronesou nasledující tvrzení:
a) Argh: "Bhee a Cshou jsou oba poctivci" Bhee: "Argh je padouch a Cshou je poctivec"
b) Argh: "Bhee je padouch"
Bhee: "Argh a Cshou mají ruznou povahu"
Kterí domorodci jsou poctivci a kterí padousi?
2.3 Aplikace
Definice 2.9 Orientovaný graf je dvojice G = (V, E), kde V je množina vrcholu a E C V2 je množina orientovaných hran meži vrcholy.
Neorientovaný graf je dvojice G = (V, E), kde V je množina vrcholu a E C {{u, v} | u, v G V} je množina hran meži vrcholy (tedy množina neusporýdaných dvojic).
Graf je souvisly, pokud pro každe dva vrcholy u, v existuje alespoň jedna cesta ž u do v. Neorientovaný graf je strom, pokud je souvisly a po odebrýní libovolne hrany se stane nesouvislým.
00       Příklad 2.10 Necht' G je neorientovany souvislý graf. Naležnete system formulí T takovy, že
T je splnitelný G je souvislý, ale není strom
00 Příklad 2.11 Necht' A, B jsou spocetne množiny a R C A x B je relace takový, že pro každe a G A je Ba = {b | (a, b) G R} konecný nepraždný soubor. Naležnete system formulí T takovy, ňže
T je splnitelny existuje injektivní funkce f : A — B takový, že f C R
(Take žadýní mužete clmpat jako bipartitní graf žadany pomocí (A, B, R) s parovýním f.)
Definice 2.12 Necht' G = (V, E) je orientovany graf a | V| = n. Hamiltonovská kružnice (HK) v orientovanem grafu G je posloupnost vrcholu v0, v1,..., vn, tak že v0 = vn, pro vsechna 0 < i < n platí (vj, vi+1) G E a pro vsechna 0 < i < j < n platí vj = v j.
000    Příklad 2.13 Necht' G je orientovany graf. Zadejte formuli y takovou, že platí
y je splnitelný       G obsahuje Hamiltonovskou kružnici (1)
a y lže sestrojit v polynomialním case.
(Ukolem je tedy v polynomialným case redukovat problem Hamiltonovske kružnice na NP-ýplný problem splnitelnosti vyrokovych formulí (SAT).)
1 Tento příklad pochází z knihy Navěky nerozhodnuto od Raymonda Smullyana
2