《集合的基本概念和运算》由会员分享，可在线阅读，更多相关《集合的基本概念和运算（75页珍藏版）》请在金锄头文库上搜索。
1、集合论分两种体系： 朴素集合论体系（康托集合论体系）要讨论的 公理集合论体系 集合论的特点是研究对象的广泛性 集合论总结出由各种对象构成的集合的共同性质，并用统一的方法来处理 作为计算机科学与工程的理论基础，广泛应用于程序设计、关系数据库、操作系统等学科,第3章 集合的基本概念和运算,3.1 集合的基本概念与表示 3.2 集合的基本运算 3.3 集合元素的计数 3.4 例题选解 习 题 三,3.1 集合的基本概念与表示,一些不同对象的全体称为集合，通常用大写的英文字母A, B, C表示。 严格地说这算不得集合的定义，因为“全体”只是“集合”一词的同义反复。在集合论中，集合是一个不能严格定义的原
2、始概念（就像几何学中的点、线、面等概念）。 对象： 组成集合的元素。用小写英文字母a, b, c表示。,如果a是A的元素，则记为 aA，读作“a属于A”或“a在集合A之中”。 如果a不是A的元素，则记为aA或 (aA)， 读作“a不属于A”或“a不在集合A之中”。 其中“”表示一种关系。 在我们所研究的集合论（古典集合论）中，对任何对象a和任何集合A，或者aA或者 aA, 两者必居其一且仅居其一。这正是集合对其元素的“确定性”要求。,集合有三个特性：确定性、互异性和无序性。 (1) 确定性：aA或aA，二者必居其一并仅居其一。 (2) 互异性： 1，2，3，2 与1，2，3视作一个集合。 (3
3、) 无序性： 1，2，3、 2，3，1 与3，1，2 视为一个集合。 集合A中的不同的元素的数目，可称为集合A的基数或者势，记为|A|。 基数有限的集合称为有穷集合，否则称为无穷集合。,表示一个集合的方法通常有两种: 列举法 描述法 （1） 列举法：将集合的元素列举出来并写在一个花括号里，元素之间用逗号分开。例如，设A是由a, b, c, d元素构成的集合，B是由a, b, c, d为元素构成的集合，则A=a, b, c, d, B=a, b, c, d ，集合B说明集合也可用作元素，因此，尽管集合与其元素是两个截然不同的概念，但一个集合完全可以成为另一个集合的元素。,列举法基本上用于有限集合
4、，如果能说明集合的特征，也可只列出部分元素，其余的用省略号表示。如自然数集可用列举法表示为 N =0, 1, 2, 3, 4, 5, , 根据所列元素，可判断 N 中的其余元素。 列举法使集合中的元素一目了然，但是元素个数很多时使用起来就很麻烦，另外，有很多集合，如大于0而小于1的所有实数的集合就不能用列举法表示。为此引入另一种表示方法。,（2） 描述法：规定一个集合A时，将A中元素的特征用一个谓词公式来描述，用谓词P(x)表示x具有性质P，用x|P(x) 表示具有性质P的集合A, 即A=x|P(x)。它表示集合A是使P(x)为真的所有元素x构成的集合，P(x)是任意谓词。 P(a)为真的充分
5、必要条件是aA, P(a)为假的充分必要条件是aA。,【例3.1.1】 (1) 设P(x) :x 是英文字母，则S=x|P(x) 表示26个英文字母的集合。 (2) N =0， 1， 2， 3， =x|x是自然数 ( 3) I+ =1， 2， 3， =x|x是正整数 (4) I ， -3， -2， -1， 0， 1， 2， 3， =x|x是整数 (5) Im0， 1， 2， ， m-1 x|xN0xm,（6） E ， -4， -2， 0， 2， 4， x|x是偶数 x|xI2|x (2|x表示2整除x) （7） 前n个自然数集合的集合 0, 0 , 1， 0， 1， 2， x|x=Inn I+
6、 In|n I+,由此可见，表示一个集合的方法是很灵活多变的，必须注意准确性和简洁性。为方便起见，本书中指定下列常见数集符号： N (Natural) 表示自然数集合（含0） I (Integer) 表示整数集合, 本书中我们也常用 Z表示整数集合 Q (Quotient) 表示有理数集合 R (Real) 表示实数集合 C (Complex) 表示复数集合 P (proton) 表示素数集合,定义3.1.1 设A、B为任意两个集合，如果A的每一个元素都是B的元素，则称集合A为集合B的子集合（或子集，subsets），表示为AB（或 BA），读作”A包含于B”（或“B包含A”）。其符号化形式为
7、 ABx(xAxB) A不是B的子集，则记作AB，其符号化形式为 ABx(xAxB ),集合之间的子集关系或包含关系是集合之间最重要的关系之一。读者必须彻底弄清子集关系和包含关系这两个完全不同的概念。集合的包含具有下列性质： （1） 自反性： AA; （2） 传递性： AB且 BC, 则AC; （3） AB且AC, 则BC。,【例3.1.2】 a，b a，c，b，d， a，b，c a，b，c， aa，b， 但aa，b， 只有aa，b 。 不过存在这样两个集合， 其中一个既是另一个的子集，又是它的元素。例如， aa， a，且aa， a。 定义3.1.2 设A、 B为任意两个集合，若B包含A同时A
8、包含B，则称集合A和B相等，记作A=B。 即对任意集合A、B，有 A=BABBAx（xAxB),定义3.1.3 设A、 B为任意两个集合, 若 A是B的子集且AB，则称A是B的真子集或称B真包含A，记为AB。 即 ABAB且AB 若集合A不是集合B的真子集，则记为AB ， 其符号化形式为 ABx(xAxB)(A=B)ABA=B,集合的真包含具有下列性质： （1） 反自反性： AA; （2） 传递性： 若AB且 BC, 则AC; （3） 反对称性： 若AB， 则BA。 定义3.1.4 没有任何元素的集合称为空集合，简称为空集， 记为。 例如， |=0， |=1。,定理3.1.1 空集是任意集合的
9、子集， 即对任何集合A， A。 证明 因x恒假， 故x(xxA)恒真， 即A恒真。 推论 空集是唯一的。 证明 设有空集 。 据定理3.1.1， 应有 和 ， 从而由定义3.1.2知 = 。,2,1,由推论可知，空集无论以什么形式出现， 它们都是相等的，所以 x|xx=x|x R x2+1=0=x|P(x) P(x)， P(x)是任意谓词.,定义3.1.5 在一定范围中，如果所有集合均为某一集合的子集，则称某集合为全集，常记为E ，即 x(xE )为真，因此 E x|P(x) P(x) ， P(x)是任意谓词 因为只要求全集包含我们讨论的所有集合，具有相对性，所以根据讨论的问题不同，可以有不同
10、的全集，即全集不是唯一的。但是为了方便起见，在以后的讨论中我们总是假定有一个足够大的集合作为全集E ，至于全集E是什么，我们有时不关心。,定理 3.1.2 设A为一有限集合， |A|=n， 那么A的子集个数为2n。,定义3.1.6 给定集合A， 由A的所有子集为元素构成的集合， 称为集合A的幂集， 记作P(A)， 即 P(A)x|xA。 由于A, AA， 故必有P(A), AP(A)。 例如： A=, P(A)= A=a, P(A)=, a A=a, b, P(A)=, a, b, a, b 显然，幂集元素的个数与集合A的元素个数有关，且当集合A的基数为n时，A有2n个子集，因此 |P(A)|
11、=2 n。,【例3.1.3】 设A=, ， B=, , , ， 求P(A)和P(B)。 解 P(A)=, , , , P(B)= , , , , , , , , , , , , , , , , ,定理3.1.3 设A, B为任意集合, AB当且仅当P(A)P(B)。 证明 先证必要性。 设AB， 为证P(A)P(B)， 又设X为P(A)中任一元素， 从而XA。 由于AB， 故XB， 从而有XP(B)。 P(A)P(B)得证. 再证充分性。 设P(A)P(B)， 又设x为A中任意元素，从而xA。考虑单元素集合x， xA, 所以xP(A)。 由于 P(A)P (B)， 因此xP(B), xB, x
12、B， 因此 AB得证。,3.2 集合的基本运算,集合的运算指以集合为运算对象，按照某种规律生成一个新的集合的运算。 定义3.2.1 设A， B为任意两个集合。由那些或属于A或属于B或同时属于二者的所有元素构成的集合称为A与B的并集（union set），记为AB。 形式化为 ABx|xAxB 称为并运算。,定理3.2.1 对任意集合A, B， 有 AAB BAB 该定理由定义3.2.1可直接得出。 定义3.2.2 设A，B为任意两个集合。由集合 A 和 B 所共有的全部元素构成的集合称为A与B的交集（intersection set）, 记为AB。形式化为 AB=x|xAxB 称为交运算。 下
13、面定理介绍交运算的性质。,定理3.2.2 对任意集合A, B， 有 ABA ABB 该定理由定义3.2.2可直接得出。 定义3.2.3 设A，B为任意两个集合。由属于A但不属于集合 B 的所有元素构成的集合称为A与B的差集（difference set），记为A-B，又称为相对补。 形式化为 A-Bx|xAxB -称为差运算。 下面定理介绍差运算的性质。,定理3.2.3 对任意的集合A, B, C， 有 （1） A-B=A-(AB) （2） A(B-A)=AB （3） A(B-C)=(AB)-C （4） A-BA,定义3.2.4 设A为任意集合, E 是全集。对于E和 A所进行的差运算称为A的
14、补集（complement set）， 也称为A 对 E 的相对补集，称为 A 的绝对补集，或简称为 A 的补集， 记为A。 即 A=E -A=x|xA 称为补运算， 它是一元运算， 是差运算的特例。 下面定理介绍补运算的性质。,定理3.2.4 对任意的集合A, B, 若AB, 则BA。,【例3.2.1】 设E 0, 1， 2， 3， ，9, 10， A=2，4， B=4, 5, 6 , 7，C=0，8，9， Dl, 2, 3, 10， 则 AB2， 4， 5， 6， 7 ABCDE AB 4 AC A-B 2 B-A5， 6， 7 A- C2， 4 A0， l， 3， 5， 6， 7， 8， 9, 10 B0， l， 2， 3， 8， 9,命题代数与集合代数，两者都是一种称为 Boole代数的抽象代数的特定情况。这个事实说明了，为什么命题演算中的各种运算，与集合论中的各种运算极为相似。在此，将列举若干集合恒等式，它们都有与其相对应的命题等价式。下面介绍集合运算的恒等式。,定理3.2.5 设A，B，C为任意集合，那么下列式成立。 （l） 等幂律 AA A AA A （2） 交换律 AB BA
