Which one of the following well-formed formulae in predicate calculus is NOT valid? A. (forall x p(x) v forall x q(x)) -> forall x (p(x) v q(x)) B. exists x (p(x) ^ q(x)) -> (exists x p(x) ^ exists x q(x)) C. (exists x p(x) v exists x q(x)) -> exists x (p(x) v q(x)) D. forall x (p(x) v q(x)) -> (forall x p(x) v forall x q(x))

GATE 2016 · Discrete Mathematics · First Order Logic · medium

Answer: D. forall x (p(x) v q(x)) -> (forall x p(x) v forall x q(x))

1. Validate options A, B, C: A: (forall x p v forall x q) -> forall x (p v q). If every x has p, then certainly every x has p v q. Valid. B: exists x (p ^ q) -> (exists x p ^ exists x q). If some x has both, it witnesses each separately. Valid. C: (exists x p v exists x q) -> exists x (p v q). The witnessing x for whichever disjunct is true also satisfies p v q. Valid.
2. Disprove option D with a counterexample: Domain = {1, 2}. Set p(1) = T, p(2) = F, q(1) = F, q(2) = T. Check antecedent forall x (p(x) v q(x)): p(1) v q(1) = T v F = T; p(2) v q(2) = F v T = T. Antecedent holds. Check consequent (forall x p(x) v forall x q(x)): forall x p(x) = p(1) ^ p(2) = T ^ F = F; forall x q(x) = q(1) ^ q(2) = F ^ T = F; so consequent = F v F = F. The whole formula D is T -> F = F. Counterexample found.