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.

The Wikipedia Link for contrapositive proofs states that proving if p then q is the same as proving if not q then not p. I don't completely follow why.

Is there any way to understand what's happening without involving logic tables ? If logic tables are inevitable, can anyone give me a basic explanation?

I can't seem to follow how if p then q gets simplified to not p or q I understand that the truth tables of the two are same. But, that's that.

share|improve this question
    
It could help to think the about contrapositive of some simple theorems, like the Pythagorean theorem. –  Ragib Zaman Jul 8 '12 at 16:43
    
Semiformally speaking: Suppose $P\implies Q$. Further suppose $Q$ is false; if $P$ were true then $Q$ would also be true and we'd have a contradiction - impossible - so $P\implies Q$ and $\lnot Q$ implies $\lnot P$, i.e. $P\implies Q$ implies $\lnot Q\implies\lnot P$, ie an implication entails its contrapositive. Of course this means the contrapositive entails the contrapositive's contrapositive, ie the original statement, hence we have an equivalence, $(P\implies Q)\iff (\lnot Q\implies \lnot P)$. –  anon Jul 8 '12 at 16:54

2 Answers 2

up vote 4 down vote accepted

The sentence "if $p$ then $q$" asserts that in every single situation (model) in which $p$ is true, $q$ must be true. The only way this can be incorrect is if we have a situation in which $p$ is true but $q$ is false. We can show this cannot be the case by showing that whenever $q$ fails, $p$ must fail, that is, by showing that if "not $q$" then "not $p$."

Conversely, suppose that in every situation in which $p$ is true, then $q$ must be true. Then there cannot be a situation in which $q$ fails and $p$ is true. So if "not $q$" holds, then "not $p$" must hold.

Thus the two assertions "if $p$ then $q$" and "if not $q$ then not $p$" hold in precisely the same cases.

Remark: The answer above is much too abstract. To understand what's going on, it is useful to examine a number of concrete cases. Suppose that we want to show that if $x^2=2$ then $x$ is not an ordinary fraction (integer divided by integer). So $p$ is the assertion $x^2=2$, and $q$ is the assertion that $x$ is not a fraction.

We prove the result by showing that if $x$ is a fraction, then $x^2$ cannot be equal to $2$, that is, by showing that "not $q$" implies "not $p$." That shows that if $x^2=2$, then $x$ could not possibly be a fraction, which is exactly what we wanted.

share|improve this answer
    
Much Clearer now. Thanks André. –  Inquest Jul 8 '12 at 17:23

"If $P$ then $Q$" tells you that whenever you know that $P$ is true, you may automatically conclude that $Q$ is true.

"If not $Q$, then not $P$" tells you that whenever you know that $Q$ is not present, you may conclude that $P$ is not present.

If ($P$ implies $Q$) is true, then knowledge of the presence of $P$ always gives us that $Q$ is present. If $Q$ isn't there, then there must be no $P$ to have put it there. Likewise, if the absence of $Q$ automatically gives us the absence of $P$, and if $P$ is present, there can be no not-$Q$ to have given us a not-$P$.

Similarly, either we have $P$ or we don't have $P$. In the case that we have $P$, we are guaranteed to have $Q$. The other case is that we don't have $P$. So we either don't have $P$, or we have $Q$ (which we got by having $P$): not-$P$ or $Q$.

On the other hand, let's say all we know is that either $P$ isn't true or $Q$ is true. If $P$ isn't true, then $P\Rightarrow Q$ is trivially true. Let's deal with the case where $P$ is true. So we know that $P$ is true and also that either $P$ isn't true or $Q$ is true. That is, since $P$ and not-$P$ can't both be true, if $P$ is true, then $Q$ is true.

share|improve this answer
    
+1. Took me a few reads to understand. The last paragraph's overall flow and structure is why most of my non-math friends don't speak to me when I'm doing math. –  Inquest Jul 8 '12 at 17:22
1  
Sorry. I'll take a look to revise it. –  Neal Jul 8 '12 at 17:26

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.