1

$\forall x (P(x)\rightarrow Q(x))$ is logically equivalent to $(\exists x P(x)\rightarrow\exists y Q(y))$

The proofs I've seen use logical reasoning to prove the equivalence.
Can someone supply a proof using the laws of boolean algebra?

EggHead
  • 667

1 Answers1

3

The two sentences are not logically equivalent. The sentence $\exists x P(x) \longrightarrow \exists y Q(y)$ is true in the natural numbers, if $P(x)$ says $x$ is odd, and $Q(y)$ says that $y$ is prime. The sentence $\forall x(P(x)\longrightarrow Q(x))$ is not.

Additionally, one cannot in general expect tools from Boolean algebra to deal with non-trivial assertions that involve quantification.

André Nicolas
  • 507,029
  • My mistake. It should have been logically implies. The factoring of the quantifiers from $\exists x,P(x) \rightarrow \exists y,Q(y)$
    could produce either $\forall x, \exists y(P(x)\rightarrow Q(y))$ or $\exists y, \forall x, (P(x)\rightarrow Q(y))$ In general $\forall x, \exists y$ is not equivalent to $\exists y, \forall x$. But in this case, it happens to be?     – EggHead Nov 23 '13 at 15:00