Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x. A. forall x (p(x) v W) == forall x (p(x)) v W B. exists x (p(x) ^ W) == exists x (p(x)) ^ W C. forall x (p(x) -> W) == forall x (p(x)) -> W D. exists x (p(x) -> W) == forall x (p(x)) -> W

GATE 2020 · Discrete Mathematics · First Order Logic · medium

Answer: Option C is the formula that is NOT logically valid.

1. Validate A, B, D using constant-W laws: A and B are direct distribution laws of forall over v and exists over ^ when W has no free x; both valid. For D, rewrite exists x (p(x) -> W) = exists x (not p(x) v W) = (exists x not p(x)) v W = not(forall x p(x)) v W = (forall x p(x)) -> W; valid.
2. Show C fails by a counterexample: The correct law is forall x (p(x) -> W) == (exists x p(x)) -> W, NOT (forall x p(x)) -> W. Counterexample for C: domain {a,b} with p(a) true, p(b) false, W false. LHS forall x (p(x) -> W): for x=a, p(a)->W = (T->F) = F, so LHS = F. RHS (forall x p(x)) -> W = (F) -> F = T. Since F != T, C is not valid.