离散数学二元关系和函数

关于离散数学二元关系和函数第1页，共36页，2022年，5月20日，14点52分，星期五在高等数学中，函数是在实数集合上进行讨论的，其定义域是连续的。本章把函数概念予以推广⑴定义域为一般的集合，支持离散应用。⑵把函数看作是一种特殊的关系：单值二元关系。4.6函数的定义与性质第2页，共36页，2022年，5月20日，14点52分，星期五函数定义定义

设F为二元关系,若x∈domF都存在唯一的y∈ranF使xFy成立,则称F为函数.对于函数F,如果有xFy,则记作y=F(x),并称y为F在x的函数值.例1F1={<x1,y1>,<x2,y2>,<x3,y2>}

F2={<x1,y1>,<x1,y2>}

F1是函数,F2不是函数4.6函数的定义与性质第3页，共36页，2022年，5月20日，14点52分，星期五函数与关系的区别从A到B的函数f与一般从A到B的二元关系R有如下区别：A的每一元素都必须是f的序偶的第一坐标，即dom(f)=A；但dom(R)R若f(x)=y，则函数f在x处的值是惟一的，即(f(x)=y)(f(x)=z)(y=z)，；但(xRy)(xRz)得不到y=z4.6函数的定义与性质第4页，共36页，2022年，5月20日，14点52分，星期五例1

设A={1,2,3,4,5}，B={6,7,8,9,10}，分别确定下列各式中的f是否为由A到B的函数。(1)f={(1,8),(3,9),(4,10),(2,6),(5,9)}(2)f={(1,9),(3,10),(2,6),(4,9)}(3)f={(1,7),(2,6),(4,5),(1,9),(5,10),(3,9)}解

（1）能构成函数，因为符合函数的定义条件。（2）不能构成函数，因为A中的元素5没有像，不满足像的存在性。（3）不能构成函数，因为A中的元素1有两个像7和9，不满足像的惟一性。

4.6函数的定义与性质第5页，共36页，2022年，5月20日，14点52分，星期五函数相等定义设F,G为函数,则

F=GFG∧GF

一般使用下面两个条件：

(1)domF=domG

(2)x∈domF=domG都有F(x)=G(x)

实例函数

F(x)=(x21)/(x+1),G(x)=x1不相等,因为domFdomG.

4.6函数的定义与性质第6页，共36页，2022年，5月20日，14点52分，星期五从A到B的函数定义

设A,B为集合,如果

f为函数

domf=A

ranfB,则称f为从A到B的函数,记作f：A→B.实例

f：N→N,f(x)=2x是从N到N的函数

g：N→N,g(x)=2也是从N到N的函数

4.6函数的定义与性质第7页，共36页，2022年，5月20日，14点52分，星期五B上A定义所有从A到B的函数的集合记作BA,读作“B上A”，符号化表示为

BA={f|f：A→B}

计数：

|A|=m,|B|=n,且m,n>0,|BA|=nm.A=,则BA=B={}.

A≠且B=,则BA=A=.

4.6函数的定义与性质第8页，共36页，2022年，5月20日，14点52分，星期五实例例2设A={1,2,3},B={a,b},求BA.

解BA={f0,f1,…,f7},其中

f0={<1,a>,<2,a>,<3,a>},f1={<1,a>,<2,a>,<3,b>}

f2={<1,a>,<2,b>,<3,a>}，f3={<1,a>,<2,b>,<3,b>}

f4={<1,b>,<2,a>,<3,a>}，f5={<1,b>,<2,a>,<3,b>}

f6={<1,b>,<2,b>,<3,a>},f7={<1,b>,<2,b>,<3,b>}

4.6函数的定义与性质第9页，共36页，2022年，5月20日，14点52分，星期五函数的像定义设函数f：A→B,A1A.

A1在f下的像：f(A1)={f(x)|x∈A1}

函数的像

f(A)=ranf

注意：函数值f(x)∈B,而像f(A1)B.例3

设f：N→N,

且

令A={0,1},B={2},那么有

f(A)=f({0,1})={f(0),f(1)}={0,2}4.6函数的定义与性质第10页，共36页，2022年，5月20日，14点52分，星期五函数的性质定义设f：A→B,

（1）若ranf=B,则称f：A→B是满射的.

（2）若任意x1，

x2

A

而且不相等，都有f(x1)与

f(x2)不相等,则称f：A→B是单射的.

（3）若f：A→B既是满射又是单射的,则称f：

A→B是双射的f

满射意味着：yB,都存在x使得

f(x)=y.f单射意味着：f(x1)=f(x2)x1=x2

