The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 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 (59.7k points)
edited by | 2.2k views

6 Answers

+28 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
+12 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 (16.3k 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.2k 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)
+2 votes

for option a If we take negation inside ¬∀x( Graph(x) ⟹ Connected) then ∃x( ¬Graph(x) ⟹ Connected)  which is wrong Graph(x) is premise and Connection is conclusion but in this condition premise wrong this eliminates option a

similarly for option c and option b is not bcz it means there exists some x for which graph is not connected and

option d means graph is not connected for all of x or option d which is answer

answered by Loyal (7.3k points)
edited by
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

44,200 questions
49,670 answers
65,819 users