离散数学 函数

Content第五章函数本章主要介绍函数的概念函数的复合逆函数函数在集合的基数中的应用。7/1/20231Definition5-1函数的基本概念一.概念[定义]：X与Y集合，f是从X到Y的关系，如果任何x∈X，都存在唯一y∈Y，使得<x,y>∈f,则称f是从X到Y的函数，(变换、映射)，记作f:X→Y,或X→Y。

如果f

:XX是函数,也称f是X上的函数.X：定义域/domainoffx:y的原像/pre-imageY：陪域/codomainoffy:x的像/imagef（X）：值域（Rf、ranf)/rangeoff7/1/20232下面是大家熟悉的实数集合上的几个关系，哪些是R到R的函数？f={<x,y>|x,y∈R∧y=}g={<x,y>|x,y∈R∧x2+y2=4}h={<x,y>|x,y∈R∧y=x2}r={<x,y>|x,y∈R∧y=lgx}v={<x,y>|x,y∈R∧y=}Definition7/1/20233二.函数的表示方法

同关系的表示方法，也有枚举法、有向图、矩阵、谓词描述法。这里不再赘述。函数的矩阵的特点：每行必有且只有一个1。三.从X到Y函数的集合YX：

YX={f|f:XY}YX：它是由所有的从X到Y函数构成的集合Definition7/1/20234例X={1,2,3}Y={a,b}所有的从X到Y函数:f1X

Yf3。。。。。123abX

Yf2。。。。。123abf8X

Yf4。。。。。123abX

Yf5。。。。。123abX

Yf6。。。。。123abX

Yf7。。。。。123abX

Y。。。。。123abX

Y。。。。。123abYX={f1,f2,f3,f4,f5,f6,f7,f8}

如果X和Y是有限集合，|X|=m,|Y|=n,因为X中的每个元素对应的函数值都有n种选择，于是可构成nm个不同的函数，因此|YX|=|Y||X|=nm,7/1/20235四.特殊函数

1.常值函数：函数f:XY，如果y0∈Y,使得对x∈X,有f(x)=y0,即ranf={y0},称f是常值函数。如上例的f

1和f

8。2.恒等函数：恒等关系IX是X到X函数，即IX:XX,称之为恒等函数。显然对于x∈X，有IX(x)=x。五.两个函数相等设有两个函数f:ABg:CD,f=g

当且仅当A=C，B=D，且对任何x∈A，有f(x)=g(x)。

即它们的定义域相等、陪域相等、对应规律相同。7/1/20236六.函数的类型1234abc1234abc123dabc23bca1一对一一对一满射的映内的入射的单射的一对一的双射的一一对应的7/1/20237思考题如果f:XX是入射的函数，则必是满射的，所以f也是双射的。此命题成立吗？答案是：不一定。例如f:NN,f(n)=2n,f是入射的，但不是满射的函数。只有当X是有限集合时，上述命题才成立。本节重点掌握：函数的定义、函数的类型的判定和证明。作业P151(1),(3),(5),(6)7/1/202385-2函数的复合[定义]

f:XY,g:YZ是函数,则定义

g

f＝{<x,z>|xXzZy(yY<x,y>f<y,z>g)}则称g

f为f与g的复合函数(左复合)。

g

f:XZ,即g

f是X到Z的函数.这样写是为了照顾数学习惯:g

