Discrete Mathematics

Chapter 2 �Basic Structures : Sets, Functions, Sequences, and Sums

大葉大學 資訊工程系 黃鈴玲

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}
• 當集合的元素很多，無法一一列舉，元素又具備某些特性時，可使用如下表示法：�Q = { x | x的特性 }�如： Q = { x | x 是小於10的正奇數 }�或：Q = { x | x 是奇數，3<x<100 }
• ∅ = { } 表示空集合�

​

​

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, q≠0 }, the set of rational 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) 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 of S.
• Example �A={1,2}�P(A) = { ∅, {1}, {2}, {1,2} }
• Example 13 : �S = {0,1,2}�P(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 and B, denoted by A×B, is the set �A×B = { (a, b) | a ∈ A and b ∈ B }
• Example 16 : �A = {1,2} , B = {a, b, c}

A×B = { (1, a), (1, b), (1, c), (2,a), (2,b), (2,c) }

• Note: |A×B| = |A|×|B|

​

Ch2-8

Ch2-9

• Def 9 : A₁, A₂, …, A_n : sets. �The Cartesian Product (笛卡耳積) of A₁, A₂, …, A_n, �denoted by A₁×A₂×…×A_n, is the set�A₁×A₂× … ×A_n = { (a₁, a₂, …, a_n) | a_i ∈ A_i, � where i=1, 2, …, n }
• Example 18: �A = {0,1} , B = {x,y}, C={a,b,c}

A×B×C = { (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) A×B� (b) B×A� (c) B×C×A

Exercise 2-1

2-2 Set Operations(集合的運算)

• Def 1,2,4 : A,B : sets
• A∪B = { x | x ∈ A or x ∈ B } (union聯集)
• A∩B = { 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 A∩B = ∅
• 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 A∩B = A∪B

pf :

​

此種圖稱為 Venn Diagram(范式圖)

Ch2-11

• Def 6,7 : A₁ , A₂ , … , A_n : sets

�

�� Let I = {1,3,5} ,�

• Def : (習題31) A,B : sets

The symmetric difference (對稱差集) of A and B, denoted by A⊕B , is the set

{ x | x ∈ A − B or x ∈ B − A } = ( A∪B ) − ( A ∩B )

• Inclusion – Exclusion Principle (排容原理)

|A ∪ B| = |A| + |B| − |A ∩ B|

Ch2-12

26. 若ABC為集合，繪出下列集合組合之范式圖。�(a) A ∩ (B∪C) �(b) A ∩ B ∩ C�(c) (A−B)∪(A−C)∪(B-C)

​

Ch2-13

14. 若A−B = {1,5,7,8}, B−A = {2,10}，以及A∩B = {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 write 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(α)=1�f(β)=1�f(β)=2�f(γ)=3

f(α)=1�f(β)=?�f(γ)=2

• Def 2 : (以 f : A→B 為例，右上圖)

A: domain (定義域) of f , B: codomain (對應域) of f

f (α) = 1 , f (β) = 4 , f (γ) = 2

1稱為α的image (映像, 必定唯一), �α稱為1的pre-image(前像, 可能不唯一)

range(值域) of f = { f (a) | a ∈ A} = f (A) = {1,2,4} (未必=B)

Example 4 : f : Z → Z, f (x) = x², 則 f 的domain, codomain 及range為何?

Ch2-15

a function

a function

g(α)=1�g(β)=2�g(γ)=1

f(α)=1�f(β)=4�f(γ)=2

• Def 3 : 令 f₁ 與 f₂ 為 A 到 R 的函數，則f₁ + f₂ 和 f₁ f₂也是 �A 到 R 的函數，分別定義為：

( f₁ + f₂ )(x) = f₁(x) + f₂(x) � (f₁ f₂)(x) = f₁(x) f₂(x)

​

• Example 6 : Let f₁ : R → R and f₂ : R → R such that

f₁(x) = x², f₂(x) = x − x². What are the function f₁ + f₂ and f₁ f₂?

Sol :

( f₁ + f₂ )(x) = f₁(x) + f₂(x) = x² + ( x – x² ) = x

(f₁ f₂)(x) = f₁(x)．f₂(x) = x²( x – x² ) = x³ – x⁴

�

Ch2-16

Ch2-17

Exercise 2-3

• 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 1-1

• Def 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 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) = n²+1� (c) f (n) = n^3� (d) f (n) = ⎡n/2⎤

※Some important functions

• Def 12:
• floor function ⎣x⎦ (底函數): 表示 ≤ x 的最大整數，即 [x]
• ceiling 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) = ⎣x²/3⎦。若集合如下，求出 f (S)。� (a) S = {−2, −1, 0, 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 a_n to denote f(n), and call a_n a term (項) of the sequence.

​

Example 1. {a_n} , where a_n = 1/n , n =1, 2, 3, …

⇒ a₁ =1, a₂ =1/2 , a₃ =1/3, …

​

Example 2. {b_n} , where b_n= (−1)ⁿ, n =0, 1, 2, …

⇒ b₀ = 1, b₁ = −1 , b₂ = 1, …

Ch2-24

Ch2-25

Exercise 2-4

1. 求出序列 {a_n} 中下列各項，其中a_n = 2(−3)ⁿ+5ⁿ。� (a) a₀� (b) a₁� (c) a₄

6. 列出下列序列的前十項。� (a)序列由10開始，接下去的項都是前項減3。� (e)序列的首兩項為1與2，接下去的項都是前兩項之和。

Example 5. 給定數列的前五項，求序列的公式：�(a) 1, 1/2, 1/4, 1/8, 1/16�(b) 1, 3, 5, 7, 9�(c) 1, −1, 1, − 1, 1

Sol :

(a) a₀ = 1, a₁ = 1/2, a₂ = 1/2², a₃ = 1/2³, a₄ = 1/2⁴,

∴ a_n = 1/2ⁿ, n =0, 1, 2, 3, …

(b) a₀ = 1, a₁ = 3, a₂ = 5, a₃ = 7, a₄ = 9

∴ a_n = 2n+1, n =0, 1, 2, 3, …

(c) a₀ = 1, a₁ = −1, a₂ = 1, a₃ = −1, a₄ = 1

∴ a_n = (−1)ⁿ, n =0, 1, 2, 3, …

​

​

Ch2-26

Example 7. How can we produce the terms of a sequence if the first 10 terms are �5, 11, 17, 23, 29, 35,41, 47, 53, 59?

Sol : (等差數列)

a₁ = 5

a₂ =11 = 5 + 6

a₃ =17 = 11 + 6 = 5 + 6 × 2

:

:

∴ a_n= 5 + 6(n−1) = 6n−1, n =1, 2, 3, …

Ch2-27

注意：序列的第一項是 a₀ 還是 a₁ 會影響 a_n 的公式，

所以寫公式時一定要標示出 n 從 0 還是 1 開始

Example 8. Conjecture a simple formula for a_n if

the first 10 terms of the sequence {a_n} are

1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047?

Sol：

顯然非等差數列

後項除以前項的值接近3

⇒ 猜測數列為 3ⁿ ± …

比較：

{3ⁿ} : 3, 9, 27, 81, 243, 729, 2187,…

{a_n} : 1, 7, 25, 79, 241, 727, 2185,…

∴ a_n = 3ⁿ − 2 , n ≥ 1

​

Ch2-28

Ch2-29

Exercise 2-4

9. 為下面給定的序列找出簡單的一般項公式，假設你的公式正確，列出接下的三項。� (c) 1, 0, 2, 0, 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 (下限), and n is the upper limit (上限).

Ch2-30

Example 10.

= 1²+2²+3²+4²+5²=55

​

Example 13. (Double summation)

​

Example 14.

​

Table 2. Some useful summation formulae

​

Ch2-31

Ch2-32

Exercise 2-4

13. 下列總和之值為何？� (a) (b) (c) �� (d)

※Cardinality(基數) (此部分跳過)

​

Def 4. The sets A and B have the same 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)