(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
Consider the following well-formed formulae:
 
Consider the following well-formed formulae:
 
 
I. $¬∀x(P(x))$
+
I. $\neg \forall x(P(x))$
 
 
II. $¬∃x(P(x))$
+
II. $\neg \exists x(P(x))$
 
 
III. $¬∃x(¬P(x))$
+
III. $\neg \exists x(\neg P(x))$
 
 
IV. $∃x(¬P(x))$
+
IV. $\exists x(\neg P(x))$
 
 
 
Which of the above are equivalent?
 
Which of the above are equivalent?
Line 29: Line 29:
  
 
[[Category: GATE2009]]
 
[[Category: GATE2009]]
[[Category: Graph Theory questions]]
+
[[Category: Mathematical Logic questions from GATE]]

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

Solution by Happy Mittal

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))$.




blog comments powered by Disqus

Consider the following well-formed formulae:

I. $¬∀x(P(x))$

II. $¬∃x(P(x))$

III. $¬∃x(¬P(x))$

IV. $∃x(¬P(x))$

Which of the above are equivalent?

(A) I and III

(B) I and IV

(C) II and III

(D) II and IV

Solution by Happy Mittal[edit]

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))$.




blog comments powered by Disqus