Quantifiers, predicates, logical equivalence I am asked if $(\exists x) (P(x) \rightarrow Q(x))$ and $\forall x P(x) \rightarrow \exists xQ(x)$ are logically equivalent. 
I don't think they are but how will I prove it?
Am I supposed to use either of the direct proof, contrapositive or contradiction proofs? Or give an interpretation?
 A: 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.
A: 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.
A: 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.
A: Assume $(\exists x)(P(x)\to Q(x))$.
Thus $P(x_0)\to Q(x_0)$ for some $x_0$.
Assume $\forall xP(x)$. Then especially $P(x_0)$. Hence $Q(x_0)$ and $\exists xQ(x)$. We have thus shown $\forall xP(x)\to \exists xQ(x)$.
Assume $\forall xP(x)\to \exists xQ(x)$.
Either $\forall xP(x)$ or $\exists x\neg P(x)$.
In the first case $\exists xQ(x)$, i.e. $Q(x_0)$ for some $x_0$ and then $P(x_0)\to Q(x_0)$.
In the second case $\neg P(x_1)$ for some $x_1$ and then $P(x_1)\to Q(x_1)$.
Thus in both cases $(\exists x)(P(x)\to Q(x))$.
A: We can think about $P$ and $Q$ as subsets of the universe (an arbitrary universe), which we shall denote as $U$. This is somewhat of a semantic analysis of the sentences, which can be enlightening.
The first sentence says that either $P\neq U$ or $P\cap Q\neq\varnothing$.
The second says that if $P=U$ then $Q\neq\varnothing$.

Now we analyze whether or not these two sentences are equivalent or not.
If $P=U$ and $Q\neq\varnothing$ (the second sentence holds) then clearly $P\cap Q\neq\varnothing$, so the first sentence holds. On the other hand if $P\neq U$ then the second sentence is automatically true, and we have some $x$ such that $P(x)$ is false, and so the first sentence is also true.
The same arguments also tell us that if the first sentence holds then the second one holds as well, in one case vacuously and in another case less vacuously.
A: Yet another way to do this is with the method of analytic tableaux. It's a systematic search for contradictions, so we assume the negation of $$(\exists x(Px\to Qx))\leftrightarrow (\forall xPx\to\exists xQx)\tag{1}$$ and show that no matter what we do, we end up with a contradiction; look:
.
Can you spot the contradictions?

 From left to right: $\neg Pa$ with $Pa$, $\neg Qa$ with $Qa$, $\neg Pb$ with $Pb$, and $\neg Qc$ with $Qc$.

Hence $(1)$ is indeed an equivalence.
This method is explained in detail in M. D'Agostino's Handbook of Tableau Methods.
