Results 1 to 5 of 5

Math Help - Prove a tautology without truth tables.

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    59

    Prove a tautology without truth tables.

    [ negation p and (p or q)] implies q.


    I have no idea how to start.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by lm6485 View Post
    [ negation p and (p or q)] implies q.


    I have no idea how to start.
    "not p and p" is a contradiction. What does this tell you?

    Edit: Maybe it will make more intuitive sense if you put statements in.

    "It is true that I'm not happy and that: I'm happy or rich (or both)." Do you see why this in all cases implies that "I'm rich"?

    Edit 2: Sorry didn't notice the "without truth tables" part.

    This might not be quite right, but here's my attempt

    not p and (p or q) <-> (not p and p) or (not p and q) <-> not p and q

    so we have

    not p
    q
    --------
    therefore q

    which is a tautology because the conclusion is the same as one of the premises.
    Last edited by undefined; September 6th 2010 at 06:28 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,805
    Thanks
    696
    Hello, lm6485!

    Use Distributive, Associative, DeMorgan's Law, and these:

    . . . . p \to q \;=\;\sim\!p \vee q . . ADI (Alternate Definition of Implication)

    . . \begin{array}{ccccc}p\;\wedge \sim\!p &=& f & [1] \\ \\[-4mm] p \vee f &=& p & [2] \\ \\[-4mm] p\;\vee \sim\!p &=& t & [3] \\ \\[-4mm] p \vee t &=& t & [4] \end{array}



    Prove without truth tables: . \bigg[ \sim p \wedge (p \vee q)\bigg]\;\to\;q

    \begin{array}{ccccc} \bigg[\sim\!p \wedge (p \vee q)\bigg]\;\to\;q && \text{Given} \\ \bigg[(\sim p \wedge p) \vee (\sim p \wedge q)\bigg] \;\to\;q && \text{Distributive} \\ \bigg[f \vee (\sim p \wedge q)\bigg] \;\to\;q && [1] \\ \\[-3mm]  (\sim p \wedge q) \;\to\;q && [2] \\ \\[-3mm] \sim(\sim p \wedge q) \vee q && \text{ADI} \\ \\[-3mm] (p \;\vee \sim\!q) \vee q && \text{DeMorgan} \\ \\[-3mm] p \vee (\sim\!q \vee q) && \text{Associative} \\ \\[-3mm] p \vee t && [3] \\ \\[-3mm] t && [4]\end{array}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    Prove without truth tables: \bigg[ \sim p \wedge (p \vee q)\bigg]\;\to\;q.
    Just for fun, I'm going to prove this formula from a "programmer's view".

    In the programmer's view, propositions like p, q, etc. are types like \mathsf{nat} for natural numbers, \mathsf{bool} for Booleans and \mathsf{string} for strings of characters. Next, p\to q is a function that accepts p and returns q; p\land q is a pair of p and q, and p\lor q is a disjoint union of p and q.

    I will write F for "false". Then \neg p is equivalent to p\to F. Also, F\to q is a tautology for any q. Thus, \neg p is a type such that, given p, one can produce a value of any type.

    Now, towards the proof of the formula, assume we are given \neg p\land(p\lor q). This is a pair of, first, \neg p and, second, either p or q. We need to produce q. If the second given element is q, then we are done. If it is p, then, using the first element \neg p, we can manufacture any type, including q.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1
    Quote Originally Posted by lm6485 View Post
    [ negation p and (p or q)] implies q.
    I have no idea how to start.
    Frankly, I am puzzled by this question.
    This is merely a statement of Disjunctive Syllogism, (D.S.).
    That is a standard rule of inference.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Truth Tables
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 4th 2011, 06:34 AM
  2. Tautology, truth table
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 23rd 2009, 07:12 PM
  3. Truth Tables
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 11th 2008, 01:30 PM
  4. help with truth tables
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 3rd 2006, 04:23 PM
  5. truth tables
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2006, 06:47 AM

Search Tags


/mathhelpforum @mathhelpforum