第一章 集 合 1. 集合的概念及其表示 2. 集合之间的关系 3. 集合的运算 4. 容斥原理.

Presentation on theme: "第一章 集 合 1. 集合的概念及其表示 2. 集合之间的关系 3. 集合的运算 4. 容斥原理."— Presentation transcript:

1 第一章 集 合 1. 集合的概念及其表示 2. 集合之间的关系 3. 集合的运算 4. 容斥原理

2 本章学习目标 通过本章的学习，应达到如下目标： 深入理解掌握集合的概念和不同的表示方法； 理解集合间的关系和特殊集合，包括幂集等；
熟练掌握集合的基本运算（交、并、补、差、对称差等）；理解集合运算的规律和主要证明方法； 了解集合的图形表示法，能够借助文氏图直观表示复杂的集合；

3 1.1 集合论(set theory) 十九世纪数学最伟大成就之一 集合论体系 创始人康托(Cantor) 朴素(naive)集合论
公理(axiomatic)集合论（蔡梅罗(Zermelo ) ) 创始人康托(Cantor) 公理化集合论: 1908年另一个德国数学家蔡梅罗(Zermelo)建立了集合论的抽象公理系统。 Georg Ferdinand Philip Cantor ~ 1918 德国数学家, 集合论创始人。他在这一领域的贡献包括实数集合不可数性的发现。

4 什么是集合(set) 集合：是一种原始概念，不能精确定义。一些具有某种特点的对象的整体就构成集合，这些对象称为元素(element)或成员(member)。 用大写英文字母A,B,C,…表示集合 用小写英文字母a,b,c,…表示元素 aA：表示a是A的元素，读作“a属于A” aA：表示a不是A的元素，读作“a不属于A” 的左边是元素，右边是集合。 康托: “凡是在我们的感觉或思维中可以明确区分的对象物，把它们看成是一个整体，这个整体，我们就称它是集合”

5 什么是集合(set)（续） 例 ： (1) 偶素数集合{2}, 称为单元集。 (2) 二进制的基数集合{0, 1}。
(3) 英文字母(大写和小写)的集合。 (4) C#语言的基本字符构成一个字符集。 (5) 计算机主存的全部存储单元集合。 (6) 全体实数的集合。 (7) 广工全体师生的集合。

6 集合的性质1（外延 (extension) 公理）
1. 外延 (extension) 公理--两个集合A和B相等的充分必要条件是它们有相同的元素。 I：互异性: 一个集合的各元素是可以互相区分开的, 即每一元素在一个集合中只出现一次。 II：无序性: 集合中元素排列次序无关紧要, 即集合表示形式的不唯一性。例：{a, b} = {b, a} III. 确定性：任一元素是否属于一个集合, 回答是确定的。 两个集合A和B相等的充分必要条件是它们由相同的元素组成。

7 集合的性质2（正则 (regularity)公理）
3. 对任何集合S, 有{S}  S；只能说 S {S}，不能说S={S}。（正则 (regularity) 公理的推论） 从而规定了集合{S}与 S的不同层次性。 说明： 1.集合与其成员是两个截然不同的概念, 集合的元素可以是任何具体或抽象事物, 包括别的集合, 但不能是本集合自身。 2.先有成员后才形成集合, 所以一个正在形成中的集合并不能作为一个实体充当本集合的成员。 {S}：以S为元素的集合：复合的集合。

8 1.2 数的集合表示 N：自然数(natural numbers)集合， N={0,1,2,3,…}
Z：整数(integers)集合， Z={0,1,2,…}={…,-2,-1,0,1,2,…} Q：有理数(整数商Quotient : i/j, j  0) R：实数(Real numbers)集合 C：复数(complex numbers)集合 P：素数或质数 (Prime)集合 下面给出本书中几个常见集合的表示符号以方便后面的引用。

9 1.3 集合的表示 列举法（枚举法） 描述法（特征法）

10 1.列举法(roster) 列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来，例如 A={a,b,c,d,…,x,y,z}
集合中的元素不规定顺序。 C={2,1}={1,2} 集合中的元素各不相同。 C={2,1,1,2}={2,1}

11 用列举法表示集合并不总是可能的。 例如, 区间[0, 1]中的所有实数的集合就不能用这种方法给出。 从计算机的观点看, 列举法是一种“静态”表示法, 若把全部列举的数据都存储在计算机中, 那将占用大量的存储空间。

