Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
Consider the following well-formed formulae: | Consider the following well-formed formulae: | ||
| − | I. $ | + | I. $\neg \forall x(P(x))$ |
| − | II. $ | + | II. $\neg \exists x(P(x))$ |
| − | III. $ | + | III. $\neg \exists x(\neg P(x))$ |
| − | IV. $ | + | 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: | + | [[Category: Mathematical Logic questions from GATE]] |
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))$.
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
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))$.
GATECSE