{{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,zx, y, z jsou boolovské funkce

  • v(x)v(x) je ohodnocení proměnných

  • ¬x,x‾\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 ¬A,¬B,A∨B,A∧B,A  ⟹  B,A  ⟺  B\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í:

  • ¬(A∨B)≡¬A∧¬B\neg{(A \lor B)} \equiv \neg{A} \land \neg{B} (de Morganovo pravidlo)

  • ¬(A∧B)≡¬A∨¬B\neg{(A \land B)} \equiv \neg{A} \lor \neg{B} (de Morganovo pravidlo)

  • A∨(B∧C)≡(A∨B)∧(A∨C)A \lor (B \land C) \equiv (A \lor B) \land (A \lor C) (distributivita ∨\lor)

  • A∧(B∨C)≡(A∧B)∨(A∧C)A \land (B \lor C) \equiv (A \land B) \lor (A \land C) (distributivita ∧\land)

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

x1x_1x2x_2x3x_3f(x1,x2,x3)f(x_1, x_2, x_3)
0010
0101
0110
1001
1011
1100
1111

Vektory, pro které f=1f = 1, nazýváme true-pointy, ostatní, pro které f=0f=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(x1,x2,x3)=(¬x1∧x2∧¬x3)∨(x1∧¬x2∧¬x3)∨(x1∧¬x2∧x3)∨(x1∧x2∧x3)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(x1,x2,x3)=(¬x1∨¬x2∨¬x3)∧(¬x1∨¬x2∨x3)∧(¬x1∨x2∨x3)∧(x1∨x2∨¬x3)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 22n2^{2^n} (tabulka má 2n2^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>gf > g právě tehdy, když ∀x:f(x)>g(x)\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  ⟹  f=1T = 1 \implies f = 1 (korektně ∀xT(x)=1  ⟹  f(x)=1\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∨TF \lor T také reprezentuje f.

Důkaz:

  • F≤F∨TF \le F \lor T triviálně

  • F≥F∨TF \ge F \lor T z definice implikantu

Definice: Pokud T1,T2T_1, T_2 jsou termy a T1≤T2T_1 \le T_2 (tj. T2T_2 je "kratší"), říkáme, že T2T_2 absorbuje T1T_1.

Pozorování: Pokud F∨T1∨T2F \lor T_1 \lor T_2 reprezentuje f a T1≤T2T_1 \le T_2, pak F∨T2F \lor T_2 reprezentuje tutéž funkci.

Definice: Termy T1T_1 a T2T_2 mají konflikt v proměnné x, pokud x∈T1x \in T_1

a ¬x∈T2\neg{x} \in T_2 (nebo ¬x∈T1\neg{x} \in T_1 a x∈T2x \in T_2). Řekneme, že T1,T2T_1, T_2 mají konsenus, pokud mají konflikt právě v jedné proměnné. Označíme-li termy T1=A∧x,T2=B∧¬xT_1 = A \land x, T_2 = B \land \neg{x}, pak Cons(A,B)=A∧BCons(A,B) = A \land B.

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

Důkaz:

  • T1≤f,T2≤fT_1 \le f, T_2 \le f

  • T1=A∧xT_1 = A \land x

  • T2=B∧x‾T_2 = B \land \overline{x}

  • T3=A∧BT_3 = A \land B

T3=1⇒(A=1)∧(B=1)⇒(T1=1)∨(T2=1)⇒f=1T_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 T1,T2T_1, T_2, že Cons(T1,T2)Cons(T_1, T_2) není absorbován žádným termem v F a přidej Cons(T1,T2)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=R1∨R2∨…∨RmF = R_1 \lor R_2 \lor \ldots \lor R_m je výstupem algoritmu a nechť PP je primární implikant f, který není obsažen v {R1,…,Rm}\{R_1, \ldots, R_m\}.

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

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

  1. ∣Q∣=n|Q| = n (obsahuje všechny proměnné), z definice Q není implikantem žádného RiR_i, pak musí mít konflikt s každým RiR_i.

    1. Q=1  ⟹  ∀i:Ri=0  ⟹  f=0Q = 1 \implies \forall i: R_i = 0 \implies f = 0

    2. Q=1  ⟹  P=1  ⟹  f=1Q = 1 \implies P = 1 \implies f = 1, což je spor, takové Q ani P nemůže existovat

  2. ∣Q∣<n|Q| <n, pak existuje proměnná x neobsažená v Q. Zkoumejme termy Qx,Qx‾Qx, Q\overline{x}. Nejsou v P{\cal P} (Q je nejdelší), avšak jsou implikanty P (a celé f). Pak existují Ri,RjR_i, R_j takové, že Qx≤Ri,Qx‾≤RjQx \leq R_i, Q\overline{x} \leq R_j (Qx implikuje pravdivost formule, musí být splněn nějaký její term). RiR_i obsahuje x (a nějaké proměnné z Q, jinak by Q≤RiQ \leq R_i), RjR_j obsahuje x‾\overline{x}. Pak Q≤Cons(Ri,Rj)Q \leq Cons(R_i,R_j). Neexistuje Rk,Cons(Ri,Rj)≤RkR_k, Cons(R_i,R_j) \leq R_k (jinak by Q≤RkQ \leq R_k). To je spor s fungováním algoritmu (Cons(Ri,Rj)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=x1x2…xn∨x1ˉy1∨x2ˉy2∨…∨xnˉynF = 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

ParseError: KaTeX parse error: Undefined control sequence: \F at position 1: \̲F̲

je exponenciálně dlouhá vzhledem k délce vstupní formule.