Chapter 3: Boolean Expressions

In this chapter, we learn how to write a Boolean expression given a truth table and use Boolean algebra to simplify Boolean equations. De Morgan’s Theorem is a particularly powerful tool in digital design, which explains that the complement of the product of all the term is equal to the sum of the complement of each term.

Objectives

By the end of this chapter you should be able to:

• Explain how to derive a Boolean equation from any truth table.
• Express a Boolean equation for any truth table by summing each of the minterms for the output.
• Understand how to use Boolean algebra to simplify equations.
• Demonstrate De Morgan’s Theorem to simplify a Boolean equation.

3.1 Boolean Equations

A Boolean equation is a functional specification of outputs in terms of inputs, which are expressed as a logical statement that is either TRUE or FALSE. The following figure exemplifies a functional specification with two inputs A and B and the output Y.

Fig. 3‑1. Functional specification with two inputs A and B and the output Y

Let’s assume that the functional specification of the above figure can be expressed as the following truth tables:

Fig. 3‑2. Boolean Equations with Truth Tables

In the first truth table, the output Y is always equal to the input B regardless of the input A. We can simplify the Boolean equation with the truth table, such as .

In the second truth table, the output Y produces TRUE if only if both two inputs A and B are TRUE. Either input A or B is FALSE, the output Y is False. Here, the output Y values are equivalent to the AND operation with two inputs A and B. We can simplify the Boolean equation with the truth table, such as .

In the last truth table, the output Y is always TRUE regardless of two inputs A and B. We can simplify the Boolean equation with the truth table, such as .

3.2 Boolean Algebra

In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0, respectively. You can simplify the Boolean equations using a variety of axioms and theorems. Like the regular algebra, the Boolean algebra has numerical operations, but it is simpler than the regular algebra because valuables have only two values, i.e. 1 or 0. The main operations of Boolean algebra are the AND operation, the OR operation and the negative or NOT operation.

Boolean Axioms and Theorems

Table 3-1 summarizes the Boolean axioms with its duality, where ANDs and ORs, 0’s and 1’s are interchanged.

Table 3‑1. Boolean Axioms with Its Duality

1. Since the Boolean algebra has the binary field, the value A will be 0 if the value A is not 1. If the value A is not 0, the value A will be 1. (2) The negative or NOT operation can be denoted as a bar over the variable. The negative operation is equivalent to the complement or inverse of the variable.

The identify theorem exists in the Boolean algebra. A variable ANDed with 1 is always equal to itself. This operation executes in AND gate, as follows:

• A = 0 ANDed with 1 equal to Y = 0,
• A = 1 ANDed with 1 equal to Y = 1.

In a similar manner, A variable Ored with 0 is always equal to itself. This operation executes in OR gate, as follows:

• A = 1 Ored with 0 equal to Y = 1,
• A = 0 Ored with 0 equal to Y = 0.

The Fig. 3-3 visualizes the identify theorem.

Fig. 3‑3. Identify Theorem

The null element theorem exists in the Boolean algebra. A variable ANDed with 0 is always equal to 0. This operation executes in AND gate, as follows:

• A = 1 ANDed with 0 equal to Y = 0,
• A = 0 ANDed with 0 equal to Y = 0.

In a similar manner, A variable Ored with 1 is always equal to 1. This operation executes in OR gate, as follows:

• A = 1 Ored with 1 equal to Y = 1,
• A = 0 Ored with 1 equal to Y = 1.

The Fig. 3-4 visualizes the null element theorem.

Fig. 3‑4. Null Element Theorem

The idempotency theorem exists in the Boolean algebra. A variable ANDed with itself is always equal to the variable. This operation executes in AND gate, as follows:

• A = 1 ANDed with itself (1) equal to Y = 1
• A = 0 ANDed with itself (0) equal to Y = 0

In a similar manner, A variable Ored with itself is always equal to the variable. This operation executes in OR gate, as follows:

• A = 1 Ored with itself (1) equal to Y = 1,
• A = 0 Ored with itself (0) equal to Y = 0.

The Fig. 3-5 visualizes the idempotency theorem.

Fig. 3‑5. Idempotency Theorem

The complement theorem exists in the Boolean algebra. A variable ANDed with its complement is always equal to 0. This operation executes in AND gate, as follows:

• A = 1 ANDed with its complement () is always equal to 0,
• A = 0 ANDed with its complement () is always equal to 0.

In a similar manner, A variable Ored with its complement is always equal to 1. This operation executes in OR gate, as follows:

• A = 1 Ored with its complement () is always equal to 1,
• A = 0 Ored with its complement () is always equal to 1.

The Fig. 3-6 visualizes the complement theorem.

Fig. 3‑6. Complement Theorem

The double complement law exists in the Boolean algebra. The double complement (negation) of a variable is always equal to the variable. This operation executes with by connecting two NOT gates serially, as follows:

• A = 0 double complement is always equal to 0,
• A = 1 double complement is always equal to 1.

The Fig. 3-7 visualizes the double complement law.

Fig. 3‑7. Double Complement Law

