离散数学概论习题答案第3章

1

第二部分 集合、矩阵、关系和函数

集合论是处理集合，函数和关系的数学理论。集合包括最基本的数学概念，例如集合，元素和成员关系。 在大多数现代数学公式中，集合论提供了一种描述数学对象的语言。集合可用来表示数及其运算，还可表示和处理非数值计算，如数据间关系的描述等。集合论，逻辑和一阶逻辑构成了数学公理化的基础。 同时，函数和关系是基于集合的映射，它们是满足某些属性的特殊集合。 接下来，我们将在两个单独的章节中介绍它们。 集和矩阵将在第3章中介绍，而关系和函数将在第4章中介绍。

第三章 集合和矩阵

3.1 集合

3.1.1 集合概念

集合没有确定的概念。一般地，我们把研究的对象统称为元素；把一些元素组成的总体叫做集合，也简称集。

通常用大写英文字母表示集合。例如，N代表是自然数集合，Z代表是整数集合，R代表是实数集合。用小写英文字母表示集合内元素。若元素a是集合A的一个元素，则表示为aA，读作元素a属于集合A；若元素a不是集合A的一个元素，则表示为aA，读作a不属于集合A。

集合分为有限集合和无限集合两种，下面给出定义。

表示集合方法有列举法和描述法两种方式，下面分别介绍。

1. 列举法

当集合是有限集合时，可以列出集合的所有元素，用逗号隔开各元素，并用花括号把所有元素括起来。这种表述方式为列举法。例如：

S1={a, b, c, d, e, f}，S2={a, b, b, c, d, e, f}，S3={ d, e, a, b, c, f}

上述三个集合S1、S2和S3是相同集合，尽管有重复元素。且集合元素之间没有次序关系。

一个集合可以作为另个集合的元素。例如，

S1={a, b, { c, d, e, f }}

集合S1包含元素a, b和{ c, d, e, f }。因为{ c, d, e, f }是集合S1中的元素，故可记为：,,,cdefA。 定义 3-1：有限个元素构成的集合为有限集合。其中集合包含元素的个数称为集合的基，记作A。无限个元素构成的集合为无限集合。 2

以上给出的集合实例都是有限集合。当集合是无限集合时，无法列出集合的所有元素，可先列出一部分元素，若剩余元素与已给出元素存在一定规律，那剩余元素的一般形式很明显可用省略号表示。如N={1, 2, 3,…}, C={2, 4, 6, 2n…}, Z+={1, 2,

3,…}。

2. 描述法

当集合中元素具有相同性质或满足相同条件时，可以用描述法表示集合中元素，不用全部列出集合中所有元素。具有相同性质或满足相同条件可用一阶逻辑中的谓词公式表示：

{()}AxPx

上式表示集合A是由具有某种性质P的元素x构成。例如，{}Axx是离散数学期末成绩为优秀的学生。

集合元素的特征如下：

(1) 确定性：设A是一个给定的集合，x是某一个具体对象，则x或者是A的元素，或者不是A的元素，两种情况必有一种且只有一种成立.。

(2) 互异性：一个给定集合中的元素，指属于这个集合的互不相同的个体（对象），因此，同一集合中不应重复出现同一元素。

(3) 无序性：一般不考虑元素之间的顺序，但在表示数列之类的特殊集合时，通常按照习惯的由小到大的数轴顺序书写。

存在两种特殊的集合：空集合和全集。

空集是客观存在的，例如2{5}Axxyxyx是=和的交点，显然函数y=x和函数y=x2无交点，故集合A是空集，即A。

根据空集定义，对于任一元素x，则x这个命题为假，即0x。

全集是个相对性概念。由于所研究的问题不同，所取全集也不同。例如，在研究平面解析几何问题时，可把整个坐标平面取为全集。在研究自然数问题时，可把自然数集N取为全集。

根据全集定义，对于任一元素x，则xE这个命题为真，即1xE。

3.1.2 集合间关系

集合包含关系在命题逻辑和一阶逻辑中的符号化表示为： 定义 3-2：集合的基为零时，该集合称为空集合，记为。

定义 3-3：考虑的所有对象构成的集合称为全集，记为E。

定义 3-4：设A和B是两个集合，如果B中元素都是A中的元素，则称B为A的子集合，简称子集。此时称B包含于A中，或A包含B。记为BA。如果A不包含B，记为BA。

二维码3-1视频3

()BAxxBxA

例如，集合A={1, 2, 3}，当集合B={4}时，4A，因此BA。当集合B={1}时，1A，因此BA。

证明：设A为任一集合，假设是集合A的子集，则 ()xxxA成立，因前件x是假，所以整个蕴含式对所有x成立，所以根据子集定义可有：

()xxxAA 成立，故假设成立，即 是集合A的子集。

集合相等关系在命题逻辑和一阶逻辑中的符号化表示为：

=(()())ABBAABxxBxAxBxA

由以上定义可知：两个集合相等的充分必要条件是两集合具有相同的元素。例如：

