离散数学二元关系

《离散数学二元关系》由会员分享，可在线阅读，更多相关《离散数学二元关系（107页珍藏版）》请在金锄头文库上搜索。

1、计计算算机机科科学学学学院院 刘刘 芳芳2024/7/211第第7章章 二元关系二元关系7.1有序对与笛卡儿积有序对与笛卡儿积7.2二元关系二元关系7.3关系的运算关系的运算7.4关系的性质关系的性质7.5关系的闭包关系的闭包7.6等价关系和划分等价关系和划分7.7偏序关系偏序关系计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2127.1 有序对与笛卡尔积有序对与笛卡尔积7.1.1有序对的定义有序对的定义7.1.2集合的笛卡尔积集合的笛卡尔积7.1.3有序有序n元组和元组和n阶笛卡尔积阶笛卡尔积计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2137.1.1 有序对的定义有序对的

2、定义定义定义7.1：两个元素两个元素x,y组成的有序序列组成的有序序列x,y，称为一个有序称为一个有序对（序偶、二元组）。对（序偶、二元组）。例：例：直角坐标系中点的坐标直角坐标系中点的坐标x,y日期的表示：日期的表示：y,m计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2147.1.1 有序对的定义有序对的定义性质：性质：当当xy时，时，x，yy，xx，yu，vxuyv例例7.1：，求，求x,y。解解：x25,2xy4x3,y 2计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2157.1.2 集合的笛卡尔积集合的笛卡尔积定义定义7.2：集合集合A与与B的笛卡儿乘积的笛卡儿乘积

3、 ABx,y|x A y B例：例：设设Aa , b，B 0，1，2，C，计算计算AB，BA，AC，AA。解：解： ABa,0,a,1,a,2, b,0,b,1,b,2BA0,a,0,b, 1,a,1,b, 2,a,2,bAC AA a,a,a,b,b,a,b,b（AA可记作可记作A2 ）例例7.2：A = = 1，2, , 求求P( (A) ) A。 计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2167.1.2 集合的笛卡尔积集合的笛卡尔积集合的笛卡儿积的性质集合的笛卡儿积的性质：性质性质1：若若|A|m,|B|n,则则|A B|mn性质性质2：对任意集合：对任意集合A，有：有：A

4、A性质性质3：一般地：一般地ABBA，即笛卡儿乘积不满足，即笛卡儿乘积不满足交换律。交换律。问题问题：什么情况下什么情况下ABBA？（ABAB）什么情况下什么情况下ABBA？（ABAB）计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2177.1.2 集合的笛卡尔积集合的笛卡尔积例例3：设设Aa，b，B1，2，3，Cp，q，计算计算(AB)C，A(BC)。解：解：(AB) C,p,q, ,p,q, ,p,q,p,q, ,p,q, ,p,q 。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2187.1.2 集合的笛卡尔积集合的笛卡尔积A(B C) a,a, a,a, a,a, b,

5、b, b,b, b,b,集合的笛卡儿积的性质集合的笛卡儿积的性质性质性质4：一般地：一般地(AB)CA(BC)，即集合的笛卡儿积不满足结即集合的笛卡儿积不满足结合律。合律。性质性质5：A C B D AB CD计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2197.1.2 集合的笛卡尔积集合的笛卡尔积性质性质6：笛卡儿积对笛卡儿积对、运算满足分配律运算满足分配律A（BC）（AB）（AC）A（BC）（AB）（AC）（AB）C（AC）（BC）（AB）C（AC）（BC）计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21107.1.2 集合的笛卡尔积集合的笛卡尔积证明：证明：A（BC）

6、（）（AB）（AC）证证：任取：任取x，yx，yA（BC） xAyBCxA（yB yC ）（xAyB） （xA yC ）（x，yAB） （x ，yAC ）x，y（AB） （AC ）所以，所以，A（BC）（AB）（AC）成立。成立。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21117.1.2 集合的笛卡尔积集合的笛卡尔积证明：证明：（AB）C（AC）（BC）证证：任取任取x，yx，y （AB）Cx（A B） yCxAxB yC（xAyC） （xB yC ）（x，yAC） （x ，yBC ）x，y （AC）（BC）所以，所以， （AB）C（AC）（BC）成立。成立。计计算算机机科科学学

7、学学院院 刘刘 芳芳2024/7/21127.1.3 有序有序 n 元组和元组和 n 阶笛卡尔积阶笛卡尔积定义定义：n个元素个元素x1，x2，xn组成的有序序列组成的有序序列,记做：记做：x1,x2,xn称为称为n重组（重组（n元序偶、元序偶、n元组）元组）。约定约定:x1，x2，, xn-1,xn=,xn性质：性质：x1,x2,xn y1,y2,ynxi yi(i=1,2,n)计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21137.1.3 有序有序 n 元组和元组和 n 阶笛卡尔积阶笛卡尔积定义定义4.4：集合集合A1、A2、An的笛卡儿乘积的笛卡儿乘积A1A2Anx1，x2，xn

