edited by
8,816 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

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

0 votes
0 votes

Answer will clearly be (D) as it says "for all x if x is a graph then it will not be connected" which is  false as although there are some graphs which are not connected  but this does not mean there are no connected graphs 

0 votes
0 votes
Option a, b, c are same and option D stated that “all graphs aren’t connected”.
Answer:

Related questions

37 votes
37 votes
11 answers
1
52 votes
52 votes
8 answers
2
Arjun asked Sep 24, 2014
13,962 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