Discrete Mathematics for Computer Science

Operations on Sets 17 Definition 2. Let A and B be sets. The intersection of A and B, denoted by A n B, is {x :xE A and x E B) T ...

18 CHAPTER 1 Sets, Proof Templates, and Induction Proof. The proofs are left as an exercise for the reader. U The intersection o ...

Operations on Sets 19 Proof. (a) Suppose that A C B or A C C. Case 1: A C B. Follow Template 1.2 (Set Inclusion) for proving tha ...

20 CHAPTER 1 Sets, Proof Templates, and Induction Generalized Unions and Intersections The definitions of union and intersection ...

Operations on Sets 21 Example 5. (a) Let A ={1, 2. 10} and B = {3, 5, 7, 9}. Then, A - B = {1, 2, 4, 6, 8, 101. (b) Let A =N and ...

22 CHAPTER 1 Sets, Proof Templates, and Induction Proof. (a) Show that (i) A _ A and (ii) A C A. To prove (i), suppose x E A. Th ...

Operations on Sets 23 DeMorgan's Laws DeMorgan's Laws are among the most important and useful results about sets. These laws des ...

24 CHAPTER 1 Sets, Proof Templates, and Induction We can define the elements of two sets that are not in their intersection in t ...

Operations on Sets 25 =CO((ANiB)U(BNA)) (ANfA=BNB=o) = (C n A nf B) U (C n A n B) (Distributive Law) Putting the reduced form of ...

26 CHAPTER 1 Sets, Proof Templates, and Induction statement is normally not equivalent to its inverse or to its converse, but th ...

Operations on Sets 27 quite reasonable is, in fact, true. In the case discussed following Theorem 4, a counterex- ample would gi ...

28 CHAPTER 1 Sets, Proof Templates, and Induction 1.3.4 Power Sets and Products We started by introducing you to thinking about ...

Operations on Sets 29 "x A y = y A x Commutative Law for Meet "x V y = y V x Commutative Law for Join "x A (y A z) = (x A y) A z ...

30 CHAPTER 1 Sets, Proof Templates, and Induction The Distributive Laws for Meet and Join are proved for the interpretation of m ...

Exercises 31 Here, it turns out that there is only one possible choice for each of T, 1, and -': T=1, 1_=0, --0=1, and-1 =0 Inde ...

32 CHAPTER 1 Sets, Proof Templates, and Induction Let X = {2, 4}, Y = {1, 4}, and Z = {0, 4, 8}. Construct the following sets: ...

Exercises 33 Which of the following statements are correct? Prove each correct statement. Disprove each incorrect statement by ...

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

The Principle of Inclusion-Exclusion 35 Theorem 1. (Basic Counting Theorem) Let A and B be subsets of a finite universal set U. ...

36 CHAPTER 1 Sets, Proof Templates, and Induction Solution. Of the 834 people, 500 are females, so 334 are males. Of the 175 peo ...