Canonical SOP and POS Forms and Karnaugh Maps

Hello students, welcome to Kwickprep. A truth table tells you what a circuit must do, but not how to build it cheaply. Is there a sure method to find the shortest expression? Yes. Today we learn minterms and maxterms, canonical SOP and POS forms, and Karnaugh maps with two, three and four variables.

Before minterms, we need four simple words. A literal is a variable or its complement, such as A or not A. A product term is literals joined by AND, such as A dot not B. A sum term is literals joined by OR, such as A plus not B. Canonical means full form: every term contains every variable exactly once.

Each row of a truth table has one minterm and one maxterm. A minterm is a product term that is one only for its own row, so a zero input gets a bar. For row zero zero, the minterm is not A dot not B, called minterm zero. A maxterm is a sum term that is zero only for its own row, so a one input gets the bar. For row zero one, the maxterm is A plus not B, called maxterm one. Row two gives minterm two, A dot not B. Row three gives maxterm three, not A plus not B.

Let us fix the rules so you never mix them up. For a minterm, a zero input gets a bar, a one stays plain, and we join with AND. For a maxterm, it is the reverse: a one gets a bar, a zero stays plain, and we join with OR. The index is the row's binary number, so row one zero one is index five. Minterm five and maxterm five are complements of each other.

Here is a three variable function F that we will use for the rest of the lesson. F is one in row zero, which is zero zero zero. F is one in row two. F is one in row four. F is one in row five. F is one in row six. In the remaining rows one, three and seven, F is zero.

SOP means sum of products. Canonical SOP is the OR of the minterms of every row where F is one. Here those are rows zero, two, four, five and six. The short form is F equals sigma of zero, two, four, five, six, where sigma means sum. The first term written in full is not A dot not B dot not C, and so on for each row.

POS means product of sums. Canonical POS is the AND of the maxterms of every row where F is zero. Here those are rows one, three and seven. The short form is F equals pi of one, three, seven, where pi means product. Maxterm one, for row zero zero one, is A plus B plus not C. Notice that sigma and pi always use the missing numbers of each other.

Let us see why we need a map. Canonical forms are always correct, but they use too many gates. A Karnaugh map, or K-map, places every minterm in a grid of boxes. The grid is arranged so that side by side boxes differ in only one variable. When two such boxes are both one, that variable drops out, because A dot B plus A dot not B is just A.

Let us start with two variables, so the map has four boxes. For F equals sigma of one, two, three, we put a one in boxes one, two and three. The top row has a zero in box zero and a one in box one. The bottom row, where A is one, is full of ones, so one group gives A. The right column, where B is one, is also full, so a second group gives B. So F equals A plus B, which is one OR gate.

Now the rules for grouping, which exams test closely. Group only ones, and each group size must be a power of two: one, two, four, eight or sixteen. A group is a rectangle or square, never a diagonal. Make every group as large as possible, since bigger groups remove more variables. Groups may overlap, and the edges wrap around, so the left edge touches the right edge. Finally, use the fewest groups that cover every one.

A three variable map has two rows for A and four columns for B and C. The columns go zero zero, zero one, one one, one zero, in Gray code, so neighbours change only one bit. The top row holds our F values for rows zero, one, three and two. The bottom row holds rows four, five, seven and six.

Now we minimise using groups. The four corner boxes are all one, and because edges wrap, they form a quad. In that quad, A and B both change, but C is always zero, so the term is not C. Box five is still alone, so pair it with box four. There A is one and B is zero, giving A dot not B. So F equals not C plus A dot not B, far shorter than five minterms.

Pause the video and try this. F equals sigma of one, three, five, seven. Which variable has the same value in all four rows? Look at the binary: every one of these rows ends in one. So the four ones form a single quad, and F is simply C.

A four variable map has sixteen boxes, with rows for A B and columns for C D, both in Gray code. Here is F equals sigma of zero, two, five, seven, eight, ten, thirteen, fifteen. Row zero zero has ones in boxes zero and two. Row zero one has ones in boxes five and seven. Row one one has ones in boxes thirteen and fifteen. Row one zero has ones in boxes eight and ten.

Let us find the groups. The four centre boxes form a quad, where B is one and D is one, so the term is B dot D. The four corners also form a quad, because the map wraps top to bottom and left to right. There B is zero and D is zero. So F equals B dot D plus not B dot not D. Eight minterms became two terms.

Some questions ask for the minimal POS form, and the same map works. Group the zeros instead of the ones. In each group, a variable that stays zero is written plain. A variable that stays one gets a bar. Join the literals of a group with OR, and join the groups with AND. For our three variable F, boxes three and seven give not B plus not C. Boxes one and three give A plus not C. So F equals, not B plus not C, dot, A plus not C.

Let us revise what we learned today. A minterm is one for exactly one row, and a maxterm is zero for exactly one row. Canonical SOP is the sum of minterms where F is one. Canonical POS is the product of maxterms where F is zero. In a K-map, neighbouring boxes differ in one variable, using Gray code order. Make groups of one, two, four, eight or sixteen, as large and as few as possible. Group ones for SOP, and group zeros for POS.