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

Proving the Demorgan Law

  1. Jan 28, 2009 #1
    1st Demorgan Law
    A-(B[tex]\cup[/tex]C) = (A-B)[tex]\cap[/tex](A-C)

    I tried this..
    ={x: x[tex]\in[/tex]A, x[tex]\notin[/tex](B[tex]\cup[/tex]C)}
    ={x: x[tex]\in[/tex]A, x[tex]\notin[/tex]B OR x[tex]\notin[/tex]C}
    ={x: x[tex]\in[/tex]A, x[tex]\notin[/tex]B AND x[tex]\in[/tex]A, x[tex]\notin[/tex]C}

    2nd Demorgan Law
    A-(B[tex]\cap[/tex]C) = (A-B)[tex]\cup[/tex](A-C)

    ={x: x[tex]\in[/tex]A, x[tex]\notin[/tex](B[tex]\cap[/tex]C)}
    ={x: x[tex]\in[/tex]A, x[tex]\notin[/tex]B AND x[tex]\notin[/tex]C}
    ={x: x[tex]\in[/tex]A, x[tex]\notin[/tex]B OR x[tex]\in[/tex]A, x[tex]\notin[/tex]C}

    Is this wrong? What am I doing wrong?
    Please help me out!

    Thank You!
  2. jcsd
  3. Jan 28, 2009 #2
    There's your problem. x[tex]\notin[/tex](B[tex]\cup[/tex]C) if and only if x[tex]\notin[/tex]B AND x[tex]\notin[/tex]C. It helps to imagine the sets as venn diagrams. Alternatively, look at it as [tex]\neg[/tex] (x [tex]\in[/tex] (B[tex]\cup[/tex]C)) which becomes [tex]\neg[/tex](x [tex]\in[/tex]B OR x[tex]\in[/tex]C) and then the not distributes by de morgan's law for logic, producing x[tex]\notin[/tex]B AND x[tex]\notin[/tex]C. I assume you're allowed to use his logic rules to prove that they hold for sets. You make a similar mistake in the second one.
  4. Jan 28, 2009 #3
    Yes i agree with mXSCNT he explained very well where you made a mistake .

    Alternatively you can prove the above by using the concept of subsets:

    X=Y iff( X is a subset of Y and Y is a subset of X) iff ( xεX <===>xεY)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook