离散数学及应用 课件 第4章 二元关系与函数

DiscreteMathematics离散数学项目化任务2在python中实现基于二元关系的智能家居系统。用于模拟基于事件和条件触发的智能家居系统。定义一些基本的设备类，并设置一个中央控制器来管理这些设备之间的交互。3第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数44.1集合的笛卡儿积和二元关系

有序对笛卡儿积及其性质二元关系的定义二元关系的表示5有序对定义

由两个客体x和y，按照一定的顺序组成的二元组称为有序对，记作<x,y>实例：点的直角坐标<3,

4>有序对性质有序性<x,y>

<y,x>例如：<3,

4>

<

4,3>

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

<x,y>=<u,v>

x=u

y=v例1<2,x+5>=<3y

4,y>，求x,y.解3y

4=2,x+5=y

y=2,x=3

课堂练习：第4.1（2）题6有序n元组定义一个有序n(n3)元组<x1,x2,…,xn>是一个有序对，其中第一个元素是一个有序n-1元组，即

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

当n=1时,<x>形式上可以看成有序1元组.

当n=2时,有序对，例如：平面直角坐标<3,4>.

当n=3时,例如：空间直角坐标<3,4,1>.实例

n维向量是有序

n元组.笛卡儿积定义设A,B为集合，A与B的笛卡儿积记作A

B，即A

B={<x,y>|x

A

y

B}.8笛卡儿积例1A={1,2,3},B={a,b,c}

A

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

B

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

},P(A)

A={

,{

}}

{

}={<

,

>,<{

},

>}课堂练习：A={

}，B={a,b}，求P(B)

A?提示：先写出来P(B)9Python编程验证集合运算的主要算律：结合律、交换律、分配律、同一律、零律、德摩根律集合元素的计数：文氏图法笛卡尔积：有序元组例1A={1,2,3},B={a,b,c}

A

B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}练习：

A={1,2},A

P(A)=？课前预习10课堂编程通过编程实现求给定集合A和B的笛卡儿乘积C的运算？提示：C=A

B={<x,y>|x

A

y

B

}

。输入集合为a,b，输出集合为c，即c=descartes(a,b)。(x,y)表示有序对。A={1,2,3},B={a,b,c}

A

B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}注意：大括号表示集合(小括号不能)，小括号表示有序元组(如笛卡尔积)中括号表示列表11笛卡儿积的性质不适合交换律

A

B

B

A(A

B,A

,B

)不适合结合律

(A

B)

C

A

(B

C)(A

,B

)对于并或交运算满足分配律

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)12笛卡儿积的性质若A或B中有一个为空集，则A

B就是空集.

A

=

B=

注意：A{}不一样练习：A={0,1},B={}，求A

B?若|A|=m,|B|=n,

则|A

B|=？

13课堂练习通过Python编程证明：A

B

B

A(A

B)

C

A

(B

C)A

(B

C)=(A

B)

(A

C)A

(B

C)=(A

B)

(A

C)提示：并交用bing(),jiao()，笛卡尔积函数为:c=descartes(a,b)令A={1,2,3}，B={2,4,5}

，C={4,7,8}14性质的证明证明A

(B

C)=(A

B)

(A

C)证任取<x,y><x,y>∈A×(B∪C)

x∈A∧y∈B∪C（并集的定义）

x∈A∧(y∈B∨y∈C)（并集的定义）

(x∈A∧y∈B)∨(x∈A∧y∈C)(分配律)

<x,y>∈A×B∨<x,y>∈A×C

<x,y>∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).15二元关系为什么要有二元关系？笛卡尔积穷举了所有的元素，但实际应用中，我们不需要知道所有的元素，只需要知道我们关心的元素，例如：选课过程中，我关心的是选离散数学的学生校运动会中，每个人关心的是自己选择的运动项目实例：同学关系、父子关系、师生关系。16二元关系的定义定义如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.抢答：R={<1,2>,<a,b>},S={<1,2>,a,b},

二元关系？R是二元关系；由于a,b不是有序对，S不是二元关系17二元关系的定义如<x,y>∈R,可记作xRy；如果<x,y>

