离散数学 第六章

更新时间:2024-05-30 10:57:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

第二部分 集合论

引言

集合是数学中最为基本的概念,又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。集合论是离散数学的重要组成部分,是现代数学中占有独特地位的一个分支。

G.康托尔是作为数学分支的集合论的奠基人。1870年前后,他关于无穷序列的研究导致集合论的系统发展。1874年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。1878年,他引进了两个集合具有相等的“势”的概念。然而,朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901年罗素发现了有名的罗素悖论。1932年康托尔也发表了关于最大基数的悖论。 集合论的现代公理化开始于1908年E.策梅罗所发表的一组公理,经过A.弗兰克尔的加工,这个系统称为策梅罗-弗兰克尔集合论(ZF),其中包括1904年策梅罗引入的选择公理。另外一种系统是冯*诺伊曼-伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设(CH)。K.哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性,P.J.科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理一起称为ZFC系统。

本部分主要介绍朴素集合论的主要内容,其中包括集合代数(第六章)、二元关系(第七章)、函数(第八章)、集合的基数(第九章)等。 本部分的先行知识及各部分的关系如下图所示:

6.1 集合的基本概念

一.集合的表示

集合是不能精确定义的基本概念。直观地说,把一些事物汇集到一起组成一个整体就叫集合,而这些事物就是这个集合的元素或成员。例如:

方程x2-1=0的实数解集合;

26个英文字母的集合;

坐标平面上所有点的集合;

……

集合通常用大写的英文字母来标记,例如自然数集合N(在离散数学中认为0也是自然数),整数集合Z,有理数集合Q,实数集合R,复数集合C等。

表示一个集合的方法有两种:列元素法和谓词表示法,前一种方法是列出集合的所有元素,元素之间用逗号隔开,并把它们用花括号括起来。例如

A={a,b,c,…,z}

Z={0,±1,±2,…}

都是合法的表示。谓词表示法是用谓词来概括集合中元素的属性,例如集合

B={x|x∈R∧x2-1=0}

表示方程x2-1=0的实数解集。许多集合可以用两种方法来表示,如B也可以写成{-1,1}。但是有些集合不可以用列元素法表示,如实数集合。

集合的元素是彼此不同的,如果同一个元素在集合中多次出现应该认为是一个元素,如

{1,1,2,2,3}={1,2,3}

集合的元素是无序的,如

{1,2,3}={3,1,2}

在本书所采用的体系中规定集合的元素都是集合。

元素和集合之间的关系是隶属关系,即属于或不属于,属于记作∈,不属于记作,例如

A={a,{b,c},d,{{d}}}

这里a∈A,{b,c}∈A,d∈A,{{d}}∈A,但bA,{d}A. b和{d}是A的元素的元素。可以用一种树形图来表示这种隶属关系,该图分层构成,每个层上的结点都表示一个集合,它的儿子就是它的元素。上述集合A的树形图如图6.1所示。图中的a,b,c,d也是集合,由于所讨论的问题与a,b,c,d的元素无关,所以没有列出它们的元素。鉴于集合的元素都是集合这一规定,隶属关系可以看作是处在不同层次上的集合之间的关系。

为了体系上的严谨性,我们规定:对任何集合A都有A

A。

二.集合之间的关系

下面考虑在同一层次上的两个集合之间的关系。

定义6.1 设A,B为集合,如果B中的每个元素都是A中的元素,则称B是A的

子集合,简称子集。这时也称B被A包含,或A包含B,记作B

如果B不被A包含,则记作B

包含的符号化表示为

B

例如N

显然对任何集合A都有A

A。

Z

Q

R

C,但Z

N。

A

x(x∈B→x∈A)

A。

A。

隶属关系和包含关系都是两个集合之间的关系,对于某些集合可以同时成立这两种关系。例如

A={a,{a}}和{a}

既有{a}∈A,又有{a}

