Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
"Equal" is not the same as "equivalent". –  Andres Caicedo Nov 2 '12 at 0:44
    
Have you tried out any concrete "examples"? "There exists something such that (if it is P, then it is Q)" vs. "if there exists something such that it is P, then there exists something such that it is Q"...I've translated generically; perhaps it's enough for you to better understand the differences (hint) between the two propositions? –  amWhy Nov 2 '12 at 0:51
    
To prove equivalence, you need to be able to derive one from the other, or "simplify" as you mention. Equivalence can also be proven by establishing that each statement implies the other. Equivalence would be the most general relationship then. If the expressions are not equivalent, you can prove this by providing a valid counterexample. Then you'd need to determine whether one of the statements implies the other (whether if one is true, the other cannot be false); if so you'd need to prove it. Implication would be the most general relationship then. –  amWhy Nov 2 '12 at 0:57
    
@AndresCaicedo I edited accordingly. –  amWhy Nov 2 '12 at 1:22

3 Answers 3

up vote 2 down vote accepted

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?

share|improve this answer
    
That makes it much more simple to understand. I would say no, they are not equivalent. But I also don't see how one would imply the either using this universe/example? –  Jakemmarsh Nov 2 '12 at 2:59

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.

share|improve this answer

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...

share|improve this answer
    
What are the rules for converting a proposition like this to ands/ors/negations? –  Jakemmarsh Nov 2 '12 at 19:57
    
Depends on your rules... –  copper.hat Nov 2 '12 at 20:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.