[小学作文]第四章 二元关系.ppt

第四章 二元关系 李春利 中国民航学院 2005.3 本章内容 4-1.序偶与集合的笛卡尔积 4-2.关系及其表示法 4-3.关系的性质 4-4.关系的复合 4-5.逆关系 4-6.关系的闭包运算 4-7.集合的划分与覆盖 4-8.等价关系与等价类 4-9.相容关系 4-10.次序关系 小结 习题 二元关系是一个很重要的概念，它在很多数学领域中都有应用，在计算机科学的如下理论都离不开关系 ： 逻辑设计、 数据结构、 编译原理、 软件工程 数据库理论、 计算理论、 算法分析、 操作系统等。 本章主要介绍： 关系的概念及表示方法 关系的性质 关系的运算: 关系的复合, 逆关系, 关系的闭包 三种重要关系: 等价关系， 相容关系, 次序关系 4-1 序偶与集合的笛卡尔积 实际上“序偶”概念以前已经用过。 例如，用序偶表示平面直角坐标系 中一个点(a,b)。 设x表示上衣,y表示裤子, (x,y)可以表示一个人的着装。 一.序偶与有序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} 例1 设A={0,1}，B={a,b}，求A?B ， B?A， A?A 。 解： 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)。 故?也不满足结合律。 2.性质 1) 如果A、B都是有限集，且|A|=m, |B|=n，则 |A?B |=mn. 证明：由笛卡尔积的定义及排列组合中的乘法原 理，直接推得此定理。 2) A?Φ=Φ?B=Φ 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) 证明⑴ ：任取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). 证明: 必要性：设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