f(x)=g(f(x))7/1/20239复合减函数黄的计缘瑞算计算梯方法朵同复萌合关摊系的绸计算哀，但要婆注意吵是左饥复合孔。例f:费XY,勾g券:YZX=锣{1攻,2浪,3昼}邀Y链={季1,而2,舞3,茶4,少}牛Z书={扛1,厕2,栽3,券4,誓5,岩}f={解<1间,2柄>,梳<2缩慧,4旋>,寒<3亚,1扶>}g=度{吓<1绿,3谈>,腹<2桶,5接>,涛<3双,2命>,注<4由,1融>竞}gf={宾<1凳,3文>,很<2欢,5附>,咬<3蹲,2领>,秀<4雨,1色>}{<榴1,疗2>昌,<病2,动4>齿,<腾3,蛇1>瞎}={及<1就,5义>,版<2咳,1阻>,贿3,雁3>辣}用有晃向图竭复合:。3。2。13214。3。2。1。4。5。3。2。1。4。5。3。2。16/食26碎/2争02纪310例令f和g都是物实数园集合R上的士函数呀,如饿下:f=呈{<迷x,晌y>贺|x洁,y湾∈R胶∧y叼=3烈x+困1牧}g=枪{<镇x,颠y>竹|x稀,y望∈R差∧y横=国x2+战x}分别罢求gf、fg、ff、gggf(x句)=蝇g(无f(爪x)搞)=陷(3造x+歌1)2+(括3x狸+1稳)=圣9x2+9仇x+清2fg震(x帐)=猛f(哪g(霞x)炎)=竖3(坐x2+x持)+1棒=3腊x2+3南x+召1ff(x舌)=世f(岭f(洋x)柿)=再3(尤3x洲+1舌)+1判=9滚x+漫4gg(x渠)=饿g(抄g(芝x)惨)=某(x2+x意)2+(斑x2+x乏)=即x4+2危x3+2俊x2+x可见姜复合傍运算不满那足交生换性。6/删26它/2舌02期311函数检复合制的性萝质1.定理5-梁2.堂1满足查可结起合性f:XY,际g屿:YZ,h:ZW是函弊数,健则葱(hg)f=h(gf)2.定理5-拜2.俯2f:XY,岸g提:YZ是两答个函弹数,则⑴如果f和g是满射的克，则gf也是满射的占；⑵如果f和g是入射的莫，则gf也是入射的唱；⑶如果f和g是双射的珠，则gf也是双射的汁。6/卧26貌/2小02惹312定理2证明：⑴设f和g是满射虏的，连因gf:X汪Z谨,任取z∈骡Z,因g:筝YZ是满射驰的，手所以骑存在y∈立Y,使得z=醉g(宿y)街,又因f:宽XY是满射井的，且所以舞存在x∈尽X,使得y=什f(好x)肿,于是饼有z=热g(省y)铃=g桃(f即(x芹))杏=gf(x滥),所以gf是满射聋的。⑵设f和g是入射摆的，条因gf:X刃Z拿,任取x1,散x2∈X愉,粮x1≠x2因f:锣XY是入射枣的，f(两x1)≠鲜f(柳x2),而f(下x1)妇,f菊(x2)∈盾Y，因g:康YZ是入射病的，g(牛f(未x1))译≠g到(f花(x2))即gf接(x1)≠gf撇(x2)所以gf也是记入射谁的。⑶由⑴授⑵可钢得此疲结论让。6/瞎26害/2进02蒸3133.定理5-螺2.午3⑴如果gf是满射的蒜，则g是满射的炮；⑵如果gf是入射的份，则f是入射的堂；⑶如果gf是双射的妥，则f是入射的和g是满射的珍。此定被理的温证明是作堆业题P1撞56印(功3)。4.定理5-里2.芳4f:杏XY是函走数,则fIX=仇f且IYf=f。6/列26遥/2舌02龄314定理4证明：先证精明定义子域、飞陪域础相等大。因为IX:XX，f:毁X哑Y，∴通f恼IX:啄X拆Y,IYf采:疾X斜Y可见fIX、IYf与f具有终相同续的定触义域庄和陪矮域。再证它们相的对趴应规奋律相俊同：观任取x∈翠X，fIX(x纤)=沃f(IX(x压))骄=f悔(x呈)IYf泪(x爷)=IY(f婆(x堵))齿=f况(x主)所以fIX=数f且IYf=f。6/秃26馅/2驴02狸3155-占3逆函免数[定义]：设f:X既y是双赚射的牢函数袋，fC:Y携X也是肝函数,称之巴为f的逆刷函数心。并踏用f-1代替fC。f-1存在悲，也所称f可逆活。显然埋，f-1也是辈双射民的函俘数。R是A到B的关耗系，芒其逆帝关系RC是B到A的关少系。f:蔑X声yfC:Y锋X,是否沫是个训函数软？请仇看下狐面的雕例子却：。3。2。1。c。b。a。3。2。1。c。b。af:XYfC:YX6/护26买/2格02敲316性质1.定理5-片3.享1设f芝:X侨Y是双全射的维函数闹，则(f-1)-1=步f。2.定理5-珠3.时2设f消:X复Y是双趣射的损函数按，则壁有f-1f=壶IX且ff-1=中IY。证明：先证明定示义域稻、陪扇域相胸等。因为f:冤X府Y是双炎射的住，f-1:Y址X也是龟双射湿的，颈所以f-1f:XX持;优IX:XX可见f-1f与IX具有艳相同禁的定日义域什和陪征域。再证它们沾的对俱应规办律相拣同：x∈便X,因f:偷X要Y,梦屡y联Y,使得y=浩f(痰x)蔬,又f可逆堆，故f-1(y明)=粗x，于是f-1f(x战)=百f-1(f恰(x驱))链=f-1(y把)=啄x=IX(x题)同理推可证ff-1=迹IY。6/鞋26盈/2港02鸣3173.定理5-槽3.状3令f:证XY,灯g手:YX是两仪个函铁数,如果gf=粮IX且fg屑=化IY,则g=f-1。证明：⑴证f和g都可承逆。托因为gf=待IX，IX是双晋射的且，短由违关系某复合蛇性质3得，f是入射的和g是满射的仓。同败理由fg格=蜻IY，得g是入射的和f是满射的答。所陆以f和g都可碍逆。⑵显然f-1和g具有诊相同狼的定乏义域嚷和陪莫域。⑶证明您它们隐的对雨应规昨律相犁同。任取y逢Y，f-1(y够)=甘f-1IY(y燃)=f-1(fg)(y汉)=逝(f-1f)g(y延)=(IXg)(y袖)觉=g长(y宝)所以f-1=g6/垫26榨/2瞒02眠318顺便挣说明：f-1=g的两拌个条泄件必仰须同浮时满归足，挖缺一赌不可角。例如X

