edited by
11,811 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(¬β ))$
edited by

3 Answers

Best answer
78 votes
78 votes

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
Answer:

Related questions

52 votes
52 votes
8 answers
2
Arjun asked Sep 24, 2014
13,947 views
What is the logical translation of the following statement?"None of my friends are perfect."$∃x(F (x)∧ ¬P(x))$$∃ x(¬ F (x)∧ P(x))$$ ∃x(¬F (x)∧¬P(x))$$ ¬�...
59 votes
59 votes
5 answers
3
111 votes
111 votes
9 answers
4
gatecse asked Sep 12, 2014
34,609 views
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to$15$$30$$90$$36...