集合论与图论(全套课件).ppt

1、2022-5-13集合论与图论第1讲1集合论与图论集合论与图论离散数学系列课程之一离散数学系列课程之一2022-5-13集合论与图论第1讲2教材教材 集合论与图论，离散数学二分册，耿素云，北大出版社，1998年2月2022-5-13集合论与图论第1讲3参考书参考书 离散数学习题集，耿素云，北大出版社 数理逻辑与集合论分册，1993年2月 图论分册，1990年3月课外读物2022-5-13集合论与图论第1讲42022-5-13集合论与图论第1讲5内容介绍 离散数学 集合论与图论 代数结构与组合数学 数理逻辑2022-5-13集合论与图论第1讲6内容介绍 集合论与图论 第一部分 集合论第1章 集合

2、第2章 二元关系第3章 函数第4章 自然数第5章 基数 内容介绍集合论与图论 第二部分 图论 第7章 图 第8章 欧拉图与哈密顿图 第9章 树 第10章 图的矩阵表示 第11章 平面图 第12章 图的着色 第13章 支配、覆盖、独立、匹配 第14章 带权图 2022-5-13集合论与图论第1讲72022-5-13集合论与图论第1讲8进度安排 课程将在4月底或5月初结束 第13周(5月18日)前考试2022-5-13集合论与图论第1讲9成绩评定 书面作业占10%，3道题/每次课 平时测验占30%，1小时/每次，2次 期末考试占60%2022-5-13集合论与图论第1讲10作业 时间：每周一交上周

3、作业，下周一发回 讲解：每次作业都有课上讲解 要求：正确、完全、简洁、清楚 Correct，Complete，Concise，Clear 提示：独立完成作业，可以讨论，但要杜绝抄袭2022-5-13集合论与图论第1讲11第1讲 命题逻辑基础 1. 命题、命题符号化 2. 合式公式、真值表、永真式 3. 逻辑等值式、推理定律 4. 形式化证明2022-5-13集合论与图论第1讲12命题符号化 简单命题： p,q,r,p1,q1,r1, 联结词： 合取联结词： 析取联结词： 否定联结词： 蕴涵联结词： 等价联结词： 逻辑真值： 0，1真值表(truth-table) 赋值(assignment)：

4、给变元指定0、1值 n个变元，共有2n种不同的赋值pqppqpqpqpq00110101110000010111110110012022-5-13集合论与图论第1讲13真值表(续)p qr(pq)rpqr00001111001100110101010111111101111111012022-5-13集合论与图论第1讲14永真式(tautology) 永真式:在各种赋值下取值均为真(重言式) 永假式:在各种赋值下取值均为假(矛盾式) 可满足式：非永假式p q (pq) pq(pq)(pq)001101011110111011112022-5-13集合论与图论第1讲152022-5-13集合论与

5、图论第1讲16逻辑等值式(identities) 等值： AB 读作：A等值于B 含义：A与B在各种赋值下取值均相等 AB 当且仅当 AB是永真式 例如： (pq)r pqr2022-5-13集合论与图论第1讲17常用逻辑等值式(关于与) 幂等律(idempotent laws)AAAAAA 交换律(commutative laws)ABBAABBA2022-5-13集合论与图论第1讲18常用逻辑等值式(关于与) 结合律(associative laws)(AB)CA(BC) (AB)CA(BC) 分配律(distributive laws)A(BC)(AB )(AC )A(BC)(AB )(

6、AC )2022-5-13集合论与图论第1讲19常用逻辑等值式(关于与) 吸收律(absorption laws)A(AB)AA(AB)A2022-5-13集合论与图论第1讲20常用逻辑等值式(关于) 双重否定律(double negation law)AA 德摩根律(DeMorgans laws)(AB)AB(AB)AB2022-5-13集合论与图论第1讲21常用逻辑等值式(关于0,1) 零律(dominance laws)A11A00 同一律(identity laws)A0AA1A2022-5-13集合论与图论第1讲22常用逻辑等值式(关于0,1) 排中律(excluded middle

7、)AA1 矛盾律(contradiction)AA02022-5-13集合论与图论第1讲23常用逻辑等值式(关于) 蕴涵等值式(conditional as disjunction)ABAB 假言易位(contrapositive law)ABBA 归谬论(AB )( AB )A2022-5-13集合论与图论第1讲24常用逻辑等值式(关于) 等价等值式(biconditional as implication)AB(AB)(BA) 等价否定等值式ABAB2022-5-13集合论与图论第1讲25等值式模式 A，B，C代表任意的公式 上述等值式称为等值式模式 每个等值式模式都给出了无穷多个同类型的

