离散数学新二元关系

1、第四章 二元关系 二元关系是一个很重要的概念，在计算机科学的如二元关系是一个很重要的概念，在计算机科学的如下理论中都有应用：下理论中都有应用： 逻辑设计、数据结构、编译原理、软件工程逻辑设计、数据结构、编译原理、软件工程, , 数据库理论、计算理论、算法分析、数据库理论、计算理论、算法分析、 操作系统等操作系统等 本章主要介绍：本章主要介绍： 关系的概念及表示方法关系的概念及表示方法 ； 关系的性质；关系的性质； 关系的运算；关系的运算； 三种特殊关系；三种特殊关系；4-1 序偶与集合的 笛卡尔积实际上实际上“序偶序偶”概念以前已经用过。例如，概念以前已经用过。例如，用序偶表示平面直角坐标系中

2、一个点用序偶表示平面直角坐标系中一个点x,yx,y。设设x x表示上衣表示上衣, ,y y表示裤子表示裤子, ,可以表示一个人可以表示一个人的着装。的着装。一一. .序偶与有序序偶与有序n n元组元组1.1.定义定义: :由两个对象由两个对象x x、y y组成的序列称为有序二组成的序列称为有序二元组，也称之为序偶，记作元组，也称之为序偶，记作；称；称x x、y y分分别为序偶别为序偶的第一，第二元素。的第一，第二元素。 注意，序偶注意，序偶与集合与集合x,yx,y不同：不同： 序偶序偶：元素：元素x x和和y y有有次序；次序； 集合集合x,yx,y：元素：元素x x和和y y的次序是无关紧要

3、的。的次序是无关紧要的。2.2.定义：定义：设设，是两个序偶，如果是两个序偶，如果x=u且且y=v，则称，则称和和相等，记作相等，记作 =.3 .定义定义:有序有序3元组是一个序偶元组是一个序偶,其第一个元素也是个序其第一个元素也是个序偶。偶。 有序有序3元组元组, c可以简记成可以简记成。 但但a,不是不是有序有序3元组。元组。 4.定义定义:有序有序n元组是一个序偶元组是一个序偶,其第一个元素本身是个其第一个元素本身是个有序有序n-1元组元组,记作记作, xn。且可以简。且可以简记成记成。5. 定义定义： = ( x1= y1) ( x2= y2) ( xn= yn)二.集合的笛卡尔积 例

4、如例如“斗兽棋斗兽棋”的的16颗棋子，颗棋子， 令：令： A=红红,蓝蓝 B=象象,狮狮,虎虎,豹豹,狼狼,狗狗,猫猫,鼠鼠每个棋子可以用一个序偶表达每个棋子可以用一个序偶表达，斗兽棋可记成集合斗兽棋可记成集合A B ： , , 虎象狮豹狼鼠猫狗虎象狮豹狼鼠猫狗1.定义定义:设设A、B是集合，由是集合，由A的元素为第一元素，的元素为第一元素，B的元素为第二元素组成序偶的集合，称为的元素为第二元素组成序偶的集合，称为A和和B的笛卡尔积，记作的笛卡尔积，记作AB，即即 A B=|x Ay B 例例1 设设A=0,1，B=a,b，求，求A B ， B A， A A 。 解：解： A B=, B A=

5、, A A=,可见可见 ABBA所以，所以，集合的笛卡尔积运算不满足交换律集合的笛卡尔积运算不满足交换律。 另外另外 (A B) C=,c| A B c C A (B C)=a,|a A B C, 因因 a,不是有序三元组不是有序三元组, 所以所以(A B) C A (B C)。 故故笛卡尔积也不满足结合律笛卡尔积也不满足结合律。2.性质性质 1) 如果如果A、B都是有限集，且都是有限集，且|A|=m, |B|=n，则，则 |A B |=mn. 2) A = B= 3) 对对和和满足分配律满足分配律。 设设A,B,C是任意集合，则是任意集合，则 A (BC)= (A B)(A C)； (AB)

6、 C= (A C)(B C)； A (BC)= (A B)(A C)； (AB) C= (A C)(B C)证明证明 ：任取：任取 A (BC) x A y BC x A (y By C) ( x A y B)(x A y C) A B A C (A B)(A C) 所以式成立。所以式成立。其余可以类似证明。其余可以类似证明。思考：思考： 对对- -和和是否满足分配律？是否满足分配律？4)若若C,则则 A B(A C B C) (C A C B).证明证明: 必要性：必要性：若若 A= , 结论显然结论显然.若若A, 设设A B，往证，往证 A C B C.因为因为C, 任取任取 A C x

7、A y C x B y C (因因A B) B C 所以所以, A C B C. 充分性：充分性： 若若C, 由由A C B C 往证往证 A B 因为因为C, 取取C中元素中元素y, 任取任取 x A, 于是于是x A y C 即即 A C B C (由由A C B C ) x B y C x B 所以所以, A B.综上综上 A B(A C B C) 类似可以证明类似可以证明 A B (C A C B).5) 设设A、B、C、D为非空集合，则为非空集合，则 A B C DA CB D.证明证明: 首先首先,由由A B C D 往证往证A CB D.因因A、B为非空集合，任取为非空集合，任取

