Results 1 to 6 of 6

Math Help - Using First DeMorgan's Law to Derive the Second

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    1

    Using First DeMorgan's Law to Derive the Second

    Hi. I've been racking my brains a little longer than I anticipated on this question from section 1.2 of Velleman's "How to Prove It".

    13. Use the first DeMorgan's Law and the double negation law to derive the second DeMorgan's Law.

    After trying various starting combinations of P and Q and attempting to use the first DeMorgan's Law [(P and Q)' <-> P' or Q'], I've hit a brick wall in finding a workable starting point. Any and all help will be greatly appreciated. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by GGB1387 View Post
    Hi. I've been racking my brains a little longer than I anticipated on this question from section 1.2 of Velleman's "How to Prove It".

    13. Use the first DeMorgan's Law and the double negation law to derive the second DeMorgan's Law.

    After trying various starting combinations of P and Q and attempting to use the first DeMorgan's Law [(P and Q)' <-> P' or Q'], I've hit a brick wall in finding a workable starting point. Any and all help will be greatly appreciated. Thanks!
    They gave you the starting point. double negation.

    since you never stated what level of rigor you needed, i won't be too rigorous.

    \neg P \wedge \neg Q \Leftrightarrow \neg \neg (\neg P \wedge \neg Q)

    \Leftrightarrow \neg [\neg (\neg P \wedge \neg Q)]

    \Leftrightarrow \neg [ \neg( \neg P) \vee \neg (\neg Q)] (by the first law)

    \Leftrightarrow \neg (P \vee Q)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2011
    Posts
    18

    Re: Using First DeMorgan's Law to Derive the Second

    I came across the same problem, but produced a different derivation. Can anyone verify it?

    *below, the double arrow "<--->" is used to denote equivalent statements


    Proof:

    By hypothesis, we have (P ∧ Q) <---> P ∨ Q. If we replace each occurrance of P with P and replace each occurrance of Q with Q, we obtain: (P ∧ Q) <---> (P) ∨ (Q). This expression becomes (P ∧ Q) <---> P ∨ Q by using the double negation law on the right-hand side. Since the two expressions on either side of the double arrow are equivalent, their negations are equivalent, so (P ∧ Q) <---> (P ∨ Q). Lastly, using double negation once again: P ∧ Q <---> (P ∨ Q), as desired.
    Last edited by Syrus; November 21st 2011 at 09:28 PM. Reason: clarification
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Using First DeMorgan's Law to Derive the Second

    Yes, this is essentially the same derivation as in post #2.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2013
    From
    usa
    Posts
    1

    Re: Using First DeMorgan's Law to Derive the Second

    Math newbie here. I've been going over How To Prove It myself and came to this same question wondering how to prove it. I now feel like I know how, but I don't understand the comment above me about how the 2nd and 3rd posts are essentially the same derivation. To me, the second post is just proving the 1st law, not actually deriving the 2nd from the 1st which is what the third post seems to be doing. Any clarification would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Using First DeMorgan's Law to Derive the Second

    Quote Originally Posted by ludragon View Post
    To me, the second post is just proving the 1st law, not actually deriving the 2nd from the 1st which is what the third post seems to be doing.
    Post #2 derives

    \neg P \wedge \neg Q\iff \neg (P \vee Q)

    and post #3 derives

    P ∧ Q <---> (P ∨ Q)

    They are exactly the same.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 27th 2011, 08:19 AM
  2. DeMorgan's law help
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 7th 2009, 01:05 PM
  3. demorgan law probabilty
    Posted in the Statistics Forum
    Replies: 2
    Last Post: October 25th 2008, 02:44 PM
  4. DeMorgan's Law?
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: October 16th 2008, 12:30 PM
  5. DeMorgan's laws help
    Posted in the Advanced Algebra Forum
    Replies: 9
    Last Post: February 3rd 2008, 07:29 PM

Search Tags


/mathhelpforum @mathhelpforum