R,则记作xyR={<1,2>,<a,b>}根据上面的记法，可以写1R2,aRb,ac等.18从A到B的关系与A上的关系定义设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例

A={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到B的二元关系是笛卡尔积A

B的子集

是任何集合的二元关系

课堂提问：R5={<0,2>,<1,2>,<1,0>},R6={<1,2>,<1,1>,<1,3>}是否为从A到B二元关系？

19课堂练习A={1}，求A上的所有二元关系？A={0,1},B={2}，求A×B的所有二元关系？A={1,2},B={2,3}，求A×B的所有二元关系？提示：笛卡尔积的所有子集0元子集：1元子集：2元子集：。。。

20二元关系计数计数|A|=n,|A×A|=n2（笛卡尔积个数），

A×A的子集有个(推理见教材)所以，A上有个不同的二元关系.例如|A|=3,则A上有=512个不同的二元关系.|A|=n,|B|=m,|A×B|=mnA×B的子集有个所以，A上有个不同的二元关系.21A上重要关系的实例设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>}

课堂练习：A={a,b,c},求EA和IA22A上重要关系的实例（续）小于等于关系LA,整除关系DA,包含关系R

定义：

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

R，R为实数集合

DB={<x,y>|x,y∈B∧x整除y},B

Z*,Z*为非0整数集

R

={<x,y>|x,y∈A∧x

y},A是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.23实例例如A={1,2,3},B={a,b},C={

,{a},{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>}

则C上的包含关系是R

={<

,

>,<

,{a}>,<

,{b}>,<

,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}

课堂练习：A={1,2,3},求A上的大于关系?

A={

,{1},{1,2}},求A上的包含关系?

设A={1,2,4,7,8}，B={2,3,5,7}，定义由A到B的关系R={(a,b)|(a+b)/5是整数}，求关系R。

课程回顾二元关系的定义：笛卡尔积的子集**能够计算所有二元关系，即所有笛卡尔积的子集**步骤：0-n元子集罗列，共有2n个重要的二元关系：小于等于关系,整除关系,包含关系课堂练习：A={1,2,3,4},求A上的小于等于关系?B={{1},{1,2},{1,2,3}},求A上的包含关系

?

25课堂练习输入集合A，编程自动输出小于等于关系LA，整除关系DA，包含关系R

对应的集合.

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

DA={<x,y>|x,y∈A∧x整除y}R

={<x,y>|x,y∈B∧x

y}实例：A={1,2,3,4}、B={{1},{1,2},{1,2,3}}。

(x,y)表示有序对。26课堂练习27关系的表示表示方式：关系的有序对集合、关系矩阵、关系图关系矩阵：若A={a1,a2,…,am}，B={b1,b2,…,bn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]m

n,其中28关系的表示关系图：若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=<A,R>,其中A为结点集，R为边集.如果<xi,xj>属于关系R，在图中就有一条从xi

到xj的有向边.注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系29实例A={1,2,3,4},R的关系矩阵MR和关系图GR如下：30实例A={1,2,3,4}有序对集合、关系矩阵如下：R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},DiscreteMathematics鄢小虎

离散数学32基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质4.2关系的运算33关系的基本运算定义定义域、值域

和域

domR={x|

y(<x,y>

R)}所有第一个元素构成ranR={y|

x(<x,y>

R)}所有第二个元素构成fldR=domR

ranR例1R={<1,2>,<1,3>,<2,4>,<4,3>},则

domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}关系的基本运算定义（续）逆与合成

R

1={<y,x>|<x,y>

R}(调换顺序)

R∘S=|<x,z>|

y(<x,y>

R

<y,z>

S)}(首尾相连)例2R={<1,2>,<2,3>,<1,4>,<2,2>}

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

R

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

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

S∘R={<1,2>,<1,4>,<3,2>,<3,3>}课堂练习：课本第117页第4.13题。

35课堂编程通过编程实现给定集合R和S的逆与合成操作？提示：

R

1={<y,x>|<x,y>

R}

R∘S=|<x,z>|

y(<x,y>

R

<y,z>

S)}。实例：R={<1,2>,<2,3>,<1,4>,<2,2>}

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}封装为函数ni(),hecheng()36限制与像定义

