第3章 集合的基本概念和运算

刘师少

Tel：86613623（h）E-mail：lss_58@163.com授课:51学时

教学目标:知识、能力、素质DiscreteMathematics第三章集合的基本概念和运算§3.1 集合的基本概念§3.2 集合的基本运算§3.3 集合中元素的计数§3.4 例题分析

什么是集合？“所要讨论的一类对象的整体”；“具有同一性质单元的集体”“一些不同的确定对象的全体”。集合里所包含的每个对象（成员）叫做集合的元素（element）。§3.1集合的基本概念§3.1集合的基本概念用大写英文字母A，B，C，···表示集合用小写英文字母a，b，c，···等表示元素aA：表示a

是A的元素，读作“a属于A”a

A：表示a

不是A的元素，读作“a

不属于A”1.二十六个英文字母可以看成是一个集合；2.所有的自然数看成是一个集合；3.浙江中医药大学信息技术学院2008的本科学生可以看成是一个集合；4.这间教室中的所有座位可以看成是一个集合。例如:§3.1集合的基本概念注意：①集合中的元素不规定顺序如：C={2,1}={1,2}②集合中的元素各不相同。如：C={2,1,1,2}={2,1}③集合的元素也可以是一个集合如A={a，{1,2}，b，{b}} aA; {1,2}A; 1A;

④集合的元素可以是具体事物，可以是抽象概念，也可以是集体，不是集合的元素称为本元。如，一本书，一支笔，集合{1,2,3}可以组成集合B={一本书，一支笔，{1,2,3}}。特别地，以集合为元素的集合称为集合族或集合类如A={{1,2,3},{8,9,6}}。

⑤

集合中元素之间可以有某种关联，也可以彼此毫无关系。§3.1集合的基本概念约定，存在一个没有任何元素的集合，称为空集，记为，有时也用{}来表示。

空集是任何集合的子集约定，所讨论的对象的全体称为全集，记作E或U，我们所讨论的集合都是全集的子集。全集是相对的。空集、全集§3.1集合的基本概念有限集A中所含元素的个数称为集合的元数。记作：|A

|如：A

={1,3,2,4,5,9}则|A

|=

6

设A是所有英文字母组成的集合，则

A=26。

特别，||=0集合的元素数§3.1集合的基本概念

11.列举法

——将集合中的元素全部列出，写在花扩号内，元素间用“，”隔开。例

A={a，b，c，d}B={1，2，3，…}

集合的表示法

2．描述法(谓词表示法)

——将集合元素的条件或性质用文字或符号在花括号内竖线后面表示出来。例S1={x|x是正奇数}S2={y|y=a或y=b}A={x|x是中国的省名}C={(x,y)|(0x1)∧(0y1)}则，C表示平面上一个正方形区域。B={x|P(x)}B由使得P(x)为真的

x

构成

几类特殊集合

●全集E定义：包含所讨论的所有集合的集合，称之为全集，记作E。实际上，就是论域。它的文氏图如右图。由于讨论的问题不同，全集也不同。所以全集不唯一。例如，若讨论数，可以把实数集看成全集。若讨论人，可以把人类看成全集。E由于论域内任何客体x都属于E，所以x∈E为永真式。所以需要用永真式定义E。

E={x|P(x)∨P(x)}性质：对于任何集合A，都有AE。N={0,1,2,3,···}，即自然数集合。Z={···,-2,-1,0,1,2,3,···}，即整数集合。Z+={1,2,3,···}，即正整数集合。Q=有理数集合。R=实数集合。C=复数集合注意0是自然数.集合间有两种关系：包含关系和相等关系１．包含关系 定义３,1设A和B是任意两个集合，则 （1）若集合A中任一元素均属于B，则称B包含A，或A为B的子集，记作AB或BA。

ABx(xAxB)

（2）若A中至少有一元素不属于B，则记为AB。

ABx(xB∧xA)

（3）若B包含A且B中至少有一元素不属于A，则称A是B的真子集，记为AB。

ABx(xAxB)∧x(xB∧xA)

定义3.2设A、B是任意两个集合，若集合A与B有：AB且BA，则称A、B相等，记为A=B。

A=Bx(xAxB)

定义3：一个集合，如果它能包括我们所考虑的目标之内的所有元素，则此集合称为全集。记作E

。 显然，对任意集合A有：AE集合的相等与包含关系具有以下性质：

