离散数学教案1

《离散数学教案1》由会员分享，可在线阅读，更多相关《离散数学教案1（50页珍藏版）》请在金锄头文库上搜索。

1、第一篇预备知识第一章集合论1.0内容提要集合的概念集合的概念1集合的表示方法集合的表示方法2集合间的关系集合间的关系3集合的运算集合的运算4无限集合无限集合5集合的概念集合的概念1集合的表示方法集合的表示方法2特殊集合特殊集合51.1本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 集合的概念集合的概念及集合间关系及集合间关系2 2 集合的表示集合的表示3 3 集合运算及集合运算及定律定律4 4 幂集幂集P(A)P(A)31 1 集合的递归集合的递归指定法表示指定法表示2 2 了解无限集了解无限集的基本概念的基本概念21 1 集合的归纳集合的归纳法表示法表示2 2 集合的对称集合的

2、对称差运算差运算 1.2集合一、集合的概念集合集合（SETSET）由指定范围内的某些特定对象由指定范围内的某些特定对象聚集在一起构成。聚集在一起构成。指定范围内的每一个对象称为这个指定范围内的每一个对象称为这个集合的元素集合的元素(element)(element)中国中国所有真皮沙发所有真皮沙发的聚集的聚集指定指定范围范围特定对特定对象象二、集合的记法通常用带(不带)标号的大写字母A、B、C、.、A1、B1、C1、.、X、Y、Z、.表示集合；通常用带（不带）标号的小写字母a、b、c、.、a1、b1、c1、.、x、y、z、.表示元素。固定的符号0,1,2,自然数集合自然数集合N,-2,-1,0

3、,1,2,整数集合整数集合Zp/q,p,q是整数，且是整数，且q0有理数集合有理数集合Q实数集合实数集合R复数集合复数集合C1.2.1集合的表示方法集合是由它包含的元素完全确定的，为了表示一个集合，通常有：枚举法隐式法（叙述法）归纳法递归指定文氏图1、枚举法（显示法）-列出集合中全部元素或部分元素的方法叫枚举法例例1.2.11.2.1 （1 1 1 1）A A A Aaaaa，b b b b，c c c c，dddd （2 2 2 2）B = 0, 1, 4, 9, 16, B = 0, 1, 4, 9, 16, B = 0, 1, 4, 9, 16, B = 0, 1, 4, 9, 16,

4、, n, n, n, n2 2 2 2, , , , 适用场景：适用场景：u一个集合仅含有限个元素一个集合仅含有限个元素u一个集合的元素之间有明显关系一个集合的元素之间有明显关系枚举法的优缺点是一种显式表示法优点：具有透明性缺点：在表示具有某种特性的集合或集合中元素过多时受到了一定的局限，而且，从计算机的角度看，显式法是一种“静态”表示法，如果一下子将这么多的“数据”输入到计算机中去，那将占据大量的“内存”。2、隐式法（叙述法）通过刻画集合中元素所具备的某种特性来表示集合的方法称为叙述法（隐式法）一般表示方法：Px|P(x)适用场景：一个集合含有很多或无穷多个元素；一个集合的元素之间有容易刻画

5、的共同特征其突出优点是原则上不要求列出集合中全部元素，而只要给出该集合中元素的特性。代表元代表元X X所具有的所具有的性质性质p p例1.2.2（1）A=x|x是“discretemathematics”中的所有字母；（2）Z=x|x是一个整数；（3）S=x|x是整数，并且x21=0；（4）Q+=x|x是一个正有理数。3、归纳法归纳法是通过归纳定义集合，主要由三部分组成：第一部分：基础。指出某些最基本的元素属于某集合；第二部分：归纳。指出由基本元素造出新元素的方法；第三部分：极小性。指出该集合的界限。注意：第一部分注意：第一部分和和第二部分第二部分指出一个集合指出一个集合至少包括至少包括的元素

