集合的基本概念1.ppt

离 散 数 学 (I),主讲教师：李占山 计算机楼A338 E-mail:zslizsli@,课程安排,本学期讲课学时：64 课程性质：必修 《离散数学》孙吉贵等 -----高等教育出版社 参考教材: 1《离散数学-学习指导与习题解答》孙吉贵等 -----高等教育出版社 2《集合论与图论》耿素云编著北京大学出版社 3《离散数学-精讲精解精练》黄健斌编著西安电子科技大学出版社,离散数学(I),第一章 集合论基础 第二章 命题逻辑 第三章 一阶逻辑 第四章 图与网络 第五章 数论基础,第一章 集合论基础,§1.1 集合的基本概念 §1.2 关 系 §1.3 映 射,集合论与第三次数学危机,集合是一个原始概念,最初是从分析数学中产生的1854年德国数学家黎曼在研究傅氏级数时，得出结论说：“若f(x)在区间上除有限个第一类间断点外是连续的，则在连续点，函数的三角函数收敛到函数值这时需要考虑这些连续点的整体，于是人们逐渐产生了点的集合的原始概念；对于集合概念的提出，起首要作用的人物是德国大数学家康托尔，他是数学史上公认的集合论的创始人1871年，他给出集合的第一个定义，且引入点集的极限点、闭集、开集、交集、并集等概念，1874年康托尔证明了代数数与有理数集的可数性和实数集的不可数性，1878年他又引入集合“势”的概念。

康托尔的工作具有革命性，一时难以被多数数学家接受，但数学的历史已有结论表明康托尔的集合论是分析数学与离散数学不可或缺的有力工具为此我们来了解一下康托尔与罗素,康托尔 (Cantor),康托尔简介,康托尔(Georg Cantor)1845年出生于俄罗斯的圣彼德堡，康托尔十多岁时就对数学产生了浓厚的兴趣1862年他在苏黎世开始了他的大学学习，1863年又在柏林大学继续学习，并得到著名数学家外尔斯特拉斯、库默尔和克罗内克的指导特别是受了外尔斯特拉斯的影响而专攻纯粹数学，1866年完成了一篇数论方面的博士论文后获得博士学位1869年康托尔得到了哈雷大学的一个职位，1879年任哈雷大学教授1891年，康托尔组建德国数学家联合会，任第一任主席1904年，伦敦皇家学会授予他最高荣誉：西尔威斯特（slvester)奖章康托尔这个人是数学界的奇才，他为数学的新奇思路和独特创造以及丰富的想象力，成为当时数学界有争议的人物但最终成为后世数学家学习与敬仰的模范康托尔的老师克罗内克是个“有穷论者”，他反对康托尔的“超穷数”的集合论观点，他不仅对康托尔的学术工作粗暴攻击，还竭力阻止康托尔去柏林大学工作，由于克罗内克的权威地位，使得其他数学家也跟着攻击康托尔的工作，使康托尔试图在柏林大学得到一个更高待遇的计划受挫。

1918年死于精神病诊所康托尔最著名的著作是1895-1897年出版的《超穷理论基础》（两卷集），康托尔指出，数学理论必须肯定实无穷，因为很多最基本的数学性质，例如一切正整数，圆周上的一切点等，事实上都是实无穷性的概念而且不能把能有穷所具有的性质强加于无穷他的“一一对应”的原理突破了传统的“整体大于部分”的旧观念，例如全体正整数与（其部分）全体正偶数一一对应，正整数集与正偶数集等势，相当于传统上的“个数相等” 康托尔的集合论现在称为朴素集合论，1871年他对集合给了一个朴素的限制宽松的定义；“把一定的并且彼此可以明确识别的事物（这种事物可以是直观的对象，也可以是思维的对象）放在一起，称为一个集合，这些事物中的每一个称为该集合的一个元素罗素简介,罗素（Bertrand Russell,1872-1970)生于一个以积极参与进步运动，热烈地投身于自由事业而著名的英格兰家庭年幼就成为孤儿的罗素由祖父抚养，并在家里接受教育1890年他进入剑桥的Trinity学院学习数学和论理学，并由于在几何学方面的工作突出为他赢得了一个研究员位置1910年Trinity学院任命他教授逻辑和数学原理的课程罗素最伟大的工作是他提出的可以作为所有数学学科基础的原理。

他最著名的文章是与人合作的《Principia Mathematica》，这篇文章试图用一组基本公理推导出所有的数学此外，他还写了包括哲学、物理和他的政治观点的很多书籍，1950年罗素赢得诺贝尔文学奖大厦基兮矗云天， 数学砥柱兮两撑竿 集合论兮康托儿峰颠巅， 逻辑理兮舌战群儒无辩§1.1 集合的基本概念,什么是集合(Set)？ “所要讨论的一类对象的整体”； “具有同一性质单元的集体” 通常，用大写的英文字母A, B, C,……表示集合；,,1、二十六个英文字母可以看成是一个集合； 2、所有的自然数看成是一个集合； 3、吉林大学计算机学院2007级的本科学生可以看成是一个集合； 4、这间教室中的所有座位可以看成是一个集合例如:,,集合的元素(member或element),组成一个集合的那些对象或单元称为这个集合的元素 通常，用小写的英文字母a, b, c,…表示集合中的元素,,设A是一个集合，a是集合A中的元素，记以aA，读作a属于A；若a不是集合A中的元素，则记以aA，读作a不属于A 例如：A是正偶数集合，则2A，8A，36A；而 3A，9A，17A,属于(belong to),,包含有限个元素的集合，称为有限集或有穷集(finite set)； 包含无限个元素的集合，称为无限集或无穷集(infinite set )。

