离散数学二元关系.ppt

1、2020/10/7,1,第四章 二元关系,主要内容： 关系的概念及表示方法 关系的性质 关系的运算: 关系的复合，求逆关系，关系的闭包。 三种关系: 等价关系，相容关系， 次序关系。,2020/10/7,2,一、序偶与有序n元组 1.定义:由两个对象x、y组成的序列称为有序二元组，也称之为序偶，记作；称x、y分别为序偶的第一，第二元素。 注意，序偶与集合x,y不同： 序偶：元素x和y有次序； 集合x,y：元素x和y的次序无关紧要。,4-1 序偶与集合的笛卡尔积,2020/10/7,3,2.定义：设，是两个序偶， 如果x=u和y=v则称和相等， 记作=。 3 .定义：有序3元组是一个序偶,其第一

2、个元素也是个序偶。 有序3元组, c可以简记成， 但不是有序3元组。,2020/10/7,4,4.定义：有序n元组是一个序偶,其第一个元素本身是个有序n-1元组, 记作, xn。且可以简记成。 5. 定义= ( x1= y1) ( x2= y2) ( xn= yn),2020/10/7,5,例如“斗兽棋”的16颗棋子，,设：A=红,蓝 B=象,狮,虎,豹,狼,狗,猫,鼠 每个棋子可以看成一个序偶，斗兽棋可记成集合AB ： , , , , ,2020/10/7,6,1.定义:设A、B是集合，由A的元素为第一元素，B的元素为第二元素组成序偶的集合，称为A和B的笛卡尔积，记作AB，即 AB=|xAy

3、B 例1 设A=0,1，B=a,b，求AB ， BA， AA 。 解： AB=, BA=, AA=, 可见 ABBA 所以，集合的笛卡尔积运算不满足交换律。,2020/10/7,7,另外 (AB)C=,c|AB cC A(BC)=|aA BC, 因 不是有序三元组, 所以(AB)CA(BC)。故也不满足结合律。,2.性质 1) 如果A、B都是有限集，且|A|=m, |B|=n，则 |AB |=mn。 证明：由笛卡尔积的定义及排列组合中的乘法原理，直接推得此定理。 2) A=B=,2020/10/7,8,3) 对和满足分配律。 设A,B,C是任意集合，则 A(BC)= (AB)(AC)； A(B

4、C)= (AB)(AC)； (AB)C= (AC)(BC)； (AB)C= (AC)(BC)； 证明 ：任取A(BC) xA yBC xA(yByC) ( xA yB)(xAyC) ABAC (AB)(AC) 所以式成立。（其余可以类似证明）,2020/10/7,9,4) 若C, 则 AB(ACBC) (CACB) 证明：充分性： 设AB，求证 ACBC 任取AC xAyC xByC (因AB) BC 所以, ACBC。 必要性：若C, 由ACBC 求证 AB 取C中元素y, 任取 xA xAyC AC BC (由ACBC ) xByC xB 所以, AB。 所以 AB(ACBC) 类似可以证

5、明 AB (CACB)。,2020/10/7,10,5) 设A、B、C、D为非空集合，则 ABCDACBD 证明：首先,由ABCD 证明ACBD 任取xA，任取yB，所以 xAyBAB CD (由ABCD ) xCyD 所以, ACBD。 其次, 由AC，BD 证明ABCD 任取AB xAyB xCyD (由AC，BD) CD 所以, ABCD 证毕。,2020/10/7,11,6)约定 (A1A2)An-1)An)=A1A2An 特别 AAA = An 设R是实数集合，则R2表示笛卡尔坐标平面， R3表示三维空间，Rn表示n维空间。 3. 应用 1)令A1=x|x是学号 A2=x|x是姓名

6、A3=男,女 A4=x|x是出生日期 A5=x|x是班级 A6 =x|x是籍贯 则A1A2A3 A4A5 A6中一个元素： 这就是学生档案数据库的一条信息，所以学生的档案就是A1A2A3 A4A5 A6的一个子集。,2020/10/7,12,2) 令A=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v, w,x,y,z 是英文字母表 一个英文单词可以看成有序n元组：如 at=, boy=, data=, computer= 于是可以说： atA2 ,boyA3,dataA4,computerA8, 所以英文词典中的单词集合可以看成是 AA2An 的一个子集

7、。 作业 P105 ,2020/10/7,13,4-2 关系及其表示法,相关 按照某种规则，确认了二个对象或多个对象之间有关系，称这二个对象或多个对象是相关的。,例1： 大写英文字母与五单位代码的对应关系R1: 令=A,B,C,D,Z =30,23,16,22,21是五单位代码集合 =11000, 10011, 01110, 10010, 10001 R1=,.,2020/10/7,14,例2：令=1,2,3,4, A中元素间的关系R2 ： R2= , , , ,AA,关系的定义 定义1: 设A、是集合，如果AB，则称R是一个从A到B的二元关系。如果 RAA，则称R是A上的二元关系。二元关系简

