离散数学第二章关系(Relation).ppt

《离散数学第二章关系(Relation).ppt》由会员分享，可在线阅读，更多相关《离散数学第二章关系(Relation).ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 关系(Relation)第一节 集合的叉积第二节 关系第三节 关系的运算第四节 二元关系的基本性质第五节 等价关系第六节 半序关系第一节 集合的叉积定义1 设a,b 是两个个体，由a,b 组成的一个计较顺序的序列称为二元组，记为(a,b)。二元组不是集合，因为二元组中的个体计较顺序。第 i 个位置上的个体称为二元组的第 i 个坐标。不同位置上的个体可以来自同一个集合，也可以来自不同的集合。不同位置上的个体可以相同，也可以不相同。定义2 设=(a,b),=(c,d)。若a=c 且b=d，则称 与 相等，记为(a,b)=(c,d)。关于二元组和二元组相等的概念可以推广到m 元组的情况。定义

2、3 设A,B 是两个非空集合 A B=(a,b)a A bB 称A B 是A 与B 的叉积（笛卡儿积）集合。两个集合的叉积是一个新的集合，它的元素是一些二元组，在每个二元组中，第一个位置上的元素称为前者，第二个位置上的元素称为后者。在A B 中，A 称为前集，B 称为后集。前集与后集可以相同，也可以不相同。若前集与后集相同，则记为A A=A2。规定A=B。由于若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集。由于偶对中的元素是有序的，因此一般地说 A B B A例1 A=a,b,c,B=0,1 A B=(a,0),(a,1),(b,0),(b,1),(c,0),(c,

3、1)B A=(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)例2 A=张三,李四，B=白狗,黄狗 A B=(张三,白狗),(张三,黄狗),(李四,白狗),(李四,黄狗)B A=(白狗,张三),(白狗,李四),(黄狗,张三),(黄狗,李四)定理1 设A,B,C,D 是四个集合，那么 A B=C D 当且仅当 A=C 且 B=D。定理2 设A,B,C 是三个集合，则 1）A(BC)=(A B)(A C)2）A(BC)=(A B)(A C)3）(A B)C=(AC)(B C)4）(AB)C=(AC)(B C)第二节 关系2.1 关系的基本概念2.2 关系表示法2.1 关系的基本

4、概念定义1 设A,B 是两个非空集合，AB 是A 与B 的叉积集合。若R 是AB 的子集，则称R 是A 与B 元素之间的一个二元关系。当 a A 且 bB 且(a,b)R 时，称a 与b有关系R。当A=B 时，称R 是A 上的一个二元关系。例1 设A 是西安交通大学全体同学组成的集合，R=(a,b)a A bA a 与b是同乡 AA 例2 设A 是一个大家庭 R1=(a,b)a A bA a 是b的父亲或母亲 R2=(a,b)a A bA a 是b的哥哥或姐姐 R3=(a,b)a A bA a 是b的丈夫或妻子例3 设N 是自然数集合，R=(a,b)a N bN a b NN 称R 是自然数集

5、合上的整除关系。例4 设 X=风，马，牛，R=(风,马)，(马,牛)XX 称R 是X 上的二元关系。定义2 设A,B 是两个非空集合，R AB 1）若R=，则称R 为空关系；2）若R=AB，则称R 为全关系；3）若A=B 且 R=(a,a)a A，则称R 是幺关系。定义3 设A,B 是两个非空集合，R AB 1）设(R)=a(bB)(a,b)R)，称(R)为R的前域。2）设(R)=b(a A)(a,b)R)，称(R)为R的后域。例 A=1,2,3 B=2,4,6,8,10 R=(1,2),(2,4),(3,6)(R)=1,2,3 A(R)=2,4,6 B定理1 设R1,R2是AB 上的两个二元

