第三章集合与关系

1、第二编 集合论 集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。 在现代数学中，每个对象（如数、函数等）本质上都是集合，都可以用某种集合来定义。数学的各个分支，本质上都是在研究这种或那种对象的集合的性质。集合论已成为全部现代数学的理论基础。第二编 集合论 集合论的特点是研究对象的广泛性。它总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。因此，集合论被广泛地应用于各种科学和技术领域。第二编 集合论 由于集合论的语言适合于描述和研究离散对象及其关系，所以也是计算机科学与工程的理论基础，在程序设计、关系数据库、排队论、开关理论，形式语言和自动机理论等学科

2、领域中都有重要的应用。 本篇主要介绍：集合、二元关系和函数，以及集合的基数问题。 第三章 集合与关系 3.1 集合概念和表示集合概念和表示3.2 集合的运算集合的运算3.3 序偶与笛卡尔积序偶与笛卡尔积3.4 关系及其表示关系及其表示3.5 关系的性质关系的性质3.6 复合关系和逆关系复合关系和逆关系3.7 关系的闭包运算关系的闭包运算 3.8集合划分和覆盖集合划分和覆盖3.9等价关系与等价类等价关系与等价类3.10相容关系相容关系3.11序关系序关系第三章 集合与关系 教学目的及要求教学目的及要求： 深刻理解和掌握有关集合和关系的基本概念和基本运深刻理解和掌握有关集合和关系的基本概念和基本运

3、算。算。 教学内容教学内容： 集合的概念与表示、集合的运算、序偶与笛卡尔积、集合的概念与表示、集合的运算、序偶与笛卡尔积、关系及表示、关系的性质、复合关系和逆关系、关系关系及表示、关系的性质、复合关系和逆关系、关系的闭包运算、等价关系与等价类、序关系。的闭包运算、等价关系与等价类、序关系。 教学重点教学重点：关系及关系的运算、等价关系、序关系。：关系及关系的运算、等价关系、序关系。 教学难点教学难点：关系的闭包运算、等价关系、等价类。：关系的闭包运算、等价关系、等价类。3.1 集合的概念和表示法1、集合与元素（1）集合：具有某种特殊性质的客体的聚合。讨论：一些不同的确定的对象之全体。客体：是泛

4、指一切，可以是具体的、抽象的元素（成员）：属于任何集合的任何客体。符号：用大写英文字母A，B.表示集合，用小写英文字母a，b.或其它符号表示元素。元素与集合间的关系： a是集合S中的元素，则写成a S ；b不是集S合中的元素，则写成b S 。3.1 集合的概念和表示法集合S的基数(势)：S中的元素个数。用|S|表示。有限集合：集合的基数（元素）是有限的。 无限集合：集合的基数（元素）是无限的。本书中常用集合符: Im(m1) 有限个正数的集合1,2,3m Nm(m0) 有限个自然数的集合0,1,2m 以上是有限集合,下面是无限集合：3.1 集合的概念和表示法N 自然数集合 0,1,2I+ 正整

5、数集合 1,2,3I 整数集合 -1,0,1,2P 素数集合 大于1的正整数，只能被1和自己整除Q 有理数集合 i/j, i、j均为整数且j0R 实数集合 有理数、无理数C 复数集合 a+bi，a、b可为实数, i= -1 3.1 集合的概念和表示法(2)集合的表示方法:(a)枚举法 (列举法) 把集合的元素列于花括号内。 例： 命题的真假值组成的集合：S=T,F 自然数0,1,2,3,4五个元素的集合：P=0,1,2,3,4(b)谓词公式描述法 所有集合均可用谓词公式来表示：S=x | p(x) 例： 3.1 集合的概念和表示法 大于10的整数的集合：S1=x | x I x10 偶整数集合

6、：S2=x | y (y I x=2y) 有限个元素集合： S3=1,2,3,4,5=x | x I (1 x 5) S4=F,T=x | x=T x=F S5=1,4= x | (x-5x+4=0) (c)同一集合可以用多种不同的形式表示。(d)集合也可作为某一集合的元素。 例：S=a,1,2,p,q 3.1 集合的概念和表示法(3)三个特殊集合 全集:如果一个集合包含了所要讨论的每一个集合，则称该集合为全集合，简称全集，用E表示。 E=x | p(x) p(x) p(x)为任何谓词公式 空集:不拥有任何元素的集合称为空集（或称零 集），用表示, =x | p(x) p(x) = 注意, 前

7、者是空集，是没有元素的集合；后者是以作为元素的集合。 集合族:集合中的元素均为集合，称这样的集合为集合族。例A=a，b，c、d3.1 集合的概念和表示法2、集合之间的关系 相等:给定二个集合A和B，当且仅当A和B具有同样的元素（成员），则A和B相等，记作A=B, 并规定 ：（A=B）x (x A x B) 例：a, b, c=b, a, a, c, c 例：设P=1,2,4，Q=1,2,4，则P Q3.1 集合的概念和表示法 包含:设A、B是任意二个集合，如果集合A的每一个元素都是B的一个元素，则称A是B的子集，或者说A包含于B，或者说B包含A，记作 A B，或者B A。并规定： A BB A

