1、离 散 数 学计算机学院 软件与理论教研室（ 313）Discrete MathematicsEmail:Tel:4994019 808* 1第二部分集集 合合 论论Set ,Relation and MappingDate 2第三章 集合、关系与映射r关系即二元关系 ,它是集合直乘积的子集r映射是特殊的二元关系r19世纪末著名德国数学家 康托康托 (G.cantor)r集合已经发展成为数学及其他各学科不可缺少的描述工具成为数学中最为基本的概念r集合论分为两种体系F朴素集合论体系 (康托集合论体系 ).v 康托从抽象原则出发概括出 :满足某性质的个体放在一起组成集合v 隐含矛盾 ,即罗素 (R
2、ussell)悖论 . F公理集合论体系 (属于数理逻辑范畴 )Date 33.1 集合及其运算1. 集合及其表示法p 用大写英文字母 A,B,C, 表示集合并用 xA 表示 x是集合 A中的元素 ,读作 “ x属于 A”用 xA表示 x不是 A中的元素 ,读作 “ x不属于 A”.p 一般 ,集合有两种表示法 :列举法 和 描述元素性质法p 列举法A=a,b,c,d,e; B=书 ,笔记本 ,铅笔 ,课桌 ,黑板 ;C=0,1,-3,6; D=北京 ,天坛 ,故宫 ,地球 ,宇宙 .p 描述元素性质法= x|x是英文字母 ; Z=x|x是整数 ;Date 4集合及其表示法p需要注意以下几点：
3、F集合中的元素各不相同如 1,2,3,4与 1,1,2,3,4,4是相同的集合都是含元素 1,2,3,4的集合F集合中的元素不规定次序如： 1,2,3,4=4,2,3,1.F有些集合的两种表示法能互相转换 ,有些则不能如： x|x是英文字母=a,b,c,d,e,f,g, x,y,z;x|x是非负偶数 =0,2,4,6,8,10,2n,;x|x是实数 不能转换为列举法表示 .Date 5集合及其表示法n 一些常用集合的表示法 :N=x|x是自然数 =0,1,2,n, Z=x|x为整数 =,-3,-2,-1,0,1,2,3,Z+=x|xZx 0=1,2,3,n,Q=x|x是有理数 R=x|x为实数
4、 还有：P表示素数集合O表示奇数集合E表示偶数集合Date 6集合间的包含与相等2.定义 3.1.1.设 A,B为集合，若 B中的元素都是 A中的元素 ,则称B是 A的子集 ,记作 BA,称 A包含 B,或 B包含于 A,并以 B A表示 B不是 A的子集 .即 BA x(x Bx A)B Ax(x Bx A).定义 3.1.2.设 A,B为集合 ,若集合 AB且 AB, 则称 A为 B的真子 集 ,记作 AB.即 AB x(x Ax B) x(x Bx A).例如： 若 A=1,2,4,B=1,2,3,4,5,则 AB, 而且 AB.J 对任意集合 A有 :AA(自反性 )J 对任意集合 A
5、,B,C,若 AB且 BC,则 AC(传递性 )Date 7空集与全集定义 3.1.3.设 A,B为集合 ,若 AB且 BA,则称 A与 B相等 ,记作A=B.定义 3.1.4.称不拥有任何元素的集合为空集 ,记作 .q空集 是任意集合的子集合 ,是任意非空集合的真子集合v 和 的关系是？q空集是任意集合的子集 ,可以形象地说 :是 “ 最小最小 ” 的集合 .但没有最大的集合 .q在讨论某些具体问题时 ,往往使用一个 在相对的意义下 是 “最大 ” 的集合 ”.Date 8空集与全集定义 3.1.5.如果限定所讨论的集合都是某一集合 E的 子集 ,则称 E为全集q 全集是一个相对的概念 ,不
6、同的实际问题可以定义不同的全集 .例如 当被讨论的集合仅仅是 0,2,4,6,6,8时 ,全集可设为 0,2,4,6,8或 x|x是 10以内的自然数 等Date 9集合的幂集3.定义 3.1.6. 设 A为一个集合 ,称由 A的所有子集组成的集合为A的幂集 ,记作 P(A),即 P(A)=X|XA.如： 设 A=1,2,3则 P(A)=,1,2,3,1,2,1,3,2,3,A. 若 |A|=n,则 P(A)的元素个数 |P(A)|=2n. q元素个数有限的集合称 有穷集 ,对其 子集 有一种 编码方法 :设 A=a1,a2,a3则 A2=A010=a2,A5=A101=a1,a3. Date 10
