数理逻辑精品教学（华南理工大学）9-1-1 集合.ppt

第二部分 集合论 引例 有10名学生参加一个Party，一共要了8瓶饮料和6个雪糕，已知有1人什么也没要，其他人每种至多要1份，问：最后有多少人既要了饮料又要了雪糕？ 集合论的功能 ——是现代数学的重要基础，集合不仅可用来表示数及运算，更可用于非数值信息的表示和处理，如： 数据的维护 数据间关系的描述 有些很难用传统的数值计算来处理，但可用集合运算来处理 集合论 集合论的地位 ——它在计算机科学领域中是不可或缺的数学工具，在 形式语言 自动机 人工智能 数据库 等领域中都卓有成效地应用了集合论。 第二部分主要介绍集合论的基础知识，如 集合的基本概念 集合的运算 集合的性质 集合的关系 集合的函数等。 第9章 集 合 9.1 集合的概念和表示方法 9.2 集合间的关系和特殊集合 9.3 集合的运算 9.4 集合的图形表示法 9.5 集合运算的性质和证明 9.6 有限集合的基数 9.1 集合的概念和表示方法 集合是不能精确定义的基本的数学概念。 一个集合一般指的是一些可确定的、可分辨的事物构成的整体。 集合的元素——集合中的对象或个体。 集合的构成—— 集合可以由各种类型的事物构成。 例如： 26个英文字母的集合； C++语言中保留字的集合； 坐标平面上所有点的集合； 方程x2－1＝0的实数解集合； 集合的表示法 通常用大写英文字母来标记一些集合。 例如， 　　N ——代表自然数集合(0∈N)， 　　Z ——代表整数集合， 　 Q ——代表有理数集合， 　　R ——代表实数集合， 　　C ——代表复数集合。 集合的表示法——列举法 列举法（外延表示法） 列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。 例如，A={1,2,3,4,5}　 其中1是A的元素，记作1?A。 同样有2?A , 4?A …..。 但6不是A的元素，可记作6?A。 注意： 对于任何集合 A 和元素 x (可以是集合)， x?A和 x?A 两者成立其一，且仅成立其一——互补律. 元素与集合的关系 ——隶属关系 属 于 ? 不属于 ? 集合的表示法——描述法 描述法(内涵表示法)—— 用谓词概括集合中元素的属性。 例如: 集合 B={x|P(x)}， 表示B由使P(x)为真的全体x构成。 B={x|x ? Z ? 3?x?6 }，则B={4,5,6}。 注意 谓词P(x)的范围一定要明确清楚，否则集合无法构造。 如：A={x|P(x)}，P(x)：x是公园里的美丽的花。 诸如: P(x)：x?x 这样的谓词不能作为定义集合的性质条件。 若用这样的谓词来确定集合会产生悖论。 如：我只给不给自己理发的人理发。 集合的元素 集合的元素可以是任何类型的事物。 一个集合也可以作为另一个集合的元素。 例如，集合A={a, b, {c,d}, {{e}} }。 其中：a ? A，{c,d} ?A, {{e}} ?A, 但是：c ?A, e ?A。 在集合论中规定 元素之间是彼此相异的，并且是没有次序关系的。 如：{3,4,5}, {3,4,4,5}, {5,3,4}都是同一个集合。 A只有4个元素， 表示成|A|=4。 元素与集合隶属关系的层次结构 例 ： A={ a, {b,c}, d, {{d }} } {b,c} ?A d ?A {{d }}?A b ?A {d } ?A n元集——含有n个元素的集合的简称； 一个集合的含有m个元素的子集称作它的m元子集。 9.2 集合间的关系和特殊集合 定义 设A, B为集合，如果B中的每个元素都是A中的元素，则称B为A的子集合，简称子集。 这时也称B被A包含，或A包含B。记作B?A 或 A?B。 “B?A”的符号化表示为： B?A ??x(x?B?x?A) 如果不被包含，则记作B ? A ，符号化为： B ? A ? ?x (x?B ? x?A) 如：A={0,1,2}, B={0,1}, C={1,2} 则有 B?A, C ?A, 但C ? B。因为存在2，2?C 但 2?B。 集合相等的定义 集合相等的定义： 设A、B为任意集合， 如果A?B且B?A，则称A与B相等。记为A=B。 如果A与B不相等，记为A≠B。 集合相等的谓词公式表示 A=B ?A?B∧B?A ?(?x)(x?A→x?B)∧(?x)(x?B→x?A) ?(?x)(x?A?x?B) 结论：两个集合相等的充要条件是它们互为子集。 集合间的关系 例如： 设 A={1, 2}，B={1, {2} }，C={2, 1} 则 A=C A≠B 集合