《离散数学》课件第五章

1、集合论第5章 关系 Relation主要内容1 有序对、笛卡尔积(卡氏积)2 二元关系3 关系的表示4 关系性质5 关系运算6 等价关系7 序关系1 有序对与笛卡尔积 定义5.1 由n个具有给定次序的个体a1,a2,an组成的序列，叫做有序n元组，记作(a1,a2,an)。其中ai（i=1,2,n）叫做该有序n元组的第i个坐标。另外，有序n元组的一种常见的特殊情形是n=2。有序二元组（a,b）又被称为序偶。 (a,b)=(c,d) a=cb=dab (a,b)(b,a) 有序n元组: (a1,a2,an)=(a1,a2,an-1),an) 定义5.2 有序n元组相等: (a1,a2,an)=(

2、b1,b2,bn) 定义5.3 设A1,A2,An是任意集合，则称集合 (a1,a2,an)|aiAi,i=1,2,n 为集合A1,A2,An的笛卡尔积，记为A1A2An。 当所有的Ai都相同且等于A时，则A1A2An可记为An。1 有序对与笛卡尔积示例A=,a, B=1,2,3.AB=,.BA=,.AA= , , , .BB= , .1 有序对与笛卡尔积笛卡尔积一些性质AB= A= B=非交换AB BA (除非 A=B A= B=)非结合(AB)C A(BC) (除非 A= B= C=)分配律A(BC) = (AB)(AC) 定理5.1 设A,B为任意两个有限集，则 |AB|=|A|B| 推

3、论5.1 设A1,A2,An为任意n个有限集，则 |A1A2An|=|A1|A2| |An|定理5.2 设A,B,C,D为任意四个非空集合，则(1)ABCD当且仅当AC,BD；(2)AB=CD当且仅当A=C,B=D。1 有序对与笛卡尔积1 有序对与笛卡尔积试证明集合分配律：A(BC) = (AB)(AC).1. A(BC) = (AB)(AC)2. A(BC) = (AB)(AC)3. (BC)A = (BA)(CA)4. (BC)A = (BA)(CA)5. A(B-C)=(AB)-(AC)6. (A-B)C=(AC)-(BC) 证明: , A(BC) xAy(BC) xA(yByC) (x

4、AyB)(xAyC)(AB)(AC)x(AB)(AC)所以，A(BC) = (AB)(AC).1 有序对与笛卡尔积例5.3 设A,B,C和D是任意的集合，试问下列等式是否成立？为什么？ (1)(AB)(CD)=(AC)(BD) 解 成立。因为对于任意的（x,y），设 (x,y)(AB)(CD)xAByCDxAxByCyD(x,y)AC(x,y)BD(x,y)(AC)(BD)(2)(AB)(CD)=(AC)(BD) 解 不成立。举一反例如下：设A=D=，B=C=1，则(AB)(CD)=BC=(1,1)，(AC)(BD)=，显然等式不成立。 1 有序对与笛卡尔积2 二元关系设nI+，A1,A2,A

5、n为任意n个集合，A1A2An，则 (1)称为A1,A2,An间的n元关系； (2)若n=2，则称为从A1到A2的二元关系（集合A到A也可以生成二元关系，并且最常用）； (3)若=，则称为空关系； (4)若=A1A2An，则称为普遍关系； (5)若A1=A2=An=A，则称为A上的n元关系； (6)若=(x,x)|xA，则称为A上的恒等关系。 若是由A到B的一个关系，且(a,b)，则a对b有关系，记为ab。中缀(infix)、前缀(prefix)、后缀(suffix)记号2 二元关系对集合A上的二元关系R, 可以定义:定义域(domain) : dom R = x | y(yA xRy) 值域

6、(range): ran R = y | x(xA xRy) 域(field): fld R = dom R ran R2 二元关系示例,是2元关系，,是2元关系，A=,a,1不是关系设A=1,2,4,7,8，B=2,3,5,7，定义由A到B的关系=(a,b)| 5|(a+b)，|表示整除，求关系。设A=2,3,4,5,9,25，定义A上的关系，对于任意的a,bA，当且仅当(a-b) A时，有ab，试问由哪些序偶组成？设A=0,1,2，求A上的普遍关系UA和A上的恒等关系IA。A到B不同的二元关系共有多少个？A上不同的二元关系共有多少个？2 二元关系示例6 设AR, 则可以定义A上的:小于等于