6、的元素，第三部分第三部分指出一个集合指出一个集合至多要包含的元素至多要包含的元素例1.2.3集合A按如下方式定义：（1）0和1都是A中的元素；（2）如果a,b是A中的元素，则ab,ba也是A中的元素；（3）有限次使用(1)、(2)后所得到的字符串都是A中的元素。试指出其定义方式。并举出集合A中的3个元素4、递归指定集合通过计算规则定义集合中的元素例例1.2.41.2.4 设设 a a0 0 1 1， a ai+1 i+1 2a2ai i （i i 0 0） 定义定义S Saa0 0 ，a a1 1 ，a a2 2 ，. a ak k | k| k 0 0 ，试写出集合试写出集合S S中的所有元

7、素。中的所有元素。 5、文氏图解法文氏图解法是一种利用平面上点的集合作成的对集合的图解。一般用平面上的圆形或方形表示一个集合。AA1.2.2集合与元素的关系元素与集合之间的“属于关系”是“明确”的。对某个集合A和元素a来说，a属于集合A，记为aA或者a不属于集合A，记为aA两者必居其一且仅居其一。例如，对元素例如，对元素2 2和和N N，就有，就有2 2属于属于N N，即，即2 2 N N，对元素对元素-2-2和和N N，就有，就有-2-2不属于不属于N N，即，即- -2 2 N N。罗素悖论例在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些自己不刮脸的人

8、刮脸。那么，谁给这位理发师刮脸？解解：设设C Cx|xx|x是不给自己刮脸的人是不给自己刮脸的人 b b是这位理发师是这位理发师如如 b b C C，则则 b b C C；如如 b b C C，则则 b b C C。1.2.3集合与集合的关系1、互异性集合中的元素都是不同的，凡是相同的元素，均视为同一个元素；1,1,2=1,22、确定性能够明确加以“区分的”对象；3、无序性集合中的元素是没有顺序的。2,1=1,2一、集合的三大特征例1.2.5设设E = E = x|(xx|(x - 1)(x - 2)(x - 3) = 0, - 1)(x - 2)(x - 3) = 0, xRxR F F =

9、 = x|(xx|(x Z Z+ +) )且且(x(x2 212)12)。试指出集合试指出集合E E和和F F中的元素。中的元素。解解 集合集合E = 1, 2, 3E = 1, 2, 3，F = 1, 2, 3F = 1, 2, 3。显然，集合显然，集合E, FE, F中的中的元素完全相同元素完全相同，我们称，我们称这样的这样的两个集合相等两个集合相等 二、外延性原理二、外延性原理二、外延性原理二、外延性原理A AB B当且仅当当且仅当A A与与B B具有相同的元素，否则，具有相同的元素，否则，A A B B。例1.2.6设A=BASIC,PASCAL,ADA，B=ADA,BASIC,PAS

10、CAL，请判断A和B的关系。解根据集合元素的无序性和外延性原理可得，A=B。因为集合A=B，所以B中的每个元素都是A中的元素，我们称集合A包含集合B。三、包含和真包含关系定义1.2.1设A,B是任意两个集合，如果B的每个元素都是A的元素，则称B是A的子集合，简称子集(Subset)，这时也称A包含B，或B被A包含，记作AB或BA，称“”或“”为包含关系(InclusionRelation)。如果B不被A所包含，则记作BA。上述包含定义的数学语言描述为：上述包含定义的数学语言描述为： B B A A对任意对任意x x，如，如x x B B，则，则x x A A。显然，显然，显然，显然，对任意集合

11、对任意集合对任意集合对任意集合A A A A，都有，都有，都有，都有A A A A A A A A。例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，BAA=B真包含关系定义1.2.2设A,B是任意两个集合，如果BA并且AB,则称B是A的真子集(ProperSubset)，记作BA，称“”为真包含关系(ProperlyInclusionRelation)。如果B不是A的真子集，则记作BA。上述真子

