34 CHAPTER 1 Sets, Proof Templates, and Induction
- Prove that in a boolean algebra
a V (b Ac) = (a v b) A C
if and only if
a V (b A (a V c)) = (a v b) A (a V c)
and
a A (b V (a A c)) = (a A b) V (a A c)
This property of a boolean algebra is called modularity.- Prove that in a boolean algebra, DeMorgan's Laws hold; that is,
-,(x V y) = -x A -,y
-,(x A y) = -X V -'y- Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 101 be a universal set. Let A, B, C C U such that
A = {1, 3, 4, 81, B = {2, 3, 4, 5, 9, 101, and C = {3, 5, 7, 9, 101. Use bit representa-
tions for A, B, and C together with UNION, INTER, DIFF, and COMP to find the bit
representation for the following:
(a) AUB
(b) ANBNC
(c) (AUC) nB
(d) (A-B) UC
(e) AAn(B-(CnB))
(f) A-(B-C)
(g) (AUB) U(C-B)rnThe Principle of Inclusion-Exclusion
A great deal can often be learned just by counting the elements in a set. Unfortunately, it
turns out that even though counting is sometimes very easy, it is sometimes very difficult,
especially if the set whose elements are being counted has a very complicated description.
As we show later, the Principle of Inclusion-Exclusion is a widely used method for count-
ing the number of elements in the union or the intersection of sets.1.5.1 Finite Cardinality
Before we focus on counting elements in unions of sets that are not disjoint, we need to
make clear some fundamental ideas about how we compute the number of elements in a set.
Definition 1. (Informal) For a finite set, the cardinality of A is the number of elements
in A. If A is infinite, then the cardinality of A is infinite. The cardinality of A is denoted
by IA I.Example 1. 1{1, 2,311 = 3. 101 = 0. 1IP(0) I = 1. i{{1, 2,3}}I = 1. IZI is infinite.
This definition should be viewed as a temporary one. The topic of cardinality will be
dealt with in Chapter 4, in which this informal definition will be replaced with a more
formal one. In Chapter 4, the idea of two sets having the same cardinality (I X I = I Y I)
will be extended to include sets with infinitely many elements. The informal definition of
cardinality suffices for finite sets; and in this section, only finite sets are considered.