F在A上的限制

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

x

A}A在F下的像

F[A]=ran(F↾A)实例R={<1,2>,<2,3>,<1,4>,<2,2>}

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

R[{1}]={2,4}R↾{1,2}={<1,2>,<1,4>,<2,3>,<2,2>}R[{1,2}]={2,3,4}注意：F↾A

F,F[A]ranF

37课堂练习第114页，第4.3题38课堂编程通过编程求解F在A上的限制，A在F下的像。提示：

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

x

A}

F[A]=ran(F↾A)实例：R={<1,2>,<2,3>,<1,4>,<2,2>}

A={1}课程回顾关系的表达：有序对集合、关系矩阵、关系图基本运算定义定义域、值域、域逆、合成、限制、像

练习：课本114页，第4.3题。如何通过编程验证算律？40关系基本运算的性质定理1设F是任意的关系,则

(1)(F

1)

1=F(2)domF

1=ranF,ranF

1=domF（否定律）编程练习：通过逆与合成操作的函数，验证以上的公式(1)实例：F={<1,2>,<2,3>,<1,4>,<2,2>}41定理2设F,G,H是任意的关系,则

(1)(F∘G)∘H=F∘(G∘H)

（结合律）(2)(F∘G)

1=G

1∘F

1（交换位置）关系基本运算的性质（续）

编程练习：通过逆与合成操作的函数，验证以上两个公式实例：F={<1,2>,<2,3>,<1,4>,<2,2>}

G={<1,1>,<2,3>},H={<2,3>,<3,2>,<3,3>}42定理3设F,G,H是任意的关系,则(1)F∘(G

H)=F∘G

F∘H(2)F∘(G

H)

F∘G

F∘H关系基本运算的性质（续）

编程练习：通过并、交、合成操作的函数，验证以上两个公式提示：当A中的所有元素都在B中，则A

B实例：F={<1,2>,<2,3>,<1,4>,<2,2>}

G={<1,1>,<2,3>},H={<2,3>,<3,2>,<3,3>}43定理3设F,G,H是任意的关系,则(3)(G

H)∘

F=G

∘F

H∘F(4)(G

H)

∘

F

G∘F

H∘F关系基本运算的性质编程练习：通过并、交、合成操作的函数，验证以上两个公式提示：当A中的所有元素都在B中，则A

B；交的函数？实例：F={<1,2>,<2,3>,<1,4>,<2,2>}

G={<1,1>,<2,3>},H={<2,3>,<3,2>,<3,3>}44A上关系的幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：

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

(2)Rn+1=Rn∘R例如：A={1,2}，R为A上的关系，

则：R0={<1,1>,<2,2>}R3=R2∘R=R∘R∘R更高次幂该怎么计算？

45幂的求法（了解）对于集合表示的关系R，计算Rn就是n个R右复合.矩阵表示就是n个矩阵相乘,其中相加采用逻辑加.例3设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R2、R3、R4、R5的值，并通过程序验证

46幂的求法（续）分别用矩阵和关系图表示各次幂，R与R2的关系矩阵分别为注意：先乘后加.

矩阵的元素相加时使用逻辑加，即为：0+0=00+1=11+0=11+1=1(课后)编程练习：编程计算R2

，R3，R4，R5的关系矩阵

提示：难度较大47同理，R3和R4的矩阵分别是：因此M4=M2,即R4=R2.因此可以得到

R2=R4=…,R3=R5=…

幂的求法（续）48R0,R1,R2,R3,…的关系图如下图所示幂的求法（续）49幂运算的性质定理3设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.DiscreteMathematics鄢小虎

离散数学课程回顾关系的表达：有序对集合、关系矩阵、关系图基本运算定义域、值域、域逆、合成、限制、像高级运算幂运算

对应矩阵中，矩阵具有哪些性质？对称性？524.3关系的性质自反性反自反性对称性反对称性传递性53自反性与反自反性定义设R为A上的关系,

(1)若

x(x∈A→<x,x>

R),则称R在A上是自反的.

(2)若

x(x∈A→<x,x>

R),则称R在A上是反自反的.

