The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1.9k views

$\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.5k points)
edited by | 1.9k views

6 Answers

+27 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
0
but is the any other approach to solve this type of the question..thanks
+10 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
answered by Boss (16k points)
edited by
0
very nice explanation...
+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 (60.4k points)
+3 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 (145 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 (6.6k 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)
+2
Question is for "DOES NOT"
–5
lol  i didnt read that,i am srry


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

37,999 questions
45,495 answers
131,567 comments
48,630 users