离散数学第二章关系(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元组的情况。,定义3

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

3、),(0,c),(1,a),(1,b),(1,c)例2 A=张三,李四，B=白狗,黄狗 AB=(张三,白狗),(张三,黄狗),(李四,白狗),(李四,黄狗)BA=(白狗,张三),(白狗,李四),(黄狗,张三),(黄狗,李四),定理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）(AB)C=(AC)(B C)4）(AB)C=(AC)(B C),第二节 关系,2.1 关系的基本概念2.2 关系表示法,2.1 关系的基本概念,定义1 设A,B是两个非空集

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

5、上的二元关系。,定义2 设A,B是两个非空集合，R AB 1）若R=，则称R为空关系；2）若R=AB，则称R为全关系；3）若A=B 且 R=(a,a)aA，则称R是幺关系。定义3 设A,B是两个非空集合，R AB 1）设(R)=a(bB)(a,b)R)，称(R)为R的前域。2）设(R)=b(aA)(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上的两个二元关系，若 R1 R2，则 1）(R1)(R2)2）(R1)(R2)定理2 设R1,R2是AB上的两

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

7、素全部圈出来就得到关系R的图形表示。所有有向弧的始端点构成(R)，所有有向弧的终端点构成(R)。若A=B，则只需在一个集合中画出元素间的关系即可。,例：关系R的图形表示,2)关系的矩阵表示法 设A,B是两个非空的有限集合，R AB 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,a3,a4，R AA R=(a1,a1),(a1,a2),(a1,a3),(a1,a4),(a2,a2),(a2,a3),(a2,a4),(a3,a3),(a

8、3,a4),(a4,a4),关系R的关系矩阵,第三节 关系的运算,3.1 逆关系定义1 设A,B是两个非空集合，R AB R1=(b,a)|bB aA(a,b)R BA 称R1是R的逆关系。定理1 设A,B是两个非空集合，RAB，SAB，则 1）(R1)1=R 2）若 R S，则 R1 S1。3）(RS)1=R1S1 4）(RS)1=R1S1,3.2 复合关系定义2 设A,B,C是三个非空集合，R AB，S BC R o S=(a,c)|aA cC(bB)(a,b)R(b,c)S)称R o S为R与S的复合关系。例1 设A是老年男子的集合，B是中年男子的集合，C是青少年男子的集合。R是由A到B

9、的父子关系，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,c2),(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）

10、(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,第四节 二元关系的基本性质,定义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

11、),(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)由反自反关系的定义知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是

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

13、d，R=(a,b),(b,c),(a,c),(c,d),(a,d),(b,d)由传递关系的定义知R是X上的传递关系。例2 设X是平面上直线的集合，R=(x,y)|xXyXxy 由平面几何的知识知，若xy 且yz，则 xz。由传递关系的定义知R是X上的传递关系。例3 相等关系是传递关系。全关系X2是自反的、对称的、传递的。幺关系I 是自反的、对称的、反对称的、传递的。空关系是反自反的、对称的、反对称的、传递的。,第五节 等价关系,5.1 等价关系和等价类定义1 设R是非空集合X上的二元关系。若R是自反的、对称的、传递的，则称R是X上的等价关系。由于等价关系是自反的，故有(R)=(R)=X。例1

14、同乡关系是等价关系。例2 平面几何中的三角形间的相似关系是等价关系。例3 平面几何中的三角形间的全等关系是等价关系。例4 平面几何中的直线间的平行关系是等价关系。例5 设N是自然数集合，m是一个正整数，R=(a,b)|aN 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|xX，称 R为集合X

15、关于等价关系R的商集，记为X/R。称X/R中元素的个数为R的秩。例1 设N是非负自然数集合，m是一个正整数，R是N上的模m同余关系，R=(a,b)|aN bN(a b mod m)。由等价关系的定义知R是N上等价关系。N/R=0R，1R，2R，3R，m-1R 商集N/R共有m个等价类，R的秩为m。例2 设X为非空集合 1）若R是全关系，则X/R=X。（最粗的关系）2）若R是幺关系，则X/R=x|x X。（最细的关系）,定理1 设R是非空集合X上的等价关系。对任意的a,bX，有 1）a aR 2）(a,b)R 当且仅当 aR=bR 3）若 aR bR，则 aR=bR。4）aX，aR=X 定理2

16、设R1和R2是非空集合X上的两个等价关系。若R1 R2，则aX，有aR1 aR2。由定理2知，若两个等价关系相等，则每个元素所对应的等价类也相同。定理3 设R1和R2是非空集合X上的两个等价关系。若aX，有 aR1 aR2，则 R1 R2。由定理3知，若两个等价关系的等价类集合相等，则两个等价关系相同。由定理2和定理3知，等价关系与等价类集合一一对应。,5.2 划分与等价关系定义4 设A是一非空集合，=A|A，若 A A，则称是A上的覆盖。定义5 设A是一非空集合，=A|A。若 1）A=A 2）当 12 时，有 A 1A 2=则称是A上的一个划分。由划分的定义知，A上的划分一定是A上的覆盖。定

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

18、由定理7知可由推出 R，再由R推出，且=，故划分与等价关系是一一对应的。,第六节 半序关系,定义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上的包含关系如图所示。自反性省略。反对称性方向省略。传递性的边省略。,例2 设A=2,3,4,6,7,8,12,36,

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

20、若(bX)(xB)(xb)，则称 b是B的上界；2）若(aX)(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,4,6,7,8,12,36,60 R=(a,b)|aA bA a|b R是A上的整除关系，R是A上的半序关系。,定义6 设(X,)是半序集，若(aX)(bX)(abba)则称(X,)是全序集，同时称是全序关系。例1 整数之间的小于等于关系是全序关系。例2 有理数之间的小于等于关系是全序关系。例3 实数之间的小于等于关系是全序关系。定义7 设(X,)是半序集，若X的每个非空子集都有最小元素，则称(X,)是良序集，同时称是良序关系。例1 自然数之间的小于等于关系是良序关系。,