实例：同姓关系、父子关系？54自反性特点关系图中，每个结点都有环55自反性特点关系矩阵中，主对角线都为156课堂提问下列关系是否为自反关系？恒等关系IA

？小于等于关系LA？(小于关系？)整除关系DA？57反自反性特点关系图中，每个结点都无环58反自反性特点关系矩阵中，主对角线都为059课堂提问下列关系是否为反自反关系？实数集上的小于关系？60实例例1A={1,2,3},R1,R2,R3是A上的关系,其中

R1＝{<1,1>,<2,2>}

R2＝{<1,1>,<2,2>,<3,3>,<1,2>}

R3＝{<1,3>}R1既不是自反也不是反自反的R2自反,R3反自反总结：可以既不是自反也不是反自反的但不能同时为自反和反自反61自反和反自反

自反反自反表达式IA

RR∩IA=

关系矩阵主对角线元素全是1主对角线元素全是0关系图每个顶点都有环每个顶点都没有环62编程练习判断关系R是否为自反关系和反自反关系。提示：自反：IA

R；反自反：R∩IA=

实例：A={1,2,3}，R＝{<1,1>,<2,2>,<3,3>,<1,2>}输入：集合A和关系R；输出：是和否通过对集合A进行循环，从而构造IA63编程练习已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为自反关系和反自反关系。

提示：主对角线元素全是1（0）实例：64对称性与反对称性定义

设R为A上的关系,

(1)若

x

y(x,y∈A∧<x,y>∈R→<y,x>∈R),则称R为A上对称的关系.

(2)若

x

y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),则称R为A上的反对称关系.判断：同姓关系、朋友关系？65对称性特点若有边，则成对出现；没有边也是可以的66对称性特点67反对称性特点若有边，则只有一条边；没有边也是可以的68反对称性特点69课堂提问下列关系是否为对称和反对称关系？恒等关系IA？空关系？父子关系？

70实例例2设A＝{1,2,3},R1,R2,R3和R4都是A上的关系,

其中

R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}

R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}

R1

对称、反对称.R2

对称，不反对称.R3

反对称，不对称.R4

不对称、也不反对称.总结：可以同时为(不为)对称和反对称71总结：对称和反对称

对称反对称表达式R=R

1

R∩R

1

IA

关系矩阵矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0关系图如果两个顶点之间有边,是一对方向相反的边(无单边)如果两点之间有边,是一条有向边(无双向边)72编程练习判断关系R是否为对称关系和反对称关系。提示：对称：R=R

1

；反对称：R∩R

1

IA

实例：A={1,2,3}，R＝{<1,1>,<1,2>,<2,1>}73扩展：编程练习已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为对称关系和反对称关系。

提示：对称：矩阵是对称矩阵；

反对称：若rij＝1,且i≠j,则rji＝0实例：74传递性定义

设R为A上的关系,若

x

y

z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),

则称R是A上的传递关系.

实例：恒等关系IA和空关系

小于等于关系,小于关系，整除关系，包含关系，真包含关系

同姓关系、父子关系、朋友关系？75传递关系

传递表达式R∘R

R关系矩阵对M2中1所在位置,M中相应位置都是1关系图如果顶点xi到xj有边，

xj

到xk有边，则从xi到xk

有边

如何存在两步可以到的边，一定存在一步可以到的边；没有两步可以到的边也ok76实例例3设A＝{1,2,3},R1,R2,R3是A上的关系,其中

R1＝{<1,1>,<2,2>}

R2＝{<1,2>,<2,3>}

R3＝{<1,3>}

R1是A上的传递关系R2不是A上的传递关系R3是A上的传递关系77编程练习判断关系R是否为传递关系。提示：R∘R

R实例：A={1,2,3}，R＝{<1,1>,<2,2>,<3,3>,<1,2>}78扩展：编程练习已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为传递关系。提示：对M2(逻辑加)中1所在位置,M中相应位置都是1实例：79关系性质的充要条件设R为A上的关系,则

(1)R在A上自反当且仅当IA

R

(2)R在A上反自反当且仅当R∩IA=

(3)R在A上对称当且仅当R=R

1

(4)R在A上反对称当且仅当R∩R

