• Boolean Expressions, Logic Diagrams and Truth Tables 63

Figure 3.9b shows the terms combined in an OR gate.

Example 3.4

Logic Diagram of

P _ QR_S_ _ S_T

R

Q

RS

T

S

QRS

R

Q

S

T

ST

QRS

_ _

3.10a shows how the circuit inputs are first combined in two OR gates. We do this first

because the ORs are in parentheses. In Figure 3.10b, each of these functions is combined

in an AND gate, according to the normal order of precedence. The AND outputs

are combined in a final OR function, as shown in Figure 3.10c.

FIGURE 3.10

Example 3.4

Logic Diagram for X _

(W _ Z _Y)V_ _ (W_ _V)Y_

W

W

Z

V

b. Combine with ANDs (order of precedence)

W

W

Z

Y

Y

V

W

W

Y

V

Y

V

W

W

_ Y

_ V

W _ Z

(W _

Z _ Y)V

_ Y

(W V)Y

_

64 C H A P T E R 3 • Boolean Algebra and Combinational Logic

❘❙❚ EXAMPLE 3.5 Use DeMorgan’s theorem to modify the Boolean equation in part 1 of Example 3.4 so that

there is no bar over any group of variables. Redraw Figure 3.9b to reflect the change.

Figure 3.11a shows the modified logic diagram. The levels of gating could be further

reduced from three to two (not counting input inverters) by “multiplying through” the

parentheses to yield the expression:

P _ QR_ _ QS_ _ S_T

Figure 3.11b shows the logic diagram for this form. We will examine this simplification

procedure more formally in a later section of this chapter.

FIGURE 3.11

Example 3.5: Reworking Figure 3.9b

Q(R

Q

R

T

S

R

S

QS

ST

_ S)

P _ QR _ QS_ ST

(R_ S)

❘❙❚

There are two basic ways to find a truth table from a logic diagram. We can examine the

output of each gate in the circuit and develop its truth table. We then use our knowledge of

gate properties to combine these intermediate truth tables into the final output truth table.

Alternatively, we can develop a Boolean expression for the logic diagram and by examining

the expression fill in the truth table in a single step. The former method is more thorough

and probably easier to understand when you are learning the technique. The latter

method is more efficient, but requires some practice and experience. We will look at both.

Examine the logic diagram in Figure 3.12. Since there are three binary inputs, there

will be eight ways those inputs can be combined. Thus, we start by making an 8-line truth

table, as in Table 3.1.

FIGURE 3.12

Logic Diagram for AB _ C

A AB

B

C

The OR gate output will describe the function of the whole circuit. In order to assess

the OR function, we must first evaluate the AND output. We add a column to the truth table

for the AND gate and look for the lines in the table where both A AND B equal logic 1 (in

this case, the last two rows). For these lines, we write a 1 in the AB column. Next, we look

at the values in column C and the AB column. If there is a 1 in either column, we write a 1

in the column for the final output.

Table 3.1 Truth Table for Figure 3.12

A B C AB AB _ C

0 0 0 0 0

0 0 1 0 1

0 1 0 0 0

0 1 1 0 1

1 0 0 0 0

1 0 1 0 1

1 1 0 1 1

1 1 1 1 1

❘❙❚ EXAMPLE 3.6 Derive the truth table for the logic diagram shown in Figure 3.13.

Example 3.6

Logic Diagram

A

B

column for each input variable and for each term in parentheses, as well as a column for the

final output. Table 3.2 shows the result. For the lines where A OR B is 0, we write a 1 in the

(A_ _ B_) column. Where A OR C is 1, we write a 1 in the (A _ C) column. For the lines

where there is a 1 in both the (A_ _ B_) AND (A _ C) columns, we write a 1 in the final output

column.

0 0 0 1 0 0

0 0 1 1 1 1

0 1 0 1 0 0

0 1 1 1 1 1

1 0 0 1 1 1

1 0 1 1 1 1

1 1 0 0 1 0

1 1 1 0 1 0

❘❙❚

Another approach to finding a truth table involves analysis of the Boolean expression

of a logic diagram. The logic diagram in Figure 3.14 can be described by the Boolean expression

Y _ A_BC _ A_ C_ _ B_D_.

A

B

D

Y

Logic Diagram

0 0 0 0 1 A_ C_, B_ D_

0 0 0 1 1 A_ C_

0 0 1 0 1 B_ D_

0 0 1 1 0

0 1 0 0 1 A_ C_

0 1 0 1 1 A_ C_

0 1 1 0 1 A_BC

0 1 1 1 1 A_BC

1 0 0 0 1 B_ D_

1 0 0 1 0

1 0 1 0 1 B_ D_

1 0 1 1 0

1 1 0 0 0

1 1 0 1 0

1 1 1 0 0

1 1 1 1 0

❘❙❚ SECTION 3.16 REVIEW PROBLEM

3.2 Find the truth table for the logic diagram shown in Figure 3.15.

A

B

Y

FIGURE 3.15

Section Review Problem 3.2

We can examine the Boolean expression to determine that the final output of the circuit

will be HIGH under one of the following conditions:

