58 DNFs

A disjunctive normal form (DNF) is a formula of the form:

$$\underset{i=1}{\overset{n}{\bigvee }}\bigwedge T_i$$

where each $T_i$ is a set of literals. We sometimes call $\bigwedge T_i$ a term. Examples:

$$\begin{array}{r}x\oplus y=(x\wedge \neg y)\vee (\neg x\wedge y)\\ \delta (x,y,z)=(\neg x\wedge y)\vee (x\wedge z)\end{array}$$

Adequacy of DNFs

Theorem

For every Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ there is a DNF $B_f$ computing it

Proof

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

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

Now define

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