2{210}Axxx

{1}Bxx

因为方程2210xx的解为1，故集合{1}Axx，则A=B。

集合真包含关系在命题逻辑和一阶逻辑中的符号化表示为：

(()())BAxxBxAxxAxB

例如，A={1，2，3}，B={1，2}，则BA。

例3.1 证明下列集合性质：

(1) 对于任一集合，都有AA。

(2) 设A、B和C为集合，有ABBCAC。

解：(1)显然成立。

(2)依据集合包含定义可知：

()()()ABBCxxAxBxxBxCxxAxCAC 定义 3-5：设A和B是两个集合，若BA且AB，则称A与B相等，记为=AB。

定义 3-6：设A和B是两个集合，若BA且AB，则称B是A的真子集，称B被A真包含，或A真包含B，记为BA。 定理3-1：空集是任何集合的子集。 4

集合间关系可以用文氏图表示。文氏图是英国数学家John Venn在1881年提出的。将全集用长方形表示，用圆形或其他封闭的几何图形表示集合。有时用点表示集合中的特定元素。

例如，集合A={1, 2, 3}是所有自然数的子集，即AE。用文氏图表示为：

图 3-1 AE的文氏图 图3-2 AB的文氏图

例如，集合A={1, 2}，则按照定义集合A的幂集()={{1}{2}{1,2}}PA，，，。显然，若集合A的元素个数是n个，则幂集P(A)有2n个元素。

例3.2 求下列集合的幂集。

(1) A

(2) A{}

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

解：(1) (){}PA

(2) (){,{}}PA

(3) (){,{{1,{2,3}}}}PA

3.1.3 集合运算

集合运算包括并（）、交（）、相对补（-）、绝对补（~）、对称补（）。任意两集合经上述运算后可生成新集合。

用文氏图表示集合A和B的并集，如图3-3所示。

E A E A B

E

E 定义 3-8：设A、B为两集合，A和B两集合的所有元素组成的集合则称为A与B的并集，记作AB，符号化表示为={}ABxxAxB。 定义 3-7：集合A的所有子集构成的集合则称为A的幂集，记作()PA，符号化表示为()={}PAxxA。 5

图3-3 AB的文氏图 图3-4 AB的文氏图

n个集合A1，A2，…，An的并集为：

121...={()()}nniiAAAAxixA

当n无限大时，可以记为：

121...={()()}iiAAAxixA

用文氏图表示集合A和B的并集，如图3-4所示。

n个集合A1，A2，…，An的交集为：

121...={()()}nniiAAAAxixA

当n无限大时，可以记为：

121...={()()}iiAAAxixA

用文氏图表示集合A和B的相对补，如图3-5所示。

图3-5 -AB的文氏图 图3-6 ~A的文氏图

用文氏图表示集合A的绝对补，如图3-6所示。

用文氏图表示集合A和B的对称补，如图3-7所示。

设A、B为任意集合，由对称差定义不难看出，对称差有下列性质： E

E A B A 定义 3-9：设A、B为两集合，A和B两集合的共同元素组成的集合则称为A与B的交集，记作AB，符号化表示为={}ABxxAxB。

定义 3-10：设A、B为两集合，由在集合A但不在集合B的元素组成的集合则称为A与B的相对补集，记作-AB，符号化表示为-={}ABxxAxB。

定义 3-11：设A为集合，由在全集E但不在集合A的元素组成的集合则称为A的绝对补集，记作~A，符号化表示为~=-{}AEAxxExA。

定义 3-12：设A、B为两集合，由在集合A中但不在集合B的元素与在集合B中但不在集合A的元素组成的集合则称为A与B对称差，记作AB，符号化表示为={()()}ABxxAxBxBxA。 6

1)=()()ABABBA

2)=()-()ABABBA

图3-7 AB的文氏图

例3.3：已知A={1, 2, 7, 8}，B={1, 2, 3, 4, 5, 6, 7}， C={0, 3, 6, 9, 12, 15, 18, 21, 24,27, 30 }，D={1, 2, 4, 8, 16, 32,64}。求下列集合运算。

(1) (())ABCD

(2) (())ABCD

(3) ()BAC

(4) (~)ABD

(5) ()ABD

解：(1)

(())0, 1,2,3, 4,5,6, 7,8,9, 12, 15, 18, 21, 24,27, 30,32,64 ABCD (2) (())ABCD

(3) {0,1,3,6,7,8,9,12,15,18,21,24,27,30}(){4,5}ACBAC

(4)~{3,4,5,6}(~){1,2,3,4,5,6,8,16,32,64}ABABD

(5) ={3,4,5,6,8}()={1,23,4,5,6,816,32,64}ABABD，，

3.1.4 集合证明

集合证明是集合论中重要的集合运算，分集合包含证明和集合恒等证明两大类。下面分别通过例子具体说明证明方法。 集合运算与集合证明都需要遵从一定的算律。E A B