GATE CS 2016 Set 1 Q.40 (CS Q.30): Combinational Circuits

Consider the two cascaded 2-to-1 multiplexers as shown in the figure.

The minimal sum of products form of the output X is

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

$\bar{P}Q + QR$

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

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

Official answer and solution

Solution

Express the output of the first multiplexer and substitute it into the second multiplexer to simplify the Boolean expression.

Recall the Boolean transfer function for a 2-to-1 multiplexer with select input $S$ and data inputs $I_0, I_1$ :

Y = \bar{S} I_0 + S I_1

For MUX 1:

f_1 = \bar{P}(0) + P(R) = PR

For MUX 2:

X = \bar{Q}(\bar{R}) + Q(f_1) = \bar{Q}\bar{R} + Q(PR) = \bar{Q}\bar{R} + PQR

The expression $\bar{Q}\bar{R} + PQR$ is already in minimal sum-of-products (SOP) form because the two product terms cannot be combined.

Final answer

Common trap

Failing to account for the inverted input $\bar{R}$ on input 0 of MUX 2.

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.