3.2.1 Boolean Expressions

In addition to binary objects, Boolean algebra also has operations that can be performed on these objects, or variables. Combining the variables and operators yields Boolean expressions. A Boolean function typically has one or more input values and yields a result, based on these input values, in the range {0,1}.

Three common Boolean operators are AND, OR, and NOT. To better understand these operators, we need a mechanism to allow us to examine their behaviors. A Boolean operator can be completely described using a table that lists the inputs, all possible values for these inputs, and the resulting values of the operation for all possible combinations of these inputs. This table is called a truth table. A truth table shows the relationship, in tabular form, between the input values and the result of a specific Boolean operator or function on the input variables. Let's look at the Boolean operators AND, OR, and NOT to see how each is represented, using both Boolean algebra and truth tables.

The logical operator AND is typically represented by either a dot or no symbol at all. For example, the Boolean expression xy is equivalent to the expression x  * y and is read "x and y." The expression xy is often referred to as a Boolean product. The behavior of this operator is characterized by the truth table shown in Table 3.1.

Table 3.1: The Truth Table for AND

Inputs	Outputs
x  y	xy
0  0	0
0  1	0
1  0	0
1  1	1

The result of the expression xy is 1 only when both inputs are 1, and 0 otherwise. Each row in the table represents a different Boolean expression, and all possible combinations of values for x and y are represented by the rows in the table.

The Boolean operator OR is typically represented by a plus sign. Therefore, the expression x + y is read "x or y." The result of x + y is 0 only when both of its input values are 0. The expression x + y is often referred to as a Boolean sum. The truth table for OR is shown in Table 3.2.

Table 3.2: The Truth Table for OR

Inputs	Outputs
x  y	x + y
0  0	0
0  1	1
1  0	1
1  1	1

The remaining logical operator, NOT, is represented typically by either an overscore or a prime. Therefore, both and x' are read as "NOT x." The truth table for NOT is shown in Table 3.3.

Table 3.3: The Truth Table for NOT

Inputs	Outputs
x
0	1
1	0

We now understand that Boolean algebra deals with binary variables and logical operations on those variables. Combining these two concepts, we can examine Boolean expressions composed of Boolean variables and multiple logic operators. For example, the Boolean function:

is represented by a Boolean expression involving the three Boolean variables x, y, and z and the logical operators OR, NOT, and AND. How do we know which operator to apply first? The rules of precedence for Boolean operators give NOT top priority, followed by AND, and then OR. For our previous function F, we would negate y first, then perform the AND of and z, and lastly OR this result with x.

We can also use a truth table to represent this expression. It is often helpful, when creating a truth table for a more complex function such as this, to build the table representing different pieces of the function, one column at a time, until the final function can be evaluated. The truth table for our function F is shown in Table 3.4.

Table 3.4: The Truth Table for F(x,y,z) = x + y-z

Inoputs		Outputs
x y z		x + = F
0 0 0	1 0	0
0 0 1	1 1	1
0 1 0	0 0	0
0 1 1	0 0	0
1 0 0	1 0	1
1 0 1	1 1	1
1 1 0	0 0	1
1 1 1	0 0	1

The last column in the truth table indicates the values of the function for all possible combinations of x, y, and z. We note that the real truth table for our function F consists of only the first three columns and the last column. The shaded columns show the intermediate steps necessary to arrive at our final answer. Creating truth tables in this manner makes it easier to evaluate the function for all possible combinations of the input values.

3.2.2 Boolean Identities

Frequently, a Boolean expression is not in its simplest form. Recall from algebra that an expression such as 2x + 6x is not in its simplest form; it can be reduced (represented by fewer or simpler terms) to 8x. Boolean expressions can also be simplified, but we need new identities, or laws, that apply to Boolean algebra instead of regular algebra. These identities, which apply to single Boolean variables as well as Boolean expressions, are listed in Table 3.5. Note that each relationship (with the exception of the last one) has both an AND (or product) form and an OR (or sum) form. This is known as the duality principle.

Table 3.5: Basic Identities of Boolean Algebra

Identity Name	AND Form	OR Form
Identity Law	1x = x	0+x=x
Null (or Dominance) Law	0x = x	1+x=1
Idempotent Law	xx = x	x+=1
Commutative Law	x = 0	x+y=y+x
Associative Law	(xy)z = x(yz)	(x+y)+z=x+(y+z)
Distributive Law	x + yz = (x+y)(x+z)	x+(y+z)=xy+xz
Absorption	x(x+y) = x	x+xy=x
DeMorgan's Law
Double Complement Law	=x

