The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 votes

$\def\graph{\text{ Graph}}
\def\connected{\text{ Connected}}$

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:

$\qquad\text{"Not every graph is connected"}$

  1. $\lnot \forall x\, \Bigl (\graph(x) \implies \connected(x) \Bigr )$
  2. $\exists x\, \Bigl (\graph(x) \land \lnot \connected(x) \Bigr )$
  3. $\lnot \forall x \, \Bigl ( \lnot \graph(x) \lor \connected(x) \Bigr )$
  4. $\forall x \, \Bigl ( \graph(x) \implies \lnot \connected(x) \Bigr )$
asked in Mathematical Logic by Veteran (52k points)
edited by | 2.5k views

5 Answers

+32 votes
Best answer

D says "all graphs are not connected"  but the question says " not every graph is connected" .i.e " there exists at least one graph which is not connected". Hence the answer is (D)

answered by Active (2.6k points)
edited by
but is the any other approach to solve this type of the question..thanks
It is negation of "every graph is connected".

So it should $\neg \forall x\;(G(x) \rightarrow C(x))$

$\equiv \neg \forall x\;(\neg G(x) \vee C(x))$

$\equiv \exists x\;(G(x)\wedge \neg C(x)$
+14 votes
Just writing to simplify each options

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

it is not the case that every graph then it will be connected,which implies that

some graph my be disconnected.

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

there exists some graph which are disconnected which implies

not every graph is connected.

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

here no need to express it in english just solve first using

de morgn's law we will get it as option B)


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

for all graph it is always disconnected...makes it FALSE

answered by Boss (15.9k points)
edited by
very nice explanation...
C on solving gives option A and not B directly
+6 votes

1. No graph is disconnected.

2. Some disconected graphs.

3. same for of previous option just do ~ operation on it.

4. Not every graph is connected.

answered by Veteran (61.4k points)
+4 votes
If you see each options A,B,C are same only i.e

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

   = ¬∀x( ~Graph(x) ∨ Connected(x))

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

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

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

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

So obviously D will be correct.
answered by (163 points)
0 votes

Option B is correct

Option D is incorrect as it means Every graph is not connected which is different from Not every graph is connected

Not every graph is connected
It can be rewritten as:

There is a graph which is not connected

so    ∃x(graph(x) ⋀ ¬connected(x)

or another way to do it ,simply:

¬∀x(graph(x) → connected(x))

∃x¬(graph(x) → connected(x))        (negation rule)

∃x¬(¬(graph(x) ⋁ connected(x))

And finally

∃x(graph(x) ⋀ ¬connected(x))

answered by (67 points)
Question is for "DOES NOT"
lol  i didnt read that,i am srry

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,084 answers
70,994 users