1. A _ 0 AND B _ 1 AND C _ 1;

2. A _ 0 AND C _ 0;

3. B _ 0 AND D _ 0.

All we have to do is look for these conditions in the truth table and write a 1 in the output

column whenever a condition is satisfied. Table 3.3 shows the result of this analysis

with each line indicating which term, or terms, contribute to the HIGH output.

3.2 • Sum-of-Products and Product-of-Sums Forms 67

3.2 Sum-of-Products and Product-of-Sums Forms

Product term A term in a Boolean expression where one or more true or complement

variables are ANDed (e.g., A_ C_).

once in true or complement form (e.g., A_ B_ C_; A B_ C_).

variables are ORed (e.g., A_ _ B _ D_).

once, in true or complement form (e.g., (A_ _ B_ _ C); (A _ B_ _ C)).

terms are summed (ORed) together (e.g., A_ B C_ _ A_ B_ C _ A B C).

are multiplied (ANDed) together (e.g., (A_ _ B_ _ C)(A _ B_ _ C_)(A_ _ B_ _ C_)).

input variable is available along a continuous conductor called a bus.

Suppose we have an unknown digital circuit, represented by the block in Figure 3.16.

All we know is which terminals are inputs, which are outputs, and how to connect the

power supply. Given only that information, we can find the Boolean expression of the

output.

in binary order and reading the output for each one. Suppose the unknown circuit in Figure

3.16 yields the truth table shown in Table 3.4.

The truth table output is HIGH for three conditions:

1. When A AND B AND C are all LOW, OR

2. When A is LOW AND B AND C are HIGH, OR

3. When A is HIGH AND B AND C are LOW.

K E Y T E R M S

Digital Circuit with

Unknown Function

Table 3.4 Truth

Table for Figure 3.19

0 0 0 1

0 1 0 0

1 0 0 1

1 1 0 0

Each of those conditions represents a minterm in the output Boolean expression. (A

minterm is a product term (AND term) that includes all variables (A, B, C) in true or complement

form.) The minterms are:

1. A_ B_ C_

2. A_ B C

3. A B_ C_

Since condition 1 OR condition 2 OR condition 3 produces a HIGH output from the

circuit, the Boolean function Y consists of all three minterms summed (ORed) together, as

follows:

This expression is in a standard form called sum-of-products (SOP) form. Figure

3.17 shows the equivalent logic circuit.

FIGURE 3.17

Logic Circuit for Y _A_ B_ C_ _A_BC _A B_ C_

The inputs A, B, and C and their complements are shown in bus form. Each variable

is available, in true or complement form, at any point along a conductor. This is a useful,

uncluttered notation for circuits that require several of the input variables more than once.

We can derive an SOP expression from a truth table as follows:

1. Every line on the truth table that has a HIGH output corresponds to a minterm in

the truth table’s Boolean expression.

2. Write all truth table variables for every minterm in true or complement form. If a

variable is 0, write it in complement form (with a bar over it); if it is 1, write it

in true form (no bar).

3. Combine all minterms in an OR function.

❘❙❚ EXAMPLE 3.7 Tables 3.5 and 3.6 show the truth tables for the Exclusive OR and the Exclusive NOR functions.

Derive the sum-of-products expression for each of these functions and draw the logic

diagram for each one.

N O T E

Truth Table

0 0 0

1 0 1

Truth Table

0 0 1

1 0 0

XOR function is A _ B _ A_B _ AB_. Figure 3.18 shows the logic diagram for this

equation.

A B

Example 3.7

SOP Form of XOR Function

A B

Example 3.7

SOP Form of XNOR Function

We can also find the Boolean function of a truth table in product-of-sums (POS)

form. The product-of-sums form of a Boolean expression consists of a number of maxterms

(i.e., sum terms (OR terms) containing all variables in true or complement form)

that are ANDed together. To find the POS form of Y, we will find the SOP expression for Y_

and apply DeMorgan’s theorems.

Recall DeMorgan’s theorems:

x_____y_____z_ _ x_ y_ z_

x__y__z_ _ x_ _ y_ _ z_

When the theorems were introduced, they were presented as two-variable theorems,

but in fact they are valid for any number of variables.

XNOR: The product terms for this function are: A_ B_ and AB. The SOP form of the XNOR

function is A _ B _ A_ B_ _ AB. The logic diagram in Figure 3.19 represents the XNOR

function. ❘❙❚

70 C H A P T E R 3 • Boolean Algebra and Combinational Logic

Let’s reexamine Table 3.4. To find the sum-of-products expression for Y, we wrote a

minterm for each line where Y _ 1. To find the SOP expression for Y_, we must write a

minterm for each line where Y _ 0. Variables A, B, and C must appear in each minterm, in

true or complement form. A variable is in complement form (with a bar over the top) if its

value is 0 in that minterm, and it is in true form (no bar) if its value is 1.

We get the following minterms for Y_:

Thus, the SOP form of Y_ is

To get Y in POS form, we must invert both sides of the above expression and apply De-

Morgan’s theorems to the righthand side.

Y _ Y _ A_ B_ C _ A_ B C_ _ A B_ C _ A B C_ _ A B C

