{{NAIL021 Skripta}}

V této kapitole nadefinujeme literály, logické operátory, Boolovské formule
a funkce. Popíšeme normální tvary formulí (DNF, CNF) a jejich vlastnosti. Dále

zavedem implikanty, konsekventy, rezoluci (konsensus). V závěru popíšeme
konsenzuální metodu a dokážeme její úplnost.

## Boolovské funkce ##

* $x, y, z$ jsou boolovské funkce
* $v(x) $ je ohodnocení  proměnných
* $\neg{x}, \overline{x}$ je \negace *x*
* proměnné a negované proměnné jsou *literály*
* $\lor, \land, \implies, \iff$ jsou logické operátory (spojky)

### Boolovská formule ###

Boolovskou formuli definujme rekurzivně:

* každý literál je Boolovská formule (dále jen formule)
* pokud jsou A, B formule, pak $\neg{A}, \neg{B}, A \lor B, A \land B, A \implies B, A \iff B$ jsou také formule

### Normální formy ###

Disjunkci literálů nazýváme *klauzule*, konjunkci literálů nazýváme
*term*. Formule je v *konjunktivní normální formě* (CNF), pokud je

konjunkcí klauzulí. Formule je v *disjunktivní normální formě* (DNF), pokud je disjunkcí termů.

### Ekvivalentní formule ###

Následující pravidla definují ekvivalentní formule, lze je využít k úpravě formulí:

* $\neg{(A \lor B)} \equiv \neg{A} \land \neg{B}$ (de Morganovo pravidlo)
* $\neg{(A \land B)} \equiv \neg{A} \lor \neg{B}$ (de Morganovo pravidlo)
* $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$ (distributivita $\lor$)
* $A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$ (distributivita $\land$)

Boolovská funkce je funkce $f: \{0, 1\}^n \rightarrow \{0, 1\}$. Lze ji reprezentovat např. formulí nebo tabulkou.

||
|----|
| $x_1$ | $x_2$ | $x_3$| $f(x_1, x_2, x_3)$|
|0 |0 |1 |0 |
|0 |1 |0 |1 |
|0 |1 |1 |0 |
|1 |0 |0 |1 |
|1 |0 |1 |1 |
|1 |1 |0 |0 |
|1 |1 |1|1 |
||

Vektory, pro které $f = 1$, nazýváme *true-pointy*, ostatní, pro které $f=0$ označujeme jako *false-pointy*.

**Pozorování**: Ke každé formuli existuje logicky ekvivalentní formule v CNF i DNF.

**Důkaz** : Pokud funkce reprezentujeme tabulkou, pak můžeme sestavit normální formy:

* DNF: disjunkce termů odpovídajících true-pointům dané funkce 

$f(x_1, x_2, x_3) = (\neg x_1 \wedge x_2 \wedge \neg x_3)\vee(x_1 \wedge \neg x_2 \wedge \neg x_3)\vee(x_1 \wedge \neg x_2 \wedge x_3)\vee(x_1 \wedge x_2 \wedge x_3)
        $

* CNF: konjunkce klauzulí odpovídajících false-pointům dané funkce

$f(x_1, x_2, x_3) = (\neg x_1 \vee \neg x_2 \vee \neg x_3 )\wedge(\neg x_1 \vee \neg x_2 \vee x_3 )\wedge(\neg x_1 \vee x_2 \vee x_3 )\wedge(x_1 \vee x_2 \vee \neg x_3 )$

**Pozorování**: Počet boolovských funkcí na *n* proměnných je $2^{2^n}$ (tabulka má $2^n$ řádků, na každém může být hodnota *1* 1 nebo 0).

### Uspořádání boolovských funkcí ###

Definujme relaci $>$ takto: $f > g$ právě tehdy, když $\forall x: f(x)> g(x)$. Odbobně $\ge, \le, <$.

V následující části se zaměříme na DNF. Věci, které dokážeme, platí analogicky i pro CNF.

**Definice**: Term *T* je *implikantem* funkce *f*, pokud $T = 1 \implies f = 1$ (korektně $\forall x T(x) = 1 \implies f(x) = 1$). Term T je *primární implikant*, pokud po vypuštění libovolného literálu přestane být implikantem.

**Věta**: Pokud DNF F reprezentuje funkci *f* a *T* je implikant *f*, pak $F \lor T$ také reprezentuje *f*.

**Důkaz**:

* $F \le F \lor T$   triviálně 
* $F \ge F \lor T$   z definice implikantu