4.6函数的定义与性质第11页，共36页，2022年，5月20日，14点52分，星期五注意：①由单射的定义可知，设X和Y是有限集合，若存在单射函数f:X→Y，则|X|≤|Y|。②由满射的定义可知，设X和Y是有限集合，若存在满射函数f:X→Y，则|X|≥|Y|。③由双射的定义可知，设X和Y是有限集合，若存在双射函数f:X→Y，则|X|=|Y|。4.6函数的定义与性质第12页，共36页，2022年，5月20日，14点52分，星期五实例例4判断下面函数是否为单射,满射,双射的,为什么?

(1)f：R→R,f(x)=x2+2x1

(2)f：Z+→R,f(x)=lnx,Z+为正整数集

(3)f：R→Z,f(x)=x

(4)f：R→R,f(x)=2x+1

(5)f：R+→R+,f(x)=(x2+1)/x,其中R+为正实数集.

4.6函数的定义与性质第13页，共36页，2022年，5月20日，14点52分，星期五解(1)f：R→R,f(x)=x2+2x1

在x=1取得极大值0.既不单射也不满射.

(2)f：Z+→R,f(x)=lnx

单调上升,是单射.但不满射,ranf={ln1,ln2,…}.(3)f：R→Z,f(x)=x

满射,但不单射,例如f(1.5)=f(1.2)=1.

(4)f：R→R,f(x)=2x+1

满射、单射、双射,因为它是单调的并且ranf=R.

(5)f：R+→R+,f(x)=(x2+1)/x

有极小值f(1)=2.该函数既不单射也不满射.

实例（续）4.6函数的定义与性质第14页，共36页，2022年，5月20日，14点52分，星期五构造从A到B的双射函数有穷集之间的构造例5A=P({1,2,3}),B={0,1}{1,2,3}解

A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={f0,f1,…,f7},其中

f0={<1,0>,<2,0>,<3,0>},f1={<1,0>,<2,0>,<3,1>},

f2={<1,0>,<2,1>,<3,0>},f3={<1,0>,<2,1>,<3,1>},

f4={<1,1>,<2,0>,<3,0>},f5={<1,1>,<2,0>,<3,1>},

f6={<1,1>,<2,1>,<3,0>},f7={<1,1>,<2,1>,<3,1>}.令f：A→B,f()=f0,f({1})=f1,f({2})=f2,f({3})=f3,f({1,2})=f4,f({1,3})=f5,f({2,3})=f6,f({1,2,3})=f74.6函数的定义与性质第15页，共36页，2022年，5月20日，14点52分，星期五实数区间之间构造双射构造方法：直线方程例6A=[0,1]

B=[1/4,1/2]

构造双射f:A→B构造从A到B的双射函数（续）解令f：[0,1]→[1/4,1/2]f(x)=(x+1)/4

4.6函数的定义与性质第16页，共36页，2022年，5月20日，14点52分，星期五构造从A到B的双射函数（续）A与自然数集合之间构造双射方法：将A中元素排成有序图形，然后从第一个元素开始按照次序与自然数对应例7A=Z,B=N，构造双射f：A→B将Z中元素以下列顺序排列并与N中元素对应：

Z：0112233…

↓↓↓↓↓↓↓

N：0123456…

则这种对应所表示的函数是：

4.6函数的定义与性质第17页，共36页，2022年，5月20日，14点52分，星期五常函数、恒等函数、单调函数

1.

设f：A→B,若存在c∈B使得x∈A都有

f(x)=c,则称f：A→B是常函数.2.称A上的恒等关系IA为A上的恒等函数,对所有的x∈A都有IA(x)=x.3.设f：R→R，如果对任意的x1,x2∈R，x1<x2,就有f(x1)

f(x2),则称f为单调递增的；如果对任意的x1,x2∈A,x1<x2,就有f(x1)<f(x2),则称f为严格单调递增的.

类似可以定义单调递减和严格单调递减的函数.4.6函数的定义与性质第18页，共36页，2022年，5月20日，14点52分，星期五集合的特征函数设A为集合,A’A,A’的特征函数

A’：A→{0,1}定义为实例集合：X={A,B,C,D,E,F,G,H},

子集：T={A,C,F,G,H}

T的特征函数T：

x

ABCDEFGHT(x)

10100111

4.6函数的定义与性质第19页，共36页，2022年，5月20日，14点52分，星期五5.设R是A上的等价关系,令

g：A→A/R

g(a)=[a],a∈A

称g是从A到商集A/R的自然映射.自然映射4.6函数的定义与性质第20页，共36页，2022年，5月20日，14点52分，星期五实例例8(1)A的每一个子集A’都对应于一个特征函数,不同的子集对应于不同的特征函数.例如A={a,b,c},则有

={<a,0>,<b,0>,<c,0>}，

{a,b}={<a,1>,<b,1>,<c,0>}(2)给定集合A，A上不同的等价关系确定不同的自然映射,其中恒等关系确定的自然映射是双射,其他的自然映射一般来说是满射.例如

A={1,2,3},R={<1,2>,<2,1>}∪IAg(1)=g(2)={1,2},g(3)={3}4.6函数的定义与性质第21页，共36页，2022年，5月20日，14点52分，星期五函数复合的定理定理设F,G是函数,则FG也是函数,且满足