6、关系，若 R1 R2，则 1）(R1)(R2)2）(R1)(R2)定理2 设R1,R2是AB 上的两个二元关系，则 1）(R1R2)=(R1)(R2)2）(R1R2)=(R1)(R2)3）(R1R2)(R1)(R2)4）(R1R2)(R1)(R2)2.2 关系表示法1)关系的图形表示法 设A,B 是两个非空的有限集合，R A B 分别用两个圆圈表示A,B 两个集合。在表示A 的圆圈中将A 的元素用小圆点表示，小圆点旁边是元素的名称。在表示B 的圆圈中将B 的元素用小圆点表示，小圆点旁边是元素的名称。关系R 中的偶对用有向弧表示。若A 中的某个元素x与B 中的某个元素y有关系R，则在x和y之间画

7、一条有向弧。有向弧的起始端与x相连，有向弧的终止端与y相连。将R 中所有的偶对连完之后，将所有的有向弧及和有向弧相连的元素全部圈出来就得到关系R 的图形表示。所有有向弧的始端点构成(R)，所有有向弧的终端点构成(R)。若A=B，则只需在一个集合中画出元素间的关系即可。A BbacdefghijR例：关系R 的图形表示2)关系的矩阵表示法 设A,B 是两个非空的有限集合，R A B A=a1,a2,a3,am B=b1,b2,b3,bn 令 MR=(xij)mn，i=1m,j=1n 1 当（ai,bj)R 时 xij=0 当（ai,bj)R 时 称MR为关系R 的关系矩阵。例 A=a1,a2,a

8、3,a4，R AA R=(a1,a1),(a1,a2),(a1,a3),(a1,a4),(a2,a2),(a2,a3),(a2,a4),(a3,a3),(a3,a4),(a4,a4)a1a2a3a4a1a2a3a410001 1 11 1 10 10 0 11关系R 的关系矩阵第三节 关系的运算3.1 逆关系定义1 设A,B 是两个非空集合，R AB R1=(b,a)|b B a A(a,b)R BA 称R1是R 的逆关系。定理1 设A,B 是两个非空集合，RA B，SA B，则 1）(R1)1=R 2）若 R S，则 R1 S1。3）(RS)1=R1S1 4）(RS)1=R1S1 3.2 复

9、合关系定义2 设A,B,C 是三个非空集合，R AB，S BC R o S=(a,c)|a A c C(bB)(a,b)R(b,c)S)称R o S 为R 与S 的复合关系。例1 设A 是老年男子的集合，B 是中年男子的集合，C 是青少年男子的集合。R 是由A 到B 的父子关系，R AB S 是由B 到C 的父子关系，S BC 则符合关系R o S 是A 到C 的祖孙关系。例2 设A=a1,a2,a3，B=b1,b2，C=c1,c2,c3,c4 R=(a1,b1),(a2,b2),(a3,b1)AB S=(b1,c4),(b2,c2),(b2,c3)BC R o S=(a1,c4),(a2,c

10、2),(a2,c3),(a3,c4)AC 定理2 设A,B,C,D 是四个非空集合，R,R1,R2 AB，S,S1,S2 BC，T CD 1）R o=o S=2）(R o S)(R)，(R o S)(S)3）若 R1 R2 且 S1 S2，则 R1 o S1 R2 o S2。4）(R o S)o T=R o(S o T)5）R o(S1S2)=(R o S1)(R o S2)(S1S2)o T=(S1 o T)(S2 o T)6）R o(S1S2)(R o S1)(R o S2)(S1S2)o T(S1 o T)(S2 o T)7）(R o S)1=S1 o R1 第四节 二元关系的基本性质定

11、义1 设R 是非空集合X 上的二元关系。若对X 中的每个元素x，都有(x,x)R，则称R 是X 上的自反关系。例1 设X=a,b,c,d，R=(a,b),(a,a),(b,b),(c,d),(c,c),(d,d)由自反关系的定义知R 是X 上的自反关系。若R=(a,a),(b,b),(c,c),(d,d)，则R 是X 上的幺关系。由此可知幺关系一定是自反关系，但自反关系不一定是幺关系。定义2 设R 是非空集合X 上的二元关系。若对X 中的每个元素x，都有(x,x)R，则称R 是X 上的反自反关系。例2 设X=a,b,c,d，R=(a,b),(a,c),(a,d),(c,d)由反自反关系的定义知

