离散数学第03章-数学书籍.ppt

第三章 集 合 3.1 集合论基础 3.2 集合运算及其性质 3.3 集合的笛卡儿积与无序积 3.1 集合论基础 1. 集合与元素 所谓集合，是指某些可辨别的不同对象的全体，将用大写字母A，B，X，Y，···表示之。组成集合的对象称为集合的元素或成员，将用小写字母a，b，x，y···表示之。a是A的元素或a属于A，记作a?A；a不属于A或a不是A的元素，记作a?A，或者?(a?A)。 集合的元素一旦给定，这一集合便完全确立。这一事实被形式地叙述为外延公理。 外延公理：两集合A和B相等，当且仅当它们有相同的元素。 若A与B相等，记为A=B；否则，记为A?B。 外延公理可形式表为： A=B?(?x)(x?A?x?B) 或者 A=B?(?x)(x?A?x?B)?(?x)(x?B?x?B) 顺便指出，在应用外延公理证明集合A与B相等时，只需考察： 对于任意元素x，应有下式 x?B?x?B 成立即可。这就是说，证明两集合相等时可按此法行事。 表示一个特定集合，基本上有两种方法： 一是枚举法，在可能时列出它的元素，元素之间用逗号分开，再用花括号括起。如 A={a,e,i,o,u} (1) 表明集合A是由字母a, e, I ,o和u为元素构成的。 二是谓词法，用谓词公式来确定集合。即个体域中能使谓词公式为真的那些元素，确定了一个集合，因为这些元素都具有某种特殊性质。若P(x)含有一个自由变元的谓词公式，则{x|P(x)}定义了集合S，并可表为 S={x|P(x)} 由此可见，P(c)为真当且仅当c?S。从而有 x?S?x?P(x) 例如，(1)可表为 A={x|x是英文字母表中元音字母} 在用性质来描述集合时，可表述为概括原理或子集合公理。 子集公理： 对于任给集合A和性质P，存在集合B，使得B中元素恰为A中满足P的那些元素。 子集公理可形式地表为 (?B)(?x)(x?B?x?A??(x)) 其中?(x)为不含B自由出现。 子集公理的提出，避免了悖论，使集合论得以存在和发展。 应该指出的是：①集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，集合并不改变，即{a, a ,e, i, o, u}= { a, u, e, o, i}。但有时对重复出现的元素都认为是集合的元素，这种集合称为多重集。即{a, a, e, i, o, u, u}?{a, e, i, o, u}。本书中集合在不特别指明时，都指前者，即①中的集合。 ②集合的元素可以是具体事物，可以是抽象概念，也可以是集体，不是集合的元素称为本元。如，一本书，一支笔，集合{1,2,3}可以组成集合B={一本书，一支笔，{1,2,3}} 。特别地，以集合为元素的集合称为集合族或集合类如A={{1,2,3}, { 8,9,6}}。 ③集合中元素之间可以有某种关联，也可以彼此毫无关系。 2. 子集、全集与空集 子集是描述一个集合与另一个集合之间的关系，其定义如下。 定义3.1.1 设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 成立即可。 此外，若集合B不包含集合A，记为A?B。 定义3.1.2 设A和B是两个集合，若A?B且A?B，则称A是B的真子集，记为A?B，也称B真包含A。该定义也可表为 A?B?(A?B?A?B) 定义3.1.3 如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记为U或E。它可形式地表为 U={x|P(x)??P(x)} 其中P(x)为任何谓词公式。 显然，全集U即是第二章中的全总论域。于是，每个元素x都属于全集U，即命题(?x)(x?U)为真。由定义易知，对任意集合A，都有A?U。 在实际应用中，常常把某个适当大的集合看成全集U。 定义3.1.4 没有任何元素的集合，称为空集，记为?，它可形式地表为： ?={x|P(x)??P(x)} 其中P(x)为任何谓词公式。 由定义可知，对任何集合A，有??A。这是因为任意元素x，公式x???x?A总是为真。 注意，?与{?}是不同的。{?}是以?为元素的集合，而?没有任何元素，能用?构成集合的无限序列： (1)?，{?}，{{?}}，··· 该序列除第一项外，每项均以前一项为元素的集合。 (2)?，{?}，{?，{?}}，··· 该序列除第一项外，每项均以前面各项为元素的集合。它即是冯·诺依曼在1924年使用空集?给出自然数的集合表示： 0:=?，1:={?}，2:={ ?,{?}}，··· 定理3.1.1 空集是唯一的 定