关系与序关系课件.ppt

《关系与序关系课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章关系与序关系关系的概念关系的表示关系的性质等价关系关系的运算偏序关系2.1关系的概念[例]设A={Alice,Bob,Tom},B={Algebra,Graphs,Sets}Alice选修了Graphs,Bob选修了Algebra,Graph和Sets;Tom选修了Algebra,Graphs;R={,,,,,}AB,表示了学生集合A与课程集合B之间的选修关系。2.1关系的概念[二元关系的一般性描

2、述]一对对象之间的关系称为二元关系。[例]teachers={a,b,c}，students={x,y,z}建立教学关系T:aTxiffaTEACHINGx用序偶集合表示为：T={,,,,}Tteachersstudents图示为：2.1关系的概念[例]Subroutines={a,b,c,d,e}子程序间调用关系图示为：Calling={,,,,,,,}CallingSubroutinesSubroutines2.

3、1关系的概念[二元关系的集合定义]设X,Y是两个集合，XY的任何一个子集R都确定了一种二元关系，称为从X到Y的二元关系。R可记为xRy，显然RXYR可记为xRy当X=Y即X与Y同一时，称R为X上的一个二元关系。2.1关系的概念[例]F={

4、x是y的父亲}S={

5、x,y为正整数且x可整除y}T={

6、y为实数}对上述的：x，y，R，有R或R，二者必居其一。2.1关系的概念[定义域]设二元关系S。由S的所有对象x组成的集合称为S的定义域，记为Dom(S)。[值

7、域]由S的所有对象y组成的集合称为S的值域，记为Ran(S)(Range(S))。记F(S)=D(S)R(S)，称为S的域。描述：Dom(S)={x

8、(y)(S)}Ran(S)={y

9、(x)(S)}2.1关系的概念若干特殊关系：①X到Y的全域关系：Ex,y=XY特别地：Ex,x=XX②空关系：③恒等关系：Ix={

10、xiX}[例]设X={1,2,3,4}，求X上的关系“>”(大于)及其定义域、值域。2.2关系的表示方法(1)集合表示法借用集合的各种描述方法对表示关系的序偶集合进行描述(2)关

11、系矩阵设X={x1,x2,…,xm}，Y={y1,y2,…,yn}，m,n<+R是X到Y的二元关系。构造矩阵MR=[mij]mn，mij=R0其它2.2关系的表示方法[例]非0行对应元素构成D(S)非0列对应元素构成R(S)2.2关系的表示方法(3)关系图表示法用结点表示X、Y上的元素；若R则从结点x到结点y画一条弧。[例]上述Teaching关系的关系图：2.2关系的表示方法[例]设X={1,2,3,4}，X上的关系“>”：2.3关系的性质[定义]设R是X上的二元关系，则：①R是自反的(x)(xXxRx)②R是

12、对称的(x)(y)(x,yXxRyyRx)③R是传递的(x)(y)(z)(x,y,zXxRyyRzxRz)④R是反自反的(x)(xX¬(xRx))⑤R是反对称的(x)(y)(x,yXxRyyRxx=y)2.2关系的性质[习题]设X={1,2,3,4}，画出X上的关系“>”，“”和整除“

13、”的关系图和关系矩阵，并判断其性质。[习题]集合上的”isanelement”以及”isasubset”具有什么性质？2.3关系的性质[例]正整数集合上的若干关系及其性质整除=≤＜自反性对称性传递性

14、反自反性反对称性判定关系“＜”的反对称性的前提条件总为F,反对称性成立。2.3关系的性质从关系矩阵和关系图看关系的性质：R是自反的：MR的对角元均为1；关系图为自环图。R是对称的：MR为对称矩阵；关系图中弧成对出现。R是反自反的：MR的对角元均为0；关系图为无自环图。R是反对称的：MR为反对称矩阵；关系图中只出现单向弧。2.3关系的性质存在着既非自反也非反自反的关系，如：存在着既对称又反对称的关系，如：2.3关系的性质存在着既非对称又非反对称的关系，如：2.4集合的划分与覆盖[定义]给定集合S，A={A1,A2,…,An}，AiS

15、，i=1..n。②若①成立且AiAj=(若ij)，则说A是S的一个划分，并称A1,A2,