CS 352 Lecture 7 – Karnaugh Maps
Dear students,
We start today with a couple more exercises on building circuit diagrams. Let’s do these one a time. Write your diagram down on paper, and then we’ll construct it together up front:
As we complete each of these, we will tally up how many transistors each requires. How many transistors does an AND gate require? An OR gate? A NOT gate?
We’ve gained some practice at converting boolean expressions to circuits. But suppose you’re sitting in your basement office at the hardware company you’re interning at, and your boss hands you a truth table and says, “Here, make this.” How do you turn a truth table into a boolean expression? This isn’t such a crazy scenario. Sometimes you just know how a circuit is supposed to behave based on its inputs.
One means of conversion is construct the sum of products, or what we’ll call the or of the ands. First draw out your truth table. Let’s use this one as an example:
A  B  Y 

0  0  1 
0  1  0 
1  0  1 
1  1  1 
Each of these rows can be described with a minterm, which is just the ANDing of the input columns:
A  B  Y  minterm 

0  0  1 
!A && !B

0  1  0 
!A && B

1  0  1 
A && !B

1  1  1 
A && B

The sum of products or the or of the ands is just the ORing of all the minterms that evaluate to 1 for a given circuit. In this case, there are three minterms that are 1, and the resulting boolean expression is:
(!A && !B)  (A && !B)  (A && B)
Let’s try creating sums of products for a couple more circuts:
A  B  Y 

0  0  0 
0  1  1 
1  0  1 
1  1  0 
A  B  C  Y 

0  0  0  0 
0  1  0  1 
1  0  0  1 
1  1  0  1 
0  0  1  0 
0  1  1  1 
1  0  1  0 
1  1  1  0 
However, not every boolean expression derived using the sum or products is as simple as can be. When you’re building a hardware component, you’d generally like to use as few transistors as possible. We will discuss Karnaugh maps (or Kmaps) as a way to simplify expressions and the hardware that captures their behavior. We’ll create Karnaugh maps for:
 The first table above.
 The second table above.
 The third table above.
 The expression
!A && B && C  !A && B && !C
.  The expression
!A && !B && !C  A && !B
.
Here’s your TODO list:
 Watch the videos below on constructing Karnaugh maps.
 On a quarter sheet, draw Karnaugh maps and show the resulting simplifications of these two expressions:
A && C  !A && !B && C !A && !B  !A && B && !C  !(A  !C)
See you next class!