7、(less than or equal to)关系:LEA = | xA yA xy 小于(less than)关系,LA = | xA yA xy 大于等于(greater than or equal to)关系大于(great than)关系7 设A为任意集合, 则可以定义P(A)上的:包含关系: A = | xA yA xy 真包含关系: A = | xA yA xy 2 二元关系示例8 自然数上的二元关系D=(m,n)N2 | m|n自然数上的同余关系Rk=(m,n)N2 | (2,|m-n|)Dmn (mod k)3 关系的表示集合论方法（序对之集合）代数表示（矩阵表示法）几何表示（

8、图）关系R的集合表达式,关系矩阵,关系图三者均可以唯一互相确定3 关系的表示关系矩阵(Matrix)设 A=a1,a2,am, B=b1,b2,bn, RAB, 则R的关系矩阵M(R) (或者记为MR ) =(rij)mn, 其中，如, A=2,3,4,5，B=6,7,8,9，由A到B的关系=(2,7),(2,9),(3,7),(3,8),(4,7),(4,9),(5,6),(5,7),(5,8),(5,9)，所以关系矩阵 3 关系的表示关系图(Graph)集合A到B的关系R的关系图G(R)或GR：由结点(表示集合元素)与有向边(表示结点代表的元素之间具有关系R)构成的图。结点数为|A|+|B

9、|，有向边数为|R|如，A=a,b,c, =,abc例如 例1中的 ， ,则的关系图如下AB4 关系的性质自反性(Reflexivity)反自反性(Anti-reflexivity) 对称性(Symmetry)反对称性(Anti-symmetry)传递性(Transitivity)4关系性质自反性(reflexivity)设RAA, 如果 x( xA xRx) ,说R是自反的(Reflexive) . R是非自反的 x( xA xRx)性质：R是自反的 IAR R-1是自反的 M( R )主对角线上的元素全为1 G( R )的每个顶点处均有环. 反自反性设RAA, 说R是反自反的(irrefl

10、exive), 如果x(xA xRx).R是非反自反的 x( xA xRx)性质: R是反自反的 IAR= R-1是反自反的 M( R )主对角线上的元素全为0 G( R )的每个顶点处均无环. 自反,自反性自反反自反非自反, 非反自反自反, 反自反 ?上的空关系对称性设RAA, 说R是对称的(Symmetric),如果xy(xAyAxRyyRx).R非对称 xy(xAyAxRyyRx)性质: R是对称的 R-1=R R-1是对称的 M( R )是对称的 G( R )的任何两个顶点之间若有边, 则必有两条方向相反的有向边. 反对称性设RAA, 说R是反对称的(Anti-symmetric),若

11、xy(xAyAxRyyRxx=y).R非反对称xy(xAyAxRyyRxxy)性质: R是反对称的 R-1 RIA R-1是反对称的 在M( R )中, ij(ijrij=1rji=0) 在G( R )中, xixj(ij), 若有有向边, 则必没有. 对称,反对称对称反对称非对称, 非反对称对称, 反对称 ?传递性设RAA, 说R是传递的(Transitive), 如果xyz(xAyAzAxRyyRzxRz).R非传递xyz(xAyAzAxRyyRzxRz)性质: R是传递的 RoRR R-1是传递的 在M(RoR)中, ij, 若rij=1,则M( R )中相应元素 rij=1. 在G(

12、R )中, xixjxk, 若有有向边, 则必有有向边. 传递性示例在 N = 0,1,2, 上:=|xNyNxy自反,反对称,传递=|xNyNxy自反,反对称,传递=|xNyNx=|xNyNxy反自反,反对称,传递示例A=a,b,cR1=,R2=,R3=,R4=,R5=,R6=,示例设R1,R2AA都具有某种性质自反反自反对称反对称传递R1-1, R2-1R1R2R1R2R1oR2 , R2oR1R1-R2 , R2-R1R1, R2示例设R1,R2AA都具有某种性质自反反自反对称反对称传递R1-1, R2-1R1R2R1R2R1oR2 , R2oR1R1-R2 , R2-R1R1, R2示

