离散数学

作者简介

内容简介

第3章集合集合论是现代数学的基础，它的起源可以追溯到16世纪末期.为了追寻微积分的坚实的基础，人们只进行了有关数集的研究.直到1876—1883年，康托发表了一系列有关集合论的文章，对任意元素的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论的深厚基础.但是，随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合论的发展一度陷入僵滞的局面.1904—1908年，策墨罗列出了**个集合论的公理系统，他的公理，使数学哲学中产生的一些矛盾基本上得到统一，在此基础上逐步形成了公理化集合论和抽象集合论，使该学科成为数学中发展*为迅速的一个分支.本章介绍集合的一些基本知识. 3.1集合的基本概念 在研究问题时，通常把具有某种性质的事物作为一个整体来研究，这个整体称为集合，其中的每个事物称为集合的元素.常用英文大写字母A,B,C等表示集合，以英文小写字母a,b,c等表示集合的元素.a∈A表示a是A的元素，aA表示a不是A的元素. 定义3.1.1一个集合若由有限个元素组成，则称为有限集，否则称为无限集.特别地，元素个数为零的集合称为空集，记作“”.用符号“|A|”表示有限集A的元素个数. 常见的集合表示法分为枚举法和特性描述法.枚举法是将集合的元素一一列出.如集合A由元素a,b,c,d组成，可记为A={a,b,c,d}.特性描述法是用集合的元素所具有的共**质来刻画集合.如A={x|x是正偶数}.一般集合可用A={x|P(x)}表示，其中P(x)表示事物x满足性质P，集合A由满足性质P的所有元素组成. 注（1） 集合的元素具有确定性，即元素a∈A或aA二者必居且仅居其一. （2） 集合的确定不应引起悖论.如A={x|xA}不能定义成为一个集合. （3） 集合中的元素具有无序性.如{a,b}={b,a}. 定义3.1.2集合间的关系有如下定义： （1） 设A，B为集合，AB表示A是B的子集，即如果a∈A，则a∈B. （2） 设A，B为集合，AB表示A是B的真子集，即AB且存在b∈B使bA. （3） 设A，B为集合，A=B表示AB且BA，即A和B元素相同，称作A与B相等. （4） 称P(X)={A|AX}为X的幂集，即X的所有子集组成的集合，有时也记为2X. 根据讨论问题的需要，常设一个充分大的集合为全集，也称为基本集，所讨论的集合均为这个集合的子集.[3]第3章集合[3][1]3.2集合的基本运算[3]注（1） X含有n个元素，则X有2n个子集，即P(X)含有2n个元素. （2） 空集是任一集合的子集. （3） 包含关系满足以下性质： ① AA；（自反性） ② 若AB,BA，则A=B； （反对称性） ③ 若AB,BC，则AC. （传递性） 例3.1.1设A={a,b},求P(A). 解P(A)={,{a},{b},{a,b}}. 注2={}，要区分与{}，其中表示空集，其中没有任何元素，而{}则表示以空集为元素的一个集族，即∈{}. 一般用N,Z,Q,R,C分别表示自然数集、整数集、有理数集、实数集、复数集，它们满足NZQRC. 3.2集合的基本运算 集合有并、交、差、补、对称差等运算. 定义3.2.1设A,B为集合，A与B的并集记作A∪B，其定义式为 A∪B={x|x∈A或x∈B}. 定义3.2.2设A,B为集合，A与B的交集记作A∩B，其定义式为 A∩B={x|x∈A且x∈B}. 定义3.2.3设A,B为集合，A与B的差集记作A－B或A\B，其定义式为 A－B={x|x∈A且xB}. 定义3.2.4设X为基本集，集合A的补集记作Ac或，其定义式为 Ac=X－A={x|xA且x∈X}. 定义3.2.5设A，B为集合，A与B的对称差记作AB，其定义式为 AB=(A－B)∪(B－A). 对称差也称为布尔和. 以上定义的并和交运算称为初级并和初级交.下面考虑推广的并和交运算，即广义并和广义交. 定义3.2.6设A为集合，A的元素的元素构成的集合称作A的广义并，记作∪A，符号化表示为 ∪A=x|zz∈A∧x∈z. 例3.2.1设A=a,b,c,a,c,d,a,e,f，B=a，C=a,c,d.则 ∪A={a,b,c,d,e,f}，∪B=a， ∪C=a∪c,d，∪= 根据广义并定义，我们有，若A=A1,A2,…,An，则∪A=A1∪A2∪…∪An. 定义3.2.7设A为集合，A的元素的元素构成的集合称作A的广义交,记作∩A，符号化表示为 ∩A=x|zz∈A→x∈z. 考虑例3.2.1中的集合，有 ∩A=a,∩B=a,∩C=a∩c,d. 但空集不可以进行广义交，因为∩不是集合，在集合论中是没有意义的.和广义并类似，若A=A1,A2,…,An，则∩A=A1∩A2∩…∩An. 例3.2.2设A={{a},a,b},计算∪∪A,∩∩A和∩∪A∪∪∪A－∪∩A. 解∪A={a,b},∩A=a,∪∪A=a∪b, ∩∪A∪∪∪A－∪∩A=a∩b∪a∪b－a =a∩b∪b－a =b. 所以∪∪A=a∪b，∩∩A=a, ∩∪A∪∪∪A－∪∩A=b. [3][1]3.3集合中元素的计数[3]3.3集合中元素的计数 集合的运算可以用文氏图表示.文氏图的构造方法如下： E是全集，圆A,B的内部为集合A,B，如果没有关于集合不交的说明，任何两圆应彼此相交.图中的阴影区域表示集合A,B在相应运算下组成的集合.具体见图3.3.1. 图3.3.1 X为集合，A,B,C为X的子集，∪,∩,c为集合的并、交、补运算，有以下性质： （1） A∪B=B∪A,A∩B=B∩A；（交换律） （2） (A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C)； （结合律） （3） A∪=A,A∩X=A； （同一律） （4） A∪Ac=X,A∩Ac=； （互补律） （5） A∪(A∩B)=A,A∩(A∪B)=A； （吸收律） （6） A∪(B∩C)=(A∪B)∩(A∪C)， A∩(B∪C)=(A∩B)∪(A∩C)； （分配律） （7） A∪A=A,A∩A=A； （幂等律） （8） A∪X=X,A∩=； （零律） （9） (Ac)c=A； （双重否定律） （10） A∪Bc=Ac∩Bc,(A∩B)c=Ac∪Bc. （德摩根律） 一本简单明了的离散数学教材