ABSTRACT
Summary of procedure when simplifying a Boolean expression using a Karnaugh map
Draw a four, eight or sixteen-cell matrix, depending on whether there are two, three or four variables.
Mark in the Boolean expression by putting l’s in the appropriate cells.
Form couples of 8, 4 or 2 cells having common edges, forming the largest groups of cells possible. (Note that a cell containing a 1 may be used more than once when forming a couple. Also note that each cell containing a 1 must be used at least once)
The Boolean expression for a couple is given by the variables which are common to all cells in the couple.
Two-variable Karnaugh maps
A truth table for a two-variable expression is shown in Table 92.1(a), the ‘1’ in the third row output showing that Z = A . B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3005.tif"/> . Each of the four possible Boolean expressions associated with a two-variable function can be depicted as shown in Table 92.1(b) in which one cell is allocated to each row of the truth table. A matrix similar to that shown in Table 92.1(b) can be used to depict Z = A . B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3006.tif"/> , by putting a 1 in the cell corresponding to A . B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3007.tif"/> . and 0’s in the remaining cells. This method of depicting a Boolean expression is called a two-variable Karnaugh map, and is shown in Table 92.1(c).
Inputs
Output
Boolean expression
A
B
Z
0
0
0
A ¯ ⋅ B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3008.tif"/>
0
1
0
A ¯ ⋅ B https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3009.tif"/>
1
0
1
A ⋅ B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3010.tif"/>
1
1
0
A ⋅ B https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3011.tif"/>
B\A
0 (Ā)
1 (A)
0( B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3012.tif"/> )
A ¯ ⋅ B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3013.tif"/>
A ⋅ B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3014.tif"/>
1(B)
A ¯ ⋅ B https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3015.tif"/>
A · B
B\A
0
1
0
0
1
1
0
0
To simplify a two-variable Boolean expression, the Boolean expression is depicted on a Karnaugh map, as outlined above.
Any cells on the map having either a common vertical side or a common horizontal side are grouped together to form a couple. (This is a coupling together of cells, not just combining two together). The simplified Boolean expression for a couple is given by those variables common to all cells in the couple.
262 Three-variable Karnaugh maps
A truth table for a three-variable expression is shown in Table 92.2(a), the 1’s in the output column showing that: Z = A ¯ . B ¯ .C . + A ¯ .B .C + A .B . C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3016.tif"/> . Each of the eight possible Boolean expressions associated with a three-variable function can be depicted as shown in Table 92.2(b) in which one cell is allocated to each row of the truth table. A matrix similar to that shown in Table 92.2(b) can be used to depict: Z = A ¯ . B ¯ .C . + A ¯ .B .C + A .B . C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3017.tif"/> , by putting 1’s in the cells corresponding to the Boolean terms on the right of the Boolean equation and 0’s in the remaining cells. This method of depicting a three-variable Boolean expression is called a three-variable Karnaugh map, and is shown in Table 92.2(c).
Inputs
Output
Boolean expression
A
B
C
Z
0
0
0
0
A ¯ ⋅ B ¯ ⋅ C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3018.tif"/>
0
0
1
1
A ¯ ⋅ B ¯ ⋅ C https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3019.tif"/>
0
1
0
0
A ¯ ⋅ B ⋅ C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3020.tif"/>
0
1
1
1
A ¯ ⋅ B ⋅ C https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3021.tif"/>
1
0
0
0
A ⋅ B ¯ ⋅ C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3022.tif"/>
1
0
1
0
A ⋅ B ¯ ⋅ C https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3023.tif"/>
1
1
0
1
A ⋅ B ⋅ C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3024.tif"/>
1
1
1
0
A · B · C
C\A · B
00 ( A ¯ ⋅ B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3025.tif"/> )
01 ( A ¯ ⋅ B https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3026.tif"/> )
11 (A · B)
10 ( A ⋅ B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3027.tif"/> )
0( C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3028.tif"/> )
A ¯ ⋅ B ¯ ⋅ C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3029.tif"/>
A ¯ ⋅ B ⋅ C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3030.tif"/>
A ⋅ B ⋅ C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3031.tif"/>
A ⋅ B ¯ ⋅ C ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3032.tif"/>
1(C)
A ¯ ⋅ B ¯ ⋅ C https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3033.tif"/>
A ¯ ⋅ B ⋅ C https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3034.tif"/>
A · B · C
A ⋅ B ¯ ⋅ C https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3035.tif"/>
C\A · B
00
01
11
10
0
0
0
1
0
1
1
1
0
0
To simplify a three-variable Boolean expression, the Boolean expression is depicted on a Karnaugh map as outlined above. Any cells on the map having common edges either vertically or horizontally are grouped together to form couples of four cells or two cells. During coupling the horizontal lines at the top and bottom of the cells are taken as a common edge, as are the vertical lines on the left and right of the cells. The simplified Boolean expression for a couple is given by those variables common to all cells in the couple.
Four-variable Karnaugh maps
A truth table for a four-variable expression is shown in Table 92.3(a), the 1’s in the output column showing that:
Inputs
Output
Boolean expression
A
B
C
D
Z
0
0
0
0
0
A ¯ ⋅ B ¯ ⋅ C ¯ ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3036.tif"/>
0
0
0
1
0
A ¯ ⋅ B ¯ ⋅ C ¯ ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3037.tif"/>
0
0
1
0
1
A ¯ ⋅ B ¯ ⋅ C ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3038.tif"/>
0
0
1
1
0
A ¯ ⋅ B ¯ ⋅ C ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3039.tif"/>
0
1
0
0
0
A ¯ ⋅ B ⋅ C ¯ ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3040.tif"/>
0
1
0
1
0
A ¯ ⋅ B ⋅ C ¯ ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3041.tif"/>
0
1
1
0
1
A ¯ ⋅ B ⋅ C ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3042.tif"/>
0
1
1
1
0
A ¯ ⋅ B ⋅ C ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3043.tif"/>
1
0
0
0
0
A ⋅ B ¯ ⋅ C ¯ ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3044.tif"/>
1
0
0
1
0
A ⋅ B ¯ ⋅ C ¯ ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3045.tif"/>
1
0
1
0
1
A ⋅ B ¯ ⋅ C ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3046.tif"/>
1
0
1
1
0
A ⋅ B ¯ ⋅ C ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3047.tif"/>
1
1
0
0
0
A ⋅ B ⋅ C ¯ ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3048.tif"/>
1
1
0
1
0
A ⋅ B ⋅ C ¯ ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3049.tif"/>
1
1
1
0
1
A ⋅ B ⋅ C ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3050.tif"/>
1
1
1
1
0
A ⋅ B ⋅ C ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3051.tif"/>
Z = A ¯ . B ¯ . C . D ¯ + A ¯ . B . C . D ¯ + A . B ¯ . C . D ¯ + A . B . C . D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3052.tif"/>263Each of the sixteen possible Boolean expressions associated with a four-variable function can be depicted as shown in Table 92.3(b), in which one cell is allocated to each row of the truth table. A matrix similar to that shown in Table 92.3(b) can be used to depict:
C · D\A · B
00 ( A ¯ ⋅ B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3053.tif"/> )
01 (Ā · B)
11 (A · B)
10 ( A ⋅ B ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3054.tif"/>
00 ( C ¯ ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3055.tif"/> )
A ¯ ⋅ B ¯ ⋅ C ¯ ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3056.tif"/>
A ¯ ⋅ B ⋅ C ¯ ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3057.tif"/>
A ⋅ B ⋅ C ¯ ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3058.tif"/>
A ⋅ B ¯ ⋅ C ¯ ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3059.tif"/>
01 ( C ¯ ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3060.tif"/> )
A ¯ ⋅ B ¯ ⋅ C ¯ ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3061.tif"/>
A ¯ ⋅ B ⋅ C ¯ ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3062.tif"/>
A ⋅ B ⋅ C ¯ ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3063.tif"/>
A ⋅ B ¯ ⋅ C ¯ ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3064.tif"/>
11 (C · D)
A ¯ ⋅ B ¯ ⋅ C ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3065.tif"/>
A ¯ ⋅ B ⋅ C ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3066.tif"/>
A · B · C · D
A ⋅ B ¯ ⋅ C ⋅ D https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3067.tif"/>
10 ( C ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3068.tif"/> )
A ¯ ⋅ B ¯ ⋅ C ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3069.tif"/>
A ¯ ⋅ B ⋅ C ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3070.tif"/>
A ⋅ B ⋅ C ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3071.tif"/>
A ⋅ B ¯ ⋅ C ⋅ D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3072.tif"/>
Z = A ¯ . B ¯ . C . D ¯ + A ¯ . B . C . D ¯ + A . B ¯ . C . D ¯ + A . B . C . D ¯ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429294402/968186b9-ffa4-4f2b-aa54-7fc58a604561/content/eq3073.tif"/>by putting 1’s in the cells corresponding to the Boolean terms on the right of the Boolean equation and 0’s in the remaining cells. This method of depicting a four-variable expression is called a four-variable Karnaugh map, and is shown in Table 92.3(c).
C · D\A · B
0.0
0.1
1.1
1.0
0.0
0
0
0
0
0.1
0
0
0
0
1.1
0
0
0
0
1.0
1
1
1
1
To simplify a four-variable Boolean expression, the Boolean expression is depicted on a Karnaugh map as outlined above. Any cells on the map having common edges either vertically or horizontally are grouped together to form couples of eight cells, four cells or two cells. During coupling, the horizontal lines at the top and bottom of the cells may be considered to be common edges, as are the vertical lines on the left and the right of the cells. The simplified Boolean expression for a couple is given by those variables common to all cells in the couple.
