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.