《离散数学PPT电子教案-第01章 集合论.ppt》由会员分享，可在线阅读，更多相关《离散数学PPT电子教案-第01章 集合论.ppt（46页珍藏版）》请在三一文库上搜索。
1、离 散 数 学,2020年1月29日星期三,2020/1/29,第一篇 预备知识,第一章 集合论,2020/1/29,1.0 内容提要,2020/1/29,1.1 本章学习要求,2020/1/29,1.2 集合,一、集合的概念,集合：是不能精确定义的基本数学概念。通常是由指定范围内的某些特定对象聚集在一起构成的。,指定范围内的每一个对象称为这个集合的元素.,中国所有真皮沙发的聚集,指定范围,特定对象,2020/1/29,二、集合的记法,通常用带(不带)标号的大写字母 A、B、C、.、A1、 B1 、C1 、.、X、Y、Z、.表示 集合； 通常用带（不带）标号的小写字母 a、b、c、.、a1、
2、b1 、c1 、.、x、y、z、.表示 元素。,2020/1/29,固定的符号, 有理数集, 自然数集, 复数集, 实数集, 整数集,2020/1/29,1.2.1 集合的表示方法,集合是由它包含的元素完全确定的，为了表示一个集合，通常有： 枚举法 (显示法) 叙述法（隐式法） 归纳法 递归指定 文氏图,2020/1/29,1、枚举法（显示法）,-列出集合中全部元素或部分元素的方法叫枚举法,例1.2.1 （1）Aa，b，c，d （2）B = 0, 1, 4, 9, 16, , n2, ,适用场景： (1) 仅含有限个元素 (2) 元素之间有明显关系,2020/1/29,例1.2.2 （1）A
3、= x|x是“discrete mathematics”中的所有字母； （2）Z = x|x是一个整数； （3）S = x|x是整数，并且x21 = 0； （4）Q+ = x|x是一个正有理数。,2、叙述法（隐式法）,2020/1/29,2、叙述法（隐式法）,通过刻画集合中元素所具备的某种特性来表示集合的方法称为叙述法（隐式法） 一般表示方法：Px|P(x) 适用场景： 一个集合含有很多或无穷多个元素； 一个集合的元素之间有容易刻画的共同特征,代表元,x所具有的性质p,2020/1/29,1.2.2 集合与元素的关系,元素与集合之间的“属于关系”是“明确”的。 对某个集合A和元素a来说， a属
4、于集合A，记为aA 或者 a不属于集合A，记为aA 两者必居其一且仅居其一。,例如，对元素 2 和集合 ，就有 2 属于 ，即 2， 对元素 -2 和集合 ，就有 -2 不属于 ，即 -2。,2020/1/29,罗素悖论,例 在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些自己不刮脸的人刮脸。那么，谁给这位理发师刮脸？,解：设 Cx|x是不给自己刮脸的人 b 是这位理发师 如 bC，则 bC； 如 bC，则 bC。,2020/1/29,1.2.3 集合与集合的关系,1、互异性 集合中的元素都是不同的，凡是相同的元 素，均视为同一个元素； 1,1,2=1,2
5、2、确定性 能够明确加以“区分的”对象； 3、无序性 集合中的元素是没有顺序的。 2,1=1,2,一、集合的三大特征,2020/1/29,例1.2.6 设A = BASIC, PASCAL, ADA， B = ADA, BASIC, PASCAL， 请判断A和B的关系。 解: 根据集合元素的无序性和外延性原理可得， A = B。,二、外延性原理 AB当且仅当A与B具有相同的元素，否则，AB。,2020/1/29,三、包含和真包含关系,定义1.2.1 设A,B是任意两个集合，如果 B的每个元素都是A的元素，则称B是A的子集合，简称子集， 这时也称 A包含B，或B被A包含，记作 AB 或 BA。
6、称“”或“”为包含关系。 如果B不被A所包含，则记作BA 。,上述包含定义的数学语言描述为： BA 对任意 x，如 xB，则 xA。,显然，对任意集合A，都有 AA。,2020/1/29,例1.2.7,设A = BASIC, PASCAL, ADA， B = ADA, BASIC, PASCAL， 请判断A和B之间的包含关系。 解 根据集合间包含关系的定义知，AB 且AB 。,又从例1.2.6知，集合A = B，于是我们有：,定理1.2.2 设 A、B 是任意两个集合，则 AB，BA A=B,2020/1/29,真包含关系,定义1.2.2 设A,B是任意两个集合，如果 BA 并且 AB 则称B
7、是A的真子集，记作 BA， 称“”为真包含关系 。 如果B不是A的真子集，则记作 BA。,上述真子集的数学语言描述为： BA 对任意 x，如 xB，则 xA, 并且 yA， 但是 yB,2020/1/29,判断下列集合之间是否具有真包含关系。 （1）a, b 和 a, b, c, d； （2）a, b, c, d和a, b, c, d。,解 根据真子集的定义，有 （1） a, b a, b, c, d； （2）因为a, b, c, da, b, c, d， 所以 a, b, c, d 不是 a, b, c, d 的真子集。,例1.2.8,2020/1/29,例1.2.9,设A = a是一个集合
8、，B = a, a，试问 AB和AB 同时成立吗？ A = a，aB AB成立； A = a，aB AB成立。 解： AB和AB同时成立。,分析,2020/1/29,1.2.4 几个特殊集合,定义1.2.3 不含任何元素的集合叫做空集，记作。 空集可以符号化为 = x|xx。,1、空集,定理1.2.3 （1）空集是一切集合的子集； （2）空集是唯一的。,2020/1/29,定义1.2.4 在一个相对固定的范围内，包含此范围内所有元素的集合，称为全集或论集，用 U 或 E 表示。 用文氏图描述如下:,U,2、全集,2020/1/29,例1.2.12,（1）在立体几何中，全集是由空间的全体点组成；
9、 （2）在我国的人口普查中，全集是由我国所有人组成。,定理1.2.5 全集是相对唯一的.,2020/1/29,集合A中元素的数目称为集合A的基数，记为|A|。 如|A|是有限的，则称集合A为有限集， 如|A|是无限的，则称集合A为无限集。,例1.2.13 求下列集合的基数。 （1）A = ； （2）B = ； （3）C = a, b, c；（4）D = a, b, c。 解： |A| = 0，|B| = 1， |C| = 3，|D| = 2。,有限集和无限集,2020/1/29,m元子集,定义1.2.6 如果一个集合A含有n个元素，则称集合A为n元集，称A的含有m个(0mn)元素的子集为A的m
10、元子集。,2020/1/29,幂集,定义1.2.7 设A为任意集合，把A的所有不同子集 构成的集合叫做A的幂集，记为P(A)或2A ， 其符号化表示为 P(A) x | xA 。,2020/1/29,例1.2.15 计算下列幂集,（1）P()；（2）P()；（3）P( a, b,c )。 解 （1）P() = ； （2）P() = , ； （3）P(a,b,c)= , a, b,c, a,b,c 。,显然，若集合有个元素，则集合共有2|A|个子集， 即： |P(A)| 2|A|。,2020/1/29,1.2.5 集合的运算,定义1.2.8 设A、B是两个集合， (1)并集 AB=x|xA或xB
11、 (2)交集 AB=x|xA且xB (3)差集 A-B=x|xA且xB (4)补集 =U-A=x|xU且xA (5)对称差集 AB= x | (xA)且(xB) 或 (xB)且(xA) ,2020/1/29,推广,A1A2A3An,=x|(xA1) 或 (xA2) 或 或 (xAn) ,A1A2A3An, x | (xA1) 且 (xA2) 且 且 (xAn) ,当n无限增大时，可以记为：,A1A2A3, A1A2A3,2020/1/29,定理1.2.5,1.等幂律:=；=； 2.交换律:=;= 3.结合律:()=()； ()=()； 4.恒等律:=； =； 5.零 律:=； =； 6.分配律
12、:()=()() ()=()() 7.吸收律:A(AB)=A; A(AB)=A；,2020/1/29,定理1.2.5(续）,8.A - A = ； 9.A - B = A - (AB)； 10.(A - B) - C = A - (BC)； 11.A(B-A) = AB；12.A - B =A ； 13.否定律： ； 14.DeMorgan律： ； 15.矛盾律： A ； 16.排中律：A U。,2020/1/29,1.3 无限集,质变,无限集合无法用确切的个数来描述。,有限集,无限集,量变,2020/1/29,1.3.1 可数集合与不可数集合,问题 1,2,3, 与 12,22,32, 哪个
13、集合的元素更多？ 引入：自然数集合 二十世纪初，集合成为数学的基本概念之后，由冯诺依曼（Von Neumann）用序列 ，, ，, , , ， 来定义自然数。,2020/1/29,自然数集合的定义, ， 若 n ，则n: nn 。 也即：0:， 1:0， 2:,0,1 . n:0,1,2,3,.n-1 . 故 0, 1, 2, 3, ., n, . ,2020/1/29,等势的概念,定义1.3.1 设A，B是两个集合，若在A，B之间存在 1-1对应的关系： ：AB 则称A与B是等势的，记为：AB。 也称集合A与B等势。,注意： 若AB，则 AB。,若AB， 则 AB,（）,（）,2020/1/
14、29,可数集合(可列集）,定义1.3.2 凡是与自然数集合等势的集合，统称为 可数集合(可列集)。记为： 0 (读作阿列夫零) 。,例1.3.1 下列集合都是可数集合： 1) O+x|x ，x是奇数 ; 2) P x|x ，x是素数 ; 3) 有理数集合 。,2020/1/29,解：1）,在O+与N之间建立1-1对应的关系 f：NO+ 如下： N . . . . O+ . 2n+1 . 所以，O+是可数集合。,2020/1/29,3）,-3/118 -2/15 -1/14 0/10 1/11 2/110 -3/111 -3/217 -2/2 -1/23 0/2 1/22 2/2 3/212 -
15、3/3 -2/36 -1/37 0/3 1/38 2/39 3/3 -3/416 -2/4 -1/415 0/4 1/414 2/4 3/413,所以，有理数集合必是可数集合。,2020/1/29,定理1.3.1,两个有限集合等势当且仅当它们有相同的元素个数； 有限集合不和其任何真子集等势； 可数集合可以和其可数的真子集等势。,2020/1/29,不可数集合,定义1.3.3 开区间(0,1)称为不可数集合，其基数设为 (读作阿列夫)；凡是与开区间(0,1)等势的集合都是不可数集合。,例1.3.2 (1) 闭区间0,1 是不可数集合； (2) 实数集合R是不可数集合。,2020/1/29,例1.
16、4.4 在20个大学生中，有10人爱好音乐，有8人爱好美术，有6人既爱好音乐又爱好美术。问不爱好音乐又不爱好美术的学生有多少个？ 解 设所有的大学生的集合为U，爱好音乐的学生集合为A，爱好美术的学生集合为B，既爱好音乐和又爱好美术的学生组成的集合为 ，则既不爱好音乐又不爱好美术的学生组成的集合为 。 如右图：,1.4 集合的应用,2020/1/29,例1.4.4解（续）,根据已知有|U| = 20，|A| = 10，|B| = 8， | | = 6 又因为，| | = |A|+|B| - | | = 10 + 8 - 6 = 12 从而，| | = |U| - | | = 20 - 12 =
17、8 即不爱好音乐又不爱好美术的学生有8个。,2020/1/29,1.5 本章总结,1、与集合相关的概念和特殊集合：集合的定义、集合的表示、属于和不属于、子集、真子集、包含和真包含、幂集、空集、全集、基数、有限集、无限集等； 2、与集合运算相关的概念和定理：集合的交、并、差、补和对称差等五种运算的定义及相关定理。,2020/1/29,习题类型,（1）基本概念题：涉及集合的表示； （2）判断题：涉及元素与集合、集合与集合间的关系； （3）计算题：涉及集合的运算和幂集的计算； （4）证明题：涉及集合相等以及集合间包含关系的证明。,2020/1/29,作业,第20-22页 7(3)(5)(6)(7), 13, 30 思考题: 31 预习: 第2章 计数问题,2020/1/29,7(3)(5)(6)(7), 13, 30, 31,7. (3) 1,2,3; (5) ,2,2; (6) a,a; (7) ,a,b. 13. 错误的是 (2) ; (6) ; (7) ; (12) ,; (13) a a. 30. (1) BC-A; (2) U-A BC. 31. 求从1到1000的整数中不能被5, 6和8中任何一个整除的整数的个数. ( 600 ),