8、具体的等值式。2022-5-13集合论与图论第1讲26等值式模式(举例) 蕴涵等值式模式ABAB 取A=p，B=q时，得到pqpq 取A=pqr，B=pq时，得到(pqr)(pq)(pqr)(pq)2022-5-13集合论与图论第1讲27对偶原理一个逻辑等值式，如果 只含有 ， ， ，0，1那么，同时 把与互换 把 0 与 1互换得到的还是等值式2022-5-13集合论与图论第1讲28对偶原理(举例) 分配律A(BC)(AB )(AC )A(BC)(AB )(AC ) 排中律(excluded middle)AA1 矛盾律(contradiction)AA02022-5-13集合论与图论第1讲

9、29对偶原理(举例、续) 零律(dominance laws)A11A00 同一律(identity laws)A0AA1A2022-5-13集合论与图论第1讲30等值演算（举例） 例：(pq)rpqr 解： (pq)r (pq)r （蕴涵等值式） (pq)r （德摩根律） pqr （结合律） 2022-5-13集合论与图论第1讲31推理定律(deduction laws) 推出： AB 读作：A推出B 含义：当A为真时，B也为真 AB 当且仅当 A B是永真式 例如： (pq ) p q 推理定律（举例） (pq )p q (pq )p q 是永真式p q pq p(pq)p(pq)pq 0

10、011010101111100010011112022-5-13集合论与图论第1讲322022-5-13集合论与图论第1讲33常见推理定律 附加律A(AB) 化简律(AB)A2022-5-13集合论与图论第1讲34常见推理定律（续） 假言推理(AB ) AB 拒取式(AB ) B A 析取三段论(AB )B A2022-5-13集合论与图论第1讲35常见推理定律（续） 假言三段论(AB)(BC)(AC) 等价三段论(AB)(BC)(AC)2022-5-13集合论与图论第1讲36常见推理定律（续） 构造性两难(AB)(CD)(AC)(BD) 构造性两难(特殊形式)(AB)(AB)(AA)B 破坏

11、性两难(AB)(CD)(BD)(AC)2022-5-13集合论与图论第1讲37推理规则 前提引入规则：在证明的任何步骤上都可以引入前提 结论引入规则：在证明的任何步骤上所得到的结论都可以做为后继证明的前提 置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中又一个公式2022-5-13集合论与图论第1讲38推理规则（续） 附加规则：A(AB) A AB 化简规则：(AB)A2022-5-13集合论与图论第1讲39推理规则（续） 假言推理规则： (AB )ABAB A B 拒取式规则：(AB )B A2022-5-13集合论与图论第1讲40推理规则（续） 假

12、言三段论规则：(AB)(BC)(AC) AB BC A C 析取三段论规则：(AB )B A2022-5-13集合论与图论第1讲41推理规则（续） 构造性两难推理规则： (AB)(CD)(AC)(BD) 破坏性两难推理规则： (AB)(CD)(BD)(AC)2022-5-13集合论与图论第1讲42推理规则（续） 合取引入规则：(A)(B)(AB)AB AB2022-5-13集合论与图论第1讲43证明(举例) 证明： (pq)rq(pr) (pq) r (pq)r (蕴涵等值式) (pq)r (德摩根律) q(pr) (交换律、结合律) q (pr) (蕴涵等值式) q(pr) (蕴涵等值式)2

