Math Is Fun Forum

osman

Guest

De'Morgan Proof in Sets

Hi. I want to prove this:

thanks

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: De'Morgan Proof in Sets

Just like any set theory proof, start by assuming x is in (A U B)^c and show that x is in A^c U B^c.  Then do the reverse way.  It should be fairly straight forward, just expand on what complement and union mean.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: De'Morgan Proof in Sets

Just like any set theory proof, start by assuming x is in (A U B)^c and show that x is in A^c ∩ B^c.

Identity

Member

Registered: 2007-04-18

Posts: 934

Re: De'Morgan Proof in Sets

I sometimes think of it this way:

(A U B)' = A' ∩ B'

The left side is equal to:

((A ∩ B) U (A ∩ B') U (B ∩ A'))' = A' ∩ B'

Since you can only ever have 4 options:  A ∩ B, A ∩ B', A' ∩ B, A' ∩ B', (like the law of trichotomy but for 4 versions) then what's not 3 of those must be the other:

A' ∩ B' = A' ∩ B'

Last edited by Identity (2007-11-02 12:10:57)

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: De'Morgan Proof in Sets

There are 2 typos in Identity's 4th line.
Correct the ampersands("&") to become logical ORs.
And swap B and A in 2nd or 3rd term.
Also learn "Karnaugh mapping" if you want to be awesome at it.  It's digital electronics stuff.

---

igloo myrtilles fourmis

Identity

Member

Registered: 2007-04-18

Posts: 934

Re: De'Morgan Proof in Sets

Thanks John, I keep thinking & is disjunction!

Yeah, Karnaugh Mapping is brilliant! They are invaluable in many set theory and probability problems! I'd take them over Venn Diagrams anyday!

DaveB

Guest

Re: De'Morgan Proof in Sets

Hey guys, I'm actually struggling with the same issue; I'm taking a discrete mathematics class and struggling heavily in even understanding the principles of the stuff.  However, I'm in desperate need to solve this proof and was hoping you could help. 

The formula, of course is, (A U B)^c = A^c ∩ B^c

I've gotten as far as saying that x is an element of A^c or B^c, but don't know how to make the leap to the other side of the equals sign to A^c ∩ B^c.  I've been up for the better part of 2 hrs trying to reason this thing, but with no luck.  Remember that this is for an entry level discrete mathematics course, so the logic and equations can't be too complicated or you'll lose me.  Any help anyone can offer would be MOST appreciated.  Thanks all!

~Dave

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: De'Morgan Proof in Sets

I've gotten as far as saying that x is an element of A^c or B^c

You should get that x is an element of A^c and B^c.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."