《离散数学-3-4序偶与笛卡儿积.ppt》由会员分享，可在线阅读，更多相关《离散数学-3-4序偶与笛卡儿积.ppt（12页珍藏版）》请在三一办公上搜索。
1、1,第三章 集合与关系,3-4 序偶与笛卡儿积 授课人：李朔,2,一、序偶,生活中许多事物是成对出现的,并且这种成对出现的事物有一定的顺序。（选课，任课，住宿）一般的说，两个具有固定顺序的客体组成一个序偶，它常常表达两个客体间的关系。序偶包含两个元素，但它们有确定的次序。P101 定义3-4.1（1）由两个元素x,y（允许x=y）按一定顺序排成的二元组称有序对（序偶），记为。称为序偶。定义3-4.1（2）两个序偶相等，即=当且仅当x=u,y=v。注：序偶x,y中，x，y分别叫做第一元素（分量）和第二元素（分量），调换第一分量和第二分量位置后，就和原来的含义不同了。即当xy 时，。例平面直角坐标
2、系中的点，等 序偶中两个元素不定来自同一个集合,3,一、序偶-推广到n元组,序偶的概念推广到三元组三元组是序偶,其第一个元素本身也是一个序偶,可形式化为,z约定三元组可记作,z=,w iff x=u,y=v,z=w序偶概念可以推广到n元组，（n3）是一个有序对，其中第一个元素为n-1元的有序对，一个有序的n元组记作，即=,xn应注意：。,4,二、笛卡尔积,序偶的元素可以分属于不同的集合，因此，对给定的集A，B可以定义一种新的集合运算，积运算。定义3-4.2 设A，B为两个集合，用A的元素作为第一个元素，B的元素作为第二个元素组成序偶。所有这样的序偶组成的集合称为A与B的笛卡儿积，记为AB，即：
3、AB=xAyB例如 A=a,b B=0,1,2，则 AB=,BA=,AXA？BXB？,5,二、笛卡尔积,如果A，B都是有限集，|A|=n，|B|=m，根据排列组合原理，|AB|=nm=|A|B|。例 设 A=a,b，B=1,2,3，试求AB和BA 验证|AB|=|A|B|和|BA|=|B|A|解：求AB和BA AB=a,1,a,2,a,3,b,1,b,2,b,3 BA=1,a,1,b,2,a,2,b,3,a,3,b 验证|AB|=|A|B|和|BA|=|B|A|AB|=6=23=|A|B|BA|=6=32=|B|A|,6,二、笛卡尔积,如果把看成运算，笛卡尔积有以下的性质（P102）：设A为任
4、意的集合，则A=A=（约定）一般地说，当AB且A，B都不空时 不满足交换律：即ABBA。在上例中，ABBA 一般地说，当A,B,C都不是空集时,不满足结合律：即(AB)CA(BC)（后者不是三元组）（P102 例题1）P102 定理3-4.1 笛卡儿积对或运算满足分配律，即（1）A（BC）=（AB）（AC）（2）A（BC）=（AB）（AC）（3）（AB）C=（AC）（BC）（4）（AB）C=（AC）（BC）*推广（AB）（C D）=？,7,二、笛卡尔积,定理3-4.1 证明：仅证第（1）个式子对任意的 A(BC)x A y B C x A(yB y C)(x A y B)(x A y C)AB
5、 AC(AB)(AC)A(BC)=(AB)(AC)*可类似地证明、,8,二、笛卡尔积,P103 定理3-4.2 设A，B，C是集合，C，则 AB的充分必要条件是ACBC AB的充分必要条件是CACB证明:仅证明,可类似地证明。设AB，下证 AC BC a,bACaAbC aBbC a,bBC 所以 ACBC 设ACBC，下证 AB 因为C，所以存在bC aAaAbCa,bAC a,bBCaBbCaB 所以 AB,9,二、笛卡尔积,P104 定理3-4.3 设A，B，C，D是非空集合，则 ABCD的充分必要条件是AC且BD。证明：设ABCD，下证 AC且BD aAbBa,bAB a,bCD aC
6、bD 所以 AC且BD 设AC且BD，下证ABCD a,bABaAbB aCbD a,bCD 所以 ABCD,10,二、笛卡尔积,两集合的笛卡尔积仍是一个集合，故有限集可以进行多次的乘积，为了与n 元组一致，我们约定：定义 笛卡尔积A1A2An定义为(A1A2An-1)An，即A1A2An=x1,x2,xn|x1A1x2A2xnAn 由定义可以看出：当n=3时，A1A2A3定义为(A1A2)A3 A1A2A3=x1,x2,x3|x1A1x2A2x3A3 当n=4时，A1A2A3A4定义为(A1A2A3)A4 A1A2A3A4=x1,x2,a3,a4|x1A1x2A2x3A3x4A4*约定 An=,11,本课小结,序偶笛卡尔积笛卡积的性质,12,作业,P104（1）,
