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!
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.