离散数学集合与关系集合

离散数学集合与关系集合第1页，课件共48页，创作于2023年2月第三章集合与关系—集合这里采用朴素集合论的方法，介绍有关集合的一些基本知识，内容显得较为直观，学起来易于接受。但集合及其相关的概念是本门课程后面各章内容的基础，读者务必熟练的掌握。

主要内容如下：集合及其表示方法集合间的关系集合的运算和运算定律集合成员表集合的分划与覆盖第2页，课件共48页，创作于2023年2月又例如

所有的正整数组成一个集合，每一个正整数均是这个集

合的元素。例如

全体中国人可组成一个集合，每一个中国人均是这个集合的

元素第三章集合与关系集合及其表示方法一、集合和元素把一些确定的、彼此不同的事物作为一个整体来

看待时，这个整体便称为是一个集合。

组成集合的那些个体称为集合的元素。

通常用大写英文字母来标记集合，用小写英文字母标记组成集合的个体若个体a是集合A的元素，则记作“a∈A”若a不是集合A的元素，则记作“aA”第3页，课件共48页，创作于2023年2月几个常见的集合的表示符号：N：所有正整数的集合。Q：所有有理数的集合。Z：所有非负整数的集合。R：所有实数的集合。I：所有整数的集合。Nm：从1到m，这m个正整数的集合。P：所有素数的集合。Zm：从0到m-1，这m个非负整数的集合。

于是2∈N，2.5N，-3N，但2.5∈Q，-3∈I。

第4页，课件共48页，创作于2023年2月二、集合的表示方法(1)列举法：按任意顺序逐一列举集合中的元素于花括号内，元素之间用逗号隔开。例如：A={2,a,b,9},B={4,5,6,7,8}(2)描述法：给定一个条件P(x)，当且仅当个体a使P(a)成立时，a∈A。其一般形式为A={a∣P(a)}例如上述集合B={a∣a∈N且4≤a≤8}

又如C={2i∣i∈Z},即C={20,21,22,23,…}D={2x∣x∈Z且x≤50},即D={0,2,4,6,…,98,100}第5页，课件共48页，创作于2023年2月三、集合的基数集合A中不同元素的个数称为集合A的基数，记作#A，或|A|。例如上页中的集合，#A=4，#B=5，#D=51，集合C有无穷多个元素，因此C的基数是无穷大。若#A是有限数，则称A为有限集，否则称A为无限集。例如

N,Z,I,R等均为无限集。

四、空集定义3-1不含有任何元素的集合，称为空集，记作φ。

例如

A={x|x∈R且x2+8=0}=φ

第6页，课件共48页，创作于2023年2月练习3-1

用列举法表示下列集合（1）A={a|a∈P且a<20}（2）B={a||a|<4且a为奇数}2.用描述法表示下列集合(1)A={0,2,4,…,200}(2)B={2,4,8,…,1024}{2,3,5,7,11,13,17,19}{-3,-1,1,3}{2x|x∈Z且x≤100}{2n|n∈N且n≤10}

第7页，课件共48页，创作于2023年2月集合间的关系集合的包含和相等是集合间的两个基本关系。例如

设A={a,b,c,d},B={a,e,x,y,z},C={a,x}BA，AB。则，CA，一、集合的包含定义3-2

设有集合A、B，如果A的每一个元素都是B的元素，则称A是B的子集或B是A的包含集，记。如果A不是B的子集，则记作AB。

第8页，课件共48页，创作于2023年2月集合的包含关系具有如下几条性质：证明性质（1）

（反证法）假设

A，（1）对任意集合A，；

（2）对任意集合A，；（3）对任意集合A、B、C，若

，，则。

则至少有一个元素，但，这与空集的定义相矛盾，因此成立。第9页，课件共48页，创作于2023年2月二、集合的相等例如

设A={x|x∈N且x能整除24}，B={1,2,3,4,6,8,12,24}则A=B=又例如

（1）{a,b,c}{b,c,a}（2）{a,b,c,c}{a,b,c}（3）{a,{b,c}}{{a,b},c}（4）{}=≠≠定义3-3

设有集合A、B，若且

，则称集合A与B相等，记作A=B。

第10页，课件共48页，创作于2023年2月例如

设A={0，1}，B={0，1，2}，C={0}则但四、空集的唯一性定理3-1

空集是唯一的

因为空集被包含于每一个集合中，三、集合的真包含定义3-4

设有集合A、B，若,且A≠B，则称A是B的真子集，记作，若A不是B的真子集，则记作。

证明

