192 CHAPTER 4 Abstract Algebra
Actually, though, the De Morgan Laws are hardly surprising. IfA
represents “it will rain on Monday,” andB represents “it will rain on
Tuesday,” then “it will not rain on Monday or Tuesday” is represented
by (A∪B)′, which is obviously the same as “it won’t rain on Monday
and it won’t rain on Tuesday,” represented mathematically byA′∩B′.
A more formal proof might run along the following lines. In proving
that for two setsS=T, it is often convenient to prove thatS⊆T and
thatT ⊆S.
Theorem. For subsetsAandBof a given setU,(A∪B)′=A′∩B′.
Proof. Let x∈(A∪B)′. Then xis not inA∪B, which means that
x is not in Aand that x is not in B, i.e., x ∈A′∩B′. This proves
that (A∪B)′⊆A′∩B′. Conversely, ifx∈A′∩B′, thenx is not in
Aand thatxis not inB, and soxis not inA∪B. But this says that
x∈(A∪B)′, proving that (A∪B)′⊆ A′∩B′. It follows, therefore,
that (A∪B)′=A′∩B′.
There are two other important results related to unions and inter-
sections, both of which are somewhat less obvious than the De Morgan
laws. Let’s summarize these results as a theorem:
Theorem. LetA, B, andC be subsets of some universal setU. Then
we have two “distributive laws:”
A∩(B∪C) = (A∩B)∪(A∩C), and A∪(B∩C) = (A∪B)∩(A∪C).