**Review:**

In Boolean logic, each term can be in one of two states:

logic level one or logic level zero

A*B means A AND B

If both A and B are at a logic one level, the output A*B is at a logic one level.

In digital logic, the AND gate performs the operation A*B. See Figure One

A + B means A OR B

If either A or B is at a logic one level, the output A + B is at a logic one level. See Figure One

A’ means NOT A

If A is at logic level 1, NOT A is at logic level 0.

A cannot equal NOT A.

The NOT gate is usually called an inverter. See Figure One

(A*B)’ means NOT(A AND B)

If either A or B is at logic level zero, the output (A*B)’ is at logic level one. In Digital Electronics, this function is performed by the NAND gate shown in Figure two.

(A + B)’ means NOT(A + B)

If either A or B is at logic level one, the output (A + B)’ is at logic level zero. In Digital Electronics, this function is performed by the NOR gate shown in Figure two.

DeMorgan’s Law

DeMorgan’s Law states that

a’*b’ = (a + b)’

We can prove that this law is correct via truth tables.

Lets consider

a’*b’ = 1

The output is 1 whenever a’ = 1 and b’ = 1

By definition, the output is 1 only when a = 0 and b = 0

Here is the truth table for a’*b’ = 1

a = 0, b = 0, a’*b’ = 1

a = 0, b = 1, a’*b’ = 0

a = 1, b = 0, a’*b’ = 0

a = 1, b = 1, a’*b’ = 0

Now lets consider

(a + b)’ = 1

The output is one only when a = 0 and b = 0

Here is the truth table for (a + b)’ = 1

a = 0, b = 0, (a + b)’ = 1

a = 0, b = 1, (a + b)’ = 0

a = 1, b = 0, (a + b)’ = 0

a = 1, b = 1, (a + b)’ = 0

DeMorgan’s Law also states that

a’ + b’ = (a*b)’

**Problem 1:**

Generate the truth table and design a circuit that satisfies the following Boolean equation:

A*B + A’B + A’B’ = 1

**Solution:**

*Truth table for the expression*

*A*B + A’B + A’B’ = 1 Expression 1a*

If you already know how to create a truth table for expression 1a, you can go directly to the section

labeled ‘Circuit design for expression A*B + A’B + A’B’ = 1.’

Lets create the truth table

If A = 0 and B = 0 then

A*B = 0*0 = 0

A’*B = 1*0 = 0

A’*B’ = 1*1 = 1

Substituting these values into expression 1a, we get

A*B + A’*B + A’*B’ =

0 + 0 + 1 = 1

Hence, the first line of our truth table is

A = 0, B = 0, Output = 1

If A = 0 and B = 1 then

A*B = 0*1 = 0

A’*B = 1*1 = 1

A’*B’ = 1*0 = 0

Substituting these values into expression 1a, we get

A*B + A’*B + A’*B’ =

0 + 1 + 0 = 1

Hence the second line of our truth table is

A = 0, B = 1, Output = 1

If A = 1 and B = 0

A*B = 1*0 = 0

A’*B = 0*0 = 0

A’*B’ = 0*1 = 0

Substituting these values into expression 1a, we get

A*B + A’*B + A’*B’ =

0 + 0 + 0 = 0

Hence the third line of our truth table is

A = 1, B = 0, Output = 0

If A = 1 and B = 1

A*B = 1*1 = 1

A’*B = 0*1 = 0

A’*B’ = 0*0 = 0

Substituting these values into expression 1a, we get

A*B + A’*B + A’*B’ =

1 + 0 + 0 = 1

Hence the fourth line of our truth table is

A = 1, B = 1, Output = 1

Our complete truth table is

A = 0, B = 0, Output = 1

A = 0, B = 1, Output = 1

A = 1, B = 0, Output = 0

A = 1, B = 1, Output = 1

*Circuit design for expression A*B + A’B + A’B’ = 1*

When designing a circuit, we are interested in the rows of the truth table that show an output of 1. Expression 1a shows that we have three AND gates

A*B

A’*B

A’*B’