The Identity Law states that any Boolean variable ANDed with 1 or ORed with 0 simply results in the original variable. (1 is the identity element for AND; 0 is the identity element for OR.) The Null Law states that any Boolean variable ANDed with 0 is 0, and a variable ORed with 1 is always 1. The Idempotent Law states that ANDing or ORing a variable with itself produces the original variable. The Inverse Law states that ANDing or ORing a variable with its complement produces the identity for that given operation. You should recognize the Commutative Law and Associative Law from algebra. Boolean variables can be reordered (commuted) and regrouped (associated) without affecting the final result. The Distributive Law shows how OR distributes over AND and vice versa.

The Absorption Law and DeMorgan's Law are not so obvious, but we can prove these identities by creating a truth table for the various expressions: If the right-hand side is equal to the left-hand side, the expressions represent the same function and result in identical truth tables. Table 3.6 depicts the truth table for both the left-hand side and the right-hand side of DeMorgan's Law for AND. It is left as an exercise to prove the validity of the remaining laws, in particular, the OR form of DeMorgan's Law and both forms of the Absorption Law.

Table 3-6: Truth Tables for the AND Form of DeMorgan's Law

x	y	(xy)	()			+
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

The Double Complement Law formalizes the idea of the double negative, which evokes rebuke from high school teachers. The Double Complement Law can be useful in digital circuits as well as in your life. For example, let x be the amount of cash you have (assume a positive quantity). If you have no cash, you have . When an untrustworthy acquaintance asks to borrow some cash, you can truthfully say that you don't have no money. That is, even if you just got paid.

One of the most common errors that beginners make when working with Boolean logic is to assume the following:

    Please note that this is not a valid equality!

DeMorgan's Law clearly indicates that the above statement is incorrect; however, it is a very easy mistake to make, and one that should be avoided.

3.2.3 Simplification of Boolean Expressions

The algebraic identities we studied in algebra class allow us to reduce algebraic expressions (such as 10x + 2y - x + 3y) to their simplest forms (9x + 5y). The Boolean identities can be used to simplify Boolean expressions in Example similar fashi: . We apply these identities in the following examples.

At times, the simplification is reasonably straightforward, as in the preceding examples. However, using the identities can be tricky, as we see in this next example.

Example 3.3 illustrates what is commonly known as the Consensus Theorem.

How did we know to insert additional terms to simplify the function? Unfortunately, there is no defined set of rules for using these identities to minimize a Boolean expression; it is simply something that comes with experience. There are other methods that can be used to simplify Boolean expressions; we mention these later in this section.

We can also use these identities to prove Boolean equalities. Suppose we want to prove that . The proof is given in Table 3.7.

Table 3-7: Example Using Identities

Proot	Identity Name
(x+y)(+y) = x+xy+y+yy	Distributive Law
= 0+xy+y+yy	Inverse Law
= 0+xy+y+y	Idempotent Law
= xy+y+y	Identity Law
= y(x+)+y	Distributive Law (and Commutative Law)
= y(1)+y	Inverse Law
= y+y	Identity Law
= y	Idempotent Law

To prove the equality of two Boolean expressions, you can also create the truth tables for each and compare. If the truth tables are identical, the expressions are equal. We leave it as an exercise to find the truth tables for the equality in Table 3.7.

3.2.4 Complements

As you saw in Example 3.1, the Boolean identities can be applied to Boolean expressions, not simply Boolean variables (we treated xy as a Boolean variable and then applied the Idempotent Law). The same is true for the Boolean operators. The most common Boolean operator applied to more complex Boolean expressions is the NOT operator, resulting in the complement of the expression. Later we will see that there is a one-to-one correspondence between a Boolean function and its physical implementation using electronic circuits. Quite often, it is cheaper and less complicated to implement the complement of a function rather than the function itself. If we implement the complement, we must invert the final output to yield the original function; this is accomplished with one simple NOT operation. Therefore, complements are quite useful.

To find the complement of a Boolean function, we use DeMorgan's Law. The OR form of this law states that . We can easily extend this to three or more variables as follows:

Given the function:

