can anyone explain to me how to prove that p → q and not q → not p are logically equivalent without truth tables

Printable View

- Mar 17th 2010, 06:15 PMquestionboylogically equivalent
can anyone explain to me how to prove that p → q and not q → not p are logically equivalent without truth tables

- Mar 17th 2010, 08:19 PMSoroban
Hello, questionboy!

Quote:

Prove that $\displaystyle p\to q$ and $\displaystyle \sim\!q \to \;\sim\!p $ are logically equivalent without truth tables

$\displaystyle p \to q \;\equiv\;\sim\!p \vee q$ . . I call it "Alternate Definition of Implication" (ADI).

Start with the right side:

. . $\displaystyle \begin{array}{ccccc}

\sim\!q \to \:\sim\!p & \equiv & q \:\vee \sim\!p & &\text{ADI} \\ \\

& \equiv & \sim\!p \vee q && \text{Comm.} \\ \\

& \equiv & p \to q && \text{ADI}

\end{array}$

- Mar 18th 2010, 12:32 AMSeppel
- Mar 18th 2010, 05:55 AMemakarov
This is fine, but expressing $\displaystyle p\to q$ as $\displaystyle \neg p\lor q$ misses an important subtlety. One can

*define*$\displaystyle \neg p$ as $\displaystyle p\to\bot$ where $\displaystyle \bot$ denotes a contradiction (e.g., 0 = 1). Indeed, $\displaystyle p$ and $\displaystyle \neg p$ imply $\displaystyle \bot$ by Modus Ponens, and deriving $\displaystyle \bot$ from $\displaystyle p$ proves $\displaystyle \neg p$ by Deduction theorem (or implication introduction).

Then $\displaystyle \neg q\to\neg p$ becomes $\displaystyle (q\to\bot)\to(p\to\bot)$. Now, it is surprising that this formula is implied by $\displaystyle p\to q$*without*using the fact that $\displaystyle \bot$ is a contradiction. I.e.,

$\displaystyle (p\to q)\to\Big((q\to r)\to(p\to r)\Big)$

is the transitivity of $\displaystyle \to$, and it is derivable for any $\displaystyle r$ using only basic rules about implication.

This suggests that $\displaystyle p\to q$ implies $\displaystyle \neg q\to\neg p$ in a much stronger sense than just in Boolean logic.