in Mathematical Logic edited by
11,835 views
45 votes
45 votes

Which one of the following is NOT logically equivalent to $¬∃x(∀ y (α)∧∀z(β ))$ ?

  1. $∀ x(∃ z(¬β )→∀ y(α))$
  2. $∀x(∀ z(β )→∃ y(¬α))$
  3. $∀x(∀ y(α)→∃z(¬β ))$
  4. $∀x(∃ y(¬α)→∃z(¬β ))$
in Mathematical Logic edited by
by
11.8k views

2 Comments

It's simply based on Demorgan's law

$\sim \exists x(\forall y(\alpha )\wedge \forall z(\beta ))$

// Simply Replace $\forall$ with $\exists$ and vice versa , $\vee$ with $\wedge$ and vice versa , $P(t)$ with $\sim$$P(t)$ and vice versa.

$\equiv$ $\forall x(\exists y(\sim\alpha )\vee\exists z(\sim(\beta )))$

// like $\overline{a+b}\equiv \overline{a}  .\overline{b}$        this $\overline{\forall xP(t)} \equiv \exists x\sim P(t)$

$\equiv \forall x(\forall z(\beta )\rightarrow \exists y(\sim(\alpha )))$    -------option B matched

Let suppose $\forall z(\beta )$ is 'a' and $\exists y(\sim\alpha )$ is 'b'

So option B is like $a->b$ and option C is $\sim b -> \sim a$ , both are equivalent so hence C is also equivalent.

Option A is $\sim a -> \sim b$ which is not equivalent to $a->b$ so out

Option D is $b->\sim a$ which is also not equivalent so out.

2
2

hope you like my approach

0
0

3 Answers

78 votes
78 votes
Best answer

A useful rule: $$\forall x (\alpha) = \neg \exists (x)  (\neg \alpha) $$i.e.; If some property $\alpha$ is true for all $x$, then it is equivalent ot say that no $x$ exists such that property $\alpha$ does not hold for it.

Starting with choices:

  1. $\forall x (\exists z (\neg \beta) \to \forall y (\alpha)) $
    $\implies \forall x (\neg \exists z (\neg \beta) \vee \forall y (\alpha)) $
    $\implies \forall x (\forall z ( \beta) \vee \forall y (\alpha)) $
    $\implies \neg \exists x \neg (\forall z ( \beta) \vee \forall y (\alpha)) $
    $\implies \neg \exists x  (\neg \forall z ( \beta) \wedge \neg \forall y (\alpha)) $

    So, A is not matching with the logical statement in question.
     
  2. $\forall x (\forall z (\beta) \to \exists y (\neg \alpha)) $
    $\implies \forall x (\neg \forall z (\beta) \vee \exists y (\neg \alpha)) $
    $\implies \neg \exists x \neg(\neg \forall z (\beta) \vee \exists y (\neg \alpha)) $
    $\implies \neg \exists x (\forall z (\beta) \wedge \neg \exists y (\neg \alpha)) $
    $\implies \neg \exists x (\forall z (\beta) \wedge \forall y (\alpha)) $

    Hence, matches with the given statement.
     
  3. $\forall x (\forall y (\alpha) \to \exists z (\neg \beta)) $
    $\implies \forall x (\neg \forall y (\alpha) \vee \exists z (\neg \beta)) $
    $\implies \neg \exists x \neg(\neg \forall y (\alpha) \vee \exists z (\neg \beta)) $
    $\implies \neg \exists x (\forall y (\alpha) \wedge \neg \exists z (\neg \beta)) $
    $\implies \neg \exists x (\forall y (\alpha) \wedge \forall z (\beta)) $

    Hence, matches with the given statement.
     
  4. $\forall x (\exists y (\neg \alpha) \to \exists z (\neg \beta)) $
    $\implies \forall x (\neg \exists y (\neg \alpha) \vee \exists z (\neg \beta)) $
    $\implies \forall x (\forall y ( \alpha) \vee \exists z (\neg \beta)) $
    $\implies \neg \exists x \neg (\forall y ( \alpha) \vee \exists  z (\neg \beta)) $
    $\implies \neg \exists x  (\neg \forall y ( \alpha) \wedge \neg \exists z (\neg \beta)) $
    $\implies \neg \exists x  (\neg \forall y ( \alpha) \wedge \forall z (\beta)) $

    So, D is not matching with the logical statement in question.


Thus both (A) and (D) are not logically equivalent to the given statement.
In GATE 2013 marks were given to all for this question

edited by
by

4 Comments

Just one question about commutativity:

Can we write  ∃x(∀z(β)∧∀y(α)) as  ∃x(∀y(α)∧∀z(β)) and 

∃x(∀z(β)∨∀y(α)) as  ∃x(∀y(α)∨∀z(β)) ?

0
0
→ Yes we can write that way. @ankitrazzagmail.com

 

→ Option D should be as per commented by @Tesla!

Please, edit the answer.
0
0

D.∀x(∃y(¬α)→∃z(β))

its ∃z (¬β) in D  option.

 

1
1
11 votes
11 votes

option A 

2 Comments

Thanks a lotss ..Sir
0
0
Good method of solving through variables p and q.
0
0
0 votes
0 votes

.

Answer:

Related questions

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