当前位置：文档之家 › 西安交通大学-刘国荣-离散数学 第三章 集合

西安交通大学-刘国荣-离散数学 第三章 集合

  • 格式：ppt
  • 大小：407.50 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

离散数学第3章

离散数学第3章

集合间的关系
例如，设集合A = {1, 2, 3, 4, 5}, B = {1, 3, 5}, C = {2, 4}。
文氏图：
A B C
则有集合B和C都是A的子集，且都是真子集，
即有 B A 和 C A
但B不是C的子集，C也不是B的子集．
25
集合间的关系
定理1 对任一集合A , 必有 定理2 对任一集合A , 必有

Ｎ代表自然数集合(包括0) Ｚ代表整数集合， Ｑ代表有理数集合， Ｒ代表实数集合， Ｃ代表复数集合．
8
3.1.1 集合的基本概念

如果b是集合A中的元素，称b属于A，并记作
b A

如果b不是集合A中的元素，称b不属于A，并 记作 b A93.1.1 源自合的基本概念例如：
把握好∈和
29
判断下列等式是否成立


(1) (2) (3) (4)
{{a, b}, c, } {{a, b}, c} {a, b, a} {a, b} {{a},{b}} {{a, b}} { ,{}, a, b} {{ ,{}}, a, b}
30
列出下列集合的元素
27
注意事项




1. 空集是个很重要的概念，一定要弄清Ø≠{Ø}， Ø中不含有 任何元素，而{Ø}中含有一个元素Ø. 2. 注意符号∈和 区别. ∈:元素与集合的关系， ：集合与集合的关系. 但是，由于集合也可以作为另一个集合的元素，所以，存在 着这样的情况： 集合A包含于集合B，集合A又属于集合B 例如： A={a,b} B={a,b,{a,b}} 此时就有A既是B的子集，又是B中的元素。 即有A B和A ∈ B同时成立。

离散数学 串讲-04.3.3

离散数学 串讲-04.3.3

3
离散数学
掌握等价关系的概念，并掌握覆盖、划分、等价类、 掌握等价关系的概念，并掌握覆盖、划分、等价类、商集的定 义和基本性质，弄清楚等价关系与划分之间的关系。 义和基本性质，弄清楚等价关系与划分之间的关系。牢记等价关 系的分类作用。 分类作用 系的分类作用。 掌握半序、半序集、全序、良序等概念， 掌握半序、半序集、全序、良序等概念，以及半序集的可比较 极大元、极小元、最大元、最小元、上界、下界、最大下界、 性、极大元、极小元、最大元、最小元、上界、下界、最大下界、 最小上界、直接后继等概念。牢记半序关系的非线性特性。 非线性特性 最小上界、直接后继等概念。牢记半序关系的非线性特性。 能画出有限半序集的哈斯图,并根据图讨论半序集的某些性质。 能画出有限半序集的哈斯图,并根据图讨论半序集的某些性质。
4
离散数学
第三章 函 数 重点要求
要求掌握函数的基本概念,弄清单射、满射、双射之间的区别。 要求掌握函数的基本概念 弄清单射、满射、双射之间的区别。 弄清单射 给定一个函数,要能够确定它是否是单射 满射、双射等。 要能够确定它是否是单射、 给定一个函数 要能够确定它是否是单射、满射、双射等。 掌握反函数和复合函数的定义和性质,并弄清楚它们存在的条件 并弄清楚它们存在的条件。 掌握反函数和复合函数的定义和性质 并弄清楚它们存在的条件。 理解元素及集合的象及原象的定义及相关的性质。 理解元素及集合的象及原象的定义及相关的性质。给定一个函 能够确定一个点的象,一个集合的象 能够确定一个点的原象,一 数,能够确定一个点的象 一个集合的象 能够确定一个点的原象 一 能够确定一个点的象 一个集合的象,能够确定一个点的原象 个集合的原象,能够确定两个函数的复合函数等 能够确定两个函数的复合函数等。 个集合的原象 能够确定两个函数的复合函数等。 掌握集合的势、可数集、不可数集等概念。 掌握集合的势、可数集、不可数集等概念。

离散数学第3章-集合论

离散数学第3章-集合论
三 定理1.4 (集合运算的基本性质) (1) 幂等律 A∪A=A A∩A=A (2) 交换律 A∪B=B∪A A∩B=B∩A (3) 结合律 A∪(B∪C)=(A∪B)∪C A∩(B∩C)=(A∩B)∩C • (4) 分配律 A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C) • • • •
例题
• 4）有多少学生选生物与计算机课，但不选艺
术课？ • 5）有多少学生选艺术课，但不选生物或计算 机课？ • 6）有多少学生选生物课，但不选艺术或计算 机课？ • 7）有多少学生选计算机课，但不选艺术或生 物课？
例题----解题思想
• 容斥原理（包含排斥）应用
• 1）讨论的范围是什么？即那些是全集中的元 素？----某学院的学生全体构成全集； • 2）将全集中的元素进行分类----按学生选课的 情况进行分类：选修艺术课为具有性质PA，选 修生物课为具有性质PB，选修计算机课为具有 性质PC，具有上述性质的集合记为A, B, C。 • 3）列出计算公式
第三章 集合论
3.1 3.2 3.3 3.4 3.5 集合的表示 集合的子集 笛卡尔积 集合的运算 罗素悖论
3.1 集合的表示
一 集合的定义 • <1> 集合：具有共同性质的一些东西汇集成
• • • 一个整体。 <2> 元素：构成一个集合中的那些对象。 a∈A a是A的元素，a属于A a∉A a不是A的元素，a不属于A
• 例1.3 集合运算
3.4 集合的运算（续）
• 例1.4，例1.5，例1.6证明 • 证明两个集合相等，可用如下办法： • <1>基本法 集合相等的充要条件是两个集合互为子集。 所以证明：x∈左式⇒x∈右式；x∈右式⇒x∈左式。 • <2>公式法 由集合运算的基本性质，通过推演，进行 证明。

