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.
Definition13.6.1.Boolean Expression.
Let \([B; \lor , \land, - ]\) be any Boolean algebra, and let \(x_1, x_2,
\ldots , x_k\) be variables in \(B\text{;}\) that is, variables that can assume values from \(B\text{.}\) A Boolean expression generated by \(x_1, x_2, \ldots , x_k\) is any valid combination of the \(x_i\) and the elements of \(B\) with the operations of meet, join, and complementation.
This definition is the analog of the definition of a proposition generated by a set of propositions, presented in Section 3.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 7.1.5.5 in Section 7.1 for counting number of functions.
Consider any Boolean algebra of order 2, \([B; \lor, \land, - ]\text{.}\) How many functions \(f:B^2\to B\) are there? First, all Boolean algebras of order 2 are isomorphic to \(\left[B_2; \lor , \land, - \right]\) so we want to determine the number of functions \(f:B_2^2\to B_2\text{.}\) If we consider a Boolean function of two variables, \(x_1\) and \(x_2\text{,}\) we note that each variable has two possible values 0 and 1, so there are \(2^2\) ways of assigning these two values to the \(k=2\) variables. Hence, the table below has \(2^2=4\) rows. So far we have a table such as this one:
How many possible different functions can there be? To list a few:\(f_1\left(x_1, x_2\right)=x_1\text{,}\)\(f_2\left(x_1,
x_2\right)=x_2\text{,}\)\(f_3\left(x_1, x_2\right)=x_1\lor x_2\text{,}\)\(f_4\left(x_1, x_2\right)=\left(x_1\land \overline{x_2}\right)\lor x_2\text{,}\)\(f_5\left(x_1,
x_2\right)= x_1\land x_2\lor \overline{x_2}\text{,}\) etc. Each of these will fill in the question marks in the table above. The tables for \(f_1\textrm{ }\) and \(f_3\) are
Two functions are different if and only if their tables are different for at least one row. Of course by using the basic laws of Boolean algebra we can see that \(f_3=f_4\text{.}\) Why? So if we simply list by brute force all “combinations” of \(x_1 \textrm{ and } x_2\) we will obtain unnecessary duplication. However, we note that for any combination of the variables \(x_1\text{,}\) and \(x_2\) there are only two possible values for \(f\left(x_1, x_2\right)\text{,}\) namely 0 or 1. Thus, we could write \(2^4=16\) different functions on 2 variables.
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.
Definition13.6.3.Minterm.
A Boolean expression generated by \(x_1, x_2, \ldots , x_k\) that has the form
where each \(y_i\) may be either \(x_i\) or \(\overline{x_i}\) is called a minterm generated by \(x_1, x_2,
\ldots , x_k\text{.}\) We use the notation \(M_{\delta_1 \delta_2 \cdots \delta_k}\) for the minterm generated by \(x_1, x_2, \ldots , x_k\text{,}\) where \(y_i=x_i\) if \(\delta_i = 1\) and \(y_i=\bar{x_i}\) if \(\delta_i = 0\)
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{.}\)
Definition13.6.4.Minterm Normal Form.
A Boolean expression generated by \(x_1, \ldots , x_k\) is in minterm normal form if it is the join of expressions of the form \(a \land m\text{,}\) where \(a\in B\) and \(m\) is a minterm generated by \(x_1, \ldots , x_k\text{.}\) That is, it is of the form
where \(p=2^k\text{,}\) and \(m_1,m_2, \ldots , m_p\) are the minterms generated by \(x_1, \ldots, x_k\text{.}\)
Note13.6.5.
We seem to require every minterm generated by \(x_1, \ldots, x_k\text{,}\) in (13.6.1), and we really do. However, some of the values of \(a_j\) can be \(\pmb{0}\text{,}\) which effectively makes the corresponding minterm disappear.
If \(B=B_2\text{,}\) then each \(a_j\) in a minterm normal form is either 0 or 1. Therefore, \(a_j\land m_j\) is either 0 or \(m_j\text{.}\)
Theorem13.6.6.Uniqueness of Minterm Normal Form.
Let \(e\left(x_1,\ldots , x_k\right)\) be a Boolean expression over B. There exists a unique minterm normal form \(M\left(x_1, \ldots , x_k\right)\) that is equivalent to \(e\left(x_1, \ldots , x_k\right)\) in the sense that e and M define the same function from \(B^k\) into \(B\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 13.6.8. Then
Consider the function \(g:B_2^3 \to B_2\) defined by Table 13.6.9.
The minterm normal form for \(g\) can be obtained by taking the join of minterms that correspond to rows that have an image value of 1. If \(g\left(a_1, a_2, a_3\right)=1\text{,}\) then include the minterm \(y_1\land y_2\land y_3\) where
\begin{equation*}
y_j=\begin{cases}
x_j & \textrm{ if } a_j=1 \\
\bar{x_j} & \textrm{ if } a_j=0\\
\end{cases}
\end{equation*}
Or, to use alternate notation, include \(M_{a_1a_2a_3}\) in the expression if and only if \(g\left(a_1, a_2, a_3\right)=1\)
The minterm normal form is a first step in obtaining an economical way of expressing a given Boolean function. For functions of more than three variables, the above set theory approach tends to be awkward. Other procedures are used to write the normal form. The most convenient is the Karnaugh map, a discussion of which can be found in any logical design/switching theory text (see, for example, [18]), on en.wikipedia.org/wiki/Karnaugh_map.
Consider \(f:B^2\to B\text{,}\) defined by \(f(0,0)=0\text{,}\)\(f(0,1)=1\text{,}\)\(f(1,0)=a\text{,}\)\(f(1,1)=a\text{,}\) and \(f(0,a)=b\text{,}\) with the images of all other pairs in \(B^2\) defined arbitrarily. This function is not a Boolean function. If we assume that it is Boolean function then \(f\) can be computed with a Boolean expression \(M\left(x_1,x_2\right)\text{.}\) This expression can be put into minterm normal form: \(M\left(x_1,x_2\right)=\left(c_1\land \overline{x_1}\land \overline{x_2}\right)\lor \left(c_2\land \overline{x_1}\land x_2\right)\lor \left(c_3\land
x_1\land \overline{x_2}\right)\lor \left(c_4\land x_1\land x_2\right)\)
Therefore, \(M\left(x_1,x_2\right)=\left(\overline{x_1}\land x_2\right)\lor \left(a\land x_1\land \overline{x_2}\right)\lor \left(a\land x_1\land x_2\right)\) and so, using this formula, \(M(0,a)=\left(\bar{0}\land a\right)\lor \left(a\land 0\land \bar{a}\right)\lor (a\land 0\land a)=a\) This contradicts \(f(0,a)=b\text{,}\) and so \(f\) is not a Boolean function.