设A、B、C为任意集合，则：自反性：AA传递性：若AB且BC，则AC反对称性：若AB且BA，则A=B若AB且AC，则BC设A，B是两个集合，若B的元素都是A的元素，则称B是A的子集，也称A包含B，或B被A包含，记以BA

，或AB

。若BA

，且AB，则称B是A的真子集，也称A真包含B

，或B真包含于A

，记以AB，或BA。【定义3.3】子集§3.1集合的基本概念A={a,{b,c},d,{{d}}}例3.0已知集合A如下,选择或填空{b,c}

Ab

A{{d}}

A{d}

Ad

A

例3.1设A={a,b,{c},{a},{a,b}}

试判断下列表达式正确与否。（1）aA（2）{a}A（3）{a}

A（4）ØA（5）Ø

A（6）bA（7）{b}A（8）{b}

A（9）{a,b}

A

(10){a,b}A(11)cA(12){c}A(13){c}

A(14){a,b,c}A

(4)，(7)，(11)，(13),(14)错误。

例3.2对于任意集合A,B和C,下述论断是否正确（1）若AB,BC则AC（2）若AB,BC则AC（3）若AB,BC则AC

解：（1）√（2）×（3）×对(3)举反例A=Ø,B={1},C={{1}}解:(1)因为BC,所以集合B的每一个元素也是集合C的元素,由AB知A是B的一个元素,因此A也是C的一个元素,故AC(2)举反例:设A={a},B={{a},b},C={{a},b,{d}}

显然AB,BC,因为aA,但aC,所以AC。

(3)和(4)举反例:设A={a},B={a,b},C={{a,b},d},显然AB,BC,但AC。因为集合C中没有元素{a}。又因为集合A中的元素a不是集合C的元素。所以AC,例3.2'

对于任意集合A,B和C,下述论断是否正确（1）若AB,BC则AC

√（2）若AB,BC则AC（3）若AB,BC则AC

(4)若AB,BC则A

C

例3.3设A={{1,2,3},{4,5},{6,7,8}}下列选项正确的是（1）1A（2）{1,2,3}

A

（3）{{4,5}}

A（4）ØA

例3.4下列各选项错误的是（1）ØØ

（2）Ø

Ø

（3）Ø{

Ø}

（4）Ø{

Ø}

例3.5在0___Ø之间填上正确的符号（1）=

（2）

（3）

（4）

（3）√（2）×（4）如：A={1、3、4、5、6、2、0}B={2、3、4、0}C={1、7、2}则AB或BACA例3.6设P={x|(x+1)24},Q={x|x2+165x}

则下列选项上正确的是（1）PQ（2）PQ

（3）QP（4）P=Q

§3.1集合的基本概念（3）【定义3.3】真子集设A，B为集合，如果BA且B≠A，则称B是A的真子集,也称B被A真包含，或B真包含于A，或A真包含B，记作BA。如果B不被A真包含,则记作BA,或者BA

真子集的符号化表示为：BAA≠B∧BA例如：{0,1}{0,1,2}

{0,1,2}{1,2,3}§3.1集合的基本概念若B为A的真子集。即：AB也就是说

A中至少有一个元素不属于集合B

。如集合：A={a,c,e,q,p},B={c,e,p},C={a,p,m}则A

BAC§3.1集合的基本概念【定义3.4】空集

不含任何元素的集合叫做空集，记作φ

。空集的符号化表示为：

={x|P(x)P(x)}

其中P(x)为任何谓词公式。如：A={x|x∈R∧x2+1=0}.

该方程无实数解注意：φ≠{φ}由定义可知，对任何集合A，有A。这是因为任意元素x，公式xxA总是为真。注意：与{}是不同的。{}是以为元素的集合，而没有任何元素，能用构成集合的无限序列：(1)，{}，{{}}，···该序列除第一项外，每项均以前一项为元素的集合。§3.1集合的基本概念(2)，{}，{，{}}，···该序列除第一项外，每项均以前面各项为元素的集合。它即是冯·诺依曼在1924年使用空集给出自然数的集合表示：0:=，1:={}，2:={,{}}，···§3.1集合的基本概念定理3.1

空集是一切集合的子集。证明：对于任何集合A，由子集定义有,φAx(x∈φx∈A)

右边的蕴涵式中前件为x∈φ为假，所以整个蕴涵式对一切x为真，所以φA为真推论：空集是唯一的。证明:如不唯一,设存在空集φ1和φ2,由定理3.1得

φ1

φ2和φ2