离散数学 第三章

离散数学 第三章

思考： 思考： ≠ 和 ⊄ 的定义 注意 ∈ 和 ⊆ 是不同层次的问题
空集与全集
空集 ∅ 不含任何元素的集合 实例 {x | x2+1=0∧x∈R} 就是空集 ∧ ∈ 定理 空集是任何集合的子集 ∅⊆A ∈∅→x∈ ∅⊆ ⇔ ∀x (x∈∅→ ∈A) ⇔T ∈∅→ 空集是惟一的. 推论 空集是惟一的. 假设存在∅ 证 假设存在∅1和∅2，则∅1⊆∅2 且∅1⊆∅2， 因此∅ ∅ 因此∅1=∅2 全集 E 相对性 在给定问题中，全集包含任何集合， 在给定问题中，全集包含任何集合，即∀A (A⊆E ) ⊆
1、集合基本运算的定义 、 ∪ ∩ − ∼ ⊕ 2、文氏图（John Venn） 、文氏图（ ） 3、例题 、 4、集合运算的算律 、 5、集合 A∪B = { x | x∈A ∨ x∈B } ∪ ∈ ∈ A∩B = { x | x∈A ∧ x∈B } ∩ ∈ ∈ A−B = { x | x∈A ∧ x∉B } − ∈ ∉ A⊕B = (A−B)∪(B−A) ⊕ − ∪ − = (A∪B)−(A∩B) ∪ − ∩ 绝对补 ∼A = E−A −
i =1 m 1≤i < j ≤ m
∑
| Ai ∩ Aj | −
1≤i < j < k ≤ m
∑
| Ai ∩ Aj ∩ Ak | +...
+(−1)m | A1 ∩ A2 ∩ ... ∩ Am |
应用
之间（ 在内） 例1 求1到1000之间（包含 和1000在内）既不能 到 之间 包含1和 在内 整除， 整除的数有多少个？ 被 5 和6 整除，也不能被 8 整除的数有多少个？ 解：S ={ x | x∈Z, 1≤ x ≤1000 }, ∈ ≤ 如下定义 S 的 3 个子集 A, B, C： ： A={ x | x∈S, 5 | x }， ∈ ， B={ x | x∈S, 6 | x }， ∈ ， C={ x | x∈S, 8 | x } ∈

第3章 集合的基本概念和运算[离散数学离散数学(第四版)清华出版社]

第3章 集合的基本概念和运算[离散数学离散数学(第四版)清华出版社]