_ (A_ B_ C)(A_ B C_)(A B_ C)(A B C_)(A B C)

_ (A _ B _ C_)(A _ B_ _ C)(A_ _ B _ C_)(A_ _ B_ _ C)(A_ _ B_ _ C_)

This Boolean expression can be implemented by the logic circuit in Figure 3.20.

We don’t have to go through the whole process outlined above every time we want to

find the POS form of a function. We can find it directly from the truth table, following the

Logic Circuit for Y _ (A _ B _ C_) (A _ B_ _ C)(A_ _ B _ C_) (A_ _ B_ _ C)(A_ _ B_ _ C_)

procedure summarized below. Use this procedure to find the POS form of the expression

given by Table 3.4. The terms in this expression are the same as those derived by DeMorgan’s

theorem.

3.2 • Sum-of-Products and Product-of-Sums Forms 71

Table 3.7 Truth Table for Example 3.8 (with minterms

and maxterms)

0 0 0 0 1 A_ B_ C_ D_

0 0 0 1 1 A_ B_ C_ D

0 0 1 0 0 A _ B _ C_ _ D

0 0 1 1 1 A_ B_ C D

0 1 0 0 0 A _ B_ _ C _ D

0 1 0 1 0 A _ B_ _ C _ D_

0 1 1 0 0 A _ B_ _ C_ _ D

0 1 1 1 0 A _ B_ _ C_ _ D_

1 0 0 0 1 A B_ C_ D_

1 0 0 1 0 A_ _ B _ C _ D_

1 0 1 0 1 A B_ C D_

1 0 1 1 0 A_ _ B _ C_ _ D_

1 1 0 0 1 A B C_ D_

1 1 0 1 1 A B C_ D

1 1 1 0 1 A B C D_

1 1 1 1 0 A_ _ B_ _ C_ _ D_

Deriving a POS expression from a truth table:

1. Every line on the truth table that has a LOW output corresponds to a maxterm in

the truth table’s Boolean expression.

2. Write all truth table variables for every maxterm in true or complement form. If

a variable is 1, write it in complement form (with a bar over it); if it is 0, write it

in true form (no bar).

3. Combine all maxterms in an AND function.

Note that these steps are all opposite to those used to find the SOP form of

the Boolean expression.

❘❙❚ EXAMPLE 3.8 Find the Boolean expression, in both SOP and POS forms, for the logic function represented

by Table 3.7. Draw the logic circuit for each form.

N O T E

Solution All minterms (for SOP form) and maxterms (for POS form) are shown in the

last two columns of Table 3.5.

_ A B C_ D _ A B C D_

(A _ B_ _ C_ _ D_)(A_ _ B _ C _ D_)(A_ _ B _ C_ _ D_)

(A_ _ B_ _ C_ _ D_)

The logic circuits are shown in Figures 3.21 and 3.22.

Example 3.8

POS Form

FIGURE 3.21

Example 3.8

SOP Form

❘❙❚

❘❙❚ SECTION 3.2 REVIEW PROBLEM

3.3 Find the SOP and POS forms of the Boolean functions represented by the following

truth tables.

a. A B C Y b.

0 0 0 0

0 1 0 0

1 0 0 1

1 1 0 0

0 0 0 1

0 1 0 0

1 0 0 1

1 1 0 1

The main reason to learn Boolean algebra is to learn how to minimize the number of logic

gates in a network. Boolean expressions with many terms, such as those represented by the

logic diagrams in Figures 3.21 and 3.22, are seldom in their simplest form. It is often possible

to apply some techniques of Boolean algebra to derive a simpler form of expression

that requires fewer gates to implement.

For example, the logic circuit in Figure 3.21 requires eight 4-input AND gates and

an 8-input OR gate. Using Boolean algebra, we can reduce its Boolean expression to

a 4-input OR. You will use a simplification technique for this example in an end-ofchapter

problem. In the meantime, let us examine some basic rules of Boolean algebra.

Commutative, Associative, and Distributive Properties

to its operands in any order without affecting the result. For example, addition

is commutative (a _ b _ b _ a), but subtraction is not (a _ b _ b _ a).

Associative property Amathematical function is associative if its operands can be

grouped in any order without affecting the result. For example, addition is associative

((a _ b) _ c _ a _ (b _ c)), but subtraction is not ((a _ b) _ c _ a _ (b _c)).

Distributive property Full name: distributive property of multiplication over addition.

The property that allows us to distribute (“multiply through”) an AND

across several OR functions. For example, a(b _ c) _ ab _ ac.

AND and OR functions are both commutative and associative. The commutative property

states that AND and OR operations are independent of input order. For inputs x and y,

Theorem 1: xy _ yx

and

The associative property allows us to perform several two-input AND or OR functions in

any order. In other words,

Theorem 3: (xy)z _ x(yz) _ (xz)y

and

K E Y T E R M S

The distributive property allows us to “multiply through” an AND function across

several OR functions. For example,

Theorem 5: x(y _ z) _ xy _ xz

and

Figure 3.23 shows the logic gate equivalents of these theorems.

A

AC

BC

BD

B C D

B

C

Y

Y