离散数学3 集合与关系.pdf

离散数学（Discrete Mathematics张捷2012-3-18Copyright：张捷第三章集合与关系(Set s and Re I at i o ns)本章首先采用朴素集合论的方法，介绍有关集合的一些基本 知识，内容显得较为直观，学起来易于接受。但集合及其相关的 概念是本门课程后面各章内容的基础，同学们务必熟练的掌握。本章重点讨论关系(主要是二元关系)，它仍然是一种集合,但它是一种更为复杂的集合。它的元素是有序二元组的形式,这些有序二元组中的两个元素来自于两个不同或者相同的集 合。因此，关系是建立在其它集合基础之上的集合。关系中 的有序二元组反映了不同集合中元素与元素之间的关系，或 者同一集合中元素之间的关系。本章讨论这些关系的表示方 法、关系的运算以及关系的性质，最后讨论集合A上几类特 殊的关系。2012-3-18Copyright：张捷2第三章集合与关系(Set s and Re I at i o ns)3.1 集合及其运算(Se ts&O pe ratio n s with s e ts)3.2 序偶与笛卡尔积(O rde re d P airs&Carte s ian P ro duct)3.3 关系(Re latio n s)3.4 关系的性质(The P ro pe tie s o f Re latio n s)(函数)3.5复合关系与逆关系(Co m po un d Re latio n s&I n ve rs e 3.徐奥臻的就|包运算(Clo s ure O pe ratio n s)3.7 集合的划分与覆盖(P artitio n&Co ve r o f Se ts)3.8 等价关系(Eq uivale n t Re latio n s)3.9 相容关系(Co m patib ility Re latio n s)序关系(O rde re d&官褊初雕)3第三章集合与关系(Set s and Re I at i o ns)3.1 集合及其运算(Se ts&O pe ratio n s with s e ts)3.1.1 集合和元素(Se ts&Ele m e n ts)3.1.2 集合间的关系(Re latio n s b e twe e n s e ts)3.1.3集合的运算和运算定律(O pe ratio n s with s e ts&O pe ratio n laws)3.1.4 塞集(P o we r s e t)2012-348Copyright：张捷4第三章集合与关系3.1 集合及其运算(Se ts&O pe ratio n s with s e ts)3.1.1 集合和元素(Se ts&Ele m e n ts)1.集合和元素定义3.L1把一些确定的、彼此不同的事物作为一 个整体来看待时，这个整体便称为是一个集合。组成集合的那些个体称为集合的元素。例如全体中国人可组成一个集合，每一个中国人均是这个集合的 元素.又例如所有的正整数组成一个集合，每一个正整数均是这个集合的元素O苏常用笑.英文字母来标记集合，用小写英文字母标 记组成集合的个体.若个体a是集合A的元素，则记作“aA”若a不是集合A的元素，则记作“空A”2012-3-18Copyright：张捷52.几个常用集合的表示符号:N：所有自然数的集合。Q：所有有理数的集合。Z：所有整数的集合。R：所有实数的集合。C:所有复数的集合。P：所有素数的集合。Nm：从1到n i,这n i个正整数的集合。Zm：从0到m-1,这m个非负整数的集合。R+：所有正实数的集合。R-：所有负实数的集合。于是2 N,2.5 e N,3 e N,但2.5Q,-3e io2012-3-18Copyright：张捷3.集合的表示方法列举法：按任意顺序逐一列举集合中的元素于花括号 内，元素之间用逗号隔开。例如：A=2,a,b,9,B=4,5,6,7,8描述法：给定一个条件P(x),当且仅当个体a使P(a)成立时,aEAo其一般形式为A=a|P(a)例如上述集合B二aaN 且 4WaW8又如C二D=2 xI ie z+,BP C=2,21,22,23,.xEZ+x50,即D=0,2,4,6,2012-3-18Copyright：张捷74.集合的基数集合A中不同元素的个数称为集合A的基数，记作 A.例如上页中的集合，四二4,跳5,|。卜51,集合C 有无穷多个元素，因此C的基数是无穷大。若|/|是有限数，则称A为有限集，否则称A为无限集。例如N,Z+,1,R等均为无限集。5.空集定义3.1.2不含有任何元素的集合，称为空集，记学例如 A=x|x R 且 x2+8=0=02012-3-18Copyright：张捷8练习3.L 1i.用列举法表示下列集合(1)A=a|aP且a2 0(2)B=a|a|v4且a为奇数2357UJ3J7J9-3,-1432.用描述法表示下列集合(l)A=0,2,4,2 00(2)B=2,4&.02 42x|xez+x1002n|neNn4内，B=d,f,a,C=e,f,g 贝lB-A=f,C-A=e,f,g=匕2012-3-18Copyright：张捷18(4).绝对补运算定义3.1.10集合A相对于全集合U期卜集称为A 的绝对补集，简称为A的补集，记作/o即A U A-u u。但A=u u A2012-3-18Copyright：张捷19例如设U=1,2,3,4,10,A=2,4,6,8,10贝！J 7=。一/=1,3,579又例如设U=I（I是整数集），/=%|%/,且10贝I 1=0/=e/且z YO修2012-3-18Copyright：张捷20(5).对称差运算定义3.1.11设有集合A、B,所有属于A而不属 于B或属于B而不属于A的元素组成的集合，称为A与B的对称差，记作/8。即/5=x(x A)v(x e B)=x(x e A B)7(x e B A)4B2012-3-18Copyright：张捷214.集合运算的定律(1).集合运算的十条定律对于全集合U的任意子集A、B、C,有:交换律 AjB=BjA AcB=BcA结合律/u(5 u C)=(/u 5)d C/c(6c C)=(Zc 6)c C分配律/c(5 u C)=(/c 5)u(/c C)/D(5 c C)=(/u 5)c(/u C)同一律 AJ0=A Ac yU=A2012-3-18Copyright：张捷互补律 AJ A=U A A=0 对合律(/)=A等暴律 Au A=A AryA=A零一律 A 1 n 万一1 n1(x+y)=Cnx+Cnx y+C xy 中，令x=y=l,便有2n=C +C1+C2+-+C-1 n n n n2 012 318因此 2)=2，即+cn n例1.设/=0,B=0,处3求2 A和2 B解 对于集合A,它只有一个子集0，即2，=0 对于集合B,有0个元素的子集：01个元素的子集：。,a,a2个元素的子集：0,“,0点,见储3个元素的子集：0,%因此2B=0j0,。,。,0,。,。,。用，,2夕 a,2012-3-18Copyright：张捷34例2.设A=0,B=2B),判断下列论断 是否正确，并将“Y”或填入相应论断后 面的括号中。(1)0 e B(Y)0rB(Y)0e8(N)(4)0,0w3(N)07B 0c B0,0口3令 C=2a=0则 B=2C=0,0(Y)(Y)(Y)(Y)2012-3-18Copyright：张捷35第三章集合与关系(Set s and Re I at i o ns)小结：本节介绍了集合的基本概念、集合的运算和运算定 律及幕集的概念。重点掌握集合的基数及幕集的概念。作业：P 86(4)a,c(6)，(9)2012-3-18Copyright：张捷36离散数学（Discrete Mathematics)张捷2012-3-18Copyright：张捷37第三章集合与关系(Set s and Re I at i o ns)3.1 集合及其运算(Se ts&O pe ratio n s with s e ts)3.2 序偶与笛卡尔积(O rde re d P airs&Carte s ian P ro duct)3.3 关系(Re latio n s)3.4 关系的性质(The P ro pe tie s o f Re latio n s)3.5 复合关系与逆关系(Co m po un d Re latio n s&I n ve rs e Re latio n s)3.6 关系的闭包运算(Clo s ure O pe ratio n s)3.7 集合的划分与覆盖(P artitio n&Co ve r o f Se ts)3.8 等价关系(Eq uivale n t Re latio n s)3.9 相容关系(Co m patib ility Re latio n s)3.10 序关系(O rde re d Re latio n s)2012-3-18 Copyright：张捷第三章集合与关系(Set s and Re I at i o ns)3.2 序偶与笛卡尔积(O rde re d P airs&Carte s ian P ro duct)3.2.1 序偶与笛卡尔积(O rde re d P airs&Carte s ian P ro duct)3.2.2 笛卡尔积的性质(The P ro pe rtie s o f Carte s ianP ro duct)2012-3-18Copyright：张捷39第三章集合与关系3.2.1 序偶与笛卡尔积(O rde re d P airs&Carte s ian P ro duct)1.有序n兀组(O rde re d n-tuple)定义3.2.1由n个具有给定次序的个体名,%，,，巴 组 成的序列称为有序n元组,记作，明。注意：有序n元组与n个元素的集合，是不相同的。例如a.b.c.d =b.a.d.c =a.b.d.c 文例如4,4,3,2二4,3,2但4,4,3,2W 4,3,22012-3-18Copyright：张捷40定义3.2.2设名,出，氏和也，也是两个 有序n元组，若%=配出=久，=勿，则称这两个有序 n元组相等，并记作当2时，有序二元组a,b又称为序偶。2.笛卡尔积定义323设A,B为任意集合，A和B的笛卡尔积用/x 5=。*表示，定义为Ax BQ G A,b G B 2012-3-18Copyright：张捷41例 1 设4=1,2,3,4,B=a,b,c,则/X B=(1,a(1,0),2,a),2,3,2,0,3,a),3,3,0),(4,a),4,3,(4,c)5X W,01,伍1伞,2,仇2,伍2,生3,03,伍3,凡4,仇4,值4)注意:Ax B B x A(2)通常我们用序偶表示两个客体之间的关系.(3)当/或者 5=0 时，/X5=0,即 0X5=/X0=0(4)笛卡尔积Ax A我们常记作/24=(%,%.)(5)如果A=,“2，Qjna z.e A,a 产 A,B=也，也AxB=B xA=AB=mn 2012-3-18Copyright：张捷例2 没 A=0,1贝 I J A2=AxA=0您1。3.2.2 笛卡尔积的性质的he P ro pe rtie s o f Carte s ian P ro duct)定理3.2.1设A、B、C是任意的集合，则有1)/x(5UC)=(/x 3)U(Zx C)2)(5UC)x/=(5x/)U(C x/)3)/x(5C C)=(/x Wx C)4)(5n c)x/=3/)n(c x%)2012-3-18Copyright：张捷43以第一个等式/X(5 U。)=(/X 5)U(/X C)为例，给出其证明。证明 设(X/)/x(5|JC)则/,且即工 /月y 3或y e C因止匕(x 4 5)或(x g A,y g C)o于是(x,)/x5 或(x/)/xC，即(X/)(/x5)U(/xC),故/x(5U C)=(/x5)U(/xC)2012-3-18Copyright：张捷44反之，设（x/）（/x5）U（/xC）,则（x,y）Zx5 或（x/）/xC,于是（X/且5）或（X，1JC）,即X /月(5或y C),即 X/且因止匕(x,y)/x(5U C),故(/x5)U(/xC)=ZxCSU。)。由上证得 Zx(5U C)=(Zx5)U(/xC)2012-3-18Copyright：张捷45定理3.2.2若C w 0,贝UA=B o（AxC）=（B xC）o（CxA）=（CxB）定理3.2.3设A、B、C、D是任意非空集合，则有AxB CxD D)例3设A、B、C、D是任意集合，判断下列等式是否成立,为什么？（/n 5）x（c n o）=（/x c）n（5x。）（2）（/U 5）X（。U。）=（/X。）U（5 X。）2012-3-18Copyright：张捷46解：(1)成立，事实上，对。(X /)A(X 5)A(C)A(D)O(X /)A(y C)A(X 5)A(y D)o(x,y)/x C)a(x,y)(/x C)口(5 x D)(2)不成立。反例如下：设A=D=。，B=C=1,贝ll(AJB)x(CJD)=BxC=(1,1)(/xC)U(g x0=U 0=0 V-2012-3-18 Copyright：弓47定义3.2.4设Ai,A2,，A。为n个(22凝合，它们的笛 卡尔积用4*/2*力表示，定义为4 x H x/=(4*h*x/_)x/,X 故4*/2*/霍有序11元组构成的集合，特别地，当n,i=1)2,4=42=4/=/时，可以写成/。例如:A=a.b,则A3=(凡凡伍凡/?也也b)5b.a.a 此处闻=2,A 根，贝L l An=(X,歹)|(x 火)A(歹 K)A(X y)x e R例4 P=,3，（2,5，e,4）J夕3夕5,。夕42012-3-18Copyright：张捷54第三章 集合与关系(Sets&Relations)定义332设夕 是由A到B的一个关系夕 的定义 域或前域记作d洞 P 的值域记作r照,分 别定义为：d om p a a/且存在 b e B,使得 a pb ra np=b b 5且存在 q e A,使得a pb 显然有 d om pA.ra np 口 B 例5没 A=2,3,5,B=2,678,9 由/到5的关系定义为：当且仅当a整除b时，有 a pb。于是夕=2,8),3,6),3,9/夕的定义域4加夕=2,3,值域ra np=2,6,8W2012-3-18Copyright：张捷553.3.2 几种特殊的关系(Se ve ral s pe cial Re latio n s)空关系对任意集合匚Ax 匚Ax A.所以。是由A到B的关系，。也是A上的关系，称为空关 系。全域关系因为 Ax A Ax A，所以是一个由/到8的关系，称为由4到5的全域关系。/x/是人上的一个关系,称为/上的全域关系。常将Ax A记作UA=a)I ai.aj e A2012-3-18 Copyright：张捷 56恒等关系定义集合/上的恒等关系/=（生。）|。/例6 设 A=a.b.c 是/上的全域关系。IA=a,a b.b c.c)是/上的恒等关2012-3-18Copyright：张捷57第三章 集合与关系(Sets&Relations)3.3.3关系的表示(The e xpre s s io n o f Re latio n s)1.集合表示法用表示集合的列举法或描述法来表示关系。例7 设 A二2,3,4,8,B二1,5,7,用描 述法定义由A至IJB的关系夕=，,试用列举法爆表示出来。2012-3-18Copyright：张捷58掇 有王、张、李、何是某校的老师，该校有三 门课程：语文、数学和英语，已知王可以教语文和 数学，张可以教语文和英语，李可以教数学，何可 以教英语，若记A=王，张，李，何,B=语文，数 学，英语。那么这些老师与课程之间的对应关系就 可以用由A到B的一个关系夕中的序偶来表示。夕=王，语文，王，数学，张，语文，张,英语，李，数学，何,英语、/C2012-3-18Copyright：张捷592.矩阵表示法定义3.3.3设A、B都是有限集，/=a.,29 9 n)5=曲也,/，由A到B的关系p可以用一个nxm的矩阵来表示，/的第i行第/列的元素5取值如 下：(1 若 QjPb jlJ jo 若 QjPb矩阵夕标为夕的关系矩阵。例7中山A到B的关系P可以 用一个4x3的矩阵来表示。/P23482012-3-18Copyright：张捷例9设/=1,2 34，A上的关系p=（%|y是x的整数倍解夕=1,11,2,1,3，1,4,2,2,2,4,3,3,（4,4）则夕可以用一个4x4的矩阵来表示。12 3 411111 2 0 10 1M 3 0 0 1 02012-3-184 0 0 0 1Copyright：张捷613.关系图表示法关系图由结点和边组成例如 例7 中的 A=2,348,B=1,5,7,P=2,5),2,7),3,5,3,7),4,5),4,7)则P的关系图如下2012-3-1862例如例9中的/=1,2 34，p=(1,1),(1,2),1,3),(1,4),(2,2),(2,4,3,3,(4,4)的关系图如下：632012-3-18 Copyright：张捷第三章 集合与关系(Sets&Relations)小结：本节介绍了关系的定义、几种特殊的 关系及关系的表示。重点掌握关系的表示方 法。作业：P109(2),(6),(7)2012-3-18Copyright：张捷64离散数学（Discrete Mathematics)张捷2012-3-18Copyright：张捷65第三章集合与关系(Set s and Re I at i o ns)3.1 集合及其运算(Se ts&O pe ratio n s with s e ts)3.2 序偶与笛卡尔积(O rde re d P airs&Carte s ian P ro duct)3.3 关系(Re latio n s)3.4 关系的性质(The P ro pe tie s o f Re latio n s)3.5 复合关系与逆关系(Co m po un d Re latio n s&I n ve rs e Re latio n s)3.6 关系的闭包运算(Clo s ure O pe ratio n s)3.7 集合的划分与覆盖(P artitio n&Co ve r o f Se ts)3.8 等价关系(Eq uivale n t Re latio n s)3.9 相容关系(Co m patib ility Re latio n s)3.10 序关系(O rde re d Re latio n s)2012-3-18 Copyright：张捷第三章 集合与关系(Sets&Relations)3.4关系的性质(The pr o per t ies o f Relat io ns)3.4.1集合A上关系的性质(The pr o per t ies o fRelat io ns o n set A)3.4.2由关系图、关系矩阵判别关系的性质2012-3-18Copyright：张捷67第三章 集合与关系(Sets&Relations)3.4.1集合A上关系的性质定义341设夕是集合A上的关系(1)若对于所有的，均有，则称夕在A 上是自反的(re fle xive)o(2)若对于所有的,均有。加2,则称夕在A 上是反 自反的(an tire fle xive)。(3)对于所有的a.b A若每当有a夕b就必有b pq 则称 夕在力上是对称的(s ym m e tric)。(4)对于所有的Q,b e A，若每当有和6夕Q就必有q=b，则称夕在4上是反对称的(an tis ym m e tric)(5)对于所有的a.b.c e 4若每当有a pb和就必有夕。,则称夕在A上是可传递的(tran s iti的疗 2012-3-18 Copyright：张捷 68例 1 设/=0,1,2,3),(1)自反与反自反P2=0,0),2,1,1),2,2),2,3),3,3夕4=自反自反非自反2012-3-18Copyright：张捷69(2)对称与反对称夕5=1。&223,3,2)对称,非反对称4=1。,。,2 M3,1),0,2 非对称,反对称 夕7=2,3),1,2),3,2 2,2非对称，非反对称4=对称,反对称2012-3-18Copyright：张捷70(3)可传递与不可传递P9=(0,0),(0,2),2,3),(0,3可传递夕 10=QN2,320不可传递夕11=3,0),2吊3,2)可传递 配张捷既对称又反对称例2 设A=1,2,3,4,5，A上的关系p=|a-b 是偶数贝 Ip=(1,1),(1,3),。,5),2,2),2,4),3,3,3,1,3,5,夕自反 p对称 p不是反对称对于任意的 a.b.c e A,a-b=2m.b-c=I n,则 a-c=(a-b)+(b-c)=2(m+n)也是偶数。因此夕是可传递的。2012-3-18Copyright：张捷72例3 设夕 1=(d6)|a.b g&且q b 则21是自反的、反对称的、可传递的。夕2-(|a.b g&且a=b 则22自反的、对称的、反对称的、可传递的。a.b&N,且a b 则夕3自反的、反对称的、可传递的。2012-3-18Copyright：张捷73例3（续）夕4=I Q,b是人，且q是b的朋友则24是自反的、对称的、可传递的。p5=（凡b）|是人，且a是6的祖先则夕5反自反的、反对称的、可传递的。p6=（|a,6是人，且q是b的父亲则夕6反自反的、反对称的。例4。是不自反、反自反的、对称的、反对称、可传递的。冽5全关系是自反的、对称的、可传递的。、公2012-3-18 Copyright：张捷 743.4.2由关系图、关系矩阵判别关系的性质1.关系矩阵若夕是自反的，则关系矩阵的主对角线上的所有元素 均1。若夕是反自反的，则关系矩阵的主对角线上所有元素 均为0。若p是对称的，则关系矩阵关于主对角线对称。若夕是反对称的，则关系矩阵中，关于主对角线对称的元素不同时为1。12 3 41F 1 1 1 1例如,2012-3-182 0 10 1M=p 3 0 0 1 04(opyriQt：张Q2.关系图若夕是自反的，则关系图中每一结点引出一个指向自身的单边环（自环）。若夕是反自反的，则关系图中每一结点均没有自环。若夕是对称的，则在关系图中，若两结点之间有边，则必 存在两条方向相反的边。若夕是反对称的，则在关系图中，任意两个不同的结点间 至多只有一条边。若夕是可传递的，则在关系图中，若每当有边由河於 向处，且又有边由处指向Q.,则必有一条边由指丽.k k j i Nf y 2012-3-18 Copyright：张捷 76例6 设/=1,2,3，下面分别给出集合A上三个关系的关系图，试判断?扁勺性质。解(1)是自反的，非对称，不是反对称，不可传递(1,2)e 夕i/2,3)e/但(1,3).pv(2)非自反，也不是发自反，非对称，反对称，可传递。(3)是自反的，对称的，可传递的，不是反q后也不是反对称。32012-3-18Copyright：张捷77第三章 集合与关系(Sets&Relations)小结：本节介绍了关系的基本性质及其判别 方法。作业：P113(1),(4)2012-3-18Copyright：张捷78离散数学（Discrete Mathematics)张捷2012-3-18Copyright：张捷79第三章集合与关系(Set s and Re I at i o ns)3.1 集合及其运算(Se ts&O pe ratio n s with s e ts)3.2 序偶与笛卡尔积(O rde re d P airs&Carte s ian P ro duct)3.3 关系(Re latio n s)3.4 关系的性质(The P ro pe tie s o f Re latio n s)3.5 复合关系与逆关系(Co m po un d Re latio n s&I n ve rs e Re latio n s)3.6 关系的闭包运算(Clo s ure O pe ratio n s)3.7 集合的划分与覆盖(P artitio n&Co ve r o f Se ts)3.8 等价关系(Eq uivale n t Re latio n s)3.9 相容关系(Co m patib ility Re latio n s)3.10 序关系(O rde re d Re latio n s)2012-3-18 Copyright：张捷第三章 集合与关系(Sets&Relations)3.5复合关系与逆关系(C o mpo und Relat io ns&Inver se Relat io ns)3.5.1关系的并、交、补及对称差运算3.5.2 逆关系(Inver se Relat io ns)3.5.3 复合关系(C o mpo und Relat io ns)2012-3-18Copyright：张捷81第三章 集合与关系(Sets&Relations)3.5.1关系的并、交、补及对称差运算定理351若R与S都是集含A到集合B的关系,则RUS,RDS,R-S,瓦一s均为A到 B的关系。例1 没 P=。，2),(2,4,(3,3),夕?=(1,3),(2,4),(4,2)则 P 2 P2=(1,2),(2,4,(3,3),(1,3),(4,2).夕夕2=2,4).0=。，2),3,3).、2_ AP2=,XU,.Wo Z3.5.2 复合关系（C o mpo und Relat io ns）1.复合关系的定义定义351设01是由A到B的关系，夕2是由B到C的 关系，则夕1和夕2的复合关系是一个由A到C的关系，用夕1。夕2表示，定义为：当且仅当存在元素6ga 使得 a p b，b p2c 时，有。夕2）。这种由0和夕2求复合关系夕1。夕2的运算称为关系 的复合运算。由定义可知：夕1。夕2=（生 e 4）a（c e C）a 9（修 B）2012-3-18A（。夕四公岫8c）83例2 设 Pi是由/=1,2,34到 5=2,3,4的关 系。夕2是由B到。=3,5,6的关系。分别定义为：P=（。，少|a+Z?=6=2,4）,3,3）,4,2）夕2=伍 c）I b整除 c =2,6）,3,3（3,6）2012-3-18 Copyright：张捷 84例3设/=5=。是所有人的集合Pi=（。|a.b e 4a是b的兄弟夕2=w/是c的父亲于是复合关系夕1。夕2=生。a.c e 4是。的叔伯2012-3-18Copyright：张捷852.关系复合运算的性质定理3.2设夕是由集合A到B的关系，则!AQ P=PoIB=P例4 以例2中的关系夕1为例，0=2,4,3,3，4,2从关系图，可得1A Pi=%,Pi.*=P2012-3-18 Copyright：张捷86定理35 3设2是由A到B的关系，/是由B到C的关系,则有(1)d om(夕1。夕2)=d om px(2)ra n(p1 p2)ra np?(3)若 p、n d om p2=心贝q。夕？=0 证：反设i。夕2。*则必存在x C使、夕1 p2z，从而3y e B.xpxy.yp2z,故 y e randomp29所以y/即夕1 C49加夕2，这就与 ra n px n d om p”(j)矛盾。2012-3-18Copyright：张捷87定理 3.5.4（1）设0是由A到B的关系，夕2是由B到C的关系，0是由C到D的关系，则有（夕1。夕2）。夕3=夕1。（夕2。夕3）设n是由A到B的关系,夕2,。3是由B到C的关系,则有 夕1。（2。夕3）=（夕1。夕2）。（夕1。夕3）设八22是由A到B的关系，03是由B到C的关系,则有（A D 夕2）。夕3=（夕1。夕3）D（夕2 P2012-3-18Copyright：张捷88例5 没 A=1,2,3,4,B=2,3,4,C=1,2,3,D=4,5,6）.A到B 的关系夕i=2,4,2,3,4,2B到C的关系夕2=2 1,3,2,4,3C到D的关系夕3=2,4,1,5,2,6,3,6则 A到C 的关系 夕J 2=2,3,2,2,4,1因此 M。夕2）。0=2,6,2,4,4,5夕2。=2,5,3,4,3,6,4,6因此 1。（夕2 夕3）=2,6,2,4,4,5 Y2。瓯以 3。夕2）。%嬴/乳夕2 0夕3）一般地，若0是一由4到4的关系，夕2是由 X 乙 乙到a的关系，2是一由4到4+1的关系，则不加括号的表达式PX。夕2。Pn，唯一地表示一由4到A 的关系，在计算这一关系时，可以运用结合 n+1律将其中任意两个相邻的关系先结合。特别，当4=/=.=/=p2=,=pn书h1 2 n+1复合关系 Q。）。简记作，花也是集A上的一个关系。2012-3-18Copyright：张捷903.求复合关系的几种方法(1)根据复合关系的定义求复合关系例5中求复合关系采用的就是这种方法。又例如 下面的关系图给出了从集合A到B的关系0 和从B到C的关系p22012-3-18Copyright：张捷91(2)运用关系矩阵的运算求复合关系布尔运算其加法和乘法运算定义如下0+0=0,0+1=1+0=1+1=111=1,0.1=1.0=00=0例如(1-0-0)+(0-1)+(1-1-1)+(0-0-0)+(1-1)=12012-3-18Copyright：张捷92关系矩阵的乘积对两个关系矩阵求其乘积时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。例6设和/是两个关系矩阵则100100100100M1-M2101010001110o o0 11 o2012-3-18Copy|ight：0捷.93复合关系的关系矩阵定理3.5.5设A、B、C均是有限集，乃是一由A 到B的关系，是一由B到C的关系，它们的关系 矩阵分别为吃和Mp,则复合关系夕1。夕2的 P 2 1关系矩阵M夕1。夕2=M/夕1 夕22012-3-18Copyright：张捷94例7 设有集合力=1,2 34,5=2,3,4,。=1,2,3 A到B的关系 q=1,2,2,4,3,3,4,2B到C的关系夕2=2 J,3,2,4J,4,3则 p、。p?=1 J,2,1,2,3,3,2,4 J2 3 4iFi o o2 0 0 1M=0 3 0 10M=3010P 24 10 1 pp212 32 P1 0 012 311 0 02 10 13 0 104 10 04 1与例6比较得2012-3-18M=Mp q Pi pCopyright：张捷-MPi95例8设A=a,b.c.d A上的关系试求22和夕3。解作出的关系矩阵abed0 1 0 0根据定理3.5.5ro5 10 10M=P C 0 0 1 1d10 0 0 0o o i o o r i100 1 0因此 p2=a,a，a,c，b/，b,c，b,Q，g c2012-3-18Copyright：张捷963 2又夕=夕。夕，所以M 3=MP P2P010010000110001010000100111001100100100011101110因此P3=生力,生生2012-3-18Copyright：张捷97（3）利用关系图求复合关系设夕是有限集A上的关系，则复合关系22也是a上的关系，由复合关系的定义，对于任意的,当且仅 I J当 /存在，使得知夕町时,有aip2aj 0 反映在关系图上，这意味着，当且仅当在夕的关第图中有某一结点ak存在，使得有边由为指向ak,且有边 由a左指向a.时，在夕之的关系图中有边从q指向.。K J 1 J2012-3-18Copyright：张捷98类似地，对于任意正整数n,当且仅当在p的关系图中存在口-1个结点ak.ak，外，使得有边勺 K2 Kn-1由指向a”，由指向a”，由。上指向i 勺 勺 2 Kn-1 J时，在夕的关系图中，有边由结点a.指向町。7 I Jn根据P的关系图构造出P的关系图：对于夕的关系图中的每一结点火,找出从巴经 过长为n的路能够到达的结点，这些结点在，的 关系图中，边必须由4.指向它们。、/2012-3-18Copyright：张捷99例 10试利用构造片和储 的关系图的方法求例9中的 24口 p解例中 P=d-2(2)构造夕的关系图。在P的关70、系图中寻、/找长为2的路。厂G*(1)先产飞 作出夕 的关系 图(3)构造夕3的关系图。;：-A，了在P的关A IX 1系图中寻11 X 找长为3的一路.I-(4)根据夕2和储的 关系图直接写出夕2和储中的序偶.例 1 L下图给出了集合/=1,2,345,6上的关 系夕的关系图，试画出关系储和炉的关系图。3.5.3 逆关系(Inver se Relat io ns)定义352设A、B是任意集合，夕是由A到B的关系，定义由B到A的关系称夕t为关系夕的逆关系。例 12设/=2,3,5，刀=4,6,10,定义由A到B的关时，有，试求P的逆关由p的定义知夕=2,4),2,6),2,10,3,6,5,10于是 夕t=4,2),6,2),10,2“6,3,10,2012-3-18Copyright：张捷102关于逆关系我们有如下定理:定理356设A、B是任意集合，P、P和夕2都是 由A到B的关系，则有(2)(3)(4)(5)(6)（丁尸二夕 x （Pl D夕2尸二夕D夕2 （Q1 C2）-1 二夕1 1 C/72(A x B)=B x A(万)二(夕 i),p=AxB-p103(Copyright：张捷2012-3-18关于逆关系我们有如下定理：定理3.5.7设A、B、C是任意集合，/1、夕2分别是 由A到B的关系和由B到C的关系，则有(71。夕2广二夕2 1 A 1定理358设P是集合A上的二元关系,则(1)P对称当且仅当(夕厂1=夕(2)P反对称当且仅当p c pT c IA证：2012-3-18Copyright：张捷104第三章 集合与关系(Sets&Relations)小结：本节主要介绍了关系的复合运算与逆 运算。重点掌握关系的复合运算及其性质、关系的逆运算的性质。作业：P118-119(1),(5),(6)2012-3-18Copyright：张捷105离散数学（Discrete Mathematics)张捷2012-3-18Copyright：张捷106第三章集合与关系(Set s and Re I at i o ns)3.1 集合及其运算(Se ts&O pe ratio n s with s e ts)3.2 序偶与笛卡尔积(O rde re d P airs&Carte s ian P ro duct)3.3 关系(Re latio n s)3.4 关系的性质(The P ro pe tie s o f Re latio n s)3.5 复合关系与逆关系(Co m po un d Re latio n s&I n ve rs e Re latio n s)3.6 关系的闭包运算(Clo s ure O pe ratio n s)3.7 集合的划分与覆盖(P artitio n&Co ve r o f Se ts)3.8 等价关系(Eq uivale n t Re latio n s)3.9 相容关系(Co m patib ility Re latio n s)3.10 序关系(O rde re d Re latio n s)2012-3-18 Copyright：张捷107第三章 集合与关系(Sets&Relations)3.6 关系的闭包运算(C lo sur e Oper at io ns)3.