Conjunctive Normal Form (CNF)
In Boolean algebra, Conjunctive Normal Form (CNF) represents a Boolean function as a conjunction (AND, \(\land\)) of clauses, where each clause is a disjunction (OR, \(\lor\)) of literals in either direct form $ x_i $ or negated form $ \overline{x_i} $. $$ ( x_1 \lor ... \lor x_n ) \ \land \ ... \ \land \ ( x_1 \lor ... \lor x_n ) $$
A single clause in CNF is considered true if at least one of its literals holds true.
Not every clause needs to encompass all variables of the Boolean function. They can incorporate any subset of the variables, including individual literals.
The essential requirement is that the collective conjunction of clauses accurately represents the original Boolean function.
CNF can depict any Boolean function, though this might lead to expressions that are either lengthy or complex.
Example
Let's look at how to express the Boolean function \( f(x, y, z) \) in CNF format.
$$ f(x, y, z) = (x \land \overline{y}) \lor z $$
To convert this into CNF, we leverage the properties of Boolean algebra, especially De Morgan's laws and distributive rules.
Initially, we expand the OR within an AND:
$$ f(x, y, z) = (x \land \overline{y}) \lor z $$
Applying distributive logic, we then obtain the CNF representation of the initial Boolean function \( f(x,y,z) \).
\[ f(x, y, z) = (x \lor z) \land (\overline{y} \lor z) \]
This CNF configuration is comprised solely of two clauses:
- \( (x \lor z) \)
- \( (\overline{y} \lor z) \)
Each clause is true (1) if one of its literals is true.
Overall, the function yields true (1) if all clauses are true. Otherwise, it results in false (0).
Below is the truth table:
\[
\begin{array}{ccc|cc|c}
x & y & z & x \lor z & \overline{y} \lor z & f(x, y, z) \\
\hline
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 \\
\end{array}
\]
The truth table also demonstrates the partial outcomes for each clause:
- The clause \( x \lor z \) is true if either \( x \) or \( z \) is true.
- The clause \( \overline{y} \lor z \) is true if \( y \) is false (i.e., \( \overline{y} \) is true) or \( z \) is true.
The Boolean function $ f(x,y,z) $ is true if both \( x \lor z \) and \( \overline{y} \lor z \) are simultaneously true (the AND value of these two expressions).
CNF is particularly valuable in the synthesis of logic circuits, solving logic problems, and in search algorithms such as those used in SAT solvers, which have wide applications across operations research and computer science.
