Discrete Mathematics for Computer Science

Chapter Review 217 the same number of places to the right or to the left. Prove that this relation is an equiv- alence relation. ...

218 CHAPTER 3 Relations Define the relation D on N so that n D m if and only if n I m. An upper bound of two natural numbers in ...

Functions In the study of mathematics, functions provide an important unifying concept. Functions are also familiar in computer ...

220 CHAPTER^4 Functions Figure 4.1 shows a picture to keep in mind when thinking about functions. x F I F(x) Figure 4.1 Function ...

Basic Definitions 221 output. Some people also have more than one child from which to choose, and in this case, the function wou ...

222 CHAPTER 4 Functions It is important to realize that the code itself is not the function. Rather, the code is just one way to ...

Basic Definitions 223 There is an obvious function: NextDay: DayOfWeek -> DayOfWeek Monday Tuesday Tuesday Wednesday Wednesda ...

224 CHAPTER 4 Functions 4.1.3 Recursively Defined Functions When a function F is defined by a formula, we can find the value of ...

Basic Definitions 225 F(O) = 1 F(1) I 1 F(2) = F(1) + F(O) = 1 + 1 = 2 F(3) =F(2)+F(1)=2+ I=3 F(4) = F(3) + F(2) = 3 +2 = 5 A re ...

226 CHAPTER 4 Functions y (-3, 0) 1 3, 0) (0,-3) (-•'1) Figure 4.3 Graph of a relation that is not a function. we often represen ...

Basic Definitions 227 Theorem 1. Let F and G be functions such that F = G. Then, domain(F) = domain(G) range(F) = range(G) and, ...

228 CHAPTER 4 Functions Pqp(qr r - p - -qAr (p A qA r) r L~g• v(pA-.qA r) ------ pAqA- r V(pA-qA-r) P r -.( -P __) ~ Vp v(-~p P- ...

Basic Definitions 229 15-- 4-- 4-- 12.5-- 10- 3-- 3- 7.5- 2- 2- 2.5 I -- -4 -2 2 4 -2 -1 1 2 -2 -1 1 2 Sqr, Sqr~lRT- 2,2U Sqrl { ...

230 CHAPTER 4 Functions The two examples we have given of partial functions actually reflect rather different ways in which part ...

Basic Definitions 231 (c) For x E IR, let Sqrt(x) be the non-negative square root of x. Then, Sqrt is a partial function, since ...

232 CHAPTER^4 Functions The function SeatOf (from Example 1(a) in Section 4.1) is 1-1 if and only if exactly zero or one person ...

Basic Definitions 233 Io 10- 7.5 5 2.5 -3 -2 1 2 3 -5 Figure 4.12 F(x) = x^3. The function SeatOf2, as shown in Figure 4.13, map ...

(^234) CHAPTER 4 Functions The horizontal line test for 1-1 functions can be easily modified to check whether a func- tion is on ...

Basic Definitions 235 The function exp : R -R IR defined as exp(x) = ex and shown in Figure 4.18 is 1-1 but not onto. y 70- 60" ...

236 CHAPTER 4 Functions storage location 18. Carry out this hashing procedure for Smith, Jones, Brown, Zento, and Ruster. Soluti ...