Project ForgeLet 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) ¬∀x (Graph(x) ⇒ Connected(x)) (B) ∃x (Graph(x) ∧ ¬Connected(x)) (C) ¬∀x (¬Graph(x) ∨ Connected(x)) (D) ∀x (Graph(x) ⇒ ¬Connected(x))
- A¬∀x (Graph(x) ⇒ Connected(x))
- B∃x (Graph(x) ∧ ¬Connected(x))
- C¬∀x (¬Graph(x) ∨ Connected(x))
- ∀x (Graph(x) ⇒ ¬Connected(x))
Explanation
"Not every graph is connected" means ∃x(Graph(x)∧¬Connected(x)) — option (B), directly. (A) and (C) are logically equivalent to (B) (¬∀x(P⇒Q) ≡ ∃x¬(P⇒Q) ≡ ∃x(P∧¬Q), and Graph(x)⇒Connected(x) ≡ ¬Graph(x)∨Connected(x)). (D) instead says EVERY graph is disconnected — a much stronger, different claim — so it does NOT represent the original statement.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.