1/28第二部分第二部分 集合论集合论集合论是研究集合一般性质的数学分支，创始人是集合论是研究集合一般性质的数学分支，创始人是康托尔康托尔(G.Cantor 1845-1918)。现代数学中，每个对。现代数学中，每个对象象(数，函数等数，函数等)本质上都是集合，即可以用某种集本质上都是集合，即可以用某种集合来示义，数学的各个分支本质上都是在研究某一合来示义，数学的各个分支本质上都是在研究某一种对象集合的性质，集合论的特点是研究对象的广种对象集合的性质，集合论的特点是研究对象的广泛性，是计算机科学的基础理论表达工具。泛性，是计算机科学的基础理论表达工具。2/28第三章第三章 集合代数集合代数3.1集合的基本概念集合的基本概念1.集合的定义集合的定义集合是现代数学中最重要的基本概念之一。我们知集合是现代数学中最重要的基本概念之一。我们知道，在任何一个数学理论中，不可能对其中的每道，在任何一个数学理论中，不可能对其中的每个概念都严格定义，这样的概念一般为数学理论个概念都严格定义，这样的概念一般为数学理论中的原始概念，而称其余的概念为它的派生概念。中的原始概念，而称其余的概念为它的派生概念。如欧几里得几何学中，如欧几里得几何学中，“点点”和和“线线”是原始概是原始概念，而念，而“三角形三角形”和和“圆圆”则为派生概念。今天则为派生概念。今天我们介绍的我们介绍的“集合集合”也是一个不能严格定义的原也是一个不能严格定义的原始概念。但是为了理解上的方便，我们仍然给一始概念。但是为了理解上的方便，我们仍然给一个不严格的定义。个不严格的定义。 3/283.1 集合的基本概念集合的基本概念定义定义3.1：任何被称为任何被称为“成员成员”或或“元素元素”的的对象的聚集称为集合对象的聚集称为集合(Set)。例如：自然数的全体例如：自然数的全体N，有理数的全体，有理数的全体Q，实，实数的全体数的全体R，复数的全体，复数的全体C，整数的全体，整数的全体Z，都是集合。都是集合。通常情况下，用带通常情况下，用带(或不带或不带)下标的大写英文字下标的大写英文字母表示集合，而用带母表示集合，而用带(或不带或不带)下标的小写英下标的小写英文字母表示集合的元素或成员。文字母表示集合的元素或成员。4/283.1 集合的基本概念集合的基本概念2.集合的表示集合的表示集合是由它所包含的元素完全确定的，有多集合是由它所包含的元素完全确定的，有多种方法来表示一个集合。种方法来表示一个集合。(1).枚举法：当一个集合仅有有限个元素或元枚举法：当一个集合仅有有限个元素或元素之间有明显的关系时，采用列出集合中全素之间有明显的关系时，采用列出集合中全部元素或部分元素的方法，叫枚举法。部元素或部分元素的方法，叫枚举法。例：例：A=1,2,3,4，B=a, b, c, x, y, z，N =0,1,2,3, 。这种方法实际上是一种显示表示法，优点是这种方法实际上是一种显示表示法，优点是具有透明性，缺点是当集合中元素比较多时具有透明性，缺点是当集合中元素比较多时会占据大量内存。会占据大量内存。5/283.1 集合的基本概念集合的基本概念(2).描述法：一般用谓词来概括集合中元素的描述法：一般用谓词来概括集合中元素的特性，由谓词特性，由谓词P(x)所定义的集合常记为：所定义的集合常记为：A=x |P(x)。例：例：B=x | x R x2-1=0。谓词表示法是一种隐式表示法，所表示的集谓词表示法是一种隐式表示法，所表示的集合元素可以是很少的或无穷多个，从计算机合元素可以是很少的或无穷多个，从计算机的角度来看，是种的角度来看，是种“动态动态”的表示法，不用的表示法，不用占据大量内存。占据大量内存。(3).文氏图法文氏图法(Venn)：文氏图解法是一种利用：文氏图解法是一种利用平面上的点的集合作成的对集合的图解，一平面上的点的集合作成的对集合的图解，一般用平面上的圆形或方形表示一个集合。般用平面上的圆形或方形表示一个集合。6/283.1 集合的基本概念集合的基本概念3.集合与元素的关系集合与元素的关系元素和集合之间的关系是元素和集合之间的关系是“隶属关系隶属关系”，即，即“属于属于”或或“不属于不属于”，“属于属于”记作记作，不属于记作不属于记作 。例：例：A=a，b，c，d，a A， b，c A，b A。例例3-1：在一个很偏僻的孤岛上，住着：在一个很偏僻的孤岛上，住着一些人家，岛上只有一个理发师，该理一些人家，岛上只有一个理发师，该理发师专给那些并且只给那些自己不刮脸发师专给那些并且只给那些自己不刮脸的人刮脸。那么该给这位理发师刮脸？的人刮脸。那么该给这位理发师刮脸？7/283.1 集合的基本概念集合的基本概念在离散数学中，我们仅讨论界限清楚无二义在离散数学中，我们仅讨论界限清楚无二义性的元素与集合的隶属关系，即元素性的元素与集合的隶属关系，即元素a要么要么属于集合属于集合A，要么不属于集合，要么不属于集合A，两者必居，两者必居其一。其一。4.集合的特性集合的特性(1).确定性：即确定性：即aA或或a A，两者必居其一，两者必居其一且仅居其一；且仅居其一；(2).互异性：集合中相同的元素被视为同一元互异性：集合中相同的元素被视为同一元素，即：素，即：1，1，2，2与与1，2相同；相同；(3).无序性：集合中的元素顺序并不重要，如无序性：集合中的元素顺序并不重要，如1，2，3，4与与2，3，4，1相同。相同。8/283.1 集合的基本概念集合的基本概念5.集合之间的关系集合之间的关系定定义义3.2：设设A，B是是两两个个集集合合，如如果果B中中的的每每个个元元素素都都是是A中中的的元元素素，则则称称B是是A的的子子集集合合，简简称称子子集集(Subset)，这这时时也也称称B被被A包包含含，或或A包包含含B，记记作作B A，或或A B，称称“ ”或或“ ”为为包包含含关关系系(Inclusion Relation)。如如果果B不被不被A包含，则记作包含，则记作B A。例：例：N Z Q R C, 但但Z N ;A=1，2，3，4，B=1，2，C=2，3，D=2，3，则则B,C,D A; C D; D C; B C,D; C,D B; A B,C,D 对任意的集合对任意的集合A，都有，都有A A 。9/283.1 集合的基本概念集合的基本概念定定义义3.3：设设A，B为为集集合合，如如果果A B且且B A，则则称称A与与B相相等等，记记作作A=B，如如果果A与与B不不相相等等，则则记记作作AB。相等的符号化表示为：相等的符号化表示为：A=B A B B A例例：A=x|xN，且且x4，B=0，1，2，3，4则则A=B。定定义义3.4：设设A，B为为集集合合，如如果果B A且且BA，则则称称B是是A的的真真子子集集(Proper Subset)，记记作作B A，称称“ ”为为真真包包含含关关系系(Properly Inclusion Relation)，如果，如果B不是不是A的真子集，则记作的真子集，则记作B A10/283.1 集合的基本概念集合的基本概念这时或者这时或者 ，或者，或者B=A，符号化表示为：，符号化表示为：例：例： ，但，但 ，0,1，2,3是是0,1,2,3的真子集，但的真子集，但1,4不是。不是。定义定义3.5：不含任何元素的集合叫做空集不含任何元素的集合叫做空集(Empty Set)，记作，记作。空集符号化表示为：。空集符号化表示为：=x |x x。例：设例：设 ，是方程，是方程 的实的实数解集，而该方程无实数解，所以数解集，而该方程无实数解，所以A= 。11/283.1 集合的基本概念集合的基本概念定定理理3.1：(1)：空空集集是是一一切切集集合合的的子子集集，(2)：空集是唯一的。：空集是唯一的。例例3-2：确定下列命题的真值：确定下列命题的真值：(1)： ，(2)： ，(3)： ，(4)： 。12/283.1 集合的基本概念集合的基本概念定义定义3.6：在一个具体问题中，如果涉及的集合都是在一个具体问题中，如果涉及的集合都是某个集合的子集，则称这个集合问全集某个集合的子集，则称这个集合问全集(Universal Ser)，用，用U或或E表示。表示。全集是唯一的，它包含了该问题所涉及的所有元素。全集是唯一的，它包含了该问题所涉及的所有元素。例：例：(1)在平面几何中，全集是由平面上全体点组成；在平面几何中，全集是由平面上全体点组成； (2)在人口研究中，全集是由世界上的所有人组成在人口研究中，全集是由世界上的所有人组成定义定义3.7：集合中的所有元素的个数称为集合的基数集合中的所有元素的个数称为集合的基数(Base Number)，记为，记为|A|；如果一个集合的基数是有；如果一个集合的基数是有限的，则称集合为有限集限的，则称集合为有限集(Finite Set)，如果一个集，如果一个集合的基数是无限的，则称集合为无限集合的基数是无限的，则称集合为无限集(Infinite Set)。13/283.1 集合的基本概念集合的基本概念例例3-3：求集合：求集合A，B，C，D的基数：的基数：A= ；B=1,2,3；C=1，2,3；D= 。解：解：|A|=0；|B|=3；|C|=2；|D|=1。定义定义3.8：含有含有n个元素的集合个元素的集合A称为称为n元集，它的含元集，它的含义义m个个(m n)元素的子集称作它的元素的子集称作它的m元子集。元子集。例例3-4：设：设A=1,2,3，求，求A的全部子集：的全部子集：解：将解：将A的全部子集按从小到大进行分类：的全部子集按从小到大进行分类： 0元子集：即空集，有元子集：即空集，有C03个：个： ； 1元子集：即单元素，有元子集：即单元素，有 C13个：个：1，2，3； 2元子集：有元子集：有C23个：个：1,2，1,3，2,3； 3元子集：有元子集：有C33个：个：1,2,3。14/283.1 集合的基本概念集合的基本概念集合集合A=1,2,3的全部子集共有的全部子集共有：一般来说，对于一般来说，对于n元集元集A，它的，它的m(0mn)元子集有元子集有个，所以它的不同子集总数为：个，所以它的不同子集总数为：定义定义3.9：设设A为集合，把为集合，把A的全体子集构成的集合的全体子集构成的集合叫做叫做A的幂集的幂集(Power Set)，记作，记作P(A)或或2A，符号化，符号化为：为：P(A)=x|x A。例：设例：设A=1,2,3，则，则P(A)= ，1，2，3，1,2，1,3，2,3，1,2,3，|P(A)|=2n15/283.1 集合的基本概念集合的基本概念例例3-5：求下列幂集：求下列幂集：(1)：P()；(2)：P()；(3)：P(,)；(4)：P(1，2,3)。16/283.2 集合的运算集合的运算为了更好的研究集合的性质，我们定义了集合的几为了更好的研究集合的性质，我们定义了集合的几个基本运算。个基本运算。定义定义3.10：设设A，B是两个集合，则是两个集合，则A与与B的并集的并集(Union)定义为：定义为： ，“”称为称为并运算并运算(Union Operation)。例：例：1,2,3,43,4,5=1,2,3,4,5，QN=Q。定义定义3.11：设设A，B是两个集合，则是两个集合，则A与与B的交集的交集(Intersection)定义为：定义为： ，“”称为交运算称为交运算(Intersection Operation)。例：例：1,2,3,4 3,4,5=3,4，a, b = ， QN=N。17/283.2 集合的运算集合的运算可以将以上定义推广到可以将以上定义推广到n个甚至无穷个集合的并集或个甚至无穷个集合的并集或交集：交集：例：例：1,22,30,1=0,1,2,3； 1,2 2,3 0,1= 。18/283.2 集合的运算集合的运算定义定义3.12：设设A，B是两个集合，则是两个集合，则A与与B的差集的差集(Subtraction)定义为：定义为： ；“-”称为差运算称为差运算(Subtraction Operation)，A-B也可也可叫做相对补集。叫做相对补集。例：例：1,2,3,4-3,4,5,6=1,2；1,2- =1,2； -1,2= ；1,2-1,2= 。定义定义3.13：设设U为全集，为全集，A是是U的子集，则集合的子集，则集合A的的补集补集(Complement)定义为：定义为：也可记为也可记为A，“-”，“”称为补运算称为补运算(Complement Operation)。例：例：U=1,2,3,4，A=1,2，A=3,4。19/283.2 集合的运算集合的运算定义定义3.14：设设A，B是两个集合，是两个集合，A与与B的对称差集的对称差集(Symmetric Differences)定义为：定义为：“ ”称为对称差运算称为对称差运算(Symmetric Differences Operation)。例：例：1,2,3,4 3,4,5,6=1,2,5,6； a, b, c =a, b, c。定理定理3.2：集合恒等式：集合恒等式：1.等幂律：等幂律：A A=A，A A=A;2.结合律结合律：(AB)C=A(BC)，(A B) C=A (B C)；3.交换律：交换律：A B=B A，A B=B A；20/283.2 集合的运算集合的运算4.分配律：分配律：A(BC)=(A B) (A C)，A (B C)=(A B)(A C)；5.同一律：同一律：A =A，A U=A；6.零律：零律：A U=U，A = ；7.排中律：排中律： ；8.矛盾律：矛盾律： ；9.吸收律：吸收律：A(A B)=A， A (A B)=A；10.德摩根律：德摩根律：(AB)=A B，(A B)=AB11.双重否定律：双重否定律： ；12.补交转换律：补交转换律： 。21/283.2 集合的运算集合的运算例例3-6：证：证：(3):A，B为集合，已知为集合，已知A-B=B-A，证明：，证明：A=B。证：证：(1):22/283.2 集合的运算集合的运算(2):(3): 同理：同理：A B，A=B。23/283.3 有限集合的计数有限集合的计数1. 鸽笼原理鸽笼原理(Pigeonhole Principle)定理定理3.3：若有若有n+1个鸽子住进个鸽子住进n个鸽笼，则至少有个鸽笼，则至少有一个鸽笼至少住进一个鸽笼至少住进2只鸽子。只鸽子。证明：证明：(用反证法用反证法)假设每个鸽笼至多只住进假设每个鸽笼至多只住进1只鸽子，只鸽子，则则n个鸽笼至多住进个鸽笼至多住进n只鸽子，这与有只鸽子，这与有n+1只鸽子矛只鸽子矛盾。盾。命题成立。命题成立。例例3-7：求证：求证：设有设有n+1个正整数个正整数 ，则总可以找到一对数则总可以找到一对数 (1ix=29, y+6=50=y=44, z+6=19=z=13, x+y+6=110-P=P=31, x+z+6=98-B=B=50, y+z+6=75-C=C=12, 总计总计=31+29+50+44+6+13+12=185；解二：用容斥原理：解二：用容斥原理： 总计总计=110+98+75-35-50-19+6=185