《离散数学》课程教材PDF电子书：第3章 集合论

第3章集合论 集合论是现代数学各分支的基础.是计算机科学许多理论不可或缺的工具.它起源于16 世纪末期，最初，人们为了追求微积分的坚实的基础，仅进行了数集的研究，直到1876一1883 年，德国数学家康托(Georg Cantor)发表了一系列有关集合论的文章，对任意元素的集合进 行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论的深厚基础.19世 纪90年代后，集合论逐渐为数学家们采用，成为分析数学、代数和几何的有力工具.经过一 百多年的发展，集合论成为数学中发展最为迅速的分支之一 本章主要介绍集合论的初步知识，如集合的基本概念、运算、性质以及笛卡儿积等内容， 3.1 基本概念 1.集合的概念 集合是集合论中最基本的概念，很难给出精确的定义，只能给出说明性的描述.一般地， 把一些确定的，可以区分的事物放在一起构成的整体称为集合，简称集.构成集合的每个 事物称为集合的元素（或成员）.构成集合的元素可以是具体的事物，也可以是抽象的事物， 例如： 方程x2-1=0的实数解集合 程序设计语言C的全部基本字符的集合 某高校全体学生的集合 坐标平面上所有点的集合 通常用大写的英文字母A,B,C,表示集合，用小写的英文字母a,b,c,表示元素.如 果元素a属于集合A,记作a∈A,读作“a属于A”.如果a不属于A,记作aEA或a年A, 读作“a不属于A”. 下面是几种特殊集合的表示符号： N—自然数集合（包括0）. Z—整数集合，Z+—正整数集合，Z一负整数集合 Q—有理整数集合，Q+—正有理数集合，Q一负有理数集合 R—实数集合，R+—正实数集合，R一负实数集合 C—复数集合，等等 2.集合的表示方法 集合有多种表示方法，这里介绍几种常用的表示方法

第3章 集 合 论 集合论是现代数学各分支的基础, 是计算机科学许多理论不可或缺的工具. 它起源于 16 世纪末期, 最初, 人们为了追求微积分的坚实的基础, 仅进行了数集的研究, 直到 1876—1883 年, 德国数学家康托 (Georg Cantor) 发表了一系列有关集合论的文章, 对任意元素的集合进 行了深入的探讨, 提出了关于基数、序数和良序集等理论, 奠定了集合论的深厚基础. 19 世 纪 90 年代后, 集合论逐渐为数学家们采用, 成为分析数学、代数和几何的有力工具. 经过一 百多年的发展, 集合论成为数学中发展最为迅速的分支之一. 本章主要介绍集合论的初步知识, 如集合的基本概念、运算、性质以及笛卡儿积等内容. 3.1 基 本 概 念 1. 集合的概念 集合是集合论中最基本的概念, 很难给出精确的定义, 只能给出说明性的描述. 一般地, 把一些确定的, 可以区分的事物放在一起构成的整体称为集合, 简称集. 构成集合的每个 事物称为集合的元素 (或成员). 构成集合的元素可以是具体的事物, 也可以是抽象的事物. 例如： 方程 x 2 − 1 = 0 的实数解集合. 程序设计语言 C 的全部基本字符的集合. 某高校全体学生的集合. 坐标平面上所有点的集合. …… 通常用大写的英文字母 A, B, C, …表示集合, 用小写的英文字母 a, b, c, …表示元素. 如 果元素 a 属于集合 A, 记作 a ∈ A, 读作“a 属于 A”. 如果 a 不属于 A, 记作 a∈A 或 a 6∈ A, 读作“a 不属于 A”. 下面是几种特殊集合的表示符号： N——自然数集合 (包括 0). Z——整数集合, Z +——正整数集合, Z −——负整数集合. Q——有理整数集合, Q+——正有理数集合, Q−——负有理数集合. R——实数集合, R+——正实数集合, R−——负实数集合. C——复数集合, 等等. 2. 集合的表示方法 集合有多种表示方法, 这里介绍几种常用的表示方法

