(1.5.4)--ch3—第二讲离散数学离散数学.pdf
离散数学离散数学 Discrete Mathematics 3.4 序偶与笛卡尔积序偶与笛卡尔积 1.序偶序偶 定义定义.由两个客体由两个客体 x和和y 按一定顺序排列成的二元组叫作按一定顺序排列成的二元组叫作 一个一个有序对有序对或或序偶序偶,记作记作.注意注意 序偶的次序不能随便调换序偶的次序不能随便调换.序偶序偶允许允许xy,且且 x 和和 y可以代表不同类型的事物可以代表不同类型的事物.当当x y 时时,称称 x 为序为序偶偶的的第一元素第一元素,y为序为序偶偶的的第二元素第二元素.定义定义3-4.1 两个序偶相等两个序偶相等,=,iff xu,yv.序偶的概念可以推广到序偶的概念可以推广到n元组：元组：三元组三元组:,z 四元组四元组:,w n元组元组:,xn=(a1=b1)(an=bn)两个两个n元组相等元组相等 xi 称为称为n元组的第元组的第i个坐标个坐标.=2.笛卡尔积笛卡尔积(Descartes Product)设设 A 和和B 是任意两集合是任意两集合,若序偶的第一成员是若序偶的第一成员是 A的元素的元素,第二个成员是第二个成员是 B 的元素的元素,所有这样的序偶集合称为所有这样的序偶集合称为 A和和B的的笛卡尔积笛卡尔积或或直积直积,记作记作AB.符号表示为符号表示为:AB=|x Ay B 定义定义3-4.2 例例1.设设A=a,b,B=1,2,3.试求试求AB,BA,解解.=,，BA=,AB(AB)(BA)=(AB)(BA).注意注意:若若A=或或B=,则则AB=一般地说一般地说,笛卡尔积运算不满足交换律笛卡尔积运算不满足交换律,即即 AB BA(当当ABAB 时时)笛卡尔积运算不满足结合律笛卡尔积运算不满足结合律,即即 (AB)C A(BC)(当当ABC时时)(AB)C=,c|(AB)c C A(BC)=a,|a A(BC)=|(a A)(b B)(c C)故故(AB)C A(BC)笛卡尔积的性质笛卡尔积的性质 定理定理3.4.1 设设A、B、C是任意的集合是任意的集合,则有则有(1)A(BC)(AB)(AC)(2)A(BC)(AB)(AC)(3)(AB)C(AC)(BC)(4)(AB)C(AC)(BC)定理定理3.4.2 若若C,则则 A B (AC BC)(CA CB)定理定理3.4.3 设设A,B,C,D为任意四个非空集合为任意四个非空集合,则有如下结论则有如下结论:A B C D 的充分必要条件是的充分必要条件是 A C,B D.定义推广定义推广 A1A2A3=(A1A2)A3 A1A2A3A4=(A1A2 A3)A4=(A1A2)A3)A4 一般地一般地,A1A2An=(A1A2An-1)An=|a1A1 a2A2 anAn 当当A1=A2=An=A时时,AAAAn.例例.设设 A=u,v,B=a,b,C=c ,试求试求 ABC.ABC=,3-5 关系及其表示关系及其表示 1.关系的定义关系的定义(The definition of Relation)定义定义3.5.1 任一任一序偶的集合序偶的集合确定了一个二元关系确定了一个二元关系R,R 中任一中任一 序偶序偶可记作可记作R或或 xRy.不在不在R中的序偶可中的序偶可记作记作 xRy.例如例如,R1=,R2=,1,2 注意注意:关系为一集合关系为一集合.aR1b,1R12 定义定义3.5.2 设设R是二元关系是二元关系,由由 R的所有的所有x 组成的集合组成的集合 称为称为R的的前域前域,记作记作dom R,即即 dom R=x|(y)(R)使使 R的所有的所有y 组成的集合称为组成的集合称为R的的值域值域,记作记作ran R.即即 ran R=y|(x)(R)R的前域和值域的并集称为的前域和值域的并集称为R 的的域域.记作记作FLD R,即即 FLD R=dom Rran R 例例.关系关系 R,FLD R=1,2,3,4 ran R=2,3,4 dom R=1,2,4 定义定义3.5.3 设设 X,Y是任意两个集合是任意两个集合,直积直积 XY 的的子集子集 R,称为称为从从 X 到到Y 的关系的关系.特别当特别当X=Y 时时,则称则称R为为X上的二元关系上的二元关系.R X Y domR ranR FLDR dom R X ran R Y FLD R XY 定理定理3.5.1 设设 R,S是从集合是从集合A到集合到集合B的两个关系的两个关系,则则 RS,RS及及 R S 仍是仍是 A到到B 的的关系关系.例题例题3 设设 X=1,2,3,4,若若 2,xyHx yZ 3,xySx yZ 求求 HS,HS,S-H.H,解解.HS H S-H H=,S=,=,=HS=例例.A=a,b,c,则则 EA IA=,=,2.几种特殊的关系几种特殊的关系(Several special Relations)空关系空关系 全域关系全域关系 IX=|x X 恒等关系恒等关系 把把XY的两个平凡的子集的两个平凡的子集 XY和和,分别称为分别称为X到到Y的的 全域关系全域关系和和空关系空关系.定义定义3-5.4 设设 IX是是 X上的二元关系且满足上的二元关系且满足 则称则称IX为为X上的上的恒等关系恒等关系.3.常用关系常用关系(1)设设 A R,A上上小于等于关系小于等于关系:(3)幂集幂集 P(A)上的上的包含关系包含关系:LA=|x,y Ax y (2)设设 B Z+,B上上整除关系整除关系:DB=|x,y Bx y R =|x,y P(A)x y 4.关系的表示关系的表示(The expression of Relations)集合表示法集合表示法 矩阵表示法矩阵表示法 定义定义1.设设 其中其中,10,ijijija bRra bR (1,2,.,)in(1,2,.,)jm 111212122212()mmRij n mnnnmrrrrrrMrrrr nmAa aaBb bb1212,是两个有限集是两个有限集,RA B则称则称 行行 列矩阵列矩阵 nm()Rijn mMr 为为 的的关系矩阵关系矩阵,R则则 的关系矩阵的关系矩阵 RRM如下所示如下所示.1a2ana1b2bmb 例例5 设集合设集合 定义从定义从 到到 的的 关系关系 2,3,4,5,6,2,3,4,ABBA,Rx y 求关系矩阵求关系矩阵.xy的倍数的倍数 是是 解解 R的关系矩阵为的关系矩阵为:0 1 1 1 0 1 0 1 0 0 0 1 0 0 0 RM 6 4 3 2 5 4 3 2 2,2,3,3,4,2,4,4,6,2,6,3 R 关系图表示法关系图表示法 设设 nmAa aaBb bb1212,是两个有限集是两个有限集,定义定义2.另外作出另外作出 个结点分别记作个结点分别记作 mb bb12,.m(1)在平面上作出在平面上作出 个结点分别记作个结点分别记作 然后然后 na aa12,n为为 到到 上的关系上的关系,则则 RAB(2)当且仅当当且仅当 且且 时时,自结点自结点 到结点到结点,aA bB,a bRab作出一条有向弧作出一条有向弧,其箭头指向其箭头指向.b用这种方法得到的图称为用这种方法得到的图称为 的的关系图关系图.记为记为 R注注:若在一个集合若在一个集合 上的二元关系上的二元关系 ,出现出现 ,画法同上画法同上;RaRbA.RG而出现而出现 时时,则画一条从结点则画一条从结点 到结点到结点 的带箭头的封闭弧的带箭头的封闭弧.aRaaa关系图主要表达邻接关系关系图主要表达邻接关系,与结点位置和线段长短无关与结点位置和线段长短无关.例例6 设集合设集合A2,3,4,5,6,B2,3,4,定义从定义从A到到B的关系的关系,R=|x 是是 y的倍数的倍数,画出关系图画出关系图.解解 2 2 3 3 4 4 5 6 例例7 设集合设集合 是是 上的一个二元关系上的一个二元关系,求关系图求关系图 c a b d 关系图如图所示关系图如图所示 解解 ,Aa b c d AR,Ra aa bb cb dc ac cc dd b .RG练习练习 设集合设集合A=1,2,3,4求关系矩阵和关系图求关系矩阵和关系图,解解 关系矩阵：关系矩阵：1100001100100100MR =关系图关系图 其中其中R=,3 1 2 4
