CHAPTER 9 |
Representations of Boolean Functions by Formulas |

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 ...

Start Free Trial

No credit card required