GATE CS 2008 Q8 — Boolean Algebra

The given logic circuit consists of an AND gate followed by an OR gate. The output expression is:

We are given the minterm lists:

• $f_1 = \Sigma m(4, 5, 6, 7, 8)$
• $f_3 = \Sigma m(1, 6, 15)$
• $f = \Sigma m(1, 6, 8, 15)$

To find $f_2$, we analyze the relation $f = (f_1 \cdot f_2) + f_3$:

1. The minterm $8$ is present in $f$ but not in $f_3$. Therefore, it must be provided by the term $(f_1 \cdot f_2)$. This implies $8 \in f_1$ and $8 \in f_2$.
2. Any minterm in $(f_1 \cdot f_2)$ must also be present in $f$. Thus, $(f_1 \cdot f_2) \subseteq \{1, 6, 8, 15\}$.
3. Since $f_1 = \{4, 5, 6, 7, 8\}$, the intersection $(f_1 \cdot f_2)$ can only contain minterms from $f_1 \cap \{1, 6, 8, 15\} = \{6, 8\}$.
4. This means $f_2$ must contain $8$, may contain $6$, but cannot contain $4, 5,$ or $7$ (as their presence in $f_2$ would introduce them into $f$, which is incorrect).

Checking the options:

• A: $\Sigma m(4, 6)$ — contains $4$ (invalid) and lacks $8$.
• B: $\Sigma m(4, 8)$ — contains $4$ (invalid).
• C: $\Sigma m(6, 8)$ — valid, contains $8$ and $6$, and does not contain $4$.
• D: $\Sigma m(4, 6, 8)$ — contains $4$ (invalid).