8、x A，任取，任取y B，所以有所以有 x A y B AB CD (由由A B C D )x C y D 所以所以, A CB D. 其次其次, 由由A C，B D. 往证往证A B C D因因A、B为非空集合，任取为非空集合，任取 AB AB x A y B x C y D (由由A C，B D) CD 所以所以, A B C D 证毕证毕.约定约定 (A1 A2) An-1) An)=A1 A2 An 特别地特别地 A A A = An 设设R是实数集合，则是实数集合，则R2表示表示笛卡尔坐标平面，笛卡尔坐标平面， R3表示表示三维欧氏空间，三维欧氏空间，Rn表示表示n维维欧氏欧氏空间。

9、空间。3.应用应用1)令令A1=x|x是是学号学号 A2=x|x是是姓名姓名 A3=男男,女女 A4=x|x是是出生日期出生日期 A5=x|x是是班级班级 A6 =x|x是是籍贯籍贯 则则A1 A2 A3 A4 A5 A6中一个元素：中一个元素：这就是学生档案数据库的一条信息，所以学生这就是学生档案数据库的一条信息，所以学生的档案就是的档案就是A1 A2 A3 A4 A5 A6的一个子集。的一个子集。n 个个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 是英文字母表是英文字母表 一个一个英文单词可以看成有序英文单词可以看成

10、有序n元组：如元组：如 at=, boy=, data=, computer= 于是可以说：于是可以说： at A2 ,boy A3,data A4,computer A8, 于是英文词典中的于是英文词典中的单词集合单词集合可以看成是可以看成是 AA2An 的一个子集。的一个子集。4-2 关系及其表示法 关系是一个非常普遍的概念，如数值的大于关系是一个非常普遍的概念，如数值的大于关系、整除关系，人类的父子关系、师生关关系、整除关系，人类的父子关系、师生关系、同学关系等。下面讨论如何定义关系和系、同学关系等。下面讨论如何定义关系和如何表示关系如何表示关系。一一. .例子例子1集合集合A = 我们

11、班我们班, 我们班上的同乡关系即是我们班上的同乡关系即是 A A的子集的子集2.令令=1,2,3,4, A中元素间的中元素间的关系关系R2 ： R2= , AA二二. . 基本概念基本概念1.关系的定义关系的定义定义定义1: 设设A、B是集合，如果是集合，如果R AB ，则称则称R是一个是一个从从A到到B的二元关系。如果的二元关系。如果 R AA，则称，则称R是是A上上的二元的二元关系。关系。 二元二元关系简称为关系关系简称为关系。 R xRy 也称之为也称之为x与与y有有R关系。关系。 R xRy 也称之为也称之为x与与y没有没有R关系。关系。例例3. R是实数集合，是实数集合，R上的几个熟

12、知的关系：上的几个熟知的关系：从例从例3中可以看出中可以看出关系是序偶关系是序偶(点点)的集合的集合(构成构成线、面线、面等等)。x2+y2=4=xy2.关系的定义域与值域关系的定义域与值域定义域定义域(domain) ：设设R AB，由所有，由所有 R的第一个元素组成的集合，称为的第一个元素组成的集合，称为R的定义域，的定义域，记作记作dom R，即，即 dom R=x| y( R) 值域值域(range) ：设设R AB，由所有，由所有 R的第的第二个元素组成的集合，称为二个元素组成的集合，称为R的值域，的值域， 记作记作ran R，即，即 ran R=y| x( R) 例：例：A=1,2

13、,3,4 , R2 为为A上的关系，上的关系，R2= , , , dom R2 =1,2,3 ran R2 =1,2,3,4三三. . 关系的表示方法关系的表示方法1. 1. 枚举法枚举法: : 即将关系中所有序偶一一列举出，写在大括号即将关系中所有序偶一一列举出，写在大括号内。如内。如R2 = , , , , , , 。2.2.谓词公式法谓词公式法： 即用谓词公式表示序偶的第一元素与第二元素间即用谓词公式表示序偶的第一元素与第二元素间的关系。例如的关系。例如 R=|xy3.3.有向图法有向图法： R AB,用两组小圆圈用两组小圆圈(称为结点称为结点)分别表示分别表示A和和B的元素，当的元素，

14、当 R时，从时，从x到到y引一条有向弧引一条有向弧(边边)。这样得到的图形称为。这样得到的图形称为R的关系图。的关系图。 如如R AA,即即R是集合是集合A中关系时中关系时,可能有可能有 R,则从则从x到到x画一条有向环画一条有向环(自回路自回路)。例例 设设A=1,2,3,4,B=a,b,c， R3 AB， R3= ,则则R3的关系图如下：的关系图如下：例例 设设A=1,2,3,4, R4 AA，R4= ,则则R4的关系图如右上图。的关系图如右上图。 1。2。 3。 4。ABabc1。4。23R4 :R3 :4.4.矩阵表示法矩阵表示法： 有限集合之间的关系也可以用矩阵来表示，以便于用计有限

