# logic operations on proposals

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!

-

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

-

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.

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