Results 1 to 2 of 2

Math Help - [SOLVED] Proof of Propositions

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    1

    [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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,867
    Thanks
    745
    Hello, GRIM!

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


    What is the best way to approach a proof based on contradiction
    for the proposition: . \bigg[(p \to q) \:\wedge \sim\! q\bigg] \to \:\sim\! p
    I use ADI (Alternate Defintion of Implication) for: . (p \to q)\:\Longleftrightarrow\:\sim\!p \vee q


    Begin with the negation of the proposition:

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

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

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

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

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

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

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

    . . . . \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.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] induction problem on set of propositions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 15th 2011, 02:44 AM
  2. Quantified Propositions to English
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 1st 2009, 03:19 AM
  3. Predicate calculus - propositions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 2nd 2009, 09:50 PM
  4. propositions and logic help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 22nd 2009, 05:57 PM
  5. Proving logic propositions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 3rd 2008, 09:22 PM

Search Tags


/mathhelpforum @mathhelpforum