Results 1 to 4 of 4

Math Help - Show that this statement is tautology without using truth table.

  1. #1
    Newbie
    Joined
    Mar 2013
    From
    Jordan
    Posts
    4

    Question Show that this statement is tautology without using truth table.

    Hi,


    [(p -> q) ^ (q->r)] -> (p -> r)

    ??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Show that this statement is tautology without using truth table.

    What other methods besides truth tables have your course used to show that a given statement is a tautology?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,001
    Thanks
    1656

    Re: Show that this statement is tautology without using truth table.

    You can just think about what the symbols mean: If the hypothesis is true then we have both p->q and q->r true. If p is true then, from p->q, what can you say about q? And what does that tell you about r?
    Last edited by HallsofIvy; March 16th 2013 at 09:23 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,811
    Thanks
    701

    Re: Show that this statement is tautology without using truth table.

    Hello, Ammar!

    I assume we want a two-column proof.

    We have this identity: . (p\to q)\:\longleftrightarrow\:(\sim p \vee q)

    I call it Alternate Definition of Implication (ADI).


    \text{Prove: }\:\big[(p\to q) \wedge (q\to r)\big]\:\to\:(p\to r)

    \begin{array}{cccccc} 1.& \big[(p\to q)\wedge(q\to r)\big]\:\to\:(p\to r) && 1. & \text{Given} \\ 2. &\big[(\sim\!p\vee q) \wedge(\sim\!q\vee r)\big] \:\to\:(\sim\!p \vee r) && 2. & \text{ADI} \\ 3. & \sim\big[(\sim\!p \vee q) \wedge (\sim\!q\vee r)\big]\:\vee\:(\sim\!p\vee r) && 3. & \text{ADI} \\ 4. & \sim(\sim\!p\vee q) \vee \sim(\sim\!q\vee r) \vee (\sim\!p\vee r) && 4. & \text{DeMorgan} \\ 5. & (p\:\wedge \sim\!q) \vee(q\:\wedge\sim\!r) \vee\sim\!p \vee r && 5. & \text{DeMorgan} \\ 6. & \big[\sim\!p\vee(p\:\wedge\sim\!q)\big] \vee \big[r\vee(q\:\wedge\sim\!r)\big] && 6. & \text{Comm.Assoc.} \\ 7. & \big[(\sim\!p \vee p) \wedge(\sim\!p\:\vee\sim\!q) \vee \big[(r\vee q)\wedge(r\vee\sim\!r)\big] && 7. &\text{Distr.} \\ 8. & \big[t \wedge(\sim\!p\vee\sim\!q)\big] \vee \big[(r\vee q)\wedge t\big] && 8. & a\:\vee\sim\!a \,=\,t \\ 9. & (\sim\!p\:\vee \sim\!q) \vee (r\vee q) && 9. & a\wedge t \,=\,a  \end{array}
    \begin{array}{cccccc}10. & \qquad\qquad\quad \sim\!p \vee (\sim\!q \vee q) \vee r & \qquad\qquad\qquad & 10.& \text{Comm.Assoc.} \\ 11. & \qquad\qquad\sim\!p \vee t \vee r && 11. & a\:\vee \sim\!a \,=\,t \\ 12. & \qquad\qquad t && 12. & a\vee t \,=\,t  \end{array}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a tautology without truth tables.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 7th 2010, 06:37 AM
  2. Constructing a truth table from a giving statement
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: January 23rd 2010, 10:35 AM
  3. Replies: 1
    Last Post: March 27th 2009, 06:43 AM
  4. Tautology, truth table
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 23rd 2009, 07:12 PM
  5. if then statement. truth table.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 30th 2008, 08:42 PM

Search Tags


/mathhelpforum @mathhelpforum