离散数学 第2版 教学课件 作者 王元元 离散数学2007.ppt

《离散数学 第2版 教学课件 作者 王元元 离散数学2007.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教材：《计算机科学中的离散结构》教员：王元元教授学时：80考试：闭卷笔试离散数学离散数学的构成集合论settheory☆组合论conbinatoric☆数论numbertheory图论graphictheory☆数理逻辑mathmaticallogic☆计算理论computabilitytheory抽象代数abstractalgebra☆其他学习要求认真读书，必须做好课前预习和课后复习。认真听课，学会做笔记，课堂记教员强调的内容，课后整理笔记，书上有的不记。认真作业，必须按时、按要求完成课后练习。认真小结，在一个大单元结束时做好阶段复习总结。学有余力的同学可以阅读一本课外参考书

2、。1.1集合的概念和表示1.1.1集合及其元素1.1.2集合的表示1.1.3外延性公理与子集合1.1.1集合及其元素--集合的描述性定义集合是作为整体识别的、确定的、互相区别的一些对象的总体。例1-1：(1)“南京大学全体学生”为一集合，其组成对象是学生。(2)“全体自然数0，1，2，3…”为一集合，其组成对象是各自然数。(3)获1988年诺贝尔文学奖的作家构成一个集合，尽管它只有一个对象——埃及作家纳吉布•马夫兹。1.1.1集合及其元素--例1-1(续)(4)育才中学的所有班级组成一集合，其组成对象是班级，而不是学生，因为集合中对象是整体识别的。(5)“好书”的全体不构成集合，

3、因为难以对每一本书的好坏作出确定的判断。(6)方程x(x2–2x+1)=0的所有根组成一个集合，它只有一个对象0和一个(而不是两个)对象1，因为集合中对象是相互区别的。(7)方程x2+x+1=0的根组成一个集合。当讨论复数时，它由两个对象组成；当讨论实数时，它是一个没有任何对象的特定集合。1.1.1集合及其元素组成集合的对象称为集合的成员或元素（members）通常用大写拉丁字母A，B，C等表示集合，用小写字母a,b,c等表示集合的元素。但是，a作为A的元素时，并不排斥a作为集合的可能性。同样，集合A也可能是别的集合的元素。元素对于集合的隶属关系是集合理论的基本概念。当对象a是集

4、合A的成员时，称a属于A，记为aA当对象a不是集合A的成员时，称a不属于A，记为aA对任何对象a和任何集合A，或者aA或者aA,两者恰居其一。这正是集合对其元素的“确定性”要求。1.1.2集合的表示列举法：规定一个集合A时，将A中元素—一列举，或列出足够多的元素以反映A中成员的特征，表示形如A＝｛a1，a2，…，an｝或A=｛a1，a2，a3,…｝描述法：规定一个集合A时，将A中元素的特征用一个谓词公式来描述，表示形如A=｛xP(x)｝或A=｛x:P(x)｝其意义为：集合A由且仅由满足谓词公式P(x)的对象所组成，即：aA当且仅当P(a)真。归纳法：在1.3节中详细介

5、绍。1.1.2集合的表示--空集、全集、集合的基数空集：没有任何元素的特定集合，记为。＝{}＝{xxx}全集：包含所有对象的集合基数：集合中成员的个数称为集合的基数，集合A的基数表示为A。1.1.3外延性公理与子集合--外延性公理外延性公理：集合A和集合B相等，当且仅当它们具有相同的元素。也就是说，集合A,B满足A=B，当且仅当对任意元素x，x属于A蕴涵x属于B;反之，x属于B蕴涵x也属于A。例1-5：根据外延公理，{0，1}={1，0}={x∣x(x2–2x＋1)=0}={xx=1或x=0}1.1.3外延性公理与子集合--子集合子集合：集合A称为集合B的子集合，如

6、果A的每一个元素都是B的元素，记为AB。集合A称为集合B的真子集，如AB且AB。”A是B的真子集”记为AB。例1-5：{a，b}{a，c，b，d}，{a，b，c}{a，b，c}，{a}{a，b}，但a{a，b}，只有a{a，b}。不过存在这样两个集合，其中一个既是另一个的子集、又是它的元素。例如，{1}{1，{l}}，且{1}{1，{l}}。1.1.3外延性公理与子集合--子集合的性质定理定理1.1：对任意集合A，B，AB当且仅当AB且BA。特别地，对任意集合A，AA。定理1.2：对任意集合A，AU。定理1.3：设A，B，C为任意集合，若AB,B

7、C，则AC。定理1.4：对任何集合A，A。定理1.6：设A为一有限集合，An，那么A的子集个数为2n。定理1.5：空集是唯一的。1.2集合运算1.2.1并交差补运算1.2.2幂集运算和广义交、并运算1.2.1并交差补运算--定义设A，B为任意集合。并运算：A∪B称为A与B的并集，定义为A∪B=｛x∣x∈A或x∈B｝。∪称为并运算。交运算：A∩B称为A与B的交集，定义为A∩B=｛x∣x∈A且x∈B｝。∩称为交运算。差运算：A-B称为A与B的差集，定义为A–B=｛x∣x