**Definice**: Pokud $T_1, T_2$ jsou termy a $T_1 \le T_2$ (tj. $T_2$ je "kratší"), říkáme, že $T_2$ *absorbuje* $T_1$.

**Pozorování**: Pokud $F \lor T_1 \lor T_2$ reprezentuje *f* a $T_1 \le T_2$, pak $F \lor T_2$ reprezentuje tutéž funkci.

**Definice**: Termy $T_1$ a $T_2$ mají *konflikt* v proměnné *x*, pokud $x \in T_1$

a $\neg{x} \in T_2$ (nebo $\neg{x} \in T_1$ a $x \in T_2$). Řekneme, že $T_1, T_2$ mají *konsenus*, pokud mají konflikt právě v jedné proměnné.
Označíme-li termy $T_1 = A \land x, T_2 = B \land \neg{x}$, pak $Cons(A,B) = A \land B$.

**Tvrzení**: Nechť $T_1, T_2$ jsou implikanty *f* mající konsenzus. Pak $T_3 = Cons>(T_1, T_2)$ je také implikantem *f*.

**Důkaz**:

* $T_1 \le f, T_2 \le f$
* $T_1 = A \land x$
* $T_2 = B \land \overline{x}$
* $T_3 = A \land B$

$T_3 = 1 \Rightarrow (A = 1) \land (B = 1) \Rightarrow (T_1 = 1) \lor (T_2 = 1) \Rightarrow f = 1$

**Definice**: Kanonická DNF funkce *f* je disjunkce všech primárních implikantů funkce *f*.

### Konsenzuální metoda ###

Vstup: DNF reprezentující *f*, výstup: kanonická DNF funkce *f*.

* Dokud se F může změnit: 
* * proveď všechny absorbce, které je možné provést
* * najdi dva termy $T_1, T_2$, že $Cons(T_1, T_2)$ není absorbován žádným termem v F a přidej $Cons(T_1, T_2)$ k F

**Důkaz konečnost**: Existuje konečně mnoho termů na *n* proměnných. Žádný term není přidán dvakrát (díky tranzitivitě absorbce).

**Důkaz správnosti**: nechť $F = R_1 \lor R_2 \lor \ldots \lor R_m$ je výstupem algoritmu a nechť $P$ je primární implikant *f*, který není obsažen v $\{R_1, \ldots, R_m\}$.

Označme ${\cal P} = \{X \vert X \leq P \& \forall i: X \nleq R_i\}$. Množina ${\cal P}$ je neprázdná, obsahuje alespoň samotné $P$. 

Nechť $Q$ je nejdelší (dle počtu literálů) term v ${\cal P}$.

1. $|Q| = n$ (obsahuje všechny proměnné), z definice Q není implikantem žádného $R_i$, pak musí mít konflikt s každým $R_i$. 
    1. $Q = 1 \implies \forall i: R_i = 0 \implies f = 0$
    1. $Q = 1 \implies P = 1 \implies f = 1$, což je spor, takové Q ani P nemůže existovat

1. $|Q| <n$, pak existuje proměnná *x* neobsažená v Q. Zkoumejme termy $Qx, Q\overline{x}$. Nejsou v ${\cal P}$ (Q je nejdelší), avšak jsou implikanty P (a celé *f*).  Pak existují $R_i, R_j$ takové, že $Qx \leq R_i, Q\overline{x} \leq R_j$ (Qx implikuje pravdivost formule, musí být splněn nějaký její term). $R_i$ obsahuje *x* (a nějaké proměnné z Q, jinak by $Q \leq R_i$), $R_j$ obsahuje $\overline{x}$. Pak $Q \leq Cons(R_i,R_j)$. Neexistuje $R_k, Cons(R_i,R_j) \leq R_k$ (jinak by $Q \leq R_k$). To je spor s fungováním algoritmu ($Cons(R_i,R_j)$ měl být přidán, ale nebyl).

### Složitost konsenzualní metody ###

Oba kroky měnící F v algoritmu konsenzualní metody lze provést v polynomiálním čase.

Cyklus ovšem může mít exponenciální počet iteraci. Ve speciálních případech (např. pokud je omezena délka klauzule, jako třeba pro 2-SAT) lze dosáhnout lepších výsledků.

* $F = x_1 x_2 \ldots x_n \vee \bar{x_1} y_1 \vee \bar{x_2} y_2 \vee \ldots \vee \bar{x_n} y_n $

Kanonická formule k $\F$ je exponenciálně dlouhá vzhledem k délce vstupní formule.
