GATE CS 1997 Q71 — Minimization (K-Maps etc.)

Part (A): Minimal Sum of Products (SOP)

Given the product-of-sums (POS) expression: $$f = (\bar{w} + y)(\bar{x} + y)(w + \bar{x} + z)(\bar{w} + z)(\bar{x} + z)$$

We can simplify this using Boolean algebra laws:

1. Combine terms using the distributive law $(A+C)(B+C) = AB+C$:
   • $(\bar{w} + y)(\bar{x} + y) = \bar{w}\bar{x} + y$
   • $(\bar{w} + z)(\bar{x} + z) = \bar{w}\bar{x} + z$
2. Substitute these back into $f$: $$f = (\bar{w}\bar{x} + y)(\bar{w}\bar{x} + z)(w + \bar{x} + z)$$
3. Simplify the first two terms again using the distributive law: $$(\bar{w}\bar{x} + y)(\bar{w}\bar{x} + z) = \bar{w}\bar{x} + yz$$
4. Multiply with the remaining term: $$f = (\bar{w}\bar{x} + yz)(w + \bar{x} + z)$$ $$f = \bar{w}\bar{x}w + \bar{w}\bar{x}\bar{x} + \bar{w}\bar{x}z + wyz + \bar{x}yz + yz$$
5. Since $\bar{w}\bar{x}w = 0$, and applying the absorption law ($A + AB = A$): $$f = \bar{w}\bar{x} + \bar{w}\bar{x}z + yz(w + \bar{x} + 1)$$ $$f = \bar{w}\bar{x} + yz$$

Thus, the minimal SOP form is $\bar{w}\bar{x} + yz$.

Part (B): Stuck-at-0 Fault Analysis

If the output is stuck at $0$, the circuit always outputs $0$. The output is correct only when the true function value $f = 0$.

Let us find the number of input combinations where $f = 1$:

• Minterms for $\bar{w}\bar{x}$ ($w=0, x=0$): $2^2 = 4$ combinations.
• Minterms for $yz$ ($y=1, z=1$): $2^2 = 4$ combinations.
• Common minterms ($\bar{w}\bar{x}yz$): $1$ combination ($0011$).

Using the principle of inclusion-exclusion, the total number of combinations where $f = 1$ is: $$4 + 4 - 1 = 7$$

Since there are $4$ variables ($w, x, y, z$), the total number of input combinations is $2^4 = 16$.

The number of combinations where $f = 0$ (and thus the stuck-at-0 output is correct) is: $$16 - 7 = 9$$