集合的概念与表示法

2018/2/23,第3章 集合,3.1 集合的概念与表示法3.2 集合的运算与性质 3.3 集合的划分与覆盖 3.4 排列与组合3.5 归纳原理3.6 容斥原理和抽屉原理3.7 递推关系3.8 集合论在命题逻辑中的应用,2018/2/23,3.1 集合的概念与表示法,3.1.1 集合的概念 集合作为数学的一个基本而又简单的原始概念，是不能精确定义的。一般我们把一些确定的互不相同的对象的全体称为集合，集合中的对象称为集合的元素。通常用大写字母(如A、B等)表示集合，用小写字母(如a、b)表示集合中的元素。给定一个集合A和一个元素a，可以判定a是否在集合A中。如果a在A中，我们称a属于A，记为aA。否则，称a不属于A，记为aA。 例如，某大学计算机系的全体学生、所有自然数等都是集合。,2018/2/23,由集合的概念可知，集合中的元素具有确定性、互异性、无序性和抽象性的特征。其中：(1)确定性是指：一旦给定了集合A，对于任意元素a，我们就可以准确地判定a是否在A中，这是明确的。(2)互异性是指：集合中的元素之间是彼此不同的。即集合a，b，b，c与集合a，b，c是一样的。(3)无序性是指：集合中的元素之间没有次序关系。即集合a，b，c与集合c，b，a是一样的。(4)抽象性是指：集合中的元素是抽象的，甚至可以是集合。如A1，2，1，2，其中1，2是集合A的元素。,2018/2/23,集合是多种多样的，我们可以根据集合中元素的个数对其进行分类。集合中元素的个数称为集合的基数，记为|A|。当|A|有限时，称A为有限集合；否则，称A为无限集合。下面将本书中常用的集合符号列举如下：N：表示全体自然数组成的集合。Z：表示全体整数组成的集合。Q：表示全体有理数组成的集合。R：表示全体实数组成的集合。Zm：表示模m同余关系所有剩余类组成的集合。,2018/2/23,3.1.2 集合的表示法 表示一个集合通常有两种方法：列举法和谓词表示法。 1. 列举法(或枚举法) 列举法就是将集合的元素全部写在花括号内，元素之间用逗号分开。例如：Aa，b，c，B0，1，2，3，。 列举法一般用于有限集合和有规律的无限集合。 2. 谓词表示法(或描述法) 谓词表示法是用谓词来概括集合中元素的属性。通常用x|p(x)来表示具有性质p的一些对象组成的集合。例如：x|1x6x为整数为由1、2、3、4、5、6组成的集合。 下面讨论集合之间的关系。,2018/2/23,3.1.3 集合的包含与相等 包含与相等是集合间的两种基本关系，也是集合论中的两个基本概念。两个集合相等是按照下述原理定义的。外延性原理 两个集合A和B是相等的，当且仅当它们有相同的元素。记为AB。例如，若A2，3，B小于4的素数，则AB。定义3.1 设A和B为两个集合，若对于任意的aA必有aB，则称A是B的子集，也称A包含于B或B包含A，记作AB。如果B不包含A，记作AB。B包含A的符号化表示为：ABx(xAxB)。例如，若A1，2，3，4，B1，2，C2，3，则BA且CA，但CB。,2018/2/23,定理3.1 集合A和B相等当且仅当这两个集合互为子集。即：ABABBA。证明 若AB，则A和B具有相同的元素，于是x(xAxB)、x(xBxA)都为真，即AB且BA。反之，若AB且BA，假设AB，则A与B元素不完全相同。不妨设有某个元素xA但xB，这与AB矛盾，所以AB。这个定理非常重要，是证明两个集合相等的基本思路和依据。,2018/2/23,定理3.2 设A、B和C是三个集合，则：(1)AA。(2)ABBCAC。证明 (1)由定义显然成立。(2)ABBCx(xAxB)x(xBxC)x(xAxB)(xBxC)x(xAxC)AC。定义3.2 设A和B是两个集合，若AB且B中至少有一个元素b使得bA，则称A是B的真子集，也称A真包含于B或B真包含A，记作AB。否则，记作AB。B真包含A的符号化表示：,2018/2/23,ABx(xAxB)x(xBxA)。若两个集合A和B没有公共元素，我们说A和B是不相交的。例如，若Aa，b，c，d，Bb，c，则B是A的真子集，但A不是A的真子集。需要指出的是，与表示元素和集合的关系，而、与表示集合和集合的关系。例如，若A0，1，B0，1，0，1，则AB且AB。定理3.3 设A、B和C是三个集合，则(1)(AA)。 (2)AB(BA)。(3)ABBCAC。,2018/2/23,证明 仅证(2)和(3)(2)ABx(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xAxB)(x(xAxB)x(xAxB)(x(xAxB)x(xBxA)(BA)。(3)ABBC(x(xAxB)x(xBxA)(x(xBxC)x(xCxB)x(xAxBxBxC)(x(xBxA)x(xCxB)x(xAxC)(x(xCxA)AC。,2018/2/23,3.1.4 空集、集族、幂集和全集定义3.3 没有任何元素的集合称为空集，记作。以集合为元素的集合称为集族。例如，x|xx是空集；xx是某大学的学生社团是集族。定理3.4 空集是任何集合的子集。证明 任给集合A，则Ax(xxA)。由于x是假的，所以x(xxA)为真，于是有A为真。推论 空集是惟一的。对于任一集合A，我们称空集和其自身A为A的平凡子集。,2018/2/23,特别要注意与的区别，是不含任何元素的集合，是任意集合的子集，而是含有一个元素的集合。定义3.4 一个集合A的所有子集组成的集合称为A的幂集，记作P(A)或2A。例1 求幂集P()、P()、P(，)、P(1，2，3)。解 P()P()，P(，)，P(1，2，3)，1，2，3，1，2，3。,2018/2/23,定理3.5 若|A|n，则|P(A)|2n。证明 因为A的m个元素的子集的个数为Cnm，所以|P(A)|Cn0Cn1Cnn2n。定理3.6 设A和B是两个集合，则：(1)BP(A)BA。(2)ABP(A)P(B)。(3)P(A)P(B)AB。(4)P(A)P(B)AB。(5)P(A)P(B)P(AB)。(6)P(A)P(B)P(AB)。,2018/2/23,定义3.5 所要讨论的集合都是某个集合的子集，称这个集合为全集，记作U或E。全集是一个相对的概念。由于所研究的问题不同，所取的全集也不同。例如，在研究整数间的问题时，可把整数集Z取作全集。在研究平面几何的问题时，可把整个坐标平面取作全集。,2018/2/23,3.1.5 有限幂集元素的编码表示 为便于在计算机中表示有限集，可对集合中的元素规定一种次序，在集合和二进制之间建立对应关系。设Ua1，a2，an，对U的任意子集A，A与一个n位二进制数b1b2bn对应，其中bi1当且仅当aiA。对于一个n位二进制数b1b2bn，使之对应一个集合Aai|bi1。 例如，若Aa，b，c，则A的幂集为P(A)Ai|iJ，其中Ji|i是二进制数且000i111，其中A000，A011b，c等。 一般地P(A)Ai|iJ，其中Ji|i是二进制数且 i 。,2018/2/23,3.2 集合的运算与性质,3.2.1 集合的交、并、补 定义3.6 设A和B为两个集合，A和B的交集AB、并集AB分别定义如下：ABx|xAxBABx|xAxB 显然，AB是由A和B的公共元素组成的集合，AB由A和B的所有元素组成的集合。 例如，若A1，2，3，B1，4，则AB1，AB1，2，3，4。集合的交与并可以推广到n个集合的情况，即A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn,2018/2/23,例1 设A和B为两个集合，且AB，则ACBC。证明 对任意的xAC，则有xA且xC。而AB，由xA得xB，则xB且xC，从而xBC。所以，ACBC。例2 设A和B为两个集合，则ABABBABA。证明 对任意的xAB，则xA或xB。又AB，所以xB，于是ABB。又显然有BAB，故ABB。反之，若ABB，因AAB，所以AB。同理可证ABABA。,2018/2/23,2018/2/23,定理3.7 对于任意3个集合A、B和C，其交、并、补满足下面10个定律：(1)幂等律 AAA，AAA(2)结合律 (AB)CA(BC)，(AB)CA(BC)(3)交换律 ABBA，ABBA(4)分配律 A(BC)(AB)(AC)，A(BC)(AB)(AC)(5)同一律 AA，AUA,2018/2/23,(6)零律 AUU，A(7)互补律 A U，A (8)吸收律 A(AB)A，A(AB)A(9)德·摩根律 ， ，A(BC)(AB)(AC)，A(BC)(AB)(AC)(10)双重否定律 A以上等式的证明主要用到命题演算的等价式，即欲证集合AB，只需证明xAxB。也可利用已有的公式证明。,2018/2/23,定理3.8 任意集合A和B，B ABU且AB。证明 如B ，则ABA U，ABA 。反之，若ABU且AB，则BBUB(A )(BA)(B )(B )(A )(B )(AB) U 。例4 证明A(BC)(AB)(AC)。证明 因为xA(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)，所以A(BC)(AB)(AC)。,2018/2/23,例5 证明 。证明 因为x xABxAxBx x x ，所以 。例6 证明A(BC)(AB)(AC)。证明 因为xA(BC)xAx(BC)xA(xBxC)(xAxB)(xAxC)x(AB)x(AC)x(AB)(AC)，所以A(BC)(AB)(AC)。,