1、Chapter 2 Basic Structures : Sets, Functions, Sequences, and Sums,大葉大學 資訊工程系 黃鈴玲,Discrete Mathematics,2-1 Sets (集合),Def 1 : A set is an unordered collection of objects.Def 2 : The objects in a set are called the elements (元素), or members of the set. x A 表示A是一個集合，而x是A中的元素例如：A = x, y, z當集合的元素很多，無法一一列舉
2、，元素又具備某些特性時，可使用如下表示法：Q = x | x的特性 如： Q = x | x 是小於10的正奇數 或：Q = x | x 是奇數，3x100 = 表示空集合,Ch2-2,Example 5 : 常見的重要集合N= 0,1,2,3, the set of natural number (自然數)(注意：有些書不把0視為自然數)Z = ,-2, -1,0,1,2, the set of integers (整數)Z+ = 1,2,3, the set of positive integers (正整數)Q = p/q | p Z, q Z, q0 , the set of rati
3、onal numbers (有理數)R = the set of real numbers (實數) (元素可表示成1.234等小數形式)Def 3 : A,B: sets. A=B iff x (x A x B) Def 4 : A B iff x (x A x B) (A是B的子集合)補充： A B 表示A B 但 A B,Ch2-3,Ch2-4,5. 判定2是否為下列集合的元素。 (a) x R | x 為大於1的整數 (b) x R | x 為整數的平方 (c) 2, 2 (d) 2, 2 (e) 2, 2, 2 (f) 2,Exercise 2-1,7. 判定下列陳述是否為真。 (a
4、) 0 (b) 0 (c) 0 (d) 0 (e) 0 0 (f) 0 0 (g) ,Ch2-5,8. 判定下列陳述是否為真。 (a) (b) , (c) (d) (e) , (f) , ,Exercise 2-1,Def 5 : S : a finite set The cardinality (基數,元素個數) of S, denoted by |S|, is the number of elements in S.Def 7 : S : a set The power set (冪集合) of S, denoted by P(S), is the set of all subsets o
5、f S.Example A=1,2P(A) = , 1, 2, 1,2 Example 13 : S = 0,1,2P(S) = , 0, 1, 2, 0,1, 0,2, 1,2, 0,1,2 ,Ch2-6,Ch2-7,17. 下列各集合的基數(cardinality)為何？ (a) a (b) a (c) a, a (d) a, a, a, a,Exercise 2-1,21(修改). 求出下列集合，其中a與b為相異元素。 (a) P(a, b) (b) P() (c) P(P(),Def 9 : A, B : sets. The Cartesian Product (笛卡耳積) of A
6、and B, denoted by AB, is the set AB = (a, b) | a A and b B Example 16 : A = 1,2 , B = a, b, cAB = (1, a), (1, b), (1, c), (2,a), (2,b), (2,c) Note: |AB| = |A|B|,Ch2-8,Ch2-9,Def 9 : A1, A2, , An : sets. The Cartesian Product (笛卡耳積) of A1, A2, , An, denoted by A1A2An, is the setA1A2 An = (a1, a2, , an
7、) | ai Ai, where i=1, 2, , n Example 18: A = 0,1 , B = x,y, C=a,b,cABC = (0,x,a), (0,x,b), (0,x,c), (0,y,a), (0,y,b), (0,y,c), (1,x,a), (1,x,b), (1,x,c), (1,y,a), (1,y,b), (1,y,c),Ch2-10,23. 令A = a, b, c, d與B = y, z，C=1,2求出 (a) AB (b) BA (c) BCA,Exercise 2-1,2-2 Set Operations(集合的運算),Def 1,2,4 : A,B
8、 : setsAB = x | x A or x B (union聯集)AB = x | x A and x B (intersection交集)A B = x | x A and x B (差集，也寫成A B)Def 3 : Two sets A,B are disjoint(互斥) if AB = Def 5 : Let U be the universal set (宇集).The complement (補集) of the set A , denoted by A , is the set U A .Example 10 : Prove that AB = AB pf : 此種圖稱為
9、 Venn Diagram(范式圖),Ch2-11,U,Def 6,7 : A1 , A2 , , An : sets Let I = 1,3,5 , Def : (習題31) A,B : setsThe symmetric difference (對稱差集) of A and B, denoted by AB , is the set x | x A - B or x B - A = ( AB ) - ( A B )Inclusion Exclusion Principle (排容原理)|A B| = |A| + |B| - |A B|,Ch2-12,26. 若ABC為集合，繪出下列集合組合
10、之范式圖。(a) A (BC) (b) A B C(c) (A-B)(A-C)(B-C),Ch2-13,14. 若A-B = 1,5,7,8, B-A = 2,10，以及AB = 3,6,9。 求出集合A與B。,Exercise 2-2,32. 找出 1,3, 5及1, 2, 3的對稱差集(symmetric difference)。,2-3 Functions (函數),Def 1 : A,B : sets A function f : A B is an assignment of exactly one element of B to each element of A. We writ
11、e f (a) = b if b is the unique element of B assigned by f to a A. Example,Ch2-14,Not a function,Not a function,f(a)=1f(b)=1f(b)=2f(g)=3,f(a)=1f(b)=?f(g)=2,Def 2 : (以 f : AB 為例，右上圖) A: domain (定義域) of f , B: codomain (對應域) of ff (a) = 1 , f (b) = 4 , f (g) = 2 1稱為a的image (映像, 必定唯一), a稱為1的pre-image(前像
12、, 可能不唯一)range(值域) of f = f (a) | a A = f (A) = 1,2,4 (未必=B)Example 4 : f : Z Z, f (x) = x2, 則 f 的domain, codomain 及range為何?,Ch2-15,a function,a function,g(a)=1g(b)=2g(g)=1,f(a)=1f(b)=4f(g)=2,Def 3 : 令 f1 與 f2 為 A 到 R 的函數，則f1 + f2 和 f1 f2也是 A 到 R 的函數，分別定義為： ( f1 + f2 )(x) = f1(x) + f2(x) (f1 f2)(x) =
13、 f1(x) f2(x) Example 6 : Let f1 : R R and f2 : R R such thatf1(x) = x2, f2(x) = x - x2. What are the function f1 + f2 and f1 f2?Sol : ( f1 + f2 )(x) = f1(x) + f2(x) = x2 + ( x x2 ) = x (f1 f2)(x) = f1(x)f2(x) = x2( x x2 ) = x3 x4,Ch2-16,Ch2-17,Exercise 2-3,1. 為何下列 f 不為R到R的函數？ (a) f (x) = 1/x (b) f (
14、x) = x (c) f (x) = (x2+1),Def 5: A function f is said to be one-to-one (一對一), or injective (嵌射), iff f (x) f (y) whenever x y. Example 8 :,Ch2-18,是 1-1,不是 1-1 , 因 g(a) = g(d) = 4, 一對一函數與映成函數,Example 10: Determine whether the function f (x) = x + 1 is one-to-one?Sol: x y x + 1 y + 1 f (x) f (y) f is
15、1-1Def 7: A function f : A B is called onto (映成), or surjective (蓋射), iff for every element b B, a A with f (a) = b. (即 B 的所有元素都被 f 對應到)Example 11:,Ch2-19,Note : 當|A| |B| 時，必定不會onto.,onto,not onto,Def 8: The function f is a one-to-one correspondence (一對一對應關係), or a bijection (雙射), if it is both 1-1
16、and onto.圖5補充 : f : A B (1) If f is 1-1 , then |A| |B| (2) If f is onto , then |A| |B| (3) if f is 1-1 and onto , then |A| = |B|.,Ch2-20,1-1 , not onto,not 1-1, onto,1-1 and onto,Ch2-21,Exercise 2-3,12, 13, 19. 判斷為何下列 由Z對應到Z的函數是否為一對一、映成或雙射函數。 (a) f (n) = n-1 (b) f (n) = n2+1 (c) f (n) = n3 (d) f (n)
17、 = n/2,Some important functionsDef 12: floor function x (底函數): 表示 x 的最大整數，即 xceiling function x (頂函數): 表示 x 的最小整數Example 24 : = - = 7 = = - = 7 = Example 29 : factorial function (階乘函數): f : N Z+ , f (n) = n! = 1 x 2 x x n,Ch2-22,Ch2-23,Exercise 2-3,27. 令f (x) = x2/3。若集合如下，求出 f (S)。 (a) S = -2, -1, 0
18、, 1, 2, 3 (b) S = 0, 1, 2, 3, 4, 5 (c) S = 1, 5, 7, 11 (d) S = 2, 6, 10, 14 ,2.4 Sequences and Summations,Sequence (數列)Def 1. A sequence is a function f from A Z+ (or A N) to a set S. We use an to denote f(n), and call an a term (項) of the sequence.Example 1. an , where an = 1/n , n =1, 2, 3, a1 =1,
19、 a2 =1/2 , a3 =1/3, Example 2. bn , where bn= (-1)n, n =0, 1, 2, b0 = 1, b1 = -1 , b2 = 1, ,Ch2-24,Ch2-25,Exercise 2-4,1. 求出序列 an 中下列各項，其中an = 2(-3)n+5n。 (a) a0 (b) a1 (c) a4,6. 列出下列序列的前十項。 (a)序列由10開始，接下去的項都是前項減3。 (e)序列的首兩項為1與2，接下去的項都是前兩項之和。,Example 5. 給定數列的前五項，求序列的公式：(a) 1, 1/2, 1/4, 1/8, 1/16(b) 1
20、, 3, 5, 7, 9(c) 1, -1, 1, - 1, 1Sol : (a) a0 = 1, a1 = 1/2, a2 = 1/22, a3 = 1/23, a4 = 1/24, an = 1/2n, n =0, 1, 2, 3, (b) a0 = 1, a1 = 3, a2 = 5, a3 = 7, a4 = 9 an = 2n+1, n =0, 1, 2, 3, (c) a0 = 1, a1 = -1, a2 = 1, a3 = -1, a4 = 1 an = (-1)n, n =0, 1, 2, 3, ,Ch2-26,Example 7. How can we produce th
21、e terms of a sequence if the first 10 terms are 5, 11, 17, 23, 29, 35,41, 47, 53, 59?Sol : (等差數列) a1 = 5 a2 =11 = 5 + 6 a3 =17 = 11 + 6 = 5 + 6 2 : : an= 5 + 6(n-1) = 6n-1, n =1, 2, 3, ,Ch2-27,注意：序列的第一項是 a0 還是 a1 會影響 an 的公式， 所以寫公式時一定要標示出 n 從 0 還是 1 開始,Example 8. Conjecture a simple formula for an if
22、 the first 10 terms of the sequence an are 1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047?Sol： 顯然非等差數列 後項除以前項的值接近3 猜測數列為 3n 比較： 3n : 3, 9, 27, 81, 243, 729, 2187, an : 1, 7, 25, 79, 241, 727, 2185, an = 3n - 2 , n 1,Ch2-28,Ch2-29,Exercise 2-4,9. 為下面給定的序列找出簡單的一般項公式，假設你的公式正確，列出接下的三項。 (c) 1, 0, 2, 0,
23、 4, 0, 8, 0, 16, 0, (d) 3, 6, 12, 24, 48, 96, 192, (e) 15, 8, 1, -6, -13, -20, - 27, (f) 3, 5, 8, 12, 17, 23, 30, 38, 47, (g) 2, 16, 54, 128, 250, 432, 686, (h) 2, 3, 7, 25, 121, 721, 5041, 40321, , Summations (級數，數列總和) Here, the variable j is call the index of summation, m is the lower limit (下限),
24、and n is the upper limit (上限).,Ch2-30,Example 10. = 12+22+32+42+52=55Example 13. (Double summation),Example 14. Table 2. Some useful summation formulae,Ch2-31,Ch2-32,Exercise 2-4,13. 下列總和之值為何？ (a) (b) (c) (d),17. 計算下面的多重總和 (a) (b) (c) (d),Cardinality(基數) (此部分跳過)Def 4. The sets A and B have the same
25、cardinality (size) if and only if there is a one-to-one correspondence (1-1,onto 的function) from A to B. Def 5. A set that is either finite or has the same cardinality as Z+ (or N) is called countable (可數). A set that is not countable is called uncountable.,Ch2-33,Ch2-34,Example 18. Show that the set of odd positive integers is a countable set.,Example 19. Show that the set of positive rational number (Q+) is countable.,Ch2-35, Z+ : 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 Q+ :,(注意，因 等於 ，故 不算),Note. R is uncountable. (Example 21),Pf: Q+ = a / b | a, b Z+ ,(Figure 2),
