GATE CS 2019 Q.40 (CS Q.30): Combinational Circuits

Consider three 4-variable functions $f_1, f_2,$ and $f_3$ , which are expressed in sum-of-minterms as

f_1 = \sum (0, 2, 5, 8, 14), \quad f_2 = \sum (2, 3, 6, 8, 14, 15), \quad f_3 = \sum (2, 7, 11, 14)

For the following circuit with one AND gate and one XOR gate, the output function $f$ can be expressed as:

$\sum (7, 8, 11)$

$\sum (2, 7, 8, 11, 14)$

$\sum (2, 14)$

$\sum (0, 2, 3, 5, 6, 7, 8, 11, 14, 15)$

Official answer and solution

Solution

Compute the minterm expressions for the AND and XOR gates in the circuit.

We are given the minterms of three 4-variable functions:

From the circuit diagram:

The inputs to the AND gate are $f_1$ and $f_2$ . The output of an AND gate corresponds to the set intersection of their minterms:

f_{\text{AND}} = f_1 \cap f_2 = \{0, 2, 5, 8, 14\} \cap \{2, 3, 6, 8, 14, 15\} = \{2, 8, 14\}

The inputs to the XOR gate are $f_{\text{AND}}$ and $f_3$ . The output of an XOR gate corresponds to the symmetric difference of their minterm sets:

f = f_{\text{AND}} \oplus f_3 = \{2, 8, 14\} \oplus \{2, 7, 11, 14\}

Common minterms are $\{2, 14\}$ . Removing them from the union gives:

f = \{8\} \cup \{7, 11\} = \{7, 8, 11\}

Thus, the output function is $f = \sum (7, 8, 11)$ .

Final answer

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.