Discrete Mathematics for Computer Science

Basic Definitions 237 A message such as LEAVINGTODAY = 1104 00 2108 13 06 19 14 0300 24 is transmitted as F(ll) F(4) F(0) F(21) ...

238 CHAPTER^4 Functions is decreasing on (-oo, 3] and increasing on [3, 00). (You can see this from the graph of the function.) ...

Exercises 239 Proof. This proof is left as an exercise for the reader. U Of course, the definitions of the terms strictly increa ...

240 CHAPTER 4 Functions List all 1-1 and onto functions from {1, 2, 31 to itself. Let A be a set with three elements and B be a ...

Exercises 241 20. Prove that the function F : Z -* Z defined as F(n) = n + 6 is a bijection. For each of the following function ...

242 CHAPTER 4 Functions Prove Theorem 3. Using the numbering scheme for the letters of the alphabet as given in Section 4.1.8, ...

Operations on Functions 243 (b) p Iq r Fpqr I 1 1 1 1 1 0 1 1 0 1 0 1 0 0 0 (^0 1 1 0) 0 1 0 1 0 0 1 0 0[0 0 1 (c) pV qY r F(p,q ...

244 CHAPTER 4 Functions Definition 1. Let both F : X --* Y and G : Y --> Z be partial functions. The composi- tion of G and F ...

Operations on Functions 245 Theorem 1. Let X, Y, and Z be sets. Let both F : X - Y and G : Y --- Z be partial functions. Then, G ...

246 CHAPTER 4 Functions Definition 2. Let F = {(x, y) E X x Y : F(x) = y} be a function. The inverse of F, denoted by F , is the ...

Operations on Functions 247 The inverse of a function F is not always a function or a partial function. If, however, F is 1-1 or ...

248 CHAPTER 4 Functions 4.3.3 Other Operations on Functions The reader is familiar with operations on polynomial functions. Cons ...

Sequences and Subsequences 249 Definition 3. An infinite sequence of elements of a set X is a function F : N --+ X. A function F ...

250 CHAPTER 4 Functions What, more precisely, is a subsequence? Think of an infinite sequence: XO, XI, X2, X3, X4, X5, X6 ..... ...

Exercises 251 W Exercises Let X = {1,2, 3, 4} and Y = {5, 6, 7, 8,9}. Let F = {(1, 5), (2,7), (4,9), (3, 8)}. Show that F is a ...

252 CHAPTER 4 Functions Find the first six terms of the sequences defined for n > 0 as: (a) H(n) = n^2 (n + 1)2/4 (b) G(n) = ...

The Pigeon-Hole Principle 253 (d) F(A 1 ) - F(A 2 ) _ F(Ai - A 2 ). (e) A, c F-I(F(A1)). (f) Find an example in which A 1 C A 2 ...

254 CHAPTER 4 Functions What can we conclude about the function that maps people to the cars in which they are riding? Is it 1-1 ...

The Pigeon-Hole Principle 255 every element of X is mapped to some element of Y, so there are at most k .n elements in X. M 4.6. ...

256 CHAPTER 4 Functions Proof By Theorem 2, ifm= lXI andn= YI within >n, then >_n+1, which implies [m ] [n + >l n -- n ...