离散数学3.4-5.ppt

34序偶与笛卡尔积,一、序偶定义:由两个元素x,y按照一定的次序组成的二元组称为有序偶对(序偶),记作,其中x为第一个元素，y为第二个元素。常常表达两个客体之间的关系。,序偶与笛卡尔积,例：平面上点的坐标；中国地处亚洲等都是序偶。序偶与集合的区别定义两个序偶相等当且仅当x=u且y=v,序偶与笛卡尔积,序偶的概念可以推广到三元组三元组是一个序偶，其第一元素本身也是序偶，可形式化表示为,z?同理四元组被定义为一个序偶，其第一元素为三元组。定义由N个元素a1,a2,a3,an按照一定的次序组成的N元组称为N重有序组，记作即：,an。,序偶与笛卡尔积,例：a年b月c日d时e分f秒可用下述六重有序组来描述：。性质:当且仅当aibi。(i1,2,3,.n)。,序偶与笛卡尔积,二、笛卡尔积定义设A，B是两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样序偶的集合，称为A和B的笛卡尔积或直积。记作AB：AB|(xA)(yB)。,序偶与笛卡尔积,例题若A=a,b,B=1,2,3，求AxB，BxA，AxA，BxB因此，一般情况下，对任何两个集合A、B，当AB时，有：ABBA，当AB时，有：ABBAA2。约定：如果A=，或者B=，则AxB=,笛卡尔积三条基本性质：1.A=且A=2.不满足交换律，即AB不一定等于BA。3.不满足结合律，即(AB)C不等于A(BC)。,序偶与笛卡尔积,笛卡尔积有如下性质(续)：4.笛卡尔积运算对并和交运算满足分配律，即：A(BC)=(AB)(AC)A(BC)=(AB)(AC)(AB)C=(AC)(BC)(AB)C=(AC)(BC)5.若C非空，则ABACBCCACB,序偶与笛卡尔积,定理：设A,B,C,D为4个非空集合，则ABCD的充要条件是AC，BD,序偶与笛卡尔积,定义设A1，A2，An是N个集合，称下述集合：A1A2An|(aiAi)i1,2,n为由A1，A2，A3，.，An构成的笛卡尔积。当A1A2An时，A1A2AnAn。,序偶与笛卡尔积,世界上存在着各种各样的关系。在数学中，关系可以表达集合中元素间的联系。如：”xy”,”点a在b和c之间”。序偶可以表达两个客体或多个客体之间的联系，因此用序偶表达关系。,3-5关系及其表示,例如，电影票与座位之间有对号关系，设X表示电影票的集合，Y表示座位的集合，R表示“对号”关系，则对于任意的xX，yY，必有x与y有对号关系和没有对号关系两种情况中的一种。上述问题可表达为xRy或xRy，也可记为R或R。由此可见对号关系R是一个序偶的集合。,一、关系定义任一序偶的集合确定了一个二元关系R，R中任一序偶可记为R或xRy。不在R中任一序偶可记为R，或xRy。例如：在实数中关系可记为,3-5、关系及其表示,定义设R为二元关系，由R的所有x组成的集合称为R的前域，即domR=x|y(xRy)使R的所有y组成的集合称为R的值域，即ranR=y|x(xRy)R的前域和值域一起称为R的域，记作FLDR，即FLDR=domRranR,例：设A=1,2,3,5,B=1,2,4,H=,，求domH,ranH,FLDH,关系及其表示,解：,关系及其表示,定义设A，B为两个集合，直积AxB的任何一个子集R称为从A到B的关系，简称关系(Relation)。特殊的，当A=B时，关系R是AxA的子集，这时称R为A上的二元关系。,关系及其表示,关系及其表示,例题设X=1,2,3,4，求X上的关系及dom和ran,关系及其表示,关系的数目：由于任何AB的子集都是一个二元关系，按照子集的定义，知AB共有个不同的子集。因此，从A到B不同的关系共有个。全域关系：AB的平凡子集AB称为A到B的全域关系空关系：AB的平凡子集称为A到B的空关系恒等关系：设IA是A的二元关系且满足IA=|xA,则称IA是A上的恒等关系,二、关系运算因为关系是序偶的集合，同一域上的关系，可以进行集合的所有运算。设R，S都是集合A到B的两个关系，则：RS|(xRy)(xSy)RS|(xRy)(xSy)R-S|(xRy)(xSy)R=|(xy)RAB-RRRABRR。,关系及其表示,关系及其表示,例：设Aa,b,c,B1,2，R,，S,，则：RS；RS；R-S；R,关系及其表示,三、关系的表示法1.集合表示法2.关系矩阵3.关系图法,关系及其表示,1.序偶集合表示法例1)、设A2,B3,关系R2)、如定义集合N上的“小于等于”关系：R|(x,yN)(xy)。,2.关系矩阵设A，B，R是从A到B的一个二元关系，则对应于关系R之关系矩阵MR（rij)nm。其中：称MR为R的邻接矩阵。,关系及其表示,例：设A2，3，4，B1，2，4.考虑从A到B的“大于等于”关系R和“小于等于”关系S：R,，S,。写出R，S的关系矩阵。解：,关系及其表示,三、关系图法如R是定义在Xx1,x2,x3,.,xn到Yy1,.,ym上的关系，则对应于关系R有如下规定：.在平面上作出n个节点分别记作x1,.,xn，再做m个节点记作y1,.,ym.如R,则从xi到yj可用一有向边相连。其箭头指向yj，如R,则xi到yj没有弧连接。这种方法连接起来的图称为R的关系图。,关系及其表示,例：设Aa1,a2,a3,a6是六个人，B1，2，3是三套房间，考虑A到B之间的一种住