13、022-5-13集合论与图论第1讲44总结 等值式（16组、24条） 幂等律、交换律、结合律、分配律、吸收律； 双重否定律、德摩根律； 零律、同一律、排中律、矛盾律； 蕴涵等值式、等价等值式、假言易位、等价否定等值式 归谬论 推理定律（9条） 附加、化简 假言推理、拒取式、析取三段论、假言三段论、 等价三段论、构造性两难（特殊形式）、破坏性两难2022-5-13集合论与图论第1讲45习题 证明下面的等值式： (1) (pq )(pr) p(qr) (2) (pq)(pq) (pq)(pq) 证明本次课讲的基本等值式和推理定律2022-5-13集合论与图论第2讲46第2讲 一阶逻辑基础内容提要

14、1. 量词、谓词、个体词、命题符号化 2. 合式公式、解释、永真式 3. 一阶逻辑等值式 4. 一阶逻辑推理规则2022-5-13集合论与图论第2讲47一阶逻辑的字母表 个体常项: a, b, c, , a1, b1, c1, 个体变项: x, y, z, , x1, y1, z1, 函数符号: f, g, h, , f1, g1, h1, 谓词符号: F, G, H, , F1, G1, H1, 量词符号: , 联结词符号: , , , , 括号与逗号: (, ), ，2022-5-13集合论与图论第2讲48谓词(predicate) 谓词：表示性质、关系等；相当于句子中的谓语。 用大写英文

15、字母F,G,H,后跟括号与变元来表示。例如：F(x): x是人。G(x,y): x与y是兄弟。 n元谓词：含有n个变元。例如： F(x)是一元谓词， G(x,y)是二元谓词2022-5-13集合论与图论第2讲49量词(quantifier) 全称(universal)量词: “所有的”, “全部的”, 存在(existential)量词: “有一些的”, “某些的”, 唯 一 ( u n i q u e ) 存 在 量 词 : ! “恰好存在一个”2022-5-13集合论与图论第2讲50量词(举例) 设：F(x)：x是自然数。G(x)：x是偶数。 H(x) ： x是奇数。 I(x,y)：x=y