8、 | xiAi i1,2,n注意注意：A1A2An1An （A1A2An1 ） An一般地：一般地：若若A1A2An A时，上式简记为：时，上式简记为：An计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21147.2 二元关系二元关系7.2.1二元关系的基本定义二元关系的基本定义7.2.2二元关系的表示二元关系的表示计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21157.2.1 二元关系的基本定义二元关系的基本定义关系关系数的数的,关系关系;VI R;计算机程序的输入与输出联系；计算机程序的输入与输出联系；数据库的数据特性联系等。数据库的数据特性联系等。集合论为刻划这种联系提

9、供了一种数学模型集合论为刻划这种联系提供了一种数学模型关系关系(Relation)。计计算算机机科科学学学学院院 刘刘 芳芳7.2.1 二元关系的基本定义二元关系的基本定义定义定义7.3如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1）集合非空）集合非空,且它的元素都是有序对且它的元素都是有序对（2）集合是空集）集合是空集则称该集合为一个二元关系则称该集合为一个二元关系,简称为关系，记作简称为关系，记作R.例如：例如：R,S,3,4.2024/7/2116计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21177.2.1 二元关系的基本定义二元关系的基本定义例例:(1)R

10、|x,y N,xy3,(2)C|x,y R,x2y21(3)R|x,y,z R,x2yz3(4)5元关系的实例元关系的实例数据库实体模型数据库实体模型员工号员工号姓名姓名年龄年龄性别性别工资工资301302303张张林林王晓云王晓云李鹏宇李鹏宇504347男男女女男男160012501500计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21187.2.1 二元关系的基本定义二元关系的基本定义定义定义7.4设设A,B为集合为集合,R AB，称称R为为A到到B的二元关系；的二元关系；R AA，称称R为为A上的关系。上的关系。例：例：若若Aa,b,B1,则：则：（1）写出）写出A到到B的所有

11、二元关系。的所有二元关系。（2）写出）写出A上的所有二元关系。上的所有二元关系。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21197.2.1 二元关系的基本定义二元关系的基本定义一般地：一般地：若若|A|m,|B|n|AB|mn,AB的子集有的子集有2mn个个,从从A到到B有有2mn个不同的二元个不同的二元关系关系.R，称称R为为空空关系；关系；RAB，称称R为为全域全域关系关系若若|A|n|AA|n2,AA的子集有的子集有2n2个个,A上有上有2n2不同的二元关系不同的二元关系.R，称称R为为A上上空空关系关系RAA，称称R为为A上的上的全域全域关系，记做关系，记做EA;R|xA

12、 ，称称R为为A上的上的相等相等关系，记做关系，记做IA;计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21207.2.1 二元关系的基本定义二元关系的基本定义常见的几种特殊的二元关系常见的几种特殊的二元关系|集合之间的关系集合之间的关系： 计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21217.2.2 二元关系的表示二元关系的表示1.集合表示法集合表示法2.关系矩阵关系矩阵(matrix of relation)设设Aa1,a2,am，Bb1,b2,bn，R是是A到到B的一个二的一个二元关系，令：元关系，令：称：称：MR为为R的的关系矩阵关系矩阵。计计算算机机科科学学学学院

13、院 刘刘 芳芳2024/7/21227.2.2 二元关系的表示二元关系的表示例例1：设设Aa,b,c,B0,1,2,3,R,写写出出MR。0001c0100b0010a3210 MR计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21237.2.2 二元关系的表示二元关系的表示例例2：设设A1,2,3,4,A上的关系上的关系R,4,2,写出写出MR。123411100200113000040100MR计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21247.2.2 二元关系的表示二元关系的表示例例3设设A1,2,3,4,A上的二元关系上的二元关系R|xy,写出写出MR。12341

14、1000211003111041111MR计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21257.2.2 二元关系的表示二元关系的表示3.关系图关系图R为为A到到B的二元关系；的二元关系；以以AB的每个元素为一个结点，对每个的每个元素为一个结点，对每个R，均连一条从结点均连一条从结点x到到y的有向边，得到一个有向图，称的有向边，得到一个有向图，称为为R的关系图的关系图，记为，记为GR。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21267.2.2 二元关系的表示二元关系的表示例例1设设Aa,b,c,B0,1,2,3,R,画出画出GR。abc0123计计算算机机科科学学学学院

15、院 刘刘 芳芳2024/7/21277.2.2 二元关系的表示二元关系的表示例例2设设A1,2,3,4,A上的二元关系上的二元关系R|xy,画出画出GR。1243计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21287.2.2 二元关系的表示二元关系的表示练习：练习：Aa, b, c, d,R,求求R的关系矩阵的关系矩阵MR和关系图和关系图 GR。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21297.2.2 二元关系的表示二元关系的表示关系的表示方法关系的表示方法关系关系R的集合表达式的集合表达式关系矩阵关系矩阵MR关系图关系图GR三者均可以唯一相互确定。三者均可以唯一相互