(1)dom(FG)={x|x∈domG

G(x)∈domF}

(2)x∈dom(FG)有FG(x)=F(G(x))

推论1

设F,G,H为函数,则(F∘G)∘H和F∘(G∘H)

都是函数,且(F∘G)∘H=F∘(G∘H)推论2

设f：B→C,g：A→B,则f∘g：A→C,且

x∈A都有f∘g(x)=f(g(x)).

4.7函数复合和反函数第22页，共36页，2022年，5月20日，14点52分，星期五函数复合运算的性质定理设g：A→B,f

：B→C.

(1)如果f,g都是满射,则fg：A→C也是满射.

(2)如果g,

f都是单射,则fg:A→C也是单射.

(3)如果g,f都是双射,则f∘g：A→C也是双射.

证(1)c∈C,由f：B→C的满射性,b∈B使得

f(b)=c.对这个b,由g：A→B的满射性，a∈A

使得f(a)=b.由合成定理f∘g(a)=f(g(a))=f(b)=c

从而证明了f∘g：A→C是满射的.第23页，共36页，2022年，5月20日，14点52分，星期五函数复合运算的性质

(2)假设存在x1,x2∈A使得fg(x1)=fg(x2)

由合成定理有f(g(x1))=f(g(x2)).

因为f：B→C是单射的,故g(x1)=g(x2).又由于g：A→B也是单射的,所以x1=x2.从而证明f∘g：A→C是单射的.(3)由(1)和(2)得证.

定理设f:AB，则

f=f∘IB

=IA∘f

第24页，共36页，2022年，5月20日，14点52分，星期五定理

设f:X→Y，g:Y→Z，那么（1）若gf是单射，则f是单射。（2）若gf是满射，则g是满射。（3）若gf是双射，则f是单射，g是满射。函数复合运算的性质第25页，共36页，2022年，5月20日，14点52分，星期五反函数存在的条件任给函数F,它的逆F1不一定是函数,是二元关系.实例：F={<a,b>,<c,b>}，F1={<b,a>,<b,c>}任给单射函数f：A→B,则f1是函数,且是从ranf到A的双射函数,但不一定是从B到A的双射函数.实例：f:N→N,f(x)=2x,

f1:ranf→N,f1

(x)=x/2第26页，共36页，2022年，5月20日，14点52分，星期五反函数定理设f：A→B是双射的,则f1：B→A也是双射函数.

证因为f是函数,所以f1是关系,且domf1=ranf=B,ranf1=domf=A,

对于任意的y∈B=domf1,假设有x1,x2∈A使得

<y,x1>∈f1∧<y,x2>∈f1成立,则由逆的定义有

<x1,y>∈f∧<x2,y>∈f根据f的单射性可得x1=x2,从而证明了f1是函数，且是满射的.下面证明f1

的单射性.若存在y1,y2∈B使得f1(y1)=f1(y2)=x,从而有

<y1,x>∈f1∧<y2,x>∈f1

<x,y1>∈f∧<x,y2>∈f

y1=y2第27页，共36页，2022年，5月20日，14点52分，星期五反函数的定义及性质对于双射函数f：A→B,称f1：B→A是它的反函数.反函数的性质定理设f：A→B是双射的,则

f1f=IA,ff1=IB

对于双射函数f：A→A,有

f1f=ff1=IA

第28页，共36页，2022年，5月20日，14点52分，星期五定理

若f:X→Y是可逆的，那么（l）(f-1)-1=f（2）f-1f=IX，ff-1=IY定理3.9

设X,Y,Z是集合，如果f:X→Y，g:Y→Z都是可逆的，那么gf也是可逆的，且(gf)-1=f-1g-1。第29页，共36页，2022年，5月20日，14点52分，星期五函数复合与反函数的计算例设f：R→R,g：R→R

求f

g,g

f.如果f和g存在反函数,求出它们的反函数.

解

f：R→R不是双射的,不存在反函数.g：R→R是双射的,它的反函数是g1：R→R,g1(x)=x2第30页，共36页，2022年，5月20日，14点52分，星期五一、两个有限集如何比较多少。设两个班级A和B，要比较这两个班级的学生哪班多，哪班少，可采取两种方法。方法1：报数。报数后看谁的数目大，数目大的就表示这个班上学生人数多。但这个方法对无限集却行不通。方法2：配对。将A中的一个学生a1和B中的一个学生b1配成一对，配好以后，不许他们再和别人配对了。然后再把A中的另一个学生a2和B中的一个学生b2配成一对，同样，配好以后也不准他们再和其他人配对了。这样一对一配下去，如果A中的人都配完了，而B还剩下一些人，则说B中的学生比A多；如果B中的人都配完了，而A剩下一些人，则说A中的学生比B多；如果A和B中的学生正好