How to prove two propositions equivalent?

Question

I was given the question:

Determine if $\exists x (P(x) \implies Q(x))$ and $\exists xP(x) \implies \exists x Q(x)$ are equivalent, i.e., always have the same truth value. If they are not equivalent figure out if one implies the other. Prove that you have correctly determined the most general logical relationship between the two expressions. Be sure to include examples if the two expressions are not equivalent.

How do I go about doing this? Would I simplify each proposition and see if they simplify to the same thing? And if they are not equivalent, how would I see if one implies the other? Thanks.

Answer 1

Let the universe be all the people on Earth, $\,P(x):=x\,$ is a mother , $\,Q(x):=x\,$ is a man, so

$$\exists\,x\left(P(x)\rightarrow Q(x)\right)=\,\text{exists a person s.t. if it is a mother then it is a man}$$

$$(\exists\,x\,P(x))\rightarrow (\exists\,x\,Q(x))=\,\text{if there exists a mother then there exists a man}$$

Do you think the above are equivalent?

Answer 2

HINTS:

1. What if $Q(x)$ is $x\ne x$, and $P$ is such that $\exists xP(x)$ and $\exists x\big(\lnot P(x)\big)$ are both true?

2. One of the propositions does imply the other.

Answer 3

I like to develop intuition with a specific universe. In this case, I take $x$ as having two values, say $0$ and $1$.

Then the first statement becomes $(\lnot P(0) \lor Q(0)) \lor (\lnot P(1) \lor Q(1))$.

The second statement becomes $(\lnot(P(0) \lor P(1)) \lor (Q(0) \lor Q(1))$.

It is straightforward to see that the assignment $P(0) = F, P(1)=T, Q(0) = F, Q(1) = F$ results in the first formula having the value $T$, while the second is $F$. Hence the formulas are not equivalent.

Rewriting the formulas as $\lnot P(0) \lor \lnot P(1) \lor Q(0) \lor Q(1)$ and $(\lnot P(0) \land \lnot P(1)) \lor Q(0) \lor Q(1)$ suggests that the second formula implies the first.

To prove this (loosely) we need only show that if the second formula is true, then so is the first.

The second formula can be true in two ways:

(1) $\exists x P(x)$ is false, in which case $\forall x \lnot P(x)$ is true, from which is follows that $\forall x (\lnot P(x) \lor Q(x))$ is true, from which we have $\forall x (P(x) \Rightarrow Q(x))$ and finally $\exists x (P(x) \Rightarrow Q(x))$ is true.

(2) $\exists x P(x)$ is true and $\exists x Q(x)$ is true. Since $\exists x Q(x)$ is true, it follows that $\exists x (\lnot P(x) \lor Q(x))$ is true, which is equivalent to $\exists x ( P(x) \Rightarrow Q(x))$.

Formalizing the proof needs more input from you...