Mathematical Predicate logic

Question

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) ¬∀(x)(Graph(x) ⇒ Connected(x))

(B) ∃x(Graph(x) ∧¬ Connected(x))

(C) ¬∀(¬Graph(x) v Connected(x))

(D) ∀x(Graph(x) ⇒ ¬Connected(x))

soln:- Every graph is connected ...

i.e. predicate formula

       ∀(x)(Graph(x)  ⇒ Connected(x))

Now taking negation of above statement, it will give "Not every graph is connected"

 i.e.   ¬∀(x)(Graph(x)  ⇒ Connected(x)) 

after solving getting answer ... (B). ∃x(Graph(x) ∧¬Connected(x)) But in answer booklet answer is D how ????

Answer 1

Yes, the logical expressions in A, B and C each say that "Not every graph is connected", whereas the expression in D says that every graph is disconnected. So D is the only expression not representing the given statement. The statement "not every graph is connected" means that there exists at least one disconnected graph, which is not the same as saying every graph is disconnected.

Answer 2

First of all "Not every graph is connected" means "There is atleast 1 graph which is not connected"

If you to take a closer look and apply some boolean logic like ($A \rightarrow B = ¬A \lor B$). You'll find option that option (A), (B) & (C) are same referring to "There is atleast 1 graph which is not connected"

(A) ¬∀(x)(Graph(x) ⇒ Connected(x))

(B) ∃x(Graph(x) ∧ ¬Connected(x))

(C) ¬∀x(¬Graph(x) v Connected(x))

But as we know $A \rightarrow B$ is more strict i.e. if A is true then B has to be true. Hence D refers to All graphs are disconnected.

(D) ∀x(Graph(x) ⇒ ¬Connected(x))

Hence answer will be (D) only