二元关系和函数

二元关系和函数第1页，共80页，2023年，2月20日，星期三2第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数第2页，共80页，2023年，2月20日，星期三34.1集合的笛卡儿积和二元关系

有序对笛卡儿积及其性质二元关系的定义二元关系的表示第3页，共80页，2023年，2月20日，星期三4

有序对的性质：1）有序性<x,y><y,x>（当xy时）

2）<x,y>与<u,v>相等的充分必要条件是

<x,y>=<u,v>x=uy=v例4.1<2,x+5>=<3y4,y>，求x,y.解3y4=2,x+5=y

y=2,x=3

§4.1二元关系的概念1.有序对/序偶：由两个元素x和y按一定顺序排成二元组，记作：<x，y>。其中x称作第一个元素；y称作第二个元素。第4页，共80页，2023年，2月20日，星期三5

实例：1.空间直角坐标系中的坐标

<3，5，－6>是有序三元组2.图书馆记录<书类别，书号，书名，作者，出版社，年份>是一个有序六元组.2.有序n元组：一个有序n(n3)元组<x1,x2,…,xn>是一个有序对，其中第一个元素是一个有序n-1元组，即

<<x1,x2,…,xn-1>,xn>=

<x1,x2,…,xn>。我们将来的研究重点为有序二元组，即有序对/序偶第5页，共80页，2023年，2月20日，星期三6例4.2A={1,2,3},B={a,b,c},C=

AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

BA={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}AA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}AC=CA=3.笛卡儿积：设A,B为集合，用A中元素为第一个元素，B中元素为第二个元素，构成有序对.所有这样的有序对组成的集合叫做

A与B的笛卡儿积记作AB,即AB={<x,y>|xAyB}。第6页，共80页，2023年，2月20日，星期三7笛卡儿积的性质：1.不适合交换律ABBA(AB,A,B)2.若A或B中有一个为空集，则AB就是空集.

A=B=

3.若|A|=m,|B|=n,则|AB|=mn

4.不适合结合律(AB)CA(BC)(A,B,C)例：A={1},B={2},C={3}AB={<1,2>},(AB)C={<<1,2>,3>}={<1,2,3>}BC={<2,3>},A(BC)={<1,<2,3>>}{<1,2,3>}第7页，共80页，2023年，2月20日，星期三8二元关系：集合中两个元素之间的某种关系例3甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。比赛结果可表示为：{<乙,甲>，<甲,丙>，<乙,丙>}，其中<x,y>表示x胜y，它表示了集合{甲,乙,丙}中元素之间的一种胜负关系.例4有A、B、C3个人和四项工作G1、G2、G3、G4，已知A可以从事工作G1和G4，B可以从事工作G3，C可以从事工作G1和G2.

那么，人和工作之间的对应关系可以记作

R＝

{<A,G1>,<A,G4>,<B,G3>,<C,G1>,<C,G2}它表示了工人集合{A,B,C}到工作集合{G1,G2,G3,G4}之间的关系第8页，共80页，2023年，2月20日，星期三如<x,y>∈R,可记作xRy；如果<x,y>R,则记作xRy实例：R1={<1,2>,<a,b>},R2=

,R3={<1,2>,3,4}，R4={<x,y>|x∈N∧y∈Z}R1,R2,R4是二元关系；R3不是二元关系。4.

二元关系：如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对(以有序对为元素的集合)（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.第9页，共80页，2023年，2月20日，星期三105.从A到B的关系与A上的关系设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做

A上的二元关系.例5A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=,R4={<0,1>}.那么R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.

计数：|A|=n,|B|=m,|A×B|=n×m,A×B的子集有个.所以A到B上有个不同的二元关系.|A|=n,|A×A|=

,A×A的子集有个.所以A上有个不同的二元关系.例如|A|=3,则A上有512个不同的二元关系.

第10页，共80页，2023年，2月20日，星期三11A上重要关系的实例设A为任意集合，是A上的关系，称为空关系EA,IA分别称为全域关系与恒等关系，定义如下：EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}

例如,A={1,2},则

EA={<1,1>,<1,2>,<2,1>,<2,2>}

IA={<1,1>,<2,2>}

注：{<1,1>}≠IA;{<2,2>}≠IA第11页，共80页，2023年，2月20日，星期三12A上重要关系的实例（续）小于等于关系LA,整除关系DA,包含关系R定义：

