1、集 合 论由于集合论的语言适合于描述和研究离散对象及其关系，所以也是计算机科学与工程的理论基础，在程序设计、关系数据库、形式语言和自动机理论等学科领域中都有重要的应用。本篇主要介绍：集合、二元关系和函数。第三章第三章集合集合1 1 集合的概念和表示法集合的概念和表示法2 2 集合的运算集合的运算3 3 集合中元素的计数集合中元素的计数1、集合与元素、集合与元素 （1）集合）集合 把人们直观的或想象中的某些确定的能够区分的对象把人们直观的或想象中的某些确定的能够区分的对象汇合在一起组成的一个整体。汇合在一起组成的一个整体。讨论：讨论：一些不同的确定的对象之全体。一些不同的确定的对象之全体。例：例
2、：10001000以内的素数的集合；以内的素数的集合；（集合）集合）这个班里高个子学生的集合；（不是集合）这个班里高个子学生的集合；（不是集合）1 集合的概念和表示法集合的概念和表示法元素（成员）：元素（成员）：组成集合的各个对象组成集合的各个对象。符号：符号：用大写英文字母表示集合，用小写英文字母或用大写英文字母表示集合，用小写英文字母或其它符号表示元素。其它符号表示元素。集合：集合：A，B.元素：元素：a，b.元素与集合间的关系：元素与集合间的关系：若若a是集合是集合S中的元素，则可中的元素，则可写成写成a S；若；若b不是集不是集S合中的元素，则可写成合中的元素，则可写成b S。集合也可
3、作为某一集合的元素。集合也可作为某一集合的元素。例：例：S=a,1,2,p,q 集合集合S的基数的基数(势势)：S中的元素个数。用中的元素个数。用|S|表示。表示。有限集合：集合的基数（元素）是有限的。有限集合：集合的基数（元素）是有限的。无限集合：集合的基数（元素）是无限的。无限集合：集合的基数（元素）是无限的。本书中常用集合符本书中常用集合符:I Im m(m1)(m1)有限个正整数的集合有限个正整数的集合1,2,31,2,3mm N Nm m(m0)(m0)有限个自然数的集合有限个自然数的集合0,1,20,1,2mm N N 自然数集合自然数集合 0,1,20,1,2 I+I+正整数集合
4、正整数集合 1,2,31,2,3 I I 整数集合整数集合 -1,0,1,2-1,0,1,2 Q Q 有理数集合有理数集合 i/j.ii/j.i、j j均为整数且均为整数且j0j0 R R 实数集合实数集合 有理数、无理数有理数、无理数 C C 复数集合复数集合 a+bia+bi，a a、b b可为实数可为实数(2)集合的表示方法集合的表示方法(a)枚举法枚举法(列举法列举法)把集合的元素列于花括号内。把集合的元素列于花括号内。例：例：命题的真假值组成的集合：命题的真假值组成的集合：S=T,F 自然数自然数0,1,2,3,4五个元素的集合：五个元素的集合：P=0,1,2,3,4(b)谓词公式描
5、述法谓词公式描述法所有集合均可用谓词公式来表示：所有集合均可用谓词公式来表示：S=x|p(x)例：大于例：大于10的整数的集合：的整数的集合：S1=x|x I x10 偶整数集合：偶整数集合：S2=x|y(y I x=2y)(c)同一集合可以用多种不同的形式表示。同一集合可以用多种不同的形式表示。S3=1,2,3,4,5=x|x I (1 x 5)S4=F,T=x|x=T x=F S5=1,4=x|(x-5x+4=0)(3)三个特殊集合：全集、空集、集合族三个特殊集合：全集、空集、集合族定义定义如果一个集合包含了所要讨论的每一个集合，则称如果一个集合包含了所要讨论的每一个集合，则称该集合为全集
6、合，简称全集，用该集合为全集合，简称全集，用E表示。表示。E=x|p(x)p(x)p(x)为任何谓词公式为任何谓词公式定义定义不拥有任何元素的集合称为空集，用不拥有任何元素的集合称为空集，用表示表示 =x|p(x)p(x)=注意：注意：，是空集，即没有元素的集合；是空集，即没有元素的集合；是是以以作为元素的集合。作为元素的集合。定义定义集合中的元素均为集合，称这样的集合为集合族。集合中的元素均为集合，称这样的集合为集合族。例例 A=a，b，c、d 2、集合之间的关系、集合之间的关系定义定义给定二个集合给定二个集合A和和B，当且仅当，当且仅当A和和B具有同样具有同样的元素（成员），则的元素（成员
7、），则A和和B才是相等的，记作才是相等的，记作A=B 并规定：（并规定：（A=B）x(x A x B)例：例：a,b,c=b,a,a,c,c 1,2,3=3,2,1 设设 P=1,2,4，Q=1,2,4，则，则P Q定义定义设设A、B是任意二个集合，如果集合是任意二个集合，如果集合A的每一个元的每一个元素都是素都是B的一个元素，则称的一个元素，则称A 是是B的子集，或者说的子集，或者说A包含包含于于B，或者说，或者说B包含包含A，记作，记作A B，或者，或者B A。记为：记为：A B B A x(x A x B)例：例：A1=1,2,3 A2=0 A3=1,2,3,0 B=1,2,3,0 则则
8、A1、A2、A3均为均为B的子集合，并记为的子集合，并记为 A1 B，A2 B，A3 B注意：区分注意：区分“”和和“”的关系的关系“”关系是指关系是指集合和该集合中元素集合和该集合中元素之间的关系。之间的关系。例：例：S=a,b,c 则则a S，b S，c S 而而“”关系是指关系是指二个集合二个集合之间的关系。之间的关系。例：例：S1=a,b S2=a,b,1,2 则则S1 S2 定义定义设设A、B是任意二个集合，若是任意二个集合，若A B且且AB，则，则称称A是是B的真子集，记作的真子集，记作A B（A真包含于真包含于B）记为：记为：A B（A B AB）例：例：A1=1,2,3 A2=
9、0 B=1,2,3,0 则则A1、A2 均为均为B的真子集，并记为的真子集，并记为 A1 B，A2 B定理定理设设A、B是任意二个集合，当且仅当是任意二个集合，当且仅当A B和和B A才有才有A=B。证明：证明：()充分性：（充分性：（A=B）（A B B A）(A=B)x(x A x B)x(x A x Bx B x A)x(x A x B)x(x B x A)(A B)(B A)()必要性：必要性：A BB A A=B(A B)(B A)x(x A x B)x(x B x A)x(x A x Bx B x A)x(x A x B)(A=B)定理定理对于任一集合对于任一集合A，则有，则有A
10、A。定理定理设有空集设有空集和任一集合和任一集合A，则，则A 证明：设证明：设x A，要证明，要证明A 只要证：只要证：x(x x A)为为“T”中没有元素中没有元素 x为假，为假，x（x x A）为）为“T”则则 A 定理定理设设E E是全集，是全集，A A是一个集合，则一定有是一个集合，则一定有A A E E。定理定理设设A A、B B、C C是任意集合，如果是任意集合，如果A A B B和和B B C C，则，则A A C C。推论推论若若A A B B和和B B C C，则，则A A C C。定理定理 是唯一的是唯一的。证明：设有二个空集合证明：设有二个空集合1 1和和2 2 是任何集
11、合的子集是任何集合的子集 （1 1 2 22 2 1 1）(1 1=2 2)是唯一的是唯一的。3、幂集和索引集合、幂集和索引集合（1）幂集）幂集定义定义 设设A A是集合，是集合，A A的所有子集（作为元素）构成的集的所有子集（作为元素）构成的集合称为合称为A A的幂集。的幂集。记作记作(A)(A)，且有：且有：(A)=x|x(A)=x|x A A 例：若例：若A1=A1=，其子集为：，其子集为：，则则 (A1)=(A1)=若若A2=aA2=a，其子集为：，其子集为：，a a，则，则 (A2)=(A2)=，aa 若若A3=1A3=1，22，其子集为：，其子集为：，11，22，11，22 则则
12、(A3)=(A3)=，11，22，11，22 注：注：|(S)|=2(S)|=2|s|s|为幂集为幂集(S)(S)的基数的基数 （2 2）索引集合）索引集合 为了在计算机上表示集合，必须给每一个集合的元素为了在计算机上表示集合，必须给每一个集合的元素加上标记，以用来表示元素在集合中的位置。加上标记，以用来表示元素在集合中的位置。例：例：S1=aS1=a，b b 假设集合假设集合S1S1中，中，a,ba,b的位置已经固定。的位置已经固定。则用二进制下标法来表示则用二进制下标法来表示S S的所有子集：的所有子集：=B=B0000，a=Ba=B1010，b=Bb=B0101，aa，b=Bb=B111
13、1 则则(S1)=B(S1)=B0000，B B0101，B B1010，B B1111=B=Bi i|i i J J 其中其中J=00J=00，0101，1010，11 11（索引集合或指标集合）（索引集合或指标集合）2 集合的运算集合的运算 1.交集（交运算）交集（交运算）定义定义任何二个集合任何二个集合A和和B的交集的交集AB是由是由A和和B所共所共有的全部元素构成的集合。有的全部元素构成的集合。记作：记作：AB=x|x A x B 例：例：A=a，b B=a，c A B=a A BAB2 集合的运算集合的运算 定理定理 集合的相交运算是集合的相交运算是可交换可交换的和的和可结合可结合的
14、，即对的，即对于任何集合于任何集合A，B，C有有 A B=B A (可交换可交换)（AB）C=A（BC）(可结合可结合)证明：设证明：设x是是AB中任一元素中任一元素 则则x AB x x|x A x B x x|x B x A x BA AB=BA 定理定理设设A是是E的任一子集，则有的任一子集，则有（1）A A=A（2）A =（3）A E=A2.并集（并运算）并集（并运算）定义定义 A、B是任意二个集合，是任意二个集合，A和和B的并集的并集AB是由是由A和和B的所有元素构成的集合。的所有元素构成的集合。记作：记作：AB=x x Ax B 例：例：A=a,b,c,B=1,2,3，则，则 AB
15、=a,b,c,1,2,3 A BAB定理定理集合的并运算是集合的并运算是可交换可交换和和可结合可结合的的.AB=BA (可交换可交换)（AB）C=A（BC）(可结合可结合)定理定理设设A、B、C是全集是全集E的任意子集，则有：的任意子集，则有：(1)AA=A (2)A=A (3)AE=E定理定理集合的并和交运算满足分配律，即并对交分配，集合的并和交运算满足分配律，即并对交分配，交对并分配。交对并分配。(1)A（BC）=（AB）（AC）(并对交分配并对交分配)(2)A（BC）=（AB）（AC）(交对并分配交对并分配)定理定理设设A，B，C，D是是E的子集，则有：的子集，则有：(1)若若A B和和
16、C D，则，则A C B D (2)若若A B和和C D，则，则AC BD (3)若若A A B，则，则 B A B (4)若若A B A，则，则A B B (5)若若A B，则，则AB=B (6)若若A B，则，则A B=A3.相对补集相对补集定义定义设设A和和B是二个任意集合，是二个任意集合，B对对A的相对补集的相对补集（A B）是由属于）是由属于A且不属于且不属于B的所有元素组成的集合。的所有元素组成的集合。记作：记作：A B=xx Ax B 例：设例：设A=0，1，2，B=2，3，4 则则 A B=0,1 ，B A=3，4 A B B A，相对补集不满足交换律。，相对补集不满足交换律。
17、定理定理设设A，B，C，D是是E的子集，则有：的子集，则有：(1)A B A (2)A =A (3)A A=(4)A (B A)=(5)A(B A)=AB4、绝对补集（补运算、绝对补集（补运算）定义定义设设E是全集，任一集合是全集，任一集合A对对E的相对补集称为的相对补集称为A的绝对补集（或称补集），记作的绝对补集（或称补集），记作A（或（或 A）。）。即：即：A=E A=x|x E x A 例：设例：设 E=a，b，c，d，A=a，b 则则 A=c，d AA定理：补集的性质如下：定理：补集的性质如下：(1)A A=E (2)A A=(3)（A）=A (4)（AB）=A B (5)（A B）=
18、AB (6)=E (7)A B=A B 例：设例：设 A=2，5，6，B=2，3，4，E=1，2，3，4，5，6则则 A B=5，6 A B=2，5，6 1，5，6=5，6 A B=A B 5、环和、环和(对称差对称差)定义定义设设A、B是任意二集合，是任意二集合，A和和B的环和记作的环和记作A B。即：即：A B=(A B)(B A)=(AB)(A B)或者或者 x (A B)x x|x A x B 例：设例：设A=2，5，6，B=2，3，4 则则 A B=3，4，5，6 A BAB定理：对称差的性质：定理：对称差的性质：(1)A B=B A (可交换可交换)(2)(A B)C=A (B C
19、)(可结合可结合)(3)A A=(4)A =A(5)A (B C)=(A B)(A C)(对对 是可以分配的是可以分配的)6、文氏图、文氏图(1)文氏图的画法规则：文氏图的画法规则：规定矩形表示规定矩形表示E,子集用圆画在子集用圆画在E中。中。(2)文氏图应用：文氏图应用：（a）表示集合和运算的关系）表示集合和运算的关系 可用文氏图画出各种运算可用文氏图画出各种运算（b）证明集合恒等式）证明集合恒等式 如右图所示：如右图所示：ABA B=下图中的阴影部分表示了每个图下边所指出的集合的下图中的阴影部分表示了每个图下边所指出的集合的运算。运算。AAA BABA BABA BAB3 集合中元素的计数集合中元素的计数n包含排斥原理：包含排斥原理：设设A1A1，A2A2为有限集，其元素个数分别为为有限集，其元素个数分别为|A1|A1|，|A2|A2|，则：则：121212|(|)|AASAAAA121212|(|)|AAAAAA推论：推论：|)|(|21321321AAAAASAAA|3213231AAAAAAA如果涉及到三个集合，包含排斥原理的公式则变成：.123123121323123|(|)|AAAAAAAAAAAAAAA
