43 CNF's

A formula is CNF if it has the form ${\bigwedge }_i,{\bigvee }_j,I_{ij}$, where each $I_{ij}$ is a literal (i.e., either $x$ or $\neg x$ for a propositional variable $x$)

Definition (Computation by a CNF)

Given a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$, we say that $f$ is computed by a CNF $A(x_1,\cdots ,x_n)$ if, for any $\overrightarrow{b}\in \{0,1{\}}^n$ we have:

$$A(b_1,\cdots ,b_n)=f(b_1,\cdots ,b_n)$$

Example: exclusive-or

The exclusive-or function $\oplus :\{0,1{\}}^2\to \{0,1\}$ is defined by:

$$x\oplus y⟺\text{exactly one of x or y is 1}$$

$x\oplus y$ is computed by the following CNF:

$$(x\vee y)\wedge (\neg x\vee \neg y)$$

Adequacy of CNFs

Theorem

For every boolean function $f:\{0,1{\}}^n\to \{0,1\}$ there is a CNF $A_f$ computing it.

Proof

Let $F:=\{\overrightarrow{b}\in \{0,1{\}}^n:f(\overrightarrow{b})=0\}$. For $b\in \{0,1\}$ write:

$$b\star x:=\{\begin{array}{l}xb=0\\ \neg xb=1\end{array}$$

Now define

$$A_f:=\underset{\overrightarrow{b}\in F}{\bigwedge }\underset{i=1}{\overset{n}{\bigvee }}{b}_i\star x_i$$