Results 1 to 5 of 5

Thread: 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; Sep 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
    12,028
    Thanks
    848
    Hello, lm6485!

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

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

    . . $\displaystyle \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: .$\displaystyle \bigg[ \sim p \wedge (p \vee q)\bigg]\;\to\;q$

    $\displaystyle \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,577
    Thanks
    790
    Prove without truth tables: $\displaystyle \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 $\displaystyle p$, $\displaystyle q$, etc. are types like $\displaystyle \mathsf{nat}$ for natural numbers, $\displaystyle \mathsf{bool}$ for Booleans and $\displaystyle \mathsf{string}$ for strings of characters. Next, $\displaystyle p\to q$ is a function that accepts $\displaystyle p$ and returns $\displaystyle q$; $\displaystyle p\land q$ is a pair of $\displaystyle p$ and $\displaystyle q$, and $\displaystyle p\lor q$ is a disjoint union of $\displaystyle p$ and $\displaystyle q$.

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

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

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,774
    Thanks
    2823
    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: Feb 23rd 2009, 07:12 PM
  3. Truth Tables
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 11th 2008, 01:30 PM
  4. help with truth tables
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 3rd 2006, 04:23 PM
  5. truth tables
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 11th 2006, 06:47 AM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum