Given a boolean function f(x_1, x_2, ..., x_n), which of the following equations is NOT true? A. f(x_1, x_2, ..., x_n) = x_1' f(x_1, x_2, ..., x_n) + x_1 f(x_1, x_2, ..., x_n) B. f(x_1, x_2, ..., x_n) = x_2 f(x_1, x_2, ..., x_n) + x_2' f(x_1, x_2, ..., x_n) C. f(x_1, x_2, ..., x_n) = x_n' f(x_1, x_2, ..., 0) + x_n f(x_1, x_2, ..., 1) D. f(x_1, x_2, ..., x_n) = f(0, x_2, ..., x_n) + f(1, x_2, ..., x_n)

GATE 2006 · Discrete Mathematics · Functions · medium

Answer: Option D is NOT true; it omits the selecting literals x_1' and x_1 of Shannon's expansion.

1. Verify A, B, C are valid expansions: A and B have the form x f + x' f = (x + x')f = f using the complement law; C is the exact Shannon expansion about x_n with cofactors f(...,0), f(...,1) gated by x_n' and x_n, so all three are always true
2. Expose D with a counterexample: take n = 1 and f = x_1; then D claims f = f(0) + f(1) = 0 + 1 = 1 for every x_1, but f(0) = 0, so D fails. The correct identity needs x_1' f(0,...) + x_1 f(1,...)