Y。。。。12ab。cf。。12Xg。。12X。。12XIX此例不只满盛足gf=IX,但f与g都非气双射自，不尤可逆拨。4.定理5-部3.衔4,令f:术XY,嘉g赏:YX是两谜个双射函数,则(gf)-1=f-1g-1此定慈理与茅关系老的复谊合求确逆(RS)C=SCRC类似山，作业P1沉56(1兰)正,组(3房诚)c费)，(5凡)6/健26窗/2煌02梳319*5-招4集合彩的特秤征函扒数与渠模糊俯子集一.集合踪蝶的特纠征函恼数[定义]:令E是全集,A是E的子集,定义函数ψA:E{0,1}对任何x∈E,有1x∈AψA(x)=

0xA称是ψA:E{0,1}子集A的特征函数.6/造26劲/2帽02强320下面桂以E=冻{a杏,b甘,c渡}为例猛,称看E的各肢个子慨集的雨特征筐函数拥。cab01abc01abc01abc01abc01abc01abc01abc016/纱26歼/2潜02签3212.性质令A,块B是全季集E的子梳集,1)A=与Φ糠x(ψA(x适)=狡0)2)A=垂E葱x(ψA(x纸)=谁1)3)AB姿狭x(ψA(x坑)典≤ψB(x羡))证明:任取x∈版E,从下巧表看咱出AB田慌x(ψA(x充)灿≤ψB(x萄))xAxBxAxBψA(x)ψB(x))

ψA(x)≤ψB(x))

FFT00TFTT01TTFF10FTTT11T6/状26迈/2务02叮3224)A=B顿x屈(ψA(x淘)=伙ψB(x扁))5)AB据话x(ψA(x虽)捞≤ψB(x仪))促x(ψB(x作)=贼1ψA(x栋)=刻0)6)ψA∩昏B(x赚)熄=ψA(x奥)ψB(x己)xAxBxA∩BψA∩B(x)ψA(x)ψB(x))

FFF00×0=0

FTF00×1=0TFF01×0=0TTT11×1=16/接26祖/2其02叔3237)Ψ~A(x训)=扰1-贫ψA(x捉))x∈Ax∈~AψA(x)Ψ~A(x)1-ψA(x))TF101-1=0FT011-0=18)拥.ψA∪夸B(x燃)事=ψA(x湿)+煤ψB(x度)-擦ψA∩磁B(x贿)x∈Ax∈BψA∩B(x)xA∪BψA∪B(x)ψA(x)+ψB(x))-ψA∩B(x)

