Lesson 5

Conjunctive Normal Form (CNF) is a conjunction of disjunctions of literals, where a literal is a variable or its negation. For example: \[(\overline{x_3}\lor x_{1}) \land (x_{2} \lor x_{3}) \land (x_{1} \lor x_{4} \lor \overline{x_2}\lor x_{3}) \ .\] Each bracket in this expression is called a clause and essentially forbids one assignment to the variables contained in that clause: for example, the first clause states that if \(x_{3}=1\) and \(x_{1}=0\), then the entire formula evaluates to zero.

Disjunctive Normal Form (DNF) is a disjunction of conjunctions of literals: \[(x_{1} \land \overline{x_2}) \lor (\overline{x_3}\land x_{1}) \ .\] Here, each bracket (called a monomial) simply specifies a condition under which the entire formula evaluates to one: for example, if \(x_{3}=0\) and \(x_{1}=1\), the formula equals one. Note that the above DNF can also be written as \[x_{1}\overline{x_2}\lor \overline{x_3}x_{1} \ .\] Much as we omit multiplication signs (that is, we usually write just \(xy\) instead of \(x \cdot y\) when \(x\) and \(y\) denote integers), we omit the \(\land\) signs here.