Results 1 to 3 of 3

Math Help - Proving logic propositions

  1. #1
    Math Engineering Student
    Krizalid's Avatar
    Joined
    Mar 2007
    From
    Santiago, Chile
    Posts
    3,654
    Thanks
    14

    Proving logic propositions

    I'm a little lost with this, can you guys provide full solutions?

    The following propositions are tautologies, prove each one of them without truth table.

    1) p \Rightarrow (p \vee q).

    This is \sim p \vee (p \vee q) \equiv ( \sim p \vee p) \vee q \equiv T \vee q \equiv T. (Where T is a tautology.) Is this right? When can I apply \sim p \vee (p \vee q) \equiv ( \sim p \vee p) \vee q? Only when having all \vee or \wedge?

    2) (p \Leftrightarrow q) \Leftrightarrow (p \wedge q) \vee ( \sim p \,\wedge  \sim q). I dunno how to solve this one.

    3) \left[ {(p \Leftrightarrow q) \wedge (q \Leftrightarrow r)} \right] \Rightarrow (p \iff q). I dunno how to solve this one either.

    4) \left[ {(p \wedge  \sim q) \Rightarrow  \sim p} \right] \Rightarrow (p \Rightarrow q).

    This would be \left[ { \sim (p \wedge  \sim q) \vee  \sim p} \right] \Rightarrow (p \Rightarrow q) \equiv ( \sim p \vee q \vee  \sim p) \Rightarrow (p \Rightarrow q). How do I proceed there?

    5) \sim (p \Leftrightarrow q) \Leftrightarrow ( \sim p \Leftrightarrow q). Help here too.

    6) \left[ {(p \Rightarrow  \sim q) \wedge ( \sim r \vee q) \wedge r} \right] \Rightarrow  \sim p. Another help here.

    7) \left[ {p \wedge (p \Rightarrow q)} \right] \Rightarrow q.

    We have \left[ {p \wedge ( \sim p \vee q)} \right] \Rightarrow q \equiv (p \wedge  \sim p) \vee (p \wedge q) \Rightarrow q. What's next?

    8) (p \wedge q) \Leftrightarrow \left[ {(p \vee q) \wedge (p \Leftrightarrow q)} \right]. Help here again

    9) (p \wedge q \Rightarrow r) \Leftrightarrow (p \wedge  \sim r \Rightarrow  \sim q). Need help here too.

    That's it, I'm lost with this, I hope you can help me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1
    By in large, this list of equivalences is asking you to reinvent the wheel.
    It is my impression that you have access to a reasonable Library.
    You need to get yourself a good basic symbolic logic textbook.
    I like the books by I.M.Copi. There are others: look for Michael Resnik or Benson Mates.

    Your problem #1 is simply known as Addition in the rules of inference.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    What is the Biconditional equivalence that they have allowed you to use? For example, my book has a list of 4:

    p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p) This is #3

    p \leftrightarrow q \equiv \sim p \leftrightarrow \sim q

    p \leftrightarrow q \equiv (p \wedge q) \vee (\sim p \wedge \sim q) This is #2

     \sim (p \leftrightarrow q) \equiv p \leftrightarrow \sim q

    I doubt they want you to just say that they are equal. So they must have one of these in particular that they want you to use when doing proofs. (sort of like how if you need to find a the derivative of x^2 with limits, you would need lim_(h -> 0) [f(x+h) -f(x)]/h. And you would get into trouble if you used the power rule to just say 2x. I get the feeling that using these methods is like the power rule, but we are supposed to use the limit definition, but unfortunately I'm not sure how it is defined for you, so if you can tell me how you were told to convert biconditional statements, I'll take another look)
    Quote Originally Posted by Krizalid View Post
    1) p \Rightarrow (p \vee q).
    ~p V (p V q) ...By Implication

    = (~p V p) V q ...By Associative laws

    = T V q ...By Negation laws

    = T ...By Domination laws

    Quote Originally Posted by Krizalid View Post
    When can I apply \sim p \vee (p \vee q) \equiv ( \sim p \vee p) \vee q? Only when having all \vee or \wedge?
    My Discrete Mathematics book has two examples for Associative laws:
    (p V q) V r = p V (q V r)
    (p ^ q) ^ r = p ^ (q ^ r)

    You could probably think of them as addition and multiplication:
    (a*b)*c = a*(b*c)
    (a+b)+c = a+(b+c)
    But you cannot mix them together.


    Quote Originally Posted by Krizalid View Post
    4) \left[ {(p \wedge  \sim q) \Rightarrow  \sim p} \right] \Rightarrow (p \Rightarrow q).

    This would be \left[ { \sim (p \wedge  \sim q) \vee  \sim p} \right] \Rightarrow (p \Rightarrow q) \equiv ( \sim p \vee q \vee  \sim p) \Rightarrow (p \Rightarrow q). How do I proceed there?
    from
    \equiv  ( (\sim p \vee q) \vee  \sim p) \Rightarrow (p \Rightarrow q)

    \equiv ( (\sim p \vee  \sim p)\vee q)  \Rightarrow (p \Rightarrow q) ...By associative laws

    \equiv ( \sim p \vee q) \Rightarrow (p \Rightarrow q) ...By Idempotent laws

    \equiv (p \Rightarrow q) \Rightarrow (p \Rightarrow q) ...By Implication

    \equiv \sim (p \Rightarrow q) \vee (p \Rightarrow q) ...By Implication Edit: I accidentally typed a tilde instead of \sim on this, this step should be ~(p->q) V (p->q)

    \equiv T ...By Negation laws


    Quote Originally Posted by Krizalid View Post
    6) \left[ {(p \Rightarrow  \sim q) \wedge ( \sim r \vee q) \wedge r} \right] \Rightarrow  \sim p. Another help here.
    \left[ {(p \Rightarrow  \sim q) \wedge ( \sim r \vee q) \wedge r} \right] \Rightarrow  \sim p. ...premise

    \equiv \left[ {(q \Rightarrow  \sim p) \wedge ( \sim r \vee q) \wedge r} \right] \Rightarrow  \sim p. ...By contraposition

    \equiv \left[ {(q \Rightarrow  \sim p) \wedge ( r \Rightarrow q) \wedge r} \right] \Rightarrow  \sim p. ...By implication

    \equiv \left[ {(q \Rightarrow  \sim p) \wedge q} \right] \Rightarrow  \sim p. ...By Modus Ponens of "r" and "r->q"

    \equiv \sim p \Rightarrow  \sim p. ...By Modus Ponens of "q" and "q->~p"

    \equiv p \vee \sim p. ...By implication

    =T ...By Negation laws


    Edit theres actually an easier way for this one:
    \left[ {(p \Rightarrow  \sim q) \wedge ( \sim r \vee q) \wedge r} \right] \Rightarrow  \sim p. ...premise

    \left[ {(p \Rightarrow  \sim q) \wedge q} \right] \Rightarrow  \sim p. ...disjunctive syllogism of "r" and "~r V q"

    \sim p \Rightarrow  \sim p. ...modus tollens of "p->q" and "~q"

    and now we're on the second to last step of the above proof

    One thing about these, is we didn't do them in this format, we would be given several premises and have to take them to a conclusion. So the steps were not sequential like this, I guess I'm improvising a bit. For example, in this last proof as I didn't need steps any more I took them out (ie making "(p->q)^~q" into "~p") But really, taking them out should have been it's own step called "simplification" But I just wasn't sure how to do that in the format that I was working with, so I kind of improvised. I'm not sure if that will be acceptable for your instructor.
    Last edited by angel.white; April 4th 2008 at 08:10 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving identity using laws of logic help?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 23rd 2011, 03:21 PM
  2. Proving a Theorem (Predicate Logic)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 13th 2011, 04:57 AM
  3. Replies: 3
    Last Post: September 17th 2010, 10:46 AM
  4. propositions and logic help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 22nd 2009, 05:57 PM
  5. Logic & Propositions & Proofs
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: September 9th 2008, 10:45 AM

Search Tags


/mathhelpforum @mathhelpforum