Let w = (x + y). Then

Now, applying DeMorgan's Law again, we get:

Therefore, if F(x,y,z) = (x + y + z), then . Applying the principle of duality, we see that .

It appears that to find the complement of a Boolean expression, we simply replace each variable by its complement (x is replaced by ) and interchange ANDs and ORs. In fact, this is exactly what DeMorgan's Law is telling us to do. For example, the complement of . We have to add the parentheses to ensure the correct precedence.

You can verify that this simple rule of thumb for finding the complement of a Boolean expression is correct by examining the truth tables for both the expression and its complement. The complement of any expression, when represented as a truth table, should have 0s for output everywhere the original function has 1s, and 1s in those places where the original function has 0s. Table 3.8 depicts the truth tables for and its complement, . The shaded portions indicate the final results for F and .

Table 3-8: Truth Table Representation for a Function and Its Complement

x	y	z		+	+z	x(+z)
0	0	0	0	1	1	0
0	0	1	0	1	1	0
0	1	0	1	1	0	0
0	1	1	0	1	1	0
1	0	0	0	0	1	1
1	0	1	0	0	1	1
1	1	0	1	1	0	0
1	1	1	0	0	1	1

3.2.5 Representing Boolean Functions

We have seen that there are many different ways to represent a given Boolean function. For example, we can use a truth table or we can use one of many different Boolean expressions. In fact, there are an infinite number of Boolean expressions that are logically equivalent to one another. Two expressions that can be represented by the same truth table are considered logically equivalent. See Example 3.4.

To help eliminate potential confusion, logic designers specify a Boolean function using a canonical, or standardized, form. For any given Boolean function, there exists a unique standardized form. However, there are different "standards" that designers use. The two most common are the sum-of-products form and the product-of-sums form.

The sum-of-products form requires that the expression be a collection of ANDed variables (or product terms) that are ORed together. The function + xyz is in sum-of-products form. The function is not in sum-of-products form. We apply the Distributive Law to distribute the x variable in F₂, resulting in the expression , which is now in sum-of-products form.

Boolean expressions stated in product-of-sums form consist of ORed variables (sum terms) that are ANDed together. The function F1(x,y,z) = (x + y)(x + is in product-of-sums form. The product-of-sums form is often preferred when the Boolean expression evaluates true in more cases than it evaluates false. This is not the case with the function, F₁, so the sum-of-products form is appropriate. Also, the sum-of-products form is usually easier to work with and to simplify, so we use this form exclusively in the sections that follow.

Any Boolean expression can be represented in sum-of-products form. Because any Boolean expression can also be represented as a truth table, we conclude that any truth table can also be represented in sum-of-products form. It is a simple matter to convert a truth table into sum-of-products form, as indicated in the following example.

Table 3.9: Truth Table Representation for the Majority Function

x	y	z	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

To convert the truth table to sum-of-products form, we start by looking at the problem in reverse. If we want the expression x + y to equal 1, then either x or y (or both) must be equal to 1. If xy + yz = 1, then either xy = 1 or yz = 1 (or both). Using this logic in reverse and applying it to Example 3.5, we see that the function must output a 1 when x = 0, y = 1, and z = 1. The product term that satisfies this is (clearly this is equal to 1 when x = 0, y = 1, and z = 1). The second occurrence of an output value of 1 is when x = 1, y = 0, and z = 1. The product term to guarantee an output of 1 is . The third product term we need is , and the last is xyz. In summary, to generate a sum-of-products expression using the truth table for any Boolean expression, you must generate a product term of the input variables corresponding to each row where the value of the output variable in that row is 1. In each product term, you must then complement any variables that are 0 for that row.

Our majority function can be expressed in sum-of-products form as F(x,y,z) = . Please note that this expression may not be in simplest form; we are only guaranteeing a standard form. The sum-of-products and product-of-sums standard forms are equivalent ways of expressing a Boolean function. One form can be converted to the other through an application of Boolean identities. Whether using sum-of-products or product-of-sums, the expression must eventually be converted to its simplest form, which means reducing the expression to the minimum number of terms. Why must the expressions be simplified? A one-to-one correspondence exists between a Boolean expression and its implementation using electrical circuits, as we shall see in the next section. Unnecessary product terms in the expression lead to unnecessary components in the physical circuit, which in turn yield a suboptimal circuit.