Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question

4 Answers 4

up vote 6 down vote accepted

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) $$

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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