2
$\begingroup$

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!

2 Answers 2

5

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

2

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.

  • 1
    Thanks! In order to prove p→q, is it equivalent to disprove p→¬q? Is this the so-called "proof by contradiction"?2010-08-21
  • 0
    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.2010-08-21
  • 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.2010-08-22
  • 1
    Ah, so it is. I forgot to use the expansion to (not a or b). Thanks for correcting Niel! :)2010-08-22