# logically equivalent

Printable View

• March 17th 2010, 06:15 PM
questionboy
logically equivalent
can anyone explain to me how to prove that p → q and not q → not p are logically equivalent without truth tables
• March 17th 2010, 08:19 PM
Soroban
Hello, questionboy!

Quote:

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

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

. . $\begin{array}{ccccc}<br /> \sim\!q \to \:\sim\!p & \equiv & q \:\vee \sim\!p & &\text{ADI} \\ \\<br /> & \equiv & \sim\!p \vee q && \text{Comm.} \\ \\<br /> & \equiv & p \to q && \text{ADI}<br /> \end{array}$

• March 18th 2010, 12:32 AM
Seppel
Hello!

Quote:

Originally Posted by Soroban
Hello, questionboy!

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

. . $\begin{array}{ccccc}<br /> \sim\!q \to \:\sim\!p & \equiv & q \:\vee \sim\!p & &\text{ADI} \\ \\<br /> & \equiv & \sim\!p \vee q && \text{Comm.} \\ \\<br /> & \equiv & p \to q && \text{ADI}<br /> \end{array}$

You should also mention the use of Double Negation.

Best wishes,
Seppel
• March 18th 2010, 05:55 AM
emakarov
This is fine, but expressing $p\to q$ as $\neg p\lor q$ misses an important subtlety. One can define $\neg p$ as $p\to\bot$ where $\bot$ denotes a contradiction (e.g., 0 = 1). Indeed, $p$ and $\neg p$ imply $\bot$ by Modus Ponens, and deriving $\bot$ from $p$ proves $\neg p$ by Deduction theorem (or implication introduction).

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

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

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

This suggests that $p\to q$ implies $\neg q\to\neg p$ in a much stronger sense than just in Boolean logic.
All times are GMT -8. The time now is 01:23 AM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 26, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9003041982650757, "perplexity_flag": "middle"}