GATE CS 2016 Set 2 Q27 — Propositional and First Order Logic

A formula in predicate logic is valid if it is true under every possible interpretation. Let us analyze each option to find the one that is NOT valid:

• Option A: Using the implication equivalence $A \implies B \equiv \neg A \vee B$, we can rewrite the antecedent: $$\forall_x p(x) \implies \forall_x q(x) \equiv \neg(\forall_x p(x)) \vee \forall_x q(x) \equiv \exists_x \neg p(x) \vee \forall_x q(x)$$ Since the antecedent is logically equivalent to the consequent, the formula is of the form $F \implies F$, which is always valid.
• Option B: The existential quantifier distributes over disjunction, meaning $(\exists x p(x) \vee \exists x q(x)) \equiv \exists x (p(x) \vee q(x))$. Since they are equivalent, the implication is valid.
• Option C: If there exists an object $x$ that satisfies both $p(x)$ and $q(x)$, then there exists an object satisfying $p(x)$ and there exists an object satisfying $q(x)$. Thus, the implication is valid.
• Option D: This is NOT valid. Consider a counterexample where the domain is the set of integers $\mathbb{Z}$:
  • Let $p(x)$ be "$x$ is even" and $q(x)$ be "$x$ is odd".
  • The antecedent $\forall x (p(x) \vee q(x))$ is True because every integer is either even or odd.
  • The consequent $(\forall x p(x) \vee \forall x q(x))$ is False because it is not true that all integers are even, nor is it true that all integers are odd.
  • Since $\text{True} \implies \text{False}$ is False, the formula is invalid.