Bài giảng Discrete Mathematics I - Chapter 4: Functions

Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.1 Chapter 4 Functions Discrete Mathematics I on 13 March 2012 Tran Vinh Tan Faculty of Computer Science and Engineering University of Technology - VNUHCM Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.2 Contents 1 Functions 2 One-to-one and Onto Functions 3 Sequences and Summation 4 Recursion Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.3 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.3 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.3 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.3 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 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) 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 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) 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 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) 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 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) 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 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) 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 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) 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 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) 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 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) 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 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) 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.4 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) 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.5 Example Example: • y is an image of d • c is a pre-image of z Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.5 Example Example: • y is an image of d • c is a pre-image of z Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.5 Example Example: • y is an image of d • c is a pre-image of z Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.5 Example Example: • y is an image of d • c is a pre-image of z Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.6 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, . . .} Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.6 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, . . .} Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.6 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, . . .} Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.7 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.7 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.8 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} Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.8 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} Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.8 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} Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.9 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? Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.9 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? Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.10 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? Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.11 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, bc, d} to {1, 2, 3, 4} with f(a) = 4, f(b) = 2, f(c) = 1, f(d) = 3. Is f a bijection? Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.12 Example Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.12 Example Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.12 Example Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.12 Example Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.12 Example Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.13 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.14 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? Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.14 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? Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.15 Example f : R→ R f(x) = 2x+ 1 f−1 : R→ R f−1(x) = x− 1 2 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.15 Example f : R→ R f(x) = 2x+ 1 f−1 : R→ R f−1(x) = x− 1 2 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.15 Example f : R→ R f(x) = 2x+ 1 f−1 : R→ R f−1(x) = x− 1 2 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.16 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)) Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.17 Example Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.17 Example Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.17 Example Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.17 Example Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.18 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}. Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.18 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}. Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.18 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}. Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.19 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.19 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.19 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 Functions Tran Vinh Tan Contents Functions One-to-one and Onto Functions Sequences and Summation Recursion 4.19 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) (