离散数学第4章-二元关系

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

1、第四章 关系,4.1 二元关系 4.2 关系的性质 4 .3 关系的运算 4 .5 关系的闭包 4.6 等价关系与划分,4.1 二元关系,一 定义4.1（二元关系） 设A和B是任意两个集合，AB的子集R称为从A到B的二元关系。当A=B时，称R为A上的二元关系。若(a, b)R，则称a与b有关系R，记为aRb。 (a, b)R：a与b没有关系R R=：空关系 R=AB：全关系,4.1 二元关系,二 定义4.2（定义域，值域） 设R是从A到B的二元关系，A的一个子集a|存在b，使得(a, b)R称为R的定义域，记为Dom R。B的一个子集b|存在a，使得 (a, b)R称为R的值域，记为Ran R

2、。 A称为R的前域，B称为R的培域，并且Dom RA，Ran RB。,4.1 二元关系,三 定义4.3 （n元关系） 设A1,An是n个任意集合，定义A1An的子集R为A1,An的n元关系。 当A1=An时，R称为A上的n元关系。,4.2 关系的性质,一 定义4.4(关系的性质) 设R是集合A上的二元关系。 (1)如果对任意aA，有aRa，则称R是自反的。 (2)如果对任意aA，有(a, a)R，则称R是反自反的。 (3) 对任意a, bA，如果aRb必有bRa，则称R是 对称的。 (4)对任意a, bA，如果aRb且bRa，必有a=b，则称R是反对称的。 (5)对任意a, b, cA，如果a

3、Rb且bRc，必有aRc，则称R是传递的。,4.2 关系的性质,二 定义4.5（关系矩阵） 设A和B是两个有限集A=a1, , am，B=b1, , bn，R是从A到B的二元关系，称m n阶矩阵MR=(mij)为R的关系矩阵，其中 若(ai, bj)R， mij =1 若(ai, bj) R，mij =0,4.2 关系的性质,三 关系图 设A=a1, , an，R是A上的二元关系。A中每个元素ai用一个点表示，称该点为顶点ai 。 如果ai R aj，则从顶点ai到顶点aj存在一条弧。 如果ai R ai，则从顶点ai到顶点ai存在一条封闭弧。 这样表示R中关系的图形，称为R的关系图。,4 .

4、3 关系的运算,定义4.6 设R1和R2是从A到B的两个二元关系，对于aA，bB，定义： R1R2：a(R1R2)b aR1b或aR2b； R1R2：a(R1R2)b aR1b且aR2b； R1-R2： a(R1-R2)b aR1b且(a, b)R2; 1：a 1b(a,b)(AB)-R1。,4 .3 关系的运算,一 逆运算 定义4.7（逆关系） 设R是从A到B的二元关系，则从B到A的二元关系记为R-1，定义为R-1 =(b,a)|(a,b)R，称为R的逆关系。 定理2.1 （1）(R-1)-1=R; （2）(R1R2)-1= R1-1 R2-1; （3）(R1R2)-1= R1-1 R2-1

5、; （4） (AB)-1= BA；,4 .3 关系的运算,定理4.1 （5）-1=； （6）()-1= AB-R-1; （7） (R1-R2)-1= R1-1-R2-1； （8）若R1R2，则R1-1 R2-1 。 证明,4 .3 关系的运算,定理4.2 R是A上的二元关系，则R是对称的R=R-1。,4 .3 关系的运算,二 复合运算 定义4.8（复合关系） 设R1是从A到B的二元关系， R2是从B到C的二元关系，则从A到C的二元关系记为R1R2，定义为R1R2 =(a, c) | aA, cC, 且存在bB使(a, b) R1, (b, c) R2称为R1和R2的复合关系。 定理4.3（结合