1

IA

(5)R在A上传递当且仅当R

R

R

80自反性证明证明模式证明R在A上自反任取x,x

A

……………..….…….

<x,x>

R

前提推理过程结论例4证明若IA

R，则

R在A上自反.证任取x,

x

A

<x,x>

IA

<x,x>

R

因此R在A上是自反的.81对称性证明证明模式证明R在A上对称任取<x,y><x,y>

R

……………..….…….

<y,x>

R

前提推理过程结论例5证明若R=R

1,则R在A上对称.证任取<x,y>

<x,y>

R

<y,x>

R

1

<x,y>

R

因此R在A上是对称的.

82反对称性证明证明模式证明R在A上反对称任取<x,y><x,y>

R

<y,x>

R

………..……….

x=y

前提推理过程结论例6证明若R∩R

1

IA,

则R在A上反对称.证任取<x,y>

<x,y>

R

<y,x>

R

<x,y>

R

<x,y>

R

1

<x,y>

R∩R

1

<x,y>

IA

x=y

因此R在A上是反对称的.83传递性证明证明模式证明R在A上传递任取<x,y>，<y,z><x,y>

R

<y,z>

R

…..……….

<x,z>

R

前提推理过程结论例7证明若R

R

R

,

则R在A上传递.证任取<x,y>，<y,z><x,y>

R

<y,z>

R

<x,z>

R

R

<x,z>

R

因此R在A上是传递的.84运算与性质的关系(了解)自反性反自反性对称性反对称性传递性R1

1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1

R2

×√√√×R1∘R2

√××××85课前复习

传递表达式R∘R

R关系矩阵对M2中1所在位置,M中相应位置都是1关系图如果顶点xi到xj有边，

xj

到xk有边，则从xi到xk

有边

对称反对称表达式R=R

1

R∩R

1

IA

关系矩阵矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0关系图如果两个顶点之间有边,是一对方向相反的边(无单边)如果两点之间有边,是一条有向边(无双向边)空集包含于任何集合86实例例8判断下图中关系的性质,并说明理由.(b)反自反，不是自反的；反对称，不是对称的；是传递的.(a)不自反也不反自反；对称,不反对称；不传递.(c)自反，不反自反；反对称，不是对称；不传递.提问？

习题4.12题。R={<1,9>,<9,1>,<2,8>,<8,2>,<3,7>,<7,3>,<4,6>,<6,4>,<5,5>}自反：反自反：对称：反对称：传递：88课堂练习判断以下的关系的性质：A＝{1,2,3},R1＝{<1,1>,<2,2>}自反：反自反：对称：反对称：传递：89课堂练习课本第114页，习题4.4，列出满足下列性质的关系自反：反自反：对称：反对称：传递：DiscreteMathematics鄢小虎

离散数学914.4关系的闭包闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质92为什么需要闭包？有时候希望关系R有一些性质，如：自反（对称或传递）性。为此，需要再R中加入一些有序对，构成新的关系R

，使得R

具有所需的性质，但又希望有序对尽可能少。满足以上要求的R

就是R的自反（对称或传递）闭包。说明：本书只研究自反、对称、传递闭包93闭包定义

定义设R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R

,使得R

满足以下条件：

（1）R

是自反的（对称的或传递的）

（2）R

R

（3）对A上任何包含R的自反（对称或传递）关系R

有R

R

.(有序对尽量少)

一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).94闭包的构造方法(应用)定理1设R为A上的关系,则有

(1)r(R)=R∪R0

(2)s(R)=R∪R

1

(3)t(R)=R∪R2∪R3∪…

说明：对于有穷集合A(|A|=n)上的关系,(3)中的并最多不超过Rn.

若R是自反的，则r(R)=R;若R是对称的，则

s(R)=R;若R是传递的，则t(R)=R.A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<a,d>}计算集合A的自反、对称和传递闭包，并编程验证依据：(1)r(R)=R∪R0(R0

=IA)

(2)s(R)=R∪R

1

(3)t(R)=R∪R2∪R3∪…

95课堂练习设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则

Mr=M+EMs=M+M

Mt=M+M2+M3+…E是和M同阶的单位矩阵,M