15、集合之间的关系也可以用矩阵来表示，以便于用计算机处理。算机处理。 设设A=a1, a2, , am，B=b1, b2, , bn是个有限集，是个有限集， R AB，定义，定义R的的mn阶阶矩阵矩阵 MR=(rij)mn，其中，其中 rij= R3= , R4= , 上例中 MR = MR4= 1 若R0 若R(1im,1jn)31 0 10 1 01 0 00 0 1431 2 3 4a b c1 0 0 10 0 1 01 1 0 01 0 0 1441 2 3 41 2 3 4四四. .三个特殊关系三个特殊关系1.空关系空关系： 因为因为 AB，(或或 AA)，所以，所以也也是一个从是一个

16、从A到到B(或或A上上)的关系，称之为的关系，称之为空关系空关系。即无任何元素的关系即无任何元素的关系.它的关系图中只有结点它的关系图中只有结点,无任何边；它的关系矩阵中无任何边；它的关系矩阵中的元素均为的元素均为0。2.完全关系完全关系(全域关系全域关系) ： AB(或或AA)本身也是一个从本身也是一个从A到到B(或或A上上) 的关系，称之为完全关系。的关系，称之为完全关系。即含有全部序偶的关系。它的关系矩阵中的元素均即含有全部序偶的关系。它的关系矩阵中的元素均为为1。3. A上的上的恒等关系恒等关系IA： IA AA，且，且IA =|xA称之为称之为A 上的恒等关系。上的恒等关系。例如例如

17、A=1,2,3, 则则IA =,A上的上的、完全关系及、完全关系及IA的关系图及矩阵如的关系图及矩阵如下：下： MIA =1 0 00 1 00 0 1331。2。31。2。31 1 11 1 11 1 1331。2。30 0 00 0 00 0 033M=MAA=AAIA五五. .关系的运算（关系的运算（1 1）：关系的集合运算）：关系的集合运算由于关系就是集合，所以集合的由于关系就是集合，所以集合的、-、 和和运算对关系也适用。运算对关系也适用。例如，例如，A是学生集合，是学生集合，R是是A上的同乡关系，上的同乡关系，S是是A上的同姓关系，则上的同姓关系，则RS：或同乡或同姓关系：或同乡或

18、同姓关系RS：既同乡又同姓关系：既同乡又同姓关系R-S ：同乡而不同姓关系：同乡而不同姓关系R S：同乡而不同姓：同乡而不同姓,或同姓而不同乡关系或同姓而不同乡关系 R：不是同乡关系：不是同乡关系, 这里这里R=(AA)-R4-3 关系的性质 本节将研究关系的一些性质，它们在关系的研究本节将研究关系的一些性质，它们在关系的研究中起着重要的作用。中起着重要的作用。这是本章最重要的一节这是本章最重要的一节。 本节中所讨论的关系都是集合本节中所讨论的关系都是集合A上的关系。上的关系。 关系的性质主要有：自反性、反自反性、对称关系的性质主要有：自反性、反自反性、对称性、反对称性和传递性。性、反对称性和

19、传递性。一一.自反性自反性定义定义:设设R是集合是集合A中的关系，如果对于中的关系，如果对于任意任意xA都有都有R (xRx)，则称，则称R是是A中自反关系。中自反关系。即即 R在在A中自反中自反x(x AxRx) 例如在实数集合中，例如在实数集合中，“ ”是自反关系，因为，是自反关系，因为，对对任意任意实数实数x，有，有x x. 从关系有向图看自反性从关系有向图看自反性:每个结点都有环。每个结点都有环。从关系矩阵看自反性：主对角线都为从关系矩阵看自反性：主对角线都为1。令A=1,2,3给定A上八个关系如下：1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R

20、1R3R4R5R6R7R8 二二.反自反性反自反性定义定义：设：设R是集合是集合A中的关系，如果对于任中的关系，如果对于任意的意的xA都有都有 R ，则称，则称R为为A中的反中的反自反关系。即自反关系。即R在在A中反自反中反自反x(x A R)从关系有向图看反自反性从关系有向图看反自反性:每个结点都无环。每个结点都无环。从关系矩阵看反自反性：主对角线都为从关系矩阵看反自反性：主对角线都为0。如实数的大于关系如实数的大于关系，父子关系是反自反的。，父子关系是反自反的。注意注意：一个不是自反的关系，不一定就是反：一个不是自反的关系，不一定就是反自反的，如前边自反的，如前边R6、R7非自反非自反,也

21、非反自反。也非反自反。令令A=1,2,3给定给定A上八个关系如下图所示，判断上八个关系如下图所示，判断哪些关系是反自反关系。哪些关系是反自反关系。1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8三三.对称性对称性定义定义:R是集合是集合A中关系中关系,若对任何若对任何x, yA,如如果有果有xRy,必有必有yRx,则称则称R为为A中的对称关系。中的对称关系。 R在在A上对称上对称x y(x A y A xRy) yRx) 从关系有向图看对称性从关系有向图看对称性:在两个不同结点之间，在两个不同结点之间，若有边的话，一定有方向相反的