28
集合的基本运算
EXAMPLE 12
证明: 证明: (A-B)∪B=A∪B. ∪ ∪ 证明: (A-B)∪ 证明: (A-B)∪B =(A∩ )∪B ∪ =(A∪B)∩( ∪B) ∪ =(A∪B)∩E ∪ =(A∪B) ∪
29
集合的基本运算
EXAMPLE 13
化简: 化简: ((A∪B∪C)∩(A∪B))-((A∪(B-C))∩A). ∪ ∪ ∪ ∪
Identity
A∪A=A A∩A=A (A∪B)∪C=A∪(B∪C) (A∪B)∪C=A∪(B∪ (A∩B)∩C=A∩(B∩C) A∪B=B∪A A∩B=B∩A B=B∪ A∪(B∩C)=(A∪B)∩(A∪C) (B∩C)=(A∪B)∩(A∪ A∩(B∪C)=(A∩B)∪ A∩(B∪C)=(A∩B)∪(A∩C) A∪=A A∩E=A A∪E=E A∩= A∩ A∪ A∩ =E = =
和
19
集合的基本运算
EXAMPLE 7
设集合A={0, 2, 4, 6, 8}, B={0, 1, 2, 3, 4}, 设集合 C={0, 3, 6, 9}. 求A∪B∪C 和A∩B∩C. A∪B∪
A∪B∪C={0,1,2,3,4,6,8,9}. ∪ ∪ A∩B∩C= {0}.
20
集合的基本运算
17
集合的基本运算
DEFINITION 9.
为全集, , 的绝对补集定 设E为全集,AE,A的绝对补集定 为全集 义为: 义为: =E-A={x | x∈E∧xA}. ∈ ∧ 因为E是全集,是真命题, 因为 是全集,是真命题,所以可以 是全集 定义为: 定义为: = {x | xA}.
18
集合的基本运算
O={1, 3, 5, 7, 9}. O={x | x >=1∧x <=10∧x is odd number}. ∧ ∧ A={a, b, c, …… n} 枚举法 A={x | P(x)} 谓词公式法

离散数学第三章-集合的基本概念和运算

离散数学第三章-集合的基本概念和运算

29
例5、证明： A B A 证明：对任意 x ，
xAB
B (第14条)
xAxB
xAxB
xA B 故 AB A B
30
例6、证明 A (B A) A B 。 证明： A (B A) A (B A)
(A B) (A A) (A B) E A B
31
例7、化简 (A B C) (A B)
A B A AB
此式给出了A是B的子集的3种等价定义。不仅提供 了证明子集的新方法，也可以用于集合公式的化简。28
除基本运算外，还有以下一些常用性质 (证明略)
16、 A B B A
“ ”的交换律
17、(A B) C A (B C) “ ”的结合律
18、 A A
19、 A A
20、 A B AC B C
A {a1, a2, an} 表示集合 A 含有元素 a1, a2, an
5
注意： (1) a A或 a A
(2) 集合中的元素均不相同
{a,b,c},{a,b,b,c},{c, a,b}
表示同一个集合。 (3) 集合的元素可以是任何类型的事物，
一个集合也可以作为另一个集合的元素。
例如：A a,{b,c},b,{b}
1元子集：{a},{b},{c} (共C31 3个)， 2元子集：{a,b},{a, c},{b, c}(共 C32 3个)， 3元子集：{a,b, c} (共 C33 1个)。 一般，n 元集共有子集 Cn0 Cn1 Cnn （11）n 2n 个。
21
定义2 ：集合 A 的幂集，记 ( A) ,是 A的全体子集的集合 例5、 A {a,b,c} ，求 (A) 。 解：(A) {,{a},{b},{c},{a,b},

离散数学文档第三章

离散数学文档第三章

第三章 集合论集合论是现代数学的基础，是数学不可或缺的基本描述工具。

可以这样讲，现代数学与离散数学的“大厦”是建立在集合论的基础之上的。

集合论的研究起源于对数学的基础研究：对数学的对象、性质及其发生、发展的一般规律进行的科学研究。

德国数学家康托尔从1874年始，发表了一系列集合论方面的著作，从而创立了集合论。

在自然科学中，除了研究处于孤立的个体之外，更重要的是将一些相关的个体放在一起进行研究，这就直观地产生了引入集合这一概念的要求。

随着计算机时代的到来，集合的元素已由传统的“数集”和“点集”拓展成包含文字、符号、图形、图表和声音等多媒体信息，构成了各种数据类型的集合。

从而集合论在编译原理、开关理论、信息检索、形式语言等各个领域得到了广泛的应用。

3.1 集合一个集合是作为整体识别的、确定的、互相区别的一些事物的全体。

严格地讲，这只是一种描述，不能算是集合的定义。

类似于几何中的点、线、面等概念，在朴素集合论中，集合也是一种不加定义而直接引入的最基本的原始概念(一给出定义就要引入悖论)。

而集合论中的其他概念，则都是从它出发给予了严格的定义。

构成集合的每个事物称为这个集合的元素或成员。

集合一般用大写字母表示，元素用小写字母表示。

但这也不是绝对的，因为一个集合可以是另外一个集合的元素。

［例3.1.1］　英文字母的集合，C语言的基本字符集，全体实数，计算机内存单元集合。

［例3.1.2］　｛1，2，3｝＝｛2，1，3｝＝｛3，1，2｝。

［例3.1.3］　常用集合：N，I(I＋，I－)，P，Q(Q＋，Q－)，R(R＋，R－)，C。

集合的表示：(1)枚举法；(2)性质描述法：S＝｛x | P(x) ｝；(3)文氏图法：用于描述集合间的关系及其运算，其特点是直观、形象、信息量大且富有启发性。

一般用矩形表示全集U，用圆表示U的子集A，B，C等等。

集合中的事物称为集合的元素，通常用小写英文字母表示。

如果x是集合S的一个元素，则称x 属于S ，记作x S ；否则称x 不属于S ，记作x A 。

《离散数学》第3章集合

《离散数学》第3章集合

集合表示方法
列举法
列举法是将集合中的元素一一列举出来，写在大括号内表示集合的方法。例如，A={1,2,3}表示集合A 由元素1、2、3组成。
描述法
描述法是通过描述集合中元素的共同特性来表示集合的方法。例如，B={x|x>0}表示集合B由所有大于 0的实数组成。
常用集合类型介绍
有限集
有限集是指集合中的元素 个数是有限的。例如， C={1,2,3,4,5}是一个有限 集，它包含5个元素。
THANKS FOR WATCHING
感谢您的观看
特殊的集合。
集合论在数据库设计中应用
实体-关系模型
集合论中的集合和关系概念被用于描述实体-关系模 型，这是数据库设计中的重要方法。
数据完整性
集合论中的概念如唯一性、存在性等可以用于定义和 维护数据库的完整性约束。
查询优化
集合论中的运算和性质可以用于优化数据库查询，提 高查询效率。
集合论在其他领域应用
元素与集合关系
元素与集合的关系
元素与集合的关系只有两种，即属于和不属于。如果元素a是集合A的元素，就说a 属于A，记作a∈A；如果元素a不是集合A的元素，就说a不属于A，记作a∉A。
元素与集合的运算
元素与集合的运算主要有并集、交集和差集等。并集是指两个集合中所有元素的 集合；交集是指两个集合中共有元素的集合；差集是指属于第一个集合但不属于 第二个集合的元素的集合。幂集与笛卡尔积关来自探讨幂集与笛卡尔积的联系
幂集与笛卡尔积的区别
幂集与笛卡尔积的应用
幂集和笛卡尔积都是集合论中的重要概 念，它们之间有着密切的联系。例如， 对于任意集合A，其幂集P(A)可以看作 是A与其自身的笛卡尔积A×A的子集构 成的集合。

离散数学第03章集合代数

离散数学第03章集合代数

四、集合的幂集
一个集合的幂集是指以该集合所有子集为元素的 集合，即是由这些子集所组成的集合族。 集合，即是由这些子集所组成的集合族。
定义3.1.5 定义3.1.5 设A为一集合，A的幂集是一集合族，记 为一集合， 的 是一集合族， 为一集合
为ρ (A)， ρ (A) ={B|BA} ， { } 由定义可知， 由定义可知，∈ρ (A)，A∈ρ (A)。 ， ∈ 。 任给一个n元集，怎样求出它的全部子集？ 任给一个 元集，怎样求出它的全部子集？ 元集
定义3.1.2 定义3.1.2 设A和B是两个集合，若AB且 是两个集合， 和 是两个集合 且
A≠B，则称 是B的真子集，记为 B，也 ≠ ，则称A是 的真子集，记为A ， 真包含A。 称B真包含 。该定义也可表为 真包含
AB (AB∧A≠B) ∧ ≠
如果A不是 的真子集 则记作A 。 如果 不是B的真子集，则记作 B。 不是 的真子集，
图中的a， ， ， 也是集合 也是集合， 图中的 ，b，c，d也是集合， 由于所讨论的问题与a， ， ， 由于所讨论的问题与 ，b，c， d的元素无关，所以没有列出它 的元素无关， 的元素无关 们的元素。鉴于集合的元素是 们的元素。鉴于集合的元素是 集合这一规定，隶属关系可以 集合这一规定，隶属关系可以 这一规定 看作是处在不同层次上的集合 之间的关系。 之间的关系。
第三章
集合代数
集合论是现代数学的基础。德国数学家康 集合论是现代数学的基础。德国数学家康 是现代数学的基础 托尔（G.Cantor）被誉为集合论的创始人。 托尔（ ）被誉为集合论的创始人。 集合论在计算机科学、人工智能领域、逻 集合论在计算机科学、人工智能领域、 在计算机科学 辑学及语言学等方面都有着重要的应用， 辑学及语言学等方面都有着重要的应用 ， 对 于从事计算机科学的工作者来说， 集合论是 于从事计算机科学的工作者来说 ， 集合论 是 不可缺少的理论知识， 不可缺少的理论知识 ， 熟悉和掌握它是十分 必要的。 必要的。

离散数学电子教材3a

离散数学电子教材3a

第3章 集合与关系集合是数学中最基本的概念之一，是现代数学的重要基础，并且已渗透到各种科学与技术领域中。

对计算机工作者来说，集合论是不可缺少的数学工具，例如在编译原理、开关理论、数据库原理、有限状态机和形式语言等领域中，都已得到广泛的应用。

集合论的创始人是康托（G .Cantor ，1845—1918）。

他所做的工作一般称为朴素集合论。

由于朴素集合论在定义集合的方法上缺乏限制，从而出现了称之为悖论的某些矛盾。

为了消除这些悖论，很多数学家，象Hilbert 、Fraenkel 和Zermelo 等都认真研究了产生悖论的原因，并在致力于问题解决的过程中，获得了种种出色的发现，由此导致了公理化的集合论系统的建立，使集合理论日臻完善。

本章介绍的集合论十分类似于朴素集合论，它具有数学分支的基本特征，象平面几何中的点、线、面一样，采纳不加定义的原始概念，提出符合客观实际的公设，确立推理关系的定理。

在我们规定的范围内，既不会导致悖论，也不会影响结论的正确性。

本章重点讨论关系（主要是二元关系），它仍然是一种集合，但它是一种更为复杂的集合。

它的元素是序偶，这些序偶中的两个元素来自于两个不同或者相同的集合。

因此，关系是建立在其它集合基础之上的集合。

关系中的序偶反映了不同集合中元素与元素之间的关系，或者同一集合中元素之间的关系。

本章将讨论这些关系的表示方法、关系的运算以及关系的性质，最后讨论集合A 上几类特殊的关系。

3.1 集合的基本概念3.1.1 集合与元素集合(set)（或称为集）是数学中的一个最基本的概念。

所谓集合，就是指具有共同性质的或适合一定条件的事物的全体，组成集合的这些“事物”称为集合的元素。

例如：班里的全体同学、全国的高等学校、自然数的全体、直线上的所有点等，均分别构成一个集合，而同学、高等学校、每个自然数、直线上的点等分别是所对应集合的元素。

集合常用大写字母表示，集合的元素常用小写字母表示。

若A 是集合，a 是A 的元素，则称a 属于A ，记作a A ∈；若a 不是A 的元素，则称a 不属于A ，记作。

离散数学_第一章_集合

离散数学_第一章_集合

3
离散数学
叙述恰当严谨，论证详尽严密，内容新颖丰富是本课 程的特点。 离散数学具有抽象性、非线性、非寻绎性、构造性、 结构性、整体性等结构性数学特点。 证明方法除了大量的运用常用的（数学）归纳法、演 绎法、反证法、归谬法、二难法、二分法、枚举法 （穷举法）、相容排斥法等方法之外，特别着重于存 在性、结构性、构造性方法，以及各部分内容自己所 特有的方法（比如图论的删点增点方法、删边增边方 法、伸路蹦圈方法）。
20
离散数学
X x Ａ y
Ｂ
例.X={a,b,c,d,e,f},A={ a,c,d} ,B={c, d,e} 。则 (AB)(BA) 。 即A与B互不包含
定理1.设A,B,C为任意三个集合。那么 (1) 自反性：A A (每个集合是它自己的子集) ； (2) 反对称性：AB BA A=B ； (3) 传递性：AB BC AC ； 这说明包含关系是集合间的半序关系(参见第二章 §6 )。 [证明].(1)(采用元素法)对于任何元素xX，若xA，则 xA。因此，根据元素x的任意性，可知AA。所以 包含关系是自反的；
18
离散数学
无重复性是集合的四大性质之一。 五.空集（empty,null,void set）：记为 空集是没有成员的集合。即 注.将空集作为集合实 际上是集合运算的封 x(x）（所谓的空集公理）； 闭性所要求的 ! 所以={ }； 空集是集合(作这点规定是运算封闭性的要求)。 空集是唯一的。因为若有两个空集，则它们有完全 相同的元素(都没有任何元素)，所以它们相等，是同 一集合。 六.全集（universe of discourse）：记为X 全集是所要研究的问题所需的全部对象（元素） 所构成的集合。 全集给个体（研究的对象）划定适当的范围。

离散数学(第三版)陈建明,刘国荣课后习题答案

离散数学(第三版)陈建明,刘国荣课后习题答案

离散数学辅助教材概念分析结构思想与推理证明第一部分集合论刘国荣交大电信学院计算机系离散数学习题解答习题一（第一章集合）1. 列出下述集合的全部元素：1）A={x | x ∈N∧x是偶数∧x＜15}2）B={x|x∈N∧4+x=3}3）C={x|x是十进制的数字}[解] 1）A={2，4，6，8，10，12，14}2）B=∅3）C={0，1，2，3，4，5，6，7，8，9}2. 用谓词法表示下列集合：1）{奇整数集合}2）{小于7的非负整数集合}3）{3，5，7，11，13，17，19，23，29}[解] 1）{n n∈I∧(∃m∈I)(n=2m+1)}；2）{n n∈I∧n≥0∧n<7}；3）{p p∈N∧p>2∧p<30∧⌝(∃d∈N)(d≠1∧d≠p∧(∃k∈N)(p=k⋅d))}。

3. 确定下列各命题的真假性：1）∅⊆∅2）∅∈∅3）∅⊆{∅}4）∅∈{∅}5）{a，b}⊆{a，b，c，{a，b，c}}6）{a,b}∈(a，b，c，{a，b，c})7）{a，b}⊆{a，b，{{a，b，}}}8）{a，b}∈{a，b，{{a，b，}}}[解]1）真。

因为空集是任意集合的子集；2）假。

因为空集不含任何元素；3）真。

因为空集是任意集合的子集；4）真。

因为∅是集合{∅}的元素；5）真。

因为{a，b}是集合{a，b，c，{a，b，c}}的子集；6）假。

因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；7）真。

因为{a，b}是集合{a，b，{{a，b}}}的子集；8）假。

因为{a,b}不是集合{a，b，{{a，b}}}的元素。

4. 对任意集合A，B，C，确定下列命题的真假性：1）如果A∈B∧B∈C，则A∈C。

2）如果A∈B∧B∈C，则A∈C。

3）如果A⊂B∧B∈C，则A∈C。

[解] 1）假。

例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。

离散数学第3章_集合

离散数学第3章_集合

第3章 集合
(2) 所谓“彼此不同”是指集合中相同的个体不能算 作不同的元素, 所以｛1, 1, 2｝就是｛1, 2｝。 用列举法 表示集合时, 要求列举的元素各不相同。 有限集合的基 数是指该集合中不同元素的个数。 (3) 集合中的元素没有限制, 不一定要求元素具有 某种共同的特性, 如允许｛2, a, 张三｝这样的集合。 集 合的元素还可以为集合, 即允许｛a, ｛a｝, ｛b｝, ｛a, b ｝｝这样的集合。
1) 用反证法。 若 A, 由定义知, 有元素a∈
而a A。 这与空集的定义矛盾, 所以必有 A。
1和 2 , 则根据1)有 2) 若有两个空集 1 2, 2 , 1 由定义 3.1―3有 1 2。
第3章 集合
定义 3.1―5 当我们所讨论的集合都是某一集合的 子集时, 这某一集合就称为全集, 并用Ｕ表示。 因为只要求全集包含我们讨论的所有集合, 所以根 据讨论的问题不同, 可以有不同的全集, 即全集不是唯 一的。 但是为了方便起见, 在以后的讨论中我们总假定 有一个足够大的集合作为全集, 至于全集是什么, 我们 有时并不关心。
2{0,1}
2
＝ ｛ , ｛ ｝ , ｛｛ 0 ｝｝ , ｛｛ 1 ｝｝ ,
｛｛0, 1｝｝, ｛ , ｛0｝｝, ｛ , ｛1｝｝, ｛ , ｛0, 1｝｝, ｛｛0｝, ｛1｝｝, ｛｛0｝, ｛0, 1｝｝, ｛｛1｝,
, ｛0｝, ｛1｝｝, ｛ , ｛0｝, ｛0, ｛0, 1｝｝, ｛
第3章 集合
集合A中元素的个数称为A的基数, 记作|A|。 当|A| 是有限数时, 集合A称作有限集, 否则称为无限集。 表示一个集合的方法通常有以下两种: 第１种称为列举法。 这种方法是把集合的元素全 部写在一个花括号里, 元素之间用逗号分开。 如Z4用 列举法表示是｛0, 1, 2, 3｝。 列举法基本上用于有限集, 但对一些有一定规律的 无限集, 也可以用列举法写出少数元素, 并加省略号表 示。 如自然数集N用列举法表示是｛1, 2, 3, …｝, 根据 所列元素, 容易判断N中的其余元素。

离散数学第三章总结

离散数学第三章总结

第三章总结集合是一个不能精确定义的基本概念。

把具有共同性质的一些东西，汇集成一个整体，就形成一个整体。

说明集合的方法有两种：1.列举法2.叙述法。

外延性原理：两个集合是相等的，当且仅当它们有相同的成员。

1．A⊆A 自反性2．（A⊆B）∧(B⊆C)⇒(A⊆C) 传递性3．若A⊆B，且A≠B则B⊈A 反对称性集合A和B相等的充分必要条件是这两个集合互为子集。

对任何集合A，⏀⊆A。

给定集合A，由集合A的所有自集为元素组成的集合，称为集合A 的幂集。

集合的交运算a)A∩A=A幂等律b)A∩⏀=⏀零律c)A∩E=A同一律d)A∩B=B∩A交换律e)（A∩B）∩C=A∩（B∩C）结合律集合并运算a)A⋃A=Ab)A⋃E=Ec)A⋃⏀=Ad)A⋃B=B⋃Ae)(A⋃B) ⋃C=A ⋃(B⋃C)分配律a)A∩(B⋃C)=(A∩B)⋃（A∩C）b)A⋃(B∩C)=(A⋃B)∩(A⋃C)设A，B为任意两个集合，所有属于A二不属于B的一切元素组成的集合S称为B对于A的补集，或相对补，记作A-B。

