Results 1 to 9 of 9

Math Help - Having problem with these 2 Tautology? (This is due today at 9am)

  1. #1
    Member
    Joined
    Jan 2009
    Posts
    93

    Having problem with these 2 Tautology? (This is due today at 9am)

    Q: Show that each condition statement is a tautology without using a truth table?
    a.)


    b.)


    Heres the laws that I have to use:

    http://www.plu.edu/~sklarjk/245s07/logequiv.pdf
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by Grillakis View Post
    Q: Show that each condition statement is a tautology without using a truth table?
    a.)


    b.)


    Heres the laws that I have to use:

    http://www.plu.edu/~sklarjk/245s07/logequiv.pdf
    a) By the Distributive Law (number 3 on the list):

    \neg p \wedge (p\wedge q)

    Becomes:

    (\neg p \wedge p)\vee(\neg p \wedge q)

     (\neg p \wedge p) is always false! They can't both be true simultaneously. Hence for the entire statement to be true, the (\neg p \wedge q) part must be true. If this is true, then it says that \neg p is true, and so is q. Which certainly implies that  q is true.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2009
    Posts
    93
    Quote Originally Posted by Mush View Post
    a) By the Distributive Law (number 3 on the list):

    \neg p \wedge (p\wedge q)

    Becomes:

    (\neg p \wedge p)\vee(\neg p \wedge q)

     (\neg p \wedge p) is always false! They can't both be true simultaneously. Hence for the entire statement to be true, the (\neg p \wedge q) part must be true. If this is true, then it says that \neg p is true, and so is q. Which certainly implies that  q is true.
    ok I see what you talking about for part a. But what about part b b/c you have implication (-->) in the equations?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by Grillakis View Post
    ok I see what you talking about for part a. But what about part b b/c you have implication (-->) in the equations?
     p \to q is the same as saying  \neg p \vee q .

    So you can write it as :

     (\neg p \vee q)\wedge(\neg q \vee r )
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jan 2009
    Posts
    93
    Quote Originally Posted by Mush View Post
     p \to q is the same as saying  \neg p \vee q .

    So you can write it as :

     (\neg p \vee q)\wedge(\neg q \vee r )
    I see.....

    I have one last question and was wondering if you can tell me if I used the right law for this.

    Q: Show that ( p → q ) ^ ( p → r ) and p → ( q ^ r ) are logically equivalent?
    A:
    ( p → q ) ^ ( p → r ) ≡ ( p v q ) ^ ( p v r ) Implication
    ≡ p v ( q ^ r ) 1st Distributive Law
    p → (q ^ r ) Double Negation
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    Quote Originally Posted by Grillakis View Post
    I see.....

    I have one last question and was wondering if you can tell me if I used the right law for this.

    Q: Show that ( p → q ) ^ ( p → r ) and p → ( q ^ r ) are logically equivalent?
    A:
    ( p → q ) ^ ( p → r ) ≡ ( p v q ) ^ ( p v r ) Implication
    ≡ p v ( q ^ r ) 1st Distributive Law
    p → (q ^ r ) Double Negation
    Yes that's fine.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jan 2009
    Posts
    93
    awesome....thank you Mush
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Oct 2008
    Posts
    71
    Quote Originally Posted by Grillakis View Post
    Q: Show that each condition statement is a tautology without using a truth table?
    a.)


    b.)


    Heres the laws that I have to use:

    http://www.plu.edu/~sklarjk/245s07/logequiv.pdf
    Grillakis here is aproof based on the rules you where given ,apart the law material implication .


    [~p^(pvq)] ------->q <=====>(is equivalent) ~[~p^(pvq)]vq, using material implication law.


    ~[~p^(pvq)]vq <=====> [pv~(pvq)]vq ,by using De Morgan


    [pv~(pvq)]vq <======> qv[pv~(qvp)] ,by using commutativity twice


    qv[pv~(qvp)] <======> (qvp)v~(qvp), by using associativity



    (qvp)v~(qvp) <======> t , by using negation laws


    I am sorry i have not figured out yet question (b)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jan 2009
    Posts
    93
    Quote Originally Posted by archidi View Post
    Grillakis here is aproof based on the rules you where given ,apart the law material implication .


    [~p^(pvq)] ------->q <=====>(is equivalent) ~[~p^(pvq)]vq, using material implication law.


    ~[~p^(pvq)]vq <=====> [pv~(pvq)]vq ,by using De Morgan


    [pv~(pvq)]vq <======> qv[pv~(qvp)] ,by using commutativity twice


    qv[pv~(qvp)] <======> (qvp)v~(qvp), by using associativity



    (qvp)v~(qvp) <======> t , by using negation laws


    I am sorry i have not figured out yet question (b)
    thats alright Archidi....thanks for your guys is help. I tried to figure this out and I handed in the paper.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Today's Putnam Problem of the Day
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: May 19th 2010, 04:39 AM
  2. tautology problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 17th 2010, 01:43 PM
  3. Today's problem that I don't understand.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 6th 2009, 10:39 AM
  4. Tautology problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 21st 2009, 01:47 PM
  5. Replies: 2
    Last Post: April 30th 2008, 10:12 AM

Search Tags


/mathhelpforum @mathhelpforum