Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: "Not every graph is connected"? A. ~forall x (Graph(x) -> Connected(x)) B. exists x (Graph(x) ^ ~Connected(x)) C. ~exists x (Graph(x) ^ ~Connected(x)) D. forall x (Graph(x) -> ~Connected(x))

GATE 2007 · Discrete Mathematics · First Order Logic · easy

Answer: D. forall x (Graph(x) -> ~Connected(x)) does NOT represent 'not every graph is connected'

1. Translate target statement: 'Not every graph is connected' = ~forall x (Graph(x) -> Connected(x)) = exists x (Graph(x) ^ ~Connected(x)). Options A and B match.
2. Evaluate option C: ~exists x (Graph(x) ^ ~Connected(x)) = forall x (Graph(x) -> Connected(x)) which means 'every graph is connected' — the OPPOSITE of the target statement. C does not represent it.
3. Evaluate option D: forall x (Graph(x) -> ~Connected(x)) means 'every graph is disconnected' — also not the same as 'not every graph is connected' which only requires at least one disconnected graph. Answer: D.