# [SOLVED] Proof of Propositions

• Mar 26th 2009, 02:08 AM
GRIM
[SOLVED] Proof of Propositions
what is the best way tp approach a proof based on contradiction for the proposition

(( p=> q)^ ~q) => ~p

I would like to learn how best to atack a problem like this - ideally a step by step process so that simillar problems can be solved.

Thanks
Grim
• Mar 26th 2009, 03:15 AM
Soroban
Hello, GRIM!

I don't know if this is the best way, but . . .

Quote:

What is the best way to approach a proof based on contradiction
for the proposition: .$\displaystyle \bigg[(p \to q) \:\wedge \sim\! q\bigg] \to \:\sim\! p$

I use $\displaystyle ADI$ (Alternate Defintion of Implication) for: .$\displaystyle (p \to q)\:\Longleftrightarrow\:\sim\!p \vee q$

Begin with the negation of the proposition:

. . $\displaystyle {\color{red}\sim}\bigg(\bigg[(p\to q) \:\wedge \sim\!q\bigg] \to \:\sim\!p\bigg)$ . . . . . . . . . [1]

. . $\displaystyle \sim\bigg(\bigg[(\sim\!p \vee q)\:\wedge \sim\!q\bigg] \to \:\sim\!p\bigg)$ . . . . . . . . ADI

. . $\displaystyle \sim\bigg(\sim\bigg[(\sim\!p \vee q)\:\wedge \sim\!q\bigg] \:\vee \:\sim\!p\bigg)$ . . . . . . ADI

. . $\displaystyle \sim\bigg(\bigg[\sim(\sim\!p \vee q) \:\vee \sim\!(\sim\! q)\bigg] \vee \sim\!p\bigg)$ . . DeMorgan

. . $\displaystyle \sim\bigg(\bigg[(p \:\wedge \sim\!q) \vee q \bigg] \vee \sim\!p\bigg)$ . . . . . . . .DeMorgan

. . $\displaystyle \sim\bigg[(p \:\wedge \sim\!q) \vee (\sim\!p \vee q)\bigg]$ . . . . . . . . Associative

. . $\displaystyle \sim(p \:\wedge \sim\!q) \:\wedge \sim(\sim\!p \vee q)$ . . . . . . . . DeMorgan

. . . . $\displaystyle \underbrace{(\sim p \vee q)}_{\text{statement}} \:\wedge \:\underbrace{\sim\!(\sim\!p \vee q)}_{\text{negation}}$ . . . . . . . DeMorgan

We have a statement and its negation . . . This is always false.

Hence, our negation [1] is false
. . and the original proposition is true.