电子工业出版社：计算机类本科规划教材《离散数学》课程教学资源（PPT课件讲稿）第4章 二元关系

第4章二元关系 第4章二元关系 4.1二元关系及其表示 4.2关系的运算 4.3关系的性质 4.4关系的闭包运算 4.5等价关系 4.6相容关系 4,7序关系 返回总目录

第4章 二元关系 第4章 二元关系 4.1 二元关系及其表示 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包运算 4.5 等价关系 4.6 相容关系 4.7 序关系 返回总目录

第4章二元关系 第4章二元关系 4.1二元关系及其表示 41.1二元关系的概念 定义4.1.1设A4和B是任意集合,如果RcA×B,则称R是 A到B的二元关系。如果R是A到A的二元关系,则称R是A上 的二元关系。 设A=1,2,3},B=1ab},R=1,,}。R是A 到B的二元关系。S=}。S是A上的 二元关系。 定义41.2设4和B是任意集合,RA×B,若∈R, 则称x与y有R关系。记为xRy。若∈R,则称x与y没有R 关系。记为xRy

第4章 二元关系 第4章 二元关系 4.1二元关系及其表示 4.1.1二元关系的概念 定义4.1.1设A和B是任意集合，如果RA×B，则称R是 A到B的二元关系。如果R是A到A的二元关系，则称R是A上 的二元关系。 设A=1,2,3，B=a,b，R=1,a,2,a,3,b。R是A 到B的二元关系。S=3,1,2,2,2,1,1,1。S是A上的 二元关系。 定义4.1.2设A和B是任意集合，RA×B，若x,yR， 则称x与y有R关系。记为xRy。若x,yR，则称x与y没有R 关系。记为x R y

如果R是A到B的二元关系,根据定义41.2,,A到B的全域关系 E=A×B=1,,, 定理41.1设A是具有n个元素的有限集,则A上的二元关 系有22种 证明:设A为具有n个元素的有限集,即=n,由排列组 合原理知A×Am2根据定理3.1.2有P(×A)F214x4=22, 即A×A的子集有2个。所以具有n个元素的有限集A上有2种 二元关系

第4章 二元关系 如果R是A到B的二元关系，根据定义4.1.2，x,yR与 xRy，x,yR与x y的意义相同。 定义4.1.3设A和B是任意集合，空集叫做A到B的空关 系，仍然记为。A，B的笛卡尔积A×B叫做A到B的全域关 系，记为E。集合a,a|aA叫做A上的恒等关系。记为IA。 【例4.1】设A=a,b，B=1,2，求A上的恒等关系IA和 A到B的全域关系A×B。 解：A上的恒等关系IA =a,a,b,b，A到B的全域关系 E =A×B=a,1,a,2,b,1,b,2 定理4.1.1设A是具有n个元素的有限集，则A上的二元关 系有2 n2种。 证明：设A为具有n个元素的有限集，即|A|=n，由排列组 合原理知|A×A|=n 2 。根据定理3.1.2有|P (A×A) |=2 |A×A|=2 ， 即A×A的子集有2 个。所以具有n个元素的有限集A上有2 种 二元关系。 2 n 2 n 2 n R

第4章二元关系 41.2二元关系的表示 1用列举法表示二元关系 例41中的A到B的全域关系 E=A×B=, A上的恒等关系 R1 都是用列举法表示的。 2用描述法表示二元关系 设R是实数集,L2=1<xy|x∈ RAyER∧x≤y},L是 实数集R上的二元关系

第4章 二元关系 4.1.2二元关系的表示 1.用列举法表示二元关系 例4.1中的A到B的全域关系 E=A×B=a,1,a,2,b,1,b,2 A上的恒等关系 IA =a,a,b,b 都是用列举法表示的。 2.用描述法表示二元关系 设R是实数集，LR = x,y | xR∧yR∧x≤y， LR是 实数集R上的二元关系

第4章二元关系 3用矩阵表示二元关系 如果A,B是有限集, A B=b1,b2…bn} R是A到的的二元关系,R的关系矩阵定义为: mmn 1∈R 0∈R 称为二元关系R的关系矩阵

第4章 二元关系 3.用矩阵表示二元关系 如果A，B是有限集， A=a1 ,a2 ,…,am ， B=b1 ,b2 ,…,bn ， R是A到B的二元关系，R的关系矩阵定义为： MR = mn R R b b a a r j j i i ij          = , , 0 1 i=1,…,m j=1,…,n 称为二元关系R的关系矩阵。 ( ) ij r

第4章二元关系 例43】设A=a1a,a1a4},B=b1,b2,b3},R是A到B 的二元关系,定义为: R, b1>} 写出R的关系矩阵 解:R的关系矩阵为: O 1 oO O

第4章 二元关系 【例4.3】设A=a1 ,a2 ,a3 ,a4 ，B=b1 ,b2 ,b3 ，R是A到B 的二元关系，定义为： R=a1 ,b1 ,a1 ,b3 ,a2 ,b2 ,a2 ,b3 ,a3 ,b1 ,a4 ,b1 ,a4 ,b2  写出R的关系矩阵。 解：R的关系矩阵为： MR =               1 1 0 1 0 0 0 1 1 1 0 1