13、例(2) R1,R2反自反 R1R2反自反.证明: (反证) 若R1oR2非反自反, 则 xA, x(R1R2)x xR1x xR2x 与R1,R2反自反矛盾! R1,R2反自反 R1R2反自反. 示例(4) R1反对称 R1-1反对称.证明: (反证) 若R1-1非反对称, 则 x,yA, xR1-1y yR1-1x xy yR1x xR1y xy 与R1反对称矛盾! R1反对称 R1-1反对称. 示例(3) R1,R2对称 R1-R2对称.证明:x,yA, x(R1-R2)y xR1y xR2y yR1x yR2x y(R1-R2)x R1,R2对称 R1-R2对称. 示例(3) R1对称

14、 R1对称.证明: x,yA, x(R1)y x(UA-R1)y xUAy xR1y yUAx yR1x y(UA-R1)x y(R1)x R1对称 R1对称. 5 关系的运算对任意关系R,G, 有:逆(Inverse Operation) : R-1 = | yRx 复合(合成)(Composite Operation)RoG = | y( xRy yGz ) RGxyz5 关系的运算例5.11 设集合A=1,2,3,4，B=2,3,4,5，C=0,1,2，1是从A到B的关系，2是从B到C的关系，分别定义为： 1=(a,b)|a+b=6，2=(b,c)|b-c=2， 试求复合关系1 2和2

15、1。 解 由题意知 1=(1,5),(2,4),(3,3),(4,2) 2=(2,0),(3,1),(4,2) 根据复合关系的定义 1 2=(2,2),(3,1),(4,0) 2 1=(3,5),(4,4) 练习 设1和2是集合A上的两个关系，判断下列命题是否正确。 (1)若1和2是自反的，则1 2也是自反的； (2)若1和2是反自反的，则1 2也是反自反的； (3)若1和2是对称的，则1 2也是对称的； (4)若1和2是反对称的，则1 2也是反对称的； (5)若1和2是传递的，则1 2也是传递的。5 关系的运算 定理5.4 设A,B,C,D为任意四个集合，1是从A到B的关系，2 和3是从B到

