FunctionsOutlineIntroductionDefinition: FunctionTerminologyFunction: VisualizationMore Definitions (1)More Definitions (2)Image of a set: ExampleMore Definitions (3)Slide 11Definition: InjectionDefinition: SurjectionDefinition: BijectionFunctions: Example 1Functions: Example 2Functions: Example 3Functions: Example 4Functions: Example 5Exercice 1Exercise 1 (cont’d)Exercise 2Exercice 3Exercice 3: AnswerExercice 4Exercice 4: AnswerExercise 5Exercice 5: f is one-to-oneExercice 5: f is not ontoSlide 30Inverse Functions (1)Inverse Functions (2)Inverse Functions: RepresentationInverse Functions: Example 1Inverse Functions: Example 2Inverse Functions: Example 2 (cont’)Inverse Functions: Example 3Function Composition (1)Function Composition (2)Composition: Graphical RepresentationComposition: Example 1Composition: Example 1 (cont’)Function EqualityAssociativitySlide 45Important Functions: IdentityInverses and IdentityImportant Functions: Absolute ValueImportant Functions: Floor & CeilingImportant Functions: FloorImportant Functions: CeilingImportant Function: FactorialFactorial Function & Stirling’s ApproximationSummaryFunctionsSection 2.3 of RosenFall 2008CSCE 235 Introduction to Discrete StructuresCourse web-page: cse.unl.edu/~cse235Questions: [email protected] 235, Fall 20082Outline•Definitions & terminology–function, domain, co-domain, image, preimage (antecedent), range, image of a set, strictly increasing, strictly decreasing, monotonic•Properties–One-to-one (injective), onto (surjective), one-to-one correspondence (bijective)–Exercices (5)•Inverse functions (examples)•Operators–Composition, Equality•Important functions–identity, absolute value, floor, ceiling, factorialFunctionsCSCE 235, Fall 20083Introduction•You have already encountered function–f(x,y) = x+y–f(x) = x–f(x) = sin(x)•Here we will study functions defined on discrete domains and ranges.•We will generalize functions to mappings•We may not always be able to write function in a ‘neat way’ as aboveFunctionsCSCE 235, Fall 20084Definition: Function•Definition: A function f from a set A to a set B is an assignment of exactly one element of B to each element of A.•We write f(a)=b if b is the unique element of B assigned by the function f to the element aA.•If f is a function from A to B, we writef: A BThis can be read as ‘f maps A to B’•Note the subtlety–Each and every element of A has a single mapping–Each element of B may be mapped to by several elements in A or not at allFunctionsCSCE 235, Fall 20085Terminology•Let f: A B and f(a)=b. Then we use the following terminology:–A is the domain of f, denoted dom(f)–B is the co-domain of f–b is the image of a–a is the preimage (antecedent) of b–The range of f is the set of all images of elements of A, denoted rng(f)FunctionsCSCE 235, Fall 20086Function: VisualizationA function, f: A BABabfDomain Co-DomainPreimage Image, f(a)=bRangeFunctionsCSCE 235, Fall 20087More Definitions (1)•Definition: Let f1 and f2 be two functions from a set A to R. Then f1+f2 and f1f2 are also function from A to R defined by:–(f1+f2)(x) = f1(x) + f2(x)–f1f2(x)= f1(x)f2(x)•Example: Let f1(x)=x4+2x2+1 and f2(x)=2-x2–(f1+f2)(x) = x4+2x2+1+2-x2 = x4+x2+3 –f1f2(x) = (x4+2x2+1)(2-x2)= -x6+3x2+2FunctionsCSCE 235, Fall 20088More Definitions (2)•Definition: Let f: A B and S A. The image of the set S is the subset of B that consists of all the images of the elements of S. We denote the image of S by f(S), so thatf(S)={ f(s) | sS}•Note there that the image of S is a set and not an element.FunctionsCSCE 235, Fall 20089Image of a set: Example•Let:–A = {a1,a2,a3,a4,a5}–B = {b1,b2,b3,b4,b5}–f={(a1,b2), (a2,b3), (a3,b3), (a4,b1), (a5,b4)}–S={a1,a3}•Draw a diagram for f•What is the:–Domain, co-domain, range of f?–Image of S, f(S)?FunctionsCSCE 235, Fall 200810More Definitions (3)•Definition: A function f whose domain and codomain are subsets of the set of real numbers (R) is called –strictly increasing if f(x)<f(y) whenever x<y and x and y are in the domain of f.–strictly decreasing if f(x)<f(y) whenever x<y and x and y are in the domain of f.•A function that is increasing or decreasing is said to be monotonicFunctionsCSCE 235, Fall 200811Outline•Definitions & terminology•Properties–One-to-one (injective)–Onto (surjective)–One-to-one correspondence (bijective)–Exercices (5)•Inverse functions (examples)•Operators•Important functionsFunctionsCSCE 235, Fall 200812Definition: Injection•Definition: A function f is said to be one-to-one or injective (or an injection) if x and y in in the domain of f, f(x)=f(y) x=y•Intuitively, an injection simply means that each element in the range has at most one preimage (antecedent)•It may be useful to think of the contrapositive of this definition x y f(x) f(y)FunctionsCSCE 235, Fall 200813Definition: Surjection•Definition: A function f: AB is called onto or surjective (or an surjection) if bB, aA with f(a)=b•Intuitively, a surjection means that every element in the codomain is mapped (i.e., it is an image, has an antecedent).•Thus, the range is the same as the codomainFunctionsCSCE 235, Fall 200814Definition: Bijection•Definition: A function f is a one-to-one correspondence (or a bijection), if is both one-to-one (injective) and onto (surjective)•One-to-one correspondences are important because they endow a function with an inverse. •They also allow us to have a concept cardinality for infinite sets•Let’s look at a few examples to develop a feel for these definitions…FunctionsCSCE 235, Fall 200815Functions: Example 1•Is this a function? Why?a1a2a3a4b1b2b3b4A B•No, because each of a1, a2 has two imagesFunctionsCSCE 235, Fall 200816Functions: Example 2•Is this a function–One-to-one (injective)? Why?–Onto (surjective)? Why?a1a2a3a4b1b2b3b4A BNo, b1 has 2 preimagesNo, b4 has no preimageFunctionsCSCE 235, Fall 200817Functions: Example 3•Is this a function–One-to-one (injective)? Why?–Onto (surjective)? Why?a1a2a3b1b2b3b4A BYes, no bi has 2 preimagesNo, b4 has no preimageFunctionsCSCE 235, Fall 200818Functions: Example 4a1a2a3a4b1b2b3A B•Is this a function–One-to-one (injective)? Why?–Onto (surjective)? Why?No, b3 has 2 preimagesYes, every bi has a preimageFunctionsCSCE 235, Fall 200819Functions: Example 5a1a2a3a4b1b2b3b4A B•Is
View Full Document
Unlocking...