Hey all, needed some help with the following proof about De Morgan's laws:

Given two subsets A, B ⊆ X,

not (A ∩ B) = (not A) ∪ (not B)

and

not (A ∪ B) = (not A) ∩ (not B)

How would we go about proving this? Thanks for the help!

Printable View

- Oct 16th 2011, 03:43 PMjstarks44444De Morgan's Laws proof
Hey all, needed some help with the following proof about De Morgan's laws:

**Given two subsets A, B ⊆ X,**

not (A ∩ B) = (not A) ∪ (not B)

and

not (A ∪ B) = (not A) ∩ (not B)

How would we go about proving this? Thanks for the help! - Oct 17th 2011, 02:56 AMemakarovRe: De Morgan's Laws proof
This question belongs in the Logic section.

I'll assume that not(A) is the complement of A with respect to X. You need to show that not (A ∩ B) ⊆ (not A) ∪ (not B) and (not A) ∪ (not B) ⊆ (A ∩ B). To prove a set inclusion, assume that some x occur in the left-hand side and prove that it occurs in the right-hand side.

I'd also like to ask if you understand on the intuitive level why "not (P and Q)" is the same as "(not P) or (not Q)". Ultimately, the problem boils down to this where P is x ∈ A and Q is x ∈ B.