LA={<x,y>|x,y∈A∧x≤y},

DA={<x,y>|x,y∈A∧x整除y},R={<x,y>|x,y∈P(A)∧xy},A是某集合.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.第12页，共80页，2023年，2月20日，星期三13实例例如A={1,2,3},B={a,b},则

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

P(B)={,{a},{b},{a,b}},则B上的包含关系是R={<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}

第13页，共80页，2023年，2月20日，星期三14关系的表示表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是从A到B的关系，以A元素为行，B元素为列，MR=[rij]mn,其中rij

=1<xi,yj>R，否则rij

=0。关系图：若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=<A,R>,以A中元素为结点，如果<xi,xj>

R，则从xi

到xj有一条有向边.注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图仅适于表示A上的关系

第14页，共80页，2023年，2月20日，星期三15实例A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系矩阵MR和关系图GR如下：习题：4.1第15页，共80页，2023年，2月20日，星期三练习1.令A={1,2,3};B={a,b},求R1={<1,a>,<1,b>,<2,b>,<3,a>}的关系矩阵。2.令A={1,2,3};求R2={<1,1>,<1,3>,<2,1>,<3,2>}的关系图。3.令F={<1,2>,<2,3>,<3,1>,<1,3>}，G={<2,1>,<2,2>,<2,3>,<1,4>}求F∘G,G∘F,F∘F。（方法自选）第16页，共80页，2023年，2月20日，星期三17基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质4.2关系的运算第17页，共80页，2023年，2月20日，星期三§4.2关系的运算关系R的定义域：

domR={x|(y)<x,y>R}(即R中有序组的第一个元素构成的集合)关系R的值域：

ranR={y|(x)<x,y>R}(即R中有序组的第二个元素构成的集合)一、关系的定义域与值域关系R的域：

fldR=domR

ranR

第18页，共80页，2023年，2月20日，星期三19关系的基本运算定义例1R={<1,2>,<1,3>,<2,4>,<4,3>},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}第19页，共80页，2023年，2月20日，星期三20关系的基本运算定义（续）

R1={<y,x>|<x,y>R}

R∘S=|<x,y>|

z(<x,z>S<z,y>R)}例2R={<1,2>,<2,3>,<1,4>,<2,2>}

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}

R1={<2,1>,<3,2>,<4,1>,<2,2>}

R∘S={<1,2>,<1,4>,<3,2>,<3,3>}S∘R={<1,3>,<2,2>,<2,3>}二.逆与合成第20页，共80页，2023年，2月20日，星期三21合成运算的图示方法

利用图示（不是关系图）方法求合成R={<1,2>,<2,3>,<1,4>,<2,2>}

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}

R∘S={<1,2>,<1,4>,<3,2>,<3,3>}

S∘R={<1,3>,<2,2>,<2,3>}RSSRS○R≠R○S第21页，共80页，2023年，2月20日，星期三22实例R={<1,2>,<3,2>,<1,4>,<2,2>}

R↾{1}={<1,2>,<1,4>}

R[{1}]={2,4}R↾{1,2}={<1,2>,<1,4>,<2,2>}

R↾=

R[{1,2}]={2,4}

三限制和像：已知二元关系F和集合A

F在A上的限制

F↾A={<x,y>|xFy

xA}

A在F下的像

F[A]=ran(F↾A)

注意：F↾AF,F[A]ranF第22页，共80页，2023年，2月20日，星期三23四.关系运算的基本性质(1)

(2)

(3)不满足交换律：

F○G≠G○F(4)满足结合律：

F○G○

H=F○

(G○H)(5)第23页，共80页，2023年，2月20日，星期三第24页，共80页，2023年，2月20日，星期三25五.A上关系的幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：

(1)R0={<x,x>|x∈A}=IA

(2)Rn+1=Rn○R

注意：对于A上的任何关系R1和R2都有

R10=R20=IA

对于A上的任何关系R都有

R1=R第25页，共80页，2023年，2月20日，星期三26(1)定义法：对于集合表示的关系R，计算Rn就是n个R左复合.(2)矩阵乘法：矩阵表示就是n个矩阵相乘,其中相加采用逻辑加.（线性代数，逻辑乘法）(3)关系图法：若点a经k(k=1,2,…,n)条线可到达点b，则在的关系图上，a到b有线相连。例3设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次幂,分别用矩阵和关系图表示.