16、C的关系，4是从C到D的关系，于是有： (1)若2 3 ，则1 2 1 3 ，2 4 3 4； (2) 1 (23) = (1 2)(1 3) (3) (23) 4 = (2 4)(3 4) (4) 1 (23) (1 2)(1 3) (5) (23) 4 (2 4)(3 4) (6) (1 2) 4 = 1 (2 4)5 关系的运算(2) R1o(R2R3) = (R1oR2)(R1oR3)证明: , R1o(R2R3)z(xR1zz(R2R3)y)z(xR1z(zR2yzR3y)z(xR1zzR2y)(xR1zzR3y)z(xR1zzR2y)z(xR1zzR3y)x(R1oR2)yx(R1

17、oR3)yx(R1oR2)(R1oR3)y(R1oR2)(R1oR3)dbca5 关系的运算(4) R1o(R2R3) (R1oR2)(R1oR3)证明: , R1o(R2R3)z(xR1zz(R2R3) y)z(xR1z(zR2yzR3y)z(xR1z zR2y)(xR1z zR3y)z(xR1z zR2y)z(xR1z zR3y)x(R1oR2)yx(R1oR3)yx(R1oR2)(R1oR3)y(R1oR2)(R1oR3).5 关系的运算定义5.10 设1,2,n分别是A1到A2,A2到 A3,An到An+1的关系，则称关系 (x1,xn+1)|x1A,xn+1An+1,存在x2A2,x

18、nAn,使(x1,x2)1,(xn,xn+1)n 为1,2,n的复合，记为1 2 n 当A1=A2=An+1=A，1=2=n=时，则复合关系12 n= 称为的n次幂，记为。定义5.11 设A为任意集合，为A上的任意二元关系，则有： （1）0是A上的恒等关系，即0 = IA； （2）n+1 = n，nN。 定理5.5 设m,nN，为集合A上的二元关系，则 （1）m n = m+n （2）(n)m = mn5 关系的运算 设A=a,b,c R1=,R2=, 试根据关系矩阵求解R1-1 ,R2-1, R1oR1a b ca b ca b ca b ca b ca b ca b ca b c对于集合A

19、上的二元关系，其复合关系n，仍是A上的二元关系。我们可以用如下的方法由的关系图作出n的关系图。 由的关系图构成n的关系图的步骤如下： （1）对的关系图（假设有m个结点）中每个结点ai(i=1,2,m)，找出从ai经由长为n的路能够到达的结点aj； （2）连接aiaj得n的一条边； （3）前两步得到的所有边组成n的关系图。 定理5.8 设和i(i=1,2,)都是从集合A到集合B的二元关系，则有： （1）(-1)-1=； （2）若12，则1-12-1； （3）若1=2，则1-1=2-1 定理5.9 设是集合A上的二元关系，则有： （1）是自反的，当且仅当-1是自反的； （2）是反自反的，当且仅当-

20、1是反自反的； （3）是对称的，当且仅当-1是对称的； （4）是反对称的，当且仅当-1是反对称的； （5）是传递的，当且仅当-1是传递的。 定理5.10 设A,B,C是三个集合，1是从A到B的关系，2是从B到C的关系，则有： (1 2)-1 = 2-1 1-1 推论5.4 设nN，是集合A上的二元关系，则(n)-1 =(-1)n 。6 关系闭包闭包(closure): 包含一些给定对象, 具有指定性质的最小集合“最小”: 任何包含同样对象, 具有同样性质的集合, 都包含这个闭包集合示例 (平面上点的凸包)6 关系闭包自反闭包: 包含给定关系R的最小自反关系, 称为R的自反闭包, 记作r( R

21、). (1) R r( R ); (2) r( R )是自反的; (3) S( (RS S自反) r( R ) S ).对称闭包 s(R)传递闭包 t(R)6 关系闭包定理5.11 设RAA且A,则 (1) R自反 r( R ) = R; (2) R对称 s( R ) = R; (3) R传递 t( R ) = R. (1) RR R自反 r( R )R且 R r( R ), 所以，r( R ) = R.6 关系闭包如何求闭包？ (1) r( R ) = R ？ (2) s( R ) = R ？ (3) t( R ) = R ?6 关系闭包设 RAA 且 A, 则 (1) r( R ) = R

22、IA; (2) s( R ) = RR-1; (3) t( R ) = RR2R3. (记为R+ , R的自反传递闭包记为R*)证明: (1);R RIA RIA自反 r( R )RIA;Rr( R ) r( R )自反 Rr( R ) IA r( R ) RIA r( R ) r( R ) = RIA6 关系闭包(3) t( R ) = RR2R31) R RR2R3; 2) (RR2R3)2 = R2R3 RR2R3 RR2R3传递 t( R )RR2R3;3) Rt( R ) t( R )传递 Rt( R )R2t( R )R3t( R ) RR2R3 t( R ) t( R ) = R

23、R2R3.R传递 R2RR G G传递 RnG 例5.15 设A=a,b,c,A上的二元关系=(a,b),(b,c),(c,a)，求r(),s(),t()。 解 r()=IA=(a,b),(b,c),(c,a)(a,a),(b,b),(c,c) =(a,a),(a,b),(b,b),(b,c),(c,a),(c,c) s()=-1=(a,b),(b,c),(c,a)(b,a),(c,b),(a,c) =(a,b),(a,c),(b,a),(b,c),(c,a),(c,b) t()=23 =(a,b),(b,c),(c,a)(a,c),(b,a),(c,b)(a,a), (b,b),(c,c)

