Boolean Algebra

In this tutorial we will learning about Karnaugh Map.

We know that truth table is used to represent values of a
boolean function. Similarly, **Karnaugh map** is another way of representing the values of a
boolean function. So, K-map is a table consisting of cells which represents a Minterm or Maxterm. Karnaugh map or K-map is named after Maurice Karnaugh.

For SOP or Sum of Products, each cells in a K-map represents a Minterm. If there are n variables for a given boolean function then, the K-map will have 2^{n} cells. And we fill the cells with 1s whose Minterms output is 1. Lets check the K-map for 2, 3 and 4 variables.

Say we have two variables X and Y then, there will be 2^{2} = 4 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the minterm. So, if a cell has number 2 then it represent minterm m_{2}.

Say we have three variables X, Y and Z then there will be 2^{3} = 8 cells in the K-map.

Each cell has a subscripted number at the bottom right corner it is the value of the minterm. So, if a cell has number 7 then it represent minterm m_{7}.

Now if we look at the above K-map we will see that the numbering scheme is 0, 1, 3, 2 in the first row and 4, 5, 7, 6 in the second row. So, the numbers differ in one place when moving from left to right.

00, 01, 11, 10 this is done so that only one variable change at a time from complement to un-complement or un-complement to complement every row.

Example, in the first row we have **X’Y’Z’, X’Y’Z, X’YZ and X’YZ’** so, only one variable change at a time as we move from left to right.

1st row: moving left to right cell-wise

X’Y’Z’ —> X’Y’Z [Z’ changed to Z]

X’Y’Z —> X’YZ [Y’ changed to Y]

X’YZ —> X’YZ’ [Z changed to Z’]

Say we have four variables W, X, Y and Z then there will be 2^{4} = 16 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the minterm. So, if a cell has number 12 then, it represent minterm m_{12}.

And in this case the numbering scheme is 0, 1, 3, 2 in the first row 4, 5, 7, 6 in the second row 12, 13, 15, 14 in the third row and 8, 9, 11, 10 in the fourth row.

Say we have a boolean function F defined on two variables A and B and F = 1 i.e., output is 1 only when exactly one of the input is 1. So, we can draw the following truth table with all possible input and output values.

To express F using Minterm shorthand notation we have to consider only those minterms for which F = 1.

F = m_{1} + m_{2}

This can also be written as

F = ∑(1, 2)

Now, we have F = m_{1} + m_{2} = ∑(1, 2)

Draw an empty K-map having 4 cells (since there are 2 variables so 2_{2} = 4 cells).

F = m_{1} + m_{2}

So, fill the cells marked with subscript 1 and 2 with value 1. And fill rest of the cells of the K-map with value 0.

In a similarly way we can fill 3 and 4 variables K-map.

For POS each cells in a K-map represents a Maxterm. If there are n variables for a given boolean function then the K-map will have 2n cells. And we fill the cells with 0s whose Maxterm output is 0. Lets check the K-map for 2, 3 and 4 variables.

Say we have two variables X and Y then there will be 2^{2} = 4 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the maxterm. So, if a cell has number 2 then, it represent maxterm M_{2}.

Say we have three variables X, Y and Z then there will be 2^{3} = 8 cells in the K-map. So, if a cell has number 0 then it represent maxterm M_{0}.

Now if we look at the above K-map we will see that the numbering scheme is 0, 1, 3, 2 in the first row and 4, 5, 7, 6 in the second row. So, the numbers differ in one place when moving from left to right.

00, 01, 11, 10 this is done so that only one variable change at a time from complement to un-complement or un-complement to complement every row.

Example, in the first row we have **X+Y+Z, X+Y+Z’, X+Y’+Z’ and X+Y’+Z** so, only one variable change at a time as we move from left to right.

1st row: moving left to right cell-wise

X+Y+Z —> X+Y+Z’ [Z changed to Z’]

X+Y+Z’ —> X+Y’+Z’ [Y changed to Y’]

X+Y’+Z’ —> X+Y’+Z [Z’ changed to Z]

Say we have four variables W, X, Y and Z then there will be 2^{4} = 16 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the maxterm. So, if a cell has number 15 then it represent maxterm M_{15.}

And in this case the numbering scheme is 0, 1, 3, 2 in the first row 4, 5, 7, 6 in the second row 12, 13, 15, 14 in the third row and 8, 9, 11, 10 in the fourth row.

Say we have a boolean function F defined on two variables A and B and F = 1 i.e., output is 1 only when exactly one of the input is 1. So we can draw the following truth table with all possible input and output values.

To express F using Maxterm shorthand notation we have to consider only those maxterms for which F = 0.

F = M_{0} . M_{3}

This can also be written as

F = ∏(0, 3)

Now that we have F = M_{0} . M_{3} = ∏(0, 3).

Draw an empty K-map having 4 cells (since there are 2 variables so 2^{2} = 4 cells)

F = M_{0} . M_{3}

So, fill the cells marked with subscript 0 and 3 with value 0. And fill rest of the cells of the K-map with value 1.

In a similarly way we can fill 3 and 4 variables K-map.