Mathematics for Computer Science

4.5. Finite Cardinality 93 Continuing with the in-charge example above, the set of instructors in charge of 6.UAT in Spring ’10 ...

Chapter 4 Mathematical Data Types94 Combining these inequalities implies that ifRis a surjective function, thenjAj  jBj. In sho ...

4.5. Finite Cardinality 95 for 0 i 5. Since 5  3 , thisfis a surjection. So we have figured out that ifAandBare finite sets, ...

Chapter 4 Mathematical Data Types96 Problems for Section 4.1 Practice Problems Problem 4.1. For any setA, let pow.A/be itspower ...

4.5. Finite Cardinality 97 Class Problems Problem 4.3. Set Formulas and Propositional Formulas. (a)Verify that the propositional ...

Chapter 4 Mathematical Data Types98 (a)Prove that pow.A\B/Dpow.A/\pow.B/: (b)Prove that pow.A/[pow.B/pow.A[B/; with equality ho ...

4.5. Finite Cardinality 99 Hint:PORQORRis equivalent to .PANDQ/OR.QANDR/OR.RANDP/OR.PANDQANDR/: Problem 4.9. Union distributes o ...

Chapter 4 Mathematical Data Types100 using the fact that the propositional formula.PANDQ/OR.PANDQ/is equivalent toP. State a sim ...

4.5. Finite Cardinality 101  (c)Fix the proof to show thatRL. Problem 4.14. Abinary wordis a finite sequence of 0 ’s and 1 ’s. ...

Chapter 4 Mathematical Data Types102 union, and complement (relative toB) to these languages a finite number of times.^10 Note t ...

4.5. Finite Cardinality 103 very simple languages are not. This problem ends with the conclusion that the languagef 00 gof even ...

Chapter 4 Mathematical Data Types104 Problems for Section 4.4 Practice Problems Problem 4.15. Theinverse,R^1 , of a binary relat ...

4.5. Finite Cardinality 105 all three parts ofR. Properties: (a)surjective (b)injective (c)total (d)function (e)bijection Prob ...

Chapter 4 Mathematical Data Types106 Problem 4.20. Give an example of a relationRthat is a total injective function from a setAt ...

4.5. Finite Cardinality 107 5.Ris emptyŒD 0 outç Below are some assertions about a relationR. For each assertion, write the numb ...

Chapter 4 Mathematical Data Types108 functions. LethWWDf ıgbe the composition function off andg, namely, the function with domai ...

4.5. Finite Cardinality 109 Problem 4.28. The language of sets and relations may seem remote from the practical world of program ...

Chapter 4 Mathematical Data Types110  relational inverse^1. ... and one extra:relational compositionwhich generalizes composit ...

4.5. Finite Cardinality 111 Exam Problems Problem 4.29. LetAbe the set containing the five sets:fag;fb;cg;fb;dg;fa;eg;fe;fg, and ...

Chapter 4 Mathematical Data Types112 Problem 4.30. (a)Five assertions about a binary relationRWA!Bare bulleted below. There are ...