Page 40 - Computer science 868 Class 12
P. 40
1.12 INTRODUCTION TO KARNAUGH MAPS
We have already learnt how to simplify a Boolean expression using Boolean laws. A Boolean expression can also be
simplified graphically using the K-map method. The K-map (Karnaugh map) is a graphical method of simplifying a
n
Boolean expression in which a rectangle or square grid of 2 (where n represents the number of Boolean variables that
constitute the expression) is drawn in a definite pattern.
K-map is a representation of the information derived from a truth table of a Boolean function in a rectangular array of
cells.
In this class, we shall discuss a K-map of 3 and 4 variables. As any Boolean expression is represented in two forms
namely SOP (Sum of Product) and POS (Product of Sum), the K-map also has two forms based on the type of expression.
The individual grid of the map is filled with 0 or 1 and accordingly, grouping is made.
The following steps are taken to minimise a Boolean expression using a Karnaugh Map.
1.12.1 Drawing a K-map
Considering a Boolean expression of three variables F(A, B, C), two rightmost terms B and C are written at the top and
the leftmost A is written to the left in such a way that at a time only one variable changes its sign. Each box represents
a minterm (for SOP) and a maxterm (for POS). The number associated with each box is its corresponding cardinal
3
number. Total 2 , i.e., 8 boxes are used to represent the terms.
The three-variable SOP K-map both in algebraic form and in binary from or grey code is illustrated below.
B'.C' B'.C B.C B.C' B.C
A' A'.B'.C' A'.B'.C A'.B.C A'.B.C' A 0 0 0 1 1 1 10
0 1 3 2
A A.B'.C' A.B'.C A.B.C A.B.C' 0 0 1 3 2
4 5 7 6 1 4 5 7 6
The three-variable POS K-map both in algebraic and binary forms is illustrated below.
B+C B+C' B'+C' B'+C B+C
A A+B+C A+B+C' A+B'+C' A+B'+C A 0 0 0 1 1 1 1 0
0 1 3 2
A' A'+B+C A'+B+C' A'+B'+C' A'+B'+C 0 0 1 3 2
4 5 7 6 1 4 5 7 6
4
Similarly, a four-variable truth table of F(A, B, C, D) can be represented with 2 , i.e., 16 grids cell. Considering a Boolean
expression F(A, B, C, D), the first two variables are written to the left, while the last two variables are written at the
top in such a way that a single variable is either complemented or uncomplemented. The minterms or maxterms along
with their cardinal numbers are shown in the diagram below.
The four-variable SOP K-map in algebraic and grey code form is illustrated below.
C'.D' C'.D C.D C.D'
A'.B' A'.B'.C'.D' A'.B'.C'.D A'.B'.C.D A'.B'.C.D'
0 1 3 2 C.D
A'.B A'.B.C'.D' A'.B.C'.D A'.B.C.D A'.B.C.D' A.B 0 0 0 1 1 1 1 0
4 5 7 6 0 0 0 1 3 2
A.B A.B.C'.D' A.B.C'.D A.B.C.D A.B.C.D'
12 13 15 14 0 1 4 5 7 6
A.B' A.B'.C'.D' A.B'.C'.D A.B'.C.D A.B'.C.D' 1 1 12 13 15 14
8 9 11 10 1 0 8 9 11 10
3838 Touchpad Computer Science-XII

