The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.5k views

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

 

(A) $∀ x(∃ z(¬β )→∀ y(α))$

(B) $∀x(∀ z(β )→∃ y(¬α))$

(C) $∀x(∀ y(α)→∃z(¬β ))$

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

asked in Mathematical Logic by Veteran (14.6k points)
retagged by | 1.5k views

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 Answers

+27 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:

A: $\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.

B: $\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.

C.  $\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.

D: $\forall x (\exists y (\neg \alpha) \to \exists z (\beta)) $

$\implies \forall x (\neg \exists y (\neg \alpha) \vee \exists z (\beta)) $

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

$\implies \neg \exists x \neg (\forall y ( \alpha) \vee \exists z (\beta)) $

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

$\implies \neg \exists x  (\neg \forall y ( \alpha) \wedge \forall z (\neg \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

answered by Veteran (332k points)
selected by
awesome.. thanx a lot
easily Understood ...Thanxs a lot
Your logical statement for option D should be $\exists z(\neg\beta)$, not that it will change the answer anyway.
+2 votes

option A 

answered by Active (2.1k points)
Thanks a lotss ..Sir


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

32,330 questions
39,146 answers
108,244 comments
36,501 users