Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 3] FUNCTIONS AND ALGORITHMS 45 EXAMPLE 3.2 (a) Letf:A→Bbe the function defined in Example 3.1 (b). Then the graph offis as ...

46 FUNCTIONS AND ALGORITHMS [CHAP. 3 Consider any functionf:A→B. Then f◦ (^1) A=f and 1B◦f=f where 1Aand 1Bare the identity func ...

CHAP. 3] FUNCTIONS AND ALGORITHMS 47 whether the concepts of being one-to-one and onto have some geometrical meaning. The answer ...

48 FUNCTIONS AND ALGORITHMS [CHAP. 3 Floor and Ceiling Functions Letxbe any real number. Thenxlies between two integers called t ...

CHAP. 3] FUNCTIONS AND ALGORITHMS 49 Arithmetic moduloMrefers to the arithmetic operations of addition, multiplication, and subt ...

50 FUNCTIONS AND ALGORITHMS [CHAP. 3 Three classes of logarithms are of special importance: logarithms to base 10, calledcommon ...

CHAP. 3] FUNCTIONS AND ALGORITHMS 51 Sequences Asequenceis a function from the setN={ 1 , 2 , 3 ,...}of positive integers into a ...

52 FUNCTIONS AND ALGORITHMS [CHAP. 3 The last sum appears very often. It has the valuen(n+ 1 )/2. That is: 1 + 2 + 3 +···+n= n(n ...

CHAP. 3] FUNCTIONS AND ALGORITHMS 53 And so on. Observe that 5 != 5 · 4 != 5 · 24 =120 and 6!= 6 · 5 != 6 · 120 = 720 This is tr ...

54 FUNCTIONS AND ALGORITHMS [CHAP. 3 Level Numbers LetPbe a procedure or recursive formula which is used to evaluatef(X)wherefis ...

CHAP. 3] FUNCTIONS AND ALGORITHMS 55 Although it is not obvious from the definition, the value of anyA(m, n)may eventually be ex ...

56 FUNCTIONS AND ALGORITHMS [CHAP. 3 Theorem 3.4 (Cantor): For any set A, we have|A|<|Power(A)|(where Power(A) is the power s ...

CHAP. 3] FUNCTIONS AND ALGORITHMS 57 EXAMPLE 3.11 (Greatest Common Divisor) Letaandbbe positive integers with, say,b<a; and s ...

58 FUNCTIONS AND ALGORITHMS [CHAP. 3 The above discussion leads us to the question of finding the complexity functionf (n)for ce ...

CHAP. 3] FUNCTIONS AND ALGORITHMS 59 Rate of Growth; BigONotation SupposeMis an algorithm, and supposenis the size of the input ...

60 FUNCTIONS AND ALGORITHMS [CHAP. 3 SolvedProblems FUNCTIONS 3.1. LetX={ 1 , 2 , 3 , 4 }. Determine whether each relation onXis ...

CHAP. 3] FUNCTIONS AND ALGORITHMS 61 3.4. Letf:R→Randg:R→Rbe defined byf(x)= 2 x+1 andg(x)=x^2 −2. Find the formula for the comp ...

62 FUNCTIONS AND ALGORITHMS [CHAP. 3 3.7. Consider functionsf:A→Bandg:B→C. Prove the following: (a)Iffandgare one-to-one, then t ...

CHAP. 3] FUNCTIONS AND ALGORITHMS 63 3.12. LetA 1 ,A 2 ,...be a countable number of finite sets. Prove that the unionS=∪iAiis co ...

64 FUNCTIONS AND ALGORITHMS [CHAP. 3 3.16. Find: (a)25(mod7);(b)25(mod5);(c)− 35 (mod 11);(d)− 3 (mod 8). Whenkis positive, simp ...