12、集的数学语言描述为：上述真子集的数学语言描述为：B B A A对任意对任意x x，如，如x x B B，则，则x x A,A,并且，并且， y y A A，但是但是y y B B判断下列集合之间是否具有真包含关系。判断下列集合之间是否具有真包含关系。（1 1）a, ba, b和和a, b, c, da, b, c, d；（2 2）a, b, c, da, b, c, d和和a, b, c, da, b, c, d。解解 根据根据真子集的定义真子集的定义，有，有（1 1） a, b a, b a, b, c, da, b, c, d；（2 2）因为）因为a, b, c, da, b, c, da

13、, b, c, da, b, c, d，所以所以a, b, c, da, b, c, d不是不是a, b, c, da, b, c, d 的真子集。的真子集。例1.2.8例1.2.9设A=a是一个集合，B=a,a，试问AB和AB同时成立吗？A=a，aBAB成立；A=a，aBAB成立。解AB和AB同时成立。分析分析1.2.4几个特殊集合定义1.2.3不含任何元素的集合叫做空集(EmptySet)，记作。空集可以符号化为=x|xx空集是客观存在的。1、空集例例例例1.2.101.2.101.2.101.2.10 设设A = A = x|(xRx|(xR) )且且(x(x2 20)0)，试列举集合试

14、列举集合A A中的所有元素。中的所有元素。解解 A = A = 。定理定理1.2.3 1.2.3 （1 1）空集是一切集合的子集；）空集是一切集合的子集；（2 2）空集是绝对唯一的。）空集是绝对唯一的。定理1.2.3（2）的证明 对对“唯一性唯一性”的证明通常采用的证明通常采用反证法反证法。即假设即假设“不唯一不唯一”，得出矛盾，从而说明结论正确，得出矛盾，从而说明结论正确假设假设1 1和和2 2是两个是两个空集，且空集，且1 12 2，再证明再证明1 12 2，出现矛盾，从而说明结论成立。，出现矛盾，从而说明结论成立。那么怎么证明那么怎么证明1 12 2？分析分析根据定理根据定理1.2.3

15、1.2.3 （1 1）空集是一切集合的子集）空集是一切集合的子集 1 1 2 2， 2 2 1 1，根据定理根据定理1.2.21.2.2， 1 12 2 1 1 2 2，2 2 1 1与与1 12 2矛盾矛盾定义1.2.4在一个相对固定的范围内，包含此范围内所有元素的集合，称为全集或论集(UniversalSet)，用U或E表示。用文氏图描述如下:U2、全集例1.2.12（1）在立体几何中，全集是由空间的全体点组成；（2）在我国的人口普查中，全集是由我国所有人组成。定理定理1.2.51.2.5 全集是相对唯一的全集是相对唯一的. .集集合合A A中中元元素素的的数数目目称称为为集集合合A A的

16、的基基数数（base base number)number)，记为记为|A|A|。如如|A|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。有限集和无限集m元子集定义1.2.6如果一个集合A含有n个元素，则称集合A为n元集，称A的含有m个(0mn)元素的子集为A的m元子集。任给一个n元集，怎样求出它的全部m元子集？例1.2.1

17、4设A=1,2，求出A的全部m元子集。n=|A|=2，mnm=0,1,2。当m=0时，得到0元子集：；当m=1时，得到1元子集：1,2；当m=2时，得到2元子集：1,2。解A的全部m元子集是、1、2和1,2。分析分析子集总数一般来说，对于n元集A，它的m（0mn）元子集有个，所以不同的子集总数有：(1+1)n2n所以，n元集共有2n个子集。幂集定义1.2.7设A为任意集合，把A的所有不同子集构成的集合叫做A的幂集(powerset)，记为P(A)或2A。其符号化表示为P(A)x|一切xA该集合又称为集族(familyofset)。 对集族的研究在数学方面、知识库和表处理对集族的研究在数学方面、

