Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

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

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

Example 13.6.2. Two variables over \(B_2\).

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:
\begin{equation*} \begin{array}{cc|c} x_1 & x_2 & f\left(x_1,x_2\right) \\ \hline 0 & 0 & ?\\ 0 & 1 & ?\\ 1 & 0 & ?\\ 1 & 1 & ?\\ \end{array} \end{equation*}
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
\begin{equation*} \begin{array}{lr} \begin{array}{cc|c} x_1 & x_2 & f_1\left(x_1,x_2\right) \\ \hline 0 & 0 & 0\\ 0 & 1 & 0\\ 1 & 0 & 1\\ 1 & 1 & 1\\ \end{array} & \begin{array}{cc|c} x_1 & x_2 & f_3\left(x_1,x_2\right) \\ \hline 0 & 0 & 0\\ 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 1\\ \end{array}\\ \end{array} \end{equation*}
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.

Definition 13.6.3. Minterm.

A Boolean expression generated by \(x_1, x_2, \ldots , x_k\) that has the form
\begin{equation*} \underset{i=1}{\overset{k}{\land }}y_i, \end{equation*}
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{.}\)

Definition 13.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
\begin{gather} \underset{j=1}{\overset{p}{\lor }}\left(a_j\land m_j\right)\tag{13.6.1} \end{gather}
where \(p=2^k\text{,}\) and \(m_1,m_2, \ldots , m_p\) are the minterms generated by \(x_1, \ldots, x_k\text{.}\)

Note 13.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{.}\)
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.

Example 13.6.7.

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
\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*}
Visualization of minterms
Figure 13.6.8. Visualization of minterms for \(x_1 \lor \bar{x_2}\)
Table 13.6.9. Definition of the boolean function \(g\)
\(x_1\) \(x_2\) \(x_3\) \(g\left(x_1, x_2, x_3\right)\)
\(0\) \(0\) \(0\) \(1\)
\(0\) \(0\) \(1\) \(0\)
\(0\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(0\)
\(1\) \(0\) \(1\) \(0\)
\(1\) \(1\) \(0\) \(1\)
\(1\) \(1\) \(1\) \(0\)

Example 13.6.10.

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\)
Therefore,
\begin{equation*} g\left(x_1, x_2, x_3\right)=\left(\overline{x_1}\land \overline{x_2}\land \overline{x_3}\right)\lor \left(\overline{x_1}\land x_2\land x_3\right)\lor \left(x_1\land x_2\land \overline{x_3}\right). \end{equation*}
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.

Exercises Exercises

1.

  1. Write the 16 possible functions of Example 13.6.2.
  2. Write out the tables of several of the above Boolean functions to show that they are indeed different.
  3. Determine the minterm normal forms of
    1. \(\displaystyle g_1\left(x_1, x_2\right)=x_1\lor x_2,\)
    2. \(\displaystyle g_2\left(x_1, x_2\right)=\overline{x_1}\lor \overline{x_2}\)
    3. \(\displaystyle g_3\left(x_1, x_2\right)=\overline{x_1 \land x_2}\)
    4. \(\displaystyle g_4\left(x_1, x_2\right)=1\)
