第4章二元关系（一）ppt课件.ppt

《第4章二元关系（一）ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章二元关系4.1二元关系及其表示4.2关系的运算4.3关系的性质4.4关系的闭包运算4.5等价关系4.6相容关系第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。

2、若x,yR，则称x与y没有R关系。记为xy。定义4.1.3设A和B是任意集合，空集Æ叫做A到B的空关系，仍然记为Æ。A，B的笛卡尔积A×B叫做A到B的全域关系，记为E。集合a,a

3、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上的二元关系有2n2种。证明：设A为具有n个元素的有限集，即

4、A

5、=n，由排列组

6、合原理知

7、A×A

8、=n2。根据定理3.1.2有

9、P(A×A)

10、=2

11、A×A

12、=2，即A×A的子集有2个。所以具有n个元素的有限集A上有2种二元关系。例：若

13、A

14、=m，

15、B

16、=n，问A到B共有多少个不同的二元关系？解：2m×n4.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

17、xR∧yR∧x≤y，LR是实数集R上的二元关系。3.用矩阵表示二元关系如果A，B是有限

18、集，A=a1,a2,…,am，B=b1,b2,…,bn，R是A到B的二元关系，R的关系矩阵定义为：MR=mni=1,…,mj=1,…,n称为二元关系R的关系矩阵。【例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=【例4.4】设A=1,2,3,4，R是A的二元关系，定义为：R=1,1,1,2,2,1,3,2,3,1,4,3,

19、4,2,4,1写出A上二元关系R的关系矩阵。解：R的关系矩阵为：MR=例4.4中的二元关系R是A上的二元关系，只需看成A到A的二元关系，利用上述定义，就可以方便地写出它的关系矩阵。A上的二元关系和A到B的二元关系的关系矩阵的定义是相同的。4.用图表示二元关系如果A和B是有限集，R是A到B二元关系，表示二元关系R的图叫做R的关系图。A到B二元关系的关系图和A上的二元关系的关系图的定义是不一样的。分别描述如下：⑴A到B二元关系R的关系图设A=a1,a2,…,am，B=b1,b2,…,bn，R是A到B二元关系，R的关系图的绘制方法如下：①画出m个小圆圈表示A的

20、元素，再画出n个小圆圈表示B的元素。这些小圆圈叫做关系图的结点(下同)。②如果ai,bjR，则从ai到bj画一根有方向(带箭头)的线。这些有方向(带箭头)的线叫做关系图的边(下同)。⑵A上的二元关系R的关系图设A=a1,a2,…,am，R是A上的二元关系，其关系图如下绘制：①画出m个小圆圈表示A的元素。②如果ai,ajR，则从ai到aj画一根有方向(带箭头)的线。例4.3、例4.4中的二元关系R的关系图如下图4.2关系的运算定义4.2.1设A，B是集合，RA×B。domR=x

21、x,yR叫做R的定义域。ranR=y

22、x,yR叫做R的值域

23、。FLDR=domR∪ranR叫做R的域。4.2.1二元关系的交、并、补、对称差运算定理4.2.1设R，S是X到Y的二元关系，则R∪S，R∩S，R-S，~R，RS也是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的二元关系。在二元关系运算中，认为全域关系是全集。所以~R=X×Y-RX×Y，即~R是X到Y的二元关系。由以上结论可以得到：(R－S)X×Y和(S－R)