φ1

根据集合相等的定义得，φ1=

φ2§3.1集合的基本概念定理3.1

空集是一切集合的子集。证明：对于任何集合A，由子集定义有,φAx(x∈φx∈A)

右边的蕴涵式中前件为x∈φ为假，所以整个蕴涵式对一切x为真，所以φA为真推论：空集是唯一的。证明:如不唯一,设存在空集φ1和φ2,由定理3.1得

φ1

φ2和φ2

φ1

根据集合相等的定义得，φ1=

φ2§3.1集合的基本概念注意符号和意义的区别：表示元素与集合之间的关系，而则表示集合与集合之间的关系。但由于集合的抽象性，集合中的元素可以是集合，故可以发生如：AB且AB的情形例3.7

设A={{1,2,3},{4,5},{6,7,8}}则

①{1,2,3}

A且

{{1,2,3}}

A

②{4,5}A且

{{4,5}}

A③{6,7,8}A且{{6,7,8}}

A特别提醒：对任意集合A,有AA。空集是任意集合的子集，且空集是唯一的。对于任意两个集合A、B，A=B的充要条件是AB且BA。重要结论§3.1集合的基本概念设A是集合，A的所有子集为元素做成的集合称为A的幂集,记以(A),(或A或２A)

符号化表示为

(A)={x|xA}例：

A={a,b,c}，则

