Lesson 7

One and the same function can be represented in CNF in different ways. For example, consider the function \(f(x_{1},x_{2})=x_{2}\). The most natural CNF for it is \((x_{2})\). At the same time, the method from the proof above will yield the following CNF: \((x_{1} \lor x_{2}) \land (\overline{x_1}\lor x_{2})\).

This raises a natural question: can we quickly find the shortest representation of a function in CNF? Such a task is computationally hard (NP-hard), so we do not currently know efficient algorithms for it. All known algorithms for minimizing the number of clauses, therefore, have exponential running time and, in practice, work in a reasonable time only for a small number of variables. The code below finds the optimal CNF representation for the function \(x \oplus yz\). Note that the method from the proof above produces four 3-clauses.

from sympy.logic.boolalg import to_cnf
from sympy.abc import x, y, z

print(to_cnf(x ^ (y & z)))

(x | y) & (x | z) & (~x | ~y | ~z)

CNF/DNF are natural representations of Boolean functions in the sense that we often want to express conditions in exactly that way: either prohibit all bad configurations or allow all good configurations. Nevertheless, CNF/DNF for some Boolean functions can be of enormous size (exponential in \(n\)).