Postacie normalne

Definicja 6.1

Literałem nazywamy formułę, która jest zmienną zdaniową lub negacją zmiennej zdaniowej.

Zauważmy, że formuła konstruowana w dowodzie twierdzenia 5.2 jest w pewnej standartowej postaci - formuła jest alternatywą formuł, które są koniunkcjami literałów. Przypomnijmy, że dla $p \Rightarrow q$ zbudujemy formułę

$(p \wedge q) \vee (\neg p \wedge q) \vee (\neg p \wedge \neg q).$

Definicja 6.2

Formuła jest w dyzjunktywnej postaci normalnej (DNF), jeśli jest alternatywą formuł które są koniunkcjami literałów. Czyli wtedy, gdy jest postaci

$\phi_1\vee \dots \vee \phi_n$

oraz każda z formuł $\phi_i$ jest koniunkcją literałów, czyli jest postaci

$l_l^i \wedge \dots \wedge l_k^i$

dla pewnych literałów $l_l^i, \dots,l_k^i$

Twierdzenie 6.3

Dla każdej formuły istnieje równoważna formuła w DNF.

Dowód

Wynika bezpośrednio z konstrukcji w dowodzie twierdzenia 5.2.

Definicja 6.4

Formuła jest w koniunktywnej postaci normalnej (CNF), jeśli jest koniunkcją formuł które są alternatywami literałów.

Twierdzenie 6.5

Dla każdej formuły istnieje równoważna formuła w CNF.

Dowód

Niech $\displaystyle \Phi$ będzie dowolną formułą. Z twierdzenia twierdzenia 6.3 wynika, że dla formuły $\displaystyle \neg \Phi$ istnieje dyzjunktywna postać normalna. Niech $\displaystyle \Psi$ będzie taką formułą. Wtedy mamy

$\displaystyle \Phi \equiv \neg \Psi.$

Stosując wielokrotnie prawa de'Morgana dla formuły $\displaystyle \neg \Psi$ otrzymamy formułę w koniunktywnej postaci normalnej. Indukcyjny dowód tego faktu pomijamy.

Ćwiczenie 6.1

Jak sprawdzić, czy formuła w CNF jest tautologią?

Rozwiązanie

Niech rozważaną formułą będzie

$\phi_1\wedge \dots \wedge \phi_n$

Aby była tautologią konieczne jest, aby każda z formuł

$\phi_i$ była tautologią. Ponieważ każda z formuł

$\phi_i$ jest alternatywą literałów to jest tautologią jedynie wtedy, gdy istnieje taki literał który występuje w

$\phi_i$ zarówno pozytywnie (czyli jako zmienna) jak i negatywnie (czyli jako zanegowana zmienna).

Ćwiczenie 6.2

Dla poniższych formuł wypisz ich najkrótsze równoważne formuły w CNF

$p \Leftrightarrow q$ ,
$p \Rightarrow (q \Rightarrow p)$ ,
$(p \Rightarrow q) \Rightarrow p$ ,
$(p \vee a \vee b) \wedge (\neg q \vee \neg a) \wedge(r \vee \neg b \vee \neg c) \wedge(c \vee p))$ ,
$(p \wedge q) \vee (r \wedge s)$ .

Rozwiązanie

$\displaystyle \neg p \vee q$
$\displaystyle \neg a \vee a$
$\displaystyle p$
$\displaystyle (p\vee r) \wedge (p\vee s)\wedge (q \vee r) \wedge (q \vee s)$

Spełnialność

Spośród wszystkich formuł wyróżnimy też zbiór formuł spełnialnych.

Definicja 6.6

Formuła jest spełnialna, jeśli istenieje takie wartościowanie, które wartościuje tą formułę na 1.

Formuły spełnialne są w ścisłym związku z tautologiami.

Twierdzenie 6.7

Formuła ${\phi}$ jest tautologią wtedy i tylko wtedy, kiedy formuła $\neg \phi$ nie jest spełnialna.

Dowód

Przypuśćmy, że formuła ${\phi}$ jest tautologią. Wtedy dla każdego wartościowania $\mathrm{v}$ mamy $v(\phi)=1$ . Stąd otrzymujemy, że dla każdego wartościowania $\mathrm{v}$ mamy $v(\neg \phi)=0$ , a więc nie istnieje wartościwanie, które spełnia $\neg \phi$ , czyli formuła ta nie jest spełnialna.

Przypuśćmy, że formuła $\neg \phi$ nie jest spełnialna, czyli nie istnieje wartościowanie $\mathrm{v}$ takie, że $v(\neg \phi)=0$ . Wynika stąd, że dla każdego wartościowania mamy $v(\phi)=1$ , a więc ${\phi}$ jest tautologią.

Ćwiczenie 6.3

Sprawdź spełnialność następujących formuł

$(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee \neg p)$
$(\neg p \vee q) \wedge (\neg q \vee \neg r) \wedge (\neg q \vee p)$

Rozwiązanie

Łatwo sprawdzić, że wartościowanie $\displaystyle v$ takie, że $\displaystyle v(p)=0, v(q)=1, v(r)=1$ spełnia pierwszą z formuł.
Po zastąpieniu alternatyw implikacjami otrzymujemy

$\displaystyle (\neg q \Rightarrow \neg p) \wedge (q \Rightarrow \neg r) \wedge (\neg p \Rightarrow q) \wedge (\neg r \Rightarrow \neg q).$

Przypuśćmy teraz, że formuła ta jest spełnialna. Niech

$\displaystyle v$ będzie wartościowaniem spełniającym. Przypuśćmy, że

$\displaystyle v(q)=0$ wtedy ponieważ

$\displaystyle v(\neg q \Rightarrow \neg p)=1$ to konieczne jest aby

$\displaystyle v(p)=0$ . Jednak wtedy ponieważ mamy

$\displaystyle v(\neg p \Rightarrow q)=1$ , to

$\displaystyle v(q)=1$ , a więc otrzymujemy sprzeczność. Przypuśćmy zatem, że

$\displaystyle v(q)=1$ wtedy ponieważ

$\displaystyle v(q \Rightarrow \neg r)=1$ , to

$\displaystyle v(r)=0$ . W takim przypadku jednak ponieważ

$\displaystyle v(\neg r \Rightarrow \neg q)=0$ otrzymujemy, że

$\displaystyle v(q)=0$ , a więc znowu sprzeczność. Wynika stąd, że nie istnieje wartościowanie spełniające dla tej formuły.

Formuły z powyższego zadania, poza tym że są w koniunktywnej postaci normalnej, to jeszcze występujące w nich klauzule mają dokładnie dwa literały. Problem spełnialności takich formuł jest nazywany w literaturze problemem 2SAT. Dla takich formuł istnieją szybkie algorytmy pozwalające ocenić ich spełnialność. Dopuszczanie klauzul o długości 3, bardzo komplikuje problem. Do dziś nie wiadomo czy dla takich formuł istnieją szybkie algorytmy oceniające spełnialność. Więcej na ten temat można się dowiedzieć z wykładu Teoria złożoności.