The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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. I and III
  2. I and IV
  3. II and III
  4. II and IV
asked in Mathematical Logic by Veteran (19.6k points)
edited by | 668 views

5 Answers

+10 votes
Best answer

Option B is correct.  I and IV are equivalent. 

¬∀x(P(x)) = ∃x(¬P(x))    [De morgan's Law]

Alternate approach:

Let's take an example.

Let P(x) = Student x is pass.

I→ Not all students are pass. (which means "Some students are fail")

II→There doesn't exist a student who is pass. (which means "Every student is fail")

III→There doesn't exist a student who is not pass  (which means "Every student is pass")

IV→Some students are not pass. (which means "Some students are fail")

I and IV are equivalent.

answered by Loyal (3.8k points)
selected by
+12 votes
I and IV are equal
answered by Veteran (14.3k points)
+5 votes
Do double negation of (i) which gives (iv).

Hence Option B is Ans.
answered by Veteran (23.5k points)
edited by
+1 vote

Just take negation out in iv then option i and iv is same so option b is correct

answered by Veteran (11.2k points)
+1 vote

Using De morgan's Law

answered by Boss (7.8k points)

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

34,170 questions
40,846 answers
39,703 users