第4章二元关系 【例44】设A=1,2,3,4},R是A的二元关系,定义为 R={,,,} 写出A上二元关系R的关系矩阵。 解:R的关系矩阵为: 110 00 0000 例44中的二元关系R是A上的二元关系,只需看成A 到A的二元关系,利用上述定义,就可以方便地写出它 的关系矩阵。A上的二元关系和A到B的二元关系的关系 矩阵的定义是相同的

第4章 二元关系 【例4.4】设A=1,2,3,4，R是A的二元关系，定义为： R=1,1,1,2,2,1,3,2,3,1,4,3,4,2,4,1 写出A上二元关系R的关系矩阵。 解：R的关系矩阵为： MR =               1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0 例4.4中的二元关系R是A上的二元关系，只需看成A 到A的二元关系，利用上述定义，就可以方便地写出它 的关系矩阵。A上的二元关系和A到B的二元关系的关系 矩阵的定义是相同的

第4章二元关系 4用图表示二元关系 如果A和B是有限集,R是A到B二元关系,还可以 用图表示二元关系R。表示二元关系R的图叫做R的关 系图。A到B二元关系的关系图和A上的二元关系的关 系图的定义是不一样的。分别描述如下: (1)到B二元关系R的关系图 设扫=a1a2…an},B=b1b2…bn},R是A到B二 元关系,R的关系图的绘制方法如下: ①画出m个小圆圈表示A的元素,再画出n个小圆 圈表示B的元素。这些小圆圈叫做关系图的结点(下 ②如果∈R,则从a到b,画一根有方向(带箭 头)的线。这些有方向(带箭头)的线叫做关系图的边 (下同)

第4章 二元关系 4.用图表示二元关系 如果A和B是有限集，R是A到B二元关系，还可以 用图表示二元关系R。表示二元关系R的图叫做R的关 系图。A到B二元关系的关系图和A上的二元关系的关 系图的定义是不一样的。分别描述如下： ⑴A到B二元关系R的关系图 设A=a1 ,a2 ,…,am ，B=b1 ,b2 ,…,bn ，R是A到B二 元关系，R的关系图的绘制方法如下： ①画出m个小圆圈表示A的元素，再画出n个小圆 圈表示B的元素。这些小圆圈叫做关系图的结点(下 同)。 ②如果ai ,bj R，则从ai到bj画一根有方向(带箭 头)的线。这些有方向(带箭头)的线叫做关系图的边 (下同)

第4章二元关系 例43中的二元关系R的关系图如图4.1 (2A上的二元关系R的关系图 设A=a1a2…;an},R是A上的二元关系,其关系图如 下绘制: ①画出m个小圆圈表示A的元素。 ②如果ER,则从a到a画一根有方向(带箭头) 的线。 例44中的二元关系R的关系图如图42。 b3 返回章目录 图4.1 图4.2

第4章 二元关系 例4.3中的二元关系R的关系图如图4.1。 ⑵A上的二元关系R的关系图 设A=a1 ,a2 ,…,am ，R是A上的二元关系，其关系图如 下绘制： ①画出m个小圆圈表示A的元素。 ②如果ai ,aj R，则从ai到aj画一根有方向(带箭头) 的线。 例4.4中的二元关系R的关系图如图4.2。 返回章目录

第4章二元关系 42关系的运算 定义42.1设A,B是集合,RcA×B。 domR=xy∈R}叫做R的定义域 ranR=y∈R}叫做R的值域 FLDR= dom ru ran r叫做R的域。 A叫做R的前域;B叫做R的陪域。 42.1二元关系的交、并、补、对称差运算 定理42.1设R,S是X到Y的二元关系,则RUS,R∩S, R-S,~R,RS也是X到Y的二元关系。 证明:因为R,S是X到Y的二元关系,所以 RcX×Y且ScX×Y。显然, RUScX×Y,即RUS是X到Y的二元关系 R∩ScX×Y,即R∩S是X到Y的二元关系 RSX×Y,即RS是X到Y的二元关系

第4章 二元关系 4.2关系的运算 定义4.2.1设A，B是集合，RA×B。 dom R=x|x,yR  叫做R的定义域。 ran R=y| x,yR 叫做R的值域。 FLD R= dom R∪ran R叫做R的域。 A叫做R的前域；B叫做R的陪域。 4.2.1二元关系的交、并、补、对称差运算 定理4.2.1设R，S是X到Y的二元关系，则R∪S，R∩S， R-S，~R，R S也是X到Y的二元关系。 证明：因为R，S是X到Y的二元关系，所以， RX×Y且SX×Y。显然， R∪SX×Y，即R∪S是X到Y的二元关系。 R∩SX×Y，即R∩S是X到Y的二元关系。 R-SX×Y，即R-S是X到Y的二元关系。 