第一章集合的基本概念ppt

离散数学教程（集合论与图论）离散数学：计算机科学与技术的数学基础课内容：集合论，图论，组合数学，代数结构，数理逻辑集合论:（第1-4章）图论:（第5-9章）组合数学:（第10-12章）教师介绍教师：吴永辉博士副教授简历：1984-1988上海科技大学计算机系本科1988-1991复旦大学计算机系硕士1991-2003华东师范大学计算机系工作1998-2001复旦大学计算机系博士2003-复旦大学计算机系工作答疑E-mail:[e-mail]《集合论与图论》课件制作软件MicrosoftPowerPointMathTypeEquation《集合论与图论》课程大纲课程性质与目的教学内容与要求使用教材、参考书籍命题说明和题型课程性质、目的与基本要求课程性质本课程讲授计算机科学与技术的数学基础课《离散数学》的部分主要内容：集合论、图论与组合数学初步，是计算机专业的主干课程之一。本课程前行课程为线性代数，数学分析(上)。课程目的使学生掌握集合论、图论与组合数学初步的基本内容，并对证明的思想和方法深入理解和体会，初步培养学生的思维过程的数学化。基本要求：掌握集合论、组合学和图论的基本概念，清楚了解引入基本概念的实际背景、各概念间相互关系；掌握基本定理以及有关理论题的证明技巧；掌握解决计数问题的基本方法和技巧；掌握图论中各算法设计的思想、正确性证明以及算法的应用。为进一步学习计算机其他课程打下坚实的基础。教学方式本课程以课堂讲授为主。考核方式平时作业；集合论、组合数学和图论3次课堂练习；期中，期末的两次笔试考试。教学内容与要求----集合论第一章集合的基本概念掌握：集合的基本概念，集合的运算。了解：集合论的悖论。掌握证明两个集合相等的基本法和公式法。第二章关系掌握：关系的性质、运算和关系的闭包，以及等价关系和偏序关系。了解：关系在关系数据库中的应用。掌握证明的类型。第三章函数掌握：函数的基本概念，复合函数和逆函数。了解：集合的特征函数。第四章无限集掌握：基数及基数的比较，判断可列集与不可列集的方法。了解：集合的递归定义。教学内容与要求----组合数学初步第十章鸽笼原理掌握：利用鸽笼原理解决组合数学中一些存在性问题的技巧。第十一章排列与组合掌握：集合的排列与组合，多重集的排列与组合等计数方法，有序划分和无序划分。第十二章生成函数与递推关系掌握：用生成函数和递推关系解决组合计数问题的方法，以及求解递推关系的生成函数方法。了解：求解递推关系的特征根方法。教学内容与要求----图论第五章图的基本概念掌握：图的基本术语，路、回路和连通的基本概念，求最短路的算法及算法正确性证明，欧拉图和哈密顿图的基本概念、判别方法以及有关定理。第六章平面图与图的着色掌握：平面图的基本概念、平面图的特征和欧拉公式，掌握图的点着色和平面图的面着色概念。了解：图的边着色概念。第七章树掌握：树的基本性质和生成树、割集、有根树的概念，求最小生成树和最优树的算法及算法的正确性证明。了解：树的计数问题。教学内容与要求----图论第八章连通度、网络与匹配教学时间：10学时；掌握：点连通度和边连通度的基本概念，掌握最大网络流算法及算法正确性证明，掌握匹配的基本概念和判别方法，掌握独立集和覆盖的基本概念和有关定理及证明方法。了解：佩特里网及其图的表示。使用教材《离散数学教程》，朱洪等著。上海科学技术文献出版社，1996。参考书籍一、基础[1]BernardKolman,etc..DiscreteMathematicalStructure,ThirdEdition.1997.清华大学出版社,PrenticeHall.(中、英文版)[2]左孝凌,李为槛,刘永才.离散数学理论分析题解。1988，上海科技文献出版社。[3]左孝凌,李为槛,刘永才.离散数学。1988，上海科技文献出版社。二、提高[4]KennethH.Rosen.DiscreteMathematicsanditsApplications.(4th,5thEdition).机械工业出版社,McGraw-Hill.(中、英文版)本书第4版是全球500多所大学的指定教材，获得了极大的成功。中文版也已被国内大学广泛采用为教材。第5版在前四版的基础上做了大量的改进，使其成为更有效的教学工具。参考课件[1]《DiscreteMathematicsandItsApplications》课件在线学习网站[1]北京大学计算机系《离散数学教程》网上教室[2]北京邮电大学《离散数学》在线课件[3]国立交通大学《离散数学——电脑辅助教学CAI》（台湾）~is83039/discret/discrete.html在线计算机和数学类书库计算机和数学类书库吉林大学的“藏经阁”elmo站:理论计算机科学经典网站国内：国际：~suresh/theory/theory-home.html命题说明和题型1填空题：基本概念的理解和掌握2判断题：概念的掌握与应用3计算、证明题：概念的综合应用，数学方法的运用集合论集合论是现代数学的基础,它已深入到各种科学和技术领域中,被广泛应用到数学和计算机科学的各分支中去。集合论的创始人：康托尔(Cantor,1845--1918)，1874年，“关于所有实代数数所成集合的一个性质”的论文。理论中出现了悖论。为解决悖论，在20世纪初开始了集合论公理学方向的研究,它是数理逻辑的中心问题之一。（本书避免用集合的公理化方法，直观地介绍朴素集合论。）集合论部分提高参考书籍沈恩绍集论与逻辑----面向计算机科学科学出版社集合论部分内容与常规教材相似，强调公理化图论图论提供了一个自然的结构，由此产生的数学模型几乎适合于所有科学（自然科学与社会科学）领域，只要这个领域研究的主题是“对象”与“对象”之间的关系。图论部分提高参考书籍BelaBollobas.ModernGraphTheory(现代图论).科学出版社&Springer.2001.组合数学1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。组合数学部分提高参考书籍RichardA.Brualdi.IntroductoryCombinatorics(3E)，(组合数学(第3版),(冯舜玺等译)),机械工业出版社,2002.第一章集合的基本概念1.1集合的表示1.2集合的子集1.3笛卡尔积1.4集合的运算1.5罗素悖论引言：什么是集合？一些自行车在计算机系车棚内的自行车一些自行车不是集合，无法确定范围和性质在计算机系车棚内的自行车是集合，可以确定范围和性质1.1集合的表示一集合的定义•1集合：具有共同性质的一些东西汇集成一个整体。例：复旦大学教师2元素：构成一个集合中的那些对象。a∈Aa是A的元素，a属于AaAa不是A的元素，a不属于A例：吴永辉∈复旦大学教师，沈恩绍复旦大学教师常用大写字母表示集合，小写字母或数字表示元素1.1集合的表示二集合的表示1列出集合中的元素：A={1,3,5,7,9}2描述集合中元素具有的共同性质{x|p(x)}：3通过某规则的计算来定义集合中的元素2{|10}Axx1.1集合的表示三术语1空集：不含任何元素的集合，记为2有/无限集：集合中有有限个元素/否则…..有限集A的元素个数称为集合A的基数，记为|A|。集合中元素之间的次序是无关紧要的。3多重集：集合中元素可以重复出现4集合族：以集合为元素组成的集合5与{}是不同的：{}表示以为元素的集合。例：设A,B,C是任意3个集合，如果AB,BC,则AC可能吗？AC常真吗？举例说明。/*集合论题集，经典习题，集合基础*/1.2集合的子集一文氏图：用平面上封闭曲线包围点集的图形来表示集合图1.1,图1.2二定义1.1（子集）集合A,B，A的每一元素都是B的元素，则A是B的子集。AB或BA。特别：AA。此外，若存在元素aA,但aB,则A不是B的子集.三定义1.2（集合相等与不相等）：集合A和B的元素全相同，则称A和B相等，A=B；否则称A和B不相等，AB。定理1.1A=BAB并且BA。1.2集合的子集——证明的方法定理1.1：A=BAB并且BA。“当且仅当”：证明由两部分组成：1）由条件证明结论A=BAB并且BA2）由结论证明条件AB并且BAA=B证明：A=BAB并且BA。因为A=B，由定义A中的每个元素是在B中，所以AB，同理B中的每个元素是在A中，所以BA。AB并且BAA=B。反证，如果AB，则A中至少有一个元素不在B中，与AB矛盾；或者B中至少有一个元素不在A中，与BA矛盾。所以AB不可能成立。所以A=B。四定义1.3（真子集）：AB并且AB，则AB。（和不同：元素集合；集合集合）例：设A,B,C是集合，判断下列命题真假，如果为真，给出证明；如果为假，给出反例：1)AB,BCAC;2)AB,BCAC;3)AB,BCAC;4)AB,BCAC;5)aA,ABaB./*集合论题集，经典习题，集合基础*/五定义1.4（全集）：在取定一个集合U以后，对于U的任何子集而言，称U为全集。定理1.2：（1）A(2)AA(3)AU1.2集合的子集——证明的方法证明：（1）A(2)AA(3)AU（1）反证法：假设结论不成立，导出矛盾结果。不是A的子集，导致矛盾（2，3）基本法：由子集定义x左x右，则左右证明：（1）A假设不是A的子集，则至少有一个元素x，使得x且xA。又因为是空集，它没有元素，所以对任何x，必有x，导致矛盾。因此是集合A的子集。反证法的证明步骤（1）假设命题的结论不成立；（2）进行一系列的推理；（3）推理过程中出现下列情况中的一种：1）与已知条件矛盾；2）与公理矛盾；3）与已知定理矛盾；（4）由于上述矛盾的出现，可以断言，原来的假定“结论不成立”是错误的（5）肯定原来命题是正确的。反证法的思想/思维过程“结论不成立”与“结论成立”必有一个正确。“结论不成立”会导致出现错误，推理过程、已知条件、公理和已知定理没有错误，惟一有错误的是一开始接假定的“结论不成立”，所以“结论不可能不成立”，即“结论成立”。1.2集合的子集六定义1.5（幂集）：A的所有子集组成的集合称为A的幂集。记为P(A)。例1.1（已知A，求幂集）定理1.3|P(A)|=2|A|证明方法：组合的方法求幂集——代数法P13习题1.13设A={a,{a}}，问：(1){a}P(A)?{a}P(A)?(2){{a}}P(A)?{{a}}P(A)?(3)又设A={a,{b}}，重复(1)、(2)。解:(1,2)首先求P(A)，代数法：代入：设x={a}，则A={a,x}；P(A)={,{a},{x},{a,x}}；回代：P(A)={,{a},{{a}},{a,{