8、x(x A x B) 例：A1=1,2,3 A2=0 A3=1,2,3,0 B=1,2,3,0 则A1、A2、A3均为B的子集合，并记为 A1 B，A2 B，A3 B3.1 集合的概念和表示法真包含:设A、B是任意二个集合，若A B且AB，则称 A是B的真子集，记作A B（A真包含于B）,并规定：A B（A B AB）注意区分“ ”和“ ”的关系： “ ”关系是指集合和该集合中元素间的关系。 例：S=a,b,c 则a S，b S，c S 而“ ”关系是指二个集合之间的关系。 例：S1=a, b S2=a,b,1,2 则S1 S2 若A不包含于B，则也可表示成A B3.1 集合的概念和表示法 定

9、理 设E是全集，A是一个集合，则一定有A E。证明： x（x A x E） 而x E始终为“T”，所以x A x E一定为“T”故有 x（x A x E）为“T”，则有A E3.1 集合的概念和表示法 定理 设A、B是任意二个集合，当且仅当A B和B A 才有A=B。证明：()充分性：（A=B）（A B B A） (A=B)x (x A x Bx B x A) x(x A x B) x(x B x A) (A B)(B A) ()必要性：A BB AA=B (A B)(B A)x(x A x B) x(x B x A) (A=B)3.1 集合的概念和表示法推论对于任一集合A，则有A A。定理设

10、A、B、C是任意集合，如果A B和B C，则A C 。推论若A B和B C，则A C 。3.1 集合的概念和表示法 定理 设有空集和任一集合A，则A证明：设x A，要证明A，只要证：（ x）(x x A)为“T”中没有元素，x为假，（ x）（x x A）为“T” 定理 是唯一的。证明：设有二个空集合1和2 是任何集合的子集（1 22 1） (1=2) 3.1 集合的概念和表示法3、幂集和索引集合 （1）幂集： 例：S1=a 则子集为，a S2=1，2 则子集为，1，2，1，2 S3= 则子集有（而不是） 由此可见,给定一个集合S,则和S一定是S的子集。 3.1 集合的概念和表示法 幂集:设A是

11、集合，A的所有子集（作为元素）的集合称为A的幂集,记作(A)或2A ,且有： (A)(=2A)=x | x A 例： 若A1=，则(A1)= 若A2=a，则(A2)=，a 若A3=1，2,则(A3)=，1，2，1，2 3.1 集合的概念和表示法讨论：(a)集合的元素个数称为集合的“基数”或叫“势” |(S)|=2 |s| 为幂集(S)的基数(b)若A为有限集合，则(A)也为有限集合。 若A为无限集合，则(A)也为无限集合。(c)一定有A (A)， (A)，即对非空集合，在幂集中至少有两个子集和A。 3.1 集合的概念和表示法（2）索引集合 为了在计算机上表示集合，必须给每一个集合的元素加上标记

12、，以用来表示元素在集合中的位置。例：S1=a，b 假设集合S1中，a,b的位置已经固定。则用二进制下标法来表示S的所有子集：= =B= =B0000，a=Ba=B1010，b=Bb=B0101，aa，b=Bb=B1111这样(S1)=B(S1)=B0000，B B0101，B B1010，B B1111=B=Bi i | i | i J J 而其中J=00J=00，0101，1010，1111（索引集合或指标集合） 3.1 集合的概念和表示法例： 已知集合S=a1，a2，a3，a4，a5，a6，S的子集有26 个,可以分别表示成B0，B1B( 26-1)则B7=B000111=a4，a5，a6

13、 B15=B001111=a3，a4，a5，a6 B22=B010110=a2，a4，a5等等3.2 集合的运算 1.交集（交运算）交集:二个集合A和B的交集AB是由A和B所共有的全部元素构成的集合，即： AB=x | x A x B 例：A=a，b B=a，c AB=a 定理 集合的相交运算是可交换的和可结合的，即对于任何集合A，B，C有 AB=BA，（AB）C=A（BC）证明：设x是AB中任一元素 则x ABx x | x A x Bx x | x B x Ax BA AB=BA 3.2 集合的运算 定理 设A是E的任一子集，则有 （1）AA=A （2）A= （3）AE=A不相交:A、B是

14、二个集合，若AB=，则称A和B 是不相交的，或者说A和B没有相同的元素。 若C是一个集合族 （集合族：元素均为集合 的集合）使C的任何二个元素都不相交，则 称C为不相交的集合族。 例：A=a，b，c A为不相交的集合族 3.2 集合的运算2.并集（并运算） 定义 A、B是任意二个集合，A和B的并集AB是 由A和B的所有元素构成的集合，即： AB=x x Ax B。例：A=a, b, c B=1,2,3 则 AB=a,b,c,1,2,3 定理 集合的并运算是可交换的和可结合的，即对 任何A，B，C,有 AB=BA和（AB）C=A（BC） 3.2 集合的运算 定理 集合的并和交运算，每一个对另一个

