离散数学英文课件：DM_lecture2_3 Functions

1、2.3: Functions,Def: Let A and B be sets. A function f: A B is a rule that assigns to each element a A exactly one element f(a) B. We also say that f : A B is a mapping from domain A to codomain B. f(a) is called the image of the element a, and the element a is called a preimage of f(a).,Graphical Re

2、presentations,Functions can be represented graphically in several ways:,A,B,a,b,f,f,x,y,Plot,Bipartite Graph,Like Venn diagrams,A,B,Some Function Terminology,If it is written that f:AB, and f(a)=b (where aA f(S)=image(S) f() = ; f-1() = ; f(a) = f(a); f(A U B) = f(A) U f(B); f(A B) f(A) f(B); f-1(A

3、U B) = f-1(A) U f-1(B); f-1(A B) = f-1(A) f-1(B),Proof of Misc. properties,f(A B) f(A) f(B)?,f(A B) = x : a (A B), f(a) = x,Choose an arbitrary x f(A B), and show that it must also be an element of f(A) f(B).,So, a (A B) such that f(a) = x.,If a A (it is), then f(a) = x f(A).,If a B (it is), then f(

4、a) = x f(B).,x f(A), and x f(B), so x f(A) f(B).,Proof of Misc. properties,f-1(A B) = f-1(A) f-1(B),Choose an arbitrary x f-1(A) f-1(B), and show that it must also be an element of f-1(A B).,If x f-1(A) (it is), then f(x) A.,If x f-1(B) (it is), then f(x) B.,so f(x) A B, and x f-1(A B).,Proof: (1) f

5、-1(A) f-1(B) f-1(A B),(2) f-1(A B) f-1(A) f-1(B) Trivial.,Function Operator Example, (“plus”,“times”) are binary operators over R. (Normal addition & multiplication.) Therefore, we can also add and multiply functions f,g:RR: (f g):RR, where (f g)(x) = f(x) g(x) (f g):RR, where (f g)(x) = f(x) g(x),O

6、ne-to-One (Injective) Functions,A function is one-to-one (1-1), or injective, or an injection, iff preimages are unique. Note: this means that if a b then f(a) f(b).,Bipartite (2-part) graph representations of functions that are (or not) one-to-one:,Onto (Surjective) Functions,A function f:AB is ont

7、o or surjective or a surjection iff its range is equal to its codomain (bB, aA: f(a)=b). Think: An onto function maps the set A onto (over, covering) the entirety of the set B, not just over a piece of it.,Illustration of Onto,Some functions that are, or are not, onto their codomains:,Onto(but not 1

8、-1),Not Onto(or 1-1),Both 1-1and onto,1-1 butnot onto,Bijections,A function f is said to be a one-to-one correspondence, or a bijection, or reversible, or invertible, iff it is both one-to-one and onto. For bijections f:AB, there exists an inverse of f, written f 1:BA, which is defined as: f 1(y) =

9、x iff f(x) = y,Illustration of Inverse,Note: No inverse exists unless f is a bijection.,Same Cardinality,Whenever there is a bijection from A to B, the two sets must have the same number of elements or the same cardinality. E.g. Let E = 0, 2, 4, 6, . . . . Then there is a bijection f from N to E, de

10、fined by f(x) = 2x. Hence, the set of even integers has the same cardinality as the set of natural numbers. OH, E LOOKS ONLY HALF AS BIG!,Composition,Definition: Let f: B C, g: A B. The composition of f with g, denoted f o g, is the function from A to C defined by f g(x) = f(g(x) If f(x) = x2 and g(

11、x) = 2x + 1, then f(g(x) = and g(f(x) = f 1 is the unique function such that where IA is the identity function on A,(2x+1)2,2x2 + 1,Illustration of Composition,Example,It follows that g must be an injection. However, f need not be an injection,Graphs of Functions,We can represent a function f:AB as

12、a set of ordered pairs (x,f(x) | xA. Note that x, there is only 1 pair (x,f(x). For functions over numbers, we can represent an ordered pair (x,y) as a point on a plane. A function is then drawn as a curve (set of points), with only one y for each x.,A Couple of Key Functions,In discrete math, we wi

13、ll frequently use the following two functions over real numbers: The floor function :RZ, where x (“floor of x”) means the largest (most positive) integer x. i.e., x : max(iZ|ix). The ceiling function :RZ, where x (“ceiling of x”) means the smallest (most negative) integer x. x : min(iZ|ix),Visualizi

14、ng Floor & Ceiling,Real numbers “fall to their floor” or “rise to their ceiling.” Note that if xZ,x x &x x Note that if xZ, x = x = x.,0,1,1,2,3,2,3,.,.,.,.,.,.,.,.,.,1.6,1.6=2,1.4= 2,1.4,1.4= 1,1.6=1,3,3=3= 3,Plots with floor/ceiling: Example,Plot of graph of function f(x) = x/3:,x,f(x),Set of poin

15、ts (x, f(x),+3,2,+2,3,Review of 2.3 (Functions),Function variables f, g, h, Notations: f:AB, f(a), f(A). Terms: image, preimage, domain, codomain, range, one-to-one, onto, strictly (in/de)creasing, bijective, inverse, composition. Function unary operator f 1, binary operators , , etc., and . The RZ functions x an