是M的转置矩阵.注意：在上述等式中矩阵的元素相加时使用逻辑加，即为：0+0=00+1=11+0=11+1=196闭包的构造方法（续）从键盘输入一个关系的关系矩阵，计算其自反、对称和传递闭包提示：Mr=M+EMs=M+M

Mt=M+M2+M3+…实例：A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<a,d>}97编程练习98闭包的构造方法（续）设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新边：

考察G的每个顶点,如果没有环就加上一个环，最终得到Gr.考察G的每条边,如果有一条xi到xj的单向边,i≠j,则在G中加一条xj到xi的反方向边，最终得到Gs.考察G的每个顶点xi,找从xi出发的每一条路径，如果从xi到路径中任何结点xj没有边，就加上这条边.当检查完所有的顶点后就得到图Gt.99实例例1设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R、

r(R)、s(R)的关系图如下图所示.Rr(R)s(R)补环补边100课堂练习课本第116页，习题4.14，求r(R)、s(R)的关系图DiscreteMathematics鄢小虎

离散数学1024.5等价关系与偏序关系等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应偏序关系

等价关系非空集合A上的自反的、对称的和传递的关系偏序关系非空集合A上的自反、反对称和传递的关系如何判断等价关系、偏序关系？A={a,b,c,d},R={<a,b>,<b,c>,<a,d>}计算R的等价关系、偏序关系？提示：关系矩阵、关系图、闭包（去重）三种方法。先自反、对称，最后计算传递闭包104等价关系的定义与实例定义设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若<x,y>∈R,称x等价于y,记做x～y.

实例设A={1,2,…,8},如下定义A上的关系R：

R={<x,y>|x,y∈A∧x≡y(mod3)}

其中x≡y(mod3)叫做x与y

模3相等,即x除以3的余数与y除以3的余数相等.105A上模3等价关系的关系图设A={1,2,…,8},

R={<x,y>|x,y∈A∧x≡y(mod3)}

106等价类定义设R为非空集合A上的等价关系,

x∈A，令

[x]R={y|y∈A∧xRy}称[x]R为x关于R的等价类,简称为x的等价类,简记为[x].实例A={1,2,…,8}上模3等价关系的等价类：

[1]=[4]=[7]={1,4,7}

[2]=[5]=[8]={2,5,8}

[3]=[6]={3,6}107等价类的性质

定理1

设R是非空集合A上的等价关系,则

(1)

x∈A,[x]是A的非空子集.

(2)

x,y∈A,如果xRy,则[x]=[y].

(3)

x,y∈A,如果xy,则[x]与[y]不交.

(4)∪{[x]|x∈A}=A，即所有等价类的并集就是A.

108实例A={1,2,…,8}上模3等价关系的等价类：

[1]=[4]=[7]={1,4,7}，

[2]=[5]=[8]={2,5,8}，

[3]=[6]={3,6}

以上3类两两不交，

{1,4,7}{2,5,8}{3,6}={1,2,…,8}109商集定义

设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,A/R={[x]R

|x∈A}实例A={1,2,…,8},A关于模3等价关系R的商集为

A/R={{1,4,7},{2,5,8},{3,6}}

A关于恒等关系和全域关系的商集为：

A/IA

={{1},{2},…,{8}}

A/EA

={{1,2,…,8}}110集合的划分定义设A为非空集合,若A的子集族π(π

P(A))满足下面条件：

(1)

π(2)π中任意两个元素不交(3)π中所有元素的并集等于A

则称π是A的一个划分,称π中的元素为A的划分块.111例题例1设A＝{a,b,c,d},

给定π1,π2,π3,π4,π5,π6如下：

π1={{a,b,c},{d}}，π2={{a,b},{c},{d}}

π3={{a},{a,b,c,d}},π4={{a,b},{c}}

π5={

,{a,b},{c,d}},π6={{a,{a}},{b,c,d}}

课堂提问：则π1和π2