15、都是可 分配的。即： (1)A（BC）=（AB）（AC） (2)A（BC）=（AB）（AC） 定理 设A、B、C是全集E的任意子集，则有： (1)AA=A (2)A=A (3)AE=E3.2 集合的运算3.相对补集： 定义 设A和B是二个任意集合，B对A的相对补 集（A-B）是由A中且不属于B的所有元素 组成的集合。即： A-B=xx Ax B=xx A x B例：设A=0，1，2 B=2，3，4 则 A-B=0,1 B-A=3，4注意，A-BB-A。3.2 集合的运算 定理 设A，B，C，D是E的子集，则有： (1 )A-B A， (2 )若A B和C D，则AC BD， (3 )若A B和

16、C D，则AC BD， (4 ) 若A AB，则 B AB (5 ) 若AB A，则AB B (6 ) 若A B，则AB=B (7 ) 若A B，则AB=A (8 )A-=A (9 )A(B-A)= (10)A(B-A)=AB3.2 集合的运算 (11)A-（BC）=（A-B）（A-C） (12)A-（BC）=（A-B）（A-C）4、绝对补集（补运算 ） 定义 设E是全集，任一集合A对E的相对补集称 为A的绝对补集（或称补集）记作A（或 A）。即： A=E-A=x| x Ex A=x| x A例：设E=a，b，c，d A=a，b 则 A=c，d 3.2 集合的运算 定理 A是E的任一子集，则有

17、 (1)A A=E (2)A A= 定理 设A、B是E的二个子集，当且仅当 AB=E和AB=才有B= A（或A= B）证明： () 充分性：B= A （AB=E）（AB=）B=A AB=AA=E AB=AA=成立3.2 集合的运算 ()必要性： (AB=E)(AB=)B=A B=EB=(AA)B =(AB)(AB) =（AB） =（AA）（AB） =A（AB） =AE=A 3.2 集合的运算补集的性质：（1）（A）=A（2）（AB）=AB（3）（AB）=AB（4）=E（5）A-B=AB 例：设A=2，5，6，B=2，3，4，C=1，3，4， E=1，2，3，4，5，6则A-B=5，6=AB =