16、确定。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21307.3 关系的运算关系的运算7.3.1关系的定义域、值域关系的定义域、值域和和域域7.3.2关系的逆关系的逆7.3.3关系的右复合关系的右复合7.3.4关系运算的性质关系运算的性质7.3.5关系的幂关系的幂计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21317.3.1 关系的关系的定义域、值域定义域、值域 和和 域域定义定义7.6：dom（R）= x| y（xRy）ran（R） = y| x（xRy）fld（R）=dom（R） ran（R） 例：例：设设Ra,1,b,2,a,3计算计算dom（R）,ran（R）,域域

17、fld（R）计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21327.3.2 关系的逆运算关系的逆运算定义定义7.7关系关系R的逆关系的逆关系R-1=|xRy例：例：R,则：则：R-1,问题：问题：已知已知MR，如何计算如何计算MR-1?已知已知GR，如何计算如何计算GR-1?计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21337.3.3 关系的右复合关系的右复合定义定义7.8关系关系F,G的右复合的右复合关系复合的求解方法关系复合的求解方法集合表达式集合表达式图示法图示法关系矩阵关系矩阵计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21347.3.3 关系的右复合关

18、系的右复合例：例：R=,S=,法法1：R S=S R=, ,法法2：利用图示方法求合成利用图示方法求合成计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21357.3.3 关系的右复合关系的右复合法法3：关系矩阵相乘的方法关系矩阵相乘的方法一般地一般地：设设:A=a1 , a2 , , am B=b1 , b2 , , bp C=c1 , c2 , , cn R是是A到到B的一个二元关系，的一个二元关系，S是是B到到C的一个二元关系，的一个二元关系，RS是是A到到C的一个二元关系的一个二元关系，计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21367.3.3 关系的右复合关系的右

