[工学]第6章 二元关系

《[工学]第6章 二元关系》由会员分享，可在线阅读，更多相关《[工学]第6章 二元关系（147页珍藏版）》请在金锄头文库上搜索。

1、电子科技大学离散数学课程组国家精品课程离散数学电子科技大学计算机科学与工程学院示范性软件学院*2电子科技大学离散数学课程组国家级精品课程第三篇 二元关系第6章 二元关 系3电子科技大学离散数学课程组国家级精品课程6.0 内容提要关系的性质3关系的闭包运算4二元关系1关系的运算24电子科技大学离散数学课程组国家级精品课程6.1本章学习要求重点掌握一般掌握了解11 二元关系的 概念和表示 2 关系的复合 与逆运算 3 关系的性质31 n重有序组2 n个集合的笛卡儿积3 n重有序组相等的判定21 关系的闭包运算5电子科技大学离散数学课程组国家级精品课程第三篇 二元关系关系理论历史悠久。它与集合论、数

2、理逻辑 、组合学、图论和布尔代数都有密切的联系。关系是日常生活以及数学中的一个基本概念 ，例如：兄弟关系，师生关系、位置关系、大小 关系、等于关系、包含关系等。6电子科技大学离散数学课程组国家级精品课程六度隔离理论six degree of separationn1967年，哈佛大学的心理学教授Stanley Milgram(1933-1984)想要描绘一个连结人与社 区的人际连系网。做过一次连锁信实验，结果 发现了“六度分隔”现象。简单地说：“你和 任何一个陌生人之间所间隔的人不会超过六个 ，也就是说，最多通过六个人你就能够认识任 何一个陌生人。” 7电子科技大学离散数学课程组国家级精品课程

3、Milgram的实验n他发现将一封信发到内布拉斯加州或则波士顿的任何 一个人然后就可以使这封信再到达马萨诸塞州任意一个 目标的手中。n这封信要求第一个随机收到信的人将信转发给他知道 的最有可能认识目标人物的那个人，但这个人必须是转 发者十分熟悉的好友。举个例子来说，如果第一个收信 人住在内布拉斯州，他认识马萨诸塞州的任何一个人， 他就可以将信发给这些人。然后这封信就会被继续不停 的传递下去直到到达目标人物手中。nMilgram发现借用每个人的社会网络，信从第一个人 开始传递到到达目标人物之间平均需要5.2个中间人。8电子科技大学离散数学课程组国家级精品课程email中的小小世界2003年，哥伦

4、比亚大学的瓦特和他的同 事在科学杂志上发表的一篇论文中称他们发现 了支持Milgram观点的证据。在他们的研究中， 参与邮件发送实验的人被要求通过他的朋友和 他认识的人转发一条消息给18个目标人物中的 一个，这18个人来自13个不同的国家。参与这 个实验的人数多达6万人。瓦特他们发现整个传 递链条最终都通过5-7步就完成了，这与 Milgram的观点极为相似。9电子科技大学离散数学课程组国家级精品课程最新研究：6.6度分割p微软研究中心的莱斯克威客与霍沃茨进行了一项新 的研究来讨论部分这种观点。因为他们使用的数据 将地理与社会等级界限给分开了。他们分析了2006 年一个月中由微软在世界范围内收

5、集到的300亿条即 时信息数据。p这些数据来自于超出以往分析过的堪称最大的社会 网络，通过仔细分析，他们发现任何两个即时信息 用户之间存在的平均间隔为数6.6，这比Milgram的 发现的间隔数稍微高一些。10电子科技大学离散数学课程组国家级精品课程关系与计算机另外，关系理论还广泛用于计算机科学技术， 如l计算机程序的输入、输出关系；l数据库的数据特性关系；l数据结构本身就是一个关系等。在某种意义下，关系是有联系的一些对象相互 之间的各种比较行为。11电子科技大学离散数学课程组国家级精品课程6.2 二元关系6.2.1 序偶与笛卡尔积 上,下；左，右；3, 其中x为第一个元素，y为第二个元素。1

