GATE CS 2014 Set 1 Q.17 (CS Q.7): Boolean Algebra and Logic Minimization

Consider the following Boolean expression for $F$ :

F(P, Q, R, S) = PQ + \bar{P}QR + \bar{P}Q\bar{R}S

The minimal sum-of-products form of $F$ is

$PQ + QR + QS$

$P + Q + R + S$

$\bar{P} + \bar{Q} + \bar{R} + \bar{S}$

$\bar{P}R + \bar{P}\bar{R}S + P$

Official answer and solution

Solution

Factor and simplify the Boolean expression using standard Boolean algebra theorems.

The given expression is:

F(P, Q, R, S) = PQ + \bar{P}QR + \bar{P}Q\bar{R}S

Factor out $Q$ from all three terms:

F = Q \left( P + \bar{P}R + \bar{P}\bar{R}S \right)

Using the Boolean identity $A + \bar{A}B = A + B$ :
First simplify $P + \bar{P}R$ :

P + \bar{P}R = P + R

Now the expression inside the parentheses becomes:

P + R + \bar{P}\bar{R}S = P + R + \overline{(P + R)}S

Applying the same identity $A + \bar{A}B = A + B$ where $A = P + R$ :

(P + R) + \overline{(P + R)}S = P + R + S

Now distribute $Q$ back:

F = Q(P + R + S) = PQ + QR + QS

This is in minimal sum-of-products (SOP) form with 3 product terms.

Final answer

Common trap

Leaving the redundant literal $\bar{P}$ or $\bar{R}$ in the product terms without applying absorption.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.