离散数学课件-第章-.pptVIP

一、序偶与有序n元组 1.定义:由两个对象x、y组成的序列称为有序二元组，也称之为序偶，记作x,y；称x、y分别为序偶x,y的第一，第二元素。 注意，序偶x,y与集合{x,y}不同： 序偶x,y：元素x和y有次序； 集合{x,y}：元素x和y的次序无关紧要。 2.定义：设x,y，u,v是两个序偶， 如果x=u和y=v则称x,y和u,v相等， 记作x,y=u,v。 3 .定义：有序3元组是一个序偶,其第一个元素也是个序偶。 有序3元组 a,b, c可以简记成a,b,c， 但a,b,c不是有序3元组。 4.定义：有序n元组是一个序偶,其第一个元素本身是个有序n-1元组, 记作x1 , x2 ,? , xn-1, xn。且可以简记成 x1 , x2 ,? , xn-1, xn。 5. 定义x1, x2 ,…, xn=y1 , y2 ,…, yn ?( x1= y1)? ( x2= y2) ???( xn= yn) 例如“斗兽棋”的16颗棋子， 1.定义:设A、B是任意两个集合，由A的元素为第一元素，B的元素为第二元素组成序偶的集合，称为集合A和B的笛卡尔乘积或直积，记作A×B，即 A?B={x,y|x?A∧y?B} 【example】 设A={0,1}，B={a,b}，求A?B ， B?A， A?A 。 solution： A?B={0,a,0,b,1,a,1,b} B?A={a,0 ,b,0,a,1,b,1} A?A={0,0,0,1,1,0,1,1} 可见 A×B≠B×A。 所以，集合的笛卡尔积运算不满足交换律。 另外，由笛卡尔积定义可知 (A?B)?C={a,b,c|a,b?A?B ?c?C} A?(B?C)={a,b,c|a?A ?b,c?B?C}, 由于 a,b,c不是有序三元组, 所以(A?B)?C?A?(B?C)。故?也不满足结合律。 3) ?对∪和∩满足分配律。 设A,B,C是任意集合，则 ⑴ A?(B∪C)= (A?B)∪(A?C)； ⑵ A?(B∩C)= (A?B)∩(A?C)； ⑶ (A∪B)?C= (A?C)∪(B?C)； ⑷ (A∩B)?C= (A?C)∩(B?C)； 对⑴ A?(B∪C)= (A?B)∪(A?C)进行证明 proof⑴ ：任取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) 所以⑴式成立。（其余可以类似证明） 4) 若C??, 则 A?B?(A?C?B?C) ?(C?A?C?B) proof：充分性： 设A?B，求证 A?C?B?C 任取x,y?A?C ?x?A?y?C ?x?B?y?C (因A?B) ?x,y?B?C 所以, A?C?B?C。 必要性：若C??, 由A?C?B?C 求证 A?B 取C中元素y, 任取 x?A ?x?A?y?C ?x,y?A?C ?x,y?B?C (由A?C?B?C ) ?x?B?y?C? x?B 所以, A?B。 所以 A?B?(A?C?B?C) 类似可以证明 A?B ?(C?A?C?B)。 5) 设A、B、C、D为非空集合，则 A?B?C?D?A?C∧B?D proof：首先,由A?B?C?D 证明A?C∧B?D 任取x?A，任取y?B，所以 x?A?y?B?x,y?A×B ?x,y?C×D (由A?B?C?D ) ?x?C?y?D 所以, A?C∧B?D。 其次, 由A?C，B?D 证明A?B?C?D 任取x,y?A×B