Lesson 6

Theorem. Any Boolean function \(f \in B_{n}\) can be represented as CNF and DNF.

Proof. Let’s prove this using the toy example from the beginning of this section.

To define \(f\) in CNF, we need to “forbid” all five assignments where the function equals zero: \[(x_{1} \lor x_{2} \lor x_{3}) \land (x_{1} \lor \overline{x_2}\lor x_{3}) \land (\overline{x_1}\lor x_{2} \lor x_{3}) \land (\overline{x_1}\lor x_{2} \lor \overline{x_3}) \land (\overline{x_1}\lor \overline{x_2}\lor \overline{x_3}) \ .\] In DNF, we need to “allow” only those assignments where the function equals one: \[\overline{x_1}\overline{x_2}x_{3} \lor \overline{x_1}x_{2}x_{3} \lor x_{1}x_{2}\overline{x_3}\ .\]◼