第一章集合论基础 1 [兼容模式].pdf

Discrete Mathematics课程要求课程要求课程要求课程要求 教材教材 课时安排课时安排 课程要求以及考试安排课程要求以及考试安排课程要求以及考试安排课程要求以及考试安排 参考书目参考书目 参考书目参考书目耿素云，屈婉玲编著离散数学(修订版)北京：高等教育出版社,2004耿素云，屈婉玲编著离散数学(修订版)北京：高等教育出版社,2004左孝凌左孝凌，李为鉴李为鉴，刘永才编著刘永才编著离散数学离散数学上海上海：上海科学技术文献出版上海科学技术文献出版左孝凌左孝凌，李为鉴李为鉴，刘永才编著刘永才编著离散数学离散数学上海上海：上海科学技术文献出版上海科学技术文献出版社,1982社,1982孙吉贵，杨凤杰，欧阳丹彤，李占山编著离散数学高等教育出版社，孙吉贵，杨凤杰，欧阳丹彤，李占山编著离散数学高等教育出版社，2002200220022002美美Kenneth H.RosenKenneth H.Rosen著袁崇义，屈婉玲，王捍贫，刘田译离散数学及其应用北京：机械工业出版社，著袁崇义，屈婉玲，王捍贫，刘田译离散数学及其应用北京：机械工业出版社，联系电话联系电话：联系电话联系电话：88202661Email:ruochenliusina com cnEmail:办公地点办公地点：主楼主楼II区区436办公地点办公地点：主楼主楼 区区绪绪 言言绪绪 言言 正如马克思所说的：“一门科学，只有当它能够运用数学时，才算真正发展了。”计算机正是在运用数学时，才算真正发展了。”计算机正是在离散数学中图灵机理论的指导下诞生的。离散数学是数学的一个分支，它以离散量作为其主要研究对象，是研究离散对象的结构以及它们主要研究对象，是研究离散对象的结构以及它们之间相互关系的科学。由于计算机不论硬件还是软件都属于离散结构，所以计算机所应用的数学软件都属于离散结构，所以计算机所应用的数学必是离散数学。绪绪 言言绪绪 言言 18世纪以前,数学基本上是研究离散对象的数量和空间关 18世纪以前,数学基本上是研究离散对象的数量和空间关系的科学。之后,因天文学,物理学的发展,如行星轨道,牛顿三大力学之后,因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极大地推动了连续数学(以微积分,数学物理方程,实、复变函数论为代表)的发展。离散对象的研究则处于停滞状态。离散对象的研究则处于停滞状态。20世纪30年代,图灵提出计算机的理论模型图灵机图灵机。这种模型早于实际制造计算机十多年,现实的计算机的计 这种模型早于实际制造计算机十多年,现实的计算机的计算能力,本质上和图灵机的计算能力一样。由于在计算机内,机器字长总是有限的,它代表离散的数由于在计算机内,机器字长总是有限的,它代表离散的数或其它离散对象，因此随着计算机科学和技术的迅猛发展,离散数学就显得重要。绪绪 言言绪绪 言言 离散数学课程是计算机系核心课程信息类专业必修课其它类专业的重要选修课程其它类专业的重要选修课程 离散数学也是后继课的基础离散数学也是后继课的基础数据结构,操作系统,编译理论,算法分析,系统结构,数据结构,操作系统,编译理论,算法分析,系统结构,容错判断容错判断,机器定理证明机器定理证明,数据库原理数据库原理,人工智能人工智能容错判断容错判断,机器定理证明机器定理证明,数据库原理数据库原理,人工智能人工智能绪绪 言言绪绪 言言 主要学习内容：1.集合论1.集合论2.代数系统2.代数系统3.图论4.数理逻辑第二篇第二篇集合论集合论第二篇第二篇集合论集合论主要内容：集合论基础集合论基础二元关系二元关系函数函数第一章第一章 集合论基础集合论基础第一章第一章 集合论基础集合论基础 本章主要介绍如下内容：基本概念及集合的表示方法基本概念及集合的表示方法集合间的关系集合间的关系特殊集合集合的运算1.1 集合的基本概念1.1 集合的基本概念1.集合与元素1.集合与元素集合：是由确定的对象(客体)构成的集体。一般用大写的英文字母表示。一般用大写的英文字母表示。这里所谓“确定”是指：论域内任何客体，要么属于这个集合，要么不属于这个集合，是唯一确定的。唯一确定的。元素：集合中的对象，称之为元素。：表示元素与集合的属于关系。：表示元素与集合的属于关系。例如，N表示自然数集合，2N，例如，N表示自然数集合，2N，而1.5不属于N，写成 1.5N。基本概念基本概念基本概念基本概念2.有限集合与无限集合有限集合有限集合：元素是有限个的集合。有限集合有限集合：元素是有限个的集合。如果A是有限集合，用|A|表示A中元素个数。例如，A=1,2,3,则|A|=3。个数。例如，A=1,2,3,则|A|=3。无限集合无限集合：元素是无限个的集合。无限集合无限集合：元素是无限个的集合。对无限集合的所谓大小的讨论，以后再进行。基本概念基本概念基本概念基本概念3.集合的表示方法3.集合的表示方法列举法列举法：将集合中的元素一一列出，写在大括号内。例如，N=1,2,3,4,A=a,b,c,d例如，N=1,2,3,4,A=a,b,c,d描述法描述法：用句子描述元素的属性。例如，B=x|x是偶数 C=x|x是实数且2x5C=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、B和C是一样的。对集合中的元素无任何限制，例如令对集合中的元素无任何限制，例如令A=人，石头，1，,B=,本书中常用的几个集合符号的约定：自然数集合N=1,2,3,自然数集合N=1,2,3,整数集合I，实数集合R，有理数集合Q特殊集合特殊集合特殊集合特殊集合全集E 包含所讨论的所有集合的集合，称之全集E:包含所讨论的所有集合的集合，称之为全集，记作E。由于讨论的问题不同，全集也不同。所以全集不唯一。以全集不唯一。例如:若讨论数，可以把实数集看成全集。若讨论人，可以把人类看成全集。空集:没有元素的集合，称之为空集，记作空集:没有元素的集合，称之为空集，记作。集合间的关系集合间的关系集合间的关系集合间的关系1.包含关系(子集)1.包含关系(子集)(1).定义：A、B是集合，如果A中元素都是B(1).定义：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的子集。记作A B。的子集。记作AB。文氏图表示如右下图。文氏图表示如右下图。例如，N是自然数集合，R是实数集合，则N RABR是实数集合，则NR集合间的关系集合间的关系集合间的关系集合间的关系(2).性质：(a).有自反性，对任何集合A有AA。(a).有自反性，对任何集合A有AA。(b).有传递性，对任何集合A、B、C，有A B且AB且BC，则AC。BC，则AC。(c).有反对称性，对任何集合A、B，有A B且AB且BA，则A=B。BA，则A=B。集合间的关系集合间的关系集合间的关系集合间的关系2.相等关系2.相等关系定义：A、B是集合，如果它们的元素完全相定义：A、B是集合，如果它们的元素完全相同，则称A与B相等。记作A=B。性质：性质：有自反性，对任何集合A，有A=A。有自反性，对任何集合A，有A=A。有传递性，对任何集合A、B、C，如果有A=B且 B=C，则A=C。A=B且 B=C，则A=C。有对称性，对任何集合A、B，如果有A=B，则B=A。集合间的关系集合间的关系集合间的关系集合间的关系3.真包含关系(真子集)3.真包含关系(真子集)定义：A、B是集合，如果A B且AB，则称B定义：A、B是集合，如果AB且AB，则称B真包含A，A真包含于B，也称A是B的真子集。记作A B。记作AB。性质：性质：有传递性，对任何集合A、B、C，如果有有传递性，对任何集合A、B、C，如果有AB且 BC，则AC。集合的运算集合的运算集合的运算集合的运算1.1.交运算交运算定义：定义：A、B是集合，由既属于A，也属于B的元素构成的集合,称之为A与B的交集,记的元素构成的集合,称之为A与B的交集,记作AB。U例如:A=1,2,3,B=2,3,4UAB则 AB=2,3ABAB集合的运算集合的运算集合的运算集合的运算2.2.并运算并运算定义定义：A、B是集合，由或属于A，或属于B定义定义：A、B是集合，由或属于A，或属于B的元素构成的集合,称之为A与B的并集,记作AB。作AB。U例如:A=1,2,3,B=2,3,4则AB 1 2 3 4UAB则AB=1,2,3,4AB集合的运算集合的运算集合的运算集合的运算3.绝对补集 定义：定义：A是集合,由不属于A的元素构成的集合,称之为A的绝对补集,记作A合,称之为A的绝对补集,记作A。例如，E=1,2,3,4，A=2,3,AEA例如，E 1,2,3,4，A 2,3,则A=1,4集合的运算集合的运算集合的运算集合的运算4.4.差运算-(相对补集)定义：A、B是集合，由属于A，而不属于B定义：A、B是集合，由属于A，而不属于B的元素构成的集合,称之为A与B的差集,或的元素构成的集合,称之为A与B的差集,或B对A的相对补集，记作A-B。AB从图中可以知道A-B=ABAB例如:A=1,2,3,B=2,3,4则A-B=1A-B则A-B=1集合的运算集合的运算BU集合的运算集合的运算5.对称差ABAB5.对称差定义定义：A、B是集合,由属于A而不属于B，定义定义：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 4则AB 1,4集合运算的基本公式集合运算的基本公式交换律交换律:AB=BA,AB=BA交换律交换律:,结合律:结合律:(AB)C=A(BC)(AB)C A(BC)(AB)C=A(BC)分配律分配律:A(BC)=(AB)(AC)分配律分配律:()()()A(BC)=(AB)(AC)同一律同一律:(,E的唯一性)同一律同一律:A=A,AE=A(,E的唯一性)互补律互补律:AA=AA=E(A的唯一性)互补律互补律:A A A A E(A的唯一性)集合运算的基本公式集合运算的基本公式集合运算的基本公式集合运算的基本公式零一律零一律:AEE AE A零一律零一律:AE=E,AE=A幂等律幂等律:AA=A,AA=A幂等律幂等律:,吸收律:吸收律:A(AB)=A,A(AB)=A双补律双补律:()双补律双补律:(A)=A,E=,=E德德摩根定律摩根定律（De Morgans Law）：）：德德 摩根定律摩根定律（De Morgan s Law）：）：(AB)=AB(AB)=AB 证明零一律证明零一律AE=EAE=E证明零一律证明零一律AEAE =E=E证证:左=AE=(AE)E=A(同一律同一律)左 AE (AE)E A (同一律同一律)=E (AE)(交换律)=(A A)(AE)(互补律)=A(A E)(分配律)=A(A E)(分配律)=A A (同一律同一律)=E (互补律)证明证明幂等律幂等律:AA=A证明证明幂等律幂等律:AA=A证:右=A=A(同一律同一律)右 A A(同一律同一律)=A(A A)(互补律)互补律)=(A A)(A A)(分配律)=(A A)E(互补律互补律)=(A A)E (互补律互补律)=(A A)(同一律)同一律)证明德证明德摩根定律摩根定律(AB)=AB证明德证明德摩根定律摩根定律(AB)=AB只需证(A B)(A B)E只需证：(A B)(A B)=E和(A B)(A B)=显然(A B)(A B)显然：(A B)(A B)=(A B)(A)(A B)(B)(分配律)=E E=E(互补律互补律,零一律零一律)=E E=E (互补律互补律,零一律零一律)及：(A B)(A B)=(A B)(A）(A B)(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)集合运算举例集合运算举例集合运算举例集合运算举例例例1 已知已知AB AC AB AC 证明证明B C例例1.已知已知AB=AC,AB=AC,证明证明B=C.例例2.化简化简:(ABC)(AB)(A(AC)(ABC)(AB)(A(AC)例例3.证明证明:(AB)-(AB)=(A-B)(B-A)(AB)(AB)(A B)(B A)例例1 已知已知AB=AC AB=AC 证明证明B=C例例1.已知已知AB=AC,AB=AC,证明证明B=C.证:B=C左左=B=B(AB)(吸收律)左左 B B(AB)(吸收律)=B(A C)=(B A)(BC)=(A C)(BC)=(A C)(BC)=C (AB)=C (A C)=C=C例例化简化简例例2.化简化简:(ABC)(AB)(A(AC)()()()解:(ABC)(AB)(A(AC)(AB)(A(AC)(吸收律)=(AB)(A(AC)(吸收律)=(AB)A(吸收律)()=A例例3.证明证明:(AB)(AB)(A B)(B A)(AB)-(AB)=(A-B)(B-A)证:左=(AB)-(AB)=(AB)(AB)=(AB)(A B)=(A A)(A B)(B A)(B B)()()()()=(A B)(B A)=(A B)(B A)=(A B)(B A)=(A-B)(B-A)1 2幂集幂集,n,n元有序组元有序组,笛卡尔乘积笛卡尔乘积1.2 幂集幂集,n,n元有序组元有序组,笛卡尔乘积笛卡尔乘积:是集合，由A的所有子集构成的集合，幂集幂集:A是集合，由A的所有子集构成的集合，称之为A的幂集。记作P(A)或2A。称之为A的幂集。记作()或。P(A)=B|BA例如:AA的幂集(A)例如:A A的幂集P(A)a ,aa,b ,a,b,a,b幂集幂集幂集幂集性质：(1).给定有限集合A，如果|A|=n,则|P(A)|=2n。(1).给定有限集合A，如果|A|=n,则|P(A)|=2n。例如：a b c 则例如：a,b,c 则P(A)=3210(),a,b,c,a,b,a,c,b,c,a,b,cC33C32C31C30|P(A)|238n n元有序组元有序组n n元有序组元有序组定义：n个（n1）按一定次序排列的客体a1,a2,，an组成一个有序序列，称为n元a1,a2,，an组成一个有序序列，称为n元有序组，记为（a1,a2,，an）。例如我国当前使用的身份证号码是由一个七例如我国当前使用的身份证号码是由一个七元有序组组成（省、市、区、出生年、月、元有序组组成（省、市、区、出生年、月、日、序列号）410102198708250037 笛卡尔乘积笛卡尔乘积笛卡尔乘积笛卡尔乘积两个集合的笛卡尔乘积：两个集合的笛卡尔乘积：定义定义：集合集合A A、B B的笛卡尔乘积可表示为的笛卡尔乘积可表示为定义定义：集合集合A A、B B的笛卡尔乘积可表示为的笛卡尔乘积可表示为AB=(a,b)|aA，bBAB=(a,b)|aA，bB例如：设A=1,2，B=a,b，则例如：设A=1,2，B=a,b，则AB=(1,a),(2,a),(1,b),(2,b)AB=(1,a),(2,a),(1,b),(2,b)笛卡尔乘积笛卡尔乘积笛卡尔乘积笛卡尔乘积n个集合的笛卡尔乘积：集合A1、A2、An的笛卡尔乘积可表示为:集合A1、A2、An的笛卡尔乘积可表示为:A1A2An=(a1,a2,an)|aiAi，i=1,2,性质：如果A、B都是有限集且|A|=m,|B|=n，性质：如果A、B都是有限集且|A|=m,|B|=n，则:|AB|=mn.本章小节本章小节本章小节本章小节本章介绍了集合的基本概念本章介绍了集合的基本概念、性质性质、表示方法表示方法本章介绍了集合的基本概念本章介绍了集合的基本概念、性质性质、表示方法表示方法和集合的基运算。主要内容包括：子集、空集、幂和集合的基运算。主要内容包括：子集、空集、幂集、集合的并、交、差.集、集合的并、交、差.