12 2.描述法(defining predicate)
也称作特征法。以某个小写英文字母表示该集合中的任意一个元素，并指出该类元素的共同特征。 例 : 正奇数集合 Odd = {m | m=2n + 1且nN}。 例 : [0, 1]上的所有连续函数所形成的集合可记成 : C[0, 1] = {f (x) | f (x)在[0, 1]上连续}。

13 描述法(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}

14 ={x|x>0且x是偶数} //描述法
描述法（续） 两种表示法可以互相转化，例如 E={2,4,6,8,…} //列举法 ={x|x>0且x是偶数} //描述法 ={x|x=2(k+1)，k为非负整数} ={2(k+1) | k为非负整数} 有些书在列举法中用:代替|, 例如 {2(k+1): k为非负整数}

15 1.4 集合之间的关系 子集、真子集（包含关系与相等关系） 空集、全集 幂集

16 集合的包含关系：子集与真子集 子集：设A和B是两个集合, 若A中的每一个元素都是B的元素, 则称A是B的子集(subset), 也称B包含(include)A, 记作A  B(或B  A)。 真子集：若A为B的子集, 且A  B, 则称A为B的真子集(proper subset), 或称B真包含A, 记作A  B, B称为A的超集(superset)。 集合A和集合B无任何关系。

17 子集、真子集(举例) 设A={England国家足球队全体成员} B={England国家足球队前锋成员} C={欧文, 鲁尼}
则有 B  A, C  B, C  A 也有 B  A, C  B, C  A

18 子集(举例) 设A={a,b,c},B={a,b,c,d},C={a,b},则 AB, CA, CB， C  AB a b c d
e f g h i j … A … B … … C

19 真子集(举例) 例 ：N  Q  R  C。 例 ：台湾人都是中国人, 台湾人真包含于中国人, 即 {台湾人}  {中国人}。
“”与“”“”的区别: 符号“”表示元素与集合间的隶属关系; 例： 1N /* 1{N}，正确与否？*/ “” “”是集合之间的包含关系, “” “”的两边均是集合, 地位平等。 集合之间可以没有任何关系。

20 包含关系的性质 设A、B、C为3个集合, 由定义可知集合的包含关系有如下性质： (1) A  A。 (自反性)
(2) 若A  B且B  A, 则A = B。(反对称性) (3) 若A  B且B  C, 则A  C。(传递性)

21 “”传递性证明 若AB,且BC, 则AC 证明: 因为 AB ，所以对于任意属于A的元素x，都有xB； 又因为BC，则xC；
 任何属于A的元素都属于C。即： AC

22 “”传递性证明 若AB,且BC, 则AC 证明: 要证AC，即证AC并且AC 首先证明AC
AB  AB 并且 AB  AB 同理 BC  BC, 所以AC. 反证法证明AC 假设A=C, 则BCBA, 又AB, 故A=B, 此与AB矛盾, 所以A=C不成立，因而AC成立. 所以, AC.

23 集合的相等关系 相等关系定义1：由外延公理, 集合A与集合B的元素完全相同时, A = B。
相等关系判定定理： 设A和B是任意两个集合, 若A  B 且 B  A, 则称A与B相等, 记作 A = B。 由外延定理证明两个集合相等是困难的。

24 集合的相等关系有如下性质： (1) A = A。 (自反性) (2) 若A = B, 则B = A。 (对称性) (3) 若A = B且B = C, 则A = C。 (传递性) 两个相等的集合并不意味着它们是用同样的方式定义的。 例 ：设集合A是方程 x2 – x = 0 的解的集合, A = {x | x2 – x = 0}; x2 – x = 0 的解为0和1 B = {0, 1}; 则 A = B。

25 空集(empty set) 空集:不包含任何元素的集合称为空集(empty set), 记作, 或{ }。
例 ：方程 x2 + 1 = 0 的实根集合是空集。 这说明空集是客观存在的。 空集的引入, 可以使许多问题的叙述得到简化。 下列命题成立：   ；  {}

26 例1 ：判断下列命题的真假: (1)    (2)    (3)   {} (4)   {} Solution ：(2)为假; 其余均为真。 例2： 列出 B = {}和 C = 的全部(真)子集。 Solution ：   {} 且 {}  {}； B有两个子集:  和 {} ； B只有一个真子集 : 。   C, 所以C只有一个子集, 没有真子集。 例3:是否存在集合A和B, 使得 AB 且 A  B。 Solution ：存在。例 A = {a}, B = {a, {a}}。

27 空集的性质 （1） 空集是一切集合的子集。 （2） 空集是唯一的。 proof 若存在空集合 1和2, 由（1）知
1  2 和 2  1, 根据集合相等的定义 1 = 2。 对于每个非空集合S, 至少有两个不同的子集, 即   S 和 S  S。 我们称和S自身是S的平凡子集。

