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: Build the 4-variable K-map (rows \(PQ\), columns \(RS\), Gray-code order 00-01-11-10 on both axes).

 PQ\RS   00(R=0,S=0)   01(R=0,S=1)   11(R=1,S=1)   10(R=1,S=0)
 00      0 (m0)         1 (m1)        1 (m3)         1 (m2)
 01      1 (m4)         1 (m5)        1 (m7)         0 (m6)
 11      1 (m12)        1 (m13)       0 (m15)        1 (m14)
 10      0 (m8)         0 (m9)        0 (m11)        1 (m10)

The K-map wraps around: the leftmost column (RS=00) is adjacent to the rightmost column (RS=10), and the top row (PQ=00) is adjacent to the bottom row (PQ=10).

Step 2: Group the two largest (4-cell) blocks.
Rows PQ=00 and PQ=01, columns RS=01 and RS=11 (all four cells are 1: m1,m3,m5,m7): this block fixes \(P=0\) and \(S=1\), giving \(\bar{P}S\).
Rows PQ=01 and PQ=11, columns RS=00 and RS=01 (all four cells are 1: m4,m5,m12,m13): this block fixes \(Q=1\) and \(R=0\), giving \(Q\bar{R}\). These are the only maximal groups available for their cells, so both are essential prime implicants.

Step 3: Identify the leftover 1-cells.
After marking \(\bar{P}S\) (m1,m3,m5,m7) and \(Q\bar{R}\) (m4,m5,m12,m13) as covered, the still-unmarked 1-cells are m2 (row 00, col 10), m10 (row 10, col 10), and m14 (row 11, col 10) -- all sitting in the RS=10 column, but the whole column cannot be taken as one group because m6 (row 01, col 10) is 0.

Step 4: Pair up the leftover cells using wraparound adjacency.
m2 (row PQ=00) and m10 (row PQ=10) are adjacent via the top-bottom wraparound, both in column RS=10 (\(R=1,S=0\)) with \(Q=0\) fixed in both rows: this pair gives \(\bar{Q}R\bar{S}\).
m10 (row PQ=10) and m14 (row PQ=11) are adjacent rows, both in column RS=10, with \(P=1\) fixed in both rows: this pair gives \(PR\bar{S}\).
m12 (row PQ=11, col RS=00) and m14 (row PQ=11, col RS=10) are adjacent columns via the left-right wraparound, in the same row PQ=11 (\(P=1,Q=1\) fixed), both with \(S=0\): this pair gives \(PQ\bar{S}\).
m2 (col RS=10) and m3 (col RS=11) are adjacent columns, same row PQ=00 (\(P=0,Q=0\) fixed): this pair gives \(\bar{P}\bar{Q}R\).

Step 5: Pick a minimal pair of these to finish the cover.
Taking \(\bar{Q}R\bar{S}\) (covers m2, m10) together with \(PQ\bar{S}\) (covers m12, m14) covers all three leftover cells \(\{2,10,14\}\) using 2 extra terms, giving the total expression \(\bar{P}S + Q\bar{R} + PQ\bar{S} + \bar{Q}R\bar{S}\), which is option (D).
Taking \(\bar{P}\bar{Q}R\) (covers m2, m3) together with \(PR\bar{S}\) (covers m10, m14) also covers \(\{2,10,14\}\), giving the total expression \(\bar{P}S + Q\bar{R} + \bar{P}\bar{Q}R + PR\bar{S}\), which is option (B).
Both choices use exactly 4 groups, the minimum possible, since the 3 leftover cells cannot be grouped into fewer than 2 additional blocks.

Step 6: Confirm options (A) and (C) leave a cell unmarked.
Option (A) uses \(\bar{P}\bar{Q}R\) and \(\bar{Q}R\bar{S}\) together, which both touch m2 but never touch m14 -- m14 stays unmarked, so option (A) is not a valid SOP for \(F\).
Option (C) uses \(PQ\bar{S}\) and \(PR\bar{S}\) together, which both touch m14 but never touch m2 -- m2 stays unmarked, so option (C) is not a valid SOP for \(F\).

Step 7: Conclusion.
The K-map grouping confirms options (B) and (D) are the correct minimal sum-of-products expressions. \[ \boxed{\text{Options (B) and (D)}} \]