9 - Representations of Boolean Functions by Formulas

Summary

In Chapter 6, we used Boolean formulas to represent Boolean functions. The idea was to write a Boolean formula over a set of n variables and then assign 0−1 values to each variable. This assignment induces a truth value to the formula, and thus we have a Boolean function over n bits. In fact, any Boolean function can be represented by a Boolean formula if the set of connectives is complete. In Section 6.6, we proved that the set {¬, and, or} is a complete set of connectives.

In this chapter, we consider special representations of functions that are often called normal forms. Boolean formulas in a normal form are restricted forms of formulas.

Given a Boolean function, one may want to find a shortest representation of the function by a Boolean formula. This question is not well defined because one needs to specify how a Boolean function is represented. Suppose the function is described by its truth table. In this case, the truth table has 2ⁿ entries, where n denotes the number of bits in the domain of the function. Obviously, we can only read or write truth tables for rather small values of n. If n ≥ 100, then all the atoms in the universe would not suffice!

Nevertheless, we present a method by Quine and McCluskey to find a shortest representation of a function by a Boolean formula in a normal form called a sum of products.