22、两条边。若有边的话，一定有方向相反的两条边。 从关系矩阵看对称性：是关于主对角线对称从关系矩阵看对称性：是关于主对角线对称 的矩阵。的矩阵。邻居关系是对称关系，朋友关系是对称关系。令A=1,2,3给定A上八个关系如下图所示，判断哪些关系是对称关系。1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8四四.反对称性反对称性定义定义:设设R为集合为集合A中关系中关系,若对任何若对任何x, yA,如果有如果有xRy,和和yRx,就就有有x=y,则称则称R为为A中反对称关系中反对称关系 。R在在A上反对称上反对称x y(x A y A xRy

23、 yRx) x=y)x y(x A y A x y xRy)y x) 由由R的关系图看反对称性：两个不同的结点之间的关系图看反对称性：两个不同的结点之间最多有一条边。最多有一条边。 从关系矩阵看反对称性：关于主对角线对称的从关系矩阵看反对称性：关于主对角线对称的两个元素中最多有一个两个元素中最多有一个1。 Rv思考：思考： 1.是否有关系既不是对称也不是反对称的？是否有关系既不是对称也不是反对称的？ 2.是否有关系既是对称也是反对称的？是否有关系既是对称也是反对称的？令A=1,2,3给定A上八个关系如下图所示，判断哪些关系是反对称关系。是否有既是对称也是反对称的关系。1。2。1。2。1。2。1

24、。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8五五. 传递性传递性定义定义:R是是A中关系，对任何中关系，对任何x,y,zA,如果有如果有xRy,和和yRz, 就就有有xRz, 则称则称R为为A中传递关系。即中传递关系。即 R在在A上传递上传递x y z(x A y A z A xRy yRz)xRz)实数集中的实数集中的、，集合、，集合 、 是传递的。是传递的。 从关系关系图和关系矩阵中不易看清是否有传递性。从关系关系图和关系矩阵中不易看清是否有传递性。必须直接根据传递的定义来检查。必须直接根据传递的定义来检查。 检查时要特别注意使得传递定义表达式的前

25、件检查时要特别注意使得传递定义表达式的前件R R 为为F时表达式为时表达式为T的情况。的情况。 令A=1,2,3给定A上八个关系如下图所示，判断哪些关系是传递关系。1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8本节要求本节要求： 1.准确掌握这五个性质的定义。准确掌握这五个性质的定义。 2.熟练掌握五个性质的判断和证明。熟练掌握五个性质的判断和证明。R是是A中中自反自反的的x(x AxRx)R是是A中中反自反反自反的的x(x A R)R是是A上上对称对称的的x y(x A y A xRy) yRx)R是是A上上反对称反对称的的x

26、 y(x A y A xRy yRx) x=y)x y(x A y A x y xRy)y x)R在在A上上传递传递x y z(x A y A z A xRy yRz)xRz)上述定义表达式都是上述定义表达式都是蕴涵式蕴涵式,所以判断关系所以判断关系R性质时要特性质时要特别注意使得性质定义表达式的前件为别注意使得性质定义表达式的前件为F的时候此表达式的时候此表达式为为T，即，即R是满足此性质的。是满足此性质的。 (自反和反自反性除外自反和反自反性除外)R自反性自反性反自反性反自反性对称性对称性传递性传递性反对称性反对称性每个结点都有环每个结点都有环 主对角线全是主对角线全是1每个结点都无环每个

27、结点都无环 主对角线全是主对角线全是0不同结点间如果有边不同结点间如果有边,则有方向相反的两条则有方向相反的两条边边.是以对角线为对称是以对角线为对称 的矩阵的矩阵不同结点间不同结点间,最多有一最多有一条边条边.以主对角线为对称以主对角线为对称的位置不会同时为的位置不会同时为1如果有边如果有边,则也有边则也有边. 或者定义的前件为假或者定义的前件为假. 如果如果aij=1,且且ajk=1,则则aik=1从关系矩从关系矩阵阵从关系的有向从关系的有向图图 性性质质 判定判定: 下面归纳这八个关系的性质：下面归纳这八个关系的性质：Y-有有 N-无无1。2。1。2。1。2。1。2。3333R2R1R3

28、R4自反性 反自反性 对称性 反对称性 传递性 R1 Y N N Y Y R2 N Y N Y N R3 Y N Y N Y R4 Y N Y Y Y 1。2。1。2。1。2。1。2。3333R5R6R7R8自反性 反自反性 对称性 反对称性 传递性 R5 N Y N Y Y R6 N N Y N N R7 N N N N N R8 N Y Y Y Y 练习练习1:令令I是整数集合，是整数集合，I上关系上关系R定义为：定义为：R=|x-y可被可被3整除整除，（也叫模，（也叫模3同余关系）同余关系）求证求证R是自反、对称和传递的。是自反、对称和传递的。证明证明：证自反性证自反性：任取：任取xI,

