《[企业管理]集合83805305》由会员分享，可在线阅读，更多相关《[企业管理]集合83805305（162页珍藏版）》请在金锄头文库上搜索。
1、第二篇第二篇 集合论集合论主要包括如下内容：主要包括如下内容：集合论初步集合论初步 二元关系二元关系 函数函数 基本概念基本概念1.1.集合与元素集合与元素集合集合：是一些确定的、可以区分的事物：是一些确定的、可以区分的事物汇集在一起组成的一个整体。用大写汇集在一起组成的一个整体。用大写的英文字母表示。的英文字母表示。元素元素：集合中的每个事物，称之为元素。：集合中的每个事物，称之为元素。用小写英文字母表示用小写英文字母表示 ：表示元素与集合的属于关系。：表示元素与集合的属于关系。 2. 2. 有限集合与无限集合有限集合与无限集合 有限集合有限集合：元素是有限个的集合。：元素是有限个的集合。如
2、果如果A是有限集合，用是有限集合，用|A|表示表示A中元素个数。中元素个数。 无限集合无限集合：元素是无限个的集合。：元素是无限个的集合。 3.3.集合的表示方法集合的表示方法 列举法（外延表示法）列举法（外延表示法）：将集合中的元素：将集合中的元素一一列出，写在大括号内。一一列出，写在大括号内。描述法（谓词法）描述法（谓词法）：用句子：用句子(或或谓词公式谓词公式)描述元素的属性。描述元素的属性。 A=x|P(x), 其中其中P(x)是谓词公式，如果论域内个体是谓词公式，如果论域内个体a使使得得P(a)为真，则为真，则aA，否则否则a A。4. 4. 说明说明集合中的元素间次序是无关紧要的，
3、但集合中的元素间次序是无关紧要的，但是必须是可以区分的。是必须是可以区分的。对集合中的元素无任何限制对集合中的元素无任何限制.常用的几个集合符号的约定：常用的几个集合符号的约定： 自然数集合自然数集合N= 0,1,2,3, 整数集合整数集合Z，实数集合实数集合R，有理数集合有理数集合Q.集合中的元素也可以是集合，下面的集合的含集合中的元素也可以是集合，下面的集合的含义不同：义不同： 如如 a： 张书记张书记 a: 党支部党支部(只有一个书记只有一个书记) a： 分党委分党委(只有一个支部只有一个支部) a： 党委党委 (只有一个分党委只有一个分党委) a： 市党委市党委(只有一个党委只有一个党
4、委)（5）对一个集合来说，任一事物或者是它的元）对一个集合来说，任一事物或者是它的元素或者不是它的元素，二者必居其一而不可兼素或者不是它的元素，二者必居其一而不可兼而有之，且结论是确定的。而有之，且结论是确定的。集合实例集合实例vB=9，8，8，7=9，8，7=7，8，9vD=x | x B（除7、8、9外的一切事物）vF=7，8，9 （FB）vA=年青人v罗素悖论：一个村子里的理发师说，我给而且只给自己不给自己理发的人理发。 集合间的关系集合间的关系一一. .被包含关系被包含关系( (子集子集) ) 1.定义定义：A、B是集合，如果是集合，如果A中元素都中元素都是是B中元素，则称中元素，则称
5、B包含包含A，A包含于包含于B，也称也称A是是B的子集。记作的子集。记作A B。 文氏图表示如右下图。文氏图表示如右下图。谓词定义谓词定义： A Bx(xAxB)AB2. 性质性质： 有自反性，对任何集合有自反性，对任何集合A有有A A。 有传递性，对任何集合有传递性，对任何集合A、B、C，有，有A B且且 B C ，则，则A C。 有反对称性，对任何集合有反对称性，对任何集合A、B，有，有A B且且 B A ，则，则A=B。例：判断下列各式的正确性。例：判断下列各式的正确性。 a a,b，aa,b， a,b a,b,a, a,ba,b,a二二. . 相等关系相等关系 定义定义：A、B是集合，
6、如果它们的元素完全相同，是集合，如果它们的元素完全相同，则称则称A与与B相等。记作相等。记作A=B。 谓词定义谓词定义： A=Bx(xAxB) 定理定理：A=B，当且仅当当且仅当A B且且 B A。 证明证明： A=Bx(xA xB) x(xAxB)(xBxA) x(xAxB) x(xBxA) A B B A2. 性质性质有自反性，对任何集合有自反性，对任何集合A，有，有A=A。有传递性，对任何集合有传递性，对任何集合A、B、C，如果如果有有A=B且且 B=C ，则，则A=C。有对称性，对任何集合有对称性，对任何集合A、B，如果有如果有A=B，则，则B=A。三三. . 真被包含关系真被包含关系
7、( (真子集真子集) ) 1. 定义定义：A、B是集合，如果是集合，如果A B且且AB，则称，则称B真包含真包含A，A真包含于真包含于B，也称也称A是是B的真子集。的真子集。记作记作A B。谓词定义：谓词定义：A BA B ABx(xAxB)x(xAxB)x(xAxB) (x(xAxB)x(xBxA)( x(xAxB)x(xAxB) ( x(xAxB) x(xBxA) x(xAxB) x(xB x A)2. 性质性质 对任何集合对任何集合A、B、C，如果如果有有A B且且 B C ，则则A C。练习题练习题：设：设A=a,a,a,b,a,b,c判断下面命判断下面命题的真值题的真值。 aA (a
8、 A) cA a a,b,c a A a,ba,b,c a,b A a,b a,b,c c a,b,c (c A)(a) 特殊集合特殊集合一一. .全集全集 E E 定义定义：包含所讨论的所有集合的集合，：包含所讨论的所有集合的集合，称之为全集，记作称之为全集，记作E。 文氏图如右图。文氏图如右图。 E=x| P(x) P(x)性质性质：对于任何集合：对于任何集合A，都有，都有A E。 E二二. .空集空集 定义定义：不含任何元素的集合，称之为空集，记：不含任何元素的集合，称之为空集，记作作。 =x| x x性质性质：1.对于如何集合对于如何集合A，都有都有 A。 因为因为 x(xxA)为永真
9、式，所以为永真式，所以 A。2.空集是唯一的。空集是唯一的。三三. .集合的幂集集合的幂集定义定义: A是是集合，由集合，由A的所有子集构成的集的所有子集构成的集合，称之为合，称之为A的幂集。记作的幂集。记作P(A)或或2A。 P(A)=B| B A例如，例如， A P(A) a a,b 结论：对任意集合结论：对任意集合A，因为因为 A， A A，所以有所以有P(A), AP(A) 。 集合的运算集合的运算一一. .交运算交运算1.定义：定义：A、B是集合，由既属于是集合，由既属于A，也属于也属于B的的元素构成的集合元素构成的集合 ,称之为称之为A与与B的交集的交集,记记作作AB。谓词定义谓词
10、定义：AB=x|xAxBxAB xAxBABAB2.性质性质幂等律幂等律 对任何集合对任何集合A，有，有AA=A。交换律交换律 对任何集合对任何集合A、B，有，有AB=BA。结合律结合律 对任何集合对任何集合A、B、C，有有 (AB)C=A(BC)。同一律同一律 对任何集合对任何集合A，有，有AE=A。零零律律 对任何集合对任何集合A，有，有A=。 A B AB=A。证明证明：AB=A x(xAB xA)x(xAB xA)(xA xAB)x(x ABxA)(x AxAB)x( (xAxB)xA) (x A(xAxB)x(x Ax B)xA) (x A(xAxB)x(T(T ( x A xB)x
11、( x A xB)x(xAxB) A B二二. .并运算并运算1.定义定义：A、B是集合，由或属于是集合，由或属于A，或属于或属于B的的元素构成的集合元素构成的集合 ,称之为称之为A与与B的并集的并集,记作记作AB谓词定义谓词定义：AB =x|xAxBxAB xAxB2.性质性质幂等律幂等律 对任何集合对任何集合A，有，有AA=A。交换律交换律 对任何集合对任何集合A、B，有，有AB=BA。 结合律结合律 对任何集合对任何集合A、B、C，有有 (AB)C=A(BC)。ABAB同一律同一律 对任何集合对任何集合A，有，有A=A。零律零律 对任何集合对任何集合A，有，有AE =E 。分配律分配律
12、对任何集合对任何集合A、B、C，有有 A(BC) =(AB)(AC)。 A(BC) =(AB)(AC)。吸收律吸收律 对任何集合对任何集合A、B，有有 A(AB)=A A(AB) =A。证明证明 A(AB)= (AE)(AB) (同一同一) = A(EB) (分配分配) = AE=A (零律零律) (同一同一) A B AB=B。三三. . 差运算差运算- (- (相对补集相对补集) )1.定义：定义：A、B是集合，由属于是集合，由属于A，而不属于而不属于B的的元素构成的集合元素构成的集合 ,称之为称之为A与与B的差集的差集,或或B对对A的的相对补集，记相对补集，记作作A-B。谓词定义谓词定义
13、：A-B =x|xAx BxA-B xAx B2.性质性质设设A、B、C是任意集合，则是任意集合，则A-=A -A= A-A= A-B A A B A-B= A-B=AAB= ABA-B四四. . 绝对补集绝对补集 1.定义：定义：A是集合是集合,由不属于由不属于A的元素构成的集合的元素构成的集合 ,称之为称之为A的绝对补集的绝对补集,记作记作A。实际上。实际上A=E-A。谓词定义谓词定义：A =E-A=x|xEx A = x|x Ax A x A2.性质性质设设A、B、C是任意集合，则是任意集合，则 E= =E (A)=A AA= AA=E A-B=ABA-AE (AB)= AB (AB)=
14、AB 证明证明：任取：任取x (AB) x (AB) x AB(xAxB) (x Ax B)xAxB xAB (AB)=AB A B B A证明证明： A B x(xAxB) x(x Bx A)x(x Bx A) B A集合恒等式与命题演算等价式的比较集合恒等式与命题演算等价式的比较v 命题演算命题演算 集合运算集合运算v对象对象 命题命题A、B 集合集合A、Bv T Ev F v运算符 A B A Bv A B A Bv A Av关系关系 A=B A=Bv AB A Bv 定律定律 定律定律五五. . 对称差对称差 1.定义定义：A、B是集合是集合,由属于由属于A而不属于而不属于B，或者属于
15、或者属于B而不属于而不属于A的元素构成的集合的元素构成的集合,称称之为之为A与与B的对称差的对称差,记作记作A B。 谓词定义谓词定义： A B=(A-B)(B-A)=x|(xAx B)(xBx A) A B=(AB)-(AB) ABABE2.性质性质 交换律交换律 对任何集合对任何集合A、B，有，有A B=B A。 结合律结合律 对任何集合对任何集合A、B、C，有有 (A B) C=A (B C)。 同一律同一律 对任何集合对任何集合A，有，有A =A。 对任何集合对任何集合A，有，有A A=。习题习题 (1)判断下面命题的真值：判断下面命题的真值：a)如果如果AB，B C ，则则 A C。
16、 b)如果如果AB，B C，则则 A C 。 c)如果如果A B，BC，则则 AC。 d)如果如果A B，BC，则，则 A C。 e)如果如果AB及及B C，则A C。f)如果如果A B，BC，则则 A C。(2)设设A=， B=P(P(A)a）是否有）是否有B ？ B？b）是否有）是否有B？ B？c）是否有）是否有B？ B？（1）已知）已知AB=AC，是否必须是否必须B=C？（2）已知已知AB=AC，是否必须是否必须B=C？（3）已知已知A B=A C，是否必须是否必须B=C？有限集合的基数有限集合的基数集合中元素的个数集合中元素的个数v(1) |P(A)|=2|A|v(2) |AB|A|+
17、|B|v(3) |AB| min|A|, |B|v(4) |A-B| |A|-|B|v(5) |A B|=|A|+|B|-2|AB|v问题问题: (2)、(3)、(4)等号成立的条件是什么？等号成立的条件是什么？ 序偶与集合的笛卡尔积序偶与集合的笛卡尔积一一. .序偶与有序序偶与有序n n元组元组1.1.定义定义: :由两个对象由两个对象x x、y y组成的序列称为有序组成的序列称为有序二元组，也称之为序偶，记作二元组，也称之为序偶，记作；称；称x x、y y分别为序偶分别为序偶的第一，第二元素。的第一，第二元素。 注意，序偶注意，序偶与集合与集合x,yx,y不同：不同： 序偶序偶：元素元素x
18、 x和和y y有有次序；次序； 集合集合x,yx,y：元素元素x x和和y y的次序是无关紧要的次序是无关紧要的。的。v2.2.定义定义：设：设 ， 是两个序偶，如果是两个序偶，如果 x=ux=u和和y=vy=v，则称，则称 和和 相等，相等， 记作记作 =.3 .定义定义:有序有序3元组是一个序偶元组是一个序偶,其第一个元素也是个其第一个元素也是个序偶。序偶。 有序有序3元组元组, c可以简记成可以简记成。 但但a,不是不是有序有序3元组。元组。 4.定义定义:有序有序n元组是一个序偶元组是一个序偶,其第一个元素本身是其第一个元素本身是个有序个有序n-1元组元组,记作记作, xn。且且可以简
19、记成可以简记成。5. 定义定义： = ( x1= y1) ( x2= y2) ( xn= yn)集合的笛卡尔积集合的笛卡尔积 例如例如“斗兽棋斗兽棋”的的16颗棋子，颗棋子，可看成是由两种颜色的集合可看成是由两种颜色的集合A和和8种动物的集合种动物的集合B组成的组成的 A=红红,蓝蓝 B=象象,狮狮,虎虎,豹豹,狼狼,狗狗,猫猫,鼠鼠每个棋子可以看成一个序偶，斗兽棋可记成集合每个棋子可以看成一个序偶，斗兽棋可记成集合A B ： , , 虎象狮豹狼鼠猫狗虎象狮豹狼鼠猫狗1.定义定义:设设A、B是集合，由是集合，由A的元素为第一元素，的元素为第一元素，B的元素为第二元素组成序偶的集合，称为的元素为
20、第二元素组成序偶的集合，称为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= A A=可见可见 ABBA所以，集合的笛卡尔积运算不满足交换律所以，集合的笛卡尔积运算不满足交换律,也不也不满足结合律满足结合律。v2.性质性质 1) 如果如果A、B都是有限集，且都是有限集，且|A|=m, |B|=n，则则 |A B |=mn. v 2) A = B= 3) 对对和和满足分配律。满足分配律。 设设A,B,C是任意集合，则是任意集合，则 A (BC)= (A B)(A C
21、)； A (BC)= (A B)(A C)； (AB) C= (A C)(B 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 B，求证求证 A C B C任取任取 A C x A y C x B y C (因因A B) B C 所以所以, A C B C. 充分性：充分性： 已知已知C 取取C中元素中元素y, 任取任
22、取 x Ax 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) 5) 设设A、B、C、D为非空集合，则为非空集合，则 A B C DA CB D.证明证明: 首先首先,由由A B C D 证明证明A CB D.任取任取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任取任取 AB AB x A y B x C y D (由由A C，B D) CD 所以所以, A B C D
23、证毕证毕.6)约定约定 (A1 A2) An-1) An)=A1 A2 An 特别特别 A A A = An 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
24、,s,t,u,v,w,x,y,z 是英文字母表是英文字母表 一个一个英文单词可以看成有序英文单词可以看成有序n元组：如元组：如 at=, boy=, data=, computer= 于是可以说：于是可以说： at A2 ,boy A3,data A4,computer A8, 于是英文词典中的于是英文词典中的单词集合单词集合可以看成是可以看成是 AA2An 的一个子集。的一个子集。优先权优先权v一元运算符一元运算符( A, P(A)v优先于二优先于二元运算符元运算符( , , , , )v优先于集合关系符优先于集合关系符(=, , , )v优先于一元联结词优先于一元联结词( )v优先于二元联
25、结词优先于二元联结词( , , , )v优先于逻辑关系符优先于逻辑关系符(, )v括号内的优先于括号外的！括号内的优先于括号外的！关系及其表示法关系及其表示法 基本概念基本概念1.关系的定义关系的定义定义定义1:设设A、是集合，如果是集合，如果 AB，则称则称R是一是一个个从从A到到B的二元关系。如果的二元关系。如果 R AA，则称则称R是是A上上的二元的二元关系。关系。二元二元关系简称为关系。关系简称为关系。定义定义2:任何序偶的集合，都称之为一个二元关系。如任何序偶的集合，都称之为一个二元关系。如:R=, R xRy 也称之为也称之为x与与y有关系。有关系。 R xRy 也称之为也称之为x
26、与与y没有关系。没有关系。关系的表示关系的表示v列举法：列举法：A=0，1 B=a，bv R1=,(A到到B的关系）的关系）v R2=,(A上的关系）上的关系）v描述法：描述法：A=1，2，3vDx=| xAyAx整除整除yvLx=|xAyAxy2.关系的定义域与值域关系的定义域与值域定义域定义域(domain) ：设设R AB，称，称集合集合 dom R=x| y( R) 为为R的定义域。的定义域。值域值域(range) ：设设R AB，称集合称集合 ran R=y| x( R) 为为R的值域。的值域。关系的域关系的域(fild)：fid R=dom R ran R.结论：结论： dom R
27、 A， ran R B。R= , dom R = ran R =三三. 关系的另两种表示法关系的另两种表示法1.1.有向图法有向图法： R AB（A、B非空、有限），用两组小圆圈非空、有限），用两组小圆圈(称为称为 结点结点)分别表示分别表示A和和B的元素，当的元素，当 R时，从时，从x到到y引一条有向弧引一条有向弧(边边)（由（由x指向指向y）。）。这样得到的图形称为这样得到的图形称为R的关系图。的关系图。 如如R AA,即即R是集合是集合A中关系时中关系时,用一组小圆圈表示用一组小圆圈表示A中的元中的元素，若素，若 R,则从则从x到到x画一条有向环画一条有向环(自回自回路路)。例例 设设A
28、=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。ABabcR3 :4。31。 2R4 :4.4.矩阵表示法矩阵表示法：非空有限集合之间的关系也可以用矩阵来表示，这种非空有限集合之间的关系也可以用矩阵来表示，这种表示法便于用计算机来处理关系。表示法便于用计算机来处理关系。 设设A=a1, a2, , am，B=b1, b2, , bn是个有限集，是个有限集， R AB，定义定义R的的mn阶阶矩阵矩阵 MR=(rij)mn，其中其中
29、 rij=称称MR为为关系关系R的关系矩阵。的关系矩阵。 1 若R0 若R(1im,1jn) 例例 设设A=1,2,3,4,B=a,b,c， R3 AB， R3= ,例例 设设A=1,2,3,4, R4 AA， R4= , 则则 MR3 = MR4=1 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)，所以所以也也是一个从是一个从A到到B(或或A上上)的关系，称之为的关系，称之为空空关系关系。2. 全域关系全
30、域关系 ： AA本身也是一个本身也是一个A上上的关系，称之为的关系，称之为A上的全上的全域关系，记为域关系，记为EA，即，即 EA=|xAyA。3. A上的上的恒等关系恒等关系IA： IA AA，且，且IA =|xA称之为称之为A 上的恒等上的恒等关系。关系。 3. A上的上的恒等关系恒等关系IA： IA AA，且，且IA =|xA称之为称之为A 上的恒上的恒等关系。等关系。 IA的的关系距阵为单位距阵。关系距阵为单位距阵。例如例如A=1,2,3, 则则IA =,A上的上的、全域关系及全域关系及IA的关系图及矩阵如的关系图及矩阵如下：下： MIA =1 0 00 1 00 0 1331。2。3
31、1。2。31 1 11 1 11 1 1331。2。30 0 00 0 00 0 033M=MAA=AAIA五五. . 关系的集合运算关系的集合运算由于关系就是集合，所以集合的由于关系就是集合，所以集合的、 、 和和 运算对关系也适用。运算对关系也适用。例如，例如，A是学生集合，是学生集合，R是是A上的同乡关系，上的同乡关系，S是是A上的同姓关系，则上的同姓关系，则RS：或同乡或同姓关系或同乡或同姓关系RS：既同乡又同姓关系既同乡又同姓关系R S ：同乡而不同姓关系同乡而不同姓关系R S：同乡而不同姓同乡而不同姓,或同姓而不同乡关系或同姓而不同乡关系 R：不是同乡关系不是同乡关系, 这里这里
32、R=(AA) R 关系的性质关系的性质本节中所讨论的关系都是集合本节中所讨论的关系都是集合A中的关系。中的关系。 关系的性质主要有：自反性、反自反性、关系的性质主要有：自反性、反自反性、对称性、反对称性和传递性。对称性、反对称性和传递性。一一. 自反性自反性定定义义:设设R是是集集合合A中中的的关关系系，如如果果对对于于任任意意xA都都有有R (xRx)，则则称称R是是A中中自自反关系。即反关系。即 R是是A中自反的中自反的x(x AxRx)从关系图看自反性从关系图看自反性:每个结点都有环。每个结点都有环。从关系矩阵看自反性：主对角线都为从关系矩阵看自反性：主对角线都为1。令令A=1,2,3,
33、给定给定A上八个关系如下：上八个关系如下：1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8二二. 反自反性反自反性定义定义：设：设R是集合是集合A中的关系，如果对于任中的关系，如果对于任意意的的xA都有都有 R ，则称则称R为为A中的中的反自反关系。即反自反关系。即R是是A中反自反的中反自反的x(x A R)从关系图看反自反性从关系图看反自反性:每个结点都无环。每个结点都无环。从关系矩阵看反自反性：主对角线都为从关系矩阵看反自反性：主对角线都为0。1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2
34、R1R3R4R5R6R7R8三三. 对称性对称性定义定义:R是集合是集合A中关系中关系, 对任何对任何x, yA,如如果有果有xRy,必有必有yRx,则称则称R为为A中的对称关系。中的对称关系。 R是是A上对称的上对称的x y(x A y A xRy) yRx) 从关系图看对称性从关系图看对称性:在两个不同的结点之间，若有边的在两个不同的结点之间，若有边的话，则有方向相反的两条边。话，则有方向相反的两条边。 从关系矩阵看对称性：以主对角线为对称的矩阵。从关系矩阵看对称性：以主对角线为对称的矩阵。1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5
35、R6R7R8四四. 反对称性反对称性定义定义:设设R为集合为集合A中关系中关系,对任何对任何x, yA,如果有如果有xRy,和和yRx,就就有有x=y,则称则称R为为A中反对称关系中反对称关系 。R是是A上反对称的上反对称的x y(x A y A xRy yRx) x=y)x y(x A y A x y xRy)y x) 由由R的关系图看反对称性：的关系图看反对称性：两个不同的结点之间两个不同的结点之间最多有一条边。最多有一条边。从关系矩阵看反对称性：从关系矩阵看反对称性：以主对角线为对称的以主对角线为对称的两个元素中最多有一个两个元素中最多有一个1。 R1。2。1。2。1。2。1。2。333
36、31。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) 从关系图和关系矩阵中不易看清是否有传递性。从关系图和关系矩阵中不易看清是否有传递性。 1。2。1。2。1。2。1。2。33331。2。1。2。1。2。1。2。3333R2R1R3R4R5R6R7R8例如例如A=1,2,A中关系中关系R=是传递的是传递的.R在在A上传递上
37、传递x y z(x A y A z A xRy yRz)xRz)x y z(xRy yRz)xRz) y z(1Ry yRz)1Rz)y z(2Ry yRz)2Rz) ( z(1R1 1Rz)1Rz) z(1R2 2Rz)1Rz) ( z(2R1 1Rz)2Rz) ( z(2R2 2Rz)2Rz) (1R1 1R1)1R1) (1R1 1R2)1R2) (1R2 2R1)1R1) (1R2 2R2)1R2) (2R1 1R1)2R1) (2R1 1R2)2R2) (2R2 2R1)2R1) (2R2 2R2)2R2) (F F)F) (F T)T) (T F)F) (T F)T) (F F)F
38、) (F T)F) (F F)F) (F F)F)T12三个三个特殊关系具有的性质特殊关系具有的性质v非空集合非空集合A上的空关系：上的空关系： v非空集合非空集合A上的全域关系：上的全域关系： v非空集合非空集合A上的恒等关系：上的恒等关系： 本节要求：本节要求： 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 y(x A y A xRy
39、 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自反性自反性反自反性反自反性对称性对称性传递性传递性反对称性反对称性每个结点都有环每个结点都有环 主对角线全是主对角线全是1每个结点都无环每个结点都无环 主对角线全是主对角线全是0不同结点间如果有边不同结点间如果有边,则有方向相反的两条则有方向相反的两条边边.是以对角线为对称是以对角线为对称 的矩阵的矩阵不同结点间不同结点间,最多有一最多有一条边条边.以主对角线为对称以主对角线为对称的位置不会同时为的位置不会同时为1如果有边如果有边,则也有边则也
40、有边. 或者定义的前件为假或者定义的前件为假. 如果如果aij=1,且且ajk=1,则则aik=1关系矩关系矩阵阵关系关系图图 性性质质 判定判定: 下面归纳以上八个关系的性质下面归纳以上八个关系的性质：Y-有有 N-无无1。2。1。2。1。2。1。2。3333R2R1R3R4自反性自反性 反自反性反自反性 对称性对称性 反对称性反对称性 传递性传递性 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
41、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整除整除，求证，求证R是自反、对称和传递是自反、对称和传递的。的。证明证明：证自反性证自反性：任取：任取xI, 因因 x-x=0, 0可被可被3整除整除,所所以有以有R, 故故R自反。自反。证对称性证对称性：任取：任取x,yI,设设R, 由由R定义得定义得 x-y可可被被3整除整除, 即即x-y=3n(nI)， y-x=-(x-y)=-3n=3(-n), 因因-nI, R, 所以所以R对称。对称。证传递性证
42、传递性:任取任取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+nI, 所以所以xRz, 所以所以R传递。传递。 关系的复合关系的复合复合关系的定义：复合关系的定义：设设R是从是从X到到Y的关系，的关系，S是从是从Y到到Z的的关系，则关系，则R和和S的复合关系记作的复合关系记作RS 。定义为：定义为： RS =|x X z Zy(y Y R S)规定：规定： R= R= 。2.2.复合关系的计算方法复合关系的计算方法 A=1,2,3 B=1,2,3.4 C=1,2,3,4,
43、5R AB S BC枚举法枚举法R=, S=, ,则则 RS= R=, S=,有向有向图法图法关系矩阵法关系矩阵法令令A=a1, a2, am B=b1, b2, bn C=c1, c2, ct R AB S BC 。C123。41。2。 3。A1。2。 3。A。B123。4RS5 。C123。45c11=(a11b11)(a12b21).(a1nbn1) = (a1kbk1) (其中其中是逻辑乘是逻辑乘,是逻辑加是逻辑加) 00=0, 01=10=11=1 00=01=10=0, 11=1cij=(ai1b1j)(ai2b2j).(ainbnj) = (aikbkj) (1im, 1jt)M
44、S MR .(aij).(bij).M (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=1nv例：已知例：已知 R=, AA S=, AAv求求 ： RS， SR， RR ， SS， (RS)R，R(SR)三三. .性质性质1.1.满足结合律满足结合律: : R AB S BC T CD 则则 R(ST)= (RS)T 由于由于ST是是B到到D的关系，所以的关系，所以R(ST)是是A到到D的关系。的关系。 (RS)是是A到到C的关系，所
45、以的关系，所以(RS)T是是A到到D的关系。的关系。证明：任取证明：任取R (S T)b(bBR S T)b(bBR c(cCST)b c(bBR(cCST)c b(cC(bBRST)c(cC b(bBRS)T)c (cCR ST)(R S) TABCDRSTR SS TR (S T)(R S) T)所以可以用下图形象表示:2. R是从是从A到到B的关系，则的关系，则 R IB=IA R=R令令A=1,2,3, B=a,b,c,d1。2。 3。AIA。Babc。dR1。2。 3。ARIB。abc。d。Babc。d1。2。 3。AB4. 关系的乘幂关系的乘幂 令令R是是A上关系，由于复合运算可结
46、合，上关系，由于复合运算可结合，所以关系的复合可以写成乘幂形式。即所以关系的复合可以写成乘幂形式。即 R R=R2， R2 R=R R2 =R3，一般地一般地 R0 =IA， Rm Rn = Rm+n (Rm)n =Rmn (m,n为非负整数为非负整数) 逆关系逆关系一一.定义定义 R是从是从A到到B的关系，如果的关系，如果将将R中的所有序偶的中的所有序偶的两个元素的位置互换，得到一个从两个元素的位置互换，得到一个从B到到A的关的关系，称之为系，称之为R的逆关系，记作的逆关系，记作R-1 ，或，或RC 。 RC =| R R RC R二二. 计算方法计算方法 1. R=, RC =2. RC的
47、有向图：是的有向图：是将将R的有向图的所有边的方向的有向图的所有边的方向颠倒一下即可。颠倒一下即可。3. RC的矩阵的矩阵 M =(MR)T 即为即为R R矩阵的转置。如矩阵的转置。如 三三.性质性质令令R、S都是从都是从X到到Y的关系，的关系，则则 1. (RC)C = R 2. (RS)C = RCSC， (RS)C = RCSC 。 3. dom RC =ran R, ran RC =dom R。 4. (R-S)C = RC-SC 。R-11 0 11 0 1 00 0 0 11 0 1 1MR=340 0 01 0 10 1 1MR =-1 435. R S RC SC 。证明证明：
48、充分性充分性，已知，已知RC SC ，则任取则任取R RC SC S R S 必要性必要性，已知，已知R S，则，则任取任取RC R S SC RC SC 6.( R)C= RC证明证明:任取任取( R)C R R RC RC ( R)C= RC7.令令R是从是从X到到Y的关系，的关系，S是是Y到到 Z的关系的关系，则则 (R S)C= SC RC 。证明证明：任取任取(R S)C R Sy(yYRS) y(yYSCRC) SC RC 所以所以(RS)C= SC RC 8. R是是A上关系，则上关系，则R是对称的，当且仅当是对称的，当且仅当 RC =R 证明证明：充分性，已知：充分性，已知 R
49、C=R 任任取取x,y A 设设 R,则则 RC,而而RC=R 所以有所以有 R ，所以所以R对称。对称。必要性，已知必要性，已知R 对称，对称，先证先证RC R，任取任取RC,则则 R,因因R对称，所以有对称，所以有R，所以所以RC R。再证再证R RC，任取任取 R, 因因R对称，所以有对称，所以有R，则则RC, 所以所以R RC。最后得最后得RC =R 。9. R是是A上关系，则上关系，则R是反对称的，当且仅当是反对称的，当且仅当 RRC IA。 证明：证明： 充分性，已知充分性，已知RRC IA， 任取任取x,y A 设设 R 且且R， RR RRC， RRC IA (因因RRC IA
50、 )x=y 所以所以R反对称反对称。必要性，已知必要性，已知R反反对称，对称， 任取任取 RRC RRC R RC R Rx=y (因因R反对称反对称) IA 所以所以RRC IA 。10. R是是A上关系，上关系，则则R是传递的，当且仅当是传递的，当且仅当 RR R。证明：必要性，证明：必要性，对任意的对任意的RR a(aAR R )因为因为R传递，有传递，有R，所以所以RR R。充分性，充分性，对任意的对任意的a、b、cA，若若R R，则由合成运算的定义，则由合成运算的定义，有有 R R，由，由RR R，有，有 R ，所以所以R传递。传递。11 . R是是A上关系，则上关系，则R是自反的，
51、当且仅当是自反的，当且仅当 IA R。 v证明：必要性证明：必要性v由于由于R是自反的，所以，对任意的是自反的，所以，对任意的a A，有，有v R，而，而vIA=| a A，所以，所以IA R。v充分性充分性v由于由于IA=| a A且且IA Rv所以任意的所以任意的a A，有，有 R，v因此因此R自反。自反。一些相关结论一些相关结论v定理定理1 设设R1、R2是是A上的自反关系，则上的自反关系，则R1C、R1R2、R1R2也是也是A上的自反关系。上的自反关系。v定理定理2 设设R1、R2是是A上的对称关系，则上的对称关系，则R1C、R1R2、R1R2也是也是A上的对称关系。上的对称关系。v证
52、明：对任意的证明：对任意的，若若 R1R2 R1 R2 R1 R2 R1R2 所以所以R1R2是是A上的对称关系。上的对称关系。证明证明2：因为：因为R1、R2是是A上的对称关系，所以有上的对称关系，所以有 R1= R1C 、R2=R2C，而，而v（R1R2）C= R1C R2C = R1R2v所以所以R1R2是是A上的对称关系。上的对称关系。定理定理3 设设R1、R2是是A上的传递关系，则上的传递关系，则R1C、R1R2也是也是A上的传递关系。上的传递关系。证明：对任意的证明：对任意的,，若若 R1 R2 R1 R2 R1 R2 R1 R2 R1 R2（ R1、R2传递）传递） R1 R2所
53、以所以R1 R2在在A上传递。上传递。定理定理4 设设R1、R2是是A上的反对称关系，则上的反对称关系，则R1C、R1R2也是也是A上的反对称关系。上的反对称关系。证明：对任意的证明：对任意的 R1 R2,且且xyy R1 R2 R1 R2由于由于R1、R2是反对称的，且是反对称的，且xyy, ,所以有所以有 R1 R2 即即 R1 R2所以所以R1 R2在在A上反对称。上反对称。关系的闭包运算关系的闭包运算 设设R是是A上的关系，有时希望上的关系，有时希望给给R增加一增加一些有序对，构成新关系些有序对，构成新关系R，使得使得R具有自具有自反性、或对称性、或传递性，但不希望反性、或对称性、或传
54、递性，但不希望R太大，即希望增加的有序对尽量少，这就太大，即希望增加的有序对尽量少，这就是闭包的思想。是闭包的思想。 二二. .闭包的定义闭包的定义：给定给定 A中关系中关系R,若若A上另一个关系上另一个关系R，满足：，满足： R R； R是自反的是自反的(对称的、传递的对称的、传递的)； R是是“最小的最小的”，即对于任何，即对于任何A上自反上自反(对称、对称、传递传递)的关系的关系R, 如果如果R R, 就有就有R R。则称则称R是是R的的自反自反(对称、传递对称、传递)闭包。记作闭包。记作r(R)、(s(R) 、t(R) (reflexive、 symmetric、transitive)
55、三三. .计算方法计算方法定理定理1.给定给定 A中关系中关系R,则则 r(R)=RIA。证明：令证明：令R=RIA,显然显然R是自反的和是自反的和R R。 下面证明下面证明R是是“最小的最小的”： 如果有如果有A上自反关系上自反关系R且且R R, 由于由于R是自反的，有是自反的，有IA R, 所以所以 RIA R, 即即R R。所以所以R就是就是R的自反闭包。即的自反闭包。即r(R)=RIA 。定理定理2.给定给定 A中关系中关系R,则则 s(R)=RRC 。v证明：证明： (1)显然显然R RRCv(2)对对 RRC,有有 R RCv即即 RC Rv所以所以 RRC， 即即RRC是对称的。
56、是对称的。v（3）设）设R是对称的，且是对称的，且R R，v对对任意的任意的v RRC R RCv若若 R，则，则 R（ R R）v若若 RC ，有，有 R，即，即 R，v由于由于R对称，所以对称，所以 R，v所以所以RRC R。v所以所以s(R)= RRC定理定理3. 给定给定 A中关系中关系R, 则则 t(R)=RR2R3. 。v证明：令证明：令R= RR2R3., 显然有显然有 R R ； 证证R是传递的：任是传递的：任取取x,y,z A,设有设有 R R, 由由R定义得必存在整数定义得必存在整数i,j使得使得 Ri , Rj ,根据关系的复合得根据关系的复合得 Ri+j, 又因又因Ri
57、+j R,所以所以 R, R传递传递。定理定理3. 给定给定 A中关系中关系R, 则则 t(R)=RR2R3. 。v（令（令R= RR2R3.,）证证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的传递闭包，
58、即的传递闭包，即 t(R)=RR2R3=Rii=1例例: A=1,2,3 A中关系中关系R,S,T,如下：如下： R=, S =, T =,求求t(R)，t()，t()定理定理4. 给定给定 A中关系中关系R,如果如果A是有限集合，是有限集合，|A|=n,则则 t(R)=RR2.Rn 。证明：证明：令令R=RR2R3., R=RR2.Rn ，显然有显然有R R。下面证明。下面证明R R：任取任取 R,由由R定义得必存在定义得必存在最小的最小的正整数正整数p 使使得得 RP , (下面证明下面证明Pn)如果如果Pn,根据关系的复合得根据关系的复合得A中必存在中必存在p-1个元素个元素e1, e2
59、,.,ep-1，使得使得 R R. R。令令x= e0，y= eP 因为因为|A|=n，所以，存在正整数所以，存在正整数t，q，0tqp，使得et= eq由此，序列可去掉中间一段成为由此，序列可去掉中间一段成为 R. R且且 R. R所以，所以， Rk，其中，其中，k=t+p-qp，与，与p最小矛盾。最小矛盾。故故 R，即，即R=R。求求t(R)的矩阵的矩阵Warshall算法：算法：|X|=n, R XX, 令令MR=A R2的矩阵的矩阵为为A2， Rk的矩阵的矩阵为为Ak .于是于是t(R)的的矩阵记作矩阵记作MR+=A+A2+Ak + (+是逻辑是逻辑加加)置新矩阵置新矩阵 A :=MR
60、 ;置置 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=1 ,2行行+2行行2行行 A不变不变 A4,2=1 ,4行行+2行行4行行,4行全
61、行全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)A=MR=A=A的初值:A=A=四四. 性质性质定理定理5. R是是A上关系，则上关系，则R是自反的，当且仅是自反的，当且仅当当 r(R)=R. R是对称的，当且仅当是对称的，当且仅当 s(R)=R. R是传递的，当且仅当是传递的，当且仅当 t(R)=R.
62、四四. 性质性质定理定理6. R是是A上关系，则上关系，则R是自反的，则是自反的，则s(R)和和t(R)也自反。也自反。 R是对称的，是对称的，则则r(R)和和t(R)也对称。也对称。 R是传递的，则是传递的，则r(R)也传递。也传递。证明证明: 因为因为R自反自反,所以所以IA R,由于由于s(R) = RRC t(R)=RR2R3，所以所以IA s(R) IA t(R)s(R)、t(R)自反自反 R是对称的，是对称的，则则r(R)和和t(R)也对称也对称。证明证明. 证明证明t(R)对称对称:(t(R)C=(RR2.Rn.)C = RC(R2)C .(Rn)C. = RC(RC)2 .(R
63、C)n. =RR2.Rn. (R对称，对称，RC =R) =t(R) 所以所以t(R)也对称。也对称。(R2)-1=(R R)-1=R-1 R-1=(R-1)2 R是传递的，则是传递的，则r(R)也传递也传递。证明：因为证明：因为R传递，所以，传递，所以， R2R。又r(R)=R IA, 所以所以(r(R)2= r(R)r(R) = (RIA)(RIA) =(RR)(RIA)(IAR)(IA IA) = R2RR IA R IA = r(R)所以， r(R)是传递的。 四四. 性质性质定理定理7：设：设R1、R2是是A上关系，如果上关系，如果R1 R2 ，则则 r(R1) r(R2) s(R1
64、) s(R2) t(R1) t(R2) 证明证明 r(R1)=IAR1 IAR2= r(R2) (或证或证 由定义由定义R2 r(R2)，由于由于R1 R2， 有有R1 r(R2)，因为因为r(R2)是自反的，所以，由闭包定义，得是自反的，所以，由闭包定义，得r(R1) r(R2)。) 定理定理. R1和和R2是是A上关系，求证上关系，求证 a) r(R1R2)= r(R1)r(R2) , b) s(R1R2)= s(R1)s(R2) , c) t(R1)t(R2) t(R1R2) , 证明证明： a) r(R1R2)= (R1R2)IA = (R1IA) (R2IA) =r(R1)r(R2)
65、 , b) s(R1R2)= (R1R2)(R1R2)C =(R1R2)(R1)C (R2)C =(R1(R1)C ) (R2(R2)C) =s(R1)s(R2) , c)因因 R1 (R1R2)且且R2 (R1R2)，得，得 t(R1) t(R1R2), t(R2) t(R1R2)，所以所以有有 t(R1)t(R2) t(R1R2)。四四. 性质性质定理定理9：设设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 = (R
66、RC) IA= s(R)IA=rs(R) 练习练习：给定：给定A中关系中关系R如图所示：分别画如图所示：分别画出出r(R)、s(R) 、t(R)、sr(R)、rs(R)、 tr(R)、rt(R)、st(R) 、ts(R) 的图。的图。1。2。431。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)归纳：关系性质证明方法归纳：关系性质证明方法设设R是是A上关系上关系，一一. .证明证明R R的自反性：的自反性：方法方法1 用自反定义证：任用自反定义证：任取取
67、 xA,证出证出R.方法方法2 用恒等关系用恒等关系IA证：证：证出证出IA R. 方法方法3 用自反闭用自反闭包证：包证：证出证出r(R)=R, 即即RIA=R.二二. .证明证明R R的反自反的反自反性：性：方法方法1 用反自反定义证：任用反自反定义证：任取取 xA,证出证出 R.三三. .证明证明R R的对称性：的对称性：方法方法1 用对称定义证：用对称定义证： 任取任取 x,yA,设设R, 证出证出 R.方法方法2 用求逆关系证用求逆关系证：证出证出 RC=R.方法方法3 用对称闭包证用对称闭包证：证出证出 s(R)=R, 即即RRC =R.四四. .证明证明R R的反对称性：的反对称
68、性：方法方法1 用定义用定义1证：证： 任取任取 x,yA,设设R, R.证出证出 x=y。方法方法2用定义用定义2证：证： 任任取取 x,yA,xy, 设设R,证出证出 R. 方法方法3 用定理证用定理证：证出证出 RRC IA .五五. .证明证明R R的传递性：的传递性：方法方法1 用传递定义证：用传递定义证： 任取任取 x,y,zA,设设R,R, 证出证出 R.方法方法2 用传递闭包证用传递闭包证：证出证出 t(R)=R, 即即 RR2R3. =R.方法方法3用定理证：用定理证：证出证出 R RRo例例 R和和S都都A上是自反、对称、传递的，求证上是自反、对称、传递的，求证RS也也是自
69、反、对称和传递的。是自反、对称和传递的。证明证明：一：一. .证明证明R RS的自反性的自反性方法方法1 用自反定义证用自反定义证：任取：任取 xA, (证出证出RS)因因R和和S都自反，所以都自反，所以有有R，S，于是于是有有RS，所以所以RS也自也自反。反。方法方法2 用恒等关系用恒等关系IA证：证：(证出证出IA RS)因因R和和S都自反，所以都自反，所以 IA R ，IA S，所以所以 IA RS所以所以RS也自反也自反。方法方法3 用自反闭包证：用自反闭包证： (证出证出r(RS)=RS, 即即 (RS)IA= RS)因因R和和S都自反，所以都自反，所以r(R)=R, r(S)=S,
70、 r(RS)=(RS)IA= (RIA)(SIA)= r(R)r(S)=RS所以所以RS也自反。也自反。二二. .证明证明RSRS的对称性：的对称性：方法方法1 用对称定义证：用对称定义证： 任取任取 x,yA,设设RSS, (证出证出 RSS.)则则R，S S，因为因为R R和和S S对称，所以对称，所以有有R，S S，于是于是RSS。RSS对称。对称。方法方法2 用求逆关系证：用求逆关系证：(证出证出 (RSS)C=RSS.)因为因为R R和和S S对称，所以有对称，所以有RC=R， S SC=S S，而而(RSS)C=RCSSC= RSS ， RSS对称对称。方法方法3 用对称闭包证：用
71、对称闭包证： (证出证出 s(RSS)=RSS, 即即(RSS)(RSS)C =RSS.)因为因为R R和和S S对称，所以对称，所以s(R)=R,s(S)=Ss(R)=R,s(S)=Ss(RSS)= (RSS)(RSS)C =(RSS)(RCSSC) =(RRC)(RS SC)(SS SC)(S SRC) =(s(R)(RS SC)(s s(S)(S SRC) =(R(RS SC)(S(S SRC)=RS (吸收律吸收律)RSS对称对称。五五. .证明证明RSS的传递性：的传递性：方法方法1 用传递定义证：任取用传递定义证：任取 x,y,zA, 设设RSS,RSS, (证出证出RSS)RSS
72、RSS RS SRS S (RR)(S S S)S) RS S （因为因为R、S传递传递） RS S 所以所以RSS传递传递。 方法方法2 用传递闭包证：用传递闭包证：证出证出 t(RSS)=RSS, 即即 (RSS)(RSS)2(RSS)3. =RSS.方法方法3用定理证用定理证：证出证出用用方法方法2、方法方法3证明此题的传递性有很大难度。证明此题的传递性有很大难度。R(ST) (RS)(RT)(RS) (RS) (RS) o练习：练习：） R和和S都是都是A上关系，上关系，a) R和和S都自反，都自反，则则 是否是否自反。自反。 b) R和和S都反自反，都反自反，则则 是否是否反自反。反
73、自反。c) R和和S都对称，都对称，则则 是否是否对称。对称。d) R和和S都传递，都传递，则则 是否是否传递。传递。） S是上关系，证明是上关系，证明若若是自反和传递，则是自反和传递，则=S。其逆为真吗？其逆为真吗？3）设设R是集合是集合A上的一个自反关系上的一个自反关系,求证：求证： R是对称和传递的，当且仅当是对称和传递的，当且仅当 和和在在R中中,则有则有也在也在R中。中。R SoR SoR SoR So So例例.R和和S都是都是A上等价关系上等价关系,下面哪个是下面哪个是A上等价关系上等价关系?证明或举反例说明证明或举反例说明. a) RS b) RS c) -R (即即AA-R)
74、 d) R-S e)R2 f) r(R-S)解解.a) c) d) f)不是不是. 请看反例请看反例:R。a。cb。a。cb。a。cb。SRS。a。cb。-R。a。cb。R。a。cb。R-S。a。cb。r(R-S) 集合的划分与覆盖集合的划分与覆盖一一. .定义定义 设设X是一个非空集合是一个非空集合,A=A1, A2,. ,An, Ai Ai X (i=1,2,.,n),如果满足如果满足A1A2.An =X (i=1,2,., n)则称则称A为集合为集合X的的覆盖覆盖。 设设A=A1, A2,. ,An是是X一个覆盖一个覆盖, 且且 Ai Aj= (i j,1i,jn)则则称称A是是X的的划
75、分。划分。每个每个Ai均称为这个划分的一个均称为这个划分的一个划分块划分块(类类)。例例 X=1,2,3, A1=1,2,3, A2=1,2,3,A3=1,2,3, A4=1,2,2,3, A5=1,3划分划分,一定是覆盖；但覆盖一定是覆盖；但覆盖, 不一定是划分不一定是划分。二二. .最小划分与最大划分最小划分与最大划分最小划分最小划分：划分块最少的划分。即只有一：划分块最少的划分。即只有一个划分块的划分，这个划分块就是个划分块的划分，这个划分块就是X本本身。身。最大划分最大划分：划分块最多的划分。即每个划：划分块最多的划分。即每个划分块里只有一个元素的划分。分块里只有一个元素的划分。 等价
76、关系与等价等价关系与等价类类一一. .等价关系等价关系1.定义定义:设设R是是A上关系上关系,若若R是自反的、对称的和是自反的、对称的和传递的，则称传递的，则称R是是A中的等价关系。中的等价关系。若若a,b A，且，且aRb，则称，则称a与与b等价。等价。例：集合例：集合A=1,2,3,4,5,6,7, R是是A上的模上的模3同余关系，即同余关系，即R=|x-y可被可被3整除整除 2.等价关系的关系图等价关系的关系图 1)完全关系完全关系(全域关系全域关系AA)图，下面分别是图，下面分别是当当A中只有中只有1、2、3个元素时的完全关系图。个元素时的完全关系图。2）.等价关系的关系图等价关系的关
77、系图:等价关系等价关系R的关系图由若干个独立子图构成，每个独立子的关系图由若干个独立子图构成，每个独立子图都是完全关系图图都是完全关系图。1。2。1。2。3。1。A=1A=1,2A=1,2,3A=1,2,3，下面，下面是是A中关系，判断那些关中关系，判断那些关系是等价关系系是等价关系1。2。1。2。331。2。1。2。1。2。1。2。3333R2R1R5R61。2。1。2。33R3R4R7R8思考题思考题：A=1,2,3,可构造多少可构造多少个个A中不同的等中不同的等价关系？可以根据等价关系有向图的特点来考虑。价关系？可以根据等价关系有向图的特点来考虑。 如果等价关系如果等价关系R中有中有 a
78、)三个独立子图的情形，则三个独立子图的情形，则( )个等价关系个等价关系 。 b)二个独立子图的情形，则二个独立子图的情形，则( )个等价关系个等价关系 。 c)一个独立子图的情形，则一个独立子图的情形，则( )个等价关系个等价关系 。一共有一共有( )个个中不同的等价关系。中不同的等价关系。二二. . 等价类等价类1.1.定义定义：R R是是A A上的等价关系上的等价关系，aA,aA,由由a a确定确定的集合的集合 aaR R: : a aR R=x|xAR=x|xAR称集合称集合 aaR R为由为由a a生生成成的的R R等价类。简称等价类。简称a a等等价类。价类。可见可见 xaxaR
79、R R不同的等价类个数不同的等价类个数=独立子图个数。独立子图个数。上述三个等价关系各有几个等价类？说出对应的上述三个等价关系各有几个等价类？说出对应的各个等价类。各个等价类。1。2。3R21。2。3R1。R3。1233.等价类性质等价类性质 R是是A上等价关系，任意上等价关系，任意a,b,cA aaR R ，且aaR R A A。 aaR RbbR R=， 当且当且仅当仅当 R R。证明证明:设设 R R，假设假设aaR RbbR R,则存在则存在xaaR RbbR R， xaaR RxbbR R,R ,R,由由R对称得对称得R又又由由R传递得传递得R,产生矛盾。产生矛盾。 若若aaR Rb
80、bR R=,而而R,由等价类定义得由等价类定义得baaR R, 又因为又因为bRb,所以所以bbbR R，所以所以baaR RbbR R，产生矛盾。产生矛盾。3.等价类性质等价类性质 aaR R=bbR R 当且当且仅当仅当 R R。证明：若证明：若R R，则任何则任何xxaaR R，有有 Ra,xR，由对称性得由对称性得 Rb,aR，再由传递性得再由传递性得 R,xb,xR,xbbR R，所以所以 aaR R bbR R。 类似可证类似可证 bbR R aaR R。 aaR R=bbR R。 如果如果aaR R=bbR R，由于有由于有aRa,所以所以aaaR R ， 又由于又由于 aaR
81、R= bbR R， 有有abbR R ，所以有所以有R R，由对称性得由对称性得 R.a,bR.三三. . 商集商集 从算术角度看从算术角度看：1用用4除除,每份每份1/4,这就这就是是“商商”,于是于是: 1=1/4+1/4+1/4+1/4 从集合角度看从集合角度看： 用刀分生 日日快快乐乐生商集的商集的定义定义定义定义：R是是A上等价关系，由上等价关系，由R的所有等价类构成的所有等价类构成的集合称之为的集合称之为A关于关于R的商集。记作的商集。记作A/R。即即 A/R=aaR R |aA。定理定理: 集合集合A上的等价关系上的等价关系R，决定了决定了A的一个划分，该划分就是商集的一个划分，
82、该划分就是商集A/R.证明：由等价类性质可得证明：由等价类性质可得 ： 1) 对任意的对任意的a A ，aR ，且，且aR A. 2) 设设aR,bR是是A/R的两个不同元素，有的两个不同元素，有 aR bR=；所以，只需要证明所以，只需要证明 3) a A aR=A。显然。显然a A aR A，由对，由对任任意的意的a A，有，有a aR a A aR，所以有，所以有A a A aR，因此，因此， a A aR A。综上所述，商集综上所述，商集A/R是是A的一个划分。的一个划分。四四. . 由划分确定等价关系由划分确定等价关系例如，例如，X=1,2,3,4,A=1,2,3,4, A是是X的一
83、个划分，求的一个划分，求X上一个上一个等价关系等价关系R，使得使得X/R=A。等价关系集合的划分A/R？2。1。3。4。定理定理: 集合集合X的一个划分可以确定的一个划分可以确定X上上的一个等价关系。的一个等价关系。证明：假设证明：假设A=A1, A2,. ,An是是X的一个划分，如下构的一个划分，如下构造造X 上上的一个等价关系的一个等价关系R: R= A12A22,An2 其中其中Ai2 = AiAi，(i=1,2n). 1) 证证R自反自反：任取：任取aX，因为因为A是是X的划分，必存在的划分，必存在Ai A使使a Ai ,于是于是AiAi , 又又AiAi R 有有aRa。 2) 证证
84、R对称对称：任取任取a,bX, 设设aRb，必存在必存在Ai A使得使得AiAi ,于是于是a,b Ai , bRa, R是对称的。是对称的。 3) 证证R传递传递：任取任取a,b,cX, 设设aRb，bRc, 必存在必存在Ai A使得使得AiAi ,AiAi , (不可能有另一个划分块不可能有另一个划分块Ak A使得使得AkAk, 因为因为 如果这样，就使得如果这样，就使得, 既既bAi又又b Ak ,与与A是划分矛盾。是划分矛盾。)于是于是a,b,c Ai , 所以所以AiAi ，又又AiAi R 有有aRc 所以所以R传递。传递。最后最后得得R是集合是集合X中的关系。中的关系。 相容关系
85、相容关系 一一. .定义定义:给定集合给定集合X上的关系上的关系r, 若若r是自反的、是自反的、对称的对称的,则则r是是A上上相容关系。相容关系。 例子例子：X 是由一些英文单词构成的集合。是由一些英文单词构成的集合。 X=fly, any, able, key, book, pump, fit, X上关上关系系r: r=|X,X且且与与含有相同字母含有相同字母 r的的关系关系图图any。ablefly。key。bookpump。fit。yaebklyfy二二. . 简化图和简化矩阵简化图和简化矩阵图的简化图的简化：不画环；不画环； 两条对称边用一条无向直线代替。两条对称边用一条无向直线代替。
86、令令x1=fly, x2= any, x3= able, x4=key, x5=book, x6= pump,x7= fit, X=x1 ,x2, x3, x4, x5, x6 ,x7, r的简化图为：的简化图为：矩阵的简化矩阵的简化：因为：因为r的矩阵是对称阵且主对角线全是的矩阵是对称阵且主对角线全是1，用下三角矩阵用下三角矩阵(不含主对角线不含主对角线)代替代替r的矩阵。的矩阵。x2。x1。x3x4。x5。x6。x7。x1x2x3x4x5x6x7x6x5x4x3x211111111 100000 0 00 0 000三三. .相容相容类类定义定义：设：设r是集合是集合X上的相容关系，上的相
87、容关系，C X,如果如果对于对于C中任意两个元素中任意两个元素x,y有有r ,称称C是是r的一个的一个相容类相容类。 x2。x1。x3x4。x5。x6。x7。最大相容类最大相容类定义定义：设：设r是集合是集合X上的相容关系，上的相容关系，C是是r的一个相容类，的一个相容类，如果如果C不能被其它不能被其它相容类所真包含，则相容类所真包含，则称称C是一个是一个最最大相容类。大相容类。 x2。x1。x3x4。x5。x6。x7。 从简化图找最大相容类从简化图找最大相容类：-找最大完全多边形。找最大完全多边形。最大完全多边形最大完全多边形：含有结点最多的多边形中，每个：含有结点最多的多边形中，每个结点都
88、与其它结点相联结。结点都与其它结点相联结。 在相容关系简化图中，在相容关系简化图中，每个最大完全多边形的结点每个最大完全多边形的结点集合构成一个最大相容类。集合构成一个最大相容类。 。x1。 。 给定给定X上相容关系上相容关系r ,如图所示如图所示,r的最大相容类：的最大相容类： x2。x3 。x1。x4。x5。结论结论v定理定理1 1 设设A ，r是A上的相容关系，则r的最大相容类集合是A的一个覆盖。v定理2 2 设设A ， C=A1, A2,. ,An是是A的的覆盖，则覆盖，则C确定的关系确定的关系 r= A1A1A2A2AnAn 是是A上的相容关系。上的相容关系。偏序关系偏序关系 数值的
89、数值的、关系；、关系； 集合的集合的 、 关系；关系； 图书馆的图书按书名的字母次序排序；图书馆的图书按书名的字母次序排序； 词典中的字词典中的字(词词)的排序；的排序； 计算机中文件按文件名排序计算机中文件按文件名排序. 一一. . 偏序关系偏序关系(partial order relation)1. 定义定义：R是是A上自反、反对称和传递的关系，则称上自反、反对称和传递的关系，则称R 是是A上的偏序关系。并称上的偏序关系。并称是偏序集。是偏序集。用符号用符号“”表示任意偏序关系。表示任意偏序关系。 例例1 A=1,2,4,6, 是是A中的整中的整除关系，其关系图如右图，除关系，其关系图如右
90、图，2. x与与y是可比较的是可比较的：是偏序集是偏序集，x,yA，如如果要么果要么xy,要么要么yx, 则称则称x与与y是可比较的。是可比较的。2。1。64二二. .全序全序( (线序、链线序、链) )定义定义：是偏序集，任何是偏序集，任何x,yA，如果如果x与与y都是可比较的，则称都是可比较的，则称是全序关系是全序关系(线序、链线序、链)。例例2 B=1,2,4,8,表示整除关系，表示整除关系，如图：如图： 全序关系一定是偏序关系，但是偏序不一定是全序关系一定是偏序关系，但是偏序不一定是全序。全序。 2。1。84“盖盖住住”v定义：定义：是偏序是偏序集，集，x,y，如果如果xy,且且xy，
91、且且不存在不存在zA,使得使得 zxzyxzzy，则称则称元素元素y盖住元素盖住元素x。元素元素y盖住盖住x xyxyz(zAzxzyxz zy)记记COV A=| x,y, y盖住盖住x.例：例：A=1,2,3,4,6,12, 为整除关系，为整除关系， 求求COV A。偏序集偏序集Hasse图的画法：图的画法：令令是偏序集，是偏序集，1.用用“ ”表示表示A中元素。中元素。2.如果如果xy,且且xy，则结点则结点y要画在结点要画在结点x的上方。的上方。3. 如果如果xy,且且y盖住盖住x，x与与y之间连一直线。之间连一直线。4. 一般先从最下层结点，逐层向上画，直到最上层结一般先从最下层结点
92、，逐层向上画，直到最上层结点。点。(采用抓两头，带中间的方法采用抓两头，带中间的方法 )。例例:画出下列两个图的画出下列两个图的Hasse图图2。1。642。1。84练习：练习：C=1,2,3,6,12,24,36, D=1,2,3,5,6,10,15,30 是是C、D上上整除关系整除关系：画出画出, 的的Hasse图：图：以及以及A=a,b,c， 的的Hasse图：图：四四. .偏序集中的重要元素偏序集中的重要元素分别介绍这些偏序集中的重要元素：分别介绍这些偏序集中的重要元素：极小元、极大元、最小元、最大元、极小元、极大元、最小元、最大元、上界、下界、上确界、下确界，上界、下界、上确界、下确
93、界，一一. .极小元与极大元极小元与极大元设设是偏序集，是偏序集，B是是A的非空子集。的非空子集。若若 y(yBx(xBxyx=y)，则称，则称y是是B的的极小元。极小元。 若若 y(yBx(xByxx=y)，则称，则称y是是B的的极大元。极大元。 例例，给定，给定的的Hasse图图如图所示：如图所示： 。12。24。36。子集子集B极小元极小元极大元极大元2,31,2,36,12,24A2, 32, 312, 3624124,36二二. .最小元与最大元最小元与最大元 若若 y(yB x(xB yx)，则称，则称y是是B的的最最小元。小元。 若若 y(yB x(xB xy)，则称，则称y是是
94、B的的最最大元。大元。 例例，给定，给定的的Hasse图图如图所示：如图所示： 。12。24。36。子集子集B最小元最小元最大元最大元2,31,2,36,12,24A无无无无1无无6241无无性质性质v对对任意非空有限集合任意非空有限集合B，极大（小）元必存在，但极大（小）元必存在，但极大（小）元不一定唯一。极大（小）元不一定唯一。v不同的极大（小）元之间是无关的。不同的极大（小）元之间是无关的。vB的最小元应小于等于的最小元应小于等于B中其他各元。中其他各元。vB中其他各元应小于等于中其他各元应小于等于B的最大元。的最大元。v最大（小）元不一定存在，但若存在，必唯一。如最大（小）元不一定存在
95、，但若存在，必唯一。如果果B有唯一的极小有唯一的极小(大大)元，则这个极小元，则这个极小(大大)元就是元就是最小最小(大大)元。否则就没有最小元。否则就没有最小(大大)元。元。性质性质定理定理：是偏序集是偏序集，B是是A的非空子集，如的非空子集，如果果B有最小元有最小元(最大元最大元)，则最小元，则最小元(最大元最大元)是唯是唯一的。一的。证明证明：假设：假设B有两个最小元有两个最小元a、b, 因为因为a是是最小元最小元，bB，根据根据最小元定义，有最小元定义，有 ab;类似地，因为类似地，因为b是是最小元，最小元，aB，根据根据最小元定最小元定义义，有，有ba。因为因为有反对称性，所以有有反
96、对称性，所以有 a=b。 3.3.上界与下界上界与下界 (Upper Bound and Lower Bound) 若若 y(yA x(xBxy)，则称，则称y是是B的的上界上界 若若 y(yA x(xB yx)，则称，则称y是是B的的下界下界例例，给定，给定的的Hasse图如图所示：图如图所示： 。12。24。36。子集子集B上界上界下界下界2,31,2,36,12,24A 16,12,24,361246,2,3,11无无6,12,24,364. 4. 最小上界最小上界( (上确界上确界) )和最大下界和最大下界( (下确界下确界) ) (Least Upper Bound and Grea
97、test Lower Bound) (Least Upper Bound and Greatest Lower Bound)定义定义1：设：设C= y|y是是B的上界的上界，则，则C的最小元的最小元称为称为B的的最最小上界小上界( (上确上确界界) ) 。定义定义2：设：设C= y|y是是B的下界的下界，则，则C的最大的最大元元称为称为B的的最最大下界大下界( (下确界下确界) ) 。 举例举例，给定，给定的的Hasse图如图所示：图如图所示：。12。24。36。子集子集B上界上界下界下界2,31,2,36,12,24A 16,12,24,361241,2,3,61无无6,12,24,36上确
98、界上确界下确界下确界6624无无1161例：设例：设A=a,b,c, 的的Hasse图如下：图如下：vB=a,b,b,c,b,c, ,则B的v极大元：v极小元：v最大元：v最小元：v上界：v下界：v上确界：v下确界：下确界： a,b,c。b。a。c。a,c。b,c。a,b。例：设例：设A=a,b,c, 的的Hasse图如下：图如下：vB=a,c,则B的v极大元：v极小元：v最大元：v最小元：v上界：v下界：v上确界：v下确界：下确界： a,b,c。b。a。c。a,c。b,c。a,b。相关性质相关性质v定理定理 设设是一个偏序集，是一个偏序集，BA，则（1）若）若b是是B的最大（小）元，则它必的
99、最大（小）元，则它必是是B的的极大（小）元。极大（小）元。（2）若）若b是是B的最大（小）元，则它必是的最大（小）元，则它必是B的的上（下）确界。上（下）确界。（3）若若b是是B的上（下）确界，且的上（下）确界，且bB，则，则b必是必是B的最大（小）元。的最大（小）元。链与反链链与反链v定义定义：设：设是一个偏序集，是一个偏序集，B BA A，（1 1）若x xy(xByBxyyx)y(xByBxyyx)，则称B B为A A上的链，B B中的元素个数称为链B B的长度。（2 2）若x xy(xByBy(xByB (xyyx(xyyx)，则称B B为A A上的反链，B B中的元素个数称为反链B
100、B的长度。规定：若B B只含有一个元素，则B B既是链又是反链。例：例：A=2,3,4,6,9,12,18，A上的整除关系。上的整除关系。v其其Hasse图如下图，则图如下图，则vA上的链为：上的链为：vA上的反链为：上的反链为：结论：若结论：若是全序关系，则是全序关系，则A是链，是链，且且A的任何子集是链。的任何子集是链。12。4。18。2。6。3。9。定理：定理：是偏序集，设是偏序集，设A中最长链的长度为中最长链的长度为n，则，则A中存在一个中存在一个由由n个反链组成的划分。个反链组成的划分。v证明：证明：n=1时，时，A就是一个反链，所以定理结论成立。就是一个反链，所以定理结论成立。v假
101、设对假设对n=k，结论成立。考虑结论成立。考虑n=k+1的情形。的情形。v当当A中中最长链的长度为最长链的长度为k+1时，时，令令M为为A中极大元的中极大元的集合，集合，v显然显然M是反是反链，而链，而A-M中最长链的长度为中最长链的长度为k，v由归纳假设由归纳假设，A-M中存在一个由中存在一个由k个反链组成的划分，个反链组成的划分，v加上加上反链反链M，A中存在一个由中存在一个由k+1个反链组成的划分。个反链组成的划分。 五五. .良序良序定义定义：是偏序集，如果是偏序集，如果对对A的任何非空子集的任何非空子集B都有最小元，则称都有最小元，则称是是A上的良序，并称上的良序，并称为良为良序集。
102、序集。定理定理：所有：所有良序集，一定是全序集。良序集，一定是全序集。证明证明：设：设为良序集为良序集,任取任取x,yA,构成子集构成子集x,y,它有最小元，该最小元或是它有最小元，该最小元或是x,或是或是y, 于是有于是有xy或或yx，所以所以是全序集。是全序集。定理定理：有限的：有限的全序集，一定是良序集。全序集，一定是良序集。证明证明：设：设A=a1,a2,an,是全序集，假设它是全序集，假设它不不是良序，必存在非空子是良序，必存在非空子集集B A，B中无最小元，因中无最小元，因B是有限集，必存在是有限集，必存在x,yB,使得使得x y 且且y x,与与是是全序矛盾全序矛盾，是良序集。是
103、良序集。枚举法枚举法关系图关系图矩阵矩阵*等价关系等价关系有有向向图图等等价价类类商商集集划划分分偏序关系偏序关系相相容容类类最最大大相相容容类类完完全全覆覆盖盖简简化化图图全全序序哈哈斯斯图图重重要要元元素素计算方法计算方法运算性质运算性质二二元元关关系系概念及表示方法概念及表示方法性性质质*自反自反对称对称传递传递反对称反对称反自反反自反相容关系相容关系运运算算复合复合求逆求逆闭包闭包谓词谓词* A=1,2,3，A上五个关系如下：上五个关系如下：下述五个关系中，下述五个关系中，哪些是等价关系？如果是等价关系，求其商集。哪些是等价关系？如果是等价关系，求其商集。哪些是相容关系？如果是相容关系，求其完全覆盖。哪些是相容关系？如果是相容关系，求其完全覆盖。哪些是偏序关系？如是偏序关系哪些是偏序关系？如是偏序关系,画画Hasse图图,并求的极并求的极小小(大大)元、最小元、最小(大大)元、上界与下界、上确界和下确界。元、上界与下界、上确界和下确界。132。132。132。132。132RSTAARAATS 自反 反自反 对称 反对称 传递N N N Y Y Y N Y N Y Y N N Y Y N Y Y Y Y Y N Y N Y
