集合论基础优秀课件.ppt
集合论基础集合论基础第1页，本讲稿共39页第一篇第一篇 绪绪 言言v离散数学的特征和性质v此课程的主要学习内容v此课程的主要学习方法第2页，本讲稿共39页第一篇第一篇 绪绪 言言v正如马克思所说的：“一门科学，只有当它能够运用数学时，才算真正发展了。”计算机正是在离散数学中图灵机理论的指导下诞生的。v离散数学是数学的一个分支，它以离散量作为其主要研究对象，是研究离散对象的结构以及它们之间相互关系的科学。由于计算机不论硬件还是软件都属于离散结构，所以计算机所应用的数学必是离散数学。第3页，本讲稿共39页第一篇第一篇 绪绪 言言v离散数学课程是 计算机系核心课程 信息类专业必修课 其它类专业的重要选修课程v离散数学也是后继课的基础 第4页，本讲稿共39页第一篇第一篇 绪绪 言言v离散数学课程的学习可以培养学生抽象的思维、逻辑推理能力和创新能力。v让学生见识一些重要的数学思想、数学方 法以及用数学解决实际问题的著名事例。培养逻辑思维的能力和分析问题解决问题的能力。第5页，本讲稿共39页第一篇第一篇 绪绪 言言v离散数学的主要学习内容：1.集合论 2.代数系统 3.图论 4.数理逻辑 *5.组合数学 *6.形式语言与自动机第6页，本讲稿共39页第一篇第一篇 绪绪 言言v特点：内容较杂，概念多，定理多，比较抽象，学习有一定的难度。v学习方法：1.准确掌握每个概念(包括内涵及外延)。2.要有刻苦钻研的精神,不断总结经验。3.在理解内容的基础上，要多做练习题，从而再进一步加深理解所学内容。4.注意培养分析问题和解决问题的能力第7页，本讲稿共39页第二篇第二篇 集合论集合论v主要包括如下内容：集合论基础 二元关系 函数第8页，本讲稿共39页第一章第一章 集合论基础集合论基础v本章主要介绍如下内容：基本概念及集合的表示方法 集合间的关系 特殊集合 集合的运算第9页，本讲稿共39页基本概念基本概念1.集合与元素 集合：是由确定的对象(客体)构成的集体。一般用大写的英文字母表示。这里所谓“确定”是指：论域内任何客体，要么属于这个集合，要么不属于这个集合，是唯一确定的。元素：集合中的对象，称之为元素。：表示元素与集合的属于关系。例如，N表示自然数集合，2N，而1.5不属于N，写成 1.5N。第10页，本讲稿共39页2.有限集合与无限集合 这里对有限集合与无限集合先给出朴素的定义，以后再给出严格的形式定义。有限集合有限集合：元素是有限个的集合。如果A是有限集合，用|A|表示A中元素个数。例如，A=1,2,3,则|A|=3。无限集合无限集合：元素是无限个的集合。对无限集合的所谓大小的讨论，以后再进行。第11页，本讲稿共39页3.集合的表示方法 列举法列举法：将集合中的元素一一列出，写在大括号内。例如，N=1,2,3,4,A=a,b,c,d 描述法描述法：用句子描述元素的属性。例如，B=x|x是偶数 C=x|x是实数且2x5 一般地，A=x|P(x),其中P(x)是谓词公式，如果客体a使得P(a)为真，则aA，否则aA。第12页，本讲稿共39页4.说明 集合中的元素间次序是无关紧要的，但是必须是 可以区分的，即是不同的。例如A=a,b,c，B=c,b,a，C=a,b,c,a，则A、B和C是一样的。对集合中的元素无任何限制，例如令 A=人，石头，1，,B=,本书中常用的几个集合符号的约定：自然数集合N=1,2,3,整数集合I，实数集合R，有理数集合Q第13页，本讲稿共39页集合中的元素也可以是集合，下面的集合的含义不同：如 a ：张书记 a :党支部(只有一个书记)a：分党委(只有一个支部)a：党委(只有一个分党委)a：市党委(只有一个党委)第14页，本讲稿共39页特殊集合特殊集合1.全集 E 定义：包含所讨论的所有集合的集合，称之为全集，记作E。由于讨论的问题不同，全集也不同。所以全集不唯一。例如:若讨论数，可以把实数集看成全集。若讨论人，可以把人类看成全集。性质：对于任何集合A，都有A在E中。第15页，本讲稿共39页特殊集合特殊集合2.空集 定义：没有元素的集合，称之为空集，记作。性质：(1).对于任何集合A，都有在A中。(2).空集是唯一的。第16页，本讲稿共39页集合间的关系集合间的关系1.包含关系(子集)(1).定义：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的子集。记作AB。文氏图表示如右下图。例如，N是自然数集合，R是实数集合，则NR AB第17页，本讲稿共39页集合间的关系集合间的关系(2).性质：(a).有自反性，对任何集合A有AA。(b).有传递性，对任何集合A、B、C，有AB且 BC，则AC。(c).有反对称性，对任何集合A、B，有AB且 BA，则A=B。第18页，本讲稿共39页集合间的关系集合间的关系2.相等关系 定义：A、B是集合，如果它们的元素完全相同，则称A与B相等。记作A=B。性质：有自反性，对任何集合A，有A=A。有传递性，对任何集合A、B、C，如果有A=B且 B=C，则A=C。有对称性，对任何集合A、B，如果有A=B，则B=A。第19页，本讲稿共39页集合间的关系集合间的关系3.真包含关系(真子集)定义：A、B是集合，如果AB且AB，则称B真包含A，A真包含于B，也称A是B的真子集。记作AB。性质：有传递性，对任何集合A、B、C，如果有AB且 BC，则AC。第20页，本讲稿共39页集合的运算集合的运算1.1.交运算交运算 定义：定义：A、B是集合，由既属于A，也属于B的元素构成的集合,称之为A与B的交集,记作AB。例如:A=1,2,3,B=2,3,4 则 AB=2,3ABAB第21页，本讲稿共39页集合的运算集合的运算性质：幂等律幂等律 对任何集合A，有AA=A。交换律交换律 对任何集合A、B，有AB=BA。结合律结合律 对任何集合A、B、C，有 (AB)C=A(BC)。同一律同一律 对任何集合A，有AE=A。零一律零一律 对任何集合A，有A=。AB AB=A。第22页，本讲稿共39页集合的运算集合的运算2.2.并运算并运算 定义：定义：A、B是集合，由或属于A，或属于B的元素构成的集合,称之为A与B的并集,记作AB。例如:A=1,2,3,B=2,3,4 则AB=1,2,3,4BAAB第23页，本讲稿共39页集合的运算集合的运算性质：幂等律幂等律 对任何集合A，有AA=A。交换律交换律 对任何集合A,B，有AB=BA。结合律结合律 对任何集合A,B,C,有(AB)C=A(BC).同一律同一律 对任何集合A，有A=A。零一律零一律 对任何集合A，有AE=E 。第24页，本讲稿共39页集合的运算集合的运算 分配律分配律 对任何集合A、B、C，有 A(BC)=(AB)(AC)。A(BC)=(AB)(AC)。吸收律吸收律 对任何集合A、B，有 A(AB)=A A(AB)=A。AB AB=B。第25页，本讲稿共39页集合的运算集合的运算3.绝对补集 定义：定义：A是集合,由不属于A的元素构成的集合,称之为A的绝对补集,记作A。例如，E=1,2,3,4，A=2,3,则A=1,4AEA第26页，本讲稿共39页集合的运算集合的运算性质：设A、B、C是任意集合，则 E=E (A)=A AA=AA=E 注：在这里只有A同时满足性质（4）（5）（称作A的惟一性）。证明：此时我们假设除了A还有B满足（4）（5），则有B=B =B(AA)=（B A）（B A）=E(B A)=B A.同理，我们可以得到A=A B.因此B=A.A-B=AB 德摩根定律（De Morgans Law）：(AB)=AB (AB)=AB第27页，本讲稿共39页集合的运算集合的运算4.4.差运算差运算-(-(相对补集相对补集)定义：定义：A、B是集合，由属于A，而不属于B的元素构成的集合,称之为A与B的差集,或B对A的相对补集，记作A-B。从图中可以知道A-B=AB例如:A=1,2,3,B=2,3,4 则A-B=1ABA-B第28页，本讲稿共39页集合的运算集合的运算性质：设A、B、C是任意集合，则 A-=A -A=A-A=A-BA AB A-B=(A-B)-C=(A-C)-(B-C)A-(BC)=(A-B)(A-C)A-(B C)=(A-B)(A-C)A(B-C)=(AB)-(AC)但对-是不可分配的，如A(A-B)=A 而(AA)-(AB)=第29页，本讲稿共39页集合的运算集合的运算v补集与差集的关系：v A=E-A，A(B)=A-B，AA=，AA=E v利用以上性质我们可以得到著名的德.摩根定律（De Morgans Law):v (A B)=A Bv (A B)=A Bv我们简单地证明一下第一个式子：v只需证：(A B)(A B)=E 和 (A B)(A B)=第30页，本讲稿共39页德德.摩根定律的证明摩根定律的证明显然：(A B)(A B)=(A B)(A)(A B)(B)=E E=E及：(A B)(A B)=(A B)(A）(A B)(B)=(B-A)(A-B)=其中，我们用到了 B(A)=B-A 和 A(B)=A-B 由补集的惟一性，得 (A B)=(A B)同理可得 (A B)=(A B)第31页，本讲稿共39页差集性质证明差集性质证明v(6)(A-B)-C=(A-C)-(B-C)v证明:v（6）(A-B)-C=(A-B)C=(A B)Cv同时(A-C)-(B-C)=(A C)(B C)v =(A C)B Cv =(A C)B (A C)Cv =(A C)B v =(A C)B v =(A B)Cv 第32页，本讲稿共39页集合的运算集合的运算5.对称差 定义：定义：A、B是集合,由属于A而不属于B，或者属于B而不属于A的元素构成的集合,称之为A与B的对称差,记作AB。由右图可以看出：AB=AB-AB=(A-B)(B-A)例如：A=1,2,3，B=2,3,4 则AB=1,4ABABE第33页，本讲稿共39页集合的运算集合的运算性质：交换律交换律 对任何集合A、B，有AB=BA。结合律结合律 对任何集合A、B、C，有 (AB)C=A(BC)。同一律同一律 对任何集合A，有A=A。对任何集合A，有AA=。对可分配 A(BC)=(AB)(AC)第34页，本讲稿共39页幂集幂集6.集合的幂集定义:A是集合，由A的所有子集构成的集合，称之为A的幂集。记作P(A)或2A。P(A)=B|BA例如:A A的幂集P(A)a ,a a,b ,a,b,a,b第35页，本讲稿共39页幂集幂集性质：(1).给定有限集合A，如果|A|=n,则|P(A)|=2n。例如：a,b,c 则 P(A)=,a,b,c,a,b,a,c,b,c,a,b,c 238C33C32C31C30|P(A)|第36页，本讲稿共39页n元有序组元有序组7.笛卡尔乘积 先给出n元有序组的定义 定义：n个（n1）按一定次序排列的客体a1,a2,，an 组成一个有序序列，称为n元有序组，记为（a1,a2,，an）。例如我国当前使用的身份证号码是由一个七元有序组组成（省、市、区、出生年、月、日、序列号）410102198708250037 第37页，本讲稿共39页笛卡尔乘积笛卡尔乘积 两个集合的笛卡尔乘积：定义：集合A、B的笛卡尔乘积可表示为 AB=(a,b)|aA，bB 例如：设A=1,2，B=a,b，则 AB=(1,a),(2,a),(1,b),(2,b)第38页，本讲稿共39页笛卡尔乘积笛卡尔乘积n个集合的笛卡尔乘积 定义：集合A1、A2、An 的笛卡尔乘积可表示为 A1A2An=(a1,a2,an)|aiAi，i=1,2,性质：如果A、B都是有限集，且|A|=m,|B|=n，则|AB|=mn.第39页，本讲稿共39页
