Karnaugh Map

In 1953,Maurice Karnaugh device a simple process of mapping by which any boolean function can be simplified.The map technique works for any no of inputs but it is suggested for only 6 or 7 inputs.

If we have two inputs the truth table can be of the following form-
 
                                             Input                           output
                                 A                         B          
                                 0                          0                    0                 (OR gate truth table)
                                 0                          1                    1          
                                 1                          0                    1
                                 1                          1                    1

here we have to draw square or rectangles such a way to take all the combinations of input.for 2 input we will have to get 2^2=4 boxes. so a  square box with four parts will do. e.g.

Each square represents the output.Here,In first box as A is 0 and B is zero,we have 0 in the first box(As you can see from the truth table).So all the values in the map is there as seen in the truth table.Next step is to group the squares where the value is 1 and find out the common term.Grouping is done by selecting boxes which have 1 and adjacent to each other either vertically or horizontally but not diagonally.

After grouping as the picture above,we have two groups where A=1 is the common value in the horizontal group and B=1 is the second group.so from the table we have the values 1 or minterms are-AB',AB and A'B.So function of the circuit f=AB'+AB+A'B=A(B+B')+A'B=A+A'B=(A+A')(A+B)=A+B.From Karnaugh map we have to select common values of the groups.The horizontal group common is A(A=0 value denoted by A') and from vertical it is B. So the simplified function is f=A+B.
Lets see it for three variables.A function f =Σ(1,3,5). Assume that the name of the variables are x,y,z.We will have 2^3=8 boxes for this purpose.The squares are numbered as the fig. below-

As from the figure you can see the values of the boxes are the decimal representation of binary value of x,y,z of the corresponding box.As the function shows us we have  value 1 in (1,3,5) position,the table is modified after putting 1's in corresponding boxes and grouping them-

Here we put 1 in appropriate boxes and grouped them.So for the horizontal grouping here we have common term x'z and for vertical group common term is y'z. So the the simplified function is f=x'z+y'z.

we can also prove that by minterms and boolean formulas-

f=x'y'z+x'yz+xy'z=x'z(y'+y)+xy'z=x'z+xy'z=z(x'+xy')=z(x'+x)(x'+y')=x'z+y'z
So once drawing and just looking at it we can simplify any digital equation from Karnaugh map.

This is the four input circuit and the function f= Σ(1,5,6,7,9,13). from the truth table simplify the function and draw the circuit.

Digital Circuit Main Page
Boolean Expressions(SOP and POS forms)

Truth Table

Combinational Circut

Sequential Circuit

Number System