6,794 views

Let $\text{ Graph}(x)$ be a predicate which denotes that $x$ is a graph. Let $\text{ 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 (\text{ Graph}(x) \implies \text{ Connected}(x) \Bigr )$
2. $\exists x\, \Bigl (\text{ Graph}(x) \land \lnot \text{ Connected}(x) \Bigr )$
3. $\lnot \forall x \, \Bigl ( \lnot \text{ Graph}(x) \lor \text{ Connected}(x) \Bigr )$
4. $\forall x \, \Bigl ( \text{ Graph}(x) \implies \lnot \text{ Connected}(x) \Bigr )$

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)

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)$
You should include one big brace for the outer one.

Otherwise it's confusing.

Not every graph is connected : ¬(every graph is connected)

: ¬(∀x( Graph(x)⟹ Connected(x))) (option a)

Now we can simplify above expression as below ,   ¬(∀x( ¬Graph(x)∨ Connected(x)))

Now bringing negation inside,we get   ∃x( Graph(x)∧¬ Connected(x)) (option b)

now apply double negation to the above statement as it does not change its meaning (law of double negation)..

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

now applying inner negation to all terms we get :¬∀x(¬ Graph(x)∨ Connected(x)) (option c)

Therefore option a,b,c are equivalent ..

:

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

by

very nice explanation...
C on solving gives option A and not B directly

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.

### 1 comment

4. Every graph is not connected.
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.
by