Results 1 to 4 of 4

Math Help - logically equivalent

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    35

    logically equivalent

    can anyone explain to me how to prove that p → q and not q → not p are logically equivalent without truth tables
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello, questionboy!

    Prove that p\to q and \sim\!q \to \;\sim\!p are logically equivalent without truth tables

    p \to q \;\equiv\;\sim\!p \vee q . . I call it "Alternate Definition of Implication" (ADI).


    Start with the right side:

    . . \begin{array}{ccccc}<br />
\sim\!q \to \:\sim\!p & \equiv & q \:\vee \sim\!p & &\text{ADI} \\ \\<br />
& \equiv & \sim\!p \vee q && \text{Comm.} \\ \\<br />
& \equiv & p \to q && \text{ADI}<br />
\end{array}

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    10
    Hello!

    Quote Originally Posted by Soroban View Post
    Hello, questionboy!


    p \to q \;\equiv\;\sim\!p \vee q . . I call it "Alternate Definition of Implication" (ADI).


    Start with the right side:

    . . \begin{array}{ccccc}<br />
\sim\!q \to \:\sim\!p & \equiv & q \:\vee \sim\!p & &\text{ADI} \\ \\<br />
& \equiv & \sim\!p \vee q && \text{Comm.} \\ \\<br />
& \equiv & p \to q && \text{ADI}<br />
\end{array}

    You should also mention the use of Double Negation.

    Best wishes,
    Seppel
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    This is fine, but expressing p\to q as \neg p\lor q misses an important subtlety. One can define \neg p as p\to\bot where \bot denotes a contradiction (e.g., 0 = 1). Indeed, p and \neg p imply \bot by Modus Ponens, and deriving \bot from p proves \neg p by Deduction theorem (or implication introduction).

    Then \neg q\to\neg p becomes (q\to\bot)\to(p\to\bot). Now, it is surprising that this formula is implied by p\to q without using the fact that \bot is a contradiction. I.e.,

    (p\to q)\to\Big((q\to r)\to(p\to r)\Big)

    is the transitivity of \to, and it is derivable for any r using only basic rules about implication.

    This suggests that p\to q implies \neg q\to\neg p in a much stronger sense than just in Boolean logic.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. how are these two statments logically equivalent?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 3rd 2011, 09:49 PM
  2. Logically equivalent
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 20th 2010, 09:20 PM
  3. logically equivalent
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 24th 2010, 01:30 AM
  4. Replies: 5
    Last Post: September 6th 2009, 02:53 PM
  5. Logically Equivalent Statement-HELP!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 17th 2008, 10:32 AM

Search Tags


/mathhelpforum @mathhelpforum