The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.1k 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(¬β ))$
asked in Mathematical Logic by Boss (18.3k points)
edited by | 2.1k 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

+34 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 (359k 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.
0
option D should be

$\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)) $
+4 votes

option A 

answered by Active (2.1k points)
0
Thanks a lotss ..Sir
0
Good method of solving through variables p and q.


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

40,879 questions
47,536 answers
146,087 comments
62,300 users