离散数学第三章第一节素材.ppt

第三章 集 合 与 关 系 集合的概念是现代数学中最基本的概念之一，集合论是现代数学的重要理论基础，并且深入到各个科学与技术领域之中。对计算机科学而言，它在开关理论，数据结构与形式语言等领域中有着广泛的应用。 本章介绍集合论的基础知识，包括集合的运算、性质、序偶、关系、函数、基数等。在方法上尽量采用前两章的符号和推理规则，作出形式的证明。 第三章 目录 第3-1讲 集合的概念和集合的运算 第3-2讲 笛卡儿积与关系 第3-3讲 复合关系、逆关系与闭包运算 第3-4讲 等价关系 第3-5讲 序关系 第3-1讲 集合的概念和运算 1. 集合的概念 2. 集合的表示 3. 集合间的关系 4. 幂集 5. 集合的运算 6. 集合运算的性质 7. 课堂练习 8. 第3-1讲 作业 1、集合的概念 集合是数学中最基本的概念之一，如同几何中的点、线等概念一样，不能再用其它有明确定义的词来定义它。 将一些确定的、彼此不同的事物的全体称之为集合。对于给定的集合和事物，应能判断这个特定的事物是否属于给定的集合。集合中的事物称为该集合的元素。 2、集合的表示 列举法：列出集合的所有元素，并用花括号括起来，元素之间用逗号隔开。例如： S={e1 ,e2 ,…,en} (具有n个元素的有限集) Ａ＝{a,{b,c},{{d}}} （ a,{b,c},{{d}}是该集合的元素） Ｎ＝{0,1,2,3,... } (N是非负整数集) 在一个集合中，元素是彼此不同的，相同的元素被认为是一个元素，而且元素之间没有次序关系，例如集合{1,2,3}，{3,1,2}和{3,3,1,2}被视为同一个集合。 叙述法（或描述法） 用谓词概括出集合中元素的特性，以确定集合的元素。 S＝{x|Ｐ(x)}，如果Ｐ(e)为真，那麽e∈S，否则e?S。 例如，设A＝{x|x∈Ｎ∧3＜x≤8}，则A＝{4,5,6,7,8}。 2、集合的表示（续） 空集 定义1 不含任何元素的集合叫空集，记作Φ。 Φ＝{x|P(x)∧?P(x)}，P(x)是任意谓词。 例如，A={x∈R∧x2＋1＝0}是空集，式中Ｒ表示实数集合。 全集 定义2 在研究某一问题时，如果所有涉及的集合都是某一集合的部分元素组成的（子集），则称该集合为全集，记作Ｅ。即 Ｅ＝{x|P(x)∨?P(x)}。（P(x)是任意谓词） 显然，全集的概念相当于论域，它是一个相对概念。 3、集合间的关系 两个集合相等，当且仅当它们有相同的成员。 集合Ａ与Ｂ相等，记作Ａ＝Ｂ。 集合Ａ与Ｂ不相等，记作Ａ≠Ｂ。 定义１ 给定集合Ａ和Ｂ，如果Ａ中每个元素都是Ｂ中的元素，则称Ａ为Ｂ的子集，记作 Ａ?Ｂ或Ｂ?Ａ，读作“Ａ包含于Ｂ”或“Ｂ包含Ａ”。如果Ａ?Ｂ且Ａ≠Ｂ，则称Ａ为Ｂ的真子集，记作Ａ?Ｂ。 A?B ? (?x)(x∈A→x∈B) A?B ? (?x)(x∈A→x∈B)∧(?x)(x∈B∧x?A) 按子集的定义，对于任何集合A、B、C都有A?A (自反性)， (A?B)∧(B?C)?(A?C) (传递性) 3、集合间的关系（续1） 定理１ 设Ａ、Ｂ为两个集合，Ａ＝Ｂ当且仅当 Ａ?Ｂ且Ｂ?Ａ。即 (A＝B)?A?B∧B?A。 证明：两个集合相等，则它们有相同的元素。 (A＝B)?(?x)(x∈A→x∈B)∧(?x)(x∈B→x∈A) ?(A?B)∧(B?A)。 反之，若(A?B)∧(B?A)，如果A≠B，则A与B的元素不完全相同。设x∈A但x?B，这与A?B矛盾；或x∈B但x?A，这与B?A矛盾，故A与B的元素必相同，即A＝B。 3、集合间的关系（续2） 例1 证明对于任何集合A、B、C都有 (A?B)∧(B?C)?(A?C) 证：(A?B)∧(B?C) ?(?x)(x∈A→x∈B)∧(?x)(x∈B→x∈C) ?(?x)（(x∈A→x∈B)∧(x∈B→x∈C)） ?(?x)(x∈A→x∈C) ? A?C 3、集合间的关系（续3） 例3 证明空集是唯一的 证：假定Φ1和Φ2为二空集。 由定理2，Φ1?Φ2，Φ2?Φ1。 再根据定理1，Φ1＝Φ2 。 4、幂集 定义４ 集合Ａ的所有子集构成的集合叫Ａ的幂集，记作ρ(A)。 根据定义，ρ(A)={X|X?A}。例如,设Ａ＝{a,b,c},则 ρ(A)＝{Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 4、幂集（续） 定理３ 设A有ｎ个元素，则ρ(A)有2n个元