假设有两个空集和，

所以有，，

由定义3-3，,故空集是唯一的。

第11页，课件共48页，创作于2023年2月五、幂集定义3-5

设有集合A，由A的所有子集组成的集合，称为集合A的幂集，记作2A即例1

设A={a}

则0个元素的子集：

1个元素的子集：{a}因此

设B={a,b}

则0个元素的子集：

1个元素的子集：{a},{b}2个元素的子集：{a,b}因此

设C={a,b,c}

则0个元素的子集：；1个元素的子集：{a},{b},{c}2个元素的子集：{a,b},{a,c},{b,c}

3个元素的子集：{a,b,c}因此

第12页，课件共48页，创作于2023年2月定理3-2

设A是有限集，则#(2A)=2#A

在二项式定理

中，令x=y=1,便有

因此

#(2A)=2n即#(2A)=2#A::{a1},:{a2},…{an}:{a1,a2},{a1,a3}…:{a1,a2,…,

an}…证明

设A={a1,a2,…,

an},从n个元素中选取m个元素的方法有种，所以A的子集个数为第13页，课件共48页，创作于2023年2月例2

设,

求2A和2B

解

对于集合A，它只有一个子集，

即

对于集合B，有

1个元素的子集：，{a}，{{a}}

2个元素的子集：,,3个元素的子集：

0个元素的子集：

因此

第14页，课件共48页，创作于2023年2月答案：ABD答案：ABC练习3-2

B.C.D.

1试判断下列各式是否正确，并将正确的题号填入括号内。

2设,试判断下列各式是否正确，并将正确的题号填入括号内。

B.C.D.

第15页，课件共48页，创作于2023年2月3设,

，判断下列论断是否正确，并将“Y”或“N”填入相应论断后面的括号中。

(1)(2)(3)(4)()()()()()()()()YYYYYYNN令则第16页，课件共48页，创作于2023年2月集合的运算和运算定律二、文氏图定义3-6

如果在某个问题中，所讨论的一切集合均是某个集合的子集，则称这个集合是该问题的全集合。记作U（或E）。

一、全集合例如

UAAB第17页，课件共48页，创作于2023年2月三、集合的运算1.并运算

定义3-7

设有集合A、B，属于A或属于B的所有元素组成的集合称为A与B的并集，记作。即例如

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

由定义1-7知，

AB第18页，课件共48页，创作于2023年2月2.交运算

定义3-8

设有集合A、B，属于A同时又属于B的所有元素组成的集合称为A与B的交集，记作。即例如

设A={a,b,c,d},B={d,f,a},C={e,f,g}则

由定义1-8可知，

AB第19页，课件共48页，创作于2023年2月3.相对补运算定义3-9

设有集合A、B，所有属于B而不属于A的元素组成的集合，称为A相对于B的补集，记作B-A。即例如

设A={a,b,c,d},B={d,f,a},C={e,f,g}则B-A={f},C-A={e,f,g}=CBA32页第20页，课件共48页，创作于2023年2月2.绝对补运算

定义3-10

集合A相对于全集合U的补集称为A的绝对补集，简称为A的补集，记作。即AA′~A第21页，课件共48页，创作于2023年2月例如设U={1，2，3，4，…，10}，A={2，4，6，8，10}则又例如

设U=I（I是整数集），

则第22页，课件共48页，创作于2023年2月四、集合运算的定律1.集合运算的十条定律对于全集合U的任意子集A、B、C，有：

交换律结合律分配律同一律第23页，课件共48页，创作于2023年2月互补律对合律等幂律零一律吸收律德•摩根律第24页，课件共48页，创作于2023年2月1.集合恒等式的几种证明方法（1）根据定义进行证明若要证明集合S=H，根据集合相等关系的定义，我们需证明且例1

证明证明

若,则，因此或者于是或者从而，则反之若，故或者。因此，或者,于是，从而，故有。由上证得，。

第25页，课件共48页，创作于2023年2月例2

证明证明

若则且，即且，因此，故。反之若，则且，即且，因此。故。由上证得，第26页，课件共48页，创作于2023年2月（2）利用已有的集合恒等式证明新的恒等式例如假设交换律、分配律、同一律和零一律都成立，则可以证明吸收律也成立。

证明（由同一律）

（由分配律）（由交换律）

（由零一律）

（由同一律）

又例如证明等幂律

证明==A(3)利用下一节介绍的集合成员表证明集合恒等式

第27页，课件共48页，创作于2023年2月D若，则A=B练习3-3