·44 第3章集合论 列元素法一把集合中的全部元素一一列举出来，元素之间用逗号“，”隔开，并把它们 用花括号“)”括起来.例如： A={1,2,3,4,5} 列元素法一般适合表示元素个数较少的集合.当集合中元素个数较多时，如果组成该集 合的元素有一定的规律，也可采用此方法，此时，列出部分元素，当看出组成该集合的其他元 素的规律时，其余元素用“”来表示.例如： B={1,2,3,,99} 此方法也可以表示含有无穷多个元素且元素有一定的规律的集合.例如： N={0,1,2,3,} 谓词表示法一一用谓词来概括集合中元素的属性.设x为某类对象的一般表示，P(x) 为关于x的一个命题，用{xP(z)}表示“使P(x)为真的全体x组成的集合”.例如，方程 x2-1=0的实数解集合可表示为C={xx∈RAx2-1=0}. 许多集合可以用两种方法来表示，如集合C也可以写成C={1,-1}.但是有些集合不 可以用列元素法表示，如实数集合R 文氏图表示法一一集合与集合的关系以及一些运算结果可以用文氏图形象地表示。在 给定的问题中，我们所考虑的所有事物的集合称为全集，记为E或U.在文氏图中，用矩形 表示全集；在矩形内部，用圆或其他形状的闭曲线表示全集的子集.不同的圆代表不同的集 合，并将运算结果得到的集合用阴影或斜线区域表示 需要注意的是，文氏图只是对某些集合间的关系及运算结果给出一种直观而形象的说 明，而不能用来证明。 全集中包含着我们讨论的所有事物.规定了全集后，我们讨论的任一集合中的所有元素 都属于全集.但全集是一个相对的概念，研究的问题不同，所取的全集也不同.例如，在研究 平面解析几何问题时，可以把整个平面取作全集：在初等数论中，可以把整数集Z作为全集 即使是同一个问题，也可以取不同的集合.例如，有关整数的问题，既可取Z为全集，也可取 Q或R为全集，但取Z为全集比取Q或R为全集显然要简便一些 3.元素与集合 对于元素与集合的理解，要注意以下几点： (1)组成一个集合的各个元素之间是彼此不同的，如果同一个元素在集合中多次出现，应 该认为是一个元素.例如： {1,1,2,4,2}={1,2,4} (2)集合的元素是无序的.例如： {1,2,3}={2,3,1 (3)任一元素（事物）是否属于一个集合，回答是确定的.也就是说，对于任意的元素α 和集合A,a∈A或a￠A必有一个成立. (4)集合的元素可以是任何事物，既可以是具体的事物，也可以是抽象的事物，还可以是 另外的集合.例如： {a,{1,2},p,{g}

· 44 · 第 3 章 集 合 论 列元素法——把集合中的全部元素一一列举出来, 元素之间用逗号“, ”隔开, 并把它们 用花括号“{}”括起来. 例如： A = {1, 2, 3, 4, 5} 列元素法一般适合表示元素个数较少的集合. 当集合中元素个数较多时, 如果组成该集 合的元素有一定的规律, 也可采用此方法, 此时, 列出部分元素, 当看出组成该集合的其他元 素的规律时, 其余元素用“…”来表示. 例如： B = {1, 2, 3, , 99} 此方法也可以表示含有无穷多个元素且元素有一定的规律的集合. 例如： N = {0, 1, 2, 3, }. 谓词表示法——用谓词来概括集合中元素的属性. 设 x 为某类对象的一般表示, P(x) 为关于 x 的一个命题, 用 {x| P(x)} 表示“使 P(x) 为真的全体 x 组成的集合”. 例如, 方程 x 2 − 1 = 0 的实数解集合可表示为 C = {x|x ∈ R ∧ x 2 − 1 = 0}. 许多集合可以用两种方法来表示, 如集合 C 也可以写成 C = {1, −1}. 但是有些集合不 可以用列元素法表示, 如实数集合 R. 文氏图表示法——集合与集合的关系以及一些运算结果可以用文氏图形象地表示。在 给定的问题中, 我们所考虑的所有事物的集合称为全集, 记为 E 或 U. 在文氏图中, 用矩形 表示全集; 在矩形内部, 用圆或其他形状的闭曲线表示全集的子集. 不同的圆代表不同的集 合, 并将运算结果得到的集合用阴影或斜线区域表示. 需要注意的是, 文氏图只是对某些集合间的关系及运算结果给出一种直观而形象的说 明, 而不能用来证明. 全集中包含着我们讨论的所有事物. 规定了全集后, 我们讨论的任一集合中的所有元素 都属于全集. 但全集是一个相对的概念, 研究的问题不同, 所取的全集也不同. 例如, 在研究 平面解析几何问题时, 可以把整个平面取作全集; 在初等数论中, 可以把整数集 Z 作为全集. 即使是同一个问题, 也可以取不同的集合. 例如, 有关整数的问题, 既可取 Z 为全集, 也可取 Q 或 R 为全集, 但取 Z 为全集比取 Q 或 R 为全集显然要简便一些. 3. 元素与集合 对于元素与集合的理解, 要注意以下几点: (1) 组成一个集合的各个元素之间是彼此不同的, 如果同一个元素在集合中多次出现, 应 该认为是一个元素. 例如: {1, 1, 2, 4, 2}={1, 2, 4} (2) 集合的元素是无序的. 例如: {1, 2, 3}={2, 3, 1} (3) 任一元素 (事物) 是否属于一个集合, 回答是确定的. 也就是说, 对于任意的元素 a 和集合 A, a ∈ A 或 a 6∈ A 必有一个成立. (4) 集合的元素可以是任何事物, 既可以是具体的事物, 也可以是抽象的事物, 还可以是 另外的集合. 例如: {a, {1, 2}, p, {q}}

3.2集合间的关系 .45· (⑤)元素和集合之间的关系是隶属关系，即属于或不属于，可以用一种树形图来表示这 种隶属关系，该图分层构成，每个层上的结点都表示一个集合，它的儿子就是它的元素.集合 S={a,{1,2},p,{g}的树形图如图3.1所示. {1,2 图3.1元素和集合间隶属关系的树形图 3.2 集合间的关系 在3.1节中，给出了“集合”“元素”以及元素与集合间的“属于”关系3个概念的直观 描述，以说明它们各自的含义.下面利用这3个概念定义集合间的关系 定义3.1设A、B是任意两个集合，如果A中的每一个元素都是B中的元素，则称 A是B的子集合，简称子集.也称A被B包含，或B包含A.记作A二B或B2A.符号 化表示为 A≤B台x(x∈A→x∈B) 如果A不被B包含，则记作A生B.符号化表示为 A4B÷3x(x∈AAx年B) 例如，A={a,b},B={a,b,c以，C={b,c,d,则有A二B,但A车C. 注意符号∈和二的区别，∈表示元素与集合间的“属于”关系，二表示集合间的“包含” 关系. 定义3.2设A,B是两个集合，如果ACB且BCA,则称A与B相等，记作A=B. 符号化表示为 A=B÷ACB且BCA 如果A与B不相等，则记作A≠B. 该定义给出了一个重要原则：要证明两个集合相等，唯一的方法就是证明每一个集合中 的任一元素均是另一个集合的元素. 定义3.3设A、B是两个集合，如果A是B的子集，而B中至少有一个元素不属于 A,则称A为B的真子集，记作ACB.符号化表示为 ACB台Hx(x∈A→x∈B)A3x(x∈BAx使A)】 或

3.2 集合间的关系 · 45 · (5) 元素和集合之间的关系是隶属关系, 即属于或不属于, 可以用一种树形图来表示这 种隶属关系, 该图分层构成, 每个层上的结点都表示一个集合, 它的儿子就是它的元素. 集合 S = {a, {1, 2}, p, {q}} 的树形图如图 3.1 所示. 图 3.1 元素和集合间隶属关系的树形图 3.2 集合间的关系 在 3.1 节中, 给出了“集合”“元素”以及元素与集合间的“属于”关系 3 个概念的直观 描述, 以说明它们各自的含义. 下面利用这 3 个概念定义集合间的关系. 定义 3.1 设 A、B 是任意两个集合, 如果 A 中的每一个元素都是 B 中的元素, 则称 A 是 B 的子集合, 简称子集. 也称 A 被 B 包含, 或 B 包含 A. 记作 A ⊆ B 或 B ⊇ A. 符号 化表示为 A ⊆ B ⇔ ∀x ( x ∈ A → x ∈ B) 如果 A 不被 B 包含, 则记作 A * B. 符号化表示为 A * B ⇔ ∃x ( x ∈ A ∧ x /∈ B) 例如, A = {a, b}, B = {a, b, c}, C = {b, c, d}, 则有 A ⊆ B, 但 A * C. 注意符号 ∈ 和 ⊆ 的区别, ∈ 表示元素与集合间的“属于”关系, ⊆ 表示集合间的“包含” 关系. 定义 3.2 设 A, B 是两个集合, 如果 A ⊆ B 且 B ⊆ A, 则称 A 与 B相等, 记作 A = B. 符号化表示为 A = B ⇔ A ⊆ B且B ⊆ A 如果 A 与 B 不相等, 则记作 A 6= B. 该定义给出了一个重要原则: 要证明两个集合相等, 唯一的方法就是证明每一个集合中 的任一元素均是另一个集合的元素. 定义 3.3 设 A、B 是两个集合, 如果 A 是 B 的子集, 而 B 中至少有一个元素不属于 A, 则称 A 为 B 的真子集, 记作 A ⊂ B. 符号化表示为 A ⊂ B ⇔ ∀x ( x ∈ A → x ∈ B) ∧ ∃x ( x ∈ B ∧ x /∈ A) 或

·46 第3章集合论 ACB台ACB∧A≠B 如果A不是B的真子集，则记作A￠B. 例如，集合{a,b}是{a,b,c的真子集，但{a,b,c和{b,c,d}都不是{a,b,c}的真子集。 集合与集合的关系可以用文氏图形象地表示，集合A和B的3种不同关系的文氏图如 图3.2所示 (a)ACB (b)AB (c)A=B 图3.2集合A和B的3种关系的文氏图 定义3.4不含任何元素的集合叫做空集，记作⑦.空集的符号化表示为 0={xx≠x} 例如，A={xz∈RAx2+2=0}是方程x2+2=0的实数解集，因为该方程无实数解， 所以A=②. 注意：0卡{0}. 定理3.1对于任意集合A,有 (1)aCA,且空集是唯一的：(2)ASA 证明：(1)假设⑦二A为假，则至少存在一个元素x,使x∈⑦且xA,因为空集⑦不 包含任何元素，所以这是不可能的. 设⑦1与⑦2都是空集，由上述结论可知，⑦1二⑦2且⑦2二⑦1，根据集合相等的定义得 01=⑦2，所以，空集是唯一的. (2)根据子集的定义可得，对于任意集合A,有A二A. 定义3.5含有n个元素的集合简称n元集，它的含有m(m≤n)个元素的子集叫做 它的m元子集. 任给一个n元集，如何求出它的全部子集呢？举例说明如下. 例3.1A={1,2,3},将A的子集分类 0元子集，也就是空集，只有一个：⑦ 1元子集，即单元集：{1}，{2}，{3}. 2元子集：{1,2}，{1,3}，{2,3}. 3元子集：{1,2,3. 一般地，对于n元集，它的m元子集有C个，所以不同的子集总数是 Co+CI+C2++Cn=2m

· 46 · 第 3 章 集 合 论 A ⊂ B ⇔ A ⊆ B ∧ A 6= B 如果 A 不是 B 的真子集, 则记作 A 6⊂ B. 例如, 集合 {a, b} 是 {a, b, c} 的真子集, 但 {a, b, c} 和 {b, c, d} 都不是 {a, b, c} 的真子集. 集合与集合的关系可以用文氏图形象地表示, 集合 A 和 B 的 3 种不同关系的文氏图如 图 3.2 所示. 图 3.2 集合 A 和 B 的 3 种关系的文氏图 定义 3.4 不含任何元素的集合叫做空集, 记作 ∅. 空集的符号化表示为 ∅ = {x| x 6= x} 例如, A = {x|x ∈ R ∧ x 2 + 2 = 0} 是方程 x 2 + 2 = 0 的实数解集, 因为该方程无实数解, 所以 A = ∅. 注意: ∅ 6= {∅}. 定理 3.1 对于任意集合 A, 有 (1)∅ ⊆ A, 且空集是唯一的; (2)A ⊆ A. 证明:(1) 假设 ∅ ⊆ A 为假, 则至少存在一个元素 x, 使 x ∈ ∅ 且 x 6∈ A, 因为空集 ∅ 不 包含任何元素, 所以这是不可能的. 设 ∅1 与 ∅2 都是空集, 由上述结论可知, ∅1 ⊆ ∅2 且 ∅2 ⊆ ∅1, 根据集合相等的定义得 ∅1 = ∅2, 所以, 空集是唯一的. (2) 根据子集的定义可得, 对于任意集合 A, 有 A ⊆ A. 定义 3.5 含有 n 个元素的集合简称 n 元集, 它的含有 m (m 6 n) 个元素的子集叫做 它的 m 元子集. 任给一个 n 元集, 如何求出它的全部子集呢? 举例说明如下. 例 3.1 A = {1, 2, 3}, 将 A 的子集分类: 0 元子集, 也就是空集, 只有一个: ∅. 1 元子集, 即单元集: {1}，{2}，{3}. 2 元子集: {1, 2}，{1, 3}，{2, 3}. 3 元子集: {1, 2, 3}. 一般地, 对于 n 元集, 它的 m 元子集有 C m n 个, 所以不同的子集总数是 C 0 n + C 1 n + C 2 n + + C n n = 2n

3.3集合的运算 .47. 3.3 集合的运算 3.3.1集合的基本运算 集合的运算，就是以集合为对象，按照确定的规则得到另外一些新集合的过程.集合的 基本运算有并、交、相对补、绝对补和对称差等 定义3.6设A、B是任意两个集合，由A或B中的元素构成的集合称为集合A与B 的并集，记作AUB. AUB={xx∈AVx∈B} 例如，A={1,2,4},B={2,4,5,则AUB={1,2,4,5. 集合的运算结果可以用文氏图形象地表示，集合A与B的并运算的文氏图表示如图3.3 所示 图3.3并运算的文氏图表示 两个集合的并运算可以推广到n个集合的并。 设A1,A2,,An是任意n个集合，则这n个集合的并可简记为UA,即 0A=ArUAU U4={r∈A1Vx∈AVVr∈An 并运算还可以推广到无穷多个集合的情况： UA:=A:UA2U UAU 定义3.7设A、B是任意两个集合，由既在A中又在B中的元素构成的集合称为集 合A与B的交集，记作A∩B. A∩B={xlx∈AAx∈B} 如果两个集合A、B的交集为空集，则称A、B不相交 例如，A={1,2,4,B={2,4,5},C={1,3},则A∩B={2,4,B∩C=⑦，所以B和 C是不相交的. 集合A与B的交运算的文氏图表示如图3.4所示 两个集合的交运算可以推广到n个集合的交

3.3 集合的运算 · 47 · 3.3 集合的运算 3.3.1 集合的基本运算 集合的运算, 就是以集合为对象, 按照确定的规则得到另外一些新集合的过程. 集合的 基本运算有并、交、相对补、绝对补和对称差等. 定义 3.6 设 A、B 是任意两个集合, 由 A 或 B 中的元素构成的集合称为集合 A 与 B 的并集, 记作 A S B. A S B = {x| x ∈ A ∨ x ∈ B} 例如, A = {1, 2, 4}, B = {2, 4, 5}, 则 A S B = {1, 2, 4, 5}. 集合的运算结果可以用文氏图形象地表示, 集合 A 与 B 的并运算的文氏图表示如图 3.3 所示. 图 3.3 并运算的文氏图表示 两个集合的并运算可以推广到 n 个集合的并. 设 A1, A2, , An 是任意 n 个集合, 则这 n 个集合的并可简记为 Sn i=1 Ai , 即 Sn i=1 Ai = A1 S A2 S S An = {x| x ∈ A1 ∨ x ∈ A2 ∨ ∨ x ∈ An} 并运算还可以推广到无穷多个集合的情况: S∞ i=1 Ai = A1 S A2 S S An S 定义 3.7 设 A、B 是任意两个集合, 由既在 A 中又在 B 中的元素构成的集合称为集 合 A 与 B 的交集, 记作 A T B. A T B = {x| x ∈ A ∧ x ∈ B} 如果两个集合 A、B 的交集为空集, 则称 A、B 不相交. 例如, A = {1, 2, 4}, B = {2, 4, 5}, C = {1, 3}, 则 A T B = {2, 4}, B T C = ∅, 所以 B 和 C 是不相交的. 集合 A 与 B 的交运算的文氏图表示如图 3.4 所示. 两个集合的交运算可以推广到 n 个集合的交