《《集合论基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《集合论基础》PPT课件.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、软件学院软件学院离离离离 散散散散 数数数数 学学学学郑 州 大 学任课教师：刘 学 文 软件学院软件学院第一篇第一篇 绪绪 言言v离散数学的特征和性质v此课程的主要学习内容v此课程的主要学习方法软件学院软件学院第一篇第一篇 绪绪 言言v正如马克思所说的：“一门科学，只有当它能够运用数学时，才算真正发展了。”计算机正是在离散数学中图灵机理论的指导下诞生的。v离散数学是数学的一个分支，它以离散量作为其主要研究对象，是研究离散对象的结构以及它们之间相互关系的科学。由于计算机不论硬件还是软件都属于离散结构，所以计算机所应用的数学必是离散数学。软件学院软件学院第一篇第一篇 绪绪 言言v离散数学课程是
2、计算机系核心课程 信息类专业必修课 其它类专业的重要选修课程v离散数学也是后继课的基础 软件学院软件学院第一篇第一篇 绪绪 言言v离散数学课程的学习可以培养学生抽象的思维、逻辑推理能力和创新能力。v让学生见识一些重要的数学思想、数学方 法以及用数学解决实际问题的著名事例。培养逻辑思维的能力和分析问题解决问题的能力。软件学院软件学院第一篇第一篇 绪绪 言言v离散数学的主要学习内容：1.集合论 2.代数系统 3.图论 4.数理逻辑 *5.组合数学 *6.形式语言与自动机软件学院软件学院第一篇第一篇 绪绪 言言v特点：内容较杂，概念多，定理多，比较抽象，学习有一定的难度。v学习方法：1.准确掌握每个
3、概念(包括内涵及外延)。2.要有刻苦钻研的精神,不断总结经验。3.在理解内容的基础上，要多做练习题，从而再进一步加深理解所学内容。4.注意培养分析问题和解决问题的能力软件学院软件学院第二篇第二篇 集合论集合论v主要包括如下内容：集合论基础 二元关系 函数软件学院软件学院第一章第一章 集合论基础集合论基础v本章主要介绍如下内容：基本概念及集合的表示方法 集合间的关系 特殊集合 集合的运算软件学院软件学院基本概念基本概念1.集合与元素 集合：是由确定的对象(客体)构成的集体。一般用大写的英文字母表示。这里所谓“确定”是指：论域内任何客体，要么属于这个集合，要么不属于这个集合，是唯一确定的。元素：集
4、合中的对象，称之为元素。：表示元素与集合的属于关系。例如，N表示自然数集合，2N，而1.5不属于N，写成 1.5N。软件学院软件学院2.有限集合与无限集合 这里对有限集合与无限集合先给出朴素的定义，以后再给出严格的形式定义。有限集合有限集合：元素是有限个的集合。如果A是有限集合，用|A|表示A中元素个数。例如，A=1,2,3,则|A|=3。无限集合无限集合：元素是无限个的集合。对无限集合的所谓大小的讨论，以后再进行。软件学院软件学院3.集合的表示方法 列举法列举法：将集合中的元素一一列出，写在大括号内。例如，N=1,2,3,4,A=a,b,c,d 描述法描述法：用句子描述元素的属性。例如，B=
5、x|x是偶数 C=x|x是实数且2x5 一般地，A=x|P(x),其中P(x)是谓词公式，如果客体a使得P(a)为真，则aA，否则aA。软件学院软件学院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软件学院软件学院集合中的元素也可以是集合，下面的集合的含义不同：如 a ：张书记 a :党支部(只有一个书记)a：分党委(只有一个支部)a
6、：党委(只有一个分党委)a：市党委(只有一个党委)软件学院软件学院特殊集合特殊集合1.全集 E 定义：包含所讨论的所有集合的集合，称之为全集，记作E。由于讨论的问题不同，全集也不同。所以全集不唯一。例如:若讨论数，可以把实数集看成全集。若讨论人，可以把人类看成全集。性质：对于任何集合A，都有A在E中。软件学院软件学院特殊集合特殊集合2.空集 定义：没有元素的集合，称之为空集，记作。性质：(1).对于任何集合A，都有在A中。(2).空集是唯一的。软件学院软件学院集合间的关系集合间的关系1.包含关系(子集)(1).定义：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的
7、子集。记作AB。文氏图表示如右下图。例如，N是自然数集合，R是实数集合，则NR AB软件学院软件学院集合间的关系集合间的关系(2).性质：(a).有自反性，对任何集合A有AA。(b).有传递性，对任何集合A、B、C，有AB且 BC，则AC。(c).有反对称性，对任何集合A、B，有AB且 BA，则A=B。软件学院软件学院集合间的关系集合间的关系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。软件学院软件
8、学院集合间的关系集合间的关系3.真包含关系(真子集)定义：A、B是集合，如果AB且AB，则称B真包含A，A真包含于B，也称A是B的真子集。记作AB。性质：有传递性，对任何集合A、B、C，如果有AB且 BC，则AC。软件学院软件学院集合的运算集合的运算1.1.交运算交运算 定义：定义：A、B是集合，由既属于A，也属于B的元素构成的集合,称之为A与B的交集,记作AB。例如:A=1,2,3,B=2,3,4 则 AB=2,3ABAB软件学院软件学院集合的运算集合的运算性质：幂等律幂等律 对任何集合A，有AA=A。交换律交换律 对任何集合A、B，有AB=BA。结合律结合律 对任何集合A、B、C，有 (A
9、B)C=A(BC)。同一律同一律 对任何集合A，有AE=A。零一律零一律 对任何集合A，有A=。AB AB=A。软件学院软件学院集合的运算集合的运算2.2.并运算并运算 定义：定义：A、B是集合，由或属于A，或属于B的元素构成的集合,称之为A与B的并集,记作AB。例如:A=1,2,3,B=2,3,4 则AB=1,2,3,4BAAB软件学院软件学院集合的运算集合的运算性质：幂等律幂等律 对任何集合A，有AA=A。交换律交换律 对任何集合A,B，有AB=BA。结合律结合律 对任何集合A,B,C,有(AB)C=A(BC).同一律同一律 对任何集合A，有A=A。零一律零一律 对任何集合A，有AE=E
10、。软件学院软件学院集合的运算集合的运算 分配律分配律 对任何集合A、B、C，有 A(BC)=(AB)(AC)。A(BC)=(AB)(AC)。吸收律吸收律 对任何集合A、B，有 A(AB)=A A(AB)=A。AB AB=B。软件学院软件学院集合的运算集合的运算3.绝对补集 定义：定义：A是集合,由不属于A的元素构成的集合,称之为A的绝对补集,记作A。例如，E=1,2,3,4，A=2,3,则A=1,4AEA软件学院软件学院集合的运算集合的运算性质：设A、B、C是任意集合，则 E=E (A)=A AA=AA=E 注：在这里只有A同时满足性质（4）（5）（称作A的惟一性）。证明：此时我们假设除了A还
11、有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软件学院软件学院集合的运算集合的运算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软件学院软件学院集合的运算集合的运算性质：设A、B、C是任意集合，则 A-=A -A=A-A=
12、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)=软件学院软件学院集合的运算集合的运算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)=软件学院软件学院德德.摩根定律的证明摩根定律的证明
13、显然：(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)软件学院软件学院差集性质证明差集性质证明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 软件
14、学院软件学院集合的运算集合的运算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软件学院软件学院集合的运算集合的运算性质：交换律交换律 对任何集合A、B，有AB=BA。结合律结合律 对任何集合A、B、C，有 (AB)C=A(BC)。同一律同一律 对任何集合A，有A=A。对任何集合A，有AA=。对可分配 A(BC)=(AB)(AC)软件学院软件学院幂集幂集6.集合的幂集定义:A是集合，由A的所有子集构成
15、的集合，称之为A的幂集。记作P(A)或2A。P(A)=B|BA例如:A A的幂集P(A)a ,a a,b ,a,b,a,b软件学院软件学院幂集幂集性质：(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)|软件学院软件学院n元有序组元有序组7.笛卡尔乘积 先给出n元有序组的定义 定义：n个（n1）按一定次序排列的客体a1,a2,，an 组成一个有序序列，称为n元有序组，记为（a1,a2,，an）。例如我国当前使用的身份证号码是由一个七元有序组组成（省、市、区、出生年、月、日、序列号）软件学院软件学院笛卡尔乘积笛卡尔乘积 两个集合的笛卡尔乘积：定义：集合A、B的笛卡尔乘积可表示为 AB=(a,b)|aA，bB 例如：设A=1,2，B=a,b，则 AB=(1,a),(2,a),(1,b),(2,b)软件学院软件学院笛卡尔乘积笛卡尔乘积n个集合的笛卡尔乘积 定义：集合A1、A2、An 的笛卡尔乘积可表示为 A1A2An=(a1,a2,an)|aiAi，i=1,2,性质：如果A、B都是有限集，且|A|=m,|B|=n，则|AB|=mn.