离散数学讲义 第四章集合论.pptVIP

* 第四章 集合 集合的概念与表示 集合的运算 Venn氏图及容斥原理 集合的划分 4.1 集合的概念与表示 将一个确定的，可以区分的事物的全体称为集合，而这些事物称为集合的元素。 若a是A的元素 称a属于A，记作a?A。 若a不是A的元素 称a不属于A，记作a?A。 集合用大写字母A，B,…来表示，而集合的元素一般用小写字母表示 元素个数有限的集合称为有限集。元素 个数无限的集合称为无限集。有限集的元 素的个数记作?A?或#A，称为A的基数。 4.1 集合的概念与表示 关于集合，有两点特别注意： 1）集合元素的无序性 2）集合中的元素不计重度 集合的表示方法： 列举法 例如：A={a,b,c,d} N={0,1,2…} Zm={0,1,2…,m-1} 4.1 集合的概念与表示 集合的表示方法： 谓词描述法： A={ x ?x具有某种性质} 例如： B= {x ?1≤x≤5,x∈R} C={ x ?x2-1=0, x∈R} D={(x,y)?x2+y2≤1，x,y∈R} 4.1 集合的概念与表示 集合的表示方法： 递归法： (1)基本项 (2)递归项 (3)极小化 例如：集合Ck={0,k,2k,...}的递归定义： 1）0∈Ck 2）若n∈Ck,则n+k∈Ck 4.1 集合的概念与表示 4.1 集合的概念与表示 集合间的关系： 包含：? 相等： A?B ??x(x?A? x?B) A?B也可记作BêA A=B ??x((x?A?x?B)∧(x?B?x?A)) ? A?B∧B? A ? 4.1 集合的概念与表示 集合间的关系： 真包含： A?B??x(x?A?x?B)∧$x(x?B∧ x?A) ? A?B∧B?A A?B也可记作B?A ? 4.1 集合的概念与表示 特殊集合 空集： 不含任何元素的集合称为空集，记作? 性质：空集是任何集合的子集 推论：空集是唯一的 给定一个非空集合A,则?和A称为A的 平凡子集。 4.1 集合的概念与表示 特殊集合 全集： 在所研究的同一个问题中，如果涉及到的 集合均是某一个集合的子集，则称该集合是 全集，记作?。 4.1 集合的概念与表示 特殊集合 幂集： 设A是一个集合，由A的所有子集组成 的集合称为A的幂集，记作ρ(A)或2A 谓词描述法表示：ρ（A）={u?u?A} 4.1 集合的概念与表示 例如：设A={0，1，2}写出A的全部子集 解：A的0元子集：? A的1元子集：{0}，{1}，{2} 2元子集：{0，1}，{0，2}，{1，2} 3元子集：{0，1，2} 定理：如A是有限集，若?A?=n则?ρ(A)?=2n 4.1 集合的概念与表示 例：A={a,{b}},写ρ （A） 解: ρ （A）={?，{a},{{b}},{a,{b}}} 例：设A={a, ?}判断下列结论是否正确 (1)??A，(2)??A，(3){?}?A， (4){?}?A,(5)a?A,(6)a?A, (7){a}?A,(8){a}?A 解：1)，2），3），5），8）是正确的 4.2 集合的运算 设A和B是两个集合，定义 A?B={x?x?A ? x?B} A?B={x?x?A ? x?B} A-B={x?x?A∧x?B} ?A={x?x?A且x?E} A?B={x?x?A且x?B?x?B且x?A} 定理：设A、B、C是三个集合，则有 (1)A?A?B，B?A?B (2)A?B?A，A?B?B。 (3)A?B?A?B (4)若A?B则A?B=A，A?B=B。 4.2 集合的运算 4.2 集合的运算 交换律 A?B=B?A，A?B=B?A 结合律 （A?B）?C=A?（B?C） （A?B）? C=A（B? C） 分配律 A?（B?C）=（A?B）?（A?C） A?（B?C）=（A?B）?（A?C） 幂等律 A?A=A，A?A=A 同一律 A??=A,A?E=A 4.2 集合的运算 零一律 A??=?，A?E=E 补余律 A??A=?，A??A=E 吸收律 A?（A?B）=A A?（A?B）=A 德摩根律 ?（A?B）=?A??B ?（A?B）=?A