Which of the following is a valid first order formula? (Here alpha and beta are first order formulae with x as their only free variable.) A. ((forall x) alpha -> (forall x) beta) -> (forall x)(alpha -> beta) B. (forall x) alpha -> (exists x) alpha /\ beta C. ((forall x) alpha \/ beta) <-> (exists x)(alpha \/ beta) D. (forall x)(alpha -> beta) -> ((forall x) alpha -> (forall x) beta)

GATE 2003 · Discrete Mathematics · First Order Logic · medium

Answer: D. (forall x)(alpha -> beta) -> ((forall x) alpha -> (forall x) beta)

1. Verify option D: Universal distribution axiom: Assume forall x (alpha(x)->beta(x)) is true, and assume forall x alpha(x) is true. For any element a in the domain: alpha(a) is true (by forall x alpha) and alpha(a)->beta(a) is true (by forall x (alpha->beta)), so by modus ponens beta(a) is true. Since a was arbitrary, forall x beta(x) is true. Hence D is valid.
2. Falsify option A with a counterexample: Domain = {1,2}. Let alpha(x) be x=1, beta(x) be x=2. Then forall x alpha is false (2 does not satisfy x=1), so the antecedent (forall x alpha)->(forall x beta) is vacuously true. But forall x(alpha->beta) requires: for x=1, alpha(1)=true and beta(1)=false (since 1 != 2), so alpha->beta is false for x=1. Hence forall x(alpha->beta) is false. So A's antecedent is true and consequent is false: A is not valid.