edited by
8,817 views
43 votes
43 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 )$
edited by

8 Answers

Best answer
52 votes
52 votes

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

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

Related questions

37 votes
37 votes
11 answers
1
52 votes
52 votes
8 answers
2
Arjun asked Sep 24, 2014
13,963 views
What is the logical translation of the following statement?"None of my friends are perfect."$∃x(F (x)∧ ¬P(x))$$∃ x(¬ F (x)∧ P(x))$$ ∃x(¬F (x)∧¬P(x))$$ ¬�...
50 votes
50 votes
4 answers
3