A。前者把它们看成是不同层次上的两个集合,后者把它们看

成是同一层次上的两个集合,都是正确的。

定义6.2 设A,B为集合,如果A

如果A与B不相等,则记作A≠B。

相等的符号化表示为

A=B

A

B∧B

A

B且B

A,则称A与B相等,记作A=B。

定义6.3 设A,B为集合,如果B

A。

如果B不是A的真子集,则记作B

真子集的符号化表示为

B

例如N

Z

Q

R

C,但N

A

B

A∧B≠A

A且B≠A,则称B是A的真子集,记作B

A。

N。

定义6.4 不含任何元素的集合叫做空集,记作

空集可以符号化表示为

={x|x≠x}。

例如{x|x∈R∧x2+1=0}是方程x2+1=0的实数解集,因为该方程无实数解,所以是空集。

定理6.1 空集是一切集合的子集。

右边的蕴涵式因前件假而为真命题,所以

A也为真。

A

x(x∈

→x∈A)

证:任何集合A,由子集定义有

推论 空集是唯一的。

根据集合相等的定义,有

1

1

2

证:假设存在空集

1

2

,由定理6.1有

21

2

含有n个元素的集合简称n元集,它的含有m(m≤n)个元素的子集叫做它的m元

子集。任给一个n元集,怎样求出它的全部子集呢?举例说明如下。 例6.1 A={1,2,3},将A的子集分类:

0元子集,也就是空集,只有一个:

1元子集,即单元集:{1},{2},{3};

2元子集:{1,2},{1,3},{2,3};

3元子集:{1,2,3}。

一般地说,对于n元集A,它的0元子集有

个,1元子集有

个,…,m

元子集有

个,…,n元子集有个。子集总数为

+++…+=2n 个。

定义6.5 设A为集合,把A的全部子集构成的集合叫做A的幂集,记作P(A)(或

PA,2A)。

幂集的符号化表示为

P(A)={x|x

A}

对于例6.1中的集合A有