解R与R2的关系矩阵分别为六.幂的求法：第26页，共80页，2023年，2月20日，星期三27同理，R0=IA,R3和R4的矩阵分别是：因此M4=M2,即R4=R2.因此可以得到

R2=R4=R6=…,R3=R5=R7=…第27页，共80页，2023年，2月20日，星期三28R0,R1,R2,R3,…的关系图如下图所示关系图法结论：仅当A有回路时，上述结论成立。第28页，共80页，2023年，2月20日，星期三当图中没有回路时：第29页，共80页，2023年，2月20日，星期三30七.幂的性质：当关系图有回路时：

(2)

(3)

第30页，共80页，2023年，2月20日，星期三31证明（2）：用数学归纳法

若n=0,则有

Rm○R0=Rm○IA=Rm=Rm+0假设Rm○Rn=Rm+n,则有

Rm○Rn+1=Rm○

(Rn○R)=(Rm○Rn)○R=Rm+n+1

。幂运算的性质（续）证明（3）：

若n=0,则有假设则有课后习题：4.2，4.3，4.13第31页，共80页，2023年，2月20日，星期三第32页，共80页，2023年，2月20日，星期三第33页，共80页，2023年，2月20日，星期三第34页，共80页，2023年，2月20日，星期三§4.3关系的性质R的关系矩阵：主对角线元素全是1R的关系图：每个顶点都有环自反性：xA

有<x,x>R(R是A上的关系)关系矩阵：主对角线元素全是0关系图：每个顶点都没有环反自反性：xA<x,x>R第35页，共80页，2023年，2月20日，星期三例1：A={1,2,3},R1={<1,1>,<2,2>}R2={<1,1>,<2,2>,<3,3>}R3={<1,1>,<2,2>,<3,3>,<2,3>}R4={<1,1>,<1,2>,<2,3>}R5={<1,2>,<2,3>}既不是自反的也不是非自反的自反的自反的既不是自反的也不是非自反的反自反的例1：是自反的一定不是反自反的；是反自反的一定不是自反的！在自反性方面R有3种可能：自反的；反自反的；既非自反又非反自反的第36页，共80页，2023年，2月20日，星期三对称性：若<x,y>R，则<y,x>R

关系矩阵：对称阵(aij=aji)关系图：如果两个顶点之间有边，一定是一对方向相反的边。反对称性：若<x,y>R且xy，则<y,x>R

关系矩阵：如果rij

=1，且ij，则rji

=0关系图：如果两个顶点之间有边，一定是只有一条有向边。！R={<x,x>|xR}既是对称关系又是反对称关系第37页，共80页，2023年，2月20日，星期三例2：A={1,2,3},R1={<1,1>,<2,2>,<3,3>,<2,1>}R2={<1,1>,<2,2>,<3,3>}R3={<1,1>,<1,2>,<2,1>}R4={<1,1>,<1,2>,<3,1>}R5={<1,2>,<2,1>,<3,1>}反对称的既对称又反对称的对称的反对称的既非对称又非反对称的！在对称性方面R有4种可能：对称的；反对称的；既对称又反对称的；既非对称又非反对称的第38页，共80页，2023年，2月20日，星期三传递性：若<x,y>R且<y,z>R，则<x,z>R

关系图：如果顶点xi到xj有边，

xj到xk有边，则从xi到xk有边！若a可经过两条或两条以上的线到达b，则<a,b>R

第39页，共80页，2023年，2月20日，星期三例3：A={1,2,3,4},R1={<1,1>,<2,2>,<3,3>}R2={<1,2>,<3,4>}R3={<1,1>,<1,2>,<2,1>}R4={<1,2>,<2,3>,<1,3>,<2,2>}R5={<1,2>,<2,1>,<3,1>,<1,3>,<3,3>}传递的传递的非传递的传递的非传递的！在传递性方面，R有两种可能：传递的；非传递的。第40页，共80页，2023年，2月20日，星期三练习：自反的对称的反对称的传递的自反的对称的传递的反自反的反对称的反对称的传递的课后习题：4.4，4.12根据关系图判断关系的综合性质：第41页，共80页，2023年，2月20日，星期三§4.4关系的闭包运算闭包：设RAA，自反闭包记作r(R)对称闭包记作s(R)传递闭包记作t(R)那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包；包含R而使之具有传递性质的最小关系，称之为R的传递闭包。一、定义包含R而使之具有对称性质的最小关系，称之为R的对称闭包。第42页，共80页，2023年，2月20日，星期三幂运算：设RAA，kN，约定(1)R0=IA={<x,x>|xA}(2)R1=R(3)Rk+1=Rk