6、律） (R1R2)R3 = R1(R2R3) 不满足交换律,4 .3 关系的运算,三 幂运算 定义4.9（幂运算） 设R是A上的二元关系，nN，R的n次幂记为Rn，定义如下： (1) R0是A上的恒等关系（即R0 =(a, a)|aA），记为IA，又R1=R； (2)Rn+1= RnR。 定理4.4 (1) Rm Rn=Rm+n (2) (Rm)n= Rmn,4.4 关系数据库,表格 线性表 关系数据库 属性 键,4 .5 关系的闭包,一 自反，对称，传递闭包 定义4.11（自反，对称，传递闭包） 设R是A上的二元关系，定义R的自反（对称，传递）闭包记为 R，满足下列三个条件： （1）R是自反

7、的（对称的，传递的）； （2）RR； （3）对任一自反（对称，传递关系）R”，RR”，则RR”。 分别记为r( R )，s( R )，t( R )。,4 .5 关系的闭包,二 基本性质 定理4.5 设R是A上的二元关系，则 R是自反的 r( R )=R； R是对称的 s( R )=R； R是传递的 t( R )=R； 定理4.6 设R1和R2是A上的二元关系，若R1R2则 r(R1) r(R2)； s(R1) s(R2)； t(R1) t(R2)。,4 .5 关系的闭包,三 计算 定理4.7 r(R)=RIA 定理4.8 s(R)=RR-1 定理4.9 t(R)=RR2R3 定理4.10 R是

8、A上的二元关系，且|A|=n，则t(R)=RR2R3Rn,4 .5 关系的闭包,四 其他性质 定理4.11 设R是A上的二元关系。 若R是自反的，则s( R )和t( R )都是自反的； 若R是对称的，则r( R )和t( R )都是对称的； 若R是传递的，则r( R )是传递的。 定理4.12 设R是A上的二元关系。 rs( R )=sr( R ) rt( R )=tr( R ) ts( R ) st( R ),4.6 等价关系与划分,一 等价关系与划分 定义4.12（划分） 设A是一个集合。AiA, Ai , i=1, , n。若A1 A2 An=A， Ai Aj=（i, j=1, n,

9、ij），则称=A1, A2, , An是A的一个划分。其中每个Ai称为划分的一个块。 定义4.13（等价关系）设R是A上的二元关系，若R是自反的、对称的和传递的，则称R是A上的等价关系。若aRb，则称a与b等价。,4.6 等价关系与划分,二 术语 定义4.14（等价类） 设R是A上的等价关系，对于每个aA，与a等价的元素全体所组成的集合称为由a生成的关于R的等价类，记为aR，即 aR =x| xA，xRa，a称为该等价类的代表元。 aR简记为a。 定义4.15（商集）设R是A上的等价关系，关于R的等价类全体所组成的集合族称为A上关于R的商集，记为A/R，即A/R=a| aA。,4.6 等价关系

10、与划分,三 性质 定理4.13 设R是A上的等价关系，则 （1）对任一aA，有aa； （2）对a, bA，如果aRb，则a=b; （3）对a, bA，如果(a, b)R，则ab=; （4）aAa=A。,4.6 等价关系与划分,定理4.14 集合A上的任一划分可以确定A上的一个等价关系R。 定理4.15 设R1和R2是A上的等价关系， R1=R2 A/R1=A/R2 。 定理4.16 设R1和R2是A上的等价关系，则 R1R2是A上的等价关系。,4.7 次序关系,一 偏序关系、偏序集 定义4.19(偏序关系) 设R是A上的二元关系，若 R是自反的、反对称的和传递的，则称R是A上的偏序关系。又记为

11、。（并不意味小于等于） 定义4.20(偏序集) 若集合A具有偏序关系R（或 ），则称A为偏序集，记为（A, R）或（A, ）。 哈斯图：表示偏序集。若a b，则结点a在b之下；若a与b之间不存在其他元素c，使a c，c b则在a与b之间用一线相连。,4.7 次序关系,例4.29 例4.30,4.7 次序关系,二 拟序关系 定义4.21（拟序关系） A上的二元关系 R是反自反的和传递的，称R为A上的拟序关系。称(A, R)为拟序集，或记为(A, )。（不意味着小于） 定理4.22 A上的二元关系 R是拟序的，则R必为反对称的。 证明：反证法,4.7 次序关系,定理4.23 设R是A上的二元关系，