8、称为关系。 定义2: 任何序偶的集合，都称之为一个二元关系。如:R=,基本概念,2020/10/7,15,R xRy 也称之为x与y有关系。,R xRy 也称之为x与y没有关系。,例3. R是实数集合，R上的几个熟知的关系,从例3中可以看出关系是序偶(点)的集合(构成线、面)。,2020/10/7,16,关系的定义域与值域 定义域(domain)：设RAB，由所有R的第一个元素组成的集合，称为R的定义域。 记作dom R，即 dom R=x|y(R) 值域(range)：设RAB，由所有R的第二个元素组成的集合，称为R的值域。 记作ran R，即 ran R=y|x(R) 令： R1= , ,

9、 , , , , dom R1 =1,2,3,4 ran R1 =1,2,3,4,2020/10/7,17,枚举法： 即将关系中所有序偶一一列举出，写在大括号内。如R = , , , , , , , 。 谓词公式法： 即用谓词公式表示序偶的第一元素与第二元素间的关系。例如 R=|xR时，从x到y引一条有向弧(边)。这样得到的图形称为R的关系图。,关系的表示方法,2020/10/7,18,例 设A=1,2,3,4,B=a,b,c, R1 AB,R2 AA， R1 = , R2 = , ,R1 、R2的关系图如下：,2020/10/7,19,矩阵表示法： 设A=a1, a2, , am，B=b1,

10、 b2, , bn是个有限集， RAB，定义R的mn阶矩阵 MR=(rij)mn，其中,例：R1= , R2= , ,2020/10/7,20,空关系： 因为AB，(或AA)，所以也是一个从A到B(或A上)的关系，称之为空关系。 即无任何元素的关系，它的关系图中只有结点,无任何边；它的矩阵中全是0。 完全关系(全域关系) ： AB(或AA)本身也是一个从A到B(或A上) 的关系，称之为完全关系。 即含有全部序偶的关系。它的矩阵中全是1。,三个特殊关系,2020/10/7,21,A上的恒等关系IA： IAAA,且IA =|xA为A上的恒等关系。 例如 A=1,2,3, 则IA =, A上的、完全

11、关系及IA的关系图及矩阵如下：,2020/10/7,22,由于关系就是集合，所以集合的、-、 和运算对关系也适用。 例如 A是学生集合，R是A上的同乡关系，S是A上的同姓关系，则 RS：或同乡或同姓关系 RS：既同乡又同姓关系 R-S ：同乡而不同姓关系 RS：同乡而不同姓,或同姓而不同乡关系 R：不是同乡关系, 这里R=(AA)-R 作业 P109 、c)d),关系的集合运算,2020/10/7,23,本节中所讨论的关系都是集合A中的关系。 关系的性质主要有：自反性、反自反性、对称性、反对称性和传递性。 一. 自反性 定义:设R是集合A中的关系，如果对于任意xA都有R (xRx)，则称R是A

12、中自反关系。 即 R是A中自反的关系x(xAxRx) 例如：在实数集合中,“”是自反关系，因为，对任意实数x，有x x.,4-3 关系的性质,2020/10/7,24,从关系有向图看自反性:每个结点都有环。 从关系矩阵看自反性：主对角线都为1。,令A=1,2,3，确定以下八个关系中哪些是自反的？,2020/10/7,25,二.反自反性 定义：设R是集合A中的关系，如果对于任意的xA都有R ，则称R为A中的反自反关系。 即 R是A中反自反的x(xAR) 从关系有向图看反自反性:每个结点都无环。 从关系矩阵看反自反性：主对角线都为0。 如 实数的大于关系，父子关系是反自反的。 注意：一个不是自反的

13、关系，不一定就是反自反 的，如前边R6、R7非自反,也非反自反。,2020/10/7,26,R2、R5、 R8、均是反自反关系。,观察下图：,2020/10/7,27,三.对称性 定义:R是集合A中关系,若对任何x, yA,如果有xRy,必有yRx,则称R为A中的对称关系。 R是A上对称的 xy(xAyAxRy) yRx) 从关系有向图看对称性:在两个不同的结点之间，若有边的话，则有方向相反的两条边。 从关系矩阵看对称性：以主对角线为对称的矩阵。 例 邻居关系和朋友关系是对称关系。,2020/10/7,28,R3、R4、 R6 、 R8均是对称关系。,2020/10/7,29,四.反对称性 定