28 全集 全集: 如果限定所讨论的集合A都是某个集合U的子集,则称集合U是全集。某些书上也记作E。
全集是相对的, 视情况而定, 因此不唯一.全集只包含与讨论有关的所有对象, 并不一定包含一切事物。 例：讨论(a,b)区间里的实数性质时, 可以选U=(a,b), U=[a,b), U=(a,b], U=[a,b], U=(a,+),U=(-,+)等

29 幂集(power set) 幂集: 设A是集合，A的全体子集组成的集合,称为A的幂集,记作P(A)，或者2A 。A称作P(A)的指标集。
P(A)={x|xA} 注意: xP(A)  xA。也就是说，P(A)中的每一个元素都是集合，这些集合中的元素全部都只能来自集合A。 例：A={a,b}, P(A)={,{a},{b},{a,b}}. A的全体子集是指：A中的全部元素的组合而成的所有集合加上空集。

30 集合的基 例：A={a,b}, P(A)={,{a},{b},{a,b}}. 基：也称作“势”。集合A中元素的个数。
基数是有限数的集合称为有限集, 否则称为无限(infinite)集。一般仅对有限集讨论其基的值。 定理：设A是有限集，且|A|=n，则A的幂集的基|P(A)|= 2n 。 例：A={a,b}, P(A)={,{a},{b},{a,b}}. |A|=2，则|P(A)|=4

31 给定一个有限集, 要保证不重复和不遗漏地写出它的全部子集, 办法之一就是将子集按基数由小到大地分类, 相同基数类的子集再按字母数字顺序逐个地写出。
例:求出集合S = {a, b, c}的所有子集。n=3 Solution: 0元子集, 只有一个C30个: ; 1元子集, 有C31个: {a}, {b}, {c}； 2元子集, 有C32个: {a, b}, {a, c}, {b, c}； 3元子集, 有C33个: {a, b, c} 。 共有子集数: C30+C31+C32+C33= (1+1)3 = 23 = 8

32 子集与二进制数 通过建立子集与二进制数的关系，求出集合的所有子集。 A={a1, a2, …, an}, |A|=n a1 a2 a3 …
0/1 1 B1010…01 = {a1, a3 , an} B0110…00 = {a2, a3} A的子集与n位二进制数一一对应

33 子集与二进制数（举例） a b c 子集 B 1 {c} {b} {b,c} {a} {a,c} {a,b} {a,b,c} 
例：设A = {a, b, c}, |A| = 3, P(A) = { B0= B000 = , B1= B001 ={c}, B2= B010 ={b}, B3= B011 ={b,c}, B4= B100 ={a} , B5= B101 ={a,c} B6= B110 ={a,b} , B7= B111 = a,b,c} } a b c 子集 B  1 {c} {b} {b,c} {a} {a,c} {a,b} {a,b,c}

34 若|A|=n，A的任一子集都可用n位二进制数中的某个数来表示;反之, 若给出2n －1中的任何一个值, 就能够确定A相应的子集。
我们只用下标来确定子集的各元素, 而字母B则是无关紧要的。 若使用十进制数作为子集的下标, 则转换为A的基数位数的二进制数后同样处理。

35 例 : 设S = {a1, a2,. , a8}, 由B17 和B31所表示的S的子集各是什么
例 : 设S = {a1, a2, ..., a8}, 由B17 和B31所表示的S的子集各是什么? 应如何表示子集{a1, a8}和{a3, a8, a7}? 解 S有28 = 256个不同的子集, 可表示为B0, B1, B2, B3, … , B255, 二进制下标有8位. B17 = B = {a4, a8} B31 = B = {a4, a5, a6, a7 , a8} {a1, a8} = B = B129 {a3, a8, a7} = B = B35。

36 空集的幂集举例 1. ||=0，|P()|=20=1; P() = 。 2. |{}|=1，|P({})|=21=2;
解释：  {}, 但   {},   {}。  表示空集, 其中没有任何元素； {} 表示集合族, 它有唯一的一个集合元素

37 幂集的性质 A  B成立当且仅当P(A)  P(B) (2) P(A∩B) = P(A)∩P(B)
(4) P(A’)  (P(A))’

38 重点掌握 集合的概念及表示方法 子集、真子集、空集、全集、幂集等概念

39 子集与二进制数（练习） 设A = {a, b, c，d}，利用子集与二进制数的关系，求P(A).

40 练习题

41 作业 P 5：3、6 举一个具体的例子说明什么是罗素悖论？罗素悖论对集合论的影响？