离散数学英文讲义：2.3 Functions

1、L o g oL o g o1 1Discrete MathematicsDr. Han HuangSouth China University of TechnologyL o g oL o g o2 2Section 2.3Chapter 2. Logic and Proof, Sets, and FunctionL o g oL o g oContentsIntroduction1 One to One Function and Onto Function 2Inverse Functions and Composition of Functions 3Graph and Some Ca

2、se of Important Function4L o g oL o g oIntroductionL o g oL o g oFunctionsvFrom 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 function can be generalized to the

3、 concept of assigning elements of any set to elements of any set.vFunctions are also called operators.L o g oL o g oFunction: 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 generalizations of this idea:

4、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 oL o g ovWe 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 subset of A x B. But functi

5、ons 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 is then a curve (set o

6、f points), with only one y for each x. L o g oL o g ovFunctions can be represented graphically in several ways:ABabffxyPlotBipartite GraphLike Venn diagramsABL o g oL o g oFunctions Weve Seen So FarvA proposition might be viewed as a function from “situations” to truth values T,F p=“It is raining.”

7、s=our situation here,now p(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 oL o g oMore functions so farvA predicate can be viewed as a function from objects to propositions: P : “is 7 fe

8、et 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 oL o g oStill 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. Suppose U=

9、0,1,2,3,4. Then S=1,3 S(0)=S(2)=S(4)=F, S(1)=S(3)=T.L o g oL o g oStill 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 oL o g oA new notationvSometimes we write YX to denote the set F of all possible functions f:

10、XY.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 oL o g oA 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

11、 of all 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 oL o g oSome Function TerminologyvIf f:AB, and f(a)=b (where aA & bB), then we say: A i

12、s the domain 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 oL o g oRange versus CodomainvThe range of a function may not be its who

13、le codomain.vThe codomain 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

14、 g oL o g oRange vs. Codomain - 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

15、 is _.A,B,C,D,EunknownA,Bstill A,B,C,D,EL o g oL o g o(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

16、.vAnother example: and are binary operators on the set of all sets.L o g oL o g oImages 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.

17、L o g oL o g oOne-to-One Functions and Onto FunctionsL o g oL o g oOne-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

18、 the domain is mapped to any given one element of the range. In this case, domain & range have same cardinality. What about codomain?L o g oL o g oOne-to-One IllustrationvAre these relations one-to-one functions?L o g oL o g oOne-to-One IllustrationvAre these relations one-to-one functions?One-t

19、o-oneL o g oL o g oOne-to-One IllustrationvAre these relations one-to-one functions?One-to-oneNot one-to-oneL o g oL o g oOne-to-One IllustrationvAre these relations one-to-one functions?One-to-oneNot one-to-oneNot even a function!L o g oL o g oSufficient Conditions for 1-1nessvFor functions f over

20、numbers, we say: f is strictly increasing iff xy f(x)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 oL o g ov If f is either strictly increa

21、sing or strictly decreasing, then f is one-to-one.Does the converse hold? NOv E.g., f:NN such thatif x is even then f(x)=x+1if x is odd then f(x)=x-1L o g oL o g oOnto (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)

22、.vConsider “country of birth of”: AB,where A=people, B=countries. Is this a function? Is it an injection? Is it a surjection?L o g oL o g oOnto (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,wher

23、e A=people, B=countries. Is this a function? Yes (always 1 c.o.b.) Is it an injection? No (many have same c.o.b.) Is it a surjection? Probably yes L o g oL o g oOnto (Surjective) FunctionsvA function f:AB is onto or surjective or a surjection iff its range is equal to its codomain. vIn predicate log

24、ic: bBaA f(a)=bL o g oL o g oOnto (Surjective) FunctionsvA function f:AB 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 &

25、amp; codomain R, x3 is onto, whereas x2 isnt. (Why not?)L o g oL o g oOnto (Surjective) 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

26、 such that for all x, f(x)=x3.Consider any negative number a=-b in R.Let z be such that z3=b. Then (-z)3=-b=aL o g oL o g oThe 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

27、 o g oL o g oThe Identity Functionv For any domain A, the identity function I:AA (also written IA) on A is the function such that aA I(a)=a.v Is the identity function 1. one-to-one (injective)?2. onto (surjective)?L o g oL o g oThe Identity Functionv For any domain A, the identity function I:AA (als

28、o written IA) on A is the function such that aA I(a)=a.v Is the identity function 1. one-to-one (injective)? Yes2. onto (surjective)? YesL o g oL o g ovThe identity function:Identity Function IllustrationsDomain and rangexyy = I(x) = xL o g oL o g oIllustration of OntovAre these functions onto their

29、 depicted co-domains?L o g oL o g oIllustration of OntovAre these functions onto?L o g oL o g oIllustration of OntovAre these functions onto?ontonot ontoontonot ontoL o g oL o g oIllustration of OntovAre these functions 1-1?ontonot ontoontonot ontoL o g oL o g oIllustration of OntovAre these functio

30、ns 1-1?not 1-1ontonot 1-1not onto1-1onto1-1not ontoL o g oL o g oInverse Function and Composition of FunctionsL o g oL o g oBijectionsvA 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 oL o g oTwo terminologies for talking about functions1.

31、 injection = one-to-one2. surjection = onto3. bijection = one-to-one correspondence3 = 1&2L o g oL o g oBijectionsvFor bijections 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 .

32、L o g oL o g oBijectionsvFor bijections 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 (recall that IA is the identity function on A)AIff1L o g oL o g oBijectionsvExample 1: Let f: Z

33、Z 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 oL o g oBijectionsvExample 1: Let f: ZZ be defined 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: Ifhh(f(x) = (x+1)-1 = xL o g oL o g oBijectionsvEx

34、ample 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 function 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 oL o g oOperators over functionsvIf (“dot”) is an n

35、-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, we define(f g):AB to be the function defined by:aA, (f g)(a) = f(a)g(a).L o g oL o g oFunction Operator Examplev , (plus,times) are binary opera

36、tors 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, where (f g)(x) = f(x) g(x)L o g oL o g oFunction Composition OperatorvFor functions g:AB and f:BC, there is a special operator called comp

37、ose (“”). 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 defined and f(g(a)C. Note that is non-commutative (i.e., we dont always have fg = gf).Note match here.L o g oL o g oFunction Compositio

38、n Operator“We dont always have fg = gf “Can you express this in predicate logic?L o g oL o g oFunction Composition Operator“We dont always have fg = gf “Can you express this in 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

39、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 oL o g oGraph and Some Case of Important FunctionL o g oL o g oAside About RepresentationsvIt is possible to represent any type of discrete structu

40、re (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 the others. However, logic, and sets are often used as the foundation for all else. E.g. in L o g oL o g oA Couple of Key