18、知识库和表处理语言以及人工智能等方面都有十分重要的意义。语言以及人工智能等方面都有十分重要的意义。 例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|。1.2.5集合的运算定义1.2.8设A、B是两个集合，(1)并集AB=x|xA或xB(2)交集AB=x|xA且xB(3)差集A-B=x|xA且xB(4)补集=U-A=x|xU且xA(,AC)(5)对称差集AB=x|(xA)且(xB)或(xB)且(xA)UA B并

19、集并集UA B差集差集A BU对称差集对称差集UA B交集交集补集补集UA推广A1A2A3An=x|(x=x|(x A A1 1) )或或(x(x A A2 2) )或或或或(x(x A An n)A A1 1AA2 2AA3 3AAn nx|(xx|(x A A1 1) )且且(x(x A A2 2) )且且且且(x(x A An n)当当n n无限增大时，可以记为：无限增大时，可以记为：A A1 1AA2 2AA3 3 A A1 1AA2 2AA3 3定理1.2.51.等幂律:=；=；2.交换律:=;=3.结合律:()=()；()=()；4.恒等律:=；=；5.零律:=；=；6.分配律:(

20、)=()()()=()()7.吸收律:A(AB)=A;A(AB)=A；定理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.排中律：AU。证明：DeMorganDeMorgan律：律：分析定理1.2.2设A、B是任意两个集合，则AB，BAA=B证明（a）：由、知，证明（b）：b（b）在中，用和分别取代A和B，则有1.3无限集质变 无限集合无法用确切的个数来描述，无限集合无法用确切的个数来描述，因此，无因此，无限集合有许多有限集合所没有的一些特征

21、，而有限限集合有许多有限集合所没有的一些特征，而有限集合的一些特征也不能任意推广到无限集合中去，集合的一些特征也不能任意推广到无限集合中去，即使有的能推广，也要做某些意义上的修改。即使有的能推广，也要做某些意义上的修改。有限集有限集无限集无限集量量 变变1.3.1可数集合与不可数集合问题1,2,3,与12,22,32,哪个集合的元素更多？引入：自然数集合二十世纪初，集合成为数学的基本概念之后，由冯诺依曼（VonNeumann，J.）用集合的方式来定义自然数取得了成功，提出了用序列，,，,，来定义自然数。自然数集合N的定义bN，b若nN，则n:nnN。也即：0:，1:0，2:,0,1.n:0,1

22、,2,3,.n-1.故N0,1,2,3,.,n,.等势的概念定义1.3.1设A，B是两个集合，若在A，B之间存在1-1对应的关系：AB则称A与B是等势的(equipotential)，记为：AB。也称集合A与B等势(equipotent)。 注意：注意：若若A AB B，则则 A A B B。 若若A A B B，则，则 A AB B （）（）可数集合(可列集）定义1.3.2凡是与自然数集合等势的集合，统称为可数集合(可列集)(CountableSet)。记为：0 (读作阿列夫零) 。例1.3.1下列集合都是可数集合：1)O+x|xN，x是奇数;2)Px|xN，x是素数;解：1）在O+与N之间建立1-1对应的关系f：NO+如下：N.O+.2n+1.所以，O+是可数集合。2）在P与N之间建立1-1对应的关系f：NP如下：N.P11.所以，P是可数集合。定理1.3.1b两个有限集合等势当且仅当它们有相同的元素个数；b有限集合不和其任何真子集等势；b可数集合可以和其可数的真子集等势。不可数集合定义1.3.3b开区间(0,1)称为不可数集合，其基数设为(读作阿列夫)；b凡是与开区间(0,1)等势的集合都是不可数集合。例例1.3.21.3.2 (1)(1)闭区间闭区间0,1 0,1 是不可数集合；是不可数集合； (2)(2)实数集合实数集合R R是不可数集合。是不可数集合。