Difference between revisions of "GATE2009 q26"

Latest revision as of 22:32, 16 April 2015

Consider the following well-formed formulae:

I. $\neg \forall x(P(x))$

II. $\neg \exists x(P(x))$

III. $\neg \exists x(\neg P(x))$

IV. $\exists x(\neg P(x))$

Which of the above are equivalent?

(A) I and III

(B) I and IV

(C) II and III

(D) II and IV

A formula $∀x(P(x))$ is equivalent to formula $¬∃x(¬P(x))$ i.e. add $¬$ inside and outside, and convert $∀$ to $∃$.

So, $¬∀x(P(x))$ is equivalent to $∃x(¬P(x))$.

@@ Line 1: / Line 1: @@
 Consider the following well-formed formulae:
- <br>
- I. &not;&forall;x(P(x))
+ I. $\neg \forall x(P(x))$
- &nbsp;
- II. &not;&exist;x(P(x))
+ II. $\neg \exists x(P(x))$
- &nbsp;
- III. &not;&exist;x(&not;P(x))
+ III. $\neg \exists x(\neg P(x))$
- &nbsp;
- IV. &exist;x(&not;P(x))
+ IV. $\exists x(\neg P(x))$
- <br>
  Which of the above are equivalent?
- <br>
- <b>(A) </b>I and III
+(A) I and III
- &nbsp;
- <b>(B) </b>I and IV
+'''(B) I and IV'''
- &nbsp;
- <b>(C) </b>II and III
+(C) II and III
- &nbsp;
- <b>(D) </b>II and IV
+(D) II and IV
 ==={{Template:Author|Happy Mittal|{{mittalweb}} }}===
-A formula &forall;x(P(x)) is equivalent to formula &not;&exist;x(&not;P(x)) i.e. add &not; inside and outside, and
+A formula $&forall;x(P(x))$ is equivalent to formula $&not;&exist;x(&not;P(x))$ i.e. add $&not;$ inside and outside, and
- convert &forall; to &exist;.
+ convert $&forall;$ to $&exist;$.
- <br>
- So, &not;&forall;x(P(x)) is equivalent to &exist;x(&not;P(x)). So option <b>(B)</b> is correct.
+ So, $&not;&forall;x(P(x))$ is equivalent to $&exist;x(&not;P(x))$.
@@ Line 29: / Line 29: @@
 [[Category: GATE2009]]
-[[Category: Graph Theory questions]]
+[[Category: Mathematical Logic questions from GATE]]