Discrete Mathematics for Computer Science

28 CHAPTER 1 Sets, Proof Templates, and Induction

1.3.4 Power Sets and Products

We started by introducing you to thinking about sets of objects and not just individual

objects. After introducing sets, we made precise what it means for one set to be a subset

of another. We can also take one more step, however, and think of the set consisting of all

subsets of a set.

Definition 8. Let A be a set. The power set of A, denoted P(A), is

P(A) = {X: X C A)

Example 9.

(a) P(0) = (0). Even though 0 has no elements, P(0) has the one element 0.

(b) P(P(0)) = P({0)) = {0, 1011.

(c) P({1, 2}) = {0, {1), {2), {1, 2}}.

(d) P({l, 2, 3}) = {0, (1}, (2), (3), {1, 2}, {2,3}, {1, 3), (1, 2,3)).

(e) P({1, 2, 13)1) = {0, (1}, (2), {{3)), {1, 2), {2, {3}}, {1, (3)), (1,2, (3111.

(f) P({{1, 2, 3}1) = {0, {1, 2, 311. This is true, because the set {{1, 2, 3}} has only one ele-

ment, {1, 2, 3}. So, there are only two subsets of {{1, 2, 3}}, one that contains {1, 2, 31

and one that does not.

Products of Sets

The next operation on sets is familiar, because it is the formalism behind the way we are

used to seeing points in two-dimensional space represented as ordered pairs.

Definition 9. For any sets X and Y, the product X x Y is the set of all ordered pairs

(a, b) such that a E X and b E Y. When X = Y, this set is also denoted X^2 .Similarly,

the product of n sets X 1 ..... Xn is the set of all ordered n-tuples (xl, ... , Xn) of elements

such that xI E X 1..... and Xn G Xn .When n copies of the same set X are used, the re-

sulting Cartesian product X x ... x X is the set of all ordered n-tuples of elements in X,

denoted Xn.

Example 10. Let X = (0, 11 and C = [a, b}. Then, X x C = ((0, a), (0, b), (1, a),

(1, b)), and C x C = I(a, a), (a, b), (b, a), (b, b)}. The product of two sets is sometimes

referred to as the Cartesian product.

1.3.5 Lattices and Boolean Algebras

The design of computer chips involves very complex interactions of very small components

or building blocks called gates. The complete design that is of a computer chip is called

a combinatorial circuit. The mathematical structure we will introduce here can be used to

design, represent, and optimize combinatorial circuits. We will look more closely at gates

and combinatorial circuits in Chapter 2, but we first need to understand the underlying

mathematical structure.

Definition 10. A lattice is a set X with two operations, called meet, denoted as A, and

join, denoted as v, that satisfy the following properties for all x, y, z E X :