离散数学教学课件03-集合与关系-3.1~3.3.pptVIP

第三章 集合与关系 Sets and Relations 第一节 集合的基本概念 定义：集合（Sets）是指某些可以辨别的不同对象的全体 一个集合是能作为整体论述的事物的集体。例如： 华北电力大学计算机专业2010级学生 硬币的正面和反面 某计算机中的全部内存 …… 集合是最简单的数学对象，大部分数学的本质问题都可以简化为集合论问题。 集合与元素 定义：元素（element）是指组成集合的对象， 也叫作成员（member）。 通常用大写字母A、B、X、Y……等表示集合用小写字母a、b、x、y……等表示元素 若a是集合A中的一个元素，则记为a ? A读作“a属于A”或“a在A中”（a is in A） 若a不是集合A中的一个元素，则记为a ? A或? (a ? A)读作“a不属于A”或“a不在A中”（a is not in A） 集合的表示 通常有3种方法表示集合： 枚举法——将集合中的所有元素都列举出来 例如：集合A是小于5的正整数。用枚举法表示为： A={1, 2, 3, 4} 在能清楚地表示集合成员的情况下可使用省略号。 例如：集合B表示1到50的整数集合。可以表示为： B={1, 2, 3, …, 50} 集合的表示 谓词描述法——用谓词描述出集合元素的公共特征 若P(x)是含有一个自由变元的谓词公式，则： S={x|P(x)}定义了集合S，S中的所有元素都满足谓词P(x)。 例如： A={x|小于5的正整数}： B={x|x ? I ∧ x5 ∧ x0} 集合的表示 归纳定义法（了解） 例如：能被3整除的正整数集合A，可以归纳定义（设论域为全体整数I）： 1) （基础） 3 ? A 2) （归纳）如果 x ? A，且 y ? A，那么 x+y ? A 3) （极小性）没有一个整数是A中的元素，除非它是应用条款1)和2)得出的。 集合与元素 集合的元素还可以是一个集合。例如： A={1, 2, 3, D}，而D={0, -1}A称为集合族（collections），或集合类 仅含有一个元素的集合称为单元素集合 要把单元素集合与集合中的元素区分开。例如： A={1, 2}，B={A} B是单元素集合，其中的唯一的一个元素是集合A 外延公理 集合的元素一旦给定，这个集合就完全确立。 外延公理：两个集合相等，当且仅当它们有相同的元素。若集合A与B相等，记为A=B；否则，记为A ≠ B 外延公理可以表示为： A=B ?(? x)(x ? A ? x ? B) 或 A=B?(?x)(x?A ? x?B)∧(?x)(x?B ? x?A) 外延公理 由外延公理可知：如果两个集合有相同的元素，那么不管集合是如何表示的，它们都相等。 列举法中，元素的次序是无关紧要的。{x, y, z} 与 {z, x, y} 是相等的集合 元素的重复出现无足轻重。{x, y} 和 {x, x, y, y } 和 {x, y, y} 都相等 集合的表示不是唯一的。{x|x2-3x+2=0} 和 {1, 2} 是相等的。 子集 定义：设A和B是任意两个集合，如果集合A的每个元素，都是集合B中的元素，称A是B的子集（Subset）（或B包含A，或A被包含于B），记为A ? B即： A ? B ?(? x)(x ? A ? x ? B) 例如：A={a, b}, B={a, b, c} 则A ? B 若集合B不包含集合A，记为A ? B 子集 定理：设A和B是两个集合，A=B当且仅当 A ? B且B ? A 证明： A=B ?(? x)(x ? A ? x ? B) ?(?x)((x?A ? x?B)∧(x?B ? x?A)) ?(?x)(x?A ? x?B)∧(?x)(x?B ? x?A) ? A ? B ∧ B ? A 推论：对于任意集合A，有A ? A 子集 定理：设A、B、C是三个集合，若 A?B 且 B?C ，则 A ? C 证明： A ? B ?(? x)(x ? A ? x ? B) B ? C ?(? x)(x ? B ? x ? 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 真子集 定义：设A和B是任意两个集合，若A ? B，且A≠B，则称A是B的真子集(或B真包含A，或A被真包含于B)，记为A ? B即： A ? B ? A ? B ∧ A≠B ?(? x)(x ? A ? x ? B) ∧ (? x)(x ? B