设E为全集，对任一集合A关于E的补E-A，称为集合A的绝对补。

∼(A⋃B)=∼A∩∼B ∼(A∩B)= ∼A⋃∼BA-B=A∩∼B A-B=A-(A∩B)A∩(B-C)=(A∩B)-(A∩C)设A，B为两个集合，若A⊆B，则a)∼B⊆∼A b)(B-A)⋃A=B 令A和B是任意两个集合，若序偶的第一个成员是A的元素，第二个元素是B的元素，所有这样的序偶集合，称为集合A和B的笛卡尔积或直积，记A×B.笛卡尔积不能交换。

不能结合。

保序，可分配。

设A,B,C,D为四个非空集合，则A×B⊆C×D的充要条件A⊆C，B⊆D.A×B=⏀⇔A=⏀⋁B=⏀若Z和S是从集合X到集合Y的两个关系，则Z，S的并交补差仍是X到Y的关系。

关系表示可用列举法，关系图，矩阵。

MR主对角线上的元素全是1，GR的每个顶点处均有自环。

离散数学第三章第四节资料

离散数学第三章第四节资料
R的关系图如下：
8
2、等价关系（3）
设Z为整数集合，R为Z上的关系，K为正整数，令 R={<x,y>|x,yZ(x-y)/KZ}
称R为模K同余关系。一般记作
R={<x,y>|x,yZx≡y(modK)} 并称x与y模K相等。容易证明，R是等价关系。
证：设任意a、b、cZ， 因(a-a)/K=0，故<a,a>R，说明R是自反的。
反 之 ， 若 A/R1= A/R2 ， 则 对 任 意 [a]R1A/R1 ， 必 有 [c]R2A/R2，使得[a]R1= [c]R2。对任意<a,b>R1，有
<a,b>R1 a[a]R1b[a]R1 a[c]R2b[c]R2 <a,b>R2
这说明R1R2，同理可证R2R1。所以R1=R2。
证：1、A/R={[a]R|aA},显然 [a]R A
aA
2、对aA，有a[a]R，所以A中的每个元素都属于 某个分块。
3、下面证明A中的任一个元素仅属于某一个分块。
设aA ，a[b]R且a[c]R，那么，bRa，cRa 。因 R对称，所以aRc。又因R是传递的,所以bRc。按定理3, [b]R=[c]R 。
={A1B1,A1B2,A2B1,A2B2,A3B1,A3B2} 中的各元素分别表示各班男生和女生的集合。
4
1、集合覆盖与划分（4）
定理1 若1={A1, A2,…, Ar}与2={B1, B2,…, Bs}是同一 集合X的两种划分，则1、 2的交叉划分
={Ai Bj|1ir, 1js}
也是集合X的一种划分。
故[a]R[b]R。 同理可证[b]R[a]R。 故[a]R=[b]R 。
反之,若[a]R=[b]R ,则 a[a]R a[b]R bRa aRb

