集合上的运算.pptVIP

南京信息工程大学数理学院 南京信息工程大学 离散数学教学组 制作 离 散 数 学 电 子 课 件 * 南京信息工程大学数理学院 * 2.1 集合的基本概念 2.2 集合上的运算 2.3 归纳法和自然数 2.4 语言上的运算 2.5 集合的笛卡儿乘积 第二章 集 合 * 南京信息工程大学数理学院 * 集合的概念是现代数学中最基本的概念之一，集合论是现代数学的重要理论基础，并且深入到各个科学与技术领域之中。对计算机科学而言，它在开关理论，数据结构与形式语言等领域中有着广泛的应用。 2、3章介绍集合论的基础知识，包括集合的运算、性质、序偶、关系、函数、基数等。在方法上尽量采用前两章的符号和推理规则，作出形式的证明。 * 南京信息工程大学数理学院 * 第2-1讲 集合的概念和运算 1. 集合的概念 2. 集合的表示 3. 集合间的关系 4. 幂集 5. 集合的运算 6. 集合运算的性质 7. 课堂练习 8. 第2-1讲 作业 * 南京信息工程大学数理学院 * 1、集合的概念 集合是数学中最基本的概念之一，如同几何中的点、线等概念一样，不能再用其它有明确定义的词来定义它。 将一些确定的、彼此不同的事物的全体称之为集合。对于给定的集合和事物，应能判断这个特定的事物是否属于给定的集合。集合中的事物称为该集合的元素。 通常，用大写的英文字母表示集合，用小写英文字母表示集合的元素。例如，习惯上用Ｎ表示非负整数的集合，用Ｑ表示有理数集合，Ｒ表示实数集合等等。 如果ａ是集合Ｓ的元素,记作ａ∈Ｓ,读作“ａ属于Ｓ”。如ｂ不是Ｓ的元素，记作 b?Ｓ，读作“ｂ不属于Ｓ”，它等价于 ?(b∈s)。若一个集合的元素个数是有限的，则称为有限集，否则称为无限集。 * 南京信息工程大学数理学院 * 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|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