14、义:设R为集合A中关系,若对任何x, yA,如果有xRy,和yRx,就有x=y,则称R为A中反对称关系 。,由R的关系图看反对称性：两个不同的结点之间最多有一条边。 从关系矩阵看反对称性：以主对角线为对称的两个元素中最多有一个1。 另外对称与反对称不是完全对立的，有些关系它既是对称也是反对称的，如空关系和恒等关系。,2020/10/7,30,上面R1、R2、R4、R5、R8均是反对称关系。 R4、R8既是对称也是反对称的。,2020/10/7,31,五. 传递性 定义:R是A中关系，对任何x,y,zA,如果有xRy,和yRz,就有xRz,则称R为A中传递关系。 即R在A上传递 xyz(xAyA

15、zAxRyyRz)xRz) 例 实数集中的、，集合、是传递的。 从关系关系图和关系矩阵中不易看清是否有传递性。必须直接根据传递的定义来检查。 检查时要特别注意使得传递定义表达式的前件为F的时候此表达式为T，即是传递的。 即若R与R有一个是F时(即定义的前件为假)，R是传递的。,例如 A=1,2,下面A中关系R是传递的。 通过带量词的公式在论域展开式说明R在A上传递,xyz(xAyAzAxRyyRz)xRz) xyz(xRyyRz)xRz) (为了简单做些删改) yz(1RyyRz)1Rz)yz(2RyyRz)2Rz) (z(1R11Rz)1Rz)z(1R22Rz)1Rz) (z(2R11Rz)

16、2Rz) (z(2R22Rz)2Rz) (1R11R1)1R1)(1R11R2)1R2) (1R22R1)1R1)(1R22R2)1R2) (2R11R1)2R1) (2R11R2)2R2) (2R22R1)2R1) (2R22R2)2R2) (FF)F)(FT)T)(TF)F)(TF)T) (FF)F) (FT)F)(FF)F)(FF)F)T,2020/10/7,33,以上R1、R3、R4、R5、R8均是传递的关系。,本节要求： 1.准确掌握这五个性质的定义。 2.熟练掌握五个性质的判断和证明。 R是A中自反的x(xAxRx) R是A中反自反的x(xAR) R是A上对称的xy(xAyAxRy

17、) yRx) R是A上反对称的 xy(xAyAxRyyRx) x=y) xy(xAyAxyxRy)y x) R在A上传递 xyz(xAyAzAxRyyRz)xRz) 注意 性质表达式的前件为F时此表达式为T，即R是满足此性质的。 (自反和反自反性除外),2020/10/7,35,2020/10/7,36,下面归纳这八个关系的性质：Y-有 N-无,2020/10/7,37,2020/10/7,38,练习1:令I是整数集合，I上关系R定义为： R=|x-y可被3整除， 求证R是自反、对称和传递的。 证明：自反性：任取xI, 因 x-x=0, 0可被3整除,所以有R, 故R自反。 对称性：任取x,y

18、I,设R, 由R定义得 x-y可被3整除, 即x-y=3n(nI)， y-x=-(x-y)=-3n=3(-n), -nN R, R是对称的。 传递性:任取x,y,zI,设xRy, yRz, 由R定义得 x-y=3m, y-z=3n (m.nI) x-z= (x-y)+(y-z)=3m+3n=3(m+n), m+nN 所以xRz, 所以R传递。 证毕,2020/10/7,39,练习2：设R是集合A上的一个自反关系,求证： R是对称和传递的，当且仅当和 在R中,则有也在R中。 证明：必要性 已知R是对称和传递的。 设R 又R，(要证出 R ) 因R对称的故R,又已知R 由传递 性得R。所以有如果和

19、在R 中,则有也在R中。 充分性 已知任意 a,b,cA，如和在 R中,则有也在R中。,2020/10/7,40,先证R对称 任取 a,bA 设R，(要证出 R ) 因R是自反的,所以R，由 R且R，根据已知条件得 R ，所以R是对称的。 再证R传递 任取 a,b,cA 设R，R。 (要证出R ) 由R是对称的,得R ，由 R且R，根据已知条件得 R ， 所以R是传递的。 作业 第113页 、,2020/10/7,41,4-4 关系的复合,下面介绍由两个关系生成一种新的关系，即关系的复合运算。 例如，有3个人a,b,c，A=a,b,c， R是A上兄妹关系， S是A上母子关系， RS 即a是b的

20、哥哥, b是a的妹妹; b是c的母亲，c是b的儿子。 则a和c间就是舅舅和外甥的关系,记作 RS, 称它是R和S的复合关系。,2020/10/7,42,1.定义:设R是从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作RS 。定义为： RS =|xXzZ y(yY RS) 显然， RS 是从X到Z的关系。 2.复合关系的计算方法(俗称过河拆桥法) A=1,2,3 B=1,2,3.4 C=1,2,3,4,5 RAB SBC 枚举法 R=, S=, 则 RS =,2020/10/7,43,有向图法, 关系矩阵法 令A=a1, a2, am B=b1, b2, bn C=c1, c2, ct

