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.

In a proposal, assume $p$ is the condition and $q$ the conclusion, so the proposal is $p \to q$.

Let $\neg$ be the negation on either condition or conclusion.
what is the name for the operation from $p\to q$ to $\neg p\to\neg q$? And what is the name for the operation from $p \to q$ to $p\to\neg q$? And from $p\to q$ to $\neg q\to\neg p$?

What topics in logic cover these stuffs?

In order to prove $p\to q$, is it equivalent to disprove $p\to\neg q$? Is this the so-called "proof by contradiction"? And is it equiv to prove $\neg q\to\neg p$?

Thanks and regards!

share|improve this question
add comment

2 Answers 2

up vote 5 down vote accepted

You can find a table of these on Wikipedia:

$$ \begin{array}{c|l} \hline p \to q & \text{Implication (Conditional)} \\\\ \neg p \to \neg q & \text{Inverse} \\\\ q \to p & \text{Converse} \\\\ \neg q \to \neg p & \text{Contrapositive} \\\\ \phantom\neg p \to \neg q & \text{Contradiction} \\\\ \hline \end{array} $$

Recall that $p \to q$ is equivalent to $\neg p \vee q$, Therefore (Implication ⇔ Contrapositive):

\begin{align} (p \to q) &\equiv (\neg p \vee q) \\ &\equiv (\neg\neg q \vee \neg p) \\ &\equiv (\neg q \to \neg p) \end{align}

Also, if we can disprove $p\to\neg q$, then we are sure both $p$ and $q$ are true, which is stronger than proving $p\to q$ that allows $p$ to be false. So they are not "equivalent".

share|improve this answer
add comment

Briefly, $p\rightarrow q$ can be read as "if $p$, then $q$"; "if not p then not q" would be the "inverse", and "if not q then not p" is the "contrapositive", which has the same truth value as the original proposal.

share|improve this answer
1  
Thanks! In order to prove p→q, is it equivalent to disprove p→¬q? Is this the so-called "proof by contradiction"? –  Tim Aug 21 '10 at 15:33
    
Yes, if "if p then not q" is false, it can only mean "if p then q" is true, via the law of excluded middle. –  J. M. Aug 21 '10 at 15:36
3  
J. Mangaldan's comment above is incorrect. This is an invalid application of the excluded middle; and the two statements p→q and ¬(p→¬q) are not equivalent. Because a→b is equivalent to ¬aVb (where V is "or"), the proposition ¬(p→¬q) is equivalent to ¬(¬pV¬q), which is equivalent to p&q; this implies, but is inequivalent to, p→q (which is equivalent to ¬pVq. –  Niel de Beaudrap Aug 22 '10 at 10:49
1  
Ah, so it is. I forgot to use the expansion to (not a or b). Thanks for correcting Niel! :) –  J. M. Aug 22 '10 at 10:58
add comment

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.