《关系与序关系》PPT课件

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

1、离散数学引论集合论与图论第二章关系与序关系2.1关系的概念[二元关系的一般性描述]一对对象之间的关系称为二元关系。[例]teachers={a,b,c}，students={x,y,z}建立教学关系T:aTxiffaTEACHINGx用序偶集合表示为：T={,,,,}Tteachersstudents图示为：2.1关系的概念[例]Subroutines={a,b,c,d,e}子程序间调用关系Calling={,,,,,

2、,,}CallingSubroutinesSubroutines图示为：2.1关系的概念[二元关系的集合定义]任何一个序偶的集合R={

3、xXyY}都确定了一种二元关系，称为从X到Y的二元关系。R可记为xRy，显然RXYR可记为xRy当X=Y（即X与Y同一）时，称上述R为X上的一个二元关系。从X到Y的任何二元关系，都可用一个序偶集合来表示：R={

4、xXyYxRy}2.1关系的概念[例]F={

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

6、,y>

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

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

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

10、(

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

12、xiX}[例]设X={1,2,3,4}，求X上的关系“>”(大于)及其定义域、值域。2.2关系的表示方法(1)集合表示法借用集合的各种描述方法对表示关系的序偶集合进行描述(2)关系矩阵设X={x1,x2,…,xm}，Y={y1,y2,…,yn}，m,n<+R是X到Y的二元关系。称矩阵MR=[mij]mn，mij=R0其它为X到Y的关

13、系矩阵。2.2关系的表示方法[例]非0行对应元素构成Dom(S)非0列对应元素构成Ran(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是对称的(x)(y)(x,yXxRyyRx)③R是传递的(x)(y)(z)(x,y,zXxRy

14、yRzxRz)④R是反自反的(x)(xX¬(xRx))⑤R是反对称的(x)(y)(x,yXxRyyRxx=y)2.3关系的性质[例]整数集合上的若干关系及其性质整除=≤＜自反性对称性传递性反自反性反对称性判定关系“＜”的反对称性的前提条件总为F,理论上反对称性成立。2.3关系的性质存在着既非自反也非反自反的关系，如：存在着既对称又反对称的关系，如：2.3关系的性质存在着既非对称又非反对称的关系，如：2.3关系的性质从关系矩阵和关系图看关系的性质：R是自反的：

15、MR的对角元均为1；关系图为自环图。R是对称的：MR为对称矩阵；关系图中弧成对出现。R是反自反的：MR的对角元均为0；关系图为无自环图。R是反对称的：MR为反对称矩阵；关系图中只出现单向弧。2.3关系的性质[例]在正整数上定义关系R：Riffx和y的最大公因子是1。讨论R的关系性质。[解]自反性：<2,2>的最大公因子是2，故<2,2>R即R非自反；对称性：成立；传递性：<2,1>R且<1,2>R但<2,2>R即R非传递；反对称性：<2,1>R且<1,2>R故R非反对称。2.4集合的划分与覆盖[定

16、义]给定集合S,A={A1,A2,…,An},AiS,i=1..n。若①成立且对于ij，有AiAj=，则说A是S的一个划分，并称A1,A2,…,An为此划分的块。从定义看，给定集合S的划分与覆盖都是S的幂集的子集。划分是一种特殊的覆盖，但覆盖不一定形成划分。2.4集合的划分与覆盖[例]自然数集合N={0,1,