21、 RAB SBC,2020/10/7,44,2020/10/7,45, 谓词公式法 设I是实数集合，R和S都是I上的关系，定义如下： R=| y=x2+3x S=| y=2x+3,所以 RS =| y=2x2+6x+3,三.性质 关系复合运算不满足交换律，但是 1.满足结合律: RAB SBC TCD 则,2020/10/7,46,b(bBR (S T) b(bBRc(cCST) bc(bBR(cCST) cb(cC(bBRST) c (cCb(bBRS)T) c (cC(R S)T) ,所以,可以用下图形象表示:,证明：任取,2020/10/7,47,2. RAB SBC TBC,证明 任取

22、R (ST) b(bBRST) b(bBR(ST) b(bBRS) (bBRT) b(bBRS) b(bBRT) R SR T (R S)(R T) 所以R (ST)=(R S)(R T),2020/10/7,48,证明 任取R (ST) b(bBRST) b(bBR(ST) b(bBRS) (bBRT) b(bBRS) b(bBRT) R S R T (R S)(R T) 所以 R (ST)(R S)(R T) x(A(x)B(x) xA(x)xB(x),2020/10/7,49,3. R是从A到B的关系，则,验证:,令A=1,2,3, B=a,b,c,d,从这两个图看出它们的复合都等于R。

23、,2020/10/7,50,4. 关系的乘幂 令R是A上关系，由于复合运算可结合，所以 关系的复合可以写成乘幂形式。即,例如R是A上关系，如上图所示,可见 R2,表明在R图上有从a到c有两条边的路径: abc;R3,表明在R图上有从a到d有三条 边的路径:abcd。.如果Rk,表明在 R图上有从x到y有k条边(长为k)的路径(x,yA)。,有,(m,n为非负整数),2020/10/7,51,4-5 逆关系,一.定义 R是从A到B的关系，如果将R中的所有序偶的 两个元素的位置互换，得到一个从B到A的关系， 称之为R的逆关系，记作RC，或 R-1。 RC=|R RC R 二. 计算方法 1. R=

24、, RC =,2020/10/7,52,2. RC的有向图：是将R的有向图的所有边的方向颠倒一下即可。 3. RC的矩阵 M =(MR)T 即为R矩阵的转置。如,三.性质 令R、S都是从X到Y的关系，则 1. (RC)C = R 2. (RS)C = RCSC 。 3. (RS)C = RCSC 。 4. (RS)C = RCSC 。,2020/10/7,53,证明1：任取(RS)C，则 (RS)C RS RS RCSC RCSC 所以 (RS)C = RCSC ，其它类似可证。 5. RS RC SC 。 证明：充分性，已知RC SC ，则任取R RC SC S RS 必要性，已知R S，则

25、任取RC R S SC RCSC,2020/10/7,54,6.(R)C=RC 证明:任取(R)C RR RC RC (R)C=RC,7.令R是从X到Y的关系，S是Y到 Z的关系，则 (R S)C= SC RC 。 (注意RC SC ) 证明：任取(R S)C R S y(yYRS) y(yYSCRC) SC RC 所以(R S)C= SC RC,2020/10/7,55,8. R是A上关系，则 R是对称的，当且仅当 RC =R R是反对称的，当且仅当 RRC IA。 证明： 充分性，已知 RC =R (证出R对称) 任取x,yA 设R,则RC,而RC =R 所以有R ，所以R对称。 必要性，

26、已知R 对称，(证出RC =R) 先证RCR，任取RC,则R,因R对称 所以有R，所以RCR。 再证R RC，任取R, 因R对称，所以有 R，则RC, 所以RRC。 最后得RC =R 。,2020/10/7,56,证明 充分性，已知RRC IA，(证出R反对称) 任取x,yA 设R 且R， RRRRC， RRC IA (因RRC IA ) x=y 所以R反对称。 必要性，已知R反对称，(证出RRC IA) 任取RRC RRCRRC RR x=y (因R反对称) IA 所以RRC IA 。,作业：第118页 a)b)、,2020/10/7,57,4-6 关系的闭包运算,关系的闭包是通过关系的复合

27、和求逆构成的一个新的关系。 这里要介绍关系的自反闭包、对称闭包和传递闭包。,一.例子 给定 A中关系R，如图所示， 求A上另一个关系R，使 得它是包含R的“最小的”(序偶 尽量少)具有自反(对称、传递)性的关系。 这个R就是R的自反(对称、传递)闭包。,2020/10/7,58,这三个关系图分别是R的自反、对称、传递闭包。,二.定义：给定 A中关系R,若A上另一个关系R， 满足：RR； R是自反的(对称的、传递的)； R是“最小的”，即对于任何A上自反(对称、传递)的关系R,如果RR,就有RR。则称R是R的自反(对称、传递)闭包。记作r(R)、s(R)、t(R)(reflexive、symme

28、tric、transitive),2020/10/7,59,三.计算方法 定理1.给定 A中关系R,则 r(R)=RIA。 证明：令R =RIA,显然R是自反的和R R ，下面证明R是“最小的”：如果有A上自反关系R且R R,又IA R,所以 RIA R,即R R 。所以R就是R的自反闭包。即r(R)=RIA 。 定理2.给定 A中关系R,则 s(R)=RRC 。 证明方法与1.类似。 定理3.给定 A中关系R,则 t(R)=RR2R3. 。 证明：令R = RR2R3., 显然有 R R ；,2020/10/7,60,证R是传递的：任取x,y,zA,设有 R R, 由R定义得必存在整数i,j

29、使得Ri , Rj ,根据关系的复合得Ri+j, 又因Ri+j R,所以 R, R传递。 证R是“最小的”：如果有A上传递关系R且RR,（证出R R ）任取 R ,则由R定义得必存在整数i,使得Ri ,根据关系的复合得A中必存在i-1个元素e1, e2,.,ei-1，使得 (见49页) RR.R。因RR, 有 R R .R 。 由于R传递，所以有 R 。 R R 。 综上所述， R就是R的传递闭包，即 t(R)=RR2R3=Ri,2020/10/7,61,用上述公式计算t(R)，要计算R的无穷大次幂,好象无法实现似的。其实则不然，请看下例: A=1,2,3 A中关系R1,R2,R3,如下： R

30、1=, R2 =, R3 =, R12 = ,R13 = R14 = 所以 t(R1)= R1 R12 R13 = R1 R22 =, R23=, R23=IA, R24= R2 . t(R2)= R2 R22 R23 R32 =, ,R33 = R32 t(R3)= R3R32,2020/10/7,62,定理4.给定 A中关系R,如果A是有限集合，|A|=n 则 t(R)=RR2.Rn 。 证明：令R =RR2R3., R =RR2.Rn 显然有R R ,下面证明R R ： 任取 R,由R定义得必存在最小的正整数i 使得Ri , (下面证明in)如果in,根据关系的复合得A中必存在i-1个元

31、素e1, e2,.,ei-1，使得 RR.R。上述元素序列: x=e0, e1, e2,.,ei-1,y=ei中共有i+1个元素，i+1n , 而A 中只有n个元素，所以上述元素中至少有两个相同，设ej=ek (jk)，于是R的关系图中会有下面这些边：,2020/10/7,63,从此图中删去回路中k-j(k-j1)条边后得Ri-(k-j)，i-(k-j)R, 于是 R R 。 最后得 R = R ，所以 t(R)=RR2.Rn 定理证毕。,2020/10/7,64,求t(R)的矩阵Warshall算法： |X|=n, RXX,令MR=A R2的矩阵为A2， Rk的矩阵为Ak .于是t(R)的矩

32、阵记作MR+=A+A2+Ak + (+是逻辑加) 置新矩阵 A :=MR ; 置 i=1; 对所有 j ,如果Aj,i =1 ,则对k=1,2,n Aj,k:=Aj,k+Ai,k; /*第j行+第i行,送回第j行*/ i加1; 如果in, 则转到步骤，否则停止。,2020/10/7,65,举例，令X=1,2,3,4, X中关系R图如右图所示。 运行该算法求t(R)的矩阵：,A=MR=,i=1 (i-列, j-行) A4,1=1 L1+L4L4,最后 A=Mt(R),i=2 A1,2=1 A2,2=1 A4,2=1 L1+L2L1 L2+L2L2 L4+L2L4,i=3 A1,3=1, A2,3

33、=1, A4,3=1 L1+L3L1 L2+L3L2 L4+L3L4,i=4 A1,4=1 A4,4=1 L1+L4L1 L4+L4L4,2020/10/7,66,四.性质 定理5. R是A上关系，则 R是自反的，当且仅当 r(R)=R. R是对称的，当且仅当 s(R)=R. R是传递的，当且仅当 t(R)=R. 定理6. R是A上关系，则 R是自反的，则s(R)和t(R)也自反。 R是对称的，则r(R)和t(R)也对称。 R是传递的，则r(R)也传递。 证明: 因为R自反,由定理5得r(R)=R,即 RIA=R, r(s(R)=s(R)IA=(RRC)IA = (RIA)RC=r(R)RC

34、=RRC =s(R)s(R)自反,2020/10/7,67,类似可以证明t(R)也自反。 证明. 证明t(R)对称: (t(R)C=(RR2.Rn.)C = RC(R2)C .(Rn)C. = RC(RC)2 .(RC)n. =RR2.Rn. (R对称，RC =R) =t(R) 所以t(R)也对称。 类似可以证明r(R)也对称。 证明. 证明r(R)传递:先用归纳法证明下面结论: (RIA)i= IARR2.Ri i=1时 RIA= IAR 结论成立。 假设ik 时结论成立，即 (RIA)k= IARR2.Rk,2020/10/7,68,当i=k+1时 (RIA)k+1=(RIA)k (RIA

35、) = (IARR2.Rk） (IAR) = (IARR2.Rk)(RR2.Rk+1) = IARR2.RkRk+1 所以结论(RIA)i= IARR2.Ri成立. t(r(R)=t(RIA) = (RIA)(RIA)2(RIA)3. =(IAR)(IARR2)(IARR2R3). = IARR2R3.= IAt(R) = IAR (R传递t(R)=R) =r(R) 所以r(R)也传递。,2020/10/7,69,定理7：设R1、R2是A上关系，如果R1R2 ，则 r(R1) r(R2) s(R1) s(R2) t(R1)t(R2) 证明 r(R1)=IAR1IAR2= r(R2) ，类似可证

36、。 定理8：设R是A上关系，则 sr(R)=rs(R) tr(R)=rt(R) st(R)ts(R) 证明： sr(R)=r(R)(r(R)c=(RIA)(RIA)c = (RIA)(RcIAc) =RIARcIA = (RRc)IA= s(R)IA=rs(R) 的证明用前边证明的结论： (RIA)k= IARR2.Rk可证，这里从略。,2020/10/7,70, 因 Rs(R) 由定理7得 t(R)ts(R) st(R)sts(R) 因s(R)对称，有定理6得ts(R) 也对称，由定理5得 sts(R)=ts(R) 所以有st(R)ts(R) 。 证明完毕。,练习：给定A中关系R如图所示：分

37、别画出r(R)、s(R) 、t(R)、sr(R)、rs(R)、tr(R)、rt(R)、st(R) 、ts(R)的图。,2020/10/7,72,本节重点掌握闭包的定义、计算方法和性质。 作业：P127 、,2020/10/7,73,4-7 集合的划分与覆盖,一.定义 设X是一个非空集合,A=A1, A2,. ,An,Ai AiX (i=1,2,.,n),如果满足A1A2.An =X (i=1,2,., n)则称A为集合X的覆盖。 设A=A1, A2,. ,An是X一个覆盖, 且AiAj= (ij,1i,jn)则称A是X的划分,每个Ai均称为这个划分的一个划分类。 例 X=1,2,3, A1=1

38、,2,3, A2=1,2,3, A3=1,2,3, A4=1,2,2,3, A5=1,3 A1, A2 ,A3 ,A4 是覆盖。 A1, A2 ,A3也是划分。 划分一定是覆盖；但覆盖不一定是划分。,2020/10/7,74,二.最小划分与最大划分 最小划分：划分块最少的划分。即只有一个划分块的划分，这个划分块就是X本身。如A1=1,2,3 。 最大划分：划分块最多的划分。即每个划分块里只有一个元素的划分。如A2 =1,2,3 。 A1,A2,A3是一种划分,其中A1是最小划分,A2是最大划分。,2020/10/7,75,三.交叉划分 例 X是东大学生集合, A和B都是X的划分： A=M,W,

39、MX, WX, M=男生,W=女生 B=L,N,LX, NX, L=辽宁人,N=非辽宁人,C=LM , LW , NM , NW ,称C是X的交叉划分。,2020/10/7,76,定义：若A=A1, A2,. ,Am与B=B1,B2,.,Bn都是集合X的划分,则其中所有的AiBj,组成的集合C,称为C是A与B两种划分的交叉划分。 证明:在C中任取元素, AiBjX (AiX,BjX) (A1B1)(A1B2).(A1Bn)(A2B1) (A2Bn). (AmB1)(AmB2).(AmBn) =(A1( B1B2B3.Bn)(A2( B1B2B3. Bn). (Am( B1B2B3. Bn) =

40、 (A1A2A3.Am) ( B1B2B3. Bn) =XX=X,2020/10/7,77,再验证C中任意两个元素不相交： 在C中任取两个不同元素AiBh和AjBk,考察 (AiBh) (AjBk) (i=j和h=k不同时成立) = (AiAj)(BhBk) ij ,hk (AiAj)(BhBk) =Ai= ij ,hk (AiAj)(BhBk)= ij, h=k (AiAj)(BhBk)= Bh = 综上所述，C是X的划分。 作业：第130页 (1),2020/10/7,78,一.等价关系 1.定义:设R是A上关系,若R是自反的、对称的和传递的，则称R是A中的等价关系。 若a,bA，且aRb

41、，则称a与b等价。 例子，集合A=1,2,3,4,5,6,7, R是A上的模3同余关系，即 R=|x-y可被3整除(或x/3与y/3的余数相同) 即R x(mod 3)=y(mod3),4-8 等价关系与等价类,2020/10/7,79,上例中的关系为： R=, ,2.等价关系的有向图 1)完全关系(全域关系AA)图，下面分别是当A中只有1、2、3个元素时的完全关系图。,A=1,A=1,2,A=1,2,3,2020/10/7,80,2.等价关系的有向图 模3同余关系R的图： 从关系图可看出R是自反、对称、传递的关系，所以R是等价关系。,等价关系R的有向图可能由若干个独立子图(R图的一部分)构成

42、的，每个独立子图都是完全关系图。 上述关系R图就是由三个独立的完全图构成的。 下面给出八个关系如图所示，根据等价关系有向图的特点，判断哪些是等价关系。,2020/10/7,81,下面是A =1,2,3中关系：,2020/10/7,82,思考题：A=1,2,3,可构造多少个A中不同的等价关系？可以根据等价关系有向图的特点来考虑。 如果等价关系R中有 a)三个独立子图的情形，则( )个等价关系 。 b)二个独立子图的情形，则( )个等价关系 。 c)一个独立子图的情形，则( )个等价关系 。 一共有( )个中不同的等价关系。,2020/10/7,83,二. 等价类,1.定义：R是A上的等价关系，a

43、A,由a确定的集合aR: aR=x|xAR 称集合aR为由a形成的R等价类。简称a等价类。 可见 xaR R 上例，A=1,2,3,4,5,6,7, R是A上的模3同余关系， 1R=1,4,7= 4R = 7R -余数为1的等价类 2R=2,5= 5R -余数为2的等价类 3R=3,6= 6R -余数为0的等价类 思考题：此例为什么只有三个等价类？,2020/10/7,84,2. 由等价关系图求等价类：R图中每个独立子图上的结点，构成一个等价类。 不同的等价类个数=独立子图个数。,上述三个等价关系各有几个等价类？说出对应的各个等价类。,2020/10/7,85,3.等价类性质 R是A上等价关系

44、，任意a,b,cA 同一个等价类中的元素，彼此有等价关系R。 即任意x,yaR，必有R 证明：任取x,yaR，由等价类定义得R, R ,由R对称得R，又由R传递得R。,2020/10/7,86, aRbR=， 当且仅当 R。 证明:设R，假设aRbR,则存在xaRbR， xaRxbR, R ,R,由R对称得R又由R传递得R,产生矛盾。 若aRbR=,而R,由等价类定义得baR, 又因为bRb,所以bbR，所以baRbR，产生矛盾。,2020/10/7,87, aR=bR 当且仅当 R。 证明：若R，则任何xaR，有R，由对称性得R，再由传递性得R,xbR，所以aRbR。 类似可证bRaR。 a

45、R=bR。 如果aR=bR，由于有aRa,所以aaR ，abR ，所以有R，由对称性得R。 .A中任何元素a,a必属于且仅属于一个等价类。 证明：A中任何元素a,由于有aRa,所以aaR ，如果 abR ，所以有R. 由性质得：aR=bR 。,2020/10/7,88,.任意两个等价类 aR、bR， 要么aR=bR ，要么aRbR= 。 (因为要么R，要么R。) . R的所有等价类构成的集合是A的一个划分。 (由性质即得。) (这个划分称之为商集) 性质（4）说明了覆盖性，性质（5）说明了不相交性,2020/10/7,89,三. 商集,定义：R是A上等价关系，由R的所有等价类构成的集合称之为A

46、关于R的商集。记作A/R。即 A/R=aR |aA,例如A=1,2,3,4,5,6,7 , R上模3同余关系，则 A/R= 1R,2R,3R =1.4.7,2,5,3,6,2020/10/7,90,练习: X=1,2,3,X上关系R1、R2 、R3，如上图所示。 X/R1=1R1,2R1,3R1=1,2,3 X/R2=1R2 ,2R2=1,2,3 X/R3=1R3=1,2,3,2020/10/7,91,定理: 集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。 证明：由等价类性质可得 ： 1) A/R中任意元素aR，有aRA。 2) 设aR,bR是A/R的两个不同元素，有aRbR

47、= 3) 因为A中每个元素都属于一个等价类，所以所有等价类的并集必等于A。 所以商集A/R是A的一个划分。 定理： 设R1和R2是非空集合A上的等价关系，则 A/R1=A/R2 当且仅当 R1=R2 。 (这个定理显然成立。),2020/10/7,92,四. 由划分确定等价关系,例如，X=1,2,3,4,A=1,2,3,4, A是X的一个划分， 求X上一个等价关系R，使得X/R=A。 显然由图可得：R=1,223242 。,一般地A=A1,A2,An是X的一个划分，则构造一个X中的等价关系R，使得X/R=A。R=A12A22,An2 其中Ai= Ai2Ai2， 下面证明R是X中的等价关系。,定

48、理: 集合X的一个划分可以确定X上的一个等价关系。 证明：假设A=A1, A2,. ,An是X的一个划分，如下构造X 上的一个等价关系R: RA12A22An2，其中Ai2=Ai2Ai2， 1) 证R自反：任取aX，因为A是X的划分，必存在 AiA使aAi ,于是AiAi , 又AiAi R 有aRa。 2) 证R对称：任取a,bX, 设aRb，必存在AiA使得 AiAi ,于是a,bAi , bRa, R是对称的。 3) 证R传递：任取a,b,cX, 设aRb，bRc, 必存在AiA使得AiAi ,AiAi ,于是a,b,cAi , 所以AiAi ，又AiAi R 有aRc 所以R传递。最后

49、得R是集合X中的等价关系。,2020/10/7,94,本节重点： 等价关系概念、证明。 等价类概念、性质。 求商集。 作业：P134 、,2020/10/7,95,4-9 相容关系,定义:给定集合X上的关系r, 若r是自反的、对称的,则r是A上相容关系。 例子：X 是由一些英文单词构成的集合。 X=fly, any, able, key, book, pump, fit, X上关系r: r=|X,X且与含有相同字母,2020/10/7,96,r的有向图： 看出有自反、 对称性。而 不传递。,相容关系的简化图和简化矩阵,图的简化：不画环； 两条对称边用一条无向直线代替。,矩阵的简化：因为r的矩阵

50、是对称阵且主对角线全是1，用下三角矩阵(不含主对角线)代替r的矩阵。,令x1=fly, x2= any, x3= able, x4=key, x5=book, x6= pump, x7= fit, X=x1 ,x2, x3, x4, x5, x6 ,x7, r的简化图为：,2020/10/7,98,相容类及最大相容类,定义：设r是集合X上的相容关系,CX,如果对于C中任意元素x,y有r ,称C是r的一个相容类。 上例中x1,x2,x3,x4,x1,x2,x3,x2,x3,x4,x1,x2, x4, x3,x4,x5,x1,x3,x4,x1,x2,x3,x4,x1,x7,x6 都是相容类。上述相

51、容类中，有些相容类间有真包含关系。,定义：设r是集合X上的相容关系，C是r的一个相容类，如果C不能被其它相容类所真包含，则称C是一个最大相容类。 也可以说，C是一个相容类，如果C中加入任意一个新元素，就不再是相容类，C就是一个最大相容类。 x1,x2,x3,x4 , x3, x4, x5, x1,x7 , x6都是最大相容类。,2020/10/7,99,从简化图找最大相容类：-找最大完全多边形。 即：含有结点最多的多边形中，每个结点都与其它结点相联结。,在相容关系简化图中，每个最大完全多边形的结点集合构成一个最大相容类。 上例中最大相容类x1,x2,x3,x4, x3, x4,x5, x1,x

52、7, x6分别对应最大完全四、三、一、零边形。,2020/10/7,100,给定X上相容关系r ,如图所示, r的最大相容类：x1,x2,x5, x2, x3, x5, x3, x4,x5, x1,x4 ,x5,完全覆盖： 定义：r是X中的相容关系，由r的所有最大相容类为元素构成的集合，称之为X的完全覆盖。记作Cr(X)。 Cr(X)=x1,x2,x3,x4, x3, x4, x5,x1,x7,x6 Cr(X)=x1,x2,x5,x2, x3, x5, x3, x4, x5, x1,x4 ,x5,作业 P139 (2),2020/10/7,101,4-10 次序关系,一. 偏序(半序)关系(p

53、artial order relation),定义：R是A上自反、反对称和传递的关系，则称R是A上的偏序关系。并称是偏序集。 例如数值的、关系和集合的都是偏序关系。 用符号“”表示任意偏序关系，但要注意“”不一定是“小于或等于”的含义。,例1 A=1,2,4,6, 是A中的整除关系，其关系图如右图，显然是自反、反对称和传递的，即它是个偏序。,2020/10/7,102,注： （1）用矩阵表示半序关系，不能明显看到二元关系的特征。 （2）用简化的关系图表示较适合。,简化的关系图： (1)自反性：每个顶点都有自回路，省去。 (2)反对称性：两个顶点间只可能有一个箭头从左右，或从下上的方向从小到大安

54、置顶点，可省略箭头。 (3)传递性：由于有(a,b)，(b,c)R 则(a,c) R 故只画(a,b)，(b,c)对应的边,省略边(a,c)。,2020/10/7,103,定义：Hasse图 设是上的一个半序关系，如果ab ，则将画在下面，且不，使ac，cb，则，间用直线连接。并符合简化的关系图的绘制，称这样得到关系图为Hasse图。,例： ， ， 1（，） ， 2（，） |， 3(s1,s2)12，s1，s2p(B),2020/10/7,104,2020/10/7,105,定义 全序： 上半序关系，如果,，都有，或，则称为上的全序关系。,二.全序(线序、链),全序的含义：中每两个元素均能比大

55、小，即任何两个元素都相关。 半序则是部分有序。 1是全序，2，3都是半序 如：2中，1，2，6,1，2，4，8，1，3，9都排成了序，但2与3，5与7，7与9，在整除的意义上来说无法排出大小来。,2020/10/7,106,练习： C=1,2,3,6,12,24,36, D=1,2,3,5,6,10,15,30 是C、D上整除关系：, 的Hasse图：,2020/10/7,107,三. 偏序集中的重要元素,y是B的极小元 y(yAx(xAxyxy) y是B的极大元 y(yAx(xAxyyx),定义极大元与极小元： 设（，）是半序集，若，且在中找不到一个元素（），使（），则称为中的极大元（极小元

56、）。,2020/10/7,108,例（N，|）是半序集，A=2，3，4，5，6，7，8，9则 中极大元：， 极小元：， 注： 极大元，极小元并不要求唯一，且同一元素，可以既是极大元，又是极小元，如，。 极大元，极小元必须是子集中的元素。,2020/10/7,109,定义 最大元与最小元： 设（，）是半序集，若，(），则称为的最大元（最小元）。,例：上例 其Hasse图如下图所示,结论：子集中是不存在最大元（最小元）的。,2020/10/7,110,定理是偏序集，B是A的非空子集，如果B有最小元(最大元)，则最小元(最大元)是唯一的。 证明：假设B有两个最小元a、b,则 因为a是最小元，bB，根

57、据最小元定义，有ab; 类似地，因为b是最小元，aB，根据最小元定义，有ba。因为有反对称性，所以有a=b。 同理可证最大元的唯一性。 小结：是偏序集，B是A的非空子集，则 B的极小(大)元总是存在的，就是子集中处在最下(上)层的元素是极小(大)元。 B的最小元(最大元)有时可能不存在，只要有唯一的极小(大)元，则这个极小(大)元就是最小(大)元。否则就没有最小(大)元。,2020/10/7,111,定义上界与下界： 设（P,）是半序集，AP，若aP，对 ,（）称为的上界（下界）。,例：B=a,b,c,R3= (s1,s2) | s1 s2，s1P(B) , (P(B), )是半序集。 设，a,b,c,a,c,a,b,a,c 其Hasse图如右图所示:,2020/10/7,112,注： （1）上例中，无最大元，但存在的上界，。 （2）为的最小元，也是的下界 （3）最大（小）元是的一个上（下）界 （4）上（下）界可以不唯一，也可以不存在,定义上确界与下确界： 设（，）是半序集，若是的一个上界（下界），而的上界（下界），都有（），则称是的上确界（下确界）。,2020/10/7,113,注： 上确界：最小上界 下确界：最大下界 如果存在上（下）确界，则上（下）确界一定是唯一的,举例，给定的Hasse图如图所