search
Log In
18 votes
2k views

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
in Mathematical Logic
edited by
2k views
1
Remember negation of quantifiers-

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

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

5 Answers

16 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

$I \implies$ Not all students are pass. (which means "Some students are fail")

$II\implies$There does not exist a student who is pass. (which means "Every student is fail")

$III \implies$There does not exist a student who is not pass  (which means "Every student is pass")

$IV\implies$Some students are not pass. (which means "Some students are fail")

I and IV are equivalent.


edited by
12 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
0 votes

Hence (i) and (iv) are equal.

Ans (D)

Answer:

Related questions

26 votes
6 answers
1
3.3k views
Which one of the following is the most appropriate logical formula to represent the statement? "Gold and silver ornaments are precious". The following notations are used: $G(x): x$ is a gold ornament $S(x): x$ is a silver ornament $P(x): x$ is precious $\forall x(P(x) \implies (G(x) \wedge S(x)))$ ... $\exists x((G(x) \wedge S(x)) \implies P(x))$ $\forall x((G(x) \vee S(x)) \implies P(x))$
asked Sep 15, 2014 in Mathematical Logic gatecse 3.3k views
20 votes
6 answers
2
3.4k views
The binary operation $\Box$ ... $P \vee Q$? $\neg Q \Box \neg P$ $P\Box \neg Q$ $\neg P\Box Q$ $\neg P\Box \neg Q$
asked Sep 15, 2014 in Mathematical Logic gatecse 3.4k views
33 votes
6 answers
3
3.9k views
Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or threatened. $∀x[(\text{tiger}(x) ∧ \text{lion}(x)) → {(\text{hungry}(x) ∨ \text{threatened}(x)) → \text{attacks}(x)}]$ ...
asked Sep 18, 2014 in Mathematical Logic Rucha Shelke 3.9k views
41 votes
3 answers
4
10.6k views
Consider the first-order logic sentence $\varphi \equiv \exists \: s \: \exists \: t \: \exists \: u \: \forall \: v \: \forall \: w \forall \: x \: \forall \: y \: \psi(s, t, u, v, w, x, y)$ where $\psi(s, t, u, v, w, x, y, )$ is ... size less than or equal to $3$ There exists no model of $\varphi$ with universe size of greater than $7$ Every model of $\varphi$ has a universe of size equal to $7$
asked Feb 14, 2018 in Mathematical Logic gatecse 10.6k views
...