and one three input OR gate

A*B + A’B + A’B’

Note that when designing a circuit, we start with the individual terms of the expression and then consider the complete expression.

One of the primary objectives in circuit design is to design the circuit with the least amount of components. We can eliminate gates from this circuit by first simplifying the boolean expression and then designing the circuit in accordance with the new simplified expression.

A*B + A’*B + A’*B’ =

B*(A + A’) + A’*B’ =

B*1 + A’*B’ =

B + A’*B’ Expression 1b

So expression 1b contains two terms

B + A’*B’ = 1

Using DeMorgan’s Law, we have

B + (A + B)’ = 1 Expression 1c

The circuit for expression 1c is shown in figure three. Note that the initial expression required four gates and this expression only requires two gates.

**Problem 2:**

Design a circuit using the following truth table

a = 0, b = 0 c = 0 output = 1

a = 0, b = 0 c = 1 output = 0

a = 0, b = 1 c = 0 output = 0

a = 0, b = 1 c = 1 output = 1

a = 1, b = 0 c = 0 output = 0

a = 1, b = 0 c = 1 output = 1

a = 1, b = 1 c = 0 output = 1

a = 1, b = 1 c = 1 output = 1

**Solution:**

Since we have three single letter inputs (a, b and c) the following analogy does not use the asterisk to indicate the AND function.

Hence

ab = a AND b

Likewise

a’b’ = a’ AND b’

Lets put all the terms where the output is 1 in a single equation

a’b’c’ represents row one of the truth table

a’bc represents row four of the truth table

ab’c represents row 6 of the truth table

abc’ represents row 7 of the truth table

abc represents row 8 of the truth table

So our initial boolean expression is

a’b’c’ + a’bc + ab’c + *abc’ + abc* = 1 Expression 2a

The fourth and fifth terms of expression 2a can be simplified.

abc’ + abc = ab

Expression 2a becomes

a’b’c’ + a’bc + ab’c + *ab* = 1 Expression 2b

We can simplify the second and third terms of expression 2b

a’bc + ab’c =

b(a’b + ab’)

Expression 2b becomes

a’b’c’ + *b(a’b + ab’)* + ab = 1 Expression 2c

a’b’c’ + *b(a’b + ab’ + a)* = 1 Expression 2d

a’b’c’ + b(a’b + *ab’ + a)* = 1 Expression 2e

We know that

ab’ + a = a(b’+1) = a

Implementing this in Expression 2e yields

a’b’c’ + b(a’b + *a*) = 1 Expression 2f

Multiplying by b we get

a’b’c’ + *ba’b + ba* = 1 Expression 2g

We know that bb = b.

Therefore expression 2g becomes

a’b’c’ + *ba’ + ba* = 1 Expression 2h

a’b’c’ + *b(a’ + a)* =1 Expression 2i

a’b’c’ + b = 1 Expression 2j

According to DeMorgan’s Law

a’b’c’ = (a + b + c)’

So expression 2j becomes

(a + b + c)’ + b = 1 Expression 2h

Hence, this circuit requires two gates. The circuit is shown in figure three.

**Problem 3:**

Design a circuit using the following truth table

a = 0, b = 0 c = 0 output = 0

a = 0, b = 0 c = 1 output = 0

a = 0, b = 1 c = 0 output = 0

a = 0, b = 1 c = 1 output = 1

a = 1, b = 0 c = 0 output = 0

a = 1, b = 0 c = 1 output = 0

a = 1, b = 1 c = 0 output = 1

a = 1, b = 1 c = 1 output = 1

**solution:**

bc + ac + abc = 1 Expression 3a

bc + ac + abc =

c(b + a + ab) = 1 Expression 3b

We know that

a + ab = a(1 + b) = a

Implementing this in expression 3b, we have

c(b + a) = 1 Expression 3c

This circuit requires two gates. The circuit is shown in figure three.

I have a Bachelor of Science in Electrical Engineering along with experience in digital logic design, testing and troubleshooting.

Digital Circuits and Microprocessors

ISBN 0-07-062945-5