6、2电子科技大学离散数学课程组国家级精品课程例6.2.1用序偶表示下列语句中的次序关系(1)平面上点A的横坐标是x,纵坐标是y,x,yR；(2)成都是四川的省会；(3)英语课本在书桌上；(4)左，右关系。解 各语句的序偶表示 如下：(1)，x,yR；(2)；(3) ；(4)。13电子科技大学离散数学课程组国家级精品课程注：序偶与集合的关系定义6.2.2 给定序偶和，如果a=c，b=d，则=。1.序偶可以看作是具有两个元素的集合，2.但是序偶中的两个元素具有确定的次序。即但是a,b=b,a.14电子科技大学离散数学课程组国家级精品课程N重有序组定义6.2.3由n个元素a1,a2,a3,an按照一定

7、次序 组成的n元组称为n重有序组(n-Type)(Vector)，记 作:例6.2.2 用n重有序组描述下列语句。（1）中国四川成都电子科技大学计算机学院；（2）2006年9月10日18点16分25秒；（3）16减5再加3除以7等于2。解各语句的n重有序组表示如下： （1） （2）； （3）。定义6.2.4给定n重有序组和。如果aibi(i1,2,，n)，则=。15电子科技大学离散数学课程组国家级精品课程笛卡尔乘积定义6.2.5设A，B是两个集合，称集合：AB|(xA)(yB)为集合A与B的笛卡尔积(DescartesProduct)。注意：（1）集合A与B的笛卡儿积AB仍然是集合；（2）集合

8、AB中的元素是序偶，序偶中的第一个 元素取自A，第二个元素取自B。16电子科技大学离散数学课程组国家级精品课程例6.2.3设A=a,B=b,c,C=,D=1,2，请分别写出 下列笛卡儿积中的元素。（1）AB,BA；（2）AC,CA；（3）A(BD),(AB)D。解 根据笛卡儿积的定义，有（1） AB=,BA=, ；（2）AC=,CA=；17电子科技大学离散数学课程组国家级精品课程例6.2.3 解（续）（3）因为BD=,，所以A(BD)=,。同理，(AB)D=,1,2,1,2。18电子科技大学离散数学课程组国家级精品课程注意由例6.2.3我们可以看出：（1）笛卡儿积不满足交换律；（2）AB=当且

9、仅当A=或者B=；（3）笛卡儿积不满足结合律；（4）对有限集A,B，有 |AB|=|BA|=|A|B|。19电子科技大学离散数学课程组国家级精品课程集合相等两个集合互相包含等式成立两个集合相等定理6.2.1笛卡尔积对并交满足分配 律 设A,B,C是任意三个集合，则（1）A(BC)=(AB)(AC)；（2）(BC)A=(BA)(CA)；（3）A(BC)=(AB)(AC)；（4）(BC)A=(BA)(CA)。分析 显然，待证等式两端都是集合20电子科技大学离散数学课程组国家级精品课程定理6.2.1 分析对（1）A(BC)=(AB)(AC) A(BC)(AB)(AC),(AB)(AC)A(BC)利用

10、按定义证明方法，首先叙述包含关系的定义，即 首先叙述A(BC)(AB)(AC)的定义：对任意A(BC)，有(AB)(AC)，则A(BC)(AB)(AC)。同理可分析(AB)(AC)A(BC)。21电子科技大学离散数学课程组国家级精品课程定理6.2.1 证明（1）对任意A(BC)，由笛卡儿积的定义知，xA且yBC；由并运算定义知，yB或者yC。于是有xA且yB或者xA且yC。从而，AB或者AC。即(AB)(AC)，所以，A(BC)(AB)(AC)。22电子科技大学离散数学课程组国家级精品课程定理6.2.1 证明（续）另一方面，对任意(AB)(AC)，由并运算定义知,AB或者AC 。由笛卡儿积的定

