离散数学(第11讲)

1、冯伟森Email138081922758/6/2022离散数学计算机学院8/6/20221计算机科学与工程学院主要内容1、关系的定义2、关系的表示3、关系的性质8/6/20222计算机科学与工程学院第五章 二元关系 在第三章我们讨论了集合及其元素，本章讨论集合中元素之间的关系。关系是表征事物的结构及其内在联系。 研究事物结构,主要是研究关系。关系的概念应用广泛,在计算机科学中起着重要的作用,如数据结构,数据库,数字逻辑,情报检索,算法分析,编译,人工智能等领域它都是很重要的数学工具。8/6/20223计算机科学与工程学院51 二元关系及其表示1、关系的定义 关系是一

2、个基本的概念,通俗地说,所谓关系,是指对象之间的相互联系,它表征事物的结构。如自然界中的“引力关系”,人与人之间的“父子关系”,“上下级关系“,”同志关系”,“同学关系”,对象间的“位置关系”,两个数间的“大于”,“等于”,“整除关系”,两个变量之间的“函数关系”,计算机部件间的“联结关系”,程序间的“调用关系”,8/6/20224计算机科学与工程学院定义5-1.1设A1,A2,An为n个非空集合，称A1A2An的任意子集R为以A1A2An为基的n元关系。特别：当R时，则称R为空关系；当RA1A2An时，则称R为全关系。由于A1A2An的任何子集都是一个n元关系，按照子集的定义，A1A2An共

3、有2|A1A2An|个不同的子集。因此，以A1A2An为基的不同关系共有2|A1A2An|个。8/6/20225计算机科学与工程学院例51在数据库中，常将用表格的方式表示出来的文件看作是关系R，如下表是一个学生学籍管理的一个数据库：则此时有关系RA1A2A6，其中系别与班级A1学号A2姓名A3性别A4年龄A5籍贯A694081-11王雷男18四川94081-13李华男19江苏94081-22张江男17北京94082-14赵小容女18云南94082-22陈涛男19广东94082-31黄静女19山东8/6/20226计算机科学与工程学院二元关系定义5-1.2设A，B为两个集合，AB的任何一个子集R

4、所定义的二元关系称为从A到B的二元关系，简称关系。如R是从A到A的二元关系，则称R为A上的二元关系。设有一序偶：R，常把这一事实记为xRy，读作“x对y有关系R”。如R，则记为xRy，读作“x对y没有关系R”。由于任何AB的子集都是一个二元关系，按照子集的定义，知AB共有2|A|B|个不同的子集。因此，从A到B不同的关系共有2|A|B|个。8/6/20227计算机科学与工程学院关系的表示法1.集合表示法由于关系也是一种特殊的集合，所以集合的两种基本的表示法也可以用到关系的表示中。即可用枚举法和叙述法来表示关系。例5.2设A2,B3,关系R如定义集合N上的“小于等于”关系：R|(x,yN)(xy

5、)。8/6/20228计算机科学与工程学院2.关系图法设Aa1,a2,a3,.,an,Bb1,b2,b3,.,bm，R是设a1,a2,a3,.,an和b1,b2,b3,.,bm分别为图中的节点，用“。”表示；如R,则从ai到bj可用一有向边aibj相连。为对应图中的有向边。从A到B的一个二元关系，则对应于关系R之关系图有如下规定：如R是定义在A上的关系，则对应于关系R有如下规定：设a1,a2,.,an为图中节点，用“。”表示。如R,则从ai到aj可用一有向边aiaj相连。为对应图中的有向边；如R,则从ai到ai用一带箭头的小圆环表示ai 8/6/20229计算机科学与工程学院例5.3设A是六个

6、程序，考虑它们之间的一种调用关系R，如Pi可调用Pj,则有R,现假设R, 则此关系R的关系图如下：8/6/202210计算机科学与工程学院例5.42）设Aa1,a2,a3,a6是六个人，B1，2，3是三套房间，考虑A到B之间的一种住宿关系R，如ai住房间j,则有R,现假设：R,则此关系R的关系图如下：8/6/202211计算机科学与工程学院3.关系矩阵设Aa1,a2,a3,.,an，Bb1,b2,b3,.,bm，R是从A到B的一个二元关系， 称矩阵MR(rij)nm为关系R的关系矩阵或邻接矩阵，其中：显然，关系矩阵是布尔矩阵。注意 在写关系矩阵时，首先应对集合A和B中的元素进行排序，不同的排序

7、会得到不同的关系矩阵。当集合以枚举法表示时，如果没有对集合的元素排序，则默认枚举的次序为元素的排序。 8/6/202212计算机科学与工程学院例5.5设A2，3，4，B1，2，4。考虑从A到B的“大于等于”关系R和“小于等于”关系S：R,，S,。写出R，S的关系矩阵。解：8/6/202213计算机科学与工程学院52 关系的性质1、自反性与反自反性定义5-1.3 设R是集合A上的二元关系，对任意的xA,都满足R，则称R是自反的，或称R具有自反性，即R在A上是自反的(x)(xA)(R)=1对任意的xA,都满足R，则称R是反自反的，或称R具有反自反性，即R在A上是反自反的(x)(xA)(R)=1 o

8、r (x)(xA)(R)=08/6/202214计算机科学与工程学院例5.5设A=a,b,c,d， R=,。因为A中每个元素x，都有R，所以R是自反的。R的关系图R的关系矩阵8/6/202215计算机科学与工程学院例5.5(续1)S=,。S的关系图S的关系矩阵因为A中每个元素x，都有S，所以S是反自反的。8/6/202216计算机科学与工程学院例5.5(续2)T=,。因为A中有元素b，使T，所以T不是自反的；因为A中有元素a，使T，所以T不是反自反的。T的关系图T的关系矩阵8/6/202217计算机科学与工程学院结论任何不是自反的关系未必一定是反自反的关系，反之亦然。即存在既不是自反的也不是反

