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

《离散数学第二章关系(Relation).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、0,1}AB={(a,0),(a,1),(b,0),(b,1),(c,0),(c,1)}BA={(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)}例2A={张三,李四}，B={白狗,黄狗}AB={(张三,白狗),(张三,黄狗),(李四,白狗),(李四,黄狗)}BA={(白狗,张三),(白狗,李四),(黄狗,张三),(黄狗,李四)}定理1设A,B,C,D是四个集合，那么AB=CD当且仅当A=C且B=D。定理2设A,B,C是三个集合，则1）A(B∪C)=(AB)∪(AC)2）A(B∩C)=(AB)∩

4、(AC)3）(A∪B)C=(A×C)∪(BC)4）(A∩B)C=(A×C)∩(BC)第二节关系2.1关系的基本概念2.2关系表示法2.1关系的基本概念定义1设A,B是两个非空集合，A×B是A与B的叉积集合。若R是A×B的子集，则称R是A与B元素之间的一个二元关系。当aA且bB且(a,b)R时，称a与b有关系R。当A=B时，称R是A上的一个二元关系。例1设A是西安交通大学全体同学组成的集合，R={(a,b)∣aA∧bA∧a与b是同乡}A×A例2设A是一个大家庭R1={(a,b)∣aA∧bA∧a是b的父亲或母亲}R2

5、={(a,b)∣aA∧bA∧a是b的哥哥或姐姐}R3={(a,b)∣aA∧bA∧a是b的丈夫或妻子}例3设N是自然数集合，R={(a,b)∣aN∧bN∧a｜b}N×N称R是自然数集合上的整除关系。例4设X={风，马，牛}，R={(风,马)，(马,牛)}X×X称R是X上的二元关系。定义2设A,B是两个非空集合，RA×B1）若R=，则称R为空关系；2）若R=A×B，则称R为全关系；3）若A=B且R={(a,a)∣aA}，则称R是幺关系。定义3设A,B是两个非空集合，RA×B1）设(R)={a∣(bB)((a,b)

6、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是A×B上的两个二元关系，若R1R2，则1）(R1)(R2)2）(R1)(R2)定理2设R1,R2是A×B上的两个二元关系，则1）(R1∪R2)=(R1)∪(R2)2）(R1∪R2)=(R1)∪(R2)3）(R1∩R2)(R1)∩(R2

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

8、点构成(R)，所有有向弧的终端点构成(R)。若A=B，则只需在一个集合中画出元素间的关系即可。ABbacdefghijR例：关系R的图形表示2)关系的矩阵表示法设A,B是两个非空的有限集合