I can demonstrate P → Q but not the equivalent (¬Q→¬P)

77 Views Asked by At

I want to demonstrate that $P \to Q$ and $ \lnot Q \to \lnot P$ are equivalent, but I just can't resolve how to get from $P \to Q$ to $\lnot Q \to \lnot P$.

From $\lnot Q \to \lnot P$ to $P \to Q$:

  1. Conditional law $(\lnot Q \to \lnot P) \implies (\lnot\lnot Q \lor \lnot P)$

  2. Doble negation law $(\lnot\lnot Q \lor \lnot P) \implies Q \lor \lnot P$

  3. Finally conditional again $\lnot P \lor Q \implies P \to Q$

How can I demonstrate the opposite?

1

There are 1 best solutions below

0
On BEST ANSWER

Just reverse direction!

These are all equivalences that you are using, so you can just go the other way around:

$$P\rightarrow Q \overset{Conditional Law}{\Rightarrow} \neg P \lor Q \overset{Double Negation}{\Rightarrow} \neg \neg Q \lor \neg P \overset{Conditional Law}{\Rightarrow} \neg Q \rightarrow \neg P$$

And by the way, you may want to throw in a step to go between $\neg P \lor Q$ and $Q \lor \neg P$ using Commutation. So, doing both directions at once:

$$P\rightarrow Q \overset{Conditional Law}{\Leftrightarrow}$$

$$ \neg P \lor Q \overset{Commutation}{\Leftrightarrow} $$

$$ Q \lor \neg P \overset{Double Negation}{\Leftrightarrow} $$

$$\neg \neg Q \lor \neg P \overset{Conditional Law}{\Leftrightarrow} $$

$$\neg Q \rightarrow \neg P$$