离散数学集合2.ppt

第3讲 集合的概念与运算® 1. 集合的概念® 2. 集合之间的关系® 3. 集合的运算® 4. 文氏图、容斥原理2024/9/71集合论(set theory)®十九世纪数学最伟大成就之一®集合论体系®朴素(naive)集合论®公理(axiomatic)集合论®创始人康托(Cantor)Georg Ferdinand Philip Cantor 1845 ~ 1918德国数学家, 集合论创始人. 2024/9/72 什么是集合(set)®集合：不能精确定义一些对象的整体就构成集合，这些对象称为元素(element)或成员(member)®用大写英文字母A,B,C,…表示集合®用小写英文字母a,b,c,…表示元素®aA：表示a是A的元素，读作“a属于A” aA：表示a不是A的元素，读作“a不属于A”2024/9/73集合的表示®列举法®描述法®特征函数法2024/9/74列举法(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}2024/9/75多重集(multiple set)®多重集: 允许元素多次重复出现的集合®元素的重复度: 元素的出现次数(0). ®例如: 设A={a,a,b,b,c}是多重集 元素a,b的重复度是2 元素c的重复度是1 元素d的重复度是02024/9/76描述法(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}2024/9/77描述法（续）®两种表示法可以互相转化，例如E={2,4,6,8,…}={x|x>0且x是偶数} ={x|x=2(k+1)，k为非负整数}={2(k+1) | k为非负整数}® 有些书在描述法中用:代替|, 例如{2(k+1): k为非负整数}2024/9/78特征函数法(characteristic function)®集合A的特征函数是A (x): 1，若xA A (x) = 0，若xA® 对多重集, A (x)=x在A中的重复度2024/9/79常用的数集合®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)集合2024/9/710集合之间的关系®子集、相等、真子集 ®空集、全集®幂集、n元集、有限集®集族2024/9/711子集(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)2024/9/712相等(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) (等值式)2024/9/713包含()的性质®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) (析取三段论) #2024/9/714包含()的性质(续)®若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. #2024/9/715真子集(proper subset) ®真子集: B真包含A:AB  AB  AB ®AB  (AB  AB) (定义) (AB)  (A=B) (德•摩根律) x(xAxB)  (A=B) (定义)2024/9/716真包含()的性质®AA 证明: A  A AA  AA  10  0. #®若AB,则 BA 证明: (反证) 设BA, 则 AB  AB  AB  AB (化简) BA  BA  BA  BA 所以 AB  BA  A=B (=定义)但是 AB  AB  AB  AB (化简) 矛盾! #2024/9/717真包含()的性质(续)®若AB,且BC, 则AC证明: AB  AB  AB  AB (化简), 同理 BC  BC, 所以AC. 假设A=C, 则BCBA, 又AB, 故A=B, 此与AB矛盾, 所以AC. 所以, AC. #2024/9/718空集(empty set)®空集:没有任何元素的集合是空集,记作®例如, {xR|x2 +1=0}®定理1: 对任意集合A, A 证明: Ax(xxA) x(0xA)1. #®推论: 空集是唯一的. 证明: 设1与2都是空集, 则 12  21  1=2 . #2024/9/719全集®全集: 如果限定所讨论的集合都是某个集合的子集,则称这个集合是全集,记作E®全集是相对的, 视情况而定, 因此不唯一.例如, 讨论(a,b)区间里的实数性质时, 可以选E=(a,b), E=[a,b), E=(a,b], E=[a,b], E=(a,+),E=(-,+)等2024/9/720幂集(power set)®幂集: A的全体子集组成的集合,称为A的幂集,记作P(A)P(A)={x|xA}®注意: xP(A)  xA®例子: A={a,b}, P(A)={,{a},{b},{a,b}}. #2024/9/721n元集(n-set)® n元集: 含有n个元素的集合称为n元集®0元集: ®1元集(或单元集),如{a}, {b}, {}, {{}},…®|A|: 表示集合A中的元素个数, A是n元集  |A|=n®有限集 (fimite set): |A|是有限数, |A|<, 也叫有穷集2024/9/722幂集(续)®定理: |A|=n  |P(A)|=2n. 证明: 每个子集对应一种染色,一共有2n 种不同染色. #A{a1} a1a2a3………an{a1,a3} … …2024/9/723集族(set family)®集族: 由集合构成的集合. 幂集都是集族.®指标集(index set): 设A是集族, 若A={A|S}, 则S称为A的指标集. S中的元素与A中的集合是一一对应的. 也记作A={A|S}={A}S®例1: {A1,A2}的指标集是{1,2}2024/9/724集族(举例)®例2: An={xN|x=n}, A0={0}, A1={1},… {An|nN}={{0},{1},{2},…} {An|nN}的指标集是N®例3: 设R+={xR|x>0}, Aa=[0,a), {Aa|aR+ }的指标集是R+0a2024/9/725集合之间的运算®并集、交集®相对补集、对称差、绝对补®广义并集、广义交集2024/9/726并集(union)®并集: AB = { x | (xA)  (xB) }xAB  (xA)  (xB)®初级并: 2024/9/727并集(举例)®例1: 设An={xR|n-1xn},n=1,2,…,10,则®例2: 设An={xR|0x1/n},n=1,2,…,则2024/9/728交集(intersection)®交集: AB = { x | (xA)  (xB) }xAB  (xA)  (xB)®初级交: 2024/9/729交集(举例)®例1: 设An={xR|n-1xn},n=1,2,…,10,则®例2: 设An={xR|0x1/n},n=1,2,…,则2024/9/730不相交(disjoint)®不相交: AB=®互不相交: 设A1,A2,…是可数多个集合, 若对于任意的ij, 都有AiAj=, 则说它们互不相交®例: 设 An={xR|n-1