12、则 (1)若R是A上的拟序关系，则r(R)=RIA是A上的偏序关系； (2) R是A上的偏序关系，则R-IA是A上的拟序关系；,4.7 次序关系,三 全序关系 定义4.22（全序关系） 设是集合A A上的二元关系，如果对于A中任意两个元素a, bA，必有a b或b a，则称 是A上的全序关系（或线性次序关系）。 定义4.23（全序集） 若集合A具有全序关系 或R），则称A为全序集或线性次序集，记为(A, )或(A, R) 。,4.7 次序关系,四 最大元、最小元、极大元、极小元 定义4.22（最大元、最小元、极大元、极小元） (1)最大元、最小元 若存在一个元素bB，对所有bB都有b b，则称

13、b是B的最大元；若都有b b，则称b是B的最小元； (2)极大元、极小元 若存在一个元素bB，且在B中不存在元素b使bb，b b，则称b是B的极大元；若在B中不存在元素b使bb，b b ，则称b是B的极小元；,4.7 次序关系,(3)上界、下界 若存在一个元素aA，对所有bB都有b a，则称a是B的上界；对所有bB都有a b，则称a是B的下界； (4)上确界、下确界 若aA是B的上界且对B的每个上界a都有a a，则称a是B的上确界（最小上界）；若aA是B的下界且对B的每个下界a都有a a，则称a是B的下确界（最大下界）。,4.7 次序关系,定理4.24 设偏序集(A, )，BA，若在B中存在最

14、大元（最小元），则必唯一。 证明： （反证） 定理4.25 设偏序集（A, ）, BA，在B中存在最大元（最小元）必为极大元（极小元）。,数学教育对计算机科学专业人才的培养目的,通过教学使学生掌握进一步学习这一学科所需要的数学知识； 通过严格的数学训练，使学生实现思维方式或思维过程的数学化。,思维方式的数学化,从普通人的思维方式转向数学家工作的思维方式： 通过对事物的抽象，运用特殊的符号或语言系统，研究事物在空间中的数量关系、位置关系、结构关系和变换规律，研究具有共同抽象概念、性质的一类事物的某些内在规律，以此指导人们从另一个侧面去认识事物。,实现思维方式数学化的步骤,第一阶段 通过对数学分析

15、、高等代数、概率统计等数学课程的学习，使学生熟悉和习惯于使用数学语言和符号系统对研究的数学对象进行严格的分析、表述、计算和推演，初步实现思维方式的数学化。,实现思维方式数学化的步骤,第二阶段 数学学习转向以计算机科学为背景的离散数学和理论计算机科学的学习，特别是通过对数理逻辑系统的学习，使学生思维方式逐步上升为系统的理性思维方式,建议使用国内外优秀教材 习题应全部作。,习题解析（一）,关系的性质 1）举出A=1, 2, 3上关系R的例子，使其具有下述性质： a) 既是对称的，又是反对称的； b) 既不是对称的，又不是反对称的； c) 是传递的。 2）举出一个集合上关系的例子，分别适合于自反，对称，传递中的两个且仅适合两个。,习题解析（一）,3）如果关系R和S是自反的，对称的和传递的，证明RS也是自反的，对称的和传递的。 4）设R1和R2是A上的二元关系，说明以下命题的真假： a) 若R1和R2是自反的，则R1 o R2是自反的; b) 若R1和R2是反自反的，则R1 o R2是反自反的; c) 若R1和R2是对称的，则R1 o R2是对称的; d) 若R1和R2是传递的，则R1 o