1设A、B、C是任意集合，判断下述论断是否正确，并将正确的题号填入括号内。

A若，则B=CB若，则B=CC若A-B=A-C，则B=C()D反例设A={a,b,c},B={b,d},C={c,d}则但23页第28页，课件共48页，创作于2023年2月2设U={1，2，3，4，5}，A={2，4}，B={4，3，5}，C={2，5，3}，确定下列集合的元素，将其填入相应的花括号内。

(1){}(2){}(3){}(4){}(5}21,42,3,4,54第29页，课件共48页，创作于2023年2月3设U表示刘平拥有的所有书的集合，，其中A是离散数学参考书的集合，B是操作系统参考书的集合，C是今年出版的新书的集合，D是从图书馆借来的书的集合。现知道如下情形：（1）所有离散数学参考书都是今年出版的新书。（）（2）所有操作系统参考书都是从图书馆借来的。（）（3）今年出版的新书不是从图书馆借来的。（）（4）没有一本操作系统的参考书是今年出版的。（

）

3157试用集合的方法分别表示上述四种情形，可供选择的答案如下，请从下述答案中挑选出相应表达式的编号填入每一种情形后面的括号中。2.3.4.5.6.7.第30页，课件共48页，创作于2023年2月4判断下列论断是否正确，对正确的论断在相应题后的括号中标入“Y”，对错误的论断在相应题后的括号中标入“N”。1）若，则（）2）若，则（）3）若，则（）4）若，则（）5）若，则()6）若，则()7）若，则()8）若，则()YYYYNNNN第31页，课件共48页，创作于2023年2月集合成员表一、并、交和补集的成员表根据集合的并和交运算的定义，全集合U中的元素u可分为如下四种情形：（1），（2），（3），（4），AB00

01

10

1100

10

10

11第32页，课件共48页，创作于2023年2月设A是全集合U的子集，根据补集的定义，全集合U中的元素可分为两种情形，（1）若，则（2）若，则的成员表

A0110第33页，课件共48页，创作于2023年2月二、由集合A1、A2、…、Ar所产生的集合的成员表。设A1、A2、…、Ar是全集合U的子集，对这些集合以及Φ和U有限次地施加补、并、交运算，可以产生出一些新的集合，这样产生的集合称为是由A1、A2、…、Ar所产生的集合。例如S第34页，课件共48页，创作于2023年2月例1

构造T=的成员表

AB0001011011110100010第35页，课件共48页，创作于2023年2月例2构造S的成员表

ABC00000101001100101110111S110011000100010010101010001000100110011000000110第36页，课件共48页，创作于2023年2月三、利用集合成员表证明集合恒等式例３

设A、B、C是任意集合，试问等式S=T是否成立？

ABC000

001

010

011

100

101

110

111ST1

1

1

1

00

0

00

0

1

1

1

1

1

11

1

1

1

0

1

0

10

0

1

1

0

1

0

10

0

1

1

0

0

0

00

0

0

0

0

1

0

10

0

1

1

0

1

0

1

其中

S=,T=分别构造S和T的成员表如下：

解第37页，课件共48页，创作于2023年2月集合的分划与覆盖一、集合的分划定义3-11

设有非空集合A，H={A1、A2、…、Am}，其中，且（i=1，2，…，m），若

（1），当i≠j时

(2)例1

设A={1，2，3，4}

则H1={{1}，{2}，{3，4}}H2={{2，3}，{1，4}}H3={{1}，{2}，{3}，{4}}。

都是A的分划则称H是集合A的一个分划，每一个称为这个分划的一个分块。第38页，课件共48页，创作于2023年2月例2设A={2，3，4，8，9，10，15}

定义A的如下子集：

试问是否A的一个分划。

解

根据题意{2，4，8，10}

{3，9，15}{10，15}

不是A的分划，可成为A的一个分划。

第39页，课件共48页，创作于2023年2月二、集合的覆盖定义3-12

设有非空集合A，,其中

且（i=1，2，…，m），若，

则称S是集合A的一个覆盖。

例如

例2中是A的分划，也是A的覆盖。是A的覆盖，但不是A的分划。第40页，课件共48页，创作于2023年2月练习3-5

1设A={a，b，c，d，e，f}，指出下列哪些是A的分划（在相应括号内填入“1”），哪些是A的覆盖（在相应括号内填入“2”），哪些既不是分划，也不是覆盖（在相应括号内填入“0”）H1={{a，b}，{c，d}，{a，e，f}}（）H2={{c，e}，{c，d，f}，{b}}（）H3={{a，b，c，d}，{e，f}}（