60 De Morgan's Law

We can also show the following equalities by truth tables

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

Theorem (Duality theorem for DNFs and CNFs)

If $f:\{0,1{\}}^k\to \{0,1\}$ is computed by ${\bigvee }_{i=1}^m{\bigwedge }_{j=1}^{n_i}{I}_{ij}$ where each $I_{ij}$ is a literal, then $\neg f$ is computed by ${\bigwedge }_{i=1}^m{\bigvee }_{j=1}^{n_i}\neg I_{ij}$
Similarly, If $f:\{0,1{\}}^k\to \{0,1\}$ is computed by ${\bigwedge }_{i=1}^m{\bigvee }_{j=1}^{n_i}{I}_{ij}$ where each $I_{ij}$ is a literal, then $\neg f$ is computed by ${\bigvee }_{i=1}^m{\bigwedge }_{j=1}^{n_i}\neg I_{ij}$

Example: Constructing a CNF for $\oplus$, again