离散数学-3-4 序偶与笛卡儿积.ppt

1、1,第三章 集合与关系,3-4 序偶与笛卡儿积 授课人：李朔 Email:,2,一、序偶,生活中许多事物是成对出现的,并且这种成对出现的事物有一定的顺序。（选课，任课，住宿） 一般的说，两个具有固定顺序的客体组成一个序偶，它常常表达两个客体间的关系。序偶包含两个元素，但它们有确定的次序。 P101 定义3-4.1（1）由两个元素x, y（允许x=y）按一定顺序排成的二元组称有序对（序偶），记为。称为序偶。 定义3-4.1（2）两个序偶相等，即 =当且仅当x=u, y=v。 注：序偶x,y中，x，y分别叫做第一元素（分量）和第二元素（分量），调换第一分量和第二分量位置后，就和原来的含义不同了。即

2、当xy 时， 。 例平面直角坐标系中的点，等 序偶中两个元素不定来自同一个集合,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的元素作为第二个元素组成序偶。所有这

3、样的序偶组成的集合称为A与B的笛卡儿积，记为AB，即： 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=2

4、3=|A|B| |BA|=6=32=|B|A|,6,二、笛卡尔积,如果把看成运算，笛卡尔积有以下的性质（P102）： 设A为任意的集合，则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,二

5、、笛卡尔积,定理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 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,二

6、、笛卡尔积,P104 定理3-4.3 设A，B，C，D是非空集合，则 ABCD的充分必要条件是AC且BD。 证明： 设ABCD， 下证 AC且BD aAbBa,bAB a,bCD aCbD 所以 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定义为(A1