59 Converting between DNFs and CNFs

Distributivity

Note that we can show the following equalities e.g., by truth tables:

$$\begin{array}{rl}x\wedge (y\vee z)& =(x\wedge y)\vee (x\wedge z)\\ x\vee (y\wedge z)& =(x\vee y)\wedge (x\vee z)\end{array}$$

By recursively applying these laws, we obtain the following:

Theorem (Distributing DNFs to CNFs and vice-versa)

1. Let $A={\bigvee }_{i=1}^n\bigwedge T_i$ be a DNF with ${\max }_{i=1}^n|T_i|\le m$. Then $A$ is computed by a CNF with at most $m^n$ clauses of size at most $n$.
2. Similarly, if $A={\bigwedge }_{i=1}^n\bigvee T_i$ be a CNF with ${\max }_{i=1}^n|C_i|\le m$. Then $A$ is computed by a DNF with at most $m^n$ clauses of size at most $n$.

Example

$x\oplus y$

$$\begin{array}{rl}x\oplus y& =(x\wedge \neg y)\vee (\neg x\wedge y)\\ & =((x\wedge \neg y)\vee \neg x)\wedge ((x\wedge \neg y)\vee y)\\ & =(x\vee \neg x)\wedge (\neg y\vee \neg x)\wedge (x\vee y)\wedge (\neg y\vee y)\\ & =(\neg y\vee \neg x)\wedge (x\vee y)\end{array}$$

$MA{J}^3$

$$\begin{array}{rl}MA{J}^3(x,y,z)& =(x\wedge y)\vee (x\wedge z)\vee (y\wedge z)\\ & =((x\wedge y)\vee (x\wedge z)\vee y)\wedge ((x\wedge y)\vee (x\wedge z)\vee z)\\ & =(x\vee y)\wedge (y\vee z)\wedge (x\vee z)\end{array}$$

Proof of distribution theorem

DNF to CNF

$A={\bigvee }_{i=1}^n\bigwedge T_i$ where $|T_i|\le m$, $\forall i$.
$\exists C_A$ a CNF equivalent to $A$ with $\le m^n$ clauses of size $\le n$

Proof: induction on n

1. Base: $n=1$ A is already a CNF of appropriate complexity
2. Inductive Step:
   • $A={\bigvee }_{i=1}^{n+1}\bigwedge T_i=\underset{A^{\prime }}{\underbrace{\underset{i=1}{\overset{n}{\bigvee }}\bigwedge T_i}}\vee \bigwedge T_{n+1}$
   • By inductive hypothesis we have ${\bigwedge }_{j=1}^{m^n}\bigvee C_j\vee \bigwedge T_{n+1}$ where $|C_j|\le n$
   • By distributivity we have ${\bigwedge }_{L\in T_{n+1}}\left({\bigwedge }_{j=1}^{m^n}\bigvee C_j\vee L\right)={\bigwedge }_{L\in T_{n+1}}{\bigwedge }_{j=1}^{m^n}\left(\bigvee (C_j\vee L)\right)=C_A$