12、R 是X 上的反自反关系。定义3 设R 是非空集合X 上的二元关系。若对于任意的x,yX，当(x,y)R 时，有(y,x)R，则称R 是X 上的对称关系。例1 设X=a,b,c，R1=(a,b),(b,a)，R2=(a,a),(b,b)，R3=X2 由对称关系的定义知R1，R2，R3都是X 上的对称关系。例2 设R 是实数集合，S=(x,y)|x R yR x=y 由实数的性质知，当x=y 时，有y=x，由对称关系的定义知S是R 上的对称关系。推而广之，凡是相等关系都是对称关系。定义4 设R 是非空集合X 上的二元关系。若对于任意的x,yX，当(x,y)R 且(y,x)R 时，有 x=y，则称

13、R 是X 上的反对称关系。例1 设R 是实数集合，S=(x,y)|x R yR xy 由实数的性质知，当xy 且 yx 时，有x=y，由反对称关系的定义知S 是R 上的反对称关系。定义5 设R 是非空集合X 上的二元关系。若对于任意的x,y,z X，当(x,y)R 且(y,z)R 时，有(x,z)R，则称R 是X上的传递关系。例1 设X=a,b,c,d，R=(a,b),(b,c),(a,c),(c,d),(a,d),(b,d)由传递关系的定义知R 是X 上的传递关系。例2 设X 是平面上直线的集合，R=(x,y)|x X yX xy 由平面几何的知识知，若xy 且yz，则 xz。由传递关系的定

14、义知R 是X 上的传递关系。例3 相等关系是传递关系。全关系X2是自反的、对称的、传递的。幺关系I 是自反的、对称的、反对称的、传递的。空关系 是反自反的、对称的、反对称的、传递的。第五节 等价关系5.1 等价关系和等价类定义1 设R 是非空集合X 上的二元关系。若R 是自反的、对称的、传递的，则称R 是X 上的等价关系。由于等价关系是自反的，故有(R)=(R)=X。例1 同乡关系是等价关系。例2 平面几何中的三角形间的相似关系是等价关系。例3 平面几何中的三角形间的全等关系是等价关系。例4 平面几何中的直线间的平行关系是等价关系。例5 设N 是自然数集合，m 是一个正整数，R=(a,b)|a

15、 N bN(a b mod m)称R 是N 上的模m 同余关系。由等价关系的定义知R 是N 上等价关系。例6 非空集合X 上的幺关系、全关系都是等价关系。等价关系的实质是将集合X 中的元素分类。定义2 设R 是非空集合X 上的等价关系。xX，称y|(y,x)R为x关于R 的等价类，记为 xR.。同时称x为等价类 xR 的代表元素。定义3 设R 是非空集合X 上的等价关系。R=xR|x X，称 R为集合X 关于等价关系R 的商集，记为X/R。称X/R 中元素的个数为R 的秩。例1 设N 是非负自然数集合，m 是一个正整数，R 是N 上的模m同余关系，R=(a,b)|a N bN(a b mod

16、m)。由等价关系的定义知R 是N 上等价关系。N/R=0R，1R，2R，3R，m-1 R 商集N/R 共有m 个等价类，R 的秩为m。例2 设X 为非空集合 1）若R 是全关系，则X/R=X。（最粗的关系）2）若R 是幺关系，则X/R=x|x X。（最细的关系）定理1 设R 是非空集合X 上的等价关系。对任意的a,b X，有 1）a a R 2）(a,b)R 当且仅当 a R=bR 3）若 a R bR，则 a R=bR。4）a X，a R=X 定理2 设R1和R2是非空集合X 上的两个等价关系。若R1 R2，则a X，有a R1 a R2。由定理2知，若两个等价关系相等，则每个元素所对应的等

17、价类也相同。定理3 设R1和R2是非空集合X 上的两个等价关系。若a X，有 a R1 a R2，则 R1 R2。由定理3知，若两个等价关系的等价类集合相等，则两个等价关系相同。由定理2和定理3知，等价关系与等价类集合一一对应。5.2 划分与等价关系定义4 设A 是一非空集合，=A|A，若 A A，则称 是A 上的覆盖。定义5 设A 是一非空集合，=A|A。若 1）A=A 2）当 1 2 时，有 A 1A 2=则称 是A 上的一个划分。由划分的定义知，A 上的划分一定是A 上的覆盖。定理4 设R 是非空集合X 上的等价关系。R=xR|x X，则称 R 是X 上的一个划分。定理4表明由集合X 上

