674
Boolean Algebra and Computer Logic
We compare the first term, 1011, with each of the three terms of the second
group, 0110, 0101, and 0011, to locate terms differing by only one factor. Such a
term is 0011. The combination 1011 and 0011 reduces to −011 when the changing variable x 1 is eliminated. We will write this reduced term with a dash in the
x 1 position in the first row of a new table. The new table is Table 8.15b, where
we’ve just seen how the first row was obtained. We’ve rewritten the original
Table 8.14 as Table 8.15a, but we have also marked the two terms 1011 and 0011
in this table with a superscript 1. This superscript 1 is a pointer that indicates
the row number of the reduced term in Table 8.15b that is formed from these
two terms (numbering terms corresponds to putting loops in the Karnaugh map).
Table 8.15
Number of 1s x 1
x 2
x 3
x 4
Three
1
0
1
1
1
Two
0
1
1
0
2
0
1
0
1
3
0
0
1
1
1, 4, 5
One
1
0
0
0
6
0
0
1
0
2, 4, 7
0
0
0
1
3, 5, 8
None
0
0
0
0
6, 7, 8
We continue this process with all the terms in Table 8.15a. A numbered term
may still be used in other combinations, just as a marked square in a Karnaugh
map can be in more than one loop. When we are done, the result is the completed
Table 8.15b shown, where the terms in this table are again grouped by the number of 1s.
We now build still another table by processing the terms in Table 8.15b.
Here not only the groupings but also the dashes help organize the search process, since terms differing by only one variable must have dashes in the same
location. Tables 8.16a and 8.16b are the same as Tables 8.15a and 8.15b, and
Table 8.16c is the new table. Again, numbers on terms in Table 8.16b that combine
serve as pointers to the reduced terms in Table 8.16c. When we have processed
all the terms in Table 8.16b, the reduction process cannot be continued. The unnumbered terms are irreducible, so they represent the possible maximum-sized
loops on a Karnaugh map.
Number of 1s x 1
x 2
x 3
x 4
Two
–
0
1
1
One
0
–
1
0
0
–
0
1
0
0
1
–
0
0
–
1
None
–
0
0
0
0
0
–
0
0
0
0
–
(a)
(b)
Boolean Algebra and Computer Logic
We compare the first term, 1011, with each of the three terms of the second
group, 0110, 0101, and 0011, to locate terms differing by only one factor. Such a
term is 0011. The combination 1011 and 0011 reduces to −011 when the changing variable x 1 is eliminated. We will write this reduced term with a dash in the
x 1 position in the first row of a new table. The new table is Table 8.15b, where
we’ve just seen how the first row was obtained. We’ve rewritten the original
Table 8.14 as Table 8.15a, but we have also marked the two terms 1011 and 0011
in this table with a superscript 1. This superscript 1 is a pointer that indicates
the row number of the reduced term in Table 8.15b that is formed from these
two terms (numbering terms corresponds to putting loops in the Karnaugh map).
Table 8.15
Number of 1s x 1
x 2
x 3
x 4
Three
1
0
1
1
1
Two
0
1
1
0
2
0
1
0
1
3
0
0
1
1
1, 4, 5
One
1
0
0
0
6
0
0
1
0
2, 4, 7
0
0
0
1
3, 5, 8
None
0
0
0
0
6, 7, 8
We continue this process with all the terms in Table 8.15a. A numbered term
may still be used in other combinations, just as a marked square in a Karnaugh
map can be in more than one loop. When we are done, the result is the completed
Table 8.15b shown, where the terms in this table are again grouped by the number of 1s.
We now build still another table by processing the terms in Table 8.15b.
Here not only the groupings but also the dashes help organize the search process, since terms differing by only one variable must have dashes in the same
location. Tables 8.16a and 8.16b are the same as Tables 8.15a and 8.15b, and
Table 8.16c is the new table. Again, numbers on terms in Table 8.16b that combine
serve as pointers to the reduced terms in Table 8.16c. When we have processed
all the terms in Table 8.16b, the reduction process cannot be continued. The unnumbered terms are irreducible, so they represent the possible maximum-sized
loops on a Karnaugh map.
Number of 1s x 1
x 2
x 3
x 4
Two
–
0
1
1
One
0
–
1
0
0
–
0
1
0
0
1
–
0
0
–
1
None
–
0
0
0
0
0
–
0
0
0
0
–
(a)
(b)