FF0F00＋0－0＝0FT0T10＋1－0＝1TF0T11＋0－0＝1TT1T11＋1－1＝16/仓26棍/2赚02拖3249)ψA-罩B(x抹)豆=ψA(x演)-竹ψA∩槐B(x芒)证明:任取x∈贸EψA-凡B(x思)谦=ψA∩恭~B(x盼)孙=ψA(x河)ψ~B(x伯)=卵ψA(x惯)(雅1-决ψB(x垂))握=ψA(x柿)-稼ψA(x挠)ψB(x倚)=屈ψA(x军)赔-ψA∩源B(x靠)应用怒上述还公式较可以奶得到血一些笋集合骆公式桃。例蒜如证拘明吸亮收律新：A∪券(A重∩B恭)吼=A证明:任取x∈薯A,ψA∪误(A采∩B版)(x档)桃=ψA(x萌)+简ψA∩灰B(x熔)-沉ψA∩未(A念∩B称)(x炉)=ψA(x邻)+浪ψA∩些B(x桂)-煎ψA∩择B(x筒)=门ψA(x释)6/那26序/2那02陵325二.模糊套子集[定义]注意:6/勺26忧/2脾02度326定义铸说明6/交26衫/2走02愧327例子.令E={,,,,}

表示E中“圆形”的模糊子集。表示E中“方形”的模糊子集。它们的隶属函数如下:abcdea1a0.4b0.8b0.3c0.3c1d0.2d0.2e0e06/迈26北/2垃02队328模糊拉子集睬的表煌示方窝法1)效序偶个的集拾合表球示2)用Za朱de养n记号传表示3)用有岂序n元组笨表示6/耳26喊/2讽02也3294)用函临数表雅达式包或曲罩线表坏示例如,以年龄为论域,E={0,1,2,3,…200},Zaden给出了“年老---”“年青---”两个模糊子集的隶属函数表示为:502516/橡26条/2底02详330模糊缴集合体的运厉算6/故26寸/2卧02堡3315-薪6集合剖的基味数一.自然挡数1.集合A的后带继集吹合A+A是个竖集合林，A的后辈继集台合A+为：A+=A∪{尺A}例如:A:悦A+:Φ=喊0兔0+=拥Φ∪您{Φ弊}=匪{Φ杰}=圾1=松{0尝}{Φ肆}=慰1夜1+={择Φ}逝∪{渴{Φ刑}}连=猛{Φ煌,{访Φ}肺}=慎2=市{0禽,1乳}{Φ匹,{举Φ}莫}=且2老2+=音{Φ判,{机Φ}绍}∪止{{狸Φ,震{Φ土}}郊}=绿{Φ留,{帜Φ}烦,{芦Φ,牢{Φ房诚}}门}=渔3=治{0吃,1凶,2看}….季..冈…菠..胁.6/铜26喝/2宪02删3322.自然非数集抢合N的定短义(Pe告an盒o公理)1)蛛.灭0∈N这里0=Φ2)顺.骗n∈N筋,则n+∈N禾,这里n+=n∪{n纳}3)您.不存去在n∈N瓶,使得n+=00是最天小的益自然乏数4)缩慧.若n+=m+,则n=皱m后继惯数的输唯一静性5)肺.如果SN，且⑴墓0∈S；⑵冈n∈S笔,则n+∈S则S=冶N。从此奴定义讯得n=亿{0漏,1暑,2银,3畜,…扔,n冠-1舰},所以殊有：0∈1霸∈2闲∈3井∈…占..坝.01闸2堡洁3投……自然竹数的搏这个烫定义讽，解闪释了提许多垃数学馅问题慌，是立一个塌很准确的洁抽象兔。因赢为0,攀1,将2,裂3,耍..本身宴就是夹个抽醉象的掀概念潮。6/汇26并/2俭02欢333二.集合伙的等瘦势比较深两个额集合克的“大小”有两呼种方葬法：数集马合中陪元素民的个呜数。惜这只殊使用粗于有柴限集徐合。看两迟个集挑合的虾元素甚间是积否有购一一她对应肌的关紧系(康双射榜)。这种练方法食既适刷用于赴有限先集合吃，也史适用脸无限挽集合锋。［定小义］：A是B集合阵，如类果存眨在双射f:卫A县B，则称A与B等势。记吸作A~爬B。例如攀下面廊集合巴间是瓜等势块的。N=桂{0不,1趟,2储,3五,4览,…衣..奖.}A=煤{0青,2船,4贱,6芝,8锦,…同..牙.}切f趴:N扒A，f(存x)暮=2芝xB=址{1乳,3秃,5役,7肯,9丧,…锄..籍.}喇g俭:N跨B，g(野x)著=2齿x+馋16/最26甚/2旷02号334集合婶间的纪等势谋关系“~”是个睛等价互关系令S是个必集合填族(脉即“所有尿集合蒸构成仇的集范合”)，沙在S上的疾等势熟关系耳~，揉满足划：⑴自反冒性：因笑为任窃何集汗合A有双颤射IA:A色A它,∴歉A~统A⑵对称蓝性：任哈何集大合A,唤B，若A~凉B，有双贼射f:A挤B波,又有双双射f-1:B江A，所以B~西A。⑶传递乘性：任怜何集矩合A,敬B,交C，若A~帽B，且B~凭C，则有街双射f:A税B壮,和双蹄射g:B尸C挖,由函抖数的练复合林得双破射：g○f:柜A产C，所以A~徐C。所以本~是拉等价劣关系珍。按照亚等势色关系“~”对集房诚合族S，进行财划分咽，得银到商箱集S/遵~，进而盯得到目基数便类的戏概念聋。6/茫26惭/2遗02娘335三.基数挠类和炉基数1.基数辅类［定恨义］S是集据合族漆，“~”是S上的括等势页关系片，相对犹~的怎等价制类称珠之为什基数岗类。S=洋{0,Φ，1,播{1波},户{a冲},揭…，2,刃{0洲,1腿},曲{a肚,b奏},刷…，3,迹{0碧,1群,2松},劝…，N,折I,排…，R,王…}S/改~=慈{[沃0]惨,[阳1]渴,[趋2]乖,[惜3]之,…仍,[浸N]贩,[灯R]锦,.烟..刘}任何喷集合A，必属书于且贴仅属倚于一剧个等挎价类疑。如{a,拿b,计0,坊1}日[文4]膨,因为{a,勇b,稀0,此1}与4息(即静集合腹{0示,1言,2天,3昌})夏等势垦。偶数用集合E=辞{0眨,2枝,4趋,6润,8投,.呈..渴}球[N舍],因为E~罪N。6/堤26等/2逢02之3362.基数[定棚义]给定佳集合A，A所属延于的产基数镜类，腹称之供为A的基趟数，侍记作K[编A]。如A=情{1厨,2激},肝A蚁[障2]增,磁K[割A]长=[厌2]往,简记补成K[往A]老=2如B=引{a祝,b干,c房诚},西B到[推3]访,欲K[剖B]你=[丢3]滋,简记享成K[乒B]袖=3采用卡这种绘简单侦记法悲，使冒得对欧于有训限集撞合A，K[躬A]勤=|赌A|。6/饮26约/2煌02档337四.有限墨集合壳与无盖限集忠合［定猜义］凡是筋和某质个自与然数n等势谁的集何合，乓都称肤之为暮有限络集合般；否挡则是涛无限逢集合做。如A=惊{a统,b庙,c胆,d议,e艰},津A与5(劈燕{0补,1汉,2诊,3意,4纹})等势蜂，故A是有粘限集龄。五.可数评集合料及其秧基数自然身数集吗合N的基撕数因为N不可区能与芝某个绸自然城数n等势抢。所重以N的基善数不叔能是刺有限纯数，标就用古一个“无限抛大”的数0(读:阿列介夫零)表示,即K[秒N]奸=公0。6/骄26催/2外02伯338可数轿集:与自污然数度集合N等势皇的集会合，祥称之而为可扰数集部。A=匙{0剩,2仿,4耐,6篇,8忌,…够..口.}拢f偶:N突A招f芳(n猫)=家2nB=蚊{1崖,3促,5爆,7义,9聪,…骨..验.}赢g折:N读B突g帮(n幕)=完2n直+1C=公{1缝00,1奸0,娘102,1摄03,1伴04,,红….依..则}白h:早N白C符h(芦n)驱=1擦0n都是虏可数战集合。至多宵可数慕集：有爆限集唤合和符可数芒集统称至多嗽可数榆集。6/帅26角/2由02石339整数滴集合I~句N因为I可以差写成卸：I=疮{0协,-除1,碌1,消-2擦,2怖,-沿3,阵3,奋-4畅,4毅,.犯..乖}即可征将I中元温素从0开始饱按照狗箭头喇指定杯次序企排列：0123-1-2-3所以I是可透数集瞧。可数拍集的桌判定定理5-逢6.致1集合A是可数索集，盖充分惭且必榨要条渠件是可油将A的元符素写富成序珠列形扇式，笔即A=躁{阀a0,a1,a2,a3,.虾..健}6/红26盒/2蝴02路340有理园数集疫合Q~兄N。因为勿每个辈有理套数都构可以扁写成恒一个诱分数咱形式凝如下旗：0/11/12/13/1-1/1-2/1-3/1-1/2-2/2-3/20/21/22/23/20/31/32/33/3-1/3-2/3-3/3-1/4-2/4-3/40/41/42/43/4.............................................可以纳从0/艇1开始丽按照绸箭头挡指定污次序适排列Q中元剥素(如果马某个交在前州面出水现，疏就跳土过去)，所骨以Q是可晌数集济。另外I×江I~样N以及N×晚N~凡N如右故图所吧示。同理怕可证N×染N~洁N011223-1-1-2-2-36/弟26腾/2按02虎341六.不可引数集码合及付其基渡数1.实数属轴上莫的(0硬,1诞)区间歌中的贺实数布是不怜可数逢的。证明：假轰设(0闷,1给)是可击数的迈，则附可以费将它脚的元停素写警成如倒下序列平形式砍：{x1,x2,x3,.刷..坊}嫁,其中xi=0榆.ai1ai2ai3……总i菌=1悼,2未,3无,…葱..即蜡0＜xi＜1aik∈{倦0,狮1,竟2,匹3,批4,暗5,总6,暗7,裹8,盯9}开k=舱1,邀2,次3,臭4,叛…令x1=0菊.a11a12a13a14….紧..x2=0宏.a21a22a23a24….金..……贵….绢..xn=0范.an1an2an3an4….窃....沈……卫..构造长一个嫌数b=隶0.预b1b2b3b4…bn……，其中b1≠a11b2≠a22b3≠a33…bn≠ann..傍.于是b≠x1,絮b≠x2,演b≠x3..辱.b≠xn…∴b(鞭0,照1)产生就矛盾藏，所弱以(0冈,1采)是不腔可数革的。6/盒26肆/2拌02比3422.连续络统基宾数⑴(0漂,1臣)区猴间的注基数饿是一驴个比N的基劲数0更大盘的无宽限大岸的数,用(阿列独夫)表示,即>0。⑵整个痕实数醉集合R~雨(0晶,1漠)证明：构青造函半数f:(0斯,1老)Rf(坑x)社=t艇g(圾πx竟-π夕/2野)显然f是双膏射，默所以R~衬(0阀,1份)。⑶实数叔轴上单的任写何一袖段连织续区伞间(a轮,b腊)的基锦数都捉是，御所以光称之抛为连续汽统基胃数。016/迫26补/2监02运3433.计算询公式⑴K[塑A1]=呀K[萄A2]=型..姐.宇=K咐[An]=,则K[A1∪A2∪.网..惭∪An]=⑵K[涂A]执=K乐[B红]=,则K[A×基B]=⑶K[序A]罢=K[殊B]普=0,然(或K[宣B]据=n吊),喜(B是多可新数集)则K[A－B]=6/映26俗/2辣02盗344七.基数杯的比朴较前边迅讲了劫基数堤相等垒与否充的问蓄题,下面揭讨论盘诸如和遍0的大承小问哪题,即所乏谓无订限集遥合的事“次屯序”愿问题静。在比少较两向个集董合基闭数相订等时,要看孕这两阔个集将合之伟间是粘否存茎在双虾射,但是映找双兵射往腊