Discrete Mathematics for Computer Science

Section 12.6 Boolean Expressions

In this section, we will use our background from the previous sections and set theory to develop a procedure for simplifying Boolean expressions. This procedure has considerable application to the simplification of circuits in switching theory or logical design.

This definition is the analog of the definition of a proposition generated by a set of propositions, presented in Section 4.2.

Each Boolean expression generated by \(k\) variables, \(e\left(x_1, \ldots , x_k\right)\text{,}\) defines a function \(f: B^k \to B\) where \(f\left(a_1,\ldots , a_k\right)=e\left(a_1, \ldots , a_k\right)\text{.}\) If \(B\) is a finite Boolean algebra, then there are a finite number of functions from \(B^k\) into \(B\text{.}\) Those functions that are defined in terms of Boolean expressions are called Boolean functions. As we will see, there is an infinite number of Boolean expressions that define each Boolean function. Naturally, the “shortest” of these expressions will be preferred. Since electronic circuits can be described as Boolean functions with \(B=B_2\text{,}\) this economization is quite useful.

In what follows, we make use of Exercise 8.1.5.7 in Section 8.1 for counting the number of functions.

Now, let's count the number of different Boolean functions in a more general setting. We will consider two cases: first, when \(B=B_2\) , and second, when \(B\) is any finite Boolean algebra with \(2^n\) elements.

Let \(B=B_2\text{.}\) Each function \(f:B^k\to B\) is defined in terms of a table having \(2^k\) rows. Therefore, since there are two possible images for each element of \(B^k\text{,}\) there are 2 raised to the \(2^k\text{,}\) or \(2^{2^k}\) different functions. We will show that every one of these functions is a Boolean function.

Now suppose that \(\lvert B\rvert =2^n>2\text{.}\) A function from \(B^k\) into \(B\) can still be defined in terms of a table. There are \(\lvert B\rvert^k\) rows to each table and \(\lvert B\rvert\) possible images for each row. Therefore, there are \(2^n\) raised to the power \(2^{nk}\) different functions. We will show that if \(n>1\text{,}\) not every one of these functions is a Boolean function.

Since all Boolean algebras are isomorphic to a Boolean algebra of sets, the analogues of statements in sets are useful in Boolean algebras.

An example of the notation is that \(M_{110} = x_1 \land x_2 \land \bar{x_3}\text{.}\)

By a direct application of the Rule of Products we see that there are \(2^k\) different minterms generated by \(x_1, \ldots , x_k\text{.}\)

The uniqueness in this theorem does not include the possible ordering of the minterms in \(M\) (commonly referred to as “uniqueness up to the order of minterms”). The proof of this theorem would be quite lengthy, and not very instructive, so we will leave it to the interested reader to attempt. The implications of the theorem are very interesting, however.

If \(\lvert B\rvert =2^n\text{,}\) then there are \(2^n\) raised to the \(2^k\) different minterm normal forms. Since each different minterm normal form defines a different function, there are a like number of Boolean functions from \(B^k\) into \(B\text{.}\) If \(B=B_2\text{,}\) there are as many Boolean functions (2 raised to the \(2^k\)) as there are functions from \(B^k\) into \(B\text{,}\) since there are \(2\) raised to the \(2^{n}\) functions from \(B^k\) into \(B\text{.}\) The significance of this result is that any desired function can be realized using electronic circuits having 0 or 1 (off or on, positive or negative) values.

More complex, multivalued circuits corresponding to boolean algebras with more than two values would not have this flexibility because of the number of minterm normal forms, and hence the number of boolean functions, is strictly less than the number of functions.

We will close this section by examining minterm normal forms for expressions over \(B_2\) , since they are a starting point for circuit economization.

Consider the Boolean expression \(f\left(x_1, x_2\right) =x_1 \lor \overline{x_2} \text{.}\) One method of determining the minterm normal form of \(f\) is to think in terms of sets. Consider the diagram with the usual translation of notation in Figure 12.6.8. Then

\begin{equation*} \begin{split} f\left(x_1, x_2\right)&=\left(\overline{x_1}\land \overline{x_2}\right)\lor \left(x_1\land \overline{x_2}\right)\lor \left(x_1\land x_2\right)\\ & = M_{00} \lor M_{10} \lor M_{11} \end{split} \end{equation*}

The minterm normal form is a first step in obtaining an economical way of expressing a given Boolean function. However, it is often not the simplest form. The process of minimizing Boolean expressions is important to logical circuit design which we will see in the next two sections.