最新离散数学课件第三章集合与关系-2精品文档

最新离散数学课件第三章集合与关系-2精品文档
中A表示所有动物Animal的集合, P表示所有植物 Plant的集合。
B也可划分成 {F, L},其中F表示史前First生 物,L表示史后Last生物。
它们的交叉划分为 : D = {A∩F, A∩L, P∩F, P∩L},
其中A∩F是史前动物, A∩L是史后动物, P∩F是史前植物, P∩L是史后植物。
定义3-9.2 若S1={A1…Am},S2={B1…Bn}是A的二个划
分,则
S={Ai∩Bj|AiS1∧BjS2}
称为A的交叉划分。
定理3-9.1 设 {A1,A2,…,Am}与{B1,B2,…,Bn}为同 一集合A的两个划分。则其交叉划分Ai∩Bj亦是原 集合的一种划分。
交叉划分举例
例：设B是所有生物的集合, 可划分成{A, P}, 其
② 因为 R s(R),故 st( R ) st(s( R )) 而st(s( R ))= sts(R) = s(ts( R )) = ts( R )
st( R ) ts( R ).
注： st(R)ts(R)未必成立。 反例：设R={ <a,b>,<c,b> }
则s(R)={ <a,b>,<b,a>,<c,b>,<b,c> } t(s(R))={ <a,b>,<b,a>,<c,b>,<b,c>,
离散数学课件第三章集合与关 系-2
复合关系举例
例：A={1，2，3，4}，B={3，5，7}，C={1，2，3} R={<2,7>，<3,5>，<4,3>}，S={<3,3>，<7,2>} 则 R◦S={<2，2>，<4，3>} 如图所示：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

22
离散数学
无重复性是集合的四大性质之一。 五.空集(empty,null,void set)：记为 空集是没有成员的集合。即 x(x) (所谓的空集公理)； 所以={ }； 空集是集合（作这点规定是运算封闭性的要求）。 空集是唯一的。因为若有两个空集，则它们有完全 相同的元素（都没有任何元素），所以它们相等，是 同一集合。 六.全集（universe of discourse）：记为X 全集是所要研究的问题所需的全部对象（元素） 所构成的集合。 23 全集给个体（研究的对象）划定适当的范围。
离散数学
集合论是一种语言。它可以作为别的学科的描述工具 语言。 二.集合的表示法： 我们规定用花括号——{ } 表示集合。 (1)文字表示法： 用文字表示集合的元素，两端加上花括号。 { 在座的同学 }； { 奇数 }； { 去年的下雨天 }； { 高等数学中的积分公式 }； { 闭区间[0,1]上的连续函数 }； 比较粗放。比较适合在对集合中的元素了解甚少、不 详，难以用精确的数学语言来刻划时使用。 (2)元素列举法（罗列法）： 15
24
离散数学
八.子集（subset）： 对于两个集合A，B，若A中的每个元素x都是B 的 一个元素，则称A包含在B中（或者说B包含A ），记 为AB。同时称A是B的子集（称B是A 的超集 (superset)）。即 AB x(xA xB) 。
X A B
录
集合 关系 函数 代数系统 格与布尔系统 图论
3
离散数学 Discrete Mathematics
序言：
离散数学是现代数学的一个重要分支，计算机科学 基础理论的核心课程。它充分描述了计算机科学的 离散性特点，是随着计算机科学的发展而逐步建立 起来的新兴的基础性学科。 本课程作为计算机科学的基础性课程，把握离散数 学的关键性问题，介绍五大块内容：集合论、代数 系统、布尔代数、图论、数理逻辑。 这些和计算机科学密切相关的理论的结构按排，既 着重于各部分之间的紧密联系，又深入探讨各部分 内容的概念、例子、理论、算法、以及实际应用。
19
离散数学
为了解决集合论中的悖论问题，人们产生了类型论和 形式化公理化集合论(ZF和ZFC公理系统)，以求排除集 合论中的悖论。 近年来，基于ZFC公理系统和一阶逻辑(谓词逻辑) ， 人们提出了抽象的计算机程序设计语言__Z语言。 在公理化集合论中，人们引进了类(class)的概念。
不包含悖论的类 (OK类) 集合(可进行运算) 类 包含悖论的类 (固有类) 非集合(不能进行运算)
离散数学
全集一般用一个矩形框来表示：
X
七.单元素集合（singleton set）：
只含一个元素的集合称为单元素集。 例如 { a }； { 张三 }； {} 左边是空集；右边不是空集，而是单元 素集合，有一个成员 ；这说明：差别在于级别。 即，右边的集合级别高。 单元素集合是构造复杂集合的‘原子’。

离散数学
的成员。 (2)a 不属于 A，记为 aA或a A ，称 a 不是 A 的 元素或a 不是 A 的成员。
A
A
a aA aA
a
判断个体 a 属于 A 还是不属于 A ，必须使用个体的 可辨认性，而且个体的可辨认性是无二义性的，即 或者 a 属于 A 或者 a 不属于 A，二者居其一且只居 其一。 14
16
离散数学
{ x: x2 = 1 }； { y : y 是开区间 (a,b) 上的连续函数 }；（混合表示 法） { 使 x2 = 1 的实数 } ={ 1，-1 } ={ x : x2 = 1 } 比较适合在对集合中的元素性质了解甚详，且易于用 精确的数学语言来刻划时使用。 外延(extension) ：集合{ x:P(x) }称为性质谓词P(x) 的 外延； 内涵(intension,connotation)：性质谓词P(x) 称为集合 { x:P(x) }的内涵； 由此看到，采用谓词法定义集合，关键是要得出内 涵P(x) ，并且显然有如下的
20
离散数学
本章我们所讲解的集合论是‘朴素(naive)’集合论； 所讨论的集合一般也不会产生悖论。 三.集合的名字： (1)大写的拉丁字母：例如A={x: x =1},B={-1,1}； (2)小写的希腊字母：例如={a,b,c},={n:nN3︱n}； (3)花写的徳文字母：例如={y:yR0y 1}, ={u:u I u+30} ； 不够用时可以加下标。 同一个集合可以有几个名字。 四.集合的相等（equality） ： 外延性原理：两个集合相等，当且仅当，它们的成员 完全相同。即 A=B x(xA xB) ；
10
离散数学
集就是“乌合之众”。不考虑怎样“乌合”起来的， 众可以具体，可以抽象。 这种乌合性被归纳为集合的一条性质 任意性：任意性是说组成集合的元素任意； 构成的法则任意； 什么都可以构成集合，不加任何限制。 任意性是集合的四大性质之一。 4. 集合论之父G.Cantor（1845-1918）说： 集合是由总括某些个体成一个整体而成的。对于每 个个体，只设其为可思考的对象，辨别它的异同。个 体之间并不需要有任何关系。
4
离散数学
叙述恰当严谨，论证详尽严密，内容新颖丰富是本课 程的特点。 离散数学具有抽象性、非线性、非寻绎性、构造性、 结构性、整体性等结构性数学特点。 证明方法除了大量的运用常用的（数学）归纳法、演 绎法、反证法、归谬法、二难法、二分法、枚举法 （穷举法）、相容排斥法等方法之外，特别着重于存 在性、结构性、构造性方法，以及各部分内容自己所 特有的方法（比如图论的删点增点方法、删边增边方 法、伸路蹦圈方法）。
17
离散数学
概括原理：集合{ x:P(x) }恰由那些满足性质谓词P(x) 的元素组成。即 x{ x:P(x) } (当且仅当) P(x)真 。 悖论(paradox)： 所谓悖论是指这样一个所谓的命题P，由P真立即推 出P假；由P假立即推出P真；即 P真P假 。 理发师悖论： 某偏远小山村仅有一位理发师。这位理发师规定： 他只给那些不给自己刮脸的人刮脸。那么要问：这位 理发师的脸由谁来刮？ 如果他给自己刮脸，那么，按他的规定，他不应该 给自己刮脸； 如果他不给自己刮脸，那么，按他的规定，他应该 给自己刮脸； 18
21
离散数学
两个集合不相等，记为AB ； 根据这个定义，关于集合我们可得下列性质： (1) 无序性：集合中的元素是无序的。例如 {a,b,c}= {b, a, c} = {b , c, a} 因此，为了使用方便，我们可任意书写集合中元 素的顺序。 但一般情况下，通常采用字母序、字典序；有时， 还需要强行命名一种序； 无序性是集合的四大性质之一。 (2)无重复性：集合中元素的重复是无意义的。例如 {a, a, a, a, b, b, b, c , c}= {a, b, c} 包(bag)：若允许元素重复称为包。例如 {a, a, a, a, b, b, b, c , c} 一般记为{4a, 3b, 2c}
离散数学
将集合中的元素逐一列出，两端加上花括号。 { 1，2，3，4，5}； { 风，马，牛 }； { 2，4，6，8，10，… }； { 3，7，11，15，19，… }； 比较适合集合中的元素有限（较少或有规律），无限 （离散而有规律）的情况。 (3)谓词表示法： { x:P(x) } 或者{ x︱P(x) } 其中：P表示 x 所满足的性质（一元谓词）。 { x : x I （且） x8} ={…，-3，-2， -1，0，1，2，3，4，5，6 ,7 } ；
离散数学
综上所述集合的概念有三要素： 1. 个体（元素） 2. 个体的可辨认性 3. 集合（动词，汇到一块） 通常用小写拉丁字母表示个体：a、b、c、d、… 通常用大写拉丁字母表示集合：A、B、C、D、… 有时还用德文花写字母表示集合：ℬ,℘,ℛ,ℰ,ℱ,ℳ, … 关于个体的辨认有赖于各方面公认的知识。 一.个体与集合之间的关系： 个体与集合之间的关系称为属于关系。 对于某个个体 a 和某个集合 A 而言， 只有两种可能： (1)a 属于（belong to） A，记为 aA（记号 是希 腊字i的第一个字母，意思是“是”。由意大利数 学家G.Peano首先采用），同时称 a 是 A 的元素或A 13
6
离散数学
于求网络的最小生成树等图的算法中。 3)函数 函数可以看成是一种特殊的关系，计算机中 把输入、输出间的关系看成是一种函数。类似地，在开 关理论、自动机原理和可计算性理论等领域中，函数都 有极其广泛的应用，其中双射函数是密码学中的重要工 具。
7
空集 全集 单元素集 子集 幂集 集合 交集 并集 余集 差集 环和集 环积集
5
离散数学
集合论在计算机科学中的应用
集合论包括集合﹑关系和函数3部分 1)集合 集合不仅可以表示数，而且可以像数一样进 行运算，还可以用于非数值信息的表示和处理，如数据 的增加、删除、排序以及数据间关系的描述，有些很难 用传统的数值计算来处理的问题，却可以用集合来处理。 因此，集合论在程序语言、数据结构、数据库与知识库、 形式语言和人工智能等领域得到了广泛的应用。 2)关系 关系也广泛地应用于计算机科学技术中，例 如计算机程序的输入和输出关系、数据库的数据特性关 系和计算机语言的字符关系等，是数据结构、情报检索、 数据库、算法分析、计算机理论等计算机领域中的良好 数据工具。另外， 关系中划分等价类的思想也可用
离散数学
西安交通大学 电子与信息工程学院 计算机软件所 刘国荣
1
离散数学
目 标
掌握集合论、代数系统、布尔代数、图论 的基本思想和方法，提高用集合论、代数系 统、布尔代数、图论的思想和方法分析问题 和解决问题的能力。
2
离散数学
目
序言 第三章 第四章 第五章 第六章 第七章 第八章
11