R二、计算方法为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。第43页，共80页，2023年，2月20日，星期三１．逻辑运算方法：设R是A上的任一关系，则(1)r(R)

=R∪IA(2)s(R)

=R∪R(3)t(R)

=R∪R2∪R3∪…∪Rn-1第44页，共80页，2023年，2月20日，星期三２．矩阵形式：(M为R的关系矩阵)(1)Mr=M+E（单位矩阵）(2)Ms=M+M'(M'是M的转置)(3)Mt=M+M2

+….+Mn-1其中“+”均表示“逻辑加”第45页，共80页，2023年，2月20日，星期三３．关系图法：(1)自反闭包图：对没有加环的点加环(2)对称闭包图：单边的加方向相反的边(3)传递闭包图：若Ai经过两条或两条以上的边可到达Aj，且无边<Ai,Aj>则加边<Ai,Aj>第46页，共80页，2023年，2月20日，星期三例4.10

设A={a,b,c,d}，A上的关系求r(R)，s(R)和t(R)解：1.逻辑求法：

r(R)=R∪IA={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<c,c>,<d,d>}R={<a,b>,<b,a>,<b,c>,<c,d>}=R∪{<a,a>,<b,b><c,c>,<d,d>}三、实例第47页，共80页，2023年，2月20日，星期三={<a,b>,<b,a>,<b,c>,<c,d>,<c,b>,<d,c>}=R∪{<b,a>,<a,b><c,b>,<d,c>}s(R)

=R∪Rt(R)

=R∪R2∪R3∪…∪Rn-1=R∪{<a,a>,<a,c><b,b>,<b,d>}∪{<a,b>,<a,d><b,a>,<b,c>}={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<a,c><b,b>,<b,d>,<a,d>}R={<a,b>,<b,a>,<b,c>,<c,d>}第48页，共80页，2023年，2月20日，星期三2.矩阵运算：

R={<a,b>,<b,a>,<b,c>,<c,d>}第49页，共80页，2023年，2月20日，星期三3.关系图方法：

课后习题：4.14Rr(R)t(R)s(R)第50页，共80页，2023年，2月20日，星期三第51页，共80页，2023年，2月20日，星期三§4.5等价关系和偏序关系等价关系：集A上的关系R是自反的,对称的和传递的。一、等价关系及用途例4.5.1：A={1,2,3,…,8}，R={<x,y>|x≡y(mod3)}则1～4～7，2～5～8，3～6设R是一个等价关系,若<x,y>∈R,称x等价于y,记做x～y.第52页，共80页，2023年，2月20日，星期三相容关系：

R是集A上的关系，且R是自反的，对称的(1)在一群人的集合上年龄，姓名相同的关系是等价关系,而朋友关系是相容关系，因为它可能不是传递的.

(2)动物是按种属分类的；“具有相同种属性”的关系是动物集合上的等价关系.(3)集合上的恒等关系和全域关系都是等价关系.(4)在同一平面上三角形之间的相似关系是等价关系,但直线间的平行关系不是等价关系也不是相容关系,因为它不是自反的.例子：！等价关系一定是相容关系；相容关系不一定是等价关系第53页，共80页，2023年，2月20日，星期三等价类：

R是集A上的等价关系，对于任一aA，[a]R={x|aRx,xA}被称为a的等价类。即：[x]R={y|x~y}在例4.5.1中：[1]R

=[4]R=[7]R={1,4,7};[2]R

=[5]R=[8]R={2,5,8};[3]R

=[6]R=[9]R={3,6,9};第54页，共80页，2023年，2月20日，星期三等价类的性质：R是非空集合，对任意的x，yA，下面的结论成立：(1)[x]R

且[x]R

A(等价类为A的子集)(2)若x~y则[x]R