例：所有英文字母组成的集合是有限集，整数集合是无限集有限集 、无限集,,约定，存在一个没有任何元素的集合，称为空集(empty set) ，记为，有时也用{}来表示 约定，所讨论的对象的全体称为全集(universal set)，记作E或U，我们所讨论的集合都是全集的子集 全集是相对的空集、全集,,设A是有穷集合， A中元素的个数称为集合A的元素数，记为A 例如，设A是所有英文字母组成的集合，则A=26 特别， |  |=0,集合的元素数,,列举法；将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，例如：V={a,e,i,o,u} 或B={1,4,9,16,25,36……} 描述法 ；通过描述集合中元素的共同特征来表示集合，例如： V= {x|x是元音字母} ，B= {x|x=a2 , a是自然数},集合的表示法,,文氏图(Venn Diagram) 用一个大的矩形表示全集，在矩形内画一些圆或其它的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素 例如：集合V={a,e,i,o,u} ，用文氏图表示如下:,,,E,V,,a,,u,,确定性； 互异性； 无序性； 多样性；,集合的特征,,任何一个对象，或者是这个集合的元素，或者不是，二者必居其一； 例如：A={x|x是自然数，且x100} B={x|x是年轻人} C={x|x是秃子},确定性,,集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。

例如： 集合A={a,b,c,c,b,d}，实际上，应该是A={a,b,c,d},互异性,,集合与其中的元素的顺序无关 例如： 集合{a,b,c,d,e}、{d,c,e,a,b}、 {e,c,d,b,a}，都是表示同一个集合无序性,,集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征 例如： A={a,{a},{{a},b},{{a}}, 1} A={1,a,*,-3,{a,b},{x|x是汽车},地球},多样性,,设集合S={A|A是集合，且AA} 若SS，则S是集合S的元素，但根据S的定义，有S  S，与假设矛盾； 若SS，则S是不以自身为元素的集合，但根据S的定义，有SS，与假设矛盾；,罗素悖论(Russell’s paradox),,当两个集合A和B的元素完全一样，即A，B实际上是同一个集合时，则称集合A，B相等，记以A=B 例：设A={x|x是偶数，且0x10}，B={2,4,6,8}，则A=B定义1】集合相等,设A，B是两个集合，若A的元素都是B的元素，则称A是B的子集，也称B包含A，或A包含于B，记以A  B，或B  A 若AB，且AB，则称A是B的真子集(proper subset)，也称B真包含A，或A真包含于B，记以AB，或B  A 。

定义2】子集(subset),设A={2,4,6,8} ，B= {x|x是正偶数}， C={x|x是整数},则有A  B，B C，AC,并且A  B，B  C，A  C 例：,对任意集合A, 有A  A 空集是任意集合的子集，且空集是唯一的 对于任意两个集合A、B，A=B当且仅当AB且BA重要结论,是否存在集合A和B, 使得AB 且A B ？若存在，请举一例 设A={a} ，B={a,{a},b,c}，则有: AB 且A B 再例如：  {}且 {},讨论：,设A 是集合，A的所有子集为元素做成的集合称为A的幂集，记以(A)或 2A (A)={S|S  A} 例： A={a,b,c} ，则 (A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}},【定义3】幂集(power set),若A为有穷集，|A|=n，则 |2A | = Cn0 + Cn1 + … + Cnn =2n x(A)当且仅当xA 设A、B是两个集合，AB当且仅当(A)(B)；,幂集的性质,,设C是一个集合若C的元素都是集合，则称C为集合族。

若集合族C可表示为C={SddD}，则称D为集合族C的标志（索引）集定义4】集合族、标志集,显然，2A是一个集合族 设A1, A2, A3, …是集合的序列，且两两之间互不相同，则集合{A1, A2, A3, …}是一个集合族，可表示为{Ai| iN}，其中,N是自然数集合，是该集合的标志集合设A，B是两个集合所有属于A或者属于B的元素做成的集合，称为A和B的并集，记以A∪B即A∪B={x|xA或xB} 例如，令A={a，b，c，d}，B={c，d，e，f}，于是A∪B={a，b，c，d，e，f}定义5】集合的并集(Union),并集的文氏图,A,B,A∪B,设A，B是两个集合由属于A又属于B的元素组成的集合，称为A和B的交集，记以A∩B即A∩B={x|xA且xB} 例如，令A={a，b，c，d}，B={c，d，e，f}，于是A∩B={c，d}定义6】集合的交集(Intersection),交集的文氏图,A,B,A∩B,设A1，A2，…，An是n个集合，则， A1∪A2∪…∪An ，简记为 A1∩A2∩…∩An ，简记为,并集和交集的推广,,设A1，A2，…，An是n个集合，则,容斥原理 (principle of inclusion-exclusion),,称为包含排斥原理，简称容斥原理。

设A，B是两个集合由属于集合A而不属于集合B的所有元素组成的集合，称为A与B的差集，记以A-B，或A\B 即A-B={x|xA且xB} 例如，令A={a，b，c，d}，B={c，d，e，f}，于是A - B={a，b}定义7】集合的差集(Difference),差集的文氏图,A,B,A-B,E,设A是一个集合，全集E与A的差集称为A的余集或补集，记以A即A=E-A 例如，令E={a，b，c，d，e，f}，A={b，c}，于是A={a，d，e，f} 特别，,【定义8】集合的补集(Complement),,,,补集的文氏图,A,A的补集,E,设A，B是两个集合则A与B的环和(对称差),记以AB, 定义为AB=(A-B)∪(B-A) A与B的对称差还有一个等价的定义，即AB=(A∪B)-(A∩B) 例：令A={a，b，c，d}，B={c，d，e，f}，于是AB={a，b， e，f}。