CompSci 102 © Michael Frank4.1Today’s topics••FunctionsFunctions– Notations and terms– One-to-One vs. Onto– Floor, ceiling, and identity••Reading: Sections 1.8Reading: Sections 1.8••UpcomingUpcoming––AlgorithmsAlgorithmsCompSci 102 © Michael Frank4.2On to section 1.8… Functions••From calculus, you are familiar with theFrom calculus, you are familiar with theconcept of a real-valued function concept of a real-valued function ff,,which assigns to each number which assigns to each number xxRR a aparticular value particular value yy==ff((xx), where ), where yyRR..••But, the notion of a function can also beBut, the notion of a function can also benaturally generalized to the concept ofnaturally generalized to the concept ofassigning elements of assigning elements of anyany set to elements set to elementsof of anyany set. (Also known as a set. (Also known as a mapmap.).)CompSci 102 © Michael Frank4.3Function: Formal Definition••For any sets For any sets AA, , BB, we say that a , we say that a functionfunction fffrom (or from (or ““mappingmapping””) A to B) A to B ( (ff::AABB) is a) is aparticular assignment of exactly oneparticular assignment of exactly oneelement element ff((xx))BB to each element to each element xxA.A.••Some further generalizations of this idea:Some further generalizations of this idea:––A A partial partial (non-(non-totaltotal)) function function ff assigns assigns zero orzero oroneone elements of elements of BB to each element to each element xxAA..––Functions of Functions of nn arguments; relations ( arguments; relations (chch. 6).. 6).CompSci 102 © Michael Frank4.4Graphical Representations••Functions can be represented graphically inFunctions can be represented graphically inseveral ways:several ways:••ABabff•••••••••xyPlotBipartite GraphLike Venn diagramsABCompSci 102 © Michael Frank4.5Functions We’ve Seen So Far••A A propositionproposition can be viewed as a function can be viewed as a functionfrom from ““situationssituations”” to truth values { to truth values {TT,,FF}}––A logic system called A logic system called situation theorysituation theory..––pp==““It is raining.It is raining.””; ; ss=our situation here,now=our situation here,now––pp((ss)){{TT,,FF}.}.••A A propositional operatorpropositional operator can be viewed as can be viewed asa function from a function from ordered pairsordered pairs of truth of truthvalues to truth values: values to truth values: e.g.e.g., , ((((FF,,TT)) = )) = TT..Another example: ((T,F)) = F.CompSci 102 © Michael Frank4.6A Neat Trick••Sometimes we write Sometimes we write YYXX to denote the set to denote the set FFof of allall possible functions possible functions ff::XXYY..••This notation is especially appropriate,This notation is especially appropriate,because for finite because for finite XX, , YY, we have , we have ||FF| = || = |YY||||XX||..••If we use representations If we use representations FF00, , TT11, , 22::{{00,,11}={}={FF,,TT}, then a subset }, then a subset TT SS is just a is just afunction from function from SS to to 22, so the power set of , so the power set of SS(set of all such fns.)(set of all such fns.) is is 22S S in this notation.in this notation.CompSci 102 © Michael Frank4.7Some Function Terminology••If it is written that If it is written that ff::AABB, and , and ff((aa)=)=bb(where (where aaAA & & bbBB), then we say:), then we say:––AA is the is the domaindomain of of ff..––BB is the is the codomaincodomain of of ff..––bb is the is the imageimage of of a a under under ff..––aa is a is a pre-imagepre-image of of bb under under f.f.••In general, In general, bb may have more than 1 pre-image. may have more than 1 pre-image.––The The rangerange RR BB of of f f is is RR={={bb | | aa ff((aa)=)=bb } }..We also saythe signatureof f is AB.CompSci 102 © Michael Frank4.8Range versus Codomain••The range of a function might The range of a function might notnot be its be itswhole whole codomaincodomain..••The The codomaincodomain is the set that the function is is the set that the function isdeclareddeclared to map all domain values into. to map all domain values into.••The range is the The range is the particularparticular set of values in set of values inthe the codomaincodomain that the function that the function actuallyactuallymaps elements of the domain to.maps elements of the domain to.CompSci 102 © Michael Frank4.9Range vs. Codomain - Example••Suppose I declare to you that: Suppose I declare to you that: ““ff is a is afunction mapping students in this class tofunction mapping students in this class tothe set of grades {A,B,C,D,E}.the set of grades {A,B,C,D,E}.””••At this point, you know At this point, you know ff’’ss codomaincodomain is: is:__________, and its range is ________.__________, and its range is ________.••Suppose the grades turn out all As and Bs.Suppose the grades turn out all As and Bs.••Then the range of Then the range of f f is _________, but itsis _________, but itscodomaincodomain is __________________. is __________________.CompSci 102 © Michael Frank4.10Operators (general definition)••An An nn-ary-ary operatoroperator overover (or (or onon) the set ) the set SS is isany function from the set of ordered any function from the set of ordered nn--tuplestuples of elements of of elements of SS, to , to SS itself. itself.••E.g.E.g., if , if SS={={TT,,FF}, }, ¬¬ can be seen as a unary can be seen as a unaryoperator, and operator, and ,, are binary operators on are binary operators on SS..••Another example: Another example: and and are binary are binaryoperators on the set of all sets.operators on the set of all sets.CompSci 102 © Michael Frank4.11Constructing Function Operators••If If •• ( (““dotdot””) is any operator over ) is any operator over BB, then we, then wecan extend can extend •• to also denote an operator to also denote an operatorover over functionsfunctions ff::AABB..••E.g.E.g.: Given any binary operator : Given any binary operator ••::BBBBBB,,and functions and functions ff,,gg::AABB, we define, we define((f f •• gg):):AABB to be the
View Full Document
Unlocking...