24、=(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c) 7 等价关系等价关系(Equivalence)设 RAA 且 A, 若R是自反的, 对称的, 传递的示例: 判断是否等价关系(A是某班学生): R1=|x,yAx与y同年生R2=|x,yAx与y同姓R3=|x,yAx比y高是A上等价关系吗?7 等价关系示例1）在一群人的集合上年龄相等的关系是等价关系，而朋友关系不一定是等价关系，因为它可能不是传递的。2）命题公式间的逻辑等值关系是等价关系。3）集合上的恒等关系和普遍关系都是等价关系。4）在同一平面上直线之间的平行关系，三角形之间的相似关

25、系都是等价关系。判定一个关系是不是恒等关系就看其是否具有三个性质。例5.17 设1是集合A上的一个二元关系，2=(a,b)存在c，使(a,c)1且(c,b)1，证明若1是一个等价关系，则2也是一个等价关系。 证明 设1是A上的等价关系， （1）对任意一个xA，因为1在A上自反，所以(x,x)1。由2的定义，(x,x)2，所以2是自反的。 2）对任意x,yA，若(x,y)2，则存在某个cA，使得(x,c)1且(c,y)1，因为1是对称，故有(y,c)1且(c,x)1，由2的定义，可知(y,x)2，所以2是对称的。 （3）对任意x,y,zA，若(x,y)2，(y,z)2，则必存在某个c1A，使(x

26、,c1)1，(c1,y)1。由1的传递性，可知(x,y)1，同理存在c2A，使(y,c2)1且(c2,z)1，由1传递，可知(y,z)1。再由2的定义，得(x,z)2。所以2是传递的。 由以上（1）（2）（3）可知2是一个等价关系。 例5.18 设1和2都是集合A上的等价关系，（1）试证明：12也是A上的等价关系； 证明 由交集的定义12=(a,b)|(a,b)1且(a,b)2。 对任意一个aA，因为1和2都是自反的，所以有(a,a)1且(a,a)2，因而有(a,a)12，故12是自反的。对任意a,bA，若(a,b)12，则有(a,b)1且(a,b)2，由1和2的对称性有(b,a)1且(b,a

27、)2，因而有(b,a)12，故12是对称的。 对任意a,b,cA，若(a,b)12，(b,c)12，则有(a,b)1，(b,c)1；(a,b)2，(b,c)2。由1和2的传递性有(a,c)1，(a,c)2，因而有(a,c)12，故12是传递的。 由以上三方面知12是A上的等价关系。 （2）12是A上的等价关系吗？为什么？举反例如下：设A=1,2,3，A上的关系1=(1,1),(2,2),(3,3),(1,3),(3,1)；2=(1,1),(2,2),(3,3),(2,3),(3,2)。 显然1和2均是等价关系。12=(1,1),(2,2),(3,3),(1,3),(3,1),(2,3),(3,

28、2)。 这里12是自反，对称的，但因为(2,3)12且(3,1)12，而(2,1)12，所以12不是传递的。 7 等价关系划分划分(Partition): 设, P(A),若满足 1) ; 2) 中元素的并集 = A 3) x,y( x,y xy xy= )则称为A的一个划分,中元素称为划分块(Block).如仅仅满足条件1)、2)，称为A的覆盖(Covering).7 等价关系划分示例 设A=0,1,2,3,4， 1=0,1,1,2,2,3,4， 2=0,1,2,3,4， 则1是A的一个覆盖但不是分划，2既是A的一个覆盖，也是A的一个分划。 如何得到集合A的划分？示例：设A是由4个元素组成的

29、集合，试问在A上可以有多少个不同的划分？将集合A分划为一块：有1种分法；将集合A分划为两块：有C(4,2)/2+C(4,1)种分法；将集合A分划为三块：有C(4,2)种分法；将集合A分划为四块：有1种分法；因此，集合A上不同等价关系的个数为 1+C(4,2)/2+C(4,1)+C(4,2)+1=15。定义5.16 设1=A1,A2,An，2=B1,B2,Bn都是集合A的分划，如果对每个Ai均有一个Bj使AiBj，则称分划1是分划2的细分或加细。 例5.20 设A=a,b,c，1=1,2,3，2=1,2,3，3=1,2,3，则1，2和3都是集合A的分划，且1是2和3的细分，2是3的细分。 7 等