29、 (要证出要证出 R )因因 x-x=0, 0可被可被3整除整除,所以有所以有R, 故故R自反。自反。证对称性证对称性：任取：任取x,yI,设设R, (要证出要证出 R ) 由由R定义得定义得 x-y可被可被3整除整除, 即即x-y=3n(nI)， y-x=-(x-y)=-3n=3(-n), 因因-nI, R, 所以所以R对称。对称。证传递性证传递性:任取任取x,y,zI,设设xRy, yRz, (要证出要证出xRz) 由由R定义得定义得 x-y=3m, y-z=3n (m.nI)x-z= (x-y)+(y-z)=3m+3n=3(m+n), 因因m+nI, 所以所以xRz, 所以所以R传递。传

30、递。 证毕证毕 练习练习2：设设R是集合是集合A上的一个自反关系上的一个自反关系,求证：求证： R是对称和传递的，当且仅当是对称和传递的，当且仅当 和和在在R中中,则有则有也在也在R中。中。证明证明：必要性必要性: 已知已知R是对称和传递的。是对称和传递的。 设设 R 又又 R，(要证出要证出 R )因因R对称的故对称的故 R,又已知又已知 R 由传递性由传递性得得 R。所以有如果。所以有如果和和在在R中中,则有则有也在也在R中。中。 充分性充分性: 已知任意已知任意 a,b,c A， 如如和和在在R中中,则有则有也在也在R中。中。先证先证R对称对称：任取任取 a,b A 设设 R，(往往证证

31、 R ) 因因R是自反的是自反的,所以所以 R，由，由 R且且 R，根据已知条件得，根据已知条件得 R ，所以所以R是对称的。是对称的。 再证再证R传递：传递：任取任取 a,b,c A 设设 R， R。(要证出要证出 R )由由R是对称的是对称的,得得 R ，由，由 R且且 R，根据已知条件得，根据已知条件得 R ， 所以所以R是传递的。是传递的。4-4 关系的运算（2）：关系的复合运算 二元关系除了可进行集合并、交、补等运算外，二元关系除了可进行集合并、交、补等运算外，还可以进行一些新的运算。还可以进行一些新的运算。先介绍由两个关系生成一种新的关系，即关系的复先介绍由两个关系生成一种新的关系

32、，即关系的复合运算。合运算。 例如：有例如：有3个人个人a,b,c，A=a,b,c， R是是A上上兄妹兄妹关系，关系， S是是A上上母子母子关系，关系， RS 即即a是是b的哥哥的哥哥, b是是c的母亲，的母亲， 则则a和和c间就是间就是舅舅和外甥舅舅和外甥的关系的关系,记作记作 R S, 称它是称它是R和和S的复合关系的复合关系。 SRabcRS1.1.定义定义:设是设是R从从X到到Y的关系，的关系，S是从是从Y到到Z的关系，的关系，则则R和和S的复合关系记作的复合关系记作R S 。定义为。定义为： R S =|x X z Z y(y Y R S)显然，显然， R S 是从是从X到到Z的关系

33、的关系。2.2.复合关系的计算方法复合关系的计算方法(俗称过河拆桥法俗称过河拆桥法) A=1,2,3 ， B=1,2,3.4 ，C=1,2,3,4,5R AB ， S BC枚举法枚举法R=, S=, 则则 R S=, 有向图法有向图法关系矩阵法关系矩阵法令令A=a1, a2, am ， B=b1, b2, bn， C=c1, c2, ct ， R AB， S BC是逻辑乘：是逻辑乘：00=0， 01=0， 10=0， 11=1是逻辑加：是逻辑加：00=0， 01=1， 10=1， 11=1 。C123。41。2。 3。A1。2。 3。A。B123。4RS5 。C123。45SRc11=(a11

34、b11)(a12b21).(a1nbn1) = (a1kbk1) cij=(ai1b1j)(ai2b2j).(ainbnj) = (aikbkj) (1im, 1jt)MS MR .(aij).(bij).M SR(cij)0 1 0 00 0 1 11 0 0 034。1 0 0 0 01 0 1 0 00 0 0 1 00 1 0 0 1=451 0 1 0 00 1 0 1 11 0 0 0 03 5k=1nk=1n谓词公式法谓词公式法设设I是实数集合，是实数集合，R和和S都是都是I上的关系，定义如下：上的关系，定义如下： R=| y=x2+3x S=| y=2x+3所以所以 R S =

