GATE CS 2007 Q22 — Propositional and First Order Logic

Let us denote the predicates as follows:

• $G(x)$: $x$ is a graph
• $C(x)$: $x$ is connected

The English statement "Not every graph is connected" can be translated step-by-step:

1. "Every graph is connected" is represented as: $$\forall x \, \bigl( G(x) \implies C(x) \bigr)$$
2. "Not every graph is connected" is the negation of the above statement: $$\lnot \forall x \, \bigl( G(x) \implies C(x) \bigr)$$ This directly matches Option A.

Let us analyze the equivalence of the other options:

• Option B: Using the equivalence $P \implies Q \equiv \lnot P \lor Q$ and De Morgan's laws for quantifiers: $$\lnot \forall x \, \bigl( G(x) \implies C(x) \bigr) \equiv \exists x \, \lnot \bigl( G(x) \implies C(x) \bigr)$$ $$\equiv \exists x \, \lnot \bigl( \lnot G(x) \lor C(x) \bigr)$$ $$\equiv \exists x \, \bigl( G(x) \land \lnot C(x) \bigr)$$ This matches Option B (which translates to: "There exists some $x$ which is a graph and is not connected").
• Option C: Replacing the implication with its disjunctive form in Option A: $$\lnot \forall x \, \bigl( G(x) \implies C(x) \bigr) \equiv \lnot \forall x \, \bigl( \lnot G(x) \lor C(x) \bigr)$$ This matches Option C.
• Option D: The statement is: $$\forall x \, \bigl( G(x) \implies \lnot C(x) \bigr)$$ This translates to: "Every graph is disconnected" (or "No graph is connected"), which is a much stronger statement and is not logically equivalent to "Not every graph is connected".

Therefore, Option D does not represent the given statement.