Results 1 to 6 of 6

Math Help - is this expression a tautology?

  1. #1
    Member
    Joined
    Jun 2007
    Posts
    77

    is this expression a tautology?

    Show that this is a tautology without creating a truth table (changing logical expression)

    (p v q) ^ (-p v r) implies (q v r)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2007
    Posts
    77
    anyone? to prove that this is a tautology then (q v r) must be true right? but how do I proof this?
    Last edited by EquinoX; June 11th 2007 at 10:45 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    \left( {p \vee q} \right) \equiv \left( { \sim q \to p} \right).
    \left( { \sim p \vee r} \right) \equiv (p \to r)

    Thus from the given:
     \left( {p \vee q} \right) \wedge \left( { \sim p \vee r} \right) \equiv \left( { \sim q \to p} \right) \wedge \left( {p \to r} \right) \equiv \left( { \sim q \to r} \right) \equiv \left( {q \vee r} \right)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2007
    Posts
    77
    what I am confused here is that how do you proof:

    (~q -> p) ^ (p -> r) is equivalent to (~q-> r)
    Last edited by EquinoX; June 11th 2007 at 11:08 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    That is a hypothetical syllogism.
    Why were you given these problems to do if you donít know the basics?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,676
    Thanks
    608
    Hello, EquinoX!

    I found a proof . . . but there must be a better way . . .


    Show that this is a tautology without creating a truth table:
    . . (p \lor q) \land (\sim p \lor r) \rightarrow (q \lor r)
    Recall that: . u \rightarrow v \;\;\equiv\;\;\sim u \lor v . (def. implication)

    Hence: . \begin{array}{cccccc}p \lor q & \equiv & \sim p \rightarrow q  & & &\\<br />
\sim p \lor r & \equiv & p \rightarrow r & \equiv & \sim r \rightarrow\,\sim p & \text{(contrapositve)}\end{array}

    The left side becomes: . (\sim r \rightarrow\,\sim p) \land (\sim p \rightarrow q)\;\;\equiv\;\;\sim r \rightarrow q\;\;\;\text{(syllogism)}

    Then: . \sim r \rightarrow q \;\;\equiv\;\;q \lor r . (def. implication)


    Ha! . . . Plato beat me to it!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. tautology
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 6th 2010, 09:24 AM
  2. tautology help
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 17th 2008, 09:09 AM
  3. Tautology
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 1st 2008, 06:17 AM
  4. Tautology
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 1st 2007, 03:02 PM
  5. tautology
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 19th 2007, 06:17 PM

Search Tags


/mathhelpforum @mathhelpforum