离散数学(第3章)陈瑜素材.ppt

计算机科学与工程学院 陈瑜 Email：chenyu.inbox@ * 第三章 集合及其运算 集合是数学中最基本的概念之一,是现代数学的重要基础,它已深入到各种科学和技术领域中。对计算机科学与技术的工作者来说,更是不可缺少的工具。本书各部分贯穿着集合论的思想。计算机科学的许多分支都大量用到集合的概念和知识,如数据结构,程序语言,数据库,人工智能等。 集合论的主要特点:研究问题的广泛性,分析思考问题的抽象性,处理问题的统一性,特别便于描述和研究离散对象及其关系。 §3.1 集合论的基本概念 二、集合的表示法： 2、隐式法（叙述法）：用一集合之元素所具有的共同性质来刻划这个集合。 一般表示方法：P＝{x|P(x)} 1）“｜”前面的x代表集合P中的任意元素 2）“｜”后面的P(x)表示x必须具有性质P 其突出优点是原则上不要求列出集合中全部元素，而只要给出该集合中元素的特性 例1： S1＝{x | x是正偶数} S2＝{x |（x?Z）并且（x0)} S3＝{x | x是四川大学的学生} S4＝{x | x是“letter”中的字母} 3、归纳法：归纳法是通过归纳定义集合，主要由三部 分组成。第一部分：基础。它指出某些最基本的元素属于 某集合；第二部分：归纳。指出由基本元素造出新元素的 方法；第三部分：极小性。指出该集合的界限。 第一部分和第二部分指出一个集合至少要包括的元素，第三部分指出一个集合至多要包含的元素。 例2 ：集合M是按如下方式定义： 1）每一个英文字母都是M中的元素； 2）如果P、Q是M中的元素，则PQ、QP也是M中的元素； 3）有限次使用（1）、（2）后所得到的字符串都是M中的元素。 4、递归指定集合 通过计算规则定义集合中的元素 5、巴科斯范式BNF表示法 BNF（Backus Normal Form）常常用来定义高级程序设计语言的标识符或表达式集合。 6、文氏图（Venn） 文氏图解是一种利用平面上点的集合作成的对集合的图解。一般用平面上的圆形或方形表示一个集合。 7、特征函数表示法 定义3.1 设A是集合,称 为A的特征函数。（它表明了集合与其成员的关系） 对某个集合Ａ和元素ａ来说，ａ或者属于集合Ａ，或者不属于集合Ａ，两者必居其一，且仅居其一。 ａ是集合Ａ的元素或ａ属于Ａ，记为： a?A ａ不是Ａ的元素或ａ不属于Ａ，记为： a?A 罗素悖论 罗素悖论 三、集合之间的关系与子集 定义3.2：设有集合A与B，若A中的每一个元素都是B中的元素，则称A是B的子集或B包含A，记为： A?B或B?A 上述包含定义又可形象地叙述为： B?A?对任意x，如x?B，则x?A。 定义3.3：设A、B是任意两个集合，如果A?B且B?A，则称A与B相等，记为A=B。 符号化表示为： A=B?A?B且B?A。 如果A和B不相等，则记作A?B。 基 数 性质3 外延性原理 §3.2 集合的运算 交集 推广 差集 补集 对称差 关于运算“差”和“补”的几个性质： 定理3.1： §3.4 集合的幂集和笛卡尔集★ ★ 例10： 设Ａ＝{ａ,ｂ}，则： 1）2A＝{?,{ａ},{ｂ},{ａ,ｂ}} 2）对于空集?，有： 2?＝{?} 2{?}＝{?,{?}} 3）?({1,{2,3}})={Φ,{1},{{2,3}},{1,{2,3}}} 定理3.2： 设A和B是两个集合， 1）如B?A， 则2B?2A 2）若集合Ａ有ｎ个元素，则集合Ａ共有2n个子集， 即：|?(A)|＝ 2n 。 二. 笛卡尔积(直积) Descartes 定义3.12:设给定n≥1个集合A1,A2,…,An,称A1×A2×…×An={a1,a2,…,an︱ai?Ai,1≤i ≤n} 为A1,A2,…,An的笛卡尔积。 对所有的i,Ai=A时, A1×A2×…×An简写成An ,如A×A=A2,A×A×A=A3 如果所有的集合都是有穷集合,则n个集合的笛卡尔积的基数为: |(A1×A2×…×An)|= |A1|×|A2|×…×|An| 集合的笛卡尔积不服从交换律,还可证明不服从结合律,但×对U, ∩可左右分配。 定理3.3:设A,B,C是任意三个集合,则 ①A×(BUC)=(A×B)U(A×C) ②A×(B∩C)=(A×B)∩(A×C) ③(BUC)×A=(B×A)U(C×A) ④(B∩C)×A=(B×A)∩(C×A) 定理3.4 :A,B,C为任意集合,C ? Φ,则 ①A ? B i