2k views

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(¬β ))$
edited | 2k views
0

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 +32 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 (\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 (355k points) edited by +1 awesome.. thanx a lot 0 easily Understood ...Thanxs a lot 0 Your logical statement for option D should be$\exists z(\neg\beta)\$, not that it will change the answer anyway.
+1
In the GATE overflow fullength test of GATE 2013, I marked the answer as D ..its showing incorrect Answer .

Kindly update it , @Arjun Sir.
0
Updated. Thanks for notifying.

option A

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