18、的等价关系R 产生的等价类集合构成集合X 上的一个划分。定理5 设 是非空集合A 上的一个划分，则由 可产生 A 上的等价关系。定理6 设R 是非空集合X 上的等价关系，=xR|x X 是R产生的X 上的等价类集合。由此集合产生的等价关系R 为(x,y)|(z X)(x zR yzR，则R=R。由定理6知可由R 推出，再由 推出R，且R=R，故等价关系与划分是一一对应的。定理7 设=A|A 是非空集合A 上的一个划分，R=(a,b)|()(a A bA)是由 产生的A 上的等价关系，=a R|a A 是由R 产生的等价类集合，则=。由定理7知可由 推出 R，再由R 推出，且=，故划分与等价关系

19、是一一对应的。第六节 半序关系定义1 设R 是非空集合X 上的二元关系，若R 是自反的、反对称的、传递的，则称R 是X 上的半序关系。通常将半序关系R 记为，称(X,)为半序集(Poset)。由于半序关系是自反的，故有(R)=(R)=X。例1 设A=a,b,c,2A=,a,b,c,a,b,a,c,b,c,a,b,c 由于2A上的包含关系是自反的、反对称的、传递的，故包含关系是2A上的半序关系。通常用Hasse 图表示半序关系。2A上的包含关系如图所示。自反性省略。反对称性方向省略。传递性的边省略。a cb,ca,b,ca,b a,cb 例2 设A=2,3,4,6,7,8,12,36,60 R=

20、(a,b)|a A bA a|b R 是A 上的整除关系。由整除的性质知R 是自反的、反对称的、传递的。由半序关系的定义知R 是A 上的半序关系。R 的Hasse 图如下：60 36 8 7423612定义2 设(X,)是半序集，1）若(bX)(xX)(xb)，则称 b是X 上的最大元。2）若(a X)(xX)(ax)，则称 a 是X 上的最小元。定理1 若半序集(X,)有最大(小)元，则最大(小)元唯一。定义3 设(X,)是半序集，1）任取bX，若X 中不存在元素x，使 bx 且 bx，则称 b 是X 中的极大元。2）任取a X，若X 中不存在元素x，使 xa 且 ax，则称 a 是X 中的

21、极小元。定义4 设(X,)是半序集，B X，1）若(bX)(xB)(xb)，则称 b是B 的上界；2）若(a X)(xB)(ax)，则称 a 是B 的下界。定义5 设(X,)是半序集，B X，1）设b是B 的一个上界，若对B 的任一上界b，有bb，则称b是B 的最小上界(上确界)，记为LUB(B)。2）设a 是B 的一个下界，若对B 的任一下界a，有a a，则称a 是B 的最大下界(下确界)，记为GLB(B)。讨论B 的最小上界(最大下界)的前提是B 的上界(下界)存在。B 的最小上界和最大下界未必存在。若存在，则唯一。B 的最小上界和最大下界可以在B 中，也可以不在B 中。例1 设A=2,3

22、,4,6,7,8,12,36,60 R=(a,b)|a A bA a|b R 是A 上的整除关系，R 是A 上的半序关系。集合 上界 下界 最小上界 最大下界B1=8,12无 4,2 无 4B2=2,36,12,36,60 无 6 无B3=7,8无 无 无 无B4=2,4,1212,36,60 212 2定义6 设(X,)是半序集，若(a X)(bX)(ab ba)则称(X,)是全序集，同时称 是全序关系。例1 整数之间的小于等于关系是全序关系。例2 有理数之间的小于等于关系是全序关系。例3 实数之间的小于等于关系是全序关系。定义7 设(X,)是半序集，若X 的每个非空子集都有最小元素，则称(X,)是良序集，同时称 是良序关系。例1 自然数之间的小于等于关系是良序关系。