Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving De Morgan laws inductively?

  1. Sep 24, 2009 #1
    How can I prove <by induction> the following De Morgan laws are valid for all n >= 2

    - ( P(d1) ^ ... ^ P(dn) ) = ( - P(d1) ) v ... v ( - P(dn) )

    knowing that -(p^q)=(-p)v(-q) and -((p)v(q))=(-p)^(-q) ?

    I can use the inductive proof method on algebra/math theorems that have to do with variables, numbers, series, sums, etc. but I don't know what to do with propositions. Help, anyone?

    I know how to prove the De Morgan laws when it comes to sets, I can also do it by deduction, but I'm just curious as to how you'd go about doing this inductively.
  2. jcsd
  3. Sep 24, 2009 #2

    Ben Niehoff

    User Avatar
    Science Advisor
    Gold Member

    Hint: Treat the propositions as formulas in Boolean algebra and use the fact that the operators ^ and v are (individually) associative.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Proving De Morgan laws inductively?
  1. Prove De Morgan's LAw (Replies: 14)

  2. De Morgan duality (Replies: 3)

  3. Proof of de morgan law (Replies: 4)

  4. De morgan's set laws (Replies: 1)

  5. Without De Morgan's (Replies: 9)