GATE CS 2019 Q30 — Boolean Algebra

From the given circuit diagram, we can determine the Boolean expression for the output function $f$:

1. The AND gate takes inputs $f_1$ and $f_2$. Its output is: $$Y = f_1 \cdot f_2$$
2. The XOR gate takes the output of the AND gate ($Y$) and $f_3$ as inputs. The final output is: $$f = Y \oplus f_3 = (f_1 \cdot f_2) \oplus f_3$$

Step 1: Compute $f_1 \cdot f_2$

The AND operation on two sum-of-minterms functions corresponds to the intersection of their minterm sets:

• $f_1 = \Sigma(0, 2, 5, 8, 14)$
• $f_2 = \Sigma(2, 3, 6, 8, 14, 15)$

$$f_1 \cdot f_2 = \Sigma(0, 2, 5, 8, 14) \cap \Sigma(2, 3, 6, 8, 14, 15) = \Sigma(2, 8, 14)$$

Step 2: Compute $f = (f_1 \cdot f_2) \oplus f_3$

The XOR operation corresponds to the symmetric difference of the minterm sets (i.e., minterms that are present in either of the sets but not in both):

• $f_1 \cdot f_2 = \Sigma(2, 8, 14)$
• $f_3 = \Sigma(2, 7, 11, 14)$

$$f = \Sigma(2, 8, 14) \oplus \Sigma(2, 7, 11, 14)$$

Evaluating the symmetric difference:

• Minterm $2$: Present in both $\rightarrow$ Excluded
• Minterm $7$: Present only in $f_3$ $\rightarrow$ Included
• Minterm $8$: Present only in $(f_1 \cdot f_2)$ $\rightarrow$ Included
• Minterm $11$: Present only in $f_3$ $\rightarrow$ Included
• Minterm $14$: Present in both $\rightarrow$ Excluded

Thus, the output function is: $$f = \Sigma(7, 8, 11)$$

Therefore, the correct option is A.