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

1、 第五节第五节 笛卡尔积笛卡尔积 在平面解析几何中在平面解析几何中,平面上的每个点约定用两平面上的每个点约定用两个有序的实数对来表示个有序的实数对来表示,这种有序的实数对就是我这种有序的实数对就是我们要研究的序偶的一种特殊情形。们要研究的序偶的一种特殊情形。 定义定义5.1(二元序偶二元序偶)设设A,B是两个集合是两个集合,x,y是分别是分别从集合从集合A和和B这两个集合取来的任意两个元素这两个集合取来的任意两个元素.我们我们把形如把形如的符号称为一个二元序偶的符号称为一个二元序偶.或者简称为或者简称为一个序偶一个序偶.x称为这个序偶的第一元素称为这个序偶的第一元素,y称为这个序称为这个序偶的

2、第二元素。偶的第二元素。 注意注意: 一般集合中的元素间是没有次序的一般集合中的元素间是没有次序的, 故故序偶用序偶用 表示表示由定义容易看出由定义容易看出:两个序偶相等两个序偶相等, 当且仅当对当且仅当对应的元素相等应的元素相等, 即即=,当且仅当当且仅当x=u, y=v. 定义定义5.2(笛卡尔积笛卡尔积) 设设A和和B是任意的是任意的集合集合, 所有可能的序偶作成的集合所有可能的序偶作成的集合|(x A) (y B)称为集合称为集合A和和B的的笛卡笛卡尔积或直积尔积或直积, 记作记作A B.即即 A B=|(x A) (y B).(注注)如果如果|A|=m, |B|=n, 则则|A B|

3、=m n=|A| |B|, 显然显然, 当当A=, 或或B=, 有有A B=, 此此时时 |A B|=0.定义定义5.2(三元序偶三元序偶) 设设A,B,C是三个集合是三个集合,x,y,z是分别从这三个是分别从这三个集合取来的任意三个元素集合取来的任意三个元素.我们把形如我们把形如,z的符号称为一个三元序偶的符号称为一个三元序偶.为了简为了简便起见便起见,三元序偶三元序偶,z通常简写为通常简写为.定义定义5.3(n元序偶的递归定义元序偶的递归定义) 设设 是是n个集合个集合(n3),从每个集从每个集合中任取一个元素合中任取一个元素,记为记为 ,我们称我们称符号符号 是一个是一个n元序偶元序偶,

4、如如果果 是一个是一个n-1元序偶元序偶.通常我们将通常我们将n元序偶元序偶 简记为简记为 . 12,.,nA AA12,.,nx xx121,.,nnx xxx121,.,nx xx121,.,nnx xxx121,.,nnx xxx定义定义5.4(多重笛卡尔积多重笛卡尔积)设设 是是n个集合个集合(n3),由一切由一切n元序偶元序偶 ( )组成的集合称为这组成的集合称为这n个集合的个集合的n重笛卡尔积重笛卡尔积,记为记为 .为简单起见我们将它记为为简单起见我们将它记为 .特别地特别地,如果如果 是一个给定的集合是一个给定的集合,则记则记笛卡尔积有如下性质笛卡尔积有如下性质:12,.,nA

5、AA121,.,nnx xxx1122,.,nnxA xAxA123.nAAAA12.nAAAA23, .,.nnAA AAA A AAA AA 定理定理5.1 设设A, B, C,D均为集合均为集合, 则有下列结则有下列结论成立论成立:(1)A (B C)=(A B) (A C), (B C) A=(B A) (C A),(2)A (B C)=(A B) (A C), (B C) A=(B A) (C A),(3)A (B-C)=(A B)-(A C), (B-C) A=(B A)-(C A),(4)若若C ,那么那么1A B A C B C,2A B C A C B. (5)设设A,B,C