11、义知,xA且yB或xA且yC 。进一步有xA且yBC，从而A(BC)。所以(AB)(AC)A(BC)。于是，根据定理1.2.2，有A(BC)=(AB)(AC)。(2)、(3)和(4)的证明作为练习，自证。23电子科技大学离散数学课程组国家级精品课程定理6.2.2设A,B,C,D是任意四个集合，则 (AB)(CD)AC，BD。证明 充分性()：对任意AB，有xA且yB。又因为AC，BD，所以有xC且yD，即CD，从而(AB)(CD)。24电子科技大学离散数学课程组国家级精品课程定理6.2.2 证明（续）必要性()：对任意的xA，yB，有AB。又因为(AB)(CD)，所以CD。根据笛卡儿积的定义有

12、xC且yD，从而AC，BD。综上所述，定理成立。25电子科技大学离散数学课程组国家级精品课程定义6.2.6设A1,A2,An是n个集合，称集合A1A2An=|(aiAi)i1,2,3,n 为集合A1,A2,An的笛卡儿积 (DescartesProduct)当A1=A2=An=A时，有A1A2An=An。26电子科技大学离散数学课程组国家级精品课程定理6.2.3当集合A1,A2,An都是有限集时， |A1A2An|=|A1|A2|An|。27电子科技大学离散数学课程组国家级精品课程6.2.2关系的定义问题：某学校组织学生看电影，电影院里共有n 个座位，看电影的学生共有m个（mn），每个 学生坐

13、一个座位。请问，怎样表示学生和座位 之间的从属关系？a1a2a3amAB bnb3 b2 b10图6.2.1假设A,B分别表示某学校 所有学生的集合和电影院 里所有座位的集合，即A=a1,a2,am,B=b1,b2, ,bn。28电子科技大学离散数学课程组国家级精品课程定义6.2.7 设A,B为两个非空集合，称AB的 任何子集R为从A到B的二元关系，简称关系 (Relation)。如AB，则称R为A上的二元关系 。二元关系设一有序对： 若R，则记为xRy，读作“x对y有关系R”； 若R，则记为xRy，读作“x对y没有关系R” 。特别地，当R=时，称R为空关系(emptyrelation)；当R

14、=AB时，则称R为全关系(TotalRelation)。29电子科技大学离散数学课程组国家级精品课程例6.2.4假设A=a,b，B=c,d，试写出从A到B的所有 不同关系。解 因为A=a,b,B=c,d，所以 AB=,。于是AB 的所有不同子集为：0元子集：；1元子集：, ；2元子集：, 30电子科技大学离散数学课程组国家级精品课程例6.2.4 解（续）, ,；3元子集： ,；4元子集：,。注意 当集合A,B都是有限集时，AB共有2|A|B|个不同 的子集，即，从A到B的不同关系共有2|A|B|个。31电子科技大学离散数学课程组国家级精品课程域a1a2a3a4a6a5a7b1 b2b3b4b6

15、b5b7b8ABCDR后 域CA，满足：Cx|R，CdomR； DB，满足：Dy|R，DranR； fldRdomRranR为R的域。前 域定 义 域值 域显然，RCDAB。32电子科技大学离散数学课程组国家级精品课程求定义在Z上关系的定义域、值域和域。 （1）R1=|(x,yZ)y=x2；（2）R2=|(x,yZ)|x|=|y|=7。解（1）domR1=Z,ranR1=Z+0,fldR1=Z；（2）domR2=7,7,ranR2=7,7,fldR2=7,7。例6.2.533电子科技大学离散数学课程组国家级精品课程例6.2.6设H=f,m,s,d表示一个家庭中父母子女四个人 的集合，确定H上的一个长幼关系RH，指出该关 系的定义域、值域和域。解 RH=,