离散数学 第2版 作者 王元元 离散数学2007.pptVIP

教材：《计算机科学中的离散结构》教员： 王 元 元 教授学时： 80考试： 闭卷笔试 离散数学的构成 集合论 set theory ☆ 组合论 conbinatoric ☆ 数论 number theory 图论 graphic theory ☆ 数理逻辑 mathmatical logic ☆ 计算理论 computability theory 抽象代数 abstract algebra ☆ 其他 学习要求 认真读书，必须做好课前预习和课后复习。 认真听课，学会做笔记，课堂记教员强调的内容，课后整理笔记，书上有的不记。 认真作业，必须按时、按要求完成课后练习。 认真小结，在一个大单元结束时做好阶段复习总结。 学有余力的同学可以阅读一本课外参考书。 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) “好书”的全体不构成集合，因为难以对每一本书的好坏作出确定的判断。 (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是集合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节中详细介绍。 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的子集合，如果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}，只