Question

Consider a Boolean function \(F\) with the following minterm expression: \[ F(P, Q, R, S) = \sum m(1, 2, 3, 4, 5, 7, 10, 12, 13, 14) \] Which of the following options is/are the minimal sum-of-products expression(s) of \(F\)?

• A. \(\bar{P}S + Q\bar{R} + \bar{P}\bar{Q}R + \bar{Q}R\bar{S}\)
• B. \(\bar{P}S + Q\bar{R} + \bar{P}\bar{Q}R + PR\bar{S}\)
• C. \(\bar{P}S + Q\bar{R} + PQ\bar{S} + PR\bar{S}\)
• D. \(\bar{P}S + Q\bar{R} + PQ\bar{S} + \bar{Q}R\bar{S}\)

Hint:

Draw the 4-variable K-map for the given minterms; find the two essential 4-cell groups first, then check which pair of 2-cell groups is needed to cover the three leftover cells m2, m10, m14.

Answer 1

The Correct Option is B, D

Step 1: List the minterms in binary (order \(PQRS\)).

m1  = 0001    m2  = 0010    m3  = 0011    m4  = 0100    m5  = 0101
m7  = 0111    m10 = 1010    m12 = 1100    m13 = 1101    m14 = 1110

The remaining minterms \(\{0,6,8,9,11,15\}\) are 0 (not don't-cares).

Step 2: Find the essential prime implicants by grouping.
Group \(\{1,3,5,7\}\) = \(0001,0011,0101,0111\): all have \(P=0, S=1\), with \(Q,R\) taking all four combinations -- a valid 4-cell group giving the prime implicant \(\bar{P}S\).
Group \(\{4,5,12,13\}\) = \(0100,0101,1100,1101\): all have \(Q=1,R=0\), with \(P,S\) taking all four combinations -- a valid 4-cell group giving the prime implicant \(Q\bar{R}\).
No larger implicant can be formed containing m1 (dropping any literal from \(\bar{P}S\) would pull in the 0-minterms \(m9, m11, m15\)), so \(\bar{P}S\) is essential. Similarly \(Q\bar{R}\) is the unique maximal implicant covering m4, so it is essential too.

Step 3: Determine what remains to be covered.
\(\bar{P}S\) covers \(\{1,3,5,7\}\); \(Q\bar{R}\) covers \(\{4,5,12,13\}\). Together they cover \(\{1,3,4,5,7,12,13\}\). The full minterm list is \(\{1,2,3,4,5,7,10,12,13,14\}\), so the still-uncovered minterms are \(\{2, 10, 14\}\).

Step 4: Find prime implicants for the remaining minterms \(\{2,10,14\}\) (binary \(0010, 1010, 1110\)).
These three cells all share \(R=1, S=0\), but the fourth corner of that potential 4-group, \(m6=0110\), is a 0-minterm, so no 4-cell group is possible; only pairwise groupings are valid:
- \(\{2,3\}\) (\(0010,0011\)): differ only in \(S\), giving \(\bar{P}\bar{Q}R\).
- \(\{2,10\}\) (\(0010,1010\)): differ only in \(P\), giving \(\bar{Q}R\bar{S}\).
- \(\{10,14\}\) (\(1010,1110\)): differ only in \(Q\), giving \(PR\bar{S}\).
- \(\{12,14\}\) (\(1100,1110\)): differ only in \(R\), giving \(PQ\bar{S}\).
Each of these is a genuine prime implicant: dropping any further literal always pulls in a 0-minterm such as \(m0, m6, m8, m9, m11\) or \(m15\).

Step 5: Combine to cover \(\{2,10,14\}\) with as few extra terms as possible.
No single prime implicant covers all three of \(2, 10, 14\) (Step 4), so at least 2 more terms are needed, chosen so their union covers \(\{2,10,14\}\):
(i) \(\bar{P}\bar{Q}R\{2,3\}\) plus \(PR\bar{S}\{10,14\}\): union covers \(\{2,3,10,14\} \supseteq \{2,10,14\}\). This is exactly option (B): \(\bar{P}S+Q\bar{R}+\bar{P}\bar{Q}R+PR\bar{S}\).
(ii) \(\bar{Q}R\bar{S}\{2,10\}\) plus \(PQ\bar{S}\{12,14\}\): union covers \(\{2,10,12,14\} \supseteq \{2,10,14\}\). This is exactly option (D): \(\bar{P}S+Q\bar{R}+PQ\bar{S}+\bar{Q}R\bar{S}\).
Both combinations use exactly 4 terms in total (2 essential plus 2 more), the minimum possible, since \(\{2,10,14\}\) genuinely requires 2 separate implicants to cover.

Step 6: Check options (A) and (C) for completeness.
Option (A): \(\bar{P}S + Q\bar{R} + \bar{P}\bar{Q}R + \bar{Q}R\bar{S}\) covers \(\{1,3,5,7\} \cup \{4,5,12,13\} \cup \{2,3\} \cup \{2,10\} = \{1,2,3,4,5,7,10,12,13\}\) -- this MISSES minterm 14 (no term is satisfied at \(P=1,Q=1,R=1,S=0\)). So option (A) does not equal \(F\); it is invalid.
Option (C): \(\bar{P}S + Q\bar{R} + PQ\bar{S} + PR\bar{S}\) covers \(\{1,3,5,7\} \cup \{4,5,12,13\} \cup \{12,14\} \cup \{10,14\} = \{1,3,4,5,7,10,12,13,14\}\) -- this MISSES minterm 2 (no term is satisfied at \(P=0,Q=0,R=1,S=0\)). So option (C) is also invalid.

Step 7: Conclusion.
Only options (B) and (D) are complete, minimal, all-prime-implicant sum-of-products expressions equal to \(F\). \[ \boxed{\text{Options (B) and (D)}} \]