《离散数学英文讲义：2.3 Functions》由会员分享，可在线阅读，更多相关《离散数学英文讲义：2.3 Functions（64页珍藏版）》请在金锄头文库上搜索。
1、L o g o1 1Discrete MathematicsDr. Han HuangSouth China University of TechnologyL o g o2 2Section 2.3Chapter 2. Logic and Proof, Sets, and FunctionL o g o3 3 3 3ContentsIntroductionIntroduction1 One to One Function and Onto Function One to One Function and Onto Function 2Inverse Functions and Composi
2、tion of Functions 3Graph and Some Case of Important Function4L o g o4 4 4 4IntroductionL o g o5 5FunctionsvFrom calculus, you know the concept of a real-valued function f, which assigns to each number xR one particular value y=f(x), where yR.vExample: f defined by the rule f(x)=x2vThe notion of a fu
3、nction can be generalized to the concept of assigning elements of any set to elements of any set.vFunctions are also called operators.L o g o6 6Function: Formal DefinitionvA function f from (or “mapping”) A to B (f:AB) is an assignment of exactly one element f(x)B to each element xA.vSome further ge
4、neralizations of this idea:Functions of n arguments: f: (A1 x A2. x An) B. A partial (non-total) function f assigns zero or one elements of B to each element x A.L o g o7 7vWe can represent a function f:AB as a set of ordered pairs f =(a,f(a) | aA.vThis makes f a relation between A and B:f is a subs
5、et of A x B. But functions are special:for every aA, there is at least one pair (a,b). Formally: aAbB(a,b)f) for every aA, there is at most one pair (a,b). Formally: a,b,c(a,b)f (a,c)f bc) vA relation over numbers can be represent as a set of points on a plane. (A point is a pair (x,y).)A function i
6、s then a curve (set of points), with only one y for each x. L o g o8 8vFunctions can be represented graphically in several ways:ABabffxyPlotBipartite GraphLike Venn diagramsABL o g o9 9Functions Weve Seen So FarvA proposition might be viewed as a function from “situations” to truth values T,Fp=“It i
7、s raining.”s=our situation here,nowp(s)T,F.vA propositional operator can be viewed as a function from ordered pairs of truth values to truth values: e.g., (F,T) = T.Another example: (T,F) = F.L o g o1010More functions so farvA predicate can be viewed as a function from objects to propositions: P : “
8、is 7 feet tall”; P(Mike) = “Mike is 7 feet tall.”vA set S over universe U can be viewed as a function from the elements of U to .L o g o1111Still More FunctionsvA set S over universe U can be viewed as a function from the elements of U to T, F, saying for each element of U whether it is in S. Suppos
9、e U=0,1,2,3,4. Then S=1,3 S(0)=S(2)=S(4)=F, S(1)=S(3)=T.L o g o1212Still More FunctionsvA set operator such as or can be viewed as a function from ordered pairs of sets, to sets. Example: (1,3,3,4) = 3L o g o1313A new notationvSometimes we write YX to denote the set F of all possible functions f: XY
10、.vThus, f YX is another way of saying that f: XY.v(This notation is especially appropriate, because for finite X, Y, we have |F| = |Y|X|. )L o g o1414A Neat TrickvIf we use representations F0, T1, then a subset TS is a function from S to 0,1, vTherefore, P(S) can be represented as 0,1S (the set of a
11、ll functions from S to 0,1 )v(Note that if we also represent 2:0,1, then P(S) can be represented as 2S . The power set of S is sometimes written this way to stress the cardinality of the power set.)L o g o1515Some Function TerminologyvIf f:AB, and f(a)=b (where aA & bB), then we say:A is the domain
12、of f. B is the codomain of f.b is the image of a under f.a is a pre-image of b under f.In general, b may have more than 1 pre-image.The range R B of f is R=b | a f(a)=b .We also saythe signatureof f is AB.L o g o1616Range versus CodomainvThe range of a function may not be its whole codomain.vThe cod
13、omain is the set that the function is declared to map all domain values into.vThe range is the particular set of values in the codomain that the function actually maps elements of the domain to.v(One might say: The range is the smallest set that could be used as its codomain.)L o g o1717Range vs. Co
14、domain - ExamplevSuppose I declare to you that: “f is a function mapping students in this class to the set of grades A,B,C,D,E.”vAt this point, you know fs codomain is: _, and its range is _.vSuppose the grades turn out all As and Bs.vThen the range of f is _, but its codomain is _.A,B,C,D,EunknownA
15、,Bstill A,B,C,D,EL o g o1818(n-ary) functions on a setvAn n-ary function (also: n-ary operator) over (also: on) S is any function from the set of ordered n-tuples of elements of S, to S itself.vE.g., if S=T,F, can be seen as a unary operator, and , are binary operators on S.vAnother example: and are
16、 binary operators on the set of all sets.L o g o1919Images of Sets under FunctionsvGiven f:AB, and SA,vThe image of S under f is the set of all images (under f) of the elements of S.f(S) : f(s) | sS : b | sS: f(s)=b.vThe range of f equalsthe image (under f) of fs domain.L o g o20202020One-to-One Fun
17、ctions and Onto FunctionsL o g o2121One-to-One FunctionsvA function is one-to-one (1-1), or injective, or an injection, iff every element of its range has only 1 pre-image. Formally: given f:AB,“x is injective” : (x,y: x y f(x) f(y).vIn other words: only one element of the domain is mapped to any gi
18、ven one element of the range.In this case, domain & range have same cardinality. What about codomain?L o g o2222One-to-One IllustrationvAre these relations one-to-one functions?L o g o2323One-to-One IllustrationvAre these relations one-to-one functions?One-to-oneL o g o2424One-to-One IllustrationvAr
19、e these relations one-to-one functions?One-to-oneNot one-to-oneL o g o2525One-to-One IllustrationvAre these relations one-to-one functions?One-to-oneNot one-to-oneNot even a function!L o g o2626Sufficient Conditions for 1-1nessvFor functions f over numbers, we say:f is strictly increasing iff xy f(x
20、)f(y) for all x,y in domain;f is strictly decreasing iff xy f(x)f(y) for all x,y in domain;vIf f is either strictly increasing or strictly decreasing, then f must be one-to-one.Does the converse hold?L o g o2727vIf f is either strictly increasing or strictly decreasing, then f is one-to-one.Does the
21、 converse hold? NOvE.g., f:NN such thatif x is even then f(x)=x+1if x is odd then f(x)=x-1L o g o2828Onto (Surjective) FunctionsvA function f:AB is onto or surjective or a surjection iff its range is equal to its codomain (bB, aA: f(a)=b).vConsider “country of birth of”: AB,where A=people, B=countri
22、es. Is this a function? Is it an injection? Is it a surjection?L o g o2929Onto (Surjective) FunctionsvA function f:AB is onto or surjective or a surjection iff its range is equal to its codomain vConsider “country of birth of”: AB,where A=people, B=countries. Is this a function? Yes (always 1 c.o.b.
23、) Is it an injection? No (many have same c.o.b.) Is it a surjection? Probably yes L o g o3030Onto (Surjective) FunctionsvA function f:AB is onto or surjective or a surjection iff its range is equal to its codomain. vIn predicate logic: bBaA f(a)=bL o g o3131Onto (Surjective) FunctionsvA function f:A
24、B is onto or surjective or a surjection iff its range is equal to its codomain (bBaA f(a)=b).vThink: An onto function maps the set A onto (over, covering) the entirety of the set B, not just over a piece of it.vE.g., for domain & codomain R, x3 is onto, whereas x2 isnt. (Why not?)L o g o3232Onto (Su
25、rjective) FunctionsE.g., for domain & codomain R, x3 is onto, but x2 is not. (Why not?)vConsider f:RR such that, for all x, f(x)=x2.Consider any negative number a=-b in R. x(x2=a). So f is not surjective.vConsider f:RR such that for all x, f(x)=x3.Consider any negative number a=-b in R.Let z be such
26、 that z3=b. Then (-z)3=-b=aL o g o3333The Identity FunctionvFor any domain A, the identity function I:AA (also written IA) on A is the function such that everything is mapped to itselfvIn predicate logic:aA I(a)=a.L o g o3434The Identity FunctionvFor any domain A, the identity function I:AA (also wr
27、itten IA) on A is the function such that aA I(a)=a.vIs the identity function 1.one-to-one (injective)?2.onto (surjective)?L o g o3535The Identity FunctionvFor any domain A, the identity function I:AA (also written IA) on A is the function such that aA I(a)=a.vIs the identity function 1.one-to-one (i
28、njective)? Yes2.onto (surjective)? YesL o g o3636vThe identity function:Identity Function IllustrationsDomain and rangexyy = I(x) = xL o g o3737Illustration of OntovAre these functions onto their depicted co-domains?L o g o3838Illustration of OntovAre these functions onto?L o g o3939Illustration of
29、OntovAre these functions onto?ontonot ontoontonot ontoL o g o4040Illustration of OntovAre these functions 1-1?ontonot ontoontonot ontoL o g o4141Illustration of OntovAre these functions 1-1?not 1-1ontonot 1-1not onto1-1onto1-1not ontoL o g o42424242Inverse Function and Composition of FunctionsL o g
30、o4343BijectionsvA function is said to be a one-to-one correspondence, or a bijection iff it is both one-to-one and onto.L o g o4444Two terminologies for talking about functions1.injection = one-to-one2.surjection = onto3.bijection = one-to-one correspondence3 = 1&2L o g o4545BijectionsvFor bijection
31、s f:AB, there exists an inverse of f, written f 1: BAvIntuitively, this is the function that undoes everything that f doesvFormally, its the unique function such that .L o g o4646BijectionsvFor bijections f:AB, there exists an inverse of f, written f 1: BAvIntuitively, this is the function that undo
32、es everything that f doesvFormally, its the unique function such that (recall that IA is the identity function on A)L o g o4747BijectionsvExample 1: Let f: ZZ be defined as f(x)=x+1. What is f1 ?vExample 2: Let g: ZN be defined as g(x)=|x|. What is g1 ?L o g o4848BijectionsvExample 1: Let f: ZZ be d
33、efined as f(x)=x+1. What is f1 ?vf1 is the function (lets call it h) h: ZZ defined as h(x)=x-1. vProof: h(f(x) = (x+1)-1 = xL o g o4949BijectionsvExample 2: Let g: ZN be defined as g(x)=|x|. What is g1 ?vThis was a trick question: there is no such function, since g is not a bijection:There is no fun
34、ction h such that h(|x|)=x and h(|x|)=x v(NB There is a relation h for which this is true.)L o g o5050Operators over functionsvIf (“dot”) is an n-ary operator over B, then we can extend to also denote an operator over functions from A to B.vE.g.: Given any binary operator :BBB, and functions f,g:AB,
35、 we define(f g):AB to be the function defined by:aA, (f g)(a) = f(a)g(a).L o g o5151Function Operator Examplev , (plus,times) are binary operators over R. (Normal addition & multiplication.)vTherefore, we can also “add” and “multiply” functions f,g:RR:(f g):RR, where (f g)(x) = f(x) g(x)(f g):RR, wh
36、ere (f g)(x) = f(x) g(x)L o g o5252Function Composition OperatorvFor functions g:AB and f:BC, there is a special operator called compose (“”).It composes (creates) a new function out of f and g by applying f to the result of applying g.We say (fg):AC, where (fg)(a) : f(g(a).g(a)B, so f(g(a) is defin
37、ed and f(g(a)C.Note that is non-commutative (i.e., we dont always have fg = gf).Note match here.L o g o5353Function Composition Operator“We dont always have fg = gf “Can you express this in predicate logic?L o g o5454Function Composition Operator“We dont always have fg = gf “Can you express this in
38、predicate logic? ( f g x(fg(x) =gf (x). Do not write: f g x(fg(x) gf (x) (Note that this formula quantifies over functions as well as ordinary objects something that is not possible in First Order Predicate Logic (FOPL), which is what was taught earlier in this course.)L o g o55555555Graph and Some
39、Case of Important FunctionL o g o5656Aside About RepresentationsvIt is possible to represent any type of discrete structure (propositions, bit-strings, numbers, sets, ordered pairs, functions) in terms of some combination of other structures.vPerhaps none of these structures is more fundamental than
40、 the others. However, logic, and sets are often used as the foundation for all else. E.g. in L o g o5757A Couple of Key FunctionsvIn discrete math, we frequently use the following two functions over real numbers:The floor function :RZ, where x (“floor of x”) means the largest integer x. I.e., x : ma
41、x(i Z|ix).The ceiling function :RZ, where x (“ceiling of x”) means the smallest integer x. x : min(i Z|ix)L o g o5858Visualizing Floor & CeilingvReal numbers “fall to their floor” or “rise to their ceiling.”0 1123 2 3. .1.6 1.6 =21.4 = 2 1.41.4 = 1 1.6 =1 33 =3 = 3L o g o5959Do these equalities hold
42、?vx = x &x = x L o g o6060It depends on whether x is an integervIf x Z then x = x = x, sox = x = x &x = x = x vBut if x Z, thenx x &x x vE.g., 3.4 = 4 3 = 3.4 L o g o6161Plots with floor/ceilingvNote that for f(x)= x , the graph of f includes the point (a, 0) for all values of a such that a 0 and a1
43、, but not for the value a=1. vx R : x = 0 = (informally) = 0,.,0.1,.0.2,.,0.9, does not include its limit 1. Sets that do not include all of their limit points are generally called open sets. vIn a plot, we draw a limit point of a curve using an open dot (circle) if the limit point is not on the curve, and with a closed (solid) dot if it is on the curve.L o g o6262Plots with floor/ceiling: ExamplevPlot of graph of function f(x) = x/3:xf(x)Set of points (x, f(x)+32+23L o g o6363vP119v30 b) c)L o g o646464