6、,D均为非空集合均为非空集合,则有则有 A B C D (A C) (B D). 证明证明:我们只给出我们只给出(1)和和(3)的第一式以及的第一式以及(5)的的证明证明.(1)的第一式的证明的第一式的证明: A (B C) (x A) (y B C) (x A) (y B) (y C) (x A) (y B) (x A) (y C) ( A B) ( A C) (A B) (A C), 同理可证其余同理可证其余.(3)的第一式的证明的第一式的证明:只证明只证明A (B-C) (A B)-(A C). A (BC) (x A) (y BC) (x A) (y B) (y C) (x A) (y

7、 B) (x A) (y C) ( A B) ( A C) (A B)(A C), 同理可证其余同理可证其余.(5)式的证明式的证明:1证明证明 A B C D (A C) (B D).证明证明: x A, y B A B. A B C D C D (x C) (y D) (A C) (B D) . 相反的包含关系可以类似地加以证明相反的包含关系可以类似地加以证明. 第六节第六节 关系及其表示关系及其表示 在科学以及人类社会活动中，到处都有各种各在科学以及人类社会活动中，到处都有各种各样的关系存在。样的关系存在。 在数学中当然充满了关系，例如在整数之间在数学中当然充满了关系，例如在整数之间对于

8、取定的一个除数有余数相同的同余关系；在对于取定的一个除数有余数相同的同余关系；在实数之间有大小关系；集合之间有包含关系；在实数之间有大小关系；集合之间有包含关系；在三角形之间有全等关系以及相似关系；即便在人三角形之间有全等关系以及相似关系；即便在人类社会中也有数不清的关系存在，例如家庭中的类社会中也有数不清的关系存在，例如家庭中的长幼关系、学校中的师生关系、工作单位里的同长幼关系、学校中的师生关系、工作单位里的同事关系以及上下级关系等等等等。事关系以及上下级关系等等等等。 如何确切地表达如何确切地表达“关系关系”这个概念，并对它这个概念，并对它进行深入的研究，是我们这一部分的一个重点内进行深入

9、的研究，是我们这一部分的一个重点内容。本书中重点讨论两个对象之间的容。本书中重点讨论两个对象之间的“二元关二元关系系”，而不涉及多个对象之间的，而不涉及多个对象之间的“多元关系多元关系”。 定义定义6.1 任意的序偶集合任意的序偶集合R A B称称为集合为集合A到到B的一个的一个二元关系二元关系(relation)， 若若是关系是关系R中的任意一个元素中的任意一个元素, 则则记作记作 R, 或或xRy, 若若不是关系不是关系R中的元素中的元素, 则记为则记为 R, 或者记作或者记作xRy,或者记为或者记为 ；当当A=B时时,称称R为为集合集合A上的一个二元关系上的一个二元关系.x R y例例1

10、. (整数集合上的同余关系整数集合上的同余关系) 取定一个正整数取定一个正整数k(通常取通常取k为大于为大于1的整数的整数,这样的数这样的数k在数论中称之为在数论中称之为“模模”,它的含它的含义实际上是除法中的义实际上是除法中的除数除数),将全体整数的集将全体整数的集合合 中的每一个整数被中的每一个整数被k除，取非负最小余除，取非负最小余数数.容易看出容易看出,可能得到的不同的余数一共有可能得到的不同的余数一共有以下以下k个个:0,1,k-1.现在定义现在定义 上的一个上的一个二元关系二元关系 如下如下: ,这里这里 的含义是的含义是 整除整除 .通常通常我们把我们把 表示成下面的形式表示成下

11、面的形式Z ZZ ZkR,kx yx yRkxyZ Zkxykx ykxy ,这个式子可以读成这个式子可以读成“ 和和 关于模关于模 同同余余”.之所以这样说之所以这样说,其原因在于其原因在于:当且仅当当且仅当成立时成立时, 和和 被模被模 除显然有相同的余除显然有相同的余数数.(mod )xykxykkxyxyk例例3.给定集合给定集合A=a,b,c,d,在集合在集合A上定义如上定义如下几两个二元关系下几两个二元关系R1,R2:R1=,R2=,.例例4.给定集合给定集合A=1,2,3,4,5,定义定义A上两个关系上两个关系如下如下:1,2xyRx yx yA Z Z2,3xyRx yx yA

