第一章集合论基础

1、离离 散散 数数 学学常 州 大 学任课教师： 朱虹第一篇第一篇 绪绪 言言v离散数学的特征和性质v此课程的主要学习内容v此课程的主要学习方法第一篇第一篇 绪绪 言言v离散数学（又称组合数学）是数学的一个分支，它以离散量作为其主要研究对象，是研究离散对象的结构以及它们之间相互关系的科学。由于计算机不论硬件还是软件都属于离散结构，所以计算机所应用的数学必是离散数学。v正如马克思所说的：“一门科学，只有当它能够运用数学时，才算真正发展了。”计算机正是在离散数学中图灵机理论的指导下诞生的。第一篇第一篇 绪绪 言言v离散数学在企业管理、交通规划、战争指挥、金融分析等领域中有很重要的应用，例如： 在美国

2、有家公司以组合数学命名，用组合数学的方法来提高企业管理的效益。 德国一位著名的组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用。第一篇第一篇 绪绪 言言v离散数学在日常生活中的应用：v世界地图着色v装箱子时，如何使得箱子尽量装满v航空调度和航班的设定v中国邮递员问题v用不同形状的地砖铺地，能否铺满v船夫要把一只狼、一只羊和一棵白菜运过河，其中狼要吃羊，羊要吃白菜，而船每趟只能运其中一个。第一篇第一篇 绪绪 言言v离散数学课程是 计算机系核心课程 信息类专业必修课 其它类专业的重要选修课程v离散数学也是后续课的基础 第一篇第一篇 绪绪 言言v离散数学课程的学习可以培养学生抽象的

3、思维、逻辑推理能力和创新能力。v让学生见识一些重要的数学思想、数学方 法以及用数学解决实际问题的著名事例。 培养逻辑思维的能力和分析问题解决问题的能力。第一篇第一篇 绪绪 言言v离散数学的主要学习内容： 1. 集合论 2. 代数系统 3. 图论 4. 数理逻辑 *5. 组合数学 *6. 形式语言与自动机第一篇第一篇 绪绪 言言v特点：内容较杂，概念多，定理多，比较抽象，学习有一定的难度。v学习方法： 1.准确掌握每个概念(包括内涵及外延)。 2.要有刻苦钻研的精神,不断总结经验。 3.在理解内容的基础上，要多做练习题，从而再进一步加深理解所学内容。 4.注意培养分析问题和解决问题的能力参考书目

4、参考书目v离散数学及其应用，机械工业出版社，Kenneth H.Rosen著，袁崇义等译v离散数学，上海科学技术文献出版社，左孝凌等著v离散数学，高等教育出版社，屈婉玲等编v这方面的参考书目很多，请大家自己选择第二篇第二篇 集合论集合论v主要包括如下内容： 集合论初步 二元关系 函数 有限集和无限集第一章第一章 集合论初步集合论初步v本章主要介绍如下内容： 基本概念及集合的表示方法 集合间的关系 特殊集合 集合的运算基本概念基本概念1.集合与元素 集合：是一些确定的对象(客体)的全体。一般用大写的英文字母表示。 这里所谓“确定”是指：论域内任何对象，要么属于这个集合，要么不属于这个集合，是唯一

5、确定的。 元素：集合中的对象。 ：表示元素与集合的属于关系。 例如，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 描述法描述法：用句

6、子描述元素的属性。 例如，B=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集合中的元素也可以是集合。例如：2，2特殊集合特殊集合1.全集 E 定义：包含所讨论的所

7、有元素的集合，称之为全集，记作E。 由于讨论的问题不同，全集也不同。所以全集不唯一。 例如: 若讨论数，可以把实数集看成全集。 若讨论人，可以把人类看成全集。 性质：对于任何集合A，都有A在E中。特殊集合特殊集合2.空集 定义：没有元素的集合，称之为空集，记作。 性质： (1).对于任何集合A，都有在A中。 (2).空集是唯一的。集合间的关系集合间的关系1.包含关系(子集) (1).定义：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的子集。记作AB。 文氏图表示如右下图。 例如，N是自然数集合， R是实数集合，则NR AB集合间的关系集合间的关系(2).性质：

8、(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。集合间的关系集合间的关系3.真包含关系(真子集) 定义：A、B是集合，如果AB且AB，则称B真包含A，A真包含于B，也称A是B的真子集。记作

9、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，有 (AB)C=A(BC)。 同一律同一律 对任何集合A，有AE=A。 零一律零一律 对任何集合A，有A=。 AB AB=A。集合的运算集合的运算2.2.并运算并运算

10、 定义：定义：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 。 集合的运算集合的运算 分配律分配律 对任何集合A、B、C，有 A(BC) =(AB)(AC)。 A(BC) =(AB)(AC)。 吸收律吸收律 对任何集合A、B，

11、有 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还有B满足（4）（5），则有B=B =B (AA)=（B A）（B A ）=E (B A)= B A.同理，我们可以得到A= A B.因此B= A.集合的运算集合的运算 A-B=AB 德摩

12、根定律（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= A-BA AB A-B= (A-B)-C=(A-C)-(B-C) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) A(B-C)=(AB)-(

13、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)=集合的运算集合的运算显然： (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)

14、 = 其中，我们用到了 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) C 集合的运算集合的运算5.对称差 定义：定义：A、B是集合,由属于A而不属于B，或者属于B而不属于A的元素构成的集合,称之为A与B的对称差,记

15、作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的所有子集构成的集合，称之为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)|集合的运算集合的运算7. 笛卡尔乘积 先给出n元有序组的定义 定义：n个（n1）按一定次序排列的客体a1 , a2 , ，an 组成一个有序序列，称为n元有序组，记为（ a1 , a2 , ，an ）。 例如我国当前使用的身份证号码是由一个七元有序组组成（省、市、区、出生年