2
$\begingroup$

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.

  • 0
    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)$.2012-07-08

2 Answers 2

5

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.

  • 0
    Much Clearer now. Thanks André.2012-07-08
2

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

  • 1
    Sorry. I'll take a look to revise it.2012-07-08