18、2，5，61，5，6=5，63.2 集合的运算5、环和(对称差) 定义 设A、B是任意二集合，A和B的环和记作 A B。即： A B=(A-B)(B-A)=(AB)(BA) 或者x(A B)xx |xAxB 例：设A=2，5，6，B=2，3，4 则 AB=3，4，5，6 3.2 集合的运算对称差的性质：(1)AB=BA (可交换)(2)(AB)C=A(BC) (可结合)(3)AB=(A-B)(B-A) =(AB)(BA)=(AB)(AB)(4)AA=(5)A=A(6)AB=(A(B)(B(A) =(AB)(BA)=(B-A)(A-B)=AB(7)A(BC)=(AB)(AC) (对可分配)3.2

19、 集合的运算6、文氏图(1)文氏图的画法规则： 规定矩形表示E。子集用圆画在E中。(2)文氏图应用：（a）表示集合和运算的关系 可用文氏图画出各种运算：（b）证明集合恒等式例：A（BC）=（AB）（AC）3.3 序偶与笛卡尔乘积 1.序偶： 定义 由二个具有给定次序的客体所组成的序列称 为序偶。记作x，y例：XY二维平面上点的坐标x，y就是序偶。说明：在序偶中二个元素要有确定的排列次序。即： 若ab时，则a，bb，a 若x，y=a，b（x=ay=b）下面定义多重序元：三重序元=x,y,z n重序元=x1，x2,x3，xn 3 序偶与笛卡尔乘积2.笛卡尔乘积 定义 设A，B为二个任意集合，若序偶

20、的第一个成 员（左元素）是A的一个元素，序偶的第 二个成员（右元素）是B的一个元素，则所 有这样的序偶的集合称为A和B的笛卡尔乘积。 记作：AB=x，y|（xA）（yB）例：设A=1，2 B=a，b 则AB=,2,b BA=, ABBA 即“”是不满足交换律。3.3 序偶与笛卡尔乘积例：设A=a，b，B=1，2，C=z 则 (AB)C=,z =, A ( BC ) =a,b1,z,2,z =a,a,b,b, （AB）CA（BC） “”不满足结合律。 3.3 序偶与笛卡尔乘积 定理 若A，B，C是三个集合，则有： (1)A（BC）=（AB）（AC） (2)A（BC）=（AB）（AC） (3)（A

21、B）C=（AC）（BC） (4)（AB）C=（AC）（BC）证明：（2）设是A(BC)中的任一元素,则A（BC） x,y |xAyBC |xAyByC3.3 序偶与笛卡尔乘积 |(xAyB)(xAyC) (AB)(AC)即 A(BC)=(AB)(AC)例：设A=1，B=1，2，C=2，3 则A（BC） =11，2，3 =1，1，1，2，1，3 3.3 序偶与笛卡尔乘积（AB）（AC）=11，212，3 =1，1，1，2，1，3 A（BC）=12=1，2 （AB）（AC） =1,1,1，21,2,1,3 =1，2 n个集合的笛卡儿乘积的定义 ：设A=Ai，iIn Ai=A1A2An = （A1A

22、2）A3）An 3.4 关系及其表示序偶a，b实际上反映了二个元素之间的关系，关系反映了事物的结构。1.关系：指事物之间（客体之间）的相互联系。日常生活中：父子关系，母子关系，兄弟关系等均为二个客体之间的关系。而祖孙关系是三个客体之间的关系（父子关系和父子关系的合成）。n元笛卡尔积A1A2An是n元关系。 3.4 关系及其表示 定义 若 则是一个二元关系。 即：序偶作为元素的 任何集合 。关系表示方法（1）枚举法（直观法、列举法）设R表示二元关系，用 表示特定的序偶， 若 ，则也可写成：x R y。|,22112121AxAxxxAAxRyRyx ,Ryx ,3.4 关系及其表示例：二元关系定

23、义如图： 可写成：由定义可见：关系是一个集合，定义集合的方法都可以来定义关系。（2）谓词公式表示法前面讲述，一个集合可用谓词公式来表达，所以关系也可用谓词公式来表达。, 4, 3, 2, 1dcbaR3.4 关系及其表示例：实数集合R上的“”关系可表达为： 大于关系：“”= 父子关系：“F”=（3）关系矩阵表示法 规定：(a)二元关系中的序偶中左元素表示行，右元素表示列；(b)若 ，则在对应位置记上“1”，否则为“0”。)( |,yxRyRxyx|,的父亲是yxyxiiRyx3.4 关系及其表示例1：设并定义为列出关系矩阵：例2：设X=a,b,c,Y=1,2, R2是的关系， 1 , 22 ,

24、 31 , 33 , 42 , 41 , 41R11101100100000001RM的关系是R,4 , 3 , 2 , 13.4 关系及其表示 是的全域关系， 2 ,1 ,2 ,1 ,2 ,1 ,2ccbbaaYXR2R3R例2：设X=a,b,c,Y=1,2, R2是的关系， 3.4 关系及其表示（4）关系图表示法规定：(a)把、集合中的元素以点的形式全部画在平面上；(b)若 ，则xi和yi之间画一箭头弧线，反之不画任何联线。 例： 是X中的二元关系，iiRyx1,4 , 3 , 2 , 1RX 1 , 22 , 31 , 33 , 42 , 41 , 41R3.4 关系及其表示用关系图表示

25、：关系的定义域和值域：定义设S是一个二元关系，D(s)是所有客体x的集合， 对于一些y来说，若有 ，则称D(s)为 S的定义域（简称“域”），即 Syx,1 , 22 , 31 , 33 , 42 , 41 , 41R1,4 , 3 , 2 , 1RX 3.4 关系及其表示 ),(|)(SyxyxsD设R(S)是所有客体y的集合，对于一些X来说，若有 Syx ,，则称集合R(S)是S的值域（简称“值”）,即： ,(|)(SyxxySR例：例：X=1,2,3,4,5,6, R为X到Y的二元关系, 4, 3, 2, 1dcbaR,fa,b,c,d,eY ，则 ,)(,4 , 3 , 2 , 1)(

26、dcbaRRRD一般情况，称X为R的前域前域，称Y为R的陪域陪域。 3.4 关系及其表示关系和笛卡尔乘积关系和笛卡尔乘积笛卡尔乘积的任何子集都可以定义一种二元关系。 例：X=1,2,3,4，Y=1,2，则 2 , 4,1 , 4,2 , 3,1 , 3,2 , 2,1 , 2,2 , 1,1 , 1YX3.4 关系及其表示3 , 42 , 41 , 42 , 31 , 31 , 2|,1yxYyXxyxS2 , 41 , 1|,22yxYyXxyxS2 , 21 , 1|,3yxYyXxyxS321,SSS均为二元关系。 三个特殊关系：空白关系，全域关系，恒等关系三个特殊关系：空白关系，全域关

27、系，恒等关系 定义定义 集合X2定义了X集合中的一种关系，通称 为X中的全域关系，用Ex表示： 例：X=1,2,3,4，Y=1,2，则 3.4 关系及其表示,|,XyxyxXXEiix空集也是 的一个子集，它也定义了一种关系称为空白关系； XX X集合中的恒等关系，|,XxxxIiiix 在全域关系和恒等关系中前域=定义域，陪域=值域。 例：=，则 ,FFTFFTTTEx,FFTTIx同一域上的关系,可进行集合的所有运算。3.5 关系的性质自反性： 定义定义 设是集合中的二元关系，对于每一个（所有的） Xx 有 xRx，则称是自反关系，X中R是自反的 )(xRxXxx例：设 ,cbaX ,ba

28、ccbbaaR是自反的关系。 R的关系矩阵 001010110RM3.5 关系的性质 定义 设R是X中的二元关系，对于每一个 ， 有x x，则称R是反自反的关系，表示成：R是X中的反 自反的关系 x x 。XxXxx()例：设X=1,2,3, 1 , 22 , 11S2 , 12S1 , 23S000100000,000000010,000100010321SSSMMM3.5 关系的性质2 , 31 , 31 , 21 , 14S110100100RM对称性对称性 定义定义 设R是X中的二元关系，对于每一个来讲，如果每当有xRy，则必有yRx，则称R是X中的对称关系，并表示成：R是X中的对称关

29、系 Xyx,)(yRxxRyXyXxyxS4既不是自反的，又不是反自反的3.5 关系的性质例：设X=1,2,3,R= 则R是对称的关系010101110RM 定义定义 设R是X集合中的二元关系，对于每一个 Xyx, 来讲，如果每当xRy和yRx就必有x=y，则称R是反对称 的关系。3.5 关系的性质 即当且仅当 )(yxyRxxRyXyXxyxX中的R才是反对称的。 讨论定义：（1）前件 yRxxRy 为“T”， 则x=y也为“T”,则为反对称的； （2）前件 yRxxRy 为“F”， 则有三种情况：后件（x=y）不论是真还是假，命题公式为“T”。 下面举例说明：3.5 关系的性质例：设X=a

30、,b,c,1accbbaR,2ccbbaacaR,3accbaaR均是反对称的100001100,001010101,100001010321RRRMMM3.5 关系的性质例：X=a,b,c,下列关系不是对称的，也不是反对称的,1cbabbaR,2cabccbaaR3.5 关系的性质010001101,00010101021RRMMX上的恒等关系 ,3ccbbaaR是自反、对称、反对称的。 3.5 关系的性质0010101003RMX上的全域关系： ,4bcaccbabcabaccbbaaR是自反的，对称的 X上的空关系是反自反、对称、反对称的。 3.5 关系的性质传递性： 定义定义 设R是X

31、中的二元关系，对于每一个 Xzyx, 来说，如果每当 yRzxRy ，就必有 xRz则称R是可传递的，并表示成：X中R可传递 )(xRzyRzxRyXzXyXxzyx讨论定义：（1）前件 yRzxRy 为“T”， 则xRz也为“T”，R是可传递的； （2）前件为“F”，有三种情况后件不论是真还是假，命题为“T”，则R是可传递的 3.5 关系的性质 例：设X=a,b,c，则下列关系均是可传递的,1cbcabaaaR,2baR,3cabaR4R3.5 关系的性质下列关系是不可传递的：,4accaaaR,5accbbaR3.5 关系的性质确定二元关系性质举例（1）设X=1,2,3，3 , 13 ,

32、22 , 11R反自反，反对称，可传递的； 3 , 22 , 11 , 12R反对称的； 3.5 关系的性质3 , 32 , 21 , 13R自反，对称，反对称，可传递的； xER 4自反，对称，可传递的； 5R反自反的，对称的，反对称的，可传递的。 3.5 关系的性质（2）若 X，则X上的空关系 自反的，反自反的，对称的，反对称的，可传递的。3.6 复合关系和逆关系关系的复合定义定义设 YX （R关系）， ZY （S关系）， 于是可用 ZX （RS） 的关系，称 RS为R和S的复合关系，并规定为： ),(|,SzyRyxYyyZzXxzxSR例：设A=1,2,3,4,5，R,S均为AA的关系

33、，且R=,S=则RS=， S R=3.6 复合关系和逆关系,RSSR“”是不可交换的。讨论：（1）RS为新的二元关系（2） RSXZ（3）当R与S，才有 RS3.6 复合关系和逆关系定理设 WZYXRRR321则有： 321321321)()(RRRRRRRRR可见合成关系图 下面定义关系R 的幂次3.6 复合关系和逆关系定义给定集合X，R是X中的二元关系，设 Nn于是R的n次幂 nR可以定义成：（1） 0R=X集合中的恒等关系 （2） RRRnn1例：设R,S是 I中的二元关系，且 |7 ,|2 ,IxxxSIxxxR则：|14,|14,IxxxRSIxxxSR3.6 复合关系和逆关系,2b

34、cabcaR|4 ,2IxxxR|49,2IxxxS|8 ,23IxxxRRR,accbbaR,cbaX 例：xIccbbaaRRR,233.6 复合关系和逆关系RRRR34nmikRaM若|X|=n，则X中的二元关系R的幂次值是有限的。一般不用求出超过X的基数次幂。 复合关系的矩阵表示复合关系的矩阵表示 设有三个集合： ZYXzzzZyyyYxxxXSRpnm,212121而|X|=m,|Y|=n,|Z|=p，则关系矩阵pnkjSbM3.6 复合关系和逆关系1)()()()()(5515451435132512151115bababababaCpmijSRcMSRSRMMM例：设X=1,2,

35、3,4,5,R,S均是X中的二元关系，R=,S= 0000000000010000000100001,0000001000100000000100100,0000000000000100100001000SRSRMMM)(1kjiknkijbac3.6 复合关系和逆关系逆关系 定义定义设X,Y是二个集合，若R是XY的关系，从YX的关系，称为R的逆关系，用 ,|,RyxxyR表示，或用 cR表示。讨论定义：（1）只要将R中每一个序偶中的元素全部调换位置， 就可得到R的逆关系 R（2）设 R的关系矩阵为 RMRM的转置矩阵； （3）在R的关系图中，只要把所有箭头改换方向就可得到的关系图。（自回路箭

36、头改变与否无关） R3.6 复合关系和逆关系例：X=0,1,2，R=, R=,011100100,001001110RRMM3.6 复合关系和逆关系定理设 ZYXSR，则可有： RSSR证明：对于任一 ZzYyXx,来讲，若有 xSRzzSRxySzxRy)()(同样 xRSzxRyySz)(x,y,z分别为X,Y,Z中的任一元素， RSSR3.6 复合关系和逆关系例： 010101010110010,111110101SRMM，试求： ,SRSRSRMMMM111111011111010,010101010001110,101011111SRSRMMM3.6 复合关系和逆关系01111101

37、1101111,011111011101111SRRSRSSRMMMMM定理定理设R是X中的二元关系，当且仅当RR则R才是对称的。3.6 复合关系和逆关系证明：充分性：R是对称的 RR对于任一 RbaRabRba,必要性： RRR是对称的， RR对任一 RabRbaRba,R一定是对称的RR3.6 复合关系和逆关系定理给定集合X,Y, YXSRRR,21，于是可有 RR ) 1 (SRSR)2(SRSR) 3(XYYX)4()5()(,)()6(RYXRRR3.6 复合关系和逆关系2121)7(RRRR2121)8(RRRR2121)9(RRRR2121)10(RRRR证明：（1）设是R中的任

38、一元素，则RbaRabRba,（10）设 YyXx,，对任一 122121)()(,RRRRyxRRyx3.6 复合关系和逆关系由（2） SRSR1221)()( (,RRRRyx由（7） 2121RRRR)(,)()(,211221RRyxRRRRyx2121RRRR3.7 关系的闭包运算定义给定集合X，R是X中的二元关系，若有另一R满足下列条件： （1）R是自反的（对称，可传递的）； （2） RR （3）对于任一自反（对称，传递的）关系R，若 RR ，则 RR 则称R是R的自反（对称，传递的）闭包，并依次用r(R),s(R),t(R)来表示之。3.7 关系的闭包运算讨论定义： （1）已知一

39、个集合中的二元关系R，则r(R),s(R),t(R)是唯一的，它是包含R的最小的自反（对称，传递）关系； （2）若R是自反（对称，传递）的，则r(R),s(R),t(R)就是R本身。 （3）若R不是自反（对称，传递）的，则我们可以补上最少序偶，使之变为自反、对称、传递关系，从而得到r(R),s(R),t(R)；3.7 关系的闭包运算例：设X=a,b,R=，r(R)=,s(R)=,t(R)=R例：求t(R)需要特别小心，要进行多次添项。 设X=a,b,c,R=，求r(R),s(R),t(R)解：r(R)= ,ccbbaaaccbbaIRxs(R)= ,caacbccbabbaRRt(R)=3.7

40、 关系的闭包运算定理给定集合X，R是X中的二元关系，于是可有： （1）当且仅当r(R)=R，则R是自反的； （2）当且仅当s(R)=R，则R是对称的； （3）当且仅当t(R)=R，则R是可传递的。xI定理定理R是X中的二元关系是X中的恒等关系， 则有 xIRRr)(证明：按定义证：（1）设 xIRR，则R是自反的， RR )2(3.7 关系的闭包运算（3）设有任一R也是自反的，且 则 RRIRx )( RRIRRxxIRR 定理定理给定集合X，R是X中的二元关系，则有 RRRS)(定理定理设X是一集合，R是X中的二元关系，则： )( ,)(12IiRURRRtii3.7 关系的闭包运算例：X=

41、a,b,c,R=，|X|=3,则 ,432RRccbbaaRbcabcaRRR,)(32ccbbaabcabcaaccbbaRRRRt定理定理设|X|=n，R是X中的二元关系，则 kRRRRt2)()0(nK 3.7 关系的闭包运算例：X=a,b,c,d,R=,则 432,RdaRdbcaR,)(432dadbcadccbbaRRRRRt定理定理设X是一集合，R是X中的二元关系，则有： （1）r(S(R)=S(r(R); （2）r(t(R)=t(r(R);（3）t(S(R) S(t(R)。 3.7 关系的闭包运算证明：（1）r(S(R)()()(xxxIRIRIRRRRr)()()()()(R

42、SrRrRrIRIRxx常用下列符号表示一些闭包： “R加”： )(RtR ，传递闭包， nniiRRRRR211“R星”： )()(*RrtRtrR，自反可传递闭包， niixRIRtRR10*)(3.7 关系的闭包运算例：设X=a,b,c,R=（1）rS(R)=r = Sr (R)=s =（2）rt(R)=r= tr(R)=t=（3）tS(R)=t = St(R)=S= t(S(R) St(R) 3.8 集合的划分和覆盖定义给定一非空集合，又设 ,21mAAAA若（1） ),2 , 1( ,miSAi（2） miiSA1则称A为S的覆盖。 例：S=a,b,c，A=a,b,b,c，B=a,a

43、,b,c， C=a,b,c，D=a,b,a,c 均为S的覆盖。 3.8 集合的划分和覆盖例：四个半圆覆盖一正方形。 定义定义给定一非空集合S，设非空集合 ,21mAAAA如果有： ),2 , 1( ,) 1 (miSAijiAA )2(或 jiAA miiSA1)3(（i,j=1,2,m） 3.8 集合的划分和覆盖则称集合A是集合S的一个划分。讨论定义： （1）划分和覆盖主要差别在第（2）条； （2）划分A中的元素，称为划分的类，在定义中 mAAA21,均是A中的一个类，类的个数称为划分的秩； （3）若A为有限集合，则A的秩是有限的，为|A|， 若A为无限集合，则划分的秩是无限的；（4）集合的

44、划分必定是一个覆盖，而覆盖不一定是划分；（5）集合S上的秩最大的划分称最大划分，最小的称最小划分。 3.8 集合的划分和覆盖例：设S=a,b,c，下列 iA均为S的一个划分：,1cbaA 类有二个a,b,c, |1A=2（秩）； ,2cbaA 类有二个a ,b ,c, |2A=2（秩）； ,3bcaA 类有二个a,c,b, |3A=2（秩）； ,4cbaA 最大划分，秩为3=|S|； ,5cbaA 最小划分，秩为1。 例：四个直角三角形 组成了正方形的一个划分 秩=4 3.8 集合的划分和覆盖定义设A和A是非空集合S的二种划分，并可表示成： , 1miiAAnijAA1若A的每一个类 jA都是

45、A的某一个类 iA的子集，则称划分A是划分A的加细， 或讲A加细了A，若A加细了A且 AA 则称A是A的真加细。讨论定义： A加细了A，一定有|A|A|（秩）， 若|A|A|，则一定为真加细。 3.8 集合的划分和覆盖例：S=a,b,c,d,S的划分：A=a,b,c,d,A=abc,d，则A是A的真加细 A=abcd,则A 是A的真加细 3.9 等价关系与等价类定义设X是一个集合，R是X中的二元关系，若R是自反的，对称的和可传递的，则称R是等价关系。例：下列关系均为等价关系 （1）实数（或I、N集上）集合上的“=”关系（相等）（2）人类 中的同姓关系（3）命题集合上的等价关系 例：设X=1,2

46、,3,4,5,6,7， 3,|,yxXyxyxR为整数3.9 等价关系与等价类试验证R是等价关系，画出R的关系图，列出R的关系矩阵 解：（1）R=（2）R的关系矩阵 1001001001001001001001001001001001001001001001001RM3.9 等价关系与等价类R满足自反、对称和可传递的，R是一等价关系定义定义设 ImIyx,若对于某个整数n有(x-y)=n m, nmyx（整数）， 则称x模m等于y，记作： )(modmyx 定理定理任何集合 IX （I的任何子集X中）的模m等价，是一个等价关系。 3.9 等价关系与等价类定义设R是X集合中的等价关系，对于任何的

47、 Xx来讲，可把集合 XxR规定成： |yRxXyyxR并称是由 Xx生成的R等价类。讨论定义： （1）等价类 Rx是一个集合，由定义中可见 XxR（2） Rx中的元素是在等价关系R中，所有与x 具有关系的元素所组成的集合，且 Rx3.9 等价关系与等价类例：设X=a,b,c,d,R是X中的等价关系，R=则 RRddcc,RRbbaa,定理定理设X是一个集合，R是X中的等价关系，则（1）若 Xx，则 Rxx（2）对于所有的 Xyx,，或者 RRyx或者 RRyx（3） XxRXx3.9 等价关系与等价类例：设X=N，关系R= )(|,yxXyXxyx可被3整除 是一等价关系， 则R可以找出三个

48、等价类：R0=0，3，6，9，此集合中的元素除以3的余数为“0”； R 1 =1，4，7，10，此集合中的元素除以3的余数为“1”；R2=2，5，8，11，此集合中的元素除以3的余数为“2”。例：X为全班同学的集合，则班中同姓关系是一个等价关系，（1）任何一个人均某一个等价类，王某某王 R张某 张R 3.9 等价关系与等价类（2）任何二个姓的等价类，只有二种可能一种：王 R= 李R 二种：王 R李R= （3）全班同学的集合=同姓关系等价类的并集=王 R李 R （4）所有等价类的集合，一定导致全班同学集合的一个划分：A=王R，李R. 3.9 等价关系与等价类定理设X是一非空集合，R是X中的等价关

49、系，R等价类的集合xR| x X是X的一个划分，且此集合称为X按R的商集，用 RX表示之。例：设X=x1,x2.xn （1）X集合中的全域关系， XXR1，它是一个等价关系， XxR1| |1XxRX按 R1的商集1|,|11RXXxxRXR它形成了X的一个最小划分 3.9 等价关系与等价类（2）X中的恒等关系 xIR 2|22XxxRXR221RnRxx),(21Xxxxn它形成了X的一个最大划分 例：X为全班同学的集合，|X|=n, (nN)（1）同学关系R1是一个等价关系， 1XRX（2）按指纹的相同关系R2是一个等价关系， 2212RnRxxRX它形成了全班同学的最大划分 3.9 等价

50、关系与等价类（3）同姓关系R3是一等价关系3RX张 R3，李R3，它形成了全班同学的既不是最大，又不是最小划分3.9 等价关系与等价类定理X是一非空集合， A为X的一个划分，且A=A1,A2,.An，则由A导出的X中的一个等价关系)(1iiniAAR例：Xa,b,c,d，A=a,b,c,d则 R(a,b a,b)(c,d c,d) =, 由此我们看到：集合X上的等价关系与X的划分之间有对应关系。3.10 相容关系定义给定一个集合X，R是X中的二元关系，如果R是自反、对称的，则称R是相容关系。 例：设X=ball,bed,dog,let,egg,5个英文单词定义X中一个二元关系：R= yxXyx

51、yx,|,有相同的字母 则R是自反的，对称的，但不可传递(ball R bed) (bed R egg) (ball R egg) 则R= 3.10 相容关系3.10 相容关系定义设X是一个集合， R是X中的相容关系，假定 AX，若任一 xA都与A中的其它所有元素有相容关系，而（X-A）中没有一个元素与A中的所有元素有相容关系，则称子集A为相容关系R的一个最大相容类。 例：上例中 5 , 4 , 2,5 , 3 , 2,4 , 2 , 1321AAA均是X中的最大相容类,且 321AAAX,321AAA定义了X的一个覆盖。 同样已知X集合的一个覆盖 ,321AAA3.10 相容关系则一定可以求

52、出相对应的相容关系来：332211AAAAAAR讨论等价关系和相容关系后可得到结论： 集合X上的相容关系R的所有最大相容类集合A1,A2,.Am构成集合X的一个覆盖。即：imiAX1 而集合X上的等价关系R的所有等价类集合构成X的一个划分3.10 相容关系求最大相容类的方法： 关系图法：确定最大完全多边形 每个顶点都与其他所有顶点相联结的多边形。 (1)孤立结点是最大的完全多边形； (2)二个相互联结的结点是最大完全多边形； (3)三角形是三个结点的最大完全多边形； 3.10 相容关系(4)四个结点； (5)五个结点; 画出简化相容关系的关系图后，先结点最多的完全多边形，以后逐次减少。3.10

53、 相容关系例：已知相容关系图，求出最大相容类3.10 相容关系5 , 45 , 23 , 24 , 3 , 14321XXXX4 , 35 , 4 , 16 , 5 , 2 , 1321XXX最大相容类集合为4 , 35 , 4 , 16 , 5 , 2 , 1,5 , 45 , 23 , 24 , 3 , 121SS3.11 序关系 定义设R是P中的二元关系，如果R是自反的，反对称和可传递的，则称R是P中的偏序关系（或称偏序），并用符号“”表示，而序偶P，则称为偏序集合。讨论定义：（1）“”不单纯意味着在实数中的关系，而是代表更为普遍的关系（具有自反，反对称和可传递性的关系）；（2）若 Pyx,，“xy”读作： “x小于或等于y”“y包含x”“x在y的前面”等；3.11 序关系（3）R是集合P中的偏序关系，则 R也是P中的偏序关系，即R用“”表示， R则用“”表示； （4）若P，是一个偏序集合，则P，也一定是偏序集合，且偏序集合是一个序偶，左元素为集合P，右元素为偏序关系。例：（1）在领导机构的集合中“领导和被领导的关系”是偏序关系；