9、自反的关系。表现在关系图上：关系R是自反的，当且仅当其关系图中每个结点都有环；关系R是反自反的，当且仅当其关系图中每个结点都无环。表现在关系矩阵上：关系R是自反的，当且仅当其关系矩阵的主对角线上全为1；关系R是反自反的当且仅当其关系矩阵的主对角线上全为0。 8/6/202218计算机科学与工程学院对称性与反对称性定义5-1.4 设R是集合A上的二元关系，对任意的x,yA，如果R，那么R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的 (x)(y)(xA)(yA)(R)(R)=1对任意的x,yA，如果R且R，那么x=y，则称关系R是反对称的，或称R具有反对称性，即R在A上是反对称的 (

10、x)(y)(xA)(yA)(R)(R)(x=y)=18/6/202219计算机科学与工程学院例5.6设A=a,b,c,d， R1=,R2=, R1的关系图R1的关系矩阵是对称的是反对称的R2的关系图R2的关系矩阵8/6/202220计算机科学与工程学院例5.6(续1)R3=,R4=, 既不是对称的，也不是反对称的R3的关系图R3的关系矩阵既是对称的，也是反对称的R4的关系图R4的关系矩阵8/6/202221计算机科学与工程学院结论任何不是对称的关系未必一定是反对称的关系，反之亦然。即存在既不是对称的也不是反对称的关系，也存在既是对称的也是反对称的关系。表现在关系图上：关系R是对称的当且仅当其关

11、系图中，任何一对结点之间，要么有方向相反的两条边，要么无任何边；关系R是反对称的当且仅当其关系图中，任何一对结点之间，至多有一条边。表现在关系矩阵上：关系R是对称的当且仅当其关系矩阵为对称矩阵，即rij=rji，i,j=1,2, ,n；关系R是反对称的当且仅当其关系矩阵为反对称矩阵，即rijrji=0，i,j=1,2,n，ij。 8/6/202222计算机科学与工程学院传递性定义5-1.4 设R是集合A上的二元关系，对任意的x,y,zA，如果R且R，那么R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的(x)(y)(z)(xA)(yA)(zA)(R)(R)(R)=1 8/6/2022

12、23计算机科学与工程学院例5.7模运算 mod： n mod d为d除n的余数 n mod d =j 读为“n 模 d 余j” 如果整数m和整数n关于模d的余数相同，称m和n（关于模d）是同余的，写为nm(mod d)xRy xy(mod m) m为确定的整数R是对称的、自反的、传递的关系，但不是反自反的和反对称的8/6/202224计算机科学与工程学院结论表现在关系图上：关系R是传递的当且仅当其关系图中，任何三个结点x,y,z（可以相同）之间，若从x到y有一条边存在，从y到z有一条边存在，则从x到z一定有一条边存在。表现在关系矩阵上：关系R是传递的当且仅当其关系矩阵中，对任意i,j,k1,2

13、,3,n，若rij=1且rjk=1，必有rik=1。8/6/202225计算机科学与工程学院53 关系的运算设R，S都是集合A到B的两个关系，则：RS|(xRy)(xSy)RS|(xRy)(xSy) R-S=|(xRy)(xSy)|(xRy) RS= |RSRS 1、关系的交、并、补、差运算根据定义，由于AB是相对于R的全集，所以AB-R,且RAB,R。8/6/202226计算机科学与工程学院例5.8设Aa,b,c,B1,2，R,，S,，则：RSRSR-S,，；,；,AB-R。8/6/202227计算机科学与工程学院关系的复合运算设R是一个从集合A到集合B的二元关系，S是从集合B到集合C的二元

14、关系(也可简单地描述为R：AB，S：BC)，则R与S的复合关系（合成关系）RS是从A到C的关系，并且：RS|(xA)(zC)(y)(yB)(xRy)(ySz)运算“”称为复合运算。8/6/202228计算机科学与工程学院复合关系的矩阵表示 R与S的复合关系（合成关系）RS也可以用矩阵来表示。 设R，S都是集合A= a1，a2，a3，.，an上的二元关系，MR(rij)， MS(sij)， =(mij)则 =MR*MS 这里的“*”运算类似矩阵乘法运算，但须将元素间的乘法改成逻辑与，将加法改成逻辑或，即 mij=(ri1s1j)(ri2s2j) (rinsnj)8/6/202229计算机科学与工

15、程学院例5.9设R,S,，分别是定义为从AB和从BC的关系，其中ABC1,2,3,4。1).用集合方法求RS，SR，RR，SS。则：RS,；SR,；RR,；SS,。8/6/202230计算机科学与工程学院例5.10 RSR。SABCAC1。1。11。12。2。22。23。3。33。34。4。44。42).用关系图求RS。3).用关系矩阵求RS。MRS MR* MS*8/6/202231计算机科学与工程学院关系的幂定义5-1.5设R是集合A上的二元关系，则可定义R的n次幂Rn（n0），该Rn也是A上的二元关系，定义如下：1.R0IA|aA；2.R1R ；3.Rn+1RnRRRn。容易证明，RmRnRm+n,(Rm)nRmn。8/6/202232计算机科学与工程学院关系的逆运算定义5-1.6设R是一个从集合A到集合B的二元关系，则从B到A的关系R-1|R称为R的逆关系,运算“-1”称为逆运算。注意：关系是一种集合，逆关系也是一种集合，因此，如果R是一个关系，则R-1和都是关