离散数学第3章(5-6)(新教材).ppt

第五节 笛卡尔积 在平面解析几何中,平面上的每个点约定用两个有序的实数对来表示,这种有序的实数对就是我们要研究的序偶的一种特殊情形。 定义5.1(二元序偶)设A,B是两个集合,x,y是分别从集合A和B这两个集合取来的任意两个元素.我们把形如的符号称为一个二元序偶.或者简称为一个序偶.x称为这个序偶的第一元素,y称为这个序偶的第二元素。 注意: 一般集合中的元素间是没有次序的, 故序偶用 表示 由定义容易看出:两个序偶相等, 当且仅当对应的元素相等, 即=,当且仅当x=u, y=v.,定义5.2(笛卡尔积) 设A和B是任意的集合, 所有可能的序偶作成的集合|(xA)(yB)称为集合A和B的笛卡尔积或直积, 记作AB.即 AB=|(xA)(yB). (注)如果|A|=m, |B|=n, 则|AB|=mn=|A|B|, 显然, 当A=, 或B=, 有AB=, 此时 |AB|=0.,定义5.2(三元序偶) 设A,B,C是三个集合,x,y,z是分别从这三个集合取来的任意三个元素.我们把形如,z的符号称为一个三元序偶.为了简便起见,三元序偶,z通常简写为.,定义5.3(n元序偶的递归定义) 设 是n个集合(n3),从每个集合中任取一个元素,记为 ,我们称符号 是一个n元序偶,如果 是一个n-1元序偶.通常我们将n元序偶 简记为 .,定义5.4(多重笛卡尔积) 设 是n个集合(n3),由一切n元序偶 ( ) 组成的集合称为这n个集合的n重笛卡尔积,记为 . 为简单起见我们将它记为 .特别地,如果 是一个给定的集合,则记 笛卡尔积有如下性质:,定理5.1 设A, B, C,D均为集合, 则有下列结论成立: (1)A(BC)=(AB)(AC), (BC)A=(BA)(CA), (2)A(BC)=(AB)(AC), (BC)A=(BA)(CA), (3)A(B-C)=(AB)-(AC), (B-C)A=(BA)-(CA), (4)若C,那么 1AB ACBC,2AB CACB.,(5)设A,B,C,D均为非空集合,则有 ABCD (AC)(BD). 证明:我们只给出(1)和(3)的第一式以及(5)的证明. (1)的第一式的证明: A(BC) (xA)(yBC) (xA)(yB)(yC) (xA)(yB)(xA)(yC) (AB)(AC) (AB)(AC), 同理可证其余.,(3)的第一式的证明: 只证明A(B-C)(AB)-(AC). A(BC) (xA)(yBC) (xA)(yB)(yC) (xA)(yB)(xA)(yC) (AB)(AC) (AB)(AC), 同理可证其余.,(5)式的证明: 1证明 ABCD (AC)(BD). 证明: xA,yB AB. ABCD CD (xC)(yD) (AC)(BD) . 相反的包含关系可以类似地加以证明.,第六节 关系及其表示 在科学以及人类社会活动中，到处都有各种各样的关系存在。 在数学中当然充满了关系，例如在整数之间对于取定的一个除数有余数相同的同余关系；在实数之间有大小关系；集合之间有包含关系；在三角形之间有全等关系以及相似关系；即便在人类社会中也有数不清的关系存在，例如家庭中的长幼关系、学校中的师生关系、工作单位里的同事关系以及上下级关系等等等等。 如何确切地表达“关系”这个概念，并对它进行深入的研究，是我们这一部分的一个重点内容。本书中重点讨论两个对象之间的“二元关系”，而不涉及多个对象之间的“多元关系”。,定义6.1 任意的序偶集合RAB称为集合A到B的一个二元关系(relation)， 若是关系R中的任意一个元素, 则记作R, 或xRy, 若不是关系R中的元素, 则记为R, 或者记作xRy,或者记为 ；当A=B时,称R为集合A上的一个二元关系.,例1. (整数集合上的同余关系) 取定一个正整数k(通常取k为大于1的整数,这样的数k在数论中称之为“模”,它的含义实际上是除法中的除数),将全体整数的集合 中的每一个整数被k除，取非负最小余数.容易看出,可能得到的不同的余数一共有以下k个:0,1,k-1.现在定义 上的一个二元关系 如下: , 这里 的含义是 整除 .通常我们把 表示成下面的形式, 这个式子可以读成“ 和 关于模 同余”.之所以这样说,其原因在于:当且仅当 成立时, 和 被模 除显然有相同的余数.,例3.给定集合A=a,b,c,d,在集合A上定义如下几两个二元关系R1,R2: R1=, R2=,.,例4.给定集合A=1,2,3,4,5,定义A上两个关系如下:,经过计算,它们实际上就是如下的两个关系 , .,由于任何非空集合都有两个平凡的子集:空集和它自己.同样地,给定任意一个非空集合A,笛卡尔积A2=AA也有两个平凡的子集:空集和它自己AA.根据定义, 和AA也都是集合A上的二元关系,分别称它们是A上的空关系以及全域关系.此外,任何非空集合上都有如下定义的一个特殊的关系 IA=|xA, 我们始终用符号IA来记这样一个特殊的关系,并称它是集合A上的恒等关系.,定义6.2(关系的前域、值域以及域) 设R是集合A到B的二元关系, dom R=x |(y)(R)称为R的前域, (domain) ran R=y |(x)(R)称为R的值域, (range) fldR=domRranR称为R的域。 (field) 显然, domRA, ranRB, RAB , filR=domRranR, 例如, 设A=1, 2, 3, 5, B=a, b, c, R=, , , ; 求: dom R, ran R, fld R . 解: dom R =1, 2, 3, ran R =b, c, fld R =domRranR=1, 2, 3, b, c.,关系除了可以用通常集合的表示方法(描述法以及列举法)表示以外, 还可以用关系矩阵和关系图来表示. 设有限集合A=x1, x2,xm, B=y1, y2,yn, R是A到B的关系, 则对应的关系矩阵M(R)=rijmn 是一个m行n列的矩阵,其中 rij =1, 当R, rij =0, 当R, (i=1, 2, m; j=1, 2, n).,仍以例4为例,写出相应的两个关系矩阵. 解:关系R1对应的关系矩阵如下示: ,而关系R2对应的关系矩阵如下示: .,设有限集合A=x1, x2,xm, B=y1, y2,yn, R是X到Y的关系, 在平面上画出m个结点表示x1, x2,xm, 画出n个结点表示y1, y2,yn, 如果R, 则自结点xi至yj引一有向弧, 如果R, 则不引自结点xi至yj的有向弧, 例如设A=x1, x2, x3, x4, B=y1, y2, y3, R=, , , , , , , 画出关系R的关系图。 x1 y1 x2 y2 x3 y3 x4,(注)下面要说明:“集合A到集合B的关系”与“集合A上的关系”没有本质的区别,在下面的意义下这两个概念可以统一起来: 设R是A到B的关系, 即RAB, 而AB(AB)(AB), 所以R(AB)(AB), 令Z=AB, 则RZZ, 即:在适当的范围内R也可以看成是“同一个集合Z上的关系