Given a boolean function f (x1, x2, ..., xn), which of the following equations…
2006
Given a boolean function f (x1, x2, ..., xn), which of the following equations is NOT true
- A.
f(x1, x2, …, xn) = x1'f(x1, x2, …, xn) + x1f(x1, x2, …, xn)
- B.
f(x1, x2, ..., xn) = x2f(x1, x2, …, xn) + x2'f(x1, x2, …, xn)
- C.
f(x1, x2, ..., xn) = xn'f(x1, x2, …, 0) + xnf(x1, x2, …,1)
- D.
f(x1, x2, ..., xn) = f(0, x2, …, xn) + f(1, x2, ..., xn)
Attempted by 265 students.
Show answer & explanation
Correct answer: D
The equation that is NOT true is: f(x1, x2, ..., xn) = f(0, x2, …, xn) + f(1, x2, ..., xn).
Why the other equations are true:
For f(x1, ..., xn) = x1' f(...) + x1 f(...): factor the right-hand side to get (x1' + x1) f(...). Since x1' + x1 = 1, the expression equals f(...).
For f(x1, ..., xn) = x2 f(...) + x2' f(...): the same factoring applies: (x2 + x2') f(...) = 1·f(...) = f(...).
For f(x1, ..., xn) = xn' f(x1, x2, …, 0) + xn f(x1, x2, …, 1): this is the Shannon expansion with respect to xn. Evaluating for xn = 0 gives f(...,0); evaluating for xn = 1 gives f(...,1). Thus the right-hand side matches f for both possible values of xn, so the identity holds.
Why the listed incorrect equation fails:
The expression f(0, x2, …, xn) + f(1, x2, …, xn) does not depend on x1, so it is constant with respect to x1 for fixed x2…xn.
Counterexample: let f(x1,x2,...,xn) = x1. Then the left-hand side equals x1, while the right-hand side equals f(0,...) + f(1,...) = 0 + 1 = 1. These are not equal for all inputs, so the equation is false in general.
Conclusion: The first three equations are valid identities (trivial factoring or Shannon expansion). The equation f(x1, x2, ..., xn) = f(0, x2, …, xn) + f(1, x2, ..., xn) is not generally true.