离散数学第13讲讲解材料.ppt

* 第二部分 集合论 对于从事计算机科学工作的人们来说，集合论是必不可少的基础知识。例如有限状态机、形式语言等都离不开子集、幂集、集合的分类等概念。集合成员表和范式在逻辑设计、定理证明中也都有重要应用。 本部分从集合的直观概念出发，介绍了集合论中的一些基本概念和基本理论，其中包括集合、关系、函数等。 离散数学 第13讲 本讲基本知识点： 1、集合的基本概念 2、集合的运算 3、集合基本恒等式 第六章 集合代数 6.1 集合的基本概念 直观定义： 一些事物汇集到一起组成的一个整体称为集合，而这些事物就是这个集合的元素或成员。 集合通常用大写字母来标记，如N、Z、Q、R、C。 集合表示方法： 列元素法 A={1,2,3,4,5} 谓词表示法 B={x | x∈N ∧1≤x≤5 } 第六章 集合代数 集合的特征 互异性 {1,2,3,2,4}= {1,2,3,4} 无序性 {4,2,1,3 }= {1,2,3,4} 元素和集合之间的关系 属于（∈）或 不属于（ ? ） 如：对于A={ 1,{2,3},{{4}}}， 1 ∈ A, {2,3} ∈ A, 3 ? A. 可以用树形图表示这种关系。 考虑：4, {4}, {{4}}呢 ? 第六章 集合代数 如： A 1 {2,3} {{4}} 2 3 {4} 4 本书规定： 对于任何集合A，都有A ? A。 第六章 集合代数 定义6.1 设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。也称B被A包含，或B包含于A，或A包含B，记作B ? A。 如果B不被A包含，则记作B ? A。 包含的符号化表示为： B ? A ??x(x∈B ? x∈A) 例如：N ? Z ? Q ? R ? C, 而C ? R. 显然：对于任何集合A，都有A ? A。 第六章 集合代数 定义6.2 设A，B为集合，如果A ? B且B ? A，则称A与B相等，记作A=B。 如果A与B不相等，则记作 A≠B。 相等的符号化表示为： A=B ? A ? B ∧ B ? A 第六章 集合代数 定义6.3 设A，B为集合，如果B ? A且B≠A，则称B是A的真子集,也称B被A真包含，或B真包含于A，或A真包含B，记作B?A。 如果B不被A真包含，则记作 A ? B。 真子集的符号化表示为：B?A ? A ≠ B ∧ B ? A 例如：N ? Z ? Q ? R ? C, 而C ? C. 显然：对于任何集合A，都有A ? A。 第六章 集合代数 含有n个元素的集合简称为n元集，它的含有m(m≤n)个元素的子集叫做它的m元子集 。 任给一个n元集， 它的0元子集的个数为：Cn0, 即φ； 它的1元子集的个数为：Cn1 ,即单元集； 它的2元子集的个数为：Cn2 ； …… 它的n元子集的个数为：Cnn . 显然：任一n元集A的子集总数为： Cn0 + Cn1 + Cn2 …+ Cnn =2n 请通过列出集合S={a,b,c}的所有子集来验证此结论。 第六章 集合代数 定义6.5 设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A) 或 2A。 幂集的符号化表示为 P(A)＝｛x|x ? A｝ 例如：若B={1，2，c, d}，则P(B)=??? 定义6.6 在一个具体问题中，若所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。 第六章 集合代数 6.2 集合的运算 定义6.7 设A，B集合，A与B的并集A∪B，交集A∩B，B对A的相对补集A-B，分别定义如下： A∪B={x|x ∈A ∨ x ∈B} A∩B={x|x ∈A ∧ x ∈B} A - B={x|x ∈A ∧ x ? B} 如：A={1,2,3}, B={3,4,5}，C={6,7} 则A∪B、A∩B、A-B、 C∩B、C-B、C-C分别为？？？ 两个集合的并交运算可推广至n个集合： A1∪A2 ∪… ∪An ={x|x ∈A1∨x∈A2∨…∨ x∈An } A1∩A2 ∩ …∩An ={x|x ∈A1 ∧x∈A2∧ …∧ x∈An } 文氏图是用来描述集合关系与运算的很好的工具，请参见课本P96。 第六章 集合代数 定义6.8 设A，