16、。 “有些自然数是偶数”。 x(F(x)G(x) “既有奇数又有偶数” 。xH(x)yG(y) 存在既奇又偶的数” 。x(H(x)G(x) “存在唯一的自然数0”。 !x(F(x)I(x,0)2022-5-13集合论与图论第2讲51个体常项(constant) 表示具体的特定对象 用小写英文字母a,b,c,来表示 例如： a:王大明，b:王小明， G(x,y): x与y是兄弟, “王大明与王小明是兄弟”: G(a,b)2022-5-13集合论与图论第2讲52个体变项(varible) 表示不确定的泛指对象 用小写英文字母x,y,z,来表示 例如： F(x): x是人。G(x): x是数。 “存

17、在着人”: xF(x) “仅有一人”: !xF(x) “万物皆数”: xG(x) 2022-5-13集合论与图论第2讲53合式公式（举例） x(F(x)y(G(y)H(x,y) F(f(a,a),b) 约定：省略多余括号 最外层 优先级递减： , ; ; ,; ,2022-5-13集合论与图论第2讲54命题符号化 个体域(scope): 个体词的取值范围, 缺省(default)采用全总个体域. 全总个体域: 世界上的万事万物 特性谓词: 表示所关注的对象的性质 两种模式: x(M(x)G(x) x(M(x)G(x) 其中M(x)是特性谓词。2022-5-13集合论与图论第2讲55命题符号化(

18、举例) 例: “有些人是要死的”. 解1: 采用全总个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: x(F(x)G(x) 解2: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: xG(x)2022-5-13集合论与图论第2讲56命题符号化(举例、续) 例: “凡人都是要死的”. 解1: 采用全总个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: x(F(x)G(x) 解2: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: xG(x)2022-5-13集合论与图论第2讲57命题符号化(

19、举例、续) 例: “存在最小的自然数”。 解1: 设: F(x): x是自然数; G(x,y): xy; 原命题符号化成: x(F(x)y(F(y)G(x,y) 解2: 采用全体自然数作为个体域. 设: G(x,y): xy; 原命题符号化成: xyG(x,y) 注意量词顺序: yxG(x,y): “没有最小的自然数”.2022-5-13集合论与图论第2讲58命题符号化(举例、续) 例: “不存在最大的自然数”。 解: 设: F(x): x是自然数; G(x,y): xy 原公式解释成: “3-35”。2022-5-13集合论与图论第2讲70一阶逻辑永真式(tautology) 永真式:在各种

20、解释下取值均为真(逻辑有效式) 命题逻辑永真式: 在各种赋值下取值均为真(重言式) 永假式:在各种解释下取值均为假(矛盾式) 命题逻辑永假式: 在各种赋值下取值均为真(矛盾式) 可满足式：非永假式一阶逻辑等值式(定义) 等值： AB 读作：A等值于B 含义：A与B在各种解释下取值均相等 AB 当且仅当 AB是永真式 例如： xF(x)xF(x)F F2022-5-13集合论与图论第2讲712022-5-13集合论与图论第2讲72一阶逻辑等值式(来源) 命题逻辑等值式的代换实例 与量词有关的 有限个体域量词消去 量词否定 量词辖域收缩与扩张 量词分配 与变项命名有关的 换名规则 代替规则2022

21、-5-13集合论与图论第2讲73代换实例 在命题逻辑等值式中, 代入一阶逻辑公式所得到的式子, 称为原来公式的代换实例. 例1：AA, 令A=xF(x), 得到xF(x)xF(x) 例2：ABAB, 令A=F(x), B=G(y), 得到F(x)G(y)F(x)G(y)2022-5-13集合论与图论第2讲74有限个体域上消去量词 设个体域为有限集D=a1, a2, an, 则xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an) 例: 个体域D=a,b,c, 则 xyF(x,y) x (F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c) (F

22、(b,a)F(b,b)F(b,c) (F(c,a)F(c,b)F(c,c)2022-5-13集合论与图论第2讲75量词否定等值式 xA(x)xA(x) xA(x)xA(x)量词否定等值式(举例) N n ( nN |an-a|N |an-a|N |an-a|N |an-a|N |an-a|N |an-a|N |an-a|N |an-a| )2022-5-13集合论与图论第2讲772022-5-13集合论与图论第2讲78量词辖域收缩与扩张() x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) BxA(x) 说明: B中不含x的出现 例

23、1: x(F(x)G(y) xF(x)G(y) 例2: xy(F(x)G(y) x(F(x)yG(y) xF(x)yG(y)2022-5-13集合论与图论第2讲79量词辖域收缩与扩张(、续) x(A(x)B) xA(x)B 证明: x(A(x)B) x(A(x)B) xA(x)B xA(x)B xA(x)B x(BA(x) BxA(x) 证明: x(BA(x) x(BA(x) BxA(x) BxA(x) BxA(x)2022-5-13集合论与图论第2讲80量词辖域收缩与扩张() x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) Bx

24、A(x) 说明: B中不含x的出现 例1: x(F(x)G(y) xF(x)G(y) 例2: xy(F(x)G(y) x(F(x)yG(y) xF(x)yG(y)2022-5-13集合论与图论第2讲81量词辖域收缩与扩张(、续) x(A(x)B) xA(x)B 证明: x(A(x)B) x(A(x)B) xA(x)B xA(x)B xA(x)B x(BA(x) BxA(x) 证明: x(BA(x) x(BA(x) BxA(x) BxA(x) BxA(x)2022-5-13集合论与图论第2讲82量词分配 x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x)量词分

25、配(反例)x(A(x)B(x) xA(x)xB(x)x(A(x)B(x) xA(x)xB(x) 个体域为全体自然数; A(x): x是偶数 B(x): x是奇数; 左1, 右0 x(A(x)B(x) xA(x)xB(x)x(A(x)B(x) xA(x)xB(x) 个体域为全体自然数; A(x): x是偶数 B(x): x是奇数; 左0, 右1 2022-5-13集合论与图论第2讲83一阶逻辑推理定律(定义) 推出： AB 读作：A推出B 含义：A为真时, B也为真 AB 当且仅当 AB是永真式 例如： xF(x) xF(x)F2022-5-13集合论与图论第2讲842022-5-13集合论与图

26、论第2讲85一阶逻辑推理定律(来源) 命题逻辑推理定律的代换实例 基本等值式生成的推理定律 其他的一阶逻辑推理定律 xA(x)xB(x) x(A(x)B(x) x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x) 2022-5-13集合论与图论第2讲86一阶逻辑推理定律(举例) 命题逻辑推理定律的代换实例 例如: 假言推理规则: (AB )AB 代入 A=F(a), B=G(a), 得到(F(a)G(a)F(a)G(a)2022-5-13集合论与图论第2讲87一阶逻辑推理定律(举例、续) 基本等值式生成的推理定律 即

27、由 AB 可得 AB 和 BA 例如: 量词分配等值式: x(A(x)B(x) xA(x)xB(x) 可得 x(A(x)B(x) xA(x)xB(x) xA(x)xB(x) x(A(x)B(x)2022-5-13集合论与图论第2讲88总结 一阶逻辑等值式（6组） 有限个体域量词消去； 量词否定； 量词辖域收缩与扩张； 量词分配； 换名规则； 代替规则 一阶逻辑推理定律2022-5-13集合论与图论第2讲89习题 1. 设个体域D=a,b,c, 消去下列各式的量词： (1) xy(F(x)G(x) (2) x(F(x,y)yG(y) 2. 证明等值式: xF(x)xG(x)xy(F(x)G(y)

28、2022-5-13集合论与图论第3讲90第3讲 集合的概念与运算 1. 集合的概念 2. 集合之间的关系 3. 集合的运算 4. 文氏图、容斥原理集合论(set theory) 十九世纪数学最伟大成就之一 集合论体系 朴素(naive)集合论 公理(axiomatic)集合论 创始人康托(Cantor)Georg Ferdinand Philip Cantor 1845 1918德国数学家, 集合论创始人. 2022-5-13集合论与图论第3讲912022-5-13集合论与图论第3讲92 什么是集合(set) 集合：不能精确定义。一些对象的整体就构成集合，这些对象称为元素(element)或成

29、员(member) 用大写英文字母A,B,C,表示集合 用小写英文字母a,b,c,表示元素 aA：表示a是A的元素，读作“a属于A” aA：表示a不是A的元素，读作“a不属于A”2022-5-13集合论与图论第3讲93集合的表示 列举法 描述法 特征函数法2022-5-13集合论与图论第3讲94列举法(roster) 列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来，例如A=a,b,c,d,x,y,z B=0,1,2,3,4,5,6,7,8,9 集合中的元素不规定顺序C=2,1=1,2 集合中的元素各不相同(多重集除外)C=2,1,1,2=2,12022-5-13集合论与图论第3讲

30、95多重集(multiple set) 多重集: 允许元素多次重复出现的集合 元素的重复度: 元素的出现次数(0). 例如: 设A=a,a,b,b,c是多重集 元素a,b的重复度是2 元素c的重复度是1 元素d的重复度是02022-5-13集合论与图论第3讲96描述法(defining predicate) 用谓词P(x)表示x具有性质P ，用x|P(x)表示具有性质 P 的集合，例如 P1 (x): x是英文字母A=x|P1 (x)=x| x是英文字母=a,b,c,d,x,y,z P2 (x): x是十进制数字B=x|P2(x)= x|x是十进制数字 =0,1,2,3,4,5,6,7,8,9

31、2022-5-13集合论与图论第3讲97描述法（续） 两种表示法可以互相转化，例如E=2,4,6,8,=x|x0且x是偶数 =x|x=2(k+1)，k为非负整数=2(k+1) | k为非负整数 有些书在描述法中用:代替|, 例如2(k+1): k为非负整数特征函数法(characteristic function) 集合A的特征函数是A (x): 1，若xA A (x) = 0，若xA 对多重集, A (x)=x在A中的重复度2022-5-13集合论与图论第3讲982022-5-13集合论与图论第3讲99常用的数集合 N：自然数(natural numbers)集合N=0,1,2,3, Z：整

32、数(integers)集合Z=0,1,2,=,-2,-1,0,1,2, Q：有理数(rational numbers)集合 R：实数(real numbers)集合 C：复数(complex numbers)集合2022-5-13集合论与图论第3讲100集合之间的关系 子集、相等、真子集 空集、全集 幂集、n元集、有限集 集族2022-5-13集合论与图论第3讲101子集(subset) B包含于A, A包含B: BA x(xBxA) B不是A的子集: BA x(xBxA) x(xBxA)x(xBxA) x(xBxA)x(xBxA)2022-5-13集合论与图论第3讲102相等(equal)

33、相等: A=B AB BA x(xAxB) A=B ABBA (=定义)x(xAxB)x(xBxA) (定义)x(xAxB)(xBxA)(量词分配)x(xAxB) (等值式)2022-5-13集合论与图论第3讲103包含()的性质 AA 证明: AAx(xAxA) 1 若AB,且AB,则 BA 证明: AB (A=B) (ABBA) (定义) (AB) (BA) (德摩根律) AB (已知) BA (即BA) (析取三段论) #2022-5-13集合论与图论第3讲104包含()的性质(续) 若AB,且BC, 则AC证明: AB x(xAxB) x, xA xB (AB) xC (BC) x(x

34、AxC), 即AC. #2022-5-13集合论与图论第3讲105真子集(proper subset) 真子集: B真包含A:AB AB AB AB (AB AB) (定义) (AB) (A=B) (德摩根律) x(xAxB) (A=B) (定义)2022-5-13集合论与图论第3讲106真包含()的性质 AA 证明: A A AA AA 10 0. # 若AB,则 BA 证明: (反证) 设BA, 则 AB AB AB AB (化简) BA BA BA BA 所以 AB BA A=B (=定义)但是 AB AB AB AB (化简) 矛盾! #2022-5-13集合论与图论第3讲107真包含

35、()的性质(续) 若AB,且BC, 则AC证明: AB AB AB AB (化简), 同理 BC BC, 所以AC. 假设A=C, 则BCBA, 又AB, 故A=B, 此与AB矛盾, 所以AC. 所以, AC. #2022-5-13集合论与图论第3讲108空集(empty set) 空集:没有任何元素的集合是空集,记作 例如, xR|x2 +1=0 定理1: 对任意集合A, A 证明: Ax(xxA) x(0 xA)1. # 推论: 空集是唯一的. 证明: 设1与2都是空集, 则 12 21 1=2 . #2022-5-13集合论与图论第3讲109全集 全集: 如果限定所讨论的集合都是某个集合

36、的子集,则称这个集合是全集,记作E 全集是相对的, 视情况而定, 因此不唯一.例如, 讨论(a,b)区间里的实数性质时, 可以选E=(a,b), E=a,b), E=(a,b, E=a,b, E=(a,+),E=(-,+)等2022-5-13集合论与图论第3讲110幂集(power set) 幂集: A的全体子集组成的集合,称为A的幂集,记作P(A)P(A)=x|xA 注意: xP(A) xA 例子: A=a,b, P(A)=,a,b,a,b. #2022-5-13集合论与图论第3讲111n元集(n-set) n元集: 含有n个元素的集合称为n元集 0元集: 1元集(或单元集),如a, b,

37、, , |A|: 表示集合A中的元素个数, A是n元集 |A|=n 有限集 (fimite set): |A|是有限数, |A|0, Aa=0,a), Aa|aR+ 的指标集是R+0a2022-5-13集合论与图论第3讲1142022-5-13集合论与图论第3讲115集合之间的运算 并集、交集 相对补集、对称差、绝对补 广义并集、广义交集并集(union)并集: AB = x | (xA) (xB) xAB (xA) (xB)初级并: 2022-5-13集合论与图论第3讲116并集(举例) 例1: 设An=xR|n-1xn,n=1,2,10,则 例2: 设An=xR|0 x1/n,n=1,2,

38、则2022-5-13集合论与图论第3讲117交集(intersection)交集: AB = x | (xA) (xB) xAB (xA) (xB)初级交: 2022-5-13集合论与图论第3讲118交集(举例) 例1: 设An=xR|n-1xn,n=1,2,10,则 例2: 设An=xR|0 x1/n,n=1,2,则2022-5-13集合论与图论第3讲119不相交(disjoint) 不相交: AB= 互不相交: 设A1,A2,是可数多个集合, 若对于任意的ij, 都有AiAj=, 则说它们互不相交 例: 设 An=xR|n-1xn, n=1,2,10, 则 A1,A2,是不相交的2022-

39、5-13集合论与图论第3讲120相对补集(set difference) 相对补集: 属于A而不属于B的全体元素,称为B对A的相对补集, 记作A-BA-B = x | (xA) (xB) A-BAB2022-5-13集合论与图论第3讲121对称差(symmetric difference) 对称差: 属于A而不属于B, 或属于B而不属于A的全体元素, 称为A与B的对称差, 记作ABAB=x|(xAxB)(xAxB) AB=(A-B)(B-A)=(AB)-(AB)ABAB2022-5-13集合论与图论第3讲122绝对补(complement) 绝对补: A=E-A, E是全集, AEA=x|(x

40、ExA)A=xE|xA)AA2022-5-13集合论与图论第3讲123相对补、对称差、补(举例) 例: 设A=xR|0 x2, B=xR|1x3, 则 A-B= xR|0 x1=0,1)B-A= xR|2x3=2,3)AB=xR|(0 x1)(2x3)=0,1)2,3)2022-5-13集合论与图论第3讲1242022-5-13集合论与图论第3讲125广义并集(big union) 广义并: 设A是集族, A中所有集合的元素的全体, 称为A的广义并, 记作A.A = x | z(xzzA 当A是以S为指标集的集族时A = A|S= A S 例: 设 A=a,b,c,d,d,e,f, 则 A=

41、a,b,c,d,e,f2022-5-13集合论与图论第3讲126广义交集(big intersection) 广义交: 设A是集族, A中所有集合的公共元素的全体, 称为A的广义交, 记作A.A = x | z(zAxz) 当A是以S为指标集的集族时A = A|S= A S 例: 设 A=1,2,3,1,a,b,1,6,7, 则 A= 12022-5-13集合论与图论第3讲127广义交、广义并(举例) 设 A1=a,b,c,d, A2=a,b, A3=a, A4=, A5=a(a), A6=, 则A1= abc,d, A1= abc,d,A2=a,b, A2=a,b, A3=a, A3=aA4

42、=, A4=,A5= a, A5= aA6=, A6=E文氏图(Venn diagram) 文氏图: 平面上的n个圆(或椭圆),使得任何可能的相交部分, 都是非空的和连通的 John Venn, 18341923 例: 2022-5-13集合论与图论第3讲128文氏图(应用) 文氏图可表示集合运算(结果用阴影表示)ABABA-BABAAAAAAABBBBBAB=2022-5-13集合论与图论第3讲129容斥原理(principle of inclusion/exclusion) 容斥原理(或包含排斥原理)2022-5-13集合论与图论第3讲130容斥原理(证明) n=2时的情况:|AB|=|A

43、|+|B|-|AB| 归纳证明: 以n=3为例:|AB C| = |(AB)C|= |AB|+|C|-|(AB)C| = |A|+|B|-|AB|+|C|-|(AC)(BC)| = |A|+|B|-|AB|+|C| -(|AC|+|BC|-|(AC)(BC)|) = |A|+|B|+|C|-|AB|-|AC|-|BC| +|ABC|ABBCA2022-5-13集合论与图论第3讲1312022-5-13集合论与图论第3讲132容斥原理(举例) 例1: 在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少? 解: 设 E=xN|1x10000, |E|=10000 A=xE|x

44、=k2kZ, |A|=100 B=xE|x=k3kZ, |B|=21 则 |(AB)|=|E|-|AB| =|E|-(|A|+|B|-|AB|) =10000-100-21+4=9883 注意 AB= xE|x=k6kZ, |AB|=4. #2022-5-13集合论与图论第3讲133容斥原理(举例、续) 例2: 在24名科技人员中,会说英,日,德,法语的人数分别为13, 5, 10, 和9, 其中同时会说英语,德语, 或同时会说英语,法语, 或同时会说德语,法语两种语言的人数均为4.会说日语的人既不会说法语也不会说德语. 试求只会说一种语言的人数各为多少?又同时会说英,德,法语的人数有多少?

45、解: 设E=x|x是24名科技人员之一, |E|=24 A=xE|x会说英语, B=xE|x会说日语, C=xE|x会说德语 D=xE|x会说法语,容斥原理(举例、续)解(续): 设所求人数分别为x1,x2,x3,x4,x(如图), A=xE|x会说英语, |A|=13 B=xE|x会说日语, |B|=5 C=xE|x会说德语, |C|=10 D=xE|x会说法语, |D|=9 首先, x2=|B|-|AB|=5-2=3, 其次,对A,C,D用容斥原理, 注意|E|=24: 24-3=21=13+10+9-4-4-4+x=20+x, 得x=1, 最后, x1=|A|-|AB|-3-3-1=13

46、-2-7=4, 同理 x3=10-3-3-1=3, x4=9-3-3-1=2. #DCBAXX1X2X3X44-X4-X4-X22022-5-13集合论与图论第3讲1342022-5-13集合论与图论第3讲135总结 集合概念: , , E, , , 集合运算: , , -, , , P( ) 文氏图 容斥原理2022-5-13集合论与图论第3讲136习题(#1) p25, 习题一, 3, 7, 10, 16 2022-5-13集合论与图论第4讲137第4讲 集合恒等式内容提要 1. 集合恒等式与对偶原理 2. 集合恒等式的证明 3. 集合列的极限 4. 集合论悖论与集合论公理2022-5-1

47、3集合论与图论第4讲138集合恒等式(关于与) 等幂律(idempotent laws)AA=AAA=A 交换律(commutative laws)AB=BAAB=BA2022-5-13集合论与图论第4讲139集合恒等式(关于与、续) 结合律(associative laws)(AB)C=A(BC) (AB)C=A(BC) 分配律(distributive laws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)2022-5-13集合论与图论第4讲140集合恒等式(关于与 、续) 吸收律(absorption laws)A(AB)=AA(AB)=A2022-5-13集合论与图论第4讲

48、141集合恒等式(关于) 双重否定律(double complement law)A=A 德摩根律(DeMorgans laws)(AB)=AB(AB)=AB2022-5-13集合论与图论第4讲142集合恒等式(关于与E) 零律(dominance laws)AE=EA= 同一律(identity laws)A=AAE=A2022-5-13集合论与图论第4讲143集合恒等式(关于,E) 排中律(excluded middle)AA = E 矛盾律(contradiction)AA = 全补律 = EE = 2022-5-13集合论与图论第4讲144集合恒等式(关于-) 补交转换律(differ

49、ence as intersection)A-B=AB集合恒等式(推广到集族)分配律德摩根律2022-5-13集合论与图论第4讲1452022-5-13集合论与图论第4讲146对偶(dual)原理 对偶式(dual): 一个集合关系式, 如果只含有, , E,=, , 那么, 同时把与互换, 把与E互换, 把与互换, 得到的式子称为原式的对偶式. 对偶原理: 对偶式同真假. 或者说, 集合恒等式的对偶式还是恒等式.2022-5-13集合论与图论第4讲147对偶原理(举例) 分配律A (B C) = (A B ) (A C )A (B C) = (A B ) (A C ) 排中律A A=E 矛盾

50、律A A= 2022-5-13集合论与图论第4讲148对偶原理(举例、续) 零律A E =EA = 同一律A =AA E=A2022-5-13集合论与图论第4讲149对偶原理(举例、续) A B AA B A AE A2022-5-13集合论与图论第4讲150集合恒等式证明(方法) 逻辑演算法: 利用逻辑等值式和推理规则 集合演算法: 利用集合恒等式和已知结论2022-5-13集合论与图论第4讲151 题目: A=B. 证明: x, xA (?) xB A=B. # 题目: AB. 证明: x, xA (?) xB AB. #逻辑演算法(格式)2022-5-13集合论与图论第4讲152分配律(