Quantifiers, predicates, logical equivalence
If you can prove that $(1)$ one statement implies the other AND $(2)$ vice versa, then you prove logical equivalence. That is, we show:
$(\exists x)(P(x) \rightarrow Q(x)) \implies (\forall x P(x) \rightarrow \exists x Q(x))\tag{1}$
$\forall x P(x) \rightarrow \exists x Q(x) \implies (\exists x)(P(x) \rightarrow Q(x))\tag{2}$
$(1)\to (2):$
Suppose $(\exists x)(P(x)\to Q(x))$.
Then $P(x_0)\to Q(x_0)$ for some $x_0$.
Now suppose $\forall xP(x)$. If there are no $x$, then the implication (2) is true.
Else, then clearly there is some $x_0$ such that $P(x_0)$.
Thus, $Q(x_0)$ and $\exists xQ(x)$.
So we have shown $\forall xP(x)\to \exists xQ(x)$.
$(2)\to (1):$
Now assume $\forall xP(x)\to \exists xQ(x)$.
Either (a) $\forall xP(x)$ or (b) $\lnot \forall x P(x) \equiv \exists x\neg P(x)$.
In the case of (a), $\exists xQ(x)$, that is, $Q(x_0)$ for some $x_0$ and so $P(x_0)\to Q(x_0)$.
In the case of (b), $\neg P(x_1)$ for some $x_1$
so then $P(x_1)\to Q(x_1)$.
Thus in either (a), (b), $(\exists x)(P(x)\to Q(x))$.
- That is, you have shown that $(1) \iff (2)$. Either statement is true if and only if the other is true. I.e. $(1) \equiv (2)$.
To disprove logical equivalence, it suffices to find a counter example: find any interpretation in which one of the statements is true, but the other is false.
Note that $$\forall x P(x) \rightarrow \exists xQ(x) \equiv \lnot\forall x P(x) \lor \exists xQ(x)$$ is false if and only if $\forall xP(x)$ is true, but $\exists x Q(x)$ is false. Put differently, the statement is true whenever $\forall xP(x)$ is false, and/or it is true whenever $\exists Q(x)$ is true.
Here is a late alternative proof (in a slightly different notation that I'm more familiar with): \begin{align} & \langle \forall x :: P(x) \rangle \Rightarrow \langle \exists x :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"expand $\;\Rightarrow\;$ in the simplest way possible"} \\ & \lnot \langle \forall x :: P(x) \rangle \lor \langle \exists x :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"simplify: DeMorgan on left hand side"} \\ & \langle \exists x :: \lnot P(x) \rangle \lor \langle \exists x :: Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"simplify: $\;\exists\;$ distributes over $\;\lor\;$ (since both are disjunctions)"} \\ & \langle \exists x :: \lnot P(x) \lor Q(x) \rangle \\ \equiv & \;\;\;\;\;\text{"reintroduce $\;\Rightarrow\;$"} \\ & \langle \exists x :: P(x) \Rightarrow Q(x) \rangle \\ \end{align} So these expressions are equivalent.
Hint: Use this fact that $P\to Q$ is logically equivalent to $\sim P\vee Q$. More over we know that $\sim (\exists x,~ P(x))\equiv \forall x, \sim P(x)$ and vice versa.