CNFの完全性
定理
任意のブール関数$ f : 2^l \to 2には同等の$ l変数のCNF$ \Phiが存在し、大きさは$ O(l2^l) $ \forall_{l \in \N} \forall_{f : 2^l \to 2}\exists_{\Phi : \text{CNF}}[f = \Phi]
Proof.
$ l変数のCNF
$ \ne_{x}(y) := \bigvee_i n_{x_i}(y_i)
$ n_{0}(y_i) := y_i
$ n_{1}(y_i) := \neg y_i
ここで$ x \ne y \iff \ne_{x}(y) = 1
$ x \ne y \iff n_{x}(y) = 1より
CNFを次のように定義する
$ \Phi(v) := \bigwedge_{w:\ f(w)=0} \ne_{w} (v)
$ \Phi(v) = 0 \iff \exists w[f(w) = 0 \land \ne_{w}(v) = 0] \iff \exists w[f(w) = 0 \land w = v] \iff f(v) = 0 より$ f = \Phi
$ \ne_{x}(y)の長さは$ O(l)
よって$ \Phi(v)の長さは$ O(l \cdot 2^l)