离散数学-3-4 序偶及笛卡儿积.pptVIP

第三章 集合与关系 3-4 序偶与笛卡儿积 授课人：李朔 Email:chn.nj.ls@ 一、序偶 生活中许多事物是成对出现的,并且这种成对出现的事物有一定的顺序。（选课，任课，住宿） 一般的说，两个具有固定顺序的客体组成一个序偶，它常常表达两个客体间的关系。序偶包含两个元素，但它们有确定的次序。 P101 定义3-4.1（1）由两个元素x, y（允许x=y）按一定顺序排成的二元组称有序对（序偶），记为x, y。称为序偶。 定义3-4.1（2）两个序偶相等，即 x, y=u, v当且仅当x=u, y=v。 注：序偶?x,y?中，x，y分别叫做第一元素（分量）和第二元素（分量），调换第一分量和第二分量位置后，就和原来的含义不同了。即当x?y 时，x, y? y, x。 例平面直角坐标系中的点1, -1，2, 2等 序偶a, b中两个元素不定来自同一个集合 一、序偶-推广到n元组 序偶的概念推广到三元组 三元组是序偶,其第一个元素本身也是一个序偶,可形式化为x,y,z 约定三元组可记作x,y,z x,y,z=u,v,w iff x=u,y=v,z=w 序偶概念可以推广到n元组，（n?3）是一个有序对，其中第一个元素为n-1元的有序对，一个有序的n元组记作， x1, x2, ?, xn即 x1, x2, ?, xn = x1, ?, xn-1, xn 应注意： x1, x2, x3 ? x1, x2, x3。 二、笛卡尔积 序偶x, y的元素可以分属于不同的集合，因此，对给定的集A，B可以定义一种新的集合运算，积运算。 定义3-4.2 设A，B为两个集合，用A的元素作为第一个元素，B的元素作为第二个元素组成序偶。所有这样的序偶组成的集合称为A与B的笛卡儿积，记为A?B，即： A?B={ x, y ? x?A?y?B} 例如 A={a, b} B={0, 1, 2}，则 A?B={a, 0, a, 1, a, 2, b, 0, b, 1, b, 2} B?A={0, a, 0, b, 1, a, 1, b, 2, a, 2, b} AXA？BXB？ 二、笛卡尔积 如果A，B都是有限集，|A|= n，|B|= m，根据排列组合原理，|A×B|=nm=|A||B|。 例 设 A=?a,b?，B=?1,2,3?， ⑴试求A×B和B×A ⑵验证|A×B|=|A||B|和|B×A|=|B||A| 解：⑴求A×B和B×A A×B=??a,1?,?a,2?,?a,3?,?b,1?,?b,2?,?b,3?? B×A=??1,a?,?1,b?,?2,a?, ?2,b?,?3,a?, ?3,b?? ⑵验证|A×B|=|A||B|和|B×A|=|B||A| |A×B|=6=2×3=|A||B| |B×A|=6=3×2=|B||A| 二、笛卡尔积 如果把×看成运算，笛卡尔积有以下的性质（P102）： ①设A为任意的集合，则A×? = ?×A= ?（约定） ②一般地说，当A?B且A，B都不空时 ×不满足交换律： 即A×B≠B×A。 在上例中，A×B≠B×A ③一般地说，当A,B,C都不是空集时,×不满足结合律： 即(A×B)×C≠A×(B×C)（后者不是三元组）（P102 例题1） P102 定理3-4.1 笛卡儿积对?或?运算满足分配律，即 （1）A?（B?C）=（A?B）?（A?C） （2）A?（B?C）=（A?B）?（A?C） （3）（A?B）?C=（A?C）?（B?C） （4）（A?B）?C=（A?C）?（B?C） *推广 （A?B）?（C ?D）=？ 二、笛卡尔积 定理3-4.1 证明：仅证第（1）个式子 对任意的x, y x, y ?A?(B?C) ? x ?A ?y ? B ? C ? x ? A ? (y?B ? y ? C) ? (x ? A ? y ? B)? (x ?A ? y ? C) ? x, y ? A?B ? x, y ? A?C ? x, y ?(A?B)?(A?C) A?(B?C)=(A?B)?(A?C) *可类似地证明⑵、⑶、⑷ 二、笛卡尔积 P103 定理3-4.2 设A，B，C是集合，C≠?，则 ⑴ A?B的充分必要条件是A×C?B×C ⑵ A?B的充分必要条件是C×A?C×B 证明: 仅证明⑴