P(A)={

,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

不难看出,若A是n元集,则P(A)有2n个元素。

定义6.6 在一个具体问题中,如果所涉及的集合都是某个集合的子集,则称这个集

合为全集,记作E。

全集是有相对性的,不同的问题有不同的全集,即使是同一个问题也可以取不同的全集。例如在研究平面上直线的相互关系时,可以把整个平面(平面上所有点的集合)取作全集,也可以把整个空间(空间上所有点的集合)取作全集。一般地说,全集取得小一些,问题的描述和处理会简单些。

6.2 集合的运算

一.集合的基本运算

集合的基本运算有并,交,相对补和对称差。

定义6.7 设A,B为集合,A与B的并集A∪B,交集A∩B,B对A的相对

补集A-B分别定义如下:

A∪B={x|x∈A∨x∈B }

A∩B={x|x∈A∧x∈B }

A-B={x|x∈A∧xB }

由定义可以看出,A∪B是由A或B中的元素构成,A∩B由A和B中的公共元素构成,A-B由属于A但不属于B的元素构成。例如

A={a,b,c},B={a},C={b,d} 则有

A∪B={a,b,c},A∩B={a},A-B={b,c},

B-A=

如果两个集合的交集为的。

两个集合的并和交运算可以推广成n个集合的并和交: A1∪A2∪…∪An={x|x∈A1∨x∈A2∨…∨x∈An} A1∩A2∩…∩An={x|x∈A1∧x∈A2∧…∧x∈An} 上述的并和交可以推广成n个集合的并和交:

,则称这两个集合是不相交的。例如B和C是不相交,B∩C=

=A1∪A2∪…∪An

=A1∩A2∩…∩An

并和交运算还可以推广到无穷多个集合的情况:

=A1∪A2∪…

=A1∩A2∩…

定义6.8 设A,B为集合,A与B的对称差集A

A

例如A={a,b,c},B={b,d},则A

对称差运算的另一种定义是

A

B=(A∪B)-(A∩B) B=(A-B)∪(B-A)

B定义为:

B={a,c,d}。

可以证明这两种定义是等价的,证明可留作练习。

在给定全集E以后,A

E,A的绝对补集~A定义如下:

定义6.9 ~A=E-A={x|x∈E∧x

A}

因为E是全集,x∈E是真命题,所以~A可以定义为

~A={x|xA }

例如E={a,b,c,d},A={a,b,c},则~A={d}。

以上集合之间的关系和运算可以用文氏图(Venn Diagram)给予形象的描述。文氏图的构造方法如下:

首先画一个大矩形表示全集E(有时为简单起见可将全集省略),其次在矩形内画一些圆(或任何其它的适当的闭曲线),用圆的内部表示集合。不同的圆代表不同的集合。

如果没有关于集合不交的说明,任何两个圆彼此相交。图中阴影的区域表示新组成的集合。图6.2就是一些文氏图的实例。

二.有穷计数集

使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来。一般地说,每一条性质决定一个集合。有多少条性质,就有多少个集合。如果没有特殊说明,任何两个集合都画成相交的,然后将已知集合的元素数填入表示该集合的区域内。通常从n个集合的交集填起,根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的,可以设为x。根据题目中的条件,列出一次方程或方程组,就可以求得所需要的结果。

例6.2 对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下:会

英、日、德和法语的人分别为13,5,10和9人,其中同时会英语和日语的有2人,会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语,分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。

解 令A,B,C,D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图如图6.3所示。设同时会三种语言的有x人,只会英、法或德语一种语言的分别为y1,y2和y3人。将x和y1,y2,y3填入图中相应的区域,然后依次填入其它区域的人数。

根据已知条件列出方程组如下:

解得x=1,y1=4,y2=2,y3=3。

例6.3 求1到1000之间(包含1和1000在内)既不能被5和6,也不能被8整除得

数有多少个。

解 设

S={x|x∈Z∧1≤x≤1000}

A={ x|x∈S∧x可被5整除}

B={ x|x∈S∧x可被6整除}

C={ x|x∈S∧x可被8整除}

用|T|表示有穷集T中得元素数,表示x1,x2,…,xn的最小公倍数,则有

|A|=

|B|=

=166 =200

表示小于等于x的最大整数,lcm(x1,x2,…,xn)

|C|=

|A∩B|=

|A∩C|=

|B∩C|=

|A∩B∩C|=

=8 =41 =25 =33

=125

将这些数字依次填入文氏图,得到图6.4.由图可知,不能被5,6和8整除的数有

1000-(200+100+33+67)=600个。

三.广义交和广义并

以上定义的并和交运算称为初级并和初级交。下面考虑推广的并和交运算,即广义并和广义交。

定义6.10 设A为集合,A的元素的元素构成的集合称为A的广义并,记为∪A。

符号化表示为

∪A={x|

z(z∈A∧x∈z)}。

例6.4 设

A={{a,b,c},{a,c,d},{a,e,f}} B={{a}} C={a,{c,d}} ∪A={a,b,c,d,e,f} ∪B={a} ∪C=a∪{c,d}

∪=

根据广义并定义不难证明,若A={ A1,A2,…,An},则∪A=A1∪A2∪…∪An。

类似地可以定义集合的广义交。

定义6.11 设A为非空集合,A的所有元素的公共元素构成的集合称为A的广义交,记为∩A。符号化表示为

∩A={x|

z(z∈A→x∈z)}

考虑例6.4中的集合,有

∩A={a},∩B={a},∩C=a∩{c,d}

细心的读者一定会注意到在定义6.11中特别强调了A是非空集合。对于空集以进行广义并,即∪

。但空集

不可以进行广义交,因为∩

不是集合,在集

合论中是没有意义的。

和广义并类似,若A={A1,A2,…,An},则∩A=A1∩A2∩…∩An。

在后面的叙述中,若只说并或交,则这都是指集合的初级并或初级交;如果在并或交前边冠以“广义”两个字,则指集合的广义并或广义交。

为了使得集合表达式更为简洁,我们对集合运算的优先顺序做如下规定:

称广义并,广义交,幂集,绝对补运算为一类运算,并,交,相对补,对称差运算为二类运算。

一类运算优先于二类运算。

一类运算之间由右向左顺序进行。

二类运算之间由括号决定先后顺序。

例如下面的集合公式:

∩A-∪B,∪P(A),~P(A)∪∪B,~(A∪B)

都是合理的公式。

例6.5 设

A={{a},{a,b}}

计算∪∪A,∩∩A和∩∪A∪(∪∪A-∪∩A)。 解 ∪A={a,b} ∩A={a} ∪∪A=a∪b ∩∩A=a ∩∪A=a∩b ∪∩A=a

∩∪A∪(∪∪A-∪∩A) =(a∩b)∪((a∪b)-a) =(a∩b)∪(b-a) =b

所以∪∪A=a∪b,∩∩A=a,∩∪A∪(∪∪A-∪∩A)=b。

6.3 集合恒等式

一.基本集合恒等式

下面的恒等式给出了集合运算的主要算律,其中A,B,C代表任意集合。

幂等律 A∪A=A (6.1)

A∩A=A (6.2)

结合律 (A∪B)∪C=A∪(B∪C) (6.3)

(A∩B)∩C=A∩(B∩C) (6.4)

交换律 A∪B=B∪A (6.5)

A∩B=B∩A (6.6)

分配律 A∪(B∩C)=(A∪B)∩(A∪C) (6.7)

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

同一律 A∪

=A (6.9)

A∩E=A (6.10)

零律 A∪E=E (6.11)

A∩

(6.12)

排中律 A∪~A=E (6.13)

(A

A

A

A

B=A

C

B=C (6.33)

A=

(6.32) =A (6.31) B)

C=A

(B

C) (6.30)

式6.29~6.33是关于对称差运算的算律,前四条可通过对称差的定义加以证明,最后一条叫做消去律,它的证明给在下面。

例6.13 已知A

A

主要内容

B=AC,证明B=C。

证 已知A

B=AC,所以有

(AB)=A(AC)

(AA)B=(AA)C (由式6.30)

B=C (由式6.32)

B=C (由式6.29)

B=C (由式6.31)

1. 集合,相等,(真)包含,子集,空集,全集,幂集 2. 交,并,(相对和绝对)补,对称差,广义交,广义并 3. 文氏图,有穷集计数问题

4. 集合恒等式(等幂律,交换律,结合律,分配律,德·摩根律,吸收律,零律,同一

律,排中律,矛盾律,余补律,双重否定律,补交转换律等)

学习要求

1. 熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示 2. 熟练掌握集合的交、并、(相对和绝对)补、对称差、广义交、广义并的定义及其性

3. 掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法 4. 牢记基本的集合恒等式(等幂律、交换律、结合律、分配律、德·摩根律、收律、零

律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律)

5. 准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式

典型习题

1. 证明 A-B=A 2. 证明 A-B=

A∩B=A

B 。 A∪B=B

A∩B=A 。

3. 设A,B为集合,试确定下列各式成立的充分必要条件: 4. 判断下列命题是否为真。 5. 设A={},B=PP(A),问下列各题是否为真。 6. 判断下列命题的真假。 7. 在下列各题中,如果命题为真,请给出证明;如果命题为假,请给出反例。 8. 证明(A-B)-C = (A-C)-(B-C)。 9. 对60个学生参加课外活动的情况进行调查。结果发现,25人参加物理小组,26人参加化学小组,26人参加生物小组。9人既参加物理小组又参加生物小组,11人既参加物理小组又参加化学小组,8人既参加化学小组又参加生物小组。8人什么小组也没参加,回答下列各问题:

内容与要求1. | 典型习题 。 证明 A-B=A A∩B= 提示 参看基本集合恒等式,集合恒等式证明技巧。 答案 必要性。假设A∩B≠属于A但是x不 属于A-B。与A-B=A矛盾。 充分性。显然A-BA∩B=矛盾。 A-B。命题得证。 A。任取x∈A,则如果x属于B,则x属于A∩B,与,必有x属于A∩B,则x属于A同时属于B,即x因此x必不属于B,即x属于A-B。从而证明了A分析 参看答案。 提示2. | 答案 | 分析 A | 返回B | 上一道 | 下一道 证明 A-B=A∪B=B A∩B=A 。 提示 参看基本集合恒等式,集合恒等式证明技巧。 答案 证明过程如下: A-B= AB A∪B=B A∩B=A A-B= 。 ① ② ③ ④ ① ①矛盾。 ②

② 假设AB,即存在x属于A但不属于B,则x属于A-B,与A-B=

③ 显然BA∪B,反之,任取x,

x∈A∨x∈B

x∈B∨x∈B

x∈A∪B

x∈B 因此A∪B ③

B。命题得证。 ④ 显然A∩B

A,任取x,

x∈A∪B

x∈B

A∩B。命题得证。

A∩B,与④矛盾。

x∈A 因此x∈A ④

x∈A∧x∈B

x∈A∩B。从而有A

① 假设存在x∈A-B,x∈A∧xB,即x∈A∧x

分析 参看答案。 提示 | 答案 | 分析 | 返回 | 上一道 | 下一道 3. 设A,B为集合,试确定下列各式成立的充分必要条件: (1)A-B=B (2)A-B=B-A (3)A∩B=A∪B (4)A B=A 提示 参看集合的基本运算,包含,文氏图。 答案 (1) A=B= (2) A=B; (3) A=B; (4) B=. ; 分析 与前面求解的问题不同,找出集合等式成立的充分必要条件的问题是比较灵活的 应用问题。求解这类问题可能用到集合的算律、不同集合之间的包含关系、甚至文氏 图等。具体求解过程可以说明如下。 (1)由A-B=B得 (A∩~B)∩B = B∩B 化简得B=。再将这个结果代入已知等式得A=。从而得到必要条件A=B==B也成立。 。 下面验证充分性。如果A=B= 成立,则A-B = (2)充分性是显然的,下面验证必要性。由A-B = B-A得 (A-B)∪A = (B-A)∪A 从而有A=A∪B,即A (3)充分性是显然的,下面验证必要性。由A∩B=A∪B得 A∪(A∩B) = A∪(A∪B) 化简得 A=A∪B,从而有A (4)充分性是显然的,下面验证必要性。由A A根据结合律有 (A即 B。同理可证BA。 B。类似可以证明BA。 B=A得 (AB) = AA A)B = A。 A B=,就是B= 提示 | 答案 | 分析 | 返回 | 上一道 | 下一道 习题

1.选择适当的谓词表示下列集合:答案

(1)小于5的非负整数

(2)奇整数集合

(3)10的整倍数的集合

2.用列元素法表示下列集合:答案

(1)S1={x|x是十进制的数字}

(2)S2={x|x=2∨x=5}

(3)S3={x|x=x∈Z∧3

(4)S4={x|x∈R∧x2-1=0∧x>3}

(5)S5={|x,y∈Z∧0≤x≤2∧-1≤y≤0}

3.设F表示一年级大学生的集合,S表示二年级大学生的集合,M表示数学专业学生的集合,R表示计算机专业学生的集合,T表示听离散数学课学生的集合,G表示星期一晚上参加音乐会的学生的集合,H表示星期一晚上很迟才睡觉的学生的集合。问下列各句子所对应的集合表达式分别是什么?请从备选的答案中挑出来。答案

(1)所有计算机专业二年级的学生在学离散数学课。

(2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉。

(3)听离散数学课的学生都没参加星期一晚上的音乐会。

(4)这个音乐会只有大学一、二年级的学生参加。

(5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会。

备选答案: ①T

④H=G∪T ⑤T∩G= ⑦G

F∪S ⑧S-(R∪M)

G ⑨G

S-(R∩M)

⑥F∪S

G

G∪H ②G∪H

T ③S∩R

T

4.确定下列命题是否为真:答案 (1) (2) (3) (4)

(5){a,b}

{a,b,c,{a,b,c}} ∈{∈{

} }

(6){a,b}∈{a,b,c,{a,b }}

(7){a,b}

{a,b,{{a,b}}}

(8){a,b}∈{a,b,{{a,b}}}

5.设S1={1,2,3,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},S5={3,5}.确定在以下条件下X可能与S1,…,S5中哪个集合相等?答案

(1)若X∩S5= (2)若X (3)X

(4)若X-S3= (5)若X

S3,且X

S1

S1且X

S3 S4但X∩S2=

6.求下列集合的幂集:答案

(1){a,b,c}

(2){1,{2,3}}

(3){} (4){

,{

}}

(5){{1,2},{2,1,1},{2,1,1,2}} (6){{

,2},{2}}

7.设E={1,2,3,4,5,6},A={1,4},B={1,2,5},C={2,4}。求下列集合:答案

(1)A∩~B

(2)(A∩B)∪~C

(3)~(A∩B)

(4)P(A)∩P(B)

(5)P(A)-P(B)

8.设A,B,C,D是Z的子集,其中

A={1,2,7,8}

B={x2|x2<50∧x∈Z}

C={x|x∈Z∧0≤x≤30∧x可以被3整除}

D={x|x=2k∧k∈Z∧0≤k≤6}

用列元素法表示下列集合:答案

(1)A∪B∪C∪D

(2)A∩B∩C∩D

(3)B-(A∪C)

(4)(~A∩B)∪D

9.化简下列集合表达式:答案

(1)((A∪B)∩B)-(A∪B)

(2)((A∪B∪C)-(B∪C))∪A

(3)(B-(A∩C))∪(A∩B∩C)

(4)(A∩B)-(C-(A∪B))

10.画出下列集合的文氏图:答案

(1)~A∩~B

(2)(A-(B∪C))((B∪C)-A)

(3)A∩(~B∪C)

11.用公式表示图6.5中阴影部分的集合。答案

12.对60个人的调查表明有25人阅读《每周新闻》杂志,26人阅读《时代》杂志,26人阅读《幸运》杂志,9人阅读《每周新闻》和《幸运》杂志,11人阅读《每周新闻》和《时代》杂志,8人阅读《时代》和《幸运》杂志,还有8人什么杂志也不读。答案

(1) 求阅读全部三种杂志的人数。

(2) 分别求只阅读《每周新闻》、《时代》、《幸运》杂志的人数。

13.某班有25个学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有两人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。答案

14.在1到300的整数中(1和300包含在内)分别求满足以下条件的整数个数:答案

(1)同时能被3,5和7整除。

(2)不能被3和5,也不能被7整除。

(3)可以被3整除,但不能被5和7整除。

(4)可以被3或5整除,但不能被7整除。

(5)只被3,5和7之中的一个数整除。

15.化简以下集合表达式:答案

(1)∪{{3,4},{{3},{4}},{3,{4}},{{3},4}} (2)∪{{

16.设集合A={{1,2},{2,3},{1,3},{

(1)∪A

(2)∩A

(3)∩∪A

(4)∪∩A

17.判断以下命题的真假:答案

(1)a∈{{a}}

(2){a}∈{{a}}

(3)x∈{x}-{{x}} (4){x}

(5)A-B=A

B=

{x}-{{x}}

}},计算下列表达式:答案

},{{

}}}

本文来源:https://www.bwwdw.com/article/vq96.html

Top