Bài giảng Discrete structures for computer science - Chapter 3: Sets and Functions

Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.1 Chapter 4 Sets and Functions Discrete Structures for Computer Science (CO1007) on Ngày 7 tháng 10 năm 2016 Nguyen An Khuong, Huynh Tuong Nguyen Faculty of Computer Science and Engineering University of Technology, VNU-HCM Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.2 Contents 1 Sets 2 Set Operation 3 Functions 4 One-to-one and Onto Functions 5 Sequences and Summation 6 Recursion Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.3 Set Definition • Set is a fundamental discrete structure on which all discrete structures are built • Sets are used to group objects, which often have the same properties Example • Set of all the students who are currently taking Discrete Mathematics 1 course. • Set of all the subjects that K2011 students have to take in the first semester. • Set of natural numbers N Definition A set is an unordered collection of objects. The objects in a set are called the elements (phần tử ) of the set. A set is said to contain (chứa) its elements. Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 Notations Definition • a ∈ A: a is an element of the set A • a /∈ A: a is not an element of the set A Definition (Set Description) • The set V of all vowels in English alphabet, V = {a, e, i, o, u} • Set of all real numbers greater than 1??? {x | x ∈ R, x > 1} {x | x > 1} {x : x > 1} Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.5 Equal Sets Definition Two sets are equal iff they have the same elements. • (A = B)↔ ∀x(x ∈ A↔ x ∈ B) Example • {1, 3, 5} = {3, 5, 1} • {1, 3, 5} = {1, 3, 3, 3, 5, 5, 5, 5} Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.6 Venn Diagram • John Venn in 1881 • Universal set (tập vũ trụ) is represented by a rectangle • Circles and other geometrical figures are used to represent sets • Points are used to represent particular elements in set Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.7 Special Sets • Empty set (tập rỗng) has no elements, denoted by ∅, or {} • A set with one element is called a singleton set • What is {∅}? • Answer: singleton Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.8 Subset Definition The set A is called a subset (tập con) of B iff every element of A is also an element of B, denoted by A ⊆ B. If A 6= B, we write A ⊂ B and say A is a proper subset (tập con thực sự) of B. • ∀x(x ∈ A→ x ∈ B) • For every set S, (i) ∅ ⊆ S, (ii) S ⊆ S. Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.9 Cardinality Definition If S has exactly n distinct elements where n is non-negative integers, S is finite set (tập hữu hạn), and n is cardinality (bản số ) of S, denoted by |S|. Example • A is the set of odd positive integers less than 10. |A| = 5. • S is the letters in Vietnamese alphabet, |S| = 29. • Null set |∅| = 0. Definition A set that is infinite if it is not finite. Example • Set of positive integers is infinite Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.10 Power Set Definition Given a set S, the power set (tập lũy thừa) of S is the set of all subsets of the set S, denoted by P (S). Example What is the power set of {0, 1, 2}? P ({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}} Example • What is the power set of the empty set? • What is the power set of the set {∅} Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.11 Power Set Theorem If a set has n elements, then its power set has 2n elements. Prove using induction! Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.12 Ordered n-tuples Definition The ordered n-tuple (dãy sắp thứ tự) (a1, a2, . . . , an) is the ordered collection that has a1 as its first element, a2 as its second element, . . ., and an as its nth element. Definition Two ordered n-tuples (a1, a2, . . . , an) = (b1, b2, . . . , bn) iff ai = bi, for i = 1, 2, . . . , n. Example 2-tuples, or ordered pairs (cặp), (a, b) and (c, d) are equal iff a = c and b = d Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.13 Cartesian Product • René Descartes (1596–1650) Definition Let A and B be sets. The Cartesian product (tích Đề-các) of A and B, denoted by A×B, is the set of ordered pairs (a, b), where a ∈ A and b ∈ B. Hence, A×B = {(a, b) | a ∈ A ∧ b ∈ B} Example Cartesian product of A = {1, 2} and B = {a, b, c}. Then A×B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)} Show that A×B 6= B ×A Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.14 Cartesian Product Definition A1×A2×· · ·×An = {(a1, a2, . . . , an) | ai ∈ Ai for i = 1, 2, . . . , n} Example A = {0, 1}, B = {1, 2}, C = {0, 1, 2}. What is A×B × C? A×B × C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)} Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.15 Union Definition The union (hợp) of A and B A ∪ B = {x | x ∈ A ∨ x ∈ B} A B A ∪B • Example: • {1,2,3} ∪ {2,4} = {1,2,3,4} • {1,2,3} ∪ ∅ = {1,2,3} Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.16 Intersection Definition The intersection (giao) of A and B A ∩ B = {x | x ∈ A ∧ x ∈ B} A B A ∩B Example: • {1,2,3} ∩ {2,4} = {2} • {1,2,3} ∩ N = {1,2,3} Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.17 Union/Intersection n⋃ i=1 Ai = A1 ∪ A2 ∪ ... ∪ An = {x | x ∈ A1 ∨ x ∈ A2 ∨ ... ∨ x ∈ An} n⋂ i=1 Ai = A1 ∩ A2 ∩ ... ∩ An = {x | x ∈ A1 ∧ x ∈ A2 ∧ ... ∧ x ∈ An} Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.18 Difference Definition The difference (hiệu) of A and B A − B = {x | x ∈ A ∧ x /∈ B} A B A−B Example: • {1,2,3} - {2,4} = {1,3} • {1,2,3} - N = ∅ Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.19 Complement Definition The complement (phần bù) of A A = {x | x /∈A} Example: • A = {1,2,3} then A = ??? • Note that A - B = A ∩ B Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.20 Set Identities A ∪ ∅ = A Identity laws A ∩ U = A Luật đồng nhất A ∪ U = U Domination laws A ∩ ∅ = ∅ Luật nuốt A ∪A = A Idempotent laws A ∩A = A Luật lũy đẳng (A¯) = A Complementation law Luật bù Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.21 Set Identities A ∪B = B ∪A Commutative laws A ∩B = B ∩A Luật giao hoán A ∪ (B ∪ C) = (A ∪B) ∪ C Associative laws A ∩ (B ∩ C) = (A ∩B) ∩ C Luật kết hợp A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C) Distributive laws A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C) Luật phân phối A ∪ B = A ∩ B De Morgan’s laws A ∩ B = A ∪ B Luật De Morgan Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.22 Method of Proofs of Set Equations To prove A = B, we could use • Venn diagrams • Prove that A ⊆ B and B ⊆ A • Use membership table • Use set builder notation and logical equivalences Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.23 Example (1) Example Verify the distributive rule P ∪ (Q ∩R) = (P ∪Q) ∩ (P ∪R) Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.24 Example (2) Example Prove: A ∩B = A ∪B (1) Show that A ∩B ⊆ A ∪B Suppose that x ∈ A ∩B By the definition of complement, x /∈ A ∩B So, x /∈ A or x /∈ B Hence, x ∈ A¯ or x ∈ B¯ We conclude, x ∈ A ∪B Or, A ∩B ⊆ A ∪B (2) Show that A ∪B ⊆ A ∩B Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.25 Example (3) Prove: A ∩B = A ∪B A B A ∩B A ∩B A¯ ∪ B¯ 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.26 Example (4) Prove: A ∩B = A ∪B A ∩B = {x|x 6∈ A ∩B} = {x|¬(x ∈ A ∩B)} = {x|¬(x ∈ A ∧ x ∈ B)} = {x|¬(x ∈ A) ∨ ¬(x ∈ B)} = {x|x 6∈ A ∨ x 6∈ B} = {x|x ∈ A ∨ x ∈ B} = {x|x ∈ A ∪B} Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.27 Introduction • Each student is assigned a grade from set {0, 0.1, 0.2, 0.3, . . . , 9.9, 10.0} at the end of semester • Function is extremely important in mathematics and computer science • linear, polynomial, exponential, logarithmic,... • Don’t worry! For discrete mathematics, we need to understand functions at a basic set theoretic level Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.28 Function Definition Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element of B to each element of A. • f : A→ B • A: domain (miền xác định) of f • B: codomain (miền giá trị) of f • For each a ∈ A, if f(a) = b • b is an image (ảnh) of a • a is pre-image (nghịch ảnh/tạo ảnh) of f(a) • Range of f is the set of all images of elements of A • f maps (ánh xạ) A to B A B a b = f(a) f f Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.29 Example Example: • y is an image of d • c is a pre-image of z Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.30 Example Example What are domain, codomain, and range of the function that assigns grades to students includes: student A: 5, B: 3.5, C: 9, D: 5.2, E: 4.9? Example Let f : Z→ Z assign the the square of an integer to this integer. What is f(x)? Domain, codomain, range of f? • f(x) = x2 • Domain: set of all integers • Codomain: Set of all integers • Range of f : {0, 1, 4, 9, . . .} Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.31 Add and multiply real-valued functions Definition Let f1 and f2 be functions from A to R. Then f1 + f2 and f1f2 are also functions from A to R defined by (f1 + f2)(x) = f1(x) + f2(x) (f1f2)(x) = f1(x)f2(x) Example Let f1(x) = x 2 and f2(x) = x− x2. What are the functions f1 + f2 and f1f2? (f1 + f2)(x) = f1(x) + f2(x) = x 2 + x− x2 = x (f1f2)(x) = f1(x)f2(x) = x 2(x− x2) = x3 − x4 Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.32 Image of a subset Definition Let f : A→ B and S ⊆ A. The image of S: f(S) = {f(s) | s ∈ S} f({a, b, c, d}) = {x, y, z} Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.33 One-to-one Definition A function f is one-to-one or injective (đơn ánh) if and only if ∀a∀b (f(a) = f(b)→ a = b) • Is f : Z→ Z, f(x) = x + 1 one-to-one? • Is f : Z→ Z, f(x) = x2 one-to-one? Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.34 Onto Definition f : A→ B is onto or surjective (toàn ánh) if and only if ∀b ∈ B, ∃a ∈ A : f(a) = b • Is f : Z→ Z, f(x) = x + 1 onto? • Is f : Z→ Z, f(x) = x2 onto? Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.35 One-to-one and onto (bijection) Definition f : A→ B is bijective (one-to-one correspondence) (song ánh) if and only if f is injective and surjective • Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f(a) = 4, f(b) = 2, f(c) = 1, f(d) = 3. Is f a bijection? Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.36 Example Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.37 Inverse function (Hàm ngược) Definition Let f : A→ B be a bijection then the inverse of f is the function f− : B → A defined by if f(a) = b then f−(b) = a A one-to-one correspondence is call invertible (khả nghịch) because we can define the inverse of this function. A B a = f−1(b) b = f(a) f(a) f−1(b) f−1 f Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.38 Example Example A = {a, b, c} and B = {1, 2, 3} with f(a) = 2 f(b) = 3 f(c) = 1 f is invertible and its inverse is f−1(1) = c f−1(2) = a f−1(3) = b Example Let f : R→ R with f(x) = x2. If f invertible? Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.39 Example f : R→ R f(x) = 2x + 1 f−1 : R→ R f−1(x) = x− 1 2 Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.40 Function Composition Definition Given a pair of functions g : A→ B and f : B → C. Then the composition (hợp thành) of f and g, denoted f ◦ g is defined by f ◦ g : A→ C f ◦ g(a) = f(g(a)) Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.41 Example Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.42 Graphs of Functions Example The graph of f(x) = x2 from Z to Z. (−3, 9) (−2, 4) (−1, 1) (0, 0) (1, 1) (2, 4) (3, 9) Definition Let f be a function from the set A to the set B. The graph of the function f is the set of ordered pairs {(a, b) | a ∈ A and f(a) = b}. Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.43 Important Functions Definition Floor function (hàm sàn) of x (bxc): the largest integer ≤ x b 12c = 0, b3.1c = 3, b7c = 7 Ceiling function (hàm trần) of x (dxe): the smallest integer ≥ x d 12e = 1, d3.1e = 4, d7e = 7 Bảng: Properties (n is an integer, x is a real number) (1a) bxc = n iff n ≤ x < n + 1 (1b) dxe = n iff n− 1 < x ≤ n (1c) bxc = n iff x− 1 < n ≤ x (1d) dxe = n iff x ≤ n < x + 1 (2) x− 1 < bxc ≤ dxe < x + 1 (3a) b−xc = −dxe (3b) d−xe = −bxc (4a) bx + nc = bxc+ n (4b) dx + ne = dxe+ n Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.44 Sequences What are the rule of these sequences (dãy)? Example 1, 3, 5, 7, 9, . . . an = 2n− 1 Arithmetic sequence (cấp số cộng) Example 1, 12 , 1 4 , 1 8 , 1 16 , . . . an = 1 2n−1 Geometric sequence (cấp số nhân) Example {an} 5, 11, 17, 23, 29, 35, 41, 47, . . . an = 6n− 1 {bn} 1, 7, 25, 79, 241, 727, 2185, . . . bn = 3n − 2 Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.45 Recurrence Relations Example {an} 5, 11, 17, 23, 29, 35, 41, 47, . . . an = an−1 + 6 for n = 2, 3, 4, . . . and a1 = 5 Recurrence relations: công thức truy hồi Definition (Fibonacci Sequence) Initial condition: f0 = 0 and f1 = 1 fn = fn−1 + fn−2 for n = 2, 3, 4, . . . Example Find the Fibonacci numbers f2, f3, f4, f5 and f6 f2 = f1 + f0 = 1 + 0 = 1 f3 = f2 + f1 = 1 + 1 = 2 f4 = f3 + f2 = 2 + 1 = 3 f5 = f4 + f3 = 3 + 2 = 5 f6 = f5 + f4 = 5 + 3 = 8 Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.46 Exercise (1) Initial deposit: $10,000 Interest: 11%/year, compounded annually (lãi suất kép) After 30 years, how much do you have in your account? Solution: Let Pn be the amount in the account after n years. The sequence {Pn} satisfies the recurrence relation Pn = Pn−1 + 0.11Pn−1 = (1.11)Pn−1. The initial condition is P0 = 10, 000 Step 1. Solve the recurrence relation (iteration technique) P1 = (1.11)P0 P2 = (1.11)P1 = (1.11) 2P0 P3 = (1.11)P2 = (1.11) 3P0 ... Pn = (1.11)Pn−1 = (1.11)nP0. Step 2. Calculate P30 = (1.11) 3010, 000 = $228, 922.97. Sets and Functions Nguyen An Khuong, Huynh Tuong Nguyen Contents Sets Set Operation Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.47 Exercise (2) What is the 2012th number in the sequence {xn}: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6,. . . Solution: In this sequence