in Mathematical Logic edited by
6,648 views
34 votes
34 votes

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 )$
in Mathematical Logic edited by
6.6k views

7 Answers

40 votes
40 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)

edited by

4 Comments

but is the any other approach to solve this type of the question..thanks
0
0
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)$
6
6
You should include one big brace for the outer one.

Otherwise it's confusing.
0
0

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 ..

answer:D

                                                :

 

0
0
19 votes
19 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

ANSWER D
edited by

2 Comments

very nice explanation...
0
0
C on solving gives option A and not B directly
2
2
8 votes
8 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.

1 comment

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

Related questions