Results 1 to 2 of 2

Math Help - Tautology problem

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    2

    Tautology problem

    So I am currently working on a problem that asks me to prove

    [(p -> q) ^ (q -> r)] -> (p -> r) is a tautology by using logical equivalences.

    I just enrolled in the course, so I don't know if this is by any means correct, but here is what I have come up with. Any assistance would be great.

    [(~p v q) ^ (~q v r)] -> (p -> r) by implication

    [(~p v q) ^ (~r v q)] -> (p -> r) contrapositive

    (~p v q) -> (p -> r) transitivity (idk if there is another term?)

    (p -> q) -> (p -> r) implication

    (q -> r) transitivity
    Follow Math Help Forum on Facebook and Google+

  2. #2
    nvv
    nvv is offline
    Newbie
    Joined
    Jan 2009
    Posts
    14
    Hi, giaky

    I'm not sure that I understand you correctly... You're not sure in your proof?
    (~p v q) -> (p -> r) transitivity (idk if there is another term?)
    I'm not sure in correctness of this operation

    Here is my proof. :

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

    [(~p v q) ^ (~q v r)] -> (~p v r) ---- by implication

    ~[(~p v q) ^ (~q v r)] v (~p v r) ---- by implication

    [~(~pvq)v~(~qvr)]v(~pvr) --- De Morgan's law

    [p^~q)v(q^~r)v(~pvr) --- De Morgan's law

    [p^q = pq ----- notation]
    [~p='p ----- notation]

    p`q v q`r v `p v r ====

    now we'll use Distributive Property: x+yz = (x+y) (x+z)
    and Basic Identity: x+x = 1

    p`q v `p = (p v `p)(`q v `p)=`q v `p
    q`r v r = (q v r)(`r v r) = q v r

    === `q v `p v q v r = `p v r = p->r

    p.s. sorry if there is misunderstanding...I'm just trying to help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. tautology problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 17th 2010, 02:43 PM
  2. Replies: 8
    Last Post: January 20th 2009, 10:49 PM
  3. tautology help
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 17th 2008, 10:09 AM
  4. Tautology
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 1st 2008, 07:17 AM
  5. Tautology
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 1st 2007, 04:02 PM

Search Tags


/mathhelpforum @mathhelpforum