1
$\begingroup$

I've discovered that many theorems in mathematics are often in forms: $$P\implies Q$$

I've also discovered that usually $\lnot Q\implies \lnot P$, if $P \implies Q$ is a theorem and I'm interested if this is always the case. So in language of mathematical logic, is the following statement always true: $$(P\implies Q)\implies (\lnot Q\implies \lnot P)$$

$\endgroup$
  • 4
    $\begingroup$ More strongly, they are equivalent. One is called the contrapositive of the other. $\endgroup$ – Simon S Nov 13 '14 at 22:15
  • 1
    $\begingroup$ Try to build the truth table for $P\to Q$ and for $\lnot Q\to \lnot P$ and deduce that these two formulas are equivalent. $\endgroup$ – TZakrevskiy Nov 13 '14 at 22:15
8
$\begingroup$

Informally, $P\Rightarrow Q$ is false when $P$ is true and $\neg Q$ is true. $\neg Q\Rightarrow\neg P$ is false when $\neg Q$ is true and $\neg(\neg P)=P$ is true. And so they're equivalent

Formally, using a truth table:

$$\begin{array}{|c|c|c|}\hline P & Q & \color{}{P\Rightarrow Q} & \neg P & \neg Q & \color{}{\neg Q\Rightarrow\neg P}&\color{}{(P\Rightarrow Q)\Rightarrow(\neg Q\Rightarrow P)}\\ \hline \color{green}1&\color{green}1&\color{green}1&\color{#C00}0&\color{#C00}0&\color{green}1&\color{green}1\\ \hline \color{green}1&\color{#C00}0&\color{green}1&\color{#C00}0&\color{green}1&\color{green}1&\color{green}1\\ \hline \color{#C00}0&\color{green}1&\color{#C00}0&\color{green}1&\color{#C00}0&\color{#C00}0&\color{green}1\\ \hline \color{#C00}0&\color{#C00}0&\color{green}1&\color{green}1&\color{green}1&\color{green}1&\color{green}1\\ \hline \end{array}$$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Along the lines of Simon S's proof...

$[P\implies Q]\equiv \neg[P \land \neg Q]$

$[\neg Q\implies \neg P]\equiv \neg[\neg Q \land \neg\neg P] \equiv \neg[\neg Q \land P]\equiv \neg[P \land \neg Q] $

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

As commented on above, the two statements are logically equivalent. Here's a proof:

$$ \begin{align*} (P\Rightarrow Q) & \Leftrightarrow \lnot(P\land\lnot Q)\\ & \Leftrightarrow \lnot\lnot\lnot(P\land\lnot Q) \\ & \Leftrightarrow\lnot\lnot(Q\lor\lnot P) \\ & \Leftrightarrow\lnot(\lnot Q\land\lnot\lnot P) \\ & \Leftrightarrow (\lnot Q \Rightarrow \lnot P) \end{align*} $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.