=[y]R，反之成立。(3)若xRy，则[x]R

∩[y]R

=

第55页，共80页，2023年，2月20日，星期三集A在等价关系R下的商集：设R为非空集A上的等价关系，A在R下的商集记作A/R，A/R={[x]R

|xA}.(集合的集合）例4.5.1的商集为：A/R={{1,4,7},{2,5,8},{3,6,9}}注意：A/EA={A}

A/IA={{x}|x∈A}第56页，共80页，2023年，2月20日，星期三集A的划分：令=A/R，满足以下性质：(1)(2)中任意两个元素不交

(3)中所有元素的并集为A则为A的划分。集合A上的划分是不唯一的第57页，共80页，2023年，2月20日，星期三对于集合A，若给定一个等价关系，则我们可唯一确定一个商集集合A上的等价关系与划分是一一对应的。集合A上的一个商集可唯一确定A上的一个划分第58页，共80页，2023年，2月20日，星期三例4.5.2

设A={1,2,3}，求出A上所有的等价关系：解：先求A的各种划分：只有1个划分块的划分1，具有两个划分块的划分2，3，和4，具有3个划分块5。第59页，共80页，2023年，2月20日，星期三设对应于划分i的等价关系Ri，i=1,2,…5，则有R5={<1,1>，<2,2>，<3,3>}R1={<1,1>，<1,2>，<1,3>，R2={<1,1>，R3={<2,2>，R4={<3,3>，<2,2>，<2,1>，<2,3>，<3,3>，<3,1>，<3,2>}<2,2>，<2,3>，<3,3>，<3,2>}<1,1>，<1,3>，<3,3>，<3,1>}<2,2>，<2,1>}<1,1>，<1,2>，第60页，共80页，2023年，2月20日，星期三偏序关系：集合A上的关系R是自反的，反对称的和传递的，记作“”。二、偏序关系及用途设R为偏序关系,如果<x,y>R,则记作xy,读作“x小于等于y”.注意:这里的“小于等于”不是指数的大小,而是在偏序关系中的顺序性.第61页，共80页，2023年，2月20日，星期三例4.5.3

设A={1,2,3}，求出A上的大于等于关系：解：={<1,1>,<2,1>,<2,2>,<3,1>,<3,2>,<3,3>}其中：11,

21,22,31,32,33第62页，共80页，2023年，2月20日，星期三偏序关系例子：（1）任何集合A上的恒等关系（2）集合A的幂集P(A)上的包含关系（4）正整数集上的整除关系都是偏序关系.（3）实数集上的小于等于，大于等于关系,第63页，共80页，2023年，2月20日，星期三相关概念：偏序集：集合A和偏序关系R≤

构成一个偏序集，记作<A,R≤

>。如：<A,R

>,<A,R整除>等可比：对于任意两个元素x和y，若x≤y或y≤x，则x与y是可比的全序关系与全序集：若A中任意两个元素都是可比的，则R≤为全序关系；<A,R≤>为全序集。第64页，共80页，2023年，2月20日，星期三盖住：如果x≤y，且不存在z使x≤z≤y(不是间接的),则称y能盖住x。例：锅，笼屉，锅盖火车卧铺的下铺，中铺，上铺第65页，共80页，2023年，2月20日，星期三例4.5.4

设A={1,2,3,4}，求出A上的整除关系：解:R整除={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,4>,<3,3>,<4,4>}则：2,3能盖住1；4能盖住2；4不能盖住1第66页，共80页，2023年，2月20日，星期三偏序集的哈斯图(1)去掉箭头；（盖住）(2)去掉间接关系；（传递）(3)去掉环。（自反的）第67页，共80页，2023年，2月20日，星期三哈斯图实例例4.5.5：画出<{1,2,3,4,5,6,7,8,9},R整除>

和<P({a,b,c}),R>第68页，共80页，2023年，2月20日，星期三全序关系的哈斯图：全序集中全部元素可以排序，它的哈斯图为一条直线。也称为线序集。集合A上的偏序关系与哈斯图是一一对应的。课后习题：4.16第69页，共80页，2023年，2月20日，星期三第70页，共80页，2023年，2月20日，星期三(2)

若yA，使得(x)(xAyx)，则称y是A的极大元

(没有比我大的)(1)

若yA，使得(x)(xA