# Are there rules of Logic dealing with the implies operator?

I'm just beginning a course in discrete mathematics and I'm learning a few of the basic laws to prove propositions. I understand how to use propositions that use the logical connectives, AND , OR, NOT. However I'm not sure how to prove a proposition that has an implies operator. For example prove the following is a tautology.

$(p\land (p\implies q))\implies q$

-

## 4 Answers

There are two possible answers. One, your language doesn't really contain the $\implies$ operator, and it is thought of as a shorthand (as in user3123's answer): $$a \implies b \text{ is a shorthand for } \lnot a \lor b.$$ Two, your language does include it, and then you have some axioms expressing its "meaning". For example, you could have a system with only $\lnot$ and $\implies$, having the following axioms

$$A \implies (B \implies A)$$

$$(A \implies B) \implies ((B \implies C) \implies (A \implies C))$$

$$(A \implies B) \implies (\lnot B \implies \lnot A)$$

and Modus Ponens as the only inference rule: given $A$ and $A \implies B$, deduce $B$. This system is complete (can prove every true proposition). The other connectives are then shorthands:

$$A \lor B \text{ stands for } \lnot A \implies B$$

$$A \land B \text{ stands for } \lnot(\lnot A \lor \lnot B)$$

-

There's a nice shortcut to proving that something with an implies operator is a tautology. Assume it's not a tautology: the only way $a \Rightarrow b$ can be false is if $a$ is true and $b$ is false, so you can assume that, etc. and this is often a quick way to reach a contradiction.

-

Funny that you can use the logical operators and ($\land$), or ($\lor$) and not ($\lnot$) but not the imply operator as its nothing else:

$(a \implies b) \Leftrightarrow (\lnot a \lor b)$

Maybe this helps? Just replace those imply operators in your equation.

-

Is what you wrote equivalent to my proposition, just rewritten? – lampShade Jan 14 '11 at 19:56
No, I just gave you a way to translate the imply-operator into something you already know (a combination of the not and or operator). – Listing Jan 14 '11 at 19:58

You may draw a truth table, in order to investigate the alternatives (see Implication at wikipedia). In words, if $A$ and $B$ are some propositions then $A\Rightarrow B$ is a third proposition which is true if and only if $A$ is false, or both $A$ and $B$ are true.

-
{"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": 20, "mathjax_display_tex": 6, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "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.9461352825164795, "perplexity_flag": "head"}