集合论-第三章2.ppt

《集合论-第三章2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§5关系矩阵和关系图前面介绍过的关系都是用集合表达式来定义的，对于有限集合上的关系还可以用关系矩阵和关系图的方法给出，这两种方法形象、直观，不仅对分析关系性质有很大的方便，而且也有利于用计算来处理有关问题。5.1关系矩阵定义1设A、B为有限集合,A={a1,a2,…,an},B={b1,b2,…,bm},则(1)若R是从A到B的二元关系，则n×m矩阵MR=(rij)n×m称为A到B的二元关系R的关系矩阵，简称关系矩阵。其中(2)若R是A上的关系，则n×n矩阵称为A上的二元关系R的关系矩阵，简称关系矩阵，其中：二、例题例1设A={a1,a2,a3,a4}，B={b1,b2,b3}。A到B的二

2、元关系R={(a1,b1),(a1,b3),(a2,b3),(a4,b2)}，则R的关系矩阵为：例2设A=1,2,3,4},，集合A上的大于关系“＞”定义为：＞={(2,1),(3,1),(4,1),(3,2),(4,2),(4,3)}，则关系“＞”的关系矩阵为：三、关系矩阵包含关系的信息设MR是关系R的关系矩阵，则(1)R是自反的⇔MR的对称线上的元素全为1。(2)R是反自反的⇔MR对称线上的元素全为0。(3)R是对称的⇔MR是对称的。(4)R是反对称的⇔若i≠j,则rij与rji不能同时为1。[或rij+rji≤1](5)R是传递的⇔若rij＝1且rjk＝1，则rik＝1。〔或MR·M

3、R≤MR，即R·R⊆R〕(6)R-1的关系矩阵为MRT。5.2关系图定义1设A，B为有限集合，A={a1,a2,…,an},B={b1,b2,…,bm},R是A到B的一个二元关系。首先在平面上用n个小圆点代表A中的n个元素，并在这些点的旁边标上a1,a2,…,an；然后用另外m个小圆点代表B中的m个元素，并在这些点旁边标上b1,b2,…,bm。于是有：若(ai,bj)∈R，则在顶点ai到作一条带箭头的线指向顶点bj；若(ai,bj)R，则ai与bj之间没有线联结。用这种方法构造的图形称为A到B的关系R的关系图，简称关系图。当A＝B时，A上的关系R的关系图画法类似。把A中的每一个元素在平面

4、上用点表示，并在这些点旁边标上元素的名字。若(ai,bj)∈R，则从代表ai的点画一条带箭头的线指向代表aj的点。若(ai,ai)∈R,则从顶点ai也画一条指向自己的矢线，称为环。这样得到的图形称为A上的关系R的关系图，简称关系图。说明：为了使图形直观，易于理解，通常把A中元素a1,a2,…,an画在左边，而把B中元素b1,b2,…,bm画在右边。2.例(1)设A={1,2,3,4},B={a,b,c}，A到B的二元关系R={(1,a),(2,a),(4,a),(3,b),(3,c)}，则R的关系图如图1所示。(2)设A={1,2,3,4}，则在A上的整除关系R={(1,1),(1,2),

5、(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}，则R的关系图如图2所示。图1图2二、关系图包含关系的所有信息(1)R是自反的⇔R的关系图的每个顶点都有一个环。(2)R是反自反的⇔R的关系图的每个顶点都没有环。(3)R是对称的⇔在R的关系图中，若两个不同的顶点间有弧，则必有方向相反的两条弧（对称弧）。(4)R是反对称⇔在R的关系图中，若两个不同的顶点之间有弧，则弧只有一条。(5)R是传递的⇔在R的关系图中，任意从某点沿箭头所指的方向经过二步走到另一点，则从该点必能一步走到另一点。5.3闭包的运算[用矩阵方法计算闭包]一、布尔矩阵的运算在关系矩阵MR中，rij的值不是

6、0就是1，这种矩阵称为布尔矩阵。把关系用对应的布尔矩阵表示，而布尔矩阵是代数所研究的对象，因此便于进行代数处理。特别是矩阵间可以进行代数运算，这有利于计算机的存储处理，下面介绍布尔矩阵间的若干运算。定义1设MR,MS是两个ｎ×ｍ阶的布尔矩阵，则（1）把MR和MS的对应元素的“逻辑和”所形成的矩阵称为MR与MS的逻辑和，记为MR∨MS。即MR∨MS=(rij∨sij)。其中，0∨0=0,0∨1=1∨0=1∨1。[∨运算是取最大]（1）把MR和MS的对应元素的“逻辑乘”所形成的矩阵称为MR与MS的逻辑乘，记为MR∧MS。即MR∧MS=(rij∧sij)。其中,0∧0=0∧1=1∧0=0,1∧1

7、=1[∧运算是取最小]（3）设MR是n×p，MS是p×m阶的布尔矩阵，定义MR与MS的“布尔乘法”运算“·”,令MR·MS=MT=(tij)nm，则[“·”运算是先取最小，再取最大]二、求R∪S，R∩S，R·S关系矩阵(1)MR∪S=MR∨MS；(2)MR∩S=MR∧MS；(3)MR·S=MR·MS。三、闭包的运算(1)Mr(R)=MR∨MI；——r(R)=R∪I(2)Ms(R)=MR∨MRT；——s(R)=R∪R-1(