Example 16: We now use an example to illustrate the reduction process in the QM when don’tcare terms appear in the given logic function. Reduce S = Sm(1, 2, 4, 5, 6, 8, 9, 12) + d(3, 10, 13, 15).
Solution: Chart 1 shows the initial grouping, Chart 2 shows the pairs, and Chart 3 shows the quads. In the case of the Kmap reduction technique, don’tcare terms were treated as valid terms if it were helpful in the reduction process. The same assumption is brought into the QM reduction process also. The QM charts of Example 16 are drawn as shown below using the principles discussed in the previous sections.
It may be noticed that the
don’tcare terms are identified with the letter d attached to them in Chart 1. However, once they are identified,
the letter d is dropped from
respective terms, as shown in Chart 3. Now, the quads and pairs are designated
using bold letters digits as shown. The reduced terms represented using
bold letters are:
A : 1, 5, 9,
13
B : 4, 5, 12, 13
C : 8, 9, 12, 13
D : 1, 3
E : 2, 3
F : 2, 6
G : 2, 10
H : 4, 6
I : 8, 10
J : 13, 15
The above groups are now
entered as shown in Table 2.18 for reduction by the modified QM technique. In
Table 2.18, we represent the selected groups by bold digits. The groups that
are not selected are represented by conventional letters and digits. In Table
2.18, we have shown a third column with entries Y/N. Y represents yes, indicating the selection of that
group, while N represents no indicating the rejection of that
group.
The finally selected reduced Groups
are A,
B,
C, and F. In selecting these groups, we have discarded Groups D,
E, H, I, and J, as each one of them contains at
least one don’tcare term, which has no relevance at all in the final groups.
For example, Groups D (2, 3d) and G
(2, 10d) have no relevance at all
since the only valid member in these groups, viz., 2, has already been selected
in Group F. Hence they are discarded. The same is the case with E,
H, I, and J. The reduction process to get the
final SOP expression is then carried out, as shown in Table 2.19.
From Table 2.19, we obtain
the resultant expression as
S = c′ d + bc′ +
ac′ + a′ b′
d +a′ cd′ (2.40)
We now solve Example 15 using the Kmap shown in Fig. 2.40. From the Kmap, we obtain the resultant expression as the same one given by Eq. (2.40).
Table 2.19
Group

Group members

Elimination

Reduced Function

A

1, 5, 9, 13,

0 0 0
1
0 1 0
1
1 0 0
1
1 1 0
1

c′d

B

4,
5, 12, 13

0 1 0
0
0 1 0
1
1 1 0 0
1
1 0
1

b c′

C

8, 9, 12, 13

1 0 0 0
1 0 0 1
1 1 0 0
1 1 0 1

a c′

F

2, 6

0 0 1 0
0 1 1
0

a′ c d′