(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}【定义3.5】幂集§3.1集合的基本概念换句话说:一个集合的幂集是指该集合所有子集的集合,即是由这些子集所组成的集合族计算方法Ａ＝{a,b,c}则P(A)={Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

C33C32C31C30|P(A)|＝＋＋＋例3.9设A={a,{a}}下列选项错误的是A.a(A)B.{a}(A)C.{{a}}(A)D.{{a}}(A)例3.10幂集P(P(P()))为（）A.{{

},{,{

}}}B.{,{,{

},{}}

C.{,{,{

}},{{}},{

}}D.{,{,{

}}}§3.1集合的基本概念∵P()={}P(P())=P({})={,{

}}

P(P(P()))=P(P({}))=P({,{

}})={,{

}{,{

}},{{

}}}∵P(A)={,{a},{{a}},{a,{a}}}

对选项⑴,因为{a,b}

中每个元素(只有a和b)均在集合{a,b,c,{a,b,c}}对选项⑶,因为{a,b}

中每个元素(只有a和b)均在集合{a,b,{{a,b}}}对选项⑵,集合{a,b,c,{a,b,c}}中含有4个元素，分别为a,b,c,{a,b,c}没有{a,b}，所以不正确。对选项⑷,集合{a,b,{{a,b}}}中含有3个元素，分别为a,b,{{a,b}}没有{a,b}，所以不正确。例3.10判断下面的关系是否正确,并简要说明理由⑴{a,b}{a,b,c,{a,b,c}}⑵{a,b}∈{a,b,c,{a,b,c}}⑶{a,b}

{a,b,{{a,b}}}⑷{a,b}∈{a,b,{{a,b}}}Cn2＋……Cn0Cn1Cnn＋＋＋Cn2＋…Cn0Cn1Cnn＋＋＋xn-1yxn-2y2xnynCn2＋……Cn0Cn1Cnn＋＋＋1.给定有限集合A，如果|A|=n,则|P(A)|=2n。证明：因为Ａ有n个元素，故P(A)中元素个数为而(x+y)n=令x=y=1时得

2n=所以|P(A)|=2n|2A|=2|A|=2n§3.1集合的基本概念幂集的性质2.x(A)当且仅当xA。3.设A、B是两个集合，AB当且仅当(A)(B)；幂集的性质§3.1集合的基本概念

集合运算是指用已知的集合去生成新的集合。假设所有集合都是全集E的子集，即这些集合是利用子集公理得到的。下面依次介绍常见的五种运算：

∩∪-～

§3.2集合的基本运算1.交运算∩定义：A、B是集合，由既属于A，也属于B的元素构成的集合,称之为A与B的交集,记作A∩B。例如A={1,2,3}B={2,3,4}A∩B={2,3}谓词定义：A∩B={x|x∈A∧x∈B}x∈A∩Bx∈A∧x∈B如果A∩B=Φ，则称A与B不相交。ABA∩B2.性质⑴幂等律对任何集合A，有A∩A=A。⑵交换律对任何集合A、B，有A∩B=B∩A。⑶结合律对任何集合A、B、C，有

(A∩B)∩C=A∩(B∩C)。⑷同一律对任何集合A，有A∩E=A。⑸零律对任何集合A，有A∩Φ=Φ。⑹ABA∩B=A。#include<stdio.h>#define N4#defineM6voidmain(){ inti,j,k; intA[4]={1,2,3,4},B[6]={1,2,3,8,9,10},C[N+M]; printf(“验证交集C=A∩B"); printf("\t"); k=0; for(j=0;j<M;j++) { for(i=0;i<N;i++) { if(B[j]==A[i]) { C[k]=B[j]; k++; break; }}} printf("\nC={"); for(i=0;i<k;i++) printf("%4d",C[i]); printf("}\n");}交集C=A∩B的程序实现2.并运算∪定义：A、B是集合，由或属于A，或属于B的元素构成的集合,称之为A与B的并集,记作A∪B。例如A={1,2,3}B={2,3,4}A∪B={1,2,3,4}谓词定义：A∪B={x|x∈A∨x∈B}x∈A∪Bx∈A∨x∈B性质⑴幂等律对任何集合A，有A∪A=A。⑵交换律对任何集合A、B，有A∪B=B∪A。

⑶结合律

对任何集合A、B、C，有

(A∪B)∪C=A∪(B∪C)。ABA∪B⑷同一律对任何集合A，有A∪Φ=A。⑸零律对任何集合A，有A∪E=E。⑹分配律对任何集合A、B、C，有

A∩(B∪C)=(A∩B)∪(A∩C)。

A∪(B∩C)=(A∪B)∩(A∪C)。⑺吸收律对任何集合A、B，有

A∪(A∩B)=AA∩(A∪B)=A。证明A∪(A∩B)=(A∩E)∪(A∩B)(同一)=A∩(E∪B)(分配)=A∩E=A(零律)(同一)⑻ABA∪B=B。#include<stdio.h>#define N4#defineM6voidmain(){ inti,j,k; intA[4]={1,2,3,4},B[6]={1,2,3,8,9,10},C[N+M]; printf("验证并集C=A∪B"); printf("\t"); for(i=0;i<N;i++) C[i]=A[i]; k=N; for(j=0;j<M;j++) { for(i=0;i<N;i++) { if(B[j]==A[i]) break; } if(i==N) { C[k]=B[j]; k++; }} printf("\nC={"); for(i=0;i<k;i++)

printf("%4d",C[i]); printf("}\n");}并集C=A∪B的程序实现3.差运算-(相对补集)定义：A、B是集合，由属于A，而不属于B的元素构成的集合,称之为A与B的差集,或B对A的相对补集，记作A-B。例如A={1,2,3}B={2,3,4}A-B={1}谓词定义：A-B={x|x∈A∧xB}x∈A-Bx∈A∧xB性质设A、B、C是任意集合，则⑴A-Φ=A⑵Φ-A=Φ⑶A-A=Φ⑷A-BAABA-B#include<stdio.h>#define N4#defineM6voidmain(){ inti,j,k; intA[4]={1,2,3,4},B[6]={1,2,3,8,9,10},C[N+M]; printf(“验证差集C=A-B"); //printf("\t"); k=0; for(i=0;i<N;i++) { for(j=0;j<M;j++) { if(B[i]==A[j]) break; } if(j==M) { C[k]=A[i]; k++; } } printf("\nC={"); for(i=0;i<k;i++) printf("%4d",C[i]); printf("}\n");}差集C=A-B的程序实现4.绝对补集~

定义：A是集合,由不属于A的元素构成的集合,称之为A的绝对补集,记作~A。

实际上~A=E-A。例如，E={1,2,3,4}A={2,3},~A={1,4}谓词定义：~A=E-A={x|x∈E∧xA}={x|xA}x∈~AxA性质设A、B、C是任意集合，则⑴~E=Φ⑵~Φ=E⑶~(~A)=A⑷A∩~A=Φ⑸A∪~A=E⑹A-B=A∩~BA~AE⑺~(A∩B)=~A∪~B⑻~(A∪B)=~A∩~B这两个公式称之为德-摩根定律。证明⑺：任取x∈~(A∩B)x∈~(A∩B)xA∩B(x∈A∧x∈B)(xA∨xB)x∈~A∨x∈~Bx∈~A∪~B∴~(A∩B)=~A∪~B⑼AB~B~A证明：ABx(x∈Ax∈B)

x(xBxA)x(x∈~Bx∈~A)

~B~A5.对称差定义：A、B是集合,由属于A而不属于B，或者属于B而不属于A的元素构成的集合,称之为A与B的对称差,记作AB。例如A={1,2,3}B={2,3,4}AB={1,4}

谓词定义：

AB=(A-B)∪(B-A)={x|(x∈A∧xB)∨(x∈B∧xA)}AB=(A∪B)-(A∩B)ABABE性质⑴

交换律对任何集合A、B，有AB=BA。⑵结合律对任何集合A、B、C，有

(AB)C=A(BC)。此式证明较繁，教材里有证明，这里从略。⑶同一律对任何集合A，有AΦ=A。⑷对任何集合A，有AA=Φ。⑸∩对可分配

A∩(BC)=(A∩B)(A∩C)证明：

(A∩B)(A∩C)=((A∩B)∪(A∩C))-((A∩B)∩(A∩C))=(A∩(B∪C))-(A∩B∩C)=A∩((B∪C)-(B∩C))(∩对-分配)=A∩(BC)只有一、二年级的学生才爱好体育运动

F:一年级大学生的集合S：二年级大学生的集合

R：计算机系学生的集合M：数学系学生的

T：选修离散数学的学生的集合

L：爱好文学学生的集合P:爱好体育运动学生的集合TM(RS)RST(MF)T=MLPPFSS(MR)P除去数学和计算机系二年级学生外都不选修离散数学所有计算机系二年级学生都选修离散数学数学系一年级的学生都没有选修离散数学数学系学生或爱好文学或爱好体育运动例3.9请指明下列的对应关系例2

例3.10分别对条件(1)到(5),确定X集合与下述那些集合相等。

S1={1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},S5={3,5}

若XS3=,则X

若XS4,XS2=,则X

若XS1，XS3,则X

若XS3=,则X

若

XS3，XS1,

则X=S2=S3,S5与S1,...,S5

都不等=S5=S1,S2,S4例3.11

证明A-(B∪C)=(A-B)∩(A-C).证明:对于x

x∈A-(B∪C)x∈A∧

x(B∪C)x∈A∧

(xB∧xC)x∈A∧

(xB∧xC)(x∈A∧xB)∧

(x∈A∧xC)x∈(A-B)∧x∈(A-C)x∈(A-B)∩(A-C)∴A-(B∪C)=(A-B)∩(A-C)§3.2集合的基本运算例3.12

证明A-(B∩C)=(A-B)∪(A-C).证明:对于x

x∈A-(B∩C)x∈A∧

x(B∩C)x∈A∧

(xB∨xC)(x∈A∧xB)

∨

(x∈A∧xC)x∈(A-B)∨x∈(A-C)x∈(A-B)∪(A-C)∴A-(B∩C)=(A-B)∪(A-C)§3.2集合的基本运算例3.13

证明A-B=A∩~B.证明:对于x

x∈A-B

x∈A

∧xB

x∈A∧x∈~B

x∈A∩~B∴A-B=A∩~B注意：此公式提供了一种将相对补运算转换为交运算的重要方法！§3.2集合的基本运算例3.14

利用代入已知恒等式证明

A∪(A∩B)=A.证明:A∪(A∩B)

=(A∩E)∪(A∩B)(公式3.7)=

A∩(E∪B)=

A∩E=

A∴A∪(A∩B)=A

P62列出了关于集合运算性质的一些重要结果，请注意掌握。§3.2集合的基本运算例3.15

证明CA∧CBCA∩B.证明1:先证“=>”对于x

x∈C=>x∈A∧x∈B(∵CA∧CB

)=>x∈A∩B∴CA∩B再证“<=”对于x

x∈C=>x∈A∩B(∵CA∩B

)=>x∈A∧x∈B

∴

CA∧CB§3.3

集合中元素的记数这节主要解决集合的计数问题。例如有AB两个商店，A店经营1000种商品，B店经营1200种商品，其中有100种商品两个商店都经营，问两个商店共经营多少种商品？显然

|A∪B|=|A|+|B|-|A∩B|如果有ABC三个商店，则|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|ABA∩BA∪B解：设A，B分别表示熟悉FORTRAN和PASCAL语言的程序员集合，将熟悉两种语言的对应人数23人添到A∩B的区域内，不难得到A-B和B-A的人数分别为A-B=A-A∩B=47-23=24B-A=B-A∩B=35-23=12从而得到A∪B=