12、 Z Z11 ,1 , 2 ,2 , 3 ,3 , 4 ,4 , 5 ,5 , 1 ,3 , 3 ,1 ,R 1,5 ,5,1 ,3,5 ,5,3 ,2,4 ,4,2 经过计算经过计算,它们实际上就是如下的两个关系它们实际上就是如下的两个关系 , .11,1 ,2,2 ,3,3 ,R 4,4 ,5,5 , 1,3 ,3,1 , 1,5 , 5,1 ,3,5 ,5,3 ,2,4 ,4,2 5,5 , 1,4 ,4,1 ,2,5 ,5,2 21,1 ,2,2 ,3,3 ,4,4 ,R 由于任何非空集合都有两个平凡的子由于任何非空集合都有两个平凡的子集集:空集和它自己空集和它自己.同样地同样地,给定

13、任意一个非给定任意一个非空集合空集合A,笛卡尔积笛卡尔积A2=A A也有两个平凡的也有两个平凡的子集子集:空集空集和它自己和它自己A A.根据定义根据定义, 和和A A也都是集合也都是集合A上的二元关系上的二元关系,分别称它分别称它们是们是A上的上的空关系空关系以及以及全域关系全域关系.此外此外,任何任何非空集合上都有如下定义的一个特殊的关非空集合上都有如下定义的一个特殊的关系系 IA=| x A, 我们始终用符号我们始终用符号IA来记这样一个特殊的来记这样一个特殊的关系关系,并称它是集合并称它是集合A上的恒等关系上的恒等关系. 定义定义6.2(关系的前域、值域以及域关系的前域、值域以及域)

14、设设R是集合是集合A到到B的二元关系的二元关系, dom R=x |( y)( R)称为称为R的的前域前域, (domain)ran R=y |( x)( R)称为称为R的的值域值域, (range)fldR=domR ranR称为称为R的的域域。 (field)显然显然, domR A, ranR B, R A B , filR=domR ranR,例如例如, 设设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 =domR ranR=1, 2,

15、3, b, c.关系除了可以用通常集合的表示方法关系除了可以用通常集合的表示方法(描述法以及描述法以及列举法列举法)表示以外表示以外, 还可以用还可以用关系矩阵关系矩阵和和关系图关系图来表来表示示. 设有限集合设有限集合A=x1, x2,xm, B=y1, y2,yn,R是是A到到B的关系的关系, 则对应的则对应的关系矩阵关系矩阵M(R)=rijm n 是一个是一个m行行n列的矩阵列的矩阵,其中其中 rij =1, 当当 R, rij =0, 当当 R, (i=1, 2, m; j=1, 2, n).仍以例仍以例4为例为例,写出相应的两个关系矩阵写出相应的两个关系矩阵.解解:关系关系R1对应的

16、关系矩阵如下示对应的关系矩阵如下示: , 11010101010()101010101010101MR而关系而关系R2对应的关系矩阵如下示对应的关系矩阵如下示: . 21001001001()001001001001001MR 设有限集合设有限集合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的有向弧的有向弧,例如设例如设

17、A=x1, x2, x3, x4, B=y1, y2, y3, R=, , , , , , , 画出关系画出关系R的关系图。的关系图。 x1 y1 x2 y2 x3 y3 x4 (注注)下面要说明下面要说明:“集合集合A到集合到集合B的关系的关系”与与“集合集合A上的关系上的关系”没有本质的区别没有本质的区别,在下面的意在下面的意义下这两个概念可以统一起来义下这两个概念可以统一起来: 设设R是是A到到B的关系的关系, 即即R A B, 而而A B (A B) (A B), 所以所以R (A B) (A B),令令Z=A B, 则则R Z Z, 即即:在适当的范围内在适当的范围内R也可以也可以看成是看成是“同一个集合同一个集合Z上的关系上