北大集合论与图论.pptxVIP

第3讲 集合的概念与运算北京大学 1. 集合的概念 2. 集合之间的关系 3. 集合的运算 4. 文氏图、容斥原理《集合论与图论》第3讲集合论(set theory)十九世纪数学最伟大成就之一集合论体系朴素(naive)集合论公理(axiomatic)集合论创始人康托(Cantor)Georg Ferdinand Philip Cantor 1845 ~ 1918德国数学家, 集合论创始人. 《集合论与图论》第3讲 什么是集合(set)集合：不能精确定义。一些对象的整体就构成集合，这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,…表示集合用小写英文字母a,b,c,…表示元素a?A：表示a是A的元素，读作“a属于A” a?A：表示a不是A的元素，读作“a不属于A”《集合论与图论》第3讲集合的表示列举法描述法特征函数法《集合论与图论》第3讲列举法(roster)列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来，例如A={a,b,c,d,…,x,y,z} B={0,1,2,3,4,5,6,7,8,9}集合中的元素不规定顺序C={2,1}={1,2}集合中的元素各不相同(多重集除外)C={2,1,1,2}={2,1}《集合论与图论》第3讲多重集(multiple set)多重集: 允许元素多次重复出现的集合元素的重复度: 元素的出现次数(?0). 例如: 设A={a,a,b,b,c}是多重集 元素a,b的重复度是2 元素c的重复度是1 元素d的重复度是0《集合论与图论》第3讲描述法(defining predicate)用谓词P(x)表示x具有性质P ，用{x|P(x)}表示具有性质 P 的集合，例如P1 (x): x是英文字母A={x|P1 (x)}={x| x是英文字母}={a,b,c,d,…,x,y,z} P2 (x): x是十进制数字B={x|P2(x)}= {x|x是十进制数字} ={0,1,2,3,4,5,6,7,8,9}《集合论与图论》第3讲描述法（续）两种表示法可以互相转化，例如E={2,4,6,8,…}={x|x0且x是偶数} ={x|x=2(k+1)，k为非负整数}={2(k+1) | k为非负整数} 有些书在描述法中用:代替|, 例如{2(k+1): k为非负整数}《集合论与图论》第3讲特征函数法(characteristic function)集合A的特征函数是?A (x): 1，若x?A ?A (x) = 0，若x?A 对多重集, ?A (x)=x在A中的重复度《集合论与图论》第3讲常用的数集合N：自然数(natural numbers)集合N={0,1,2,3,…}Z：整数(integers)集合Z={0,?1,?2,…}={…,-2,-1,0,1,2,…}Q：有理数(rational numbers)集合R：实数(real numbers)集合C：复数(complex numbers)集合《集合论与图论》第3讲集合之间的关系子集、相等、真子集 空集、全集幂集、n元集、有限集集族《集合论与图论》第3讲子集(subset) B包含于A, A包含B:B?A ? ?x(x?B?x?A)B不是A的子集: B?A ? ?x(x?B?x?A)??x(x?B?x?A)??x?(?x?B?x?A) ??x(x?B??x?A)??x(x?B?x?A)《集合论与图论》第3讲相等(equal)相等:A=B ? A?B ? B?A ? ?x(x?A?x?B) A=B ? A?B?B?A (=定义)??x(x?A?x?B)??x(x?B?x?A) (?定义)??x((x?A?x?B)?(x?B?x?A))(量词分配)??x(x?A?x?B) (?等值式)《集合论与图论》第3讲包含(?)的性质A?A 证明:A?A??x(x?A?x?A) ?1若A?B,且A?B,则 B?A 证明:A?B ? ?(A=B) ? ?(A?B?B?A) (定义) ??(A?B) ? ?(B?A) (德?摩根律) A?B (已知) ??B?A (即B?A) (析取三段论)#《集合论与图论》第3讲包含(?)的性质(续)若A?B,且B?C, 则A?C证明:A?B ? ?x(x?A?x?B) ?x, x?A ? x?B (A?B) ? x?C (B?C) ? ?x(x?A?x?C), 即A?C. #《集合论与图论》第3讲真子集(proper subset) 真子集: B真包含A:A?B ? A?B ? A?B A?B ? ?(A?B ? A?B) (?定义)? ?(A?B) ? (A=B) (德?摩根律)? ?