The commutative law exists in the Boolean algebra.

• ; A ANDed with B is equal to B ANDed with A
• ; A Ored with B is equal to B Ored with A

The associative law exists in the Boolean algebra. When we execute AND or OR gates with more than 2 inputs, the order doesn’t matter.

• ; A ANDed with BC is equal to C ANDed with AB.
• ; A Ored with (B+C) is equal to C Ored with (A+B).

The distributive law exists in the Boolean algebra.

• ; A ANDed with (B+C) is equal to AB Ored with AC.

The absorption law exists in the Boolean algebra.

With the distributive law, the left-hand side of the equation can be expressed as follows:
, where the round bracket is further simplified as due to the identify theorem. A variable A ANDed with 1 is equal to A , which is identical to the right-hand side of the above equation.

With the distributive law, the left-hand side of the equation can be expressed as follows:
, where is equal to () due to the idempotency theorem. Now the above equation is expressed as . You can also simplify the equation by drawing the truth table, as follows:

Exercises

Simplifying the following Boolean Equations:

Answer:

(2)

Answer:

(3)

Answer:

3.3 De Morgan’s Theorems

De Morgan’s Theorems are a pair of transformation rules that are both valid rules of inference. The rules can be expressed as:

• The complement of the intersection of two sets is the same as the union of their complements; and
• the complement of the union of two sets is the same as the intersection of their complements,

where the intersection and union operations are expressed as AND and OR gates, respectively in the digital logic systems. In the Boolean algebra, these are written formally as follows:

Bubble pushing is a technique to apply De Morgan’s theorem directly to the logic diagram. There are two steps to use the bubble pushing, as follows:

• Change the logic gate (AND to OR and OR to AND).
• Add bubbles to the inputs and outputs where there were none, and remove the original bubbles.

For example, the backward bubble pushing is applied to NAND gate, pushing the bubble in the output side back to input side. After changing AND gate to OR gate, add bubbles to two inputs A and B, as shown in the following figures:

Fig. 3‑8. Backward Bubble Pushing

The forward bubble pushing is applied to the logic gate which has the bubbles at all the inputs, by pushing the bubbles at the input side A & B to the output side Y. After changing OR gate to AND gate, add a bubble to the output Y, as shown in the following figures:

Fig. 3‑9. Forward Bubble Pushing

There are rules for the bubble pushing, as listed:

• Begin at output, then work toward inputs
• Push bubbles on final output back
• Draw gates in a form so bubbles cancel

There are four inputs, A, B, C, and D in Fig. 3-10. Two inputs A & B are fed into NOR gate. It’s output and the input C are fed into a NAND gate. The output of NAND gate and the input D are fed into another NAND gate, and those two inputs produce the output Y.

Fig. 3‑10. Bubble Pushing Example

The last NAND gate can be changed with the backward bubble pushing, as shown in Fig. 3-11.

• Body changes from AND to OR gate.
• Adds bubbles to inputs. No bubble at the output.

Fig. 3‑11. Bubble Pushing Example – No Output Bubble-1

Two bubbles, i.e. the output bubble of NAND gate and the input bubble produced with backward, are now put in the same line. These two bubbles canceled each other, because the double complement of a variable is always equal to the variable.

NOR gate with two inputs A & B can be changed with De Morgan’s Theorems, as shown in Fig. 3-12:

• Body changes from OR to AND gate.
• Adds bubbles to inputs. No bubble at the output.

Fig. 3‑12. Bubble Pushing Example – No Output Bubble-2

From the above figure, we can draw the following Boolean equation: . Note that we will get the Boolean equation without De Morgan’s theorems.

Exercise

1. There are five inputs, A, B, C, D, and E with four NAND gates, as shown in Fig. 3-13:

Fig. 3‑13. Quiz 1 Figure

• NAND_1 gate has two inputs A and B. NAND_2 gate has two inputs C and D.
• The two outputs of NAND gates fed into NAND_3 gate.
• The out of the NAND_3 gate and input E fed into the NAND_4 gate, produce the output Y.

Simply the logic gates with De Morgan’s theorems and write the corresponding Boolean equation.

1. There are five inputs, A, B, C, D, and E with three NAND gates and one NOR gate, as shown in Fig. 3-14:

Fig. 3‑14. Quiz 2 Figure

• NAND_1 gate has two inputs A and B. NAND_2 gate has two inputs C and D.
• The two outputs of NAND gates fed into NAND_3 gate.
• The out of the NAND_3 gate and input E fed into the NOR_4 gate, produce the output Y

Simply the logic gates with De Morgan’s theorems and write the corresponding Boolean equation.

1. There are four inputs, A, B, C, and D with three NAND gates, as shown in Fig. 3-15:

Fig. 3‑15. Quiz 3 Figure

• One NAND gate has two inputs A and B. Another NAND gate has two inputs C and D.
• The two outputs of NAND gates fed into the other NAND gate, and produce output Y.

Simply the logic gates with De Morgan’s theorems and write the corresponding Boolean equation.

1. Simplify the following Boolean expression to a minimum number of literals:

Answer)