19、复合则：则：MR ( rij )mp MS ( sij )pn MR S ( tij )mn计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2137MRMsMRSabc11102001pqa10b10c01pq1102017.3.3 关系的右复合关系的右复合例例1：计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21387.3.4 关系运算的性质关系运算的性质定理定理7.1设设F是任意的关系是任意的关系,则则(1)(F 1) 1F(2)domF 1ranF,ranF 1domF证明：证明：(1)任取任取,由逆的定义有由逆的定义有 (F 1) 1F 1F所以有所以有(F 1) 1F(

20、2)任取任取xdomF 1 y(F 1) y(F)xranF所以有所以有domF 1ranF.同理可证同理可证ranF 1domF.计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21397.3.4 关系运算的性质关系运算的性质定理定理7.2设设F,G,H是任意的关系是任意的关系,则则(1)(F 。G)。H=F 。(G 。H)证明：证明：任取任取, (F G) H t (F GH) t ( s (FG)H) t s (FGH) s (F t (GH) s (FG H)F (G H)所以所以(F G) H =F (G H)计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21407.3

21、.4 关系运算的性质关系运算的性质定理定理7.2设设F,G,H是任意的关系是任意的关系,则则(2)(F 。G) 1= G 1。F 1证明：证明：任取任取,(F G) 1F G t (F(t,x)G) t (G 1(t,y)F 1)G 1 F 1所以所以(F G) 1= G 1 F 1计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21417.3.4 关系运算的性质关系运算的性质定理定理7.3设设R为为A上的关系上的关系,则则 R IA=IA R=R例：例：设设A1,2,3,4，A上的二元关系上的二元关系R=,，求：，求：R IAIA R计计算算机机科科学学学学院院 刘刘 芳芳2024/7

22、/21427.3.5 关系的幂关系的幂定义定义7.10：若若R是是A上二元关系上二元关系, ,Rn( (nN) 定义如下：定义如下：R0IARn+1 RnR问题：问题：给定集合给定集合A和和A上的关系上的关系R，如何计算如何计算Rn （nN） ? 计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21437.3.5 关系的幂关系的幂例：设例：设Aa,b,c,d,R,求求Rn。方法方法1：按照定义求解：按照定义求解解：解：R0,R1,R2,R3,R4,R2R4R6R3R5R7计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21447.3.5 关系的幂关系的幂方法方法2：利用关系矩阵相乘

23、的方法：利用关系矩阵相乘的方法由于：由于：M4=M2,即即R4=R2.于是：可以得到于是：可以得到R2=R4=R6=,R3=R5=R7=计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21457.3.5 关系的幂关系的幂方法方法3：用关系图的方法得到用关系图的方法得到R0,R1,R2,R3,的关系图如下图所示的关系图如下图所示从关系图看幂Rn运算(n1)：1.从R的每个结点x出发，凡通过数n条边能到达的结点y，则有Rn。2.Rn，意味着关系图中从x到y存在长为 n的一条路径；计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21467.3.5 关系的幂关系的幂幂运算的性质幂运算的性质

24、引：鸽笼原理（抽屉原理）引：鸽笼原理（抽屉原理）若有若有n个鸽笼，个鸽笼，n1只鸽子，则至少有一个鸽笼里至少只鸽子，则至少有一个鸽笼里至少有两只鸽子。有两只鸽子。（将（将n1个物体放入个物体放入n个盒子里，则至少有一个盒子里个盒子里，则至少有一个盒子里有有2个或个或2个以上的物体。）个以上的物体。）计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21477.3.5 关系的幂关系的幂定理定理7.6：设设|A|n, R是是A上二元关系，则存在上二元关系，则存在s、t,使使RsRt(0st2n2)。证明：证明：R是是A上的关系，则对任意上的关系，则对任意k N，Rk AA。又又 |AA|n2|

25、( AA)|2n2，即即A上共有上共有2n2个不同的二元关系。个不同的二元关系。但：序列但：序列R0，R1，R2n2共有共有2n21项，项，因此因此,存在存在s,t N,使使Rs=Rt (0st2n2)。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21487.3.5 关系的幂关系的幂定理定理7.7：若若R是是A上二元关系，上二元关系，m,n N, ,则：则：1. Rm Rn Rmn2. (Rm) nRmn定理定理7.8：若若R是是A上二元关系，若存在自然数上二元关系，若存在自然数s,t(st)，使得使得RsRt , ,则：则：1.对任意对任意k N, Rs+k Rtk2.对任意对任意

26、k,i N, Rs+kp+i Rsi,其中其中p=ts。 3.令令S=R0,R1,Rt-1，则对任意，则对任意q N, Rq S.计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21497.4 关系的性质关系的性质7.4.1自反性和反自反性自反性和反自反性7.4.2对称性和反对称性对称性和反对称性7.4.3传递性传递性7.4.4关系性质的判定关系性质的判定计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21507.4.1 自反性和反自反性自反性和反自反性定义定义7.11：设设R为为A上的关系上的关系,(1)若若 x(xA R),则称则称R在在A上是上是自反自反的的.(2)若若 x(

27、xA R),则称则称R在在A上是上是反自反反自反的的.例例7.10：A =1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中R1 = ,R2=,R3=关系是自反（关系是自反（反自反反自反）的）的关系图中关系图中每个结点均有（每个结点均有（无无）环。）环。关系是自反（关系是自反（反自反反自反）的）的关系关系矩阵主对角线的元素全为矩阵主对角线的元素全为1（0）自反性与反自反性是互斥的，但不互补。自反性与反自反性是互斥的，但不互补。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21517.4.2 对称性和反对称性对称性和反对称性定义定义7.12：设设R为为A上的关系上的关系,(1)

28、若若 x y(x,yARR),则称则称R为为A上上对称对称的关系的关系.(2)若若 x y(x,yARRx=y), x y(x,yAR xy R), 则称为则称为A上的上的反对称反对称关系关系.例例7.11设设A1,2,3,R1,R2,R3和和R4都是都是A上的关系上的关系,其中其中R1,，R2,R3,，R4,计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21527.4.2 对称和反对称性对称和反对称性注意：注意：从关系图判断从关系图判断关系是对称的关系是对称的关系图两关系图两结点若有边，则一定是结点若有边，则一定是双向的，即方向相反的一对有向边。双向的，即方向相反的一对有向边。关系是

29、反对称的关系是反对称的关系图中两关系图中两结点之间若有边结点之间若有边，则则一定为单向的。一定为单向的。从关系矩阵判断从关系矩阵判断关系是对称的关系是对称的关系关系矩阵关于主对角线对称。矩阵关于主对角线对称。关系是反对称的关系是反对称的对任意的对任意的i,j,(ij),rij1rji0。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21537.4.3 传递性传递性例例7.12设设A1, 2, 3,R1,R2,R3是是A上的关系上的关系,其中其中R1,R2,R3定义定义7.13：设设R为为A上的关系上的关系,若若 x y z(x,y,zARRR),则称则称R是是A上的上的传递传递关系关系

30、.关系是传递的关系是传递的关系图中若两关系图中若两结点之间至少有两条边相连，则一定存在捷径。结点之间至少有两条边相连，则一定存在捷径。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21547.4.4 关系性质的判定关系性质的判定自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性表达式表达式IA RRIA=R=R 1RR 1 IAR R R关系矩关系矩阵阵主对角主对角线元素线元素全是全是1主对角线主对角线元素全是元素全是0矩阵是对称矩阵是对称矩阵矩阵若若rij1,且且ij,则则rji0对对M2中中1所所在位置在位置,M中相应位置中相应位置都是都是1关系图关系图每个顶每个

31、顶点都有点都有环环每个顶点每个顶点都没有环都没有环如果两个顶如果两个顶点之间有边点之间有边,一定是一对一定是一对方向相反的方向相反的边边(无单边无单边)如果两点之如果两点之间有边间有边,一定一定是一条单向是一条单向边边(无双向边无双向边)如果顶点如果顶点xi到到xj有边有边,xj到到xk有边有边,则则从从xi到到xk也也有边有边计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21557.4.4 关系性质的判定关系性质的判定例例7.14:判断下图中关系的性质判断下图中关系的性质,并说明理由并说明理由(3)自反自反，不是反自反；，不是反自反；反对称反对称，不是对称；不传递，不是对称；不传递.

32、(1)(2)(3)(1)不自反也不反自反；不自反也不反自反；对称对称,不反对称；不传递不反对称；不传递.(2)不是自反；不是自反；反自反反自反；反对称反对称,不是对称；不是对称；传递传递.计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21567.4.4 关系性质的判定关系性质的判定思考：思考：设设Aa,b,c，试给出试给出A上的一个二元关系上的一个二元关系R，使其同使其同时不满足自反性、反自反性、对称性、反对称性和传时不满足自反性、反自反性、对称性、反对称性和传递性递性(要求画出要求画出R的关系图的关系图)。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21577.5 关系的闭

33、包关系的闭包7.5.1闭包的定义闭包的定义7.5.2闭包的构造方法闭包的构造方法计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21587.5.1 闭包的定义闭包的定义定义定义7.14（闭包（闭包)设设R为为A上的二元关系，如果上的二元关系，如果A上的二元关系上的二元关系R，使：使：1.R R；2.R是是自反的自反的（对称的对称的或或传递的传递的）；3.对对A上的任何关系上的任何关系R”，如果如果R R”,且且R”自反自反（对称对称或或传递传递）,必有必有R R”；则称则称R为为R的的自反自反（对称对称或或传递传递）闭包。）闭包。记做：记做：r(R)（ s(R)或或t(R)）计计算算机机

34、科科学学学学院院 刘刘 芳芳2024/7/21597.5.1 闭包的定义闭包的定义例：例：Aa,b,c,d,R,求求r(R),s(R),t(R)。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21607.5.2 闭包的构造方法闭包的构造方法1.集合表达式集合表达式定理定理7.10设设R为为A上的二元关系，则：上的二元关系，则：(1)r（R）RR0（ R0 IA）(2)s（R）RR-1(3)t（R）RR2R3计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21617.5.2 闭包的构造方法闭包的构造方法（1） r（R）RI IA证明：令证明：令R RIA1.显然显然 R R ；2.

35、对任意对任意xA，有有 I IA, 当然当然 RI IA R， 故故R自反自反；3.设另有关系设另有关系R”也是自反的也是自反的，且且R R”，R”自反自反 I IA R”，又又R R”故：故： RI IA R” ，即即R R” 。所以说：所以说：r（R）RI IA。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2162(2) s（R）RR-1证明：令证明：令R R R-1-1i.显然显然 R R ；ii.对任意对任意 R R R R 1 1 R 1 1 R R R 1 1 R 故故R对称；对称； 7.5.2 闭包的构造方法闭包的构造方法计计算算机机科科学学学学院院 刘刘 芳芳2024

36、/7/2163iii.设另有关系设另有关系R也是对称的，且也是对称的，且R R，则对任意则对任意 R R R 1 1若若 R,由于由于R R 知知 R若若 R1 1,则则 R,由于由于R R,故有故有 R,而而R对称对称,于是于是 R。 R R所以说：所以说：s（R）R R-1。7.5.2 闭包的构造方法闭包的构造方法计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2164(3) t（R）R R2 R3 证明：令证明：令R R R2 R3 i.显然显然 R R ；ii.对任意对任意， R, 必必 k,j（k,j1,使使 Rk, Rj,于是于是 Rk Rj Rk+j R,即即 R故故R传递

37、；传递；7.5.2 闭包的构造方法闭包的构造方法计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2165iii.设另有关系设另有关系R也是传递的，且也是传递的，且R R，则对则对任意任意 R, ,必必 k(k1),使使 Rk k, ,显然存在序列：显然存在序列：xc0,c1,c2,cky,使：使：, R R由已知：由已知：R传递，故传递，故 R R R 因此因此t（R）R R2 R3 成立。成立。 即即 R R R RK个个7.5.2 闭包的构造方法闭包的构造方法计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21667.5.2 闭包的构造方法闭包的构造方法2.关系矩阵表示关系矩阵

38、表示设关系设关系R,r(R),s(R),t(R)的关系矩阵分别为的关系矩阵分别为M,Mr,Ms和和Mt ,则则Mr =M+E Ms =M+MTMt =M+M2+M3+3.关系图表示关系图表示计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21677.5.2 闭包的构造方法闭包的构造方法例例7.15设设A=a,b,c,d,R=,R和和r(R),s(R),t(R)的关系图如下图所示的关系图如下图所示.计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21687.6 等价关系和划分等价关系和划分7.6.1等价关系的定义等价关系的定义7.6.2等价类和商集等价类和商集7.6.3集合的划分集合

39、的划分7.6.4等价关系与划分的关系等价关系与划分的关系计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21697.6.1 等价关系的定义等价关系的定义定义定义7.15非空集合非空集合A上的二元关系上的二元关系R，如果如果R是是(1)自反的自反的(2)对称的对称的(3)传递的传递的称称R为为等价关系等价关系Equivalence Relations。若若R为一个等价关系，为一个等价关系，xRy，称为称为x等价于等价于y,记作：记作：xy。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21707.6.1 等价关系的定义等价关系的定义例例7.16A1,2,3,4,5,6,7,8上的关

40、系上的关系RR|x,yAxy(mod3)为为A上的一个等价关系。上的一个等价关系。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21717.6.1 等价关系的定义等价关系的定义模模m相等（同余）关系相等（同余）关系设设x，yA（A Z），），mZ+，如果如果xymk(kZ)，那么那么x与与y是模是模m相等，记为：相等，记为：xy(mod m)（或称（或称x和和y模模m同余）。同余）。一般地一般地非空集合非空集合A上的模上的模m同余关系同余关系 R|x,yAxy(mod m)是一个是一个等价关系等价关系。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21727.6.2 等价类和商

41、集等价类和商集定义定义7.16：等价类等价类设设R为非空集合为非空集合A上的等价关系上的等价关系, xA，令，令xR y|yAxRy称称xR为为x关于关于R的等价类的等价类,简称为简称为x的等价类的等价类,简记简记为为x.定义定义7.17:商集商集ARxR|xA计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21737.6.2 等价类和商集等价类和商集例：例：写出写出A1,2,3,4,5,6,7,8上的模上的模3等价关系的等价等价关系的等价类和商集。类和商集。则则: 1471,4,7 2582,5,8 363,6 AR 1,4,7 , 2,5,8 , 3,6计计算算机机科科学学学学院院

42、刘刘 芳芳2024/7/2174例例2Aa,b,c,d,e,f，A上的等价关系上的等价关系R的关系图如下：的关系图如下：bcadef则：则：abca,b,cded,effARa ,d , f7.6.2 等价类和商集等价类和商集计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21757.6.2 等价类和商集等价类和商集例例3R是是Z上的模上的模4等价关系，则：等价关系，则：0,8,4,0,4,8,1,7,3,1,5,9,2,6,2,2,6,10,3,5,1,3，7,11,ZR0,1,2,3计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21767.6.2 等价类和商集等价类和商集等价

43、类的性质等价类的性质定理定理7.14：设设R为非空集合为非空集合A上的等价关系，则上的等价关系，则计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21777.6.3 集合的划分集合的划分定义定义7.18：设设A为非空集合为非空集合,若若A的子集族的子集族 ( P(A)满足下面满足下面条件：条件：(1) (2) x y (x,y xyxy)(3) A 称称 是是A的一个的一个划分划分,称称 中的元素为中的元素为A的的划分块划分块.计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21787.6.3 集合的划分集合的划分问题问题1：设设Aa,b,c,d,给定给定 1, 2, 3, 4,

44、5, 6如下：如下： 1a,b,c,d 2a,b,c,d 3a,a,b,c,d 4a,b,c 5,a,b,c,d 6a,a,b,c,d其中其中 1和和 2是是A的划分的划分,其他都不是其他都不是A的划分的划分.计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21797.6.3 集合的划分集合的划分问题问题2A1,2,3，则集合则集合A的划分有几个？分别是什么？的划分有几个？分别是什么？ 11,2,3 22,1,3 33,1,2 41,2,3 51,2,3计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21807.6.4 等价关系与划分的关系等价关系与划分的关系等价关系与划分是一一对

45、应的关系等价关系与划分是一一对应的关系一方面：一方面：集合集合A上的一个等价关系上的一个等价关系R确定确定A的一个划分的一个划分,即即AR。另一方面：另一方面：集合集合A的一个划分，确定的一个划分，确定A上的一个等价关系上的一个等价关系R。任给任给A 的一个划分的一个划分 ,如下定义如下定义A 上的关系上的关系R： R |x,yAx 与与y 在在 的同一划分块中的同一划分块中R 为为A上的等价关系，上的等价关系，且该等价关系确定的商集就且该等价关系确定的商集就是是 .计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21817.6.4 等价关系与划分的关系等价关系与划分的关系例：例：若若A

46、a,b,c,d,e,f,A上的一个划分上的一个划分 a，b，c，d，e，f ，则：则：确定确定A上的一个等价关系上的一个等价关系。R , , bc adef计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21827.6.4 等价关系与划分的关系等价关系与划分的关系一般地：一般地：若若A上的划分上的划分A1,A2,Am。则则确定确定A上的一个等价关系上的一个等价关系R计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21837.6.4 等价关系与划分的关系等价关系与划分的关系问题问题3：设设A1，2，3（1）A上共有多少个不同的二元关系；上共有多少个不同的二元关系；（2）给出）给出A上

47、所有的等价关系。上所有的等价关系。分析：分析：p1 5分别对应于等价关系分别对应于等价关系R1 R5.其中其中:R1=,IAR2=,IAR3=,IAR4= =EAR5=IA计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21847.6.4 等价关系与划分的关系等价关系与划分的关系思考练习思考练习A1，2共有多少个二元关系，其中有几个是等价共有多少个二元关系，其中有几个是等价关系，请写出来。关系，请写出来。A1，2，3，4共有多少个二元关系，其中有几个共有多少个二元关系，其中有几个是等价关系，请写出来。是等价关系，请写出来。A1，2，3，4，5共有多少个二元关系，其中有几共有多少个二元关系

48、，其中有几个是等价关系，请写出来。个是等价关系，请写出来。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21857.7 偏序关系偏序关系7.7.1偏序关系及相关定义偏序关系及相关定义7.7.2哈斯图哈斯图7.7.3偏序集中的特殊元素偏序集中的特殊元素7.7.4调度问题调度问题计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21867.7.1偏序关系及相关定义偏序关系及相关定义定义定义7.19：R是非空集合是非空集合A上的二元关系，如果上的二元关系，如果R是：是：(1)自反的自反的(2)反对称的反对称的(3)传递的传递的则称则称R是是A上上偏序关系偏序关系(半序关系部分序关系半序关

49、系部分序关系),记作记作 。设设 为偏序关系为偏序关系,如果如果,则记作则记作x y,读作读作x“小小于或等于于或等于”y.计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21877.7.1偏序关系及相关定义偏序关系及相关定义实例实例:集合集合A上的恒等关系上的恒等关系IA 是是A上的偏序关系上的偏序关系.小于或等于关系小于或等于关系,整除关系和包含关系也是相应集合整除关系和包含关系也是相应集合上的偏序关系上的偏序关系.定义定义7.22：集合集合A连同连同A上的偏序关系上的偏序关系R一起称为一个一起称为一个偏序集偏序集，记为记为（或：或：）。）。计计算算机机科科学学学学院院 刘刘 芳芳2

50、024/7/21887.7.1偏序关系及相关定义偏序关系及相关定义定义定义7.20：设设R为非空集合为非空集合A上的偏序关系上的偏序关系,定义：定义： x, y A， x yx y xy x,y A,x与与y 可比可比x y y x.定义定义7.21：全序全序R为非空集合为非空集合A上的偏序上的偏序, x,y A,x与与y 都可比，则称都可比，则称R为全序（线序）关系。为全序（线序）关系。如：如：4268计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21897.7.1偏序关系及相关定义偏序关系及相关定义定义定义7.23：覆盖覆盖设设R为非空集合为非空集合A上的偏序关系上的偏序关系, x

51、,yA,如果如果x y且不存在且不存在z A使得使得x z y,则称则称y覆盖覆盖x。如：如：4268计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21907.7.2 哈斯图哈斯图偏序关系的表示方法偏序关系的表示方法1.关系矩阵关系矩阵不能明显看出二元关系的特征。不能明显看出二元关系的特征。2.关系图关系图比较烦琐比较烦琐3.简化的关系图简化的关系图哈斯图（哈斯图（ Hasse图）图）计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21917.7.2 哈斯图哈斯图例例1：A2，4，6，8，A上的二元关系：上的二元关系：Ra，ba|b，a,bA42684268简化简化计计算算机机科

52、科学学学学院院 刘刘 芳芳2024/7/21927.7.2 哈斯图哈斯图关系图关系图哈斯图：哈斯图：自反性：自反性：每个顶点都有自回路，省去。每个顶点都有自回路，省去。反对称性：反对称性：两个顶点间只可能有一个箭头两个顶点间只可能有一个箭头,从下从下上的方向从上的方向从小到大安置顶点，可省略箭头。小到大安置顶点，可省略箭头。传递性：传递性：若若y覆盖覆盖x，则在则在x和和y之间连一条线之间连一条线计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21937.7.2 哈斯图哈斯图例例2：画出画出1,2,9，R的哈斯图。的哈斯图。全序关系线序关系全序关系线序关系计计算算机机科科学学学学院院 刘

53、刘 芳芳2024/7/21947.7.2 哈斯图哈斯图例例3：画出画出1,2,3,4,5,6,7,8,9,R整除整除，P(a,b,c),R 的哈斯图。的哈斯图。计计算算机机科科学学学学院院 刘刘 芳芳练习练习1：已知偏序集已知偏序集的哈斯图如下图所示的哈斯图如下图所示,试求出集合试求出集合A和关系和关系R的表达式的表达式.2024/7/21957.7.2 哈斯图哈斯图A=a,b,c,d,e,f,g,hR=,IA 计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2196课堂练习课堂练习练习练习2：已知偏序集已知偏序集,的关系图如下，试将关系图改画的关系图如下，试将关系图改画成哈斯图。成哈斯

54、图。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2197课堂练习课堂练习练习练习3图示为偏序集图示为偏序集的哈斯图，试画出其关系图。的哈斯图，试画出其关系图。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/2198课堂练习课堂练习问题问题设设A=1,2，求，求A上的所有的偏序关系。上的所有的偏序关系。设设A=1,2,3，求，求A上的所有的偏序关系。上的所有的偏序关系。计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21997.7.3 偏序集中的特殊元素偏序集中的特殊元素定义定义7.24：设：设A,是偏序集是偏序集,B A,bB：若若 x(xBx b)成立，则称成立，则称b

55、为为B的的最大元最大元。若若 x(xBb x)成立，则称成立，则称b为为B的的最小元最小元。例例1：对偏序集合对偏序集合2,4,6,8，R整除整除分别写出如下集合的分别写出如下集合的最大元和最小元：最大元和最小元：2，4，6，82，4，82，4，64，6，84268计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21100例例2：对偏序集合对偏序集合1,2,3,4,5,6,7,8,9,R整除整除分别写分别写出如下集合的最大元和最小元：出如下集合的最大元和最小元：1,3,5,91,2,3,61,3,5,72,3,4,6,87.7.3 偏序集中的特殊元素偏序集中的特殊元素计计算算机机科科学学

56、学学院院 刘刘 芳芳2024/7/211017.7.3 偏序集中的特殊元素偏序集中的特殊元素定义定义7.24：设：设A,是偏序集是偏序集,B A,b B： x（xBb x），），则称则称b为为B的的极大元极大元。 x（xBx b ），），则称则称b为为B的的极小元极小元。例例1：对偏序集合对偏序集合2,4,6,8，R整除整除分别写出如下集合的分别写出如下集合的极大元和极小元：极大元和极小元：2，4，6，82，4，82，4，64，6，84268计计算算机机科科学学学学院院 刘刘 芳芳2024/7/21102例例2：对偏序集合对偏序集合1,2,3,4,5,6,7,8,9,R整除整除分别写分别写出如

57、下集合的极大元和极小元出如下集合的极大元和极小元：1,3,5,91,2,3,61,3,5,72,3,4,6,87.7.3 偏序集中的特殊元素偏序集中的特殊元素计计算算机机科科学学学学院院 刘刘 芳芳2024/7/211037.7.3 偏序集中的特殊元素偏序集中的特殊元素性质性质对于有穷集，极小元和极大元必存在，可能存在多个对于有穷集，极小元和极大元必存在，可能存在多个.最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.最小元一定是极小元；最大元一定是极大元最小元一定是极小元；最大元一定是极大元.孤立结点既是极小元，也是极大元孤立结点既是极小元，也是极大元.计

58、计算算机机科科学学学学院院 刘刘 芳芳2024/7/211047.7.3 偏序集中的特殊元素偏序集中的特殊元素定义定义7.25:设设为偏序集为偏序集,B A,a A.（1）若若 x(xBx a)成立成立,则称则称a为为B的的上界上界.（2）若若 x(xBa x)成立成立,则称则称a为为B的的下界下界.（3）令令Cy|y为为B的上界的上界,则称则称C的最小元为的最小元为B的的最小上界最小上界或或上确界上确界.（4）令令Dy|y为为B的下界的下界,则称则称D的最大元为的最大元为B的的最大下界最大下界或或下确界下确界.计计算算机机科科学学学学院院 刘刘 芳芳例：例：对偏序集合对偏序集合2,3,6,1

59、2,24,36,R整除整除,求如下集合的上求如下集合的上界、最小上界、下界、最大下界。界、最小上界、下界、最大下界。2，3，612，24，362，324，366，122024/7/211052426363127.7.3 偏序集中的特殊元素偏序集中的特殊元素计计算算机机科科学学学学院院 刘刘 芳芳2024/7/211067.7.3 偏序集中的特殊元素偏序集中的特殊元素例例7.21：设偏序集设偏序集如下图所示如下图所示求求A 的极小元、最小元、极大元、最大元的极小元、最小元、极大元、最大元.设设Bb,c,d ,求求B 的下界、上界、下确界、上确界的下界、上界、下确界、上确界.解：解：极小元：极小元

60、：a,b,c,g；极大元：极大元：a,f,h；最小元：无最小元：无最大元：无最大元：无B的下界和最大下界都不存在的下界和最大下界都不存在,B的上界有的上界有d 和和f,最小上界为最小上界为d.计计算算机机科科学学学学院院 刘刘 芳芳2024/7/211077.7.3 偏序集中的特殊元素偏序集中的特殊元素性质：性质：下界、上界、下确界、上确界不一定存在下界、上界、下确界、上确界不一定存在下界、上界存在不一定惟一下界、上界存在不一定惟一下确界、上确界如果存在，则惟一下确界、上确界如果存在，则惟一集合的最小元就是它的下确界，最大元就是它的上确集合的最小元就是它的下确界，最大元就是它的上确界；反之不对界；反之不对.