Equivalence for quantifications

121 Views Asked by At

Considering:

(1) $(\exists x)(E(x) \land (\forall y)(E(y)\rightarrow M(x,y)))$

There are equivalences that say:
$\lnot(\forall x) A \equiv (\exists x) \lnot A$

$\lnot(\exists x) A \equiv (\forall x) \lnot A$

So, if I want to express (1) only with the "forall" quantifier I got:

(2) $\lnot(\forall x)(E(x) \rightarrow \lnot((\forall y)(E(y)\rightarrow M(x,y))))$

Is this ok? What happens with the $\lnot((\forall y)(E(y)\rightarrow M(x,y))))$ part???

Is the same as $\lnot((\forall y))\lnot((E(y)\rightarrow M(x,y)))$ ??

More over, if I want quantifiers at the start of the expression, could be (1) directly expressed as:

(3) $(\exists x)(\forall y)((E(x) \land (E(y))\rightarrow M(x,y)))$ ??

Or something can like (3) only be obtained coming from (2) ??:

$\lnot(\forall x)(\forall y)((E(x) \land (E(y))\rightarrow M(x,y)))$


EDIT: Here i go again, are the next expressions equivalent?:

  1. $(\exists x)(E(x) \land (\forall y)(E(y)\rightarrow M(x,y)))$

  2. $\lnot(\forall x)\lnot(E(x) \land (\forall y)(E(y)\rightarrow M(x,y)))$

  3. $\lnot(\forall x)(\lnot(E(x)) \lor \lnot((\forall y)(E(y)\rightarrow M(x,y))))$

  4. $\lnot(\forall x)(E(x) \rightarrow \lnot((\forall y)(E(y)\rightarrow M(x,y))))$

  5. $\lnot(\forall x)(E(x) \rightarrow \lnot((\forall y)(\lnot(E(y))\lor M(x,y))))$

  6. $\lnot(\forall x)(E(x) \rightarrow (\exists y)\lnot((\lnot(E(y))\lor M(x,y))))$

  7. $\lnot(\forall x)(E(x) \rightarrow (\exists y)(E(y)\land \lnot(M(x,y))))$

This rule is valid?: $\lnot((\forall x) A) \equiv \lnot(\forall x) A \equiv (\exists x) \lnot A$

1

There are 1 best solutions below

6
On BEST ANSWER

Both 2 and 3 are correct. 3 can be obtained from 1 directly. Not sure what the $\lnot((\forall y))\lnot((E(y)\rightarrow M(x,y)))$ means -why the double parentheses? If you ignore those, then it's just $\exists y(E(y)\rightarrow M(x,y))$, which is true, but weaker than what you started with.