Representing Boolean Functions

Introduction: Boolean function can be represented by a Boolean sum of Boolean products of the variables and their complements. The solution of this problem shows that every Boolean function can be represented using the three Boolean operators ·, , and Boolean functions can be represented using only one operator. Both of these problems have practical importance in circuit design.

Sum-of-Products Expansions: We will use examples to illustrate one importantway to find a Boolean expression that represents a Boolean function.

DEFINITION 1 A literal is a Boolean variable or its complement. A minterm of the Boolean variables x1, x2, . . . , xn is a Boolean product y1y2 · · · yn, where yi = xi or yi = xi . Hence, a minterm is a product of n literals, with one literal for each variable.

A minterm has the value 1 for one and only one combination of values of its variables. More precisely, the minterm y1y2 . . . yn is 1 if and only if each yi is 1, and this occurs if and only if xi = 1 when yi = xi and xi = 0 when yi = xi .

EXAMPLE 2 Find a minterm that equals 1 if x1 = x3 = 0 and x2 = x4 = x5 = 1, and equals 0 otherwise.
Solution: The minterm has the correct set of values.

By taking Boolean sums of distinct minterms we can build up a Boolean expression with a specified set of values. In particular, a Boolean sum of minterms has the value 1 when exactly one of the minterms in the sum has the value 1. It has the value 0 for all other combinations of values of the variables. Consequently, given a Boolean function, a Boolean sum of minterms can be formed that has the value 1 when this Boolean function has the value 1, and has the value 0 when the function has the value 0. The minterms in this Boolean sum correspond to those combinations of values for which the function has the value 1. The sum of minterms that represents the function is called the sum-of-products expansion or the disjunctive normal form of the Boolean function.

EXAMPLE 3 Find the sum-of-products expansion for the function F(x, y, z) =

Solution:We will find the sum-of-products expansion of F(x, y, z) in two ways. First, we will use Boolean identities to expand the product and simplify.We find that

Second, we can construct the sum-of-products expansion by determining the values of F for all possible values of the variables x, y, and z. These values are found in Table 2. The sum-ofproducts expansion of F is the Boolean sum of three minterms corresponding to the three rows of this table that give the value 1 for the function. This gives

It is also possible to find a Boolean expression that represents a Boolean function by taking a Boolean product of Boolean sums. The resulting expansion is called the conjunctive normal form or product-of-sums expansion of the function. These expansions can be found from sum-of-products expansions by taking duals. How to find such expansions directly is described in Exercise 10.

Functional Completeness: Every Boolean function can be expressed as a Boolean sum of minterms. Each minterm is the Boolean product of Boolean variables or their complements. This shows that every Boolean function can be represented using the Boolean operators ·, , and −. Because every Boolean function can be represented using these operators we say that the set {·, , − } is functionally complete. Can we find a smaller set of functionally complete operators? We can do so if one of the three operators of this set can be expressed in terms of the other two. This can be done using one of De Morgan’s laws.We can eliminate all Boolean sums using the identity

which is obtained by taking complements of both sides in the second De Morgan law, given in Table 5 in Section 12.1, and then applying the double complementation law. This means that the set {·, − } is functionally complete. Similarly, we could eliminate all Boolean products using the identity

which is obtained by taking complements of both sides in the first De Morgan law, given in Table 5 in Section 12.1, and then applying the double complementation law. Consequently { , − } is functionally complete. Note that the set { , ·} is not functionally complete, because it is impossible to express the Boolean function F(x) = x using these operators

We have found sets containing two operators that are functionally complete. Can we find a smaller set of functionally complete operators, namely, a set containing just one operator? Such sets exist. Define two operators, the | or NAND operator, defined by 1 | 1 = 0 and 1 | 0 = 0 | 1 = 0 | 0 = 1; and the ↓ or NOR operator, defined by 1 ↓ 1 = 1 ↓ 0 = 0 ↓ 1 = 0 and 0 ↓ 0 = 1. Both of the sets { | } and { ↓ } are functionally complete. To see that { | } is functionally complete, because {·, − } is functionally complete, all that we have to do is show that both of the operators · and − can be expressed using just the | operator. This can be done as