离散数学 教学课件 作者 李盘林 第04章.ppt

《离散数学 教学课件 作者 李盘林 第04章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第四章关系4.1二元关系4.2关系运算4.3关系类型退出4.1二元关系二元关系，这里是指集合中两个元素之间的关系。1．基本概念定义4.1.1给定任意集合A和B，若RAB，则称R为从A到B的二元关系，特别在A=B时，称R为A上的二元关系。可见，R是有序对的集合。若R，则也表为xRy，即RxRy。若R=，则称R为A到B上空关系；若R=AB，称R为A到B上全域关系。特别当A=B时，称为A上空关系，称R=AA为A上的全域关系。称R={

2、xA}为A上的恒等关系，记为IA。类似地可定义n元

3、关系。若SAi，则称S为Ai上的n元关系。特别A1=A2=···=An时，称S为A上的n元关系。定义4.1.2令RAB，且D(R)={x

4、(y)(xRy)}R(R)={y

5、(x)(xRy)}F(R)=D(R)+R(R)则称D(R)、R(R)和F(R)分别是二元关系R的定义域、值域和域。显然D(R)A，R(R)B。由于关系是有序对的集合，对它可进行集合运算，其结果也是有序对的集合，即也是某一种二元关系。令R和S是两个二元关系，则R∪S，R∩S，R-S，RS和R’都分别定义了某一种二元关系，并且可表成：x(R∪S)

6、yxRyxSyx(R∩S)yxRyxSyx(R-S)yxRyxSyx(RS)yxRyxSyxR’yxRy2．关系矩阵与关系图表达从有穷集合到有穷集合的二元关系时，矩阵和有向图都是得力的工具。定义4.1.3给集合A={a1,a2,···,am}和B={b1,b2,···,bn}，且RAB，若1aiRbjrij=0否则则称矩阵MR=(rij)mn为R的关系矩阵。当给定关系R，可求出关系矩阵MR；反之，若给出关系矩阵MR，也能求出关系R。集合A上的二元关系R也可用有向图表示。具体方法是：用小圆圈“”表示

7、A中的元素，小圆圈称为图的结点。把对应于元素ai和aj的结点，分别标记ai和aj。。若R，则用弧线段或直线段把ai和aj连接起来，并在弧线或直线上设置一箭头，使之由ai指向aj；若R，则在结点ai上画一条带箭示的自封闭曲线或有向环，称这样的弧线或封闭曲线为弧或有向环。这样得到的有向图叫做关系R的图示，简称关系图，记为GR。3．关系的性质关系的性质是指集合中二元关系的性质，这些性质扮演着重要角色，下面将定义这些性质，并给出它的关系矩阵和关系图的特点。定义4.1.4令RAA，若对A中每

8、个x，都有xRx，则称R是自反的，即A上关系R是自反的<x)(xAxRx)该定义表明了，在自反的关系R中，除其他有序对外，必须包括有全部由每个xA所组成的元素相同的有序对。在全集U中所有子集的集合中，包含关系是自反的，相等关系=也是自反的；但是，真包含关系不是自反的。整数集合Z中，关系≤是自反的，而关系<不是自反的。定义4.1.5令RAA，若对于A中每个x，有xRx，则称R是反自反的，即A上关系R是反自反的<x)(xAxRx)该定义表明了，一个反自反的关系R中，不应包括有任何相同元素的有序对。由定义4

9、.1.4说明中，可知真包含关系是反自反的，但包含关系不是反自反的；小于关系<是反自反的，而≤不是反自反的。应该指出，任何一个不是自反的关系，未必是反自反的；反之，任何一个不是反自反的关系，未必是自反的。这就是说，存在既不是自反的也不是反自反的二元关系。定义4.1.6令RAA，对于A中每个x和y，若xRy，则yRx，称R是对称的，即A上关系R是对称的(x)(y)(x,yAxRy→yRx)该定义表明了，在表示对称的关系R的有序对集合中，若有有序对，则必定还会有有序对。在全集U的所有子集的集合中

10、，相等关系是对称的，包含关系和真包含关系都不是对称的；在整数集合Z中，相等关系=是对称的，而关系≤和<都不是对称的。定义4.1.7令RAA，对于A中每个x和y，若xRy且yRx，则x=y，称R是反对称的，即A上关系R是反对称的(x)(y)(x,yAxRyyRx→x=y)该定义表明了，在表示反对称关系R的有序对集合中，若存在有序对和，则必定是x=y。或者说，在R中若有有序对，则除非x=y，否则必定不会出现。在全集U的所有子集的集合中，相等关系=，包含关系和真包含关系

11、都是反对称的，但全域关系不是反对称的。在整数集合Z中，=，≤和<也都是反对称的。可见，有些关系既是对称的又是反对称的，如相等关系；有些关系是对称的但不是反对称的，如Z中的“绝对值相等”；有些关系是反对称的，但不是对称的，如Z中的≤和<。还有的关系既不是对称的又不是反对称的，例