2
$\begingroup$

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 4

7

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

5

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.

1

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.

  • 0
    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).2011-01-14
1

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.