in Mathematical Logic edited by
2,848 views
20 votes

Consider the following well-formed formulae:

  1. $\neg \forall x(P(x))$
  2. $\neg \exists x(P(x))$
  3. $\neg \exists x(\neg P(x))$
  4. $\exists x(\neg P(x))$


Which of the above are equivalent?

  1. $\text{I}$ and $\text{III}$
  2. $\text{I}$ and $\text{IV}$
  3. $\text{II}$ and $\text{III}$
  4. $\text{II}$ and $\text{IV}$
in Mathematical Logic edited by
by
2.8k views

1 comment

Remember negation of quantifiers-

$\neg\forall x(P(x))=\exists x(\neg P(x))$

$\neg \exists x(P(x))=\forall x(\neg P(x))$
1

Subscribe to GO Classes for GATE CSE 2022

6 Answers

18 votes
 
Best answer

Option (B) is correct.  I and IV are equivalent. 

$¬∀x(P(x)) \equiv ∃x(¬P(x))$    [De morgan's Law]

Alternate approach:

Let's take an example.

Let $P(x)\implies$  Student $x$ is pass

  • $\text{I}\;\; \implies$ Not all students are pass. (which means "Some students are fail")
  • $\text{II}\;\implies$There does not exist a student who is pass. (which means "Every student is fail")
  • $\text{III} \implies$There does not exist a student who is not pass  (which means "Every student is pass")
  • $\text{IV} \implies$Some students are not pass. (which means "Some students are fail")

I and IV are equivalent.

edited by
13 votes
I and IV are equal
5 votes
Do double negation of (i) which gives (iv).

Hence Option B is Ans.
edited by
4 votes

Using De Morgan's Law

  1. $\neg \forall x\big(P(x)\big) \equiv \exists x\big(\neg P(x) \big) $
  2. $ \neg \exists x\big( P(x) \big) \equiv \forall x\big(\neg P(x) \big)$
  3. $ \neg \exists x\big( \neg P(x) \big) \equiv \forall x\big(P(x) \big)$
  4. $ \exists x\big( \neg P(x) \big) \equiv \neg \forall x\big(P(x) \big)$

$I$ and $IV$ are equivalents.

So, the correct answer is $(B).$

edited by
1 vote

Hence (i) and (iv) are equal.

Ans (D)

0 votes
B is correct for this I and IV are equivalent.
Answer:

Related questions

Ask
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true