Results 1 to 9 of 9
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Need help with this logic question (algerbraically)

  1. #1
    Member
    Joined
    Oct 2011
    Posts
    170
    Thanks
    3

    Need help with this logic question (algerbraically)

    Question. While trying to prove a propositional logic statement, a student makes use o the following incorrect equivalence: NOT(p OR q) == NOT p OR NOT q

    Show algerbraically that the equivalence is invalid.


    Now the only thing I can think of is writting

    NOT(p AND q) expands to NOT p AND NOT q
    NOT p OR NOT q simplifies to NOT(p AND q)

    So you can see they are not the same thing, but the question is worth 8% I'm not really sure what it's asking exactly.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1781
    Awards
    1

    Re: Need help with this logic question (algerbraically)

    Quote Originally Posted by uperkurk View Post
    Question. While trying to prove a propositional logic statement, a student makes use o the following incorrect equivalence: NOT(p OR q) == NOT p OR NOT q
    Show algerbraically that the equivalence is invalid.
    Now the only thing I can think of is writting
    NOT(p AND q) expands to NOT p AND NOT q
    NOT p OR NOT q simplifies to NOT(p AND q)
    So you can see they are not the same thing, but the question is worth 8% I'm not really sure what it's asking exactly.
    What does "Show algerbraically that the equivalence is invalid." really mean?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2011
    Posts
    170
    Thanks
    3

    Re: Need help with this logic question (algerbraically)

    It's supposed to mean break it down. You can prove something is right or wrong via truth tables or algerbraically apparently. Here is a picture from some examples of "showing algebraically"
    Attached Thumbnails Attached Thumbnails Need help with this logic question (algerbraically)-untitled.png  
    Last edited by uperkurk; August 17th 2012 at 01:01 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2011
    Posts
    170
    Thanks
    3

    Re: Need help with this logic question (algerbraically)

    So any idea?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Need help with this logic question (algerbraically)

    Proofs that proceed by rewriting using logic laws can show that two expressions are equivalent, not that they are non-equivalent. The only way to show the latter is if you have two expressions about which you know that they are not equivalent. For example, it may be given that x AND y is not equivalent to x OR y or that T is not equivalent to F. If the first of these non-equivalences is known, then you may substitute NOT x for p and NOT y for q in the erroneous equation. Then, using that equation, the left-hand side is equivalent to x OR y. Using the correct De Morgan's rule, the left-hand side is equivalent to x AND y.

    A better way would be to replace p and q with truth values that make the truth-value of the left-hand side different from the truth value of the right-hand side and then reduce both sides to those truth values using logic laws. It seems that we can take for granted that T is not equivalent to F. However, this method is basically the same as using truth tables.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2011
    Posts
    170
    Thanks
    3

    Re: Need help with this logic question (algerbraically)

    Thanks, here is the actual question in full maybe this will clear things up...
    Attached Thumbnails Attached Thumbnails Need help with this logic question (algerbraically)-untitled.png  
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Need help with this logic question (algerbraically)

    That's what I am saying: the problem suggests producing a statement whose left-hand side cannot be equivalent to the right-hand side. Now, about which two expressions it is clear that they cannot be equivalent is subjective. To one person it is clear that NOT (p OR q) cannot be equivalent to (NOT p) OR (NOT q), but to another this is not obvious and he/she only knows that p AND q and p OR q are not equivalent. To a purist, the only obvious thing is that T and F are not equivalent. For this reason, I don't think the problem is well-posed. Nevertheless, I suggest choosing two expressions whose non-equivalence you can justify and then proceed by making appropriate substitutions for p and q as described in post post #5.
    Thanks from uperkurk
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Aug 2012
    From
    Delft, The Netherlands
    Posts
    11
    Thanks
    1

    Re: Need help with this logic question (algerbraically)

    Here's what I would do. I'd start re-writing the RHS \neg p\vee\neg q to get to \neg(p\wedge q) and then conclude that quite obviously, \neg(p\wedge q)\not\equiv\neg(p\vee q), since that would mean conjunction is equivalent to disjunction.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Aug 2012
    From
    Delft, The Netherlands
    Posts
    11
    Thanks
    1

    Re: Need help with this logic question (algerbraically)

    Quote Originally Posted by uperkurk View Post
    Now the only thing I can think of is writting

    NOT(p AND q) expands to NOT p AND NOT q
    NOT p OR NOT q simplifies to NOT(p AND q)
    I'm not quite sure how your argument would proceed. NOT(p AND q) does not expand to NOT p AND NOT q, but to NOT p OR NOT q. (I've given my suggestion above, btw.) And, being a logic teacher myself, I find the phrasing of this assignment ambiguous.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. logic question
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 4th 2009, 06:39 AM
  2. logic question
    Posted in the Discrete Math Forum
    Replies: 20
    Last Post: January 25th 2009, 11:51 AM
  3. Question about logic
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 5th 2008, 06:51 AM
  4. Logic Question
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: June 24th 2008, 12:24 AM
  5. Logic Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 25th 2008, 06:26 PM

Search Tags


/mathhelpforum @mathhelpforum