Are they the same formulas?

38 Views Asked by At

I was wondering if the below formulas are the same in a logical sense? Could I use the first one instead of the second and vice versa?

  1. $\forall x (P(x) \implies \exists y Q(y))$
  2. $\forall x \exists y (P(x) \implies Q(y))$
2

There are 2 best solutions below

0
On BEST ANSWER

See Prenex normal form. They are equivalent

0
On

1 implies 2: Suppose 1. If $P(x)$ is false for all x then 2 is true. Otherwise $P(x)$ is true for at least one $x_0$ hence by 1 there exists $y_0$ such that $Q(y_0)$ is true. Now let $x$, the there exists $y$ (namely $y_0$) such that $P(x)$ implies $Q(y)$ therefore 2.

2 implies 1: Suppose 2. Let $x$, then there exists $y_0$ such that $P(x)$ implies $Q(y_0)$. In particular, if $P(x)$ is true then there exists $y$ (namely $y_0$) such that $Q(y)$ is true.

Hence 1 and 2 are indeed logically equivalent.