Which one of these first-order logic formula is valid?

Correct formula and proof: ∀x(P(x) => Q(x)) => (∀xP(x) => ∀xQ(x)) is valid.

• Proof outline: Assume both ∀x(P(x) ⇒ Q(x)) and ∀xP(x). Take an arbitrary element a of the domain. From ∀x(P(x) ⇒ Q(x)) we get P(a) ⇒ Q(a). From ∀xP(x) we get P(a). By modus ponens, Q(a). Since a was arbitrary, ∀xQ(x). Therefore (∀xP(x) ⇒ ∀xQ(x)) follows, making the whole implication true in every interpretation.

Counterexamples for the other formulas:

• Formula ∃x(P(x) ∨ Q(x)) ⇒ (∃xP(x) ⇒ ∃xQ(x)) is not valid. Counterexample: domain {c} with P(c)=true, Q(c)=false. Then ∃x(P∨Q) and ∃xP hold, but ∃xQ does not, so the implication can fail.

• Formula ∃x(P(x) ∧ Q(x)) ⇔ (∃xP(x) ∧ ∃xQ(x)) is not valid. Counterexample: domain {a,b} with P(a)=true, Q(b)=true, all other P/Q false. Then ∃x(P∧Q) is false but ∃xP ∧ ∃xQ is true.

• Formula ∀x∃y P(x,y) ⇒ ∃y∀x P(x,y) is not valid. Counterexample: domain {a,b} with P(a,a)=true and P(b,b)=true only. Then for each x there exists y (y=x) with P(x,y), so ∀x∃y P(x,y) holds, but there is no single y that works for both x=a and x=b, so ∃y∀x P(x,y) fails.

Summary: only the universal distribution of implication (the first formula) is valid; the other three fail in simple models as shown.