GATE CS 2014 Set 1 Q.55 (CS Q.45): Combinational Circuits

Consider the 4-to-1 multiplexer with two select lines $P$ and $Q$ given below.

The minimal sum-of-products form of the Boolean expression for the output $F$ of the multiplexer is

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

$\bar{P}Q + \bar{P}QR + P\bar{Q}\bar{R} + PQ\bar{R}$

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

$\bar{P}QR$

Official answer and solution

Solution

Derive the output Boolean function from the multiplexer truth table and simplify to minimal sum-of-products form.

The 4-to-1 multiplexer has select lines $S_1 = P$ and $S_0 = Q$ , and inputs:

The output expression is:

F = \bar{P}\bar{Q} \cdot I_0 + \bar{P}Q \cdot I_1 + P\bar{Q} \cdot I_2 + PQ \cdot I_3

F = \bar{P}\bar{Q}(0) + \bar{P}Q(1) + P\bar{Q}(R) + PQ(\bar{R})

F = \bar{P}Q + P\bar{Q}R + PQ\bar{R}

To minimize this SOP expression:
Combine the first and third terms by expanding $\bar{P}Q$ with $R$ :

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

Now combine $\bar{P}Q\bar{R}$ with $PQ\bar{R}$ :

\bar{P}Q\bar{R} + PQ\bar{R} = (\bar{P} + P)Q\bar{R} = Q\bar{R}

Thus, $\bar{P}Q + PQ\bar{R} = \bar{P}Q + Q\bar{R}$ .

Adding the remaining essential prime implicant $P\bar{Q}R$ :

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

All three terms are prime implicants and are essential. Therefore, the minimal SOP form is:

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

Final answer

Common trap

Failing to simplify $\bar{P}Q + PQ\bar{R}$ to $\bar{P}Q + Q\bar{R}$ via consensus.

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.