35、| y=2x2+6x+3三三. .性质性质 关系复合运算不满足交换律关系复合运算不满足交换律1. 1. 结合律结合律: : R AB，S BC，T CD 则则TS)(RT)S(Rxx2+3x2(x2+3x)+3 = 2x2+6x+3RSCSR (S T)可以用下图形象表示:ABDRTR SS T(R S) T)证明：任取证明：任取R?(S?T)b(bBR S?T)b(bBR c(cCST)b c(bBR (cCST)c b(cC(bBRS) T)c (cC b(bBRS) T)c (cCR?ST)(R?S)?T所以所以 R?(S?T)= (R?S)?T2. R AB S BC T BC R?(

36、ST)=(R?S)(R?T)R?(ST) (R?S)(R?T)证明证明 任取任取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)证明证明 R?(ST) (R?S)(R?T)任取任取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) x(A(x)B(x) xA(x) xB(x)3. R是从A到B的关系，则 R IB=IA R=R下面

37、列举一例来验证。令A=1,2,3, B=a,b,c,d从这两个图看出它们的复合都等于R。1。2。 3。AIA。Babc。dR1。2。 3。ARIB。abc。d。Babc。d1。2。 3。AB4. 关系的乘幂关系的乘幂 令令R是是A上关系，由于复合运算可结合，所上关系，由于复合运算可结合，所以以关系的复合可以写成乘幂形式。即关系的复合可以写成乘幂形式。即 R R=R2， R2 R=R R2 =R3，一般地 R0 =IA， Rm Rn = Rm+n (Rm)n =Rmn (m,n为非负整数为非负整数)4-5 关系运算（3）：逆关系 逆关系逆关系(反关系反关系)也是我们经常遇到的概念，例也是我们经常

38、遇到的概念，例如如与与就是互为逆关系。就是互为逆关系。一一.定义定义 R是从是从A到到B的关系，如果将的关系，如果将R中的所有序偶的中的所有序偶的两个元素的位置互换，得到一个从两个元素的位置互换，得到一个从B到到A的关系，的关系，称之为称之为R的逆关系，记作的逆关系，记作RC，或，或 R-1。 RC=| R R RC R二二. 计算方法计算方法 1. R=, RC =,2. RC的有向图：是将的有向图：是将R的有向图的所有边的方向的有向图的所有边的方向颠倒一下即可。颠倒一下即可。3. RC的矩阵的矩阵 M =(MR)T 即为即为R R矩阵的转置。矩阵的转置。如如 三三.性质性质令令R、S都是从

39、都是从X到到Y的关系，则的关系，则 1. (RC)C = R 2. (RS)C = RCSC 。 3. (RS)C = RCSC 。 4. (RS)C = RCSC 。RC1 0 11 0 1 00 0 0 11 0 1 1MR=340 0 01 0 10 1 1MR =c 43证明证明2. (RS)C = RCSC 任取任取 (RS)C，则，则 (RS)C RS R S RC SC RCSC所以所以 (RS)C = RCSC ，其它类似可证。其它类似可证。5.(R)C=RC证明证明:任取任取(R)C R R RC RC 所以所以 (R)C=RC6.令令R是从是从X到到Y的关系，的关系，S是是

40、Y到到 Z的关系，则的关系，则 (R?S)C= SC?RC 。 (注意注意RC?SC )证明证明：任取任取(R?S)C R?Sy(yYRS) y(yYSCRC) SC?RC 所以所以 (R?S)C= SC?RC 7. R S RC SC 。证明：充分性证明：充分性，已知，已知RC SC ，则任取，则任取RR RC SC S 所以所以 R S 必要性必要性，已知，已知R S，则任取，则任取RC ，RC R S SC 所以所以 RC SC8. R是是A上关系，则上关系，则 R是对称的，当且仅当是对称的，当且仅当 RC =R R是反对称的，当且仅当是反对称的，当且仅当 RRC IA。 证明证明 充分

41、性充分性：已知：已知 RC =R (往往证证R对称对称) 任取任取 x,y A，设设 R，则，则 RC， 而而RC =R ，所以有，所以有 R ，所以，所以R对称。对称。必要性必要性：已知：已知R 对称，对称，(往证往证RC =R)先证先证RC R，任取任取RC，则，则 R，因因R对称，所以有对称，所以有R，所以，所以 RC R。再证再证R RC，任取任取 R，因，因R对称，所以有对称，所以有R，则，则RC，所以，所以 R RC。最后得最后得RC =R 。证明证明 R是反对称的，当且仅当是反对称的，当且仅当 RRC IA充充分性：分性：已知已知RRC IA，(往往证证R反对称反对称) 任取任取

42、 x,y A，设设 R 且且R， RR RRC， RRC IA (因因RRC IA )x=y 所以所以 R反对称。反对称。必要性必要性：已知：已知R反反对称，对称，(往证往证RRC IA) 任取任取 RRC RRC R RC R Rx=y (因因R反对称反对称) IA 所以所以 RRC IA 。第第4-3和和4-4节的节的要求要求：熟练掌握求复合关系和逆关系的计算方法熟练掌握求复合关系和逆关系的计算方法及性质。及性质。4-6 关系的运算（4）： 关系的闭包运算这里要介绍这里要介绍关系的自反闭包关系的自反闭包、对称闭包对称闭包和和传递闭包传递闭包一一. .例子例子 给定给定 A中关系中关系R，如

43、图所示，如图所示，分别求分别求A上另一个关系上另一个关系R，使使得它是包含得它是包含R的的“最小的最小的”(序偶序偶尽量少尽量少) 具有自反具有自反(对称、传递对称、传递)性的关系性的关系。这这个个R就是就是R的的自反自反(对称、传递对称、传递)闭包。闭包。这三个关系图分别是这三个关系图分别是R的的自反、对称、传递闭包自反、对称、传递闭包1。2。31。2。31。2。31。2。3二二. .定义定义：给定：给定 A中关系中关系R，若，若A上另一个关上另一个关系系R ，满足：，满足： R R ； R 是自反的是自反的(对称的、传递的对称的、传递的)； R 是是“最小的最小的”， 即对于任何即对于任何

44、A上自反上自反(对称、传递对称、传递)的关系的关系R ，如果如果 R R ，就有就有R R。则称则称R 是是R的的自反自反(对称、传递对称、传递)闭包。闭包。记作记作r(R)、(s(R) 、t(R) 。 (reflexive、 symmetric、transitive)实际上实际上r(R)、(s(R) 、t(R) 就是包含就是包含R的的“最小最小”的的自反自反(对称、传递对称、传递)关系。关系。三三. .计算方法计算方法定理定理1.给定给定 A中关系中关系R,则则 r(R)=RIA。证明：令证明：令R=RIA，显然显然R是自反的是自反的且且R R，下面证明下面证明R是是“最小的最小的”：如果有

45、如果有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 ； 再再证证R是传递的：是传递的：任取任取x,y,z A，设有设有 R且且 R， 由由R定义得必存在定义得必存在整数整数 i,j 使得使得 Ri ， Rj ，根据关系的复合得根据关系的复合得

46、 Ri+j， 又因又因Ri+j R，所以所以 R，所以所以R传递传递。再证再证R是是“最小的最小的”：如果有：如果有A上传递关系上传递关系R”且且 R R”，（往证，（往证R R”）任取任取 R，则由则由R定义得必存在整数定义得必存在整数i，使得使得 Ri ，根据关系的复合根据关系的复合定义，定义，A中必存在中必存在i-1个元素个元素e1, e2,.,ei-1，使得使得 R R. R。因因R R”，所以有所以有 R” R”. R”。由于由于R”传递，传递，所以有所以有 R”。因此因此 R R”。综上所述综上所述，R就是就是R的传递闭包，即的传递闭包，即 t(R)=RR2R3=Rii=1用上述用

47、上述公式计算公式计算t(R)，要计算要计算R的无穷大次幂的无穷大次幂，好好象无法实现。其实不然，请看下例象无法实现。其实不然，请看下例:A=1,2,3 A中关系中关系R1,R2,R3,如下：如下：R1=,R2 =,R3 =, = = = 所以所以t(R1)= = R1 =, =, =IA, = R2 .t(R2)= R2 =, = t(R3)= R2 2R13R14R11R12R13R12R23R24R23R22R23R23R32R32R32R3定理定理4. 给定给定 A中关系中关系R，如果如果A是有限集合，是有限集合，|A|=n则则 t(R)=RR2.Rn 。证明：令证明：令R=RR2R3.

48、, R”=RR2.Rn下面证明下面证明R=R” ，显然有显然有R” R。下面证明。下面证明R R”：任取任取 R，由由R定义得定义得 必存在必存在最小的最小的正整数正整数i 使得使得 Ri ，(下面证明下面证明in) 如果如果in，根据关系的复合根据关系的复合定义，定义，A中必存在中必存在i-1个元素个元素e1, e2,.,ei-1，使得使得 R R. R。上述元素序列上述元素序列：x=e0, e1, e2,.,ei-1, y=ei 中共有中共有i+1个元素，个元素，i+1n , 而而A 中只有中只有n个元素个元素，所以上述元素中至少有两个，所以上述元素中至少有两个相同，设相同，设ej=ek

49、(jk)，于是于是R的关系图中会有下面这些边：的关系图中会有下面这些边：于是有于是有 R R. R R . R 所以所以 Ri-(k-j)，i-(k-j)i，与与i是是最小的最小的矛盾。矛盾。所以所以in，所以所以R”，于是于是 R R”。综上综上 R=R”，所以，所以 t(R)=RR2.Rn 定理证毕。定理证毕。 。 。 。xe1ej-1ej =ekej+1。.。ej+2ek-1ek-2ek+1ek+2.ei-1y求求t(R)的矩阵的矩阵Warshall算法：算法：|X|=n, R XX, 令令MR=A R2的矩阵为的矩阵为A2， Rk的矩阵为的矩阵为Ak .于是于是t(R)的的矩阵记作矩阵

50、记作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, 则转到步骤则转到步骤，否则停止。，否则停止。下面举例，令下面举例，令X=1,2,3,4,X中关系中关系R图如右图所示。图如右图所示。运行该算法运行该算法求求t(R)的矩阵的矩阵：1。2。43i=1 (i-列列, j-行行) A4,1=1 1行行+4行行4行行i=2 A1,2=1 ,1行行+2行行1行行 A2,2=

51、1 ,2行行+2行行2行行 A不变不变 A4,2=1 ,4行行+2行行4行行,4行全行全1, A不变不变i=3 A1,3=1,1行行+3行行1行行, 3行全行全0, A不变不变 A2,3=1,2行行+3行行2行行, 3行全行全0, A不变不变 A4,3=1,4行行+3行行4行行, 3行全行全0, A不变不变i=4 A1,4=1 ,1行行+4行行1行行 A4,4=1 ,4行行+4行行4行行 A不变不变,最后最后 A=Mt(R)1101000001101010A=MR=A=1111000001101010A的初值:A=1111000001101110A=1111000001101111四四. .性

52、质性质定理定理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)I

53、A=(RRC)IA= (RIA)RC=r(R)RC =RRC =s(R)s(R)自反自反 类似可以证明类似可以证明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 结论成立。结论成立。 假设

54、假设i=k 时结论成立，即时结论成立，即 (RIA)k= IARR2.Rk可用归纳法可用归纳法证明证明(Ri)c=(Rc)i当当i=k+1时时(RIA)k+1=(RIA)k (RIA) = (IARR2.Rk） (IAR) = (IARR2.Rk)(RR2.Rk+1) = IARR2.RkRk+1所以结论成立所以结论成立.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)也传递。也传递。 。定理定理7：设：设R1、R2是是A上关系

55、，如果上关系，如果R1 R2 ，则，则 r(R1) r(R2) s(R1) s(R2) t(R1) t(R2) 证明证明 r(R1)=IAR1 IAR2= r(R2) ，类似可证。，类似可证。定理定理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很容易证明，这里从略。很容易证明，这里从略

56、。 证明证明st(R) ts(R) 因因 R s(R) 由定理由定理7得得 t(R) ts(R) st(R) sts(R) 因因s(R)对称，有定理对称，有定理6得得ts(R) 也对称，由定理也对称，由定理5得得sts(R)=ts(R) 所以有所以有st(R) ts(R) 。通常将通常将t(R) 记成记成R+， tr(R)记成记成R*，即即 t(R)= R+=RR2.Rn= tr(R)=rt(R) =R*= R0RR2.Rn=练习练习：给定：给定A中关系中关系R如图所示：分别画出如图所示：分别画出r(R)、s(R) 、t(R)、sr(R)、rs(R)、 tr(R)、rt(R)、st(R) 、t

57、s(R) 的图。的图。1。2。43Rii=1Rii=01。2。431。2。431。2。431。2。431。2。431。2。431。2。431。2。431。2。43r(R)s(R)t(R)sr(R)rs(R)tr(R)rt(R)st(R)ts(R)本节重点掌握闭包的定义、计算方法和性本节重点掌握闭包的定义、计算方法和性质。质。作业作业 第第127页页 、4-7 集合的划分与覆盖图书馆的图书，要分成许多类存放，学校的学生图书馆的图书，要分成许多类存放，学校的学生要按照专业分成许多班，要按照专业分成许多班，即对集合的元素划分即对集合的元素划分一一. .定义定义 设设X是一个非空集合，是一个非空集合，

58、A=A1, A2,. ,An, Ai 且且 Ai X (i=1,2,.,n)，如果满足，如果满足A1A2.An =X 则称则称A为集合为集合X的覆盖的覆盖。 设设A=A1, A2,.,An是是X一个覆盖，一个覆盖，且且Ai Aj= (i j,1i,jn)，则称则称A是集合是集合X的划分。的划分。每每个个Ai均称为这个划分的一个划分块均称为这个划分的一个划分块(类类)。例例 X=1,2,3, A1=1,2,3, A2=1,2,3,A3=1,2,3, A4=1,2,2,3, A5=1,3A1, A2 ,A3 ,A4 是覆盖。是覆盖。 A1, A2 ,A3也是划分。也是划分。划分一定是覆盖；但覆盖划

59、分一定是覆盖；但覆盖, 不一定是划分。不一定是划分。二二. .最小划分与最大划分最小划分与最大划分最小划分最小划分：划分块最少的划分。即只有一个划分：划分块最少的划分。即只有一个划分块的划分，块的划分，这个划分块就是这个划分块就是X本身本身。如。如A1 。最大划分最大划分：划分块最多的划分。：划分块最多的划分。即每个划分块里即每个划分块里只有一个元素的划分只有一个元素的划分。如。如A2 。 A1,A2,A3是一种划分是一种划分,其中其中A1是最小划分是最小划分,A2是最是最大划分。大划分。三三. .交叉划分交叉划分 例例 X是东大学生集合是东大学生集合, A和和B都是都是X的划分：的划分：A=

60、M,W,M X, W X, M=男生男生,W=女生女生B=L,N,L X, N X, L=辽宁人辽宁人,N=非非辽宁人辽宁人C=LM , LW , NM , NW 称称C是是X的交叉划分。的交叉划分。MWLNLMLWNMNW辽宁男生辽宁女生非辽宁男生非辽宁女生定理：定理：若若A=A1, A2,. ,Am与与B=B1,B2,.,Bn都是集合都是集合X的的划分，由其中所有的划分，由其中所有的Ai Bj(i=1m, j=1n)组成集合组成集合C, 则则C亦为集合亦为集合X的划分，称为的划分，称为A与与B的交叉划分的交叉划分. 证明：设证明：设 C=A1 B1,A1 B2,.,A1 Bn, A2 B1