Which one of these first-order logic formulae is valid? A. forall x P(x) => forall x Q(x) => forall x (P(x) => Q(x)) B. exists x P(x) ^ exists x Q(x) => exists x (P(x) ^ Q(x)) C. forall x (P(x) v Q(x)) => (forall x P(x)) v (forall x Q(x)) D. forall x P(x) v Q(x) => forall x (P(x) v Q(x))

GATE 2007 · Discrete Mathematics · First Order Logic · medium

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

1. Verify option A is valid: Option A: (forall x P(x)) => ((forall x Q(x)) => (forall x (P(x) => Q(x)))). Assume forall x P(x) and forall x Q(x) both hold. Take any x: P(x) is true and Q(x) is true. Since Q(x) is true, the implication P(x) => Q(x) is true. Since x was arbitrary, forall x (P(x) => Q(x)) holds. So option A is valid.
2. Counterexample for option B, C, D: Option B: domain = {1, 2}, P(1)=T, P(2)=F, Q(1)=F, Q(2)=T. Then exists x P(x) and exists x Q(x) are both true, but exists x (P(x)^Q(x)) is false. So B is not valid. Option C: same domain, P(x): x=1, Q(x): x=2. forall x(P v Q) is T, but (forall P) v (forall Q) is F. Not valid. Option D is similarly not valid.