




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 【正版授权】 ISO/IEC/IEEE 8802-15-9:2024 EN Telecommunications and information exchange between systems - Local and metropolitan area networks specific requirements - Part 15-9: Transpor
- 电力施工承包合同(5篇)
- 口罩销售的合同(6篇)
- 房地产项目开发委托代理合同
- 文化旅游产业推广与合作经营合同
- 房产收购合作协议书
- 书面货物运输合同
- 互联网项目合作协议
- 可再生能源发电项目合作开发协议
- 制式装修合同
- CentOS 7系统配置与管理(Linux 试题库) 习题答案 (杨海艳 第2版)
- 中国氢内燃机行业发展环境、市场运行格局及前景研究报告-智研咨询(2024版)
- 开学季初三冲刺中考开学第一课为梦想加油课件
- 2025年四川绵阳科技城新区投资控股集团有限公司招聘笔试参考题库附带答案详解
- 2025年人教版英语五年级下册教学进度安排表
- 学校食堂餐厅管理者食堂安全考试题附答案
- 2025延长石油(集团)限责任公司社会招聘高频重点提升(共500题)附带答案详解
- 病原微生物安全
- 玻璃电动平移门施工方案
- 2.1大都市的辐射功能-以我国上海为例(第一课时)课件高中地理湘教版(2019)选择性必修2+
- 长鑫存储校招在线测评题库
评论
0/150
提交评论