是A的划分,其他都不是A的划分.为什么？112等价关系与划分的一一对应商集A/R就是A的一个划分不同的商集对应于不同的划分例2给出A＝{1,2,3}上所有的等价关系求解思路：先做出A的所有划分,然后根据划分写出对应的等价关系.划分等价关系113等价关系与划分之间的对应π2,π3和π3分别对应等价关系R2,R3和R4.

R2={<2,3>,<3,2>}∪IA，R3={<1,3>,<3,1>}∪IA

R4={<1,2>,<2,1>}∪IAπ1对应于全域关系EA，π5对应于恒等关系IA213

1

213

5213

2213

4213

3114课堂练习例3设A={1,2,3,4}，在A

A上定义二元关系R：

<<x,y>,<u,v>>

R

x+y=u+v，求R导出的划分.

解A

A={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}115课堂练习（续）根据<x,y>的x+y=2,3,4,5,6,7,8将A

A划分成7个等价类：

(A

A)/R={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<2,3>,<3,2>,<4,1>},{<2,4>,<3,3>,<4,2>},{<3,4>,<4,3>},{<4,4>}}

116偏序关系定义非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作≼.设≼为偏序关系,如果<x,y>∈≼,则记作x≼y,读作x“小于或等于”y.

实例集合A上的恒等关系IA是A上的偏序关系.

小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.也是等价关系？117偏序关系定义集合A和A上的偏序关系≼一起叫做偏序集,记作<A,≼>.

实例：整数集和小于等于关系构成偏序集<Z,≤>，幂集P(A)和包含关系构成偏序集<P(A),R

>.118相关概念x与y可比：设R为非空集合A上的偏序关系,

x,y

A,x与y可比

x≼y∨y≼x.

课堂提问：大于关系、小于等于关系、整除关系？

全序关系：

R为非空集合A上的偏序,

x,y

A,x与y都是可比的，则称R为全序实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系DiscreteMathematics鄢小虎

离散数学课程回顾

等价关系非空集合A上的自反的、对称的和传递的关系偏序关系非空集合A上的自反、反对称和传递的关系划分等价关系1214.6函数的定义与性质函数的定义函数定义从A到B的函数函数的像函数的性质函数的单射、满射、双射性构造双射函数122函数的本质为什么学习函数？函数是特殊的二元关系，以前学到所有关系的运算和性质都适用于函数123函数定义定义设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不是函数124函数相等定义设F,G为函数,则

F=G

F

G∧G

F

如果两个函数F和G相等,一定满足下面两个条件：

(1)domF=domG

(2)

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

注意：没有ranF=ranG

实例函数

F(x)=(x2

1)/(x+1),G(x)=x

1不相等,因为domF

domG.

125从A到B的函数定义

设A,B为集合,如果

f为函数

domf=A

ranf

B（不是等于）,则称f为从A到B的函数,记作f：A→B.实例

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

g：N→N,g(x)=2也是从N到N的函数126B上A定义所有从A到B的函数的集合记作BA,读作“B上A”，符号化表示为

BA={f|f：A→B}计数：

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

127实例例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>}

128课堂练习课本第117页，习题4.22，求P(A),

BA129函数的像定义设函数f：A→B,A1

A.

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

函数的像

f(A)

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

B.例3

设f：N→N,

且

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

f(A)=f({0,1})={f(0),f(1)}={0,2}

f(B)=？

130函数的像定义设函数f：A→B,A1

A.

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

函数的像

f(A)

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

B.例3

设f：N→N,

且

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

f(A)=f({0,1})={f(0),f(1)}={0,2}

f(B)=？

131函数的性质定义设f：A→B,

（1）若ranf=B,则称f：A→B是满射的.(值域用完)

（2）若

y∈ranf都存在唯一的x∈A使得f(x)=y,则称f：A→B是单射的.

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

满射意味着：

y

B,都存在x

A

使得

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

x1=x2

132课本第95页，例4.18。实例讲解（1）满射、非单射（2）不是函数（3）不是函数（4）抛物线，不是单射，也不是满射（5）是单射，是满射133课堂练习例4判断下面函数是否为单射,满射,双射的,为什么?

(1)f：R→R,f(x)=

x2+2x

1

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

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

134解(1)f：R→R,f(x)=

x2+2x

1

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

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

单调上升,是单射.但不满射,ranf=