Mathematics for Computer Science
6.5. Induction in Computer Science 193 Figure 6.2 Constructing the Koch Snowflake. Problem 6.8. Fractals are an example of mathe ...
Chapter 6 Recursive Data Types194 Definition. Base case: The LBThl;leafihasunique labels. Constructor case: IfBandCare LBT’s wit ...
6.5. Induction in Computer Science 195 Definition. The set RAF ofrational functionsof one real variable is the set of functions ...
Chapter 6 Recursive Data Types196 F 2 : – 52 F 2 , ifn;m 2 F 1 , thennm 2 F 2. (a)Show that one of these definitions is tech ...
6.5. Induction in Computer Science 197 (c)The recursive definition AmbRecMatch is ambiguous because it allows the stconstructor ...
Chapter 6 Recursive Data Types198 Sincex 2 Erasable and has positive length, there must be an erase,y 2 Erasable, ofx. Sojyj Dn ...
6.5. Induction in Computer Science 199 Homework Problems Problem 6.16. One way to determine if a string has matching brackets, t ...
Chapter 6 Recursive Data Types200 Prove that ifBWN^2 !Nis a partial function that satisfies this same definition, thenBis total ...
6.5. Induction in Computer Science 201 because at each move, the complete game situation is known to the players, and this infor ...
Chapter 6 Recursive Data Types202 lows: Base case: A valuev 2 Vis a VG, and is called anended game. Constructor case: IffG 0 ;G ...
6.5. Induction in Computer Science 203 Any pair of strategies for the two players determines a unique play of a game, and hence ...
Chapter 6 Recursive Data Types204 a choice of any positive integern, after which we play ann-game tournament. Now the meta-chess ...
7 Infinite Sets This chapter is about infinite sets and some challenges in proving things about them. Wait a minute! Why bring u ...
Chapter 7 Infinite Sets206 7.1 Infinite Cardinality In the late nineteenth century, the mathematician Georg Cantor was studying ...
7.1. Infinite Cardinality 207 ordinalswith special well-ordering properties. The theory of ordinals requires get- ting deeper in ...
Chapter 7 Infinite Sets208 Another familiar set property is that for any two sets, either the first is at least as big as the se ...
7.1. Infinite Cardinality 209 Proof. SinceAisnotthe same size asA[fbgwhenAis finite, we only have to show thatA[fbgisthe same si ...
Chapter 7 Infinite Sets210 The proof is left to Problem 7.12. The most fundamental countably infinite set is the set,N, itself. ...
7.1. Infinite Cardinality 211 7.1.3 Power sets are strictly bigger Cantor’s astonishing discovery was thatnot all infinite sets ...
Chapter 7 Infinite Sets212 More Countable and Uncountable Sets Once we have a few sets we know are countable or uncountable, we ...
«
6
7
8
9
10
11
12
13
14
15
»
Free download pdf