30、价关系等价类等价类设R是A上等价关系,xA,令 xR= y | yA xRy ,称xR为x关于R的等价类, 简称x的等价类,可简记为x.示例 设A=a,b,c,d,e，A上的关系=(a,a),(a,b),(b,a),(b,b),(c,c),(d,d),(d,e),(e,d),(e,e)，确定由集合A中的元素产生的等价类。7 等价关系等价类注意到，由等价关系确定的等价类具有如下性质：xR ;xRy xR=yR ;xRy xRyR= ;U xR | xA =A.A=U x | xA U xR | xA U A | xA =A. U xR | xA = A.7 等价关系商集商集: 设R是A上等价关系

31、, A/R = xR | xA 称为A关于R的商集, 简称A的商集.商集的基数称为等价关系的秩。显然 U A/R = A.如例5.21中的商集为A/=a,b,c,d,e =a,b,c,d,e。 定理5.15 设是集合A上的等价关系，则A关于的商集A/是A的一个分划，称为A关于的等价分划。 定理5.16 集合A的一个分划确定A上的一个等价关系。 例5.22 设A=a,b,c,d,e有一个分划=a,b,c,d,e，求所确定的等价关系。 解 设 1=a,ba,b=(a,a),(a,b),(b,a),(b,b)， 2=cc=(c,c), 3=d,ed,e=(d,d),(d,e),(e,d),(e,e)

32、。 所以=123=(a,a),(a,b),(b,a),(b,b),(c,c), (d,d),(d,e),(e,d),(e,e)。 7 等价关系划分与等价关系示例 A=a,b,c, 求A上全体等价关系解: A上不同划分共有5种:R1= UA, R2=IA, R3=IA, R4=IA, R5=IA.abcabcabcabcabc7 等价关系商集示例 设A=a1,a2,an, IA, UA,Rij=IA,都是A上等价关系, 求对应的商集, 其中ai,ajA, ij. 解: A/IA= a1, a2, an A/UA= a1,a2,an A/Rij= A/IAai,aj - ai,aj.7 等价关系划

33、分与等价关系设A, 则(1) R是A上等价关系 商集A/R是A的划分(2) 是A的划分 R是A上等价关系,其中x R y z(zxzyz) R称为由划分 所定义的等价关系(同块关系).练习：教材p100.28题8 偏序关系偏序关系(Partial Order):设 RAA 且 A, 若R是自反的, 反对称的, 传递的通常用表示偏序关系,读作“小于等于”; “严格小于”: xy xy xy偏序集(Poset, Partial-Order Set): , 是A上偏序关系例: , , 8 偏序关系练习 设是集合A上的偏序关系，BA，试证明(BB)是B上的偏序关系。8 偏序关系Hasse图设是偏序集,

34、 x,yA可比(comparable): x与y可比 xy yx覆盖(cover): y覆盖x xy z( zA xzy )哈斯图(Hasse): 图中每个顶点代表A的一个元素,当且仅当y覆盖x时,在x与y之间画无向边, 并且x画在y下方链、反链8 偏序关系示例集合A=a, b, c, A的幂集P(A)上的包含关系是一个偏序关系 集合A=2, 3, 4, 6, 8, 12, 36, 60上的整除关系“”是一个偏序关系设n是一个正整数, Sn是n的所有因子的集合。 例如, 当n=30时, S30=1, 2, 3, 5, 6, 10, 15, 30。 设“|”是整除关系, 则是偏序集8 偏序关系特殊元素偏序集中的特殊元素设为偏序集, BA, yB最大元(maximum/greatest element): y是B的最大元 x( xB xy )最小元(minimum/least element): y是B的最小元 x( xB yx )极大元(maximal element): y是B的极大元 x(xB bx xb) 极小元(minimal element): y是B的极小元 x(xB bx bx)8 偏序关系特殊元素示例偏序集，由下图的哈斯图给出。 （1）B1=b,d,e,g （2）B2=b,c,d,e,f,g （3）B3=a,c,d （4）B4=d,e解 （