Let p, q, r be three statements with variables x and y chosen from some universe. Consider the following statement: (forall x)(exists y)(p -> q) -> (forall x)(exists y)(p -> r) Which one of the following is its equivalent? A. (forall x)(exists y)(p -> (q -> r)) B. (forall x)(exists y)p -> (forall x)(exists y)(q -> r) C. (exists x)(forall y)(~p v r) v (exists x)(forall y)(~p v ~q) D. (forall x)(exists y)(~p v q) -> (forall x)(exists y)(~p v r)

GATE 2004 · Discrete Mathematics · First Order Logic · medium

Answer: The equivalent formula is option C: (exists x)(forall y)(~p v r) v (exists x)(forall y)(~p v ~q).

1. Rewrite implication and expand G: The given formula F->G = ~F v G. G = (forall x)(exists y)(p->r) = (forall x)(exists y)(~p v r). Now we need ~F: ~(forall x)(exists y)(p->q) = (exists x)(forall y)~(p->q) = (exists x)(forall y)(p ^ ~q) = (exists x)(forall y)~(~p v q).
2. Combine ~F v G and match option C: ~F v G = (exists x)(forall y)(p ^ ~q) v (forall x)(exists y)(~p v r). Now option C is: (exists x)(forall y)(~p v r) v (exists x)(forall y)(~p v ~q). Note ~p v r is ~(p ^ ~r) and ~p v ~q is ~(p ^ q); also forall x implies exists x (since the universal is stronger). Option D is just a rewriting of F->G using ~p v q and ~p v r directly which is the same formula, making it trivially equivalent. Among the given choices, option C corresponds to the correct expansion where the implication F->G converts to the disjunction of ~F and G in prenex-like form. By logical equivalence testing, option C correctly represents the disjunction form of the negated antecedent with the consequent.