Discrete Mathematics for Computer Science

30 CHAPTER 1 Sets, Proof Templates, and Induction

The Distributive Laws for Meet and Join are proved for the interpretation of meet as

intersection and join as union in Theorem 3 (Section 1.3.1).

The final property we need is stated abstractly in terms of two special elements that

must be identified in the set of elements forming a lattice. The usual way to prove this

result is to assume that the lattice has this property and then determine what these special

elements must be.

Definition 12. Let X together with the operations meet (A) and join (v) be a lattice. X is

a complemented lattice if

1. There are two (unequal) elements, one called the minimum element, denoted I (read
   bottom), and the other called the maximum element, denoted T (read top), such that
   for every x E X,

xAT=x, xAL=_L, xvT=T, andxvL=x

2. For each x E X, there is an element -x E X such that x A -x = -L and x v -x = T.

Example 13. Let A be a set, and let X = P(A). The lattice on X with meet defined as

intersection and join defined as union is a complemented lattice.

Solution. Let T = A and -L = 0. Since for any B E X we have BnT=BOA = B,

B nl1=B n 0=0, B UT=B UA=A, andBU-_=B U 0 =B, Xisacomple-

mented lattice. M

The definition does not tell you what elements of a lattice should be -L and T or what

the relationship between -x and x is. For the lattice of subsets of a set A, we can use 0 =1L

and A itself as T. We also define -x as the complement of x. With these definitions of T,

-L, and --x for this lattice, you can show that the lattice is complemented. The details are

left as Exercise 23 in Section 1.4.

The mathematical structure that is of importance in computer science can now be

defined.

Definition 13. A boolean algebra is a complemented, distributive lattice.

The boolean algebra used by computer scientists to model combinatorial circuits is

based on the set of elements {0, 11 and the operations shown in Table 1.1 where v is the

meet and A is the join.

Table 1.1 Operations for a

Boolean Algebra

V 0 1 A 0 1

0 0 1 0 0 0

1 0 1

Example 14. Let B be a set of elements assigned values from the set {0, 1 }, and let the

operations v and A be defined on B as described in Table 1.1. B together with v as meet

and A as join forms a boolean algebra.