离散数学第二章关系(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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第二 关系 Relation

链接地址:https://www.31ppt.com/p-6595651.html