A Worked Example

Problem:

 Given a Boolean expression:

F = AB + CD

construct a logic circuit design. The problem is that in your box of logic gates, there are numerous OR and NOT gates but only a single AND gate. What do you do?

 

Clue:

Convert the expression F from a sum of products to a product of sums representation.

 

Approach:

We will be using  DeMorgan's Law (sometimes also called DeMorgan's Laws, with an "s"):

(ab)' = a' + b'
(a+b)' = a'b'

Note that

F = AB + CD

is the sum of two terms, which fits the pattern of the right-hand term of the first part of the law

a' + b'

from DeMorgan's Laws above. To apply DeMorgan's here, we need only substitute AB for a' and CD for b', and also substitute their negations, (AB)' for a'' = a and (CD)' for b'' = b.

So, starting with the equation for F:

F = AB + CD

and also with the first part of DeMorgan's Law:

(ab)' = a' + b'

our substitutions yield:

F = ((AB)' (CD)')'

Examining this intermediate result, we see that once again a pattern from DeMorgan's Law:

(ab)' = a' + b'

is used, specifically the negation of the product of two terms on the left-hand side of the first law. This (ab)' pattern is used twice in this new statement of F, once in the term (AB)' and once in  the term (CD)'. Just by chance, in the first use of this pattern,  A really does correspond to a, and B really does correspond to b. Starting with the pattern of the first DeMorgan's Law:

(ab)' = a' + b'

we then make the substitution and get:

(AB)' = A' + B'

Substituting the right-hand side A' + B of this, which can be redrawn as  (A' + B') after parenthesizing and recoloring, for (AB)' in the latest statement of F:

F = ((AB)' (CD)')'

gives us:

F = ((A' + B')(CD)')'

Similarly substituting (C' + D') for (CD)' gives us:


F
= ((A' + B')(C' + D'))'

 

This statement of F has but one AND operator, and two OR operators, so that the problem of setting up F to meet our hardware specifications has been solved.

At this point it is a good idea to check our work. See the following truth table to see that the two colored columns, representing F and our new restatement of it, match exactly.

Side Note: Do not be fooled by the fact that we are using lower case a and b in the statement of DeMorgan's Law, and upper case A and B in the statement of F. The particular variable names used have nothing whatsoever to do with the problem, and in particular a has nothing to do with A, nor does b with B. For example, we could have said that 

F = (Wallawalla)(Mattawa) + (Foobar)(Aspen)

or stated  DeMorgan's Law as:

(XY)' = X' + Y'
(X+Y)' = X'Y'

 


 

Truth Table to Compare F = AB + CD with ((A' + B')(C' + D'))'

A

B

C

D

A'

B'

C'

D'

A'+B'

C'+D'

(A'+B')(C'+D')

((A'+B')(C'+D'))'

AB

CD

F

1

1

1

1

0

0

0

0

0

0

0

1

1

1

1

1

1

1

0

0

0

0

1

0

1

0

1

1

0

1

1

1

0

1

0

0

1

0

0

1

0

1

1

0

1

1

1

0

0

0

0

1

1

0

1

0

1

1

0

1

1

0

1

1

0

1

0

0

1

0

0

1

0

1

1

1

0

1

0

0

1

0

1

1

1

1

0

0

0

0

1

0

0

1

0

1

1

0

1

1

1

0

0

0

0

1

0

0

0

0

1

1

1

1

1

1

0

0

0

0

0

1

1

1

1

0

0

0

1

0

0

1

0

1

1

0

1

1

0

1

0

0

1

1

1

1

0

0

0

0

0

1

0

1

1

0

1

0

1

1

1

0

0

0

0

0

1

0

0

1

0

1

1

1

1

1

0

0

0

0

0

0

1

1

1

1

0

0

1

0

0

1

0

1

1

0

0

1

0

1

1

0

1

1

1

1

0

0

0

0

0

0

0

1

1

1

1

0

1

1

1

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

0

0

0

0

 

Apply the logic gates:

 

The last step in working the problem is to translate the new representation of F into a logic diagram with OR, NOT, and AND gates:

F = ((A' + B')(C' + D'))'

For the drawing Smartdraw Professional Plus v. 6.2 and its Electrical Engineering/Logic add-in library were used, with the resulting screen image captured by Snagit from Techsmith.com, and optimized for the Web by Photoshop7. The title graphic was done in Photoshop 7.

 

Copyright © 2003 Crystal Sloan and Dr. Yul Williams
Page Design by Crystal Sloan 2003