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]]