Answer.
  1. \(\displaystyle \begin{array}{l} f_1\left(x_1,x_2\right)=0 \\ f_2\left(x_1,x_2\right)=\left(\overline{x_1}\land \overline{x_2}\right) \\ f_3\left(x_1,x_2\right)=\left(\overline{x_1}\land x_2\right) \\ f_4\left(x_1,x_2\right)=\left(x_1\land \overline{x_2}\right) \\ f_5\left(x_1,x_2\right)=\left(x_1\land x_2\right) \\ f_6\left(x_1,x_2\right)=\left(\left(\overline{x_1}\land \overline{x_2}\right)\lor \left(\overline{x_1}\land x_2\right)\right)=\overline{x_1} \\ f_7\left(x_1,x_2\right)=\left(\left(\overline{x_1}\land \overline{x_2}\right)\lor \left(x_1\land \overline{x_2}\right)\right)=\overline{x_2} \\ f_8\left(x_1,x_2\right)=\left(\left(\overline{x_1}\land \overline{x_2}\right)\lor \left(x_1\land x_2\right)\right)=\left(\left(x_1\land x_2\right)\lor \left(\overline{x_1}\land \overline{x_2}\right)\right) \\ f_9\left(x_1,x_2\right)=\left(\left(\overline{x_1}\land x_2\right)\lor \left(x_1\land \overline{x_2}\right)\right)=\left(\left(x_1\land \overline{x_2}\right)\lor \left(\overline{x_1}\land x_2\right)\right) \\ f_{10}\left(x_1,x_2\right)=\left(\left(\overline{x_1}\land x_2\right)\lor \left(x_1\land x_2\right)\right)=x_2 \\ f_{11}\left(x_1,x_2\right)=\left(\left(x_1\land \overline{x_2}\right)\lor \left(x_1\land x_2\right)\right)=x_1 \\ f_{12}\left(x_1,x_2\right)=\left(\left(\overline{x_1}\land \overline{x_2}\right)\lor \left(\overline{x_1}\land x_2\right)\lor \left(x_1\land \overline{x_2}\right)\right)=\left(\overline{x_1}\lor \overline{x_2}\right) \\ f_{13}\left(x_1,x_2\right)=\left(\left(\overline{x_1}\land \overline{x_2}\right)\lor \left(\overline{x_1}\land x_2\right)\lor \left(x_1\land x_2\right)\right)=\left(\overline{x_1}\lor x_2\right) \\ f_{14}\left(x_1,x_2\right)=\left(\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)\right)=\left(x_1\lor \overline{x_2}\right) \\ f_{15}\left(x_1,x_2\right)=\left(\left(\overline{x_1}\land x_2\right)\lor \left(x_1\land \overline{x_2}\right)\lor \left(x_1\land x_2\right)\right)=\left(x_1\lor x_2\right) \\ f_{16}\left(x_1,x_2\right)=\left(\left(\overline{x_1}\land \overline{x_2}\right)\lor \left(\overline{x_1}\land x_2\right)\lor \left(x_1\land \overline{x_2}\right)\lor \left(x_1\land x_2\right)\right)=1 \\ \end{array}\)
  2. The truth table for the functions in part (a) are
    \begin{equation*} \begin{array}{llllllllll} x_1 & x_2 & f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \end{array} \end{equation*}
    \begin{equation*} \begin{array}{llllllllll} x_1 & x_2 & f_9 & f_{10} & f_{11} & f_{12} & f_{13} & f_{14} & f_{15} & f_{16} \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ \end{array} \end{equation*}
    1. \(\displaystyle g_1\left(x_1,x_2\right)=f_{15}\left(x_1,x_2\right)\)
    2. \(\displaystyle g_2\left(x_1,x_2\right)=f_{12}\left(x_1,x_2\right)\)
    3. \(\displaystyle g_3\left(x_1,x_2\right)=f_{12}\left(x_1,x_2\right)\)
    4. \(\displaystyle g_4\left(x_1,x_2\right)=f_{16}\left(x_1,x_2\right)\)

2.

Consider the Boolean expression \(f\left(x_1, x_2, x_3\right)=\left(\overline{x_3}\land x_2\right)\lor\left(\overline{x_1}\land x_3\right)\lor \left(x_2\land x_3\right)\) on \(\left[B_2^3; \lor, \land, - \right].\)
  1. Simplify this expression using basic Boolean algebra laws.
  2. Write this expression in minterm normal form.
  3. Write out the table for the given function defined by \(f\) and compare it to the tables of the functions in parts a and b.
  4. How many possible different functions in three variables on \(\left[B_2; \lor, \land, - \right]\) are there?

3.

Let \([B; \lor , \land, - ]\) be a Boolean algebra of order 4, and let \(f\) be a Boolean function of two variables on \(B\text{.}\)
  1. How many elements are there in the domain of f?
  2. How many different Boolean functions are there of two, variables? Three variables?
  3. Determine the minterm normal form of \(f\left(x_1, x_2\right)=x_1\lor x_2\text{.}\)
  4. If \(B=\{0, a, b, 1\}\text{,}\) define a function from \(B^2\) into \(B\) that is not a Boolean function.
Answer.
  1. The number of elements in the domain of \(f\) is \(16=4^2=\left| B\right| ^2\)
  2. With two variables, there are \(4^3 = 256\) different Boolean functions. With three variables, there are \(4^8=65536\) different Boolean functions.
  3. \(\displaystyle f\left(x_1,x_2\right)=\left(1\land \overline{x_1}\land \overline{x_2}\right)\lor \left(1\land \overline{x_1}\land x_2\right)\lor \left(1\land x_1\land \overline{x_2}\right)\lor \left(0\land x_1\land x_2\right)\)
  4. 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)\)
    \begin{equation*} \begin{array}{c} f(0,0)=0 \Rightarrow M(0,0)=0 \Rightarrow c_1= 0\\ f(0,1)=1 \Rightarrow M(0,0)=1 \Rightarrow c_2= 1\\ f(1,0)=a \Rightarrow M(0,0)=a \Rightarrow c_3= a\\ f(1,1)=a \Rightarrow M(0,0)=a \Rightarrow c_4= a\\ \end{array} \end{equation*}
    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.
You have attempted of activities on this page.
PrevTopNext