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

上传人：小飞机

文档编号：1579687

上传时间：2022-12-08

格式：PPT

页数：375

大小：7.39MB

《集合论与图论(全套ppt课件).ppt》由会员分享，可在线阅读，更多相关《集合论与图论(全套ppt课件).ppt（375页珍藏版）》请在三一办公上搜索。

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

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

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

4、t)：给变元指定0、1值n个变元，共有2n种不同的赋值,2022/12/8,集合论与图论第1讲,13,真值表(续),2022/12/8,集合论与图论第1讲,14,永真式(tautology),永真式:在各种赋值下取值均为真(重言式)永假式:在各种赋值下取值均为假(矛盾式)可满足式：非永假式,2022/12/8,集合论与图论第1讲,15,2022/12/8,集合论与图论第1讲,16,逻辑等值式(identities),等值： AB 读作：A等值于B含义：A与B在各种赋值下取值均相等AB 当且仅当 AB是永真式例如： (pq)r pqr,2022/12/8,集合论与图论第1讲,17,常用逻辑等值式

5、(关于与),幂等律(idempotent laws)AAAAAA交换律(commutative laws)ABBAABBA,2022/12/8,集合论与图论第1讲,18,常用逻辑等值式(关于与),结合律(associative laws)(AB)CA(BC) (AB)CA(BC) 分配律(distributive laws)A(BC)(AB )(AC )A(BC)(AB )(AC ),2022/12/8,集合论与图论第1讲,19,常用逻辑等值式(关于与),吸收律(absorption laws)A(AB)AA(AB)A,2022/12/8,集合论与图论第1讲,20,常用逻辑等值式(关于),双重

6、否定律(double negation law)AA德摩根律(DeMorgans laws)(AB)AB(AB)AB,2022/12/8,集合论与图论第1讲,21,常用逻辑等值式(关于0,1),零律(dominance laws)A11A00同一律(identity laws)A0AA1A,2022/12/8,集合论与图论第1讲,22,常用逻辑等值式(关于0,1),排中律(excluded middle)AA1矛盾律(contradiction)AA0,2022/12/8,集合论与图论第1讲,23,常用逻辑等值式(关于),蕴涵等值式(conditional as disjunction)ABA

7、B假言易位(contrapositive law)ABBA归谬论(AB )( AB )A,2022/12/8,集合论与图论第1讲,24,常用逻辑等值式(关于),等价等值式(biconditional as implication)AB(AB)(BA)等价否定等值式ABAB,2022/12/8,集合论与图论第1讲,25,等值式模式,A，B，C代表任意的公式上述等值式称为等值式模式每个等值式模式都给出了无穷多个同类型的具体的等值式。,2022/12/8,集合论与图论第1讲,26,等值式模式(举例),蕴涵等值式模式ABAB取A=p，B=q时，得到pqpq取A=pqr，B=pq时，得到(pqr)(pq

8、)(pqr)(pq),2022/12/8,集合论与图论第1讲,27,对偶原理,一个逻辑等值式，如果只含有，，，0，1那么，同时把与互换把 0 与 1互换得到的还是等值式,2022/12/8,集合论与图论第1讲,28,对偶原理(举例),分配律A(BC)(AB )(AC )A(BC)(AB )(AC )排中律(excluded middle)AA1矛盾律(contradiction)AA0,2022/12/8,集合论与图论第1讲,29,对偶原理(举例、续),零律(dominance laws)A11A00同一律(identity laws)A0AA1A,2022/12/8,集合论与图论第1讲

9、,30,等值演算（举例）,例：(pq)rpqr 解： (pq)r (pq)r （蕴涵等值式） (pq)r （德摩根律） pqr （结合律）,2022/12/8,集合论与图论第1讲,31,推理定律(deduction laws),推出： AB 读作：A推出B含义：当A为真时，B也为真AB 当且仅当 A B是永真式例如： (pq ) p q,推理定律（举例）,(pq )p q(pq )p q 是永真式,2022/12/8,集合论与图论第1讲,32,2022/12/8,集合论与图论第1讲,33,常见推理定律,附加律A(AB)化简律(AB)A,2022/12/8,集合论与图论第1讲,34,常见推理定律

10、（续）,假言推理(AB ) AB拒取式(AB ) B A析取三段论(AB )B A,2022/12/8,集合论与图论第1讲,35,常见推理定律（续）,假言三段论(AB)(BC)(AC)等价三段论(AB)(BC)(AC),2022/12/8,集合论与图论第1讲,36,常见推理定律（续）,构造性两难(AB)(CD)(AC)(BD)构造性两难(特殊形式)(AB)(AB)(AA)B破坏性两难(AB)(CD)(BD)(AC),2022/12/8,集合论与图论第1讲,37,推理规则,前提引入规则：在证明的任何步骤上都可以引入前提结论引入规则：在证明的任何步骤上所得到的结论都可以做为后继证明的前提置换规则：

11、在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中又一个公式,2022/12/8,集合论与图论第1讲,38,推理规则（续）,附加规则：A(AB) A AB化简规则：(AB)A,2022/12/8,集合论与图论第1讲,39,推理规则（续）,假言推理规则： (AB )ABAB A B拒取式规则：(AB )B A,2022/12/8,集合论与图论第1讲,40,推理规则（续）,假言三段论规则：(AB)(BC)(AC) AB BC A C析取三段论规则：(AB )B A,2022/12/8,集合论与图论第1讲,41,推理规则（续）,构造性两难推理规则： (AB)(CD)(A

12、C)(BD)破坏性两难推理规则： (AB)(CD)(BD)(AC),2022/12/8,集合论与图论第1讲,42,推理规则（续）,合取引入规则：(A)(B)(AB)AB AB,2022/12/8,集合论与图论第1讲,43,证明(举例),证明： (pq)rq(pr) (pq) r (pq)r (蕴涵等值式) (pq)r (德摩根律) q(pr) (交换律、结合律) q (pr) (蕴涵等值式) q(pr) (蕴涵等值式),2022/12/8,集合论与图论第1讲,44,总结,等值式（16组、24条）幂等律、交换律、结合律、分配律、吸收律；双重否定律、德摩根律；零律、同一律、排中律、矛盾律；蕴涵等值

13、式、等价等值式、假言易位、等价否定等值式归谬论推理定律（9条）附加、化简假言推理、拒取式、析取三段论、假言三段论、等价三段论、构造性两难（特殊形式）、破坏性两难,2022/12/8,集合论与图论第1讲,45,习题,证明下面的等值式： (1) (pq )(pr) p(qr) (2) (pq)(pq) (pq)(pq)证明本次课讲的基本等值式和推理定律,2022/12/8,集合论与图论第2讲,46,第2讲一阶逻辑基础,内容提要 1. 量词、谓词、个体词、命题符号化 2. 合式公式、解释、永真式 3. 一阶逻辑等值式 4. 一阶逻辑推理规则,2022/12/8,集合论与图论第2讲,47,一阶逻辑的

14、字母表,个体常项: 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/12/8,集合论与图论第2讲,48,谓词(predicate),谓词：表示性质、关系等；相当于句子中的谓语。用大写英文字母F,G,H,后跟括号与变元来表示。例如：F(x): x是人。G(x,y): x与y是兄弟。 n元谓词：含有n个变元。例如： F(x)是一元谓词， G(x,y)

15、是二元谓词,2022/12/8,集合论与图论第2讲,49,量词(quantifier),全称(universal)量词: “所有的”, “全部的”,存在(existential)量词: “有一些的”, “某些的”,唯一(unique)存在量词: ! “恰好存在一个”,2022/12/8,集合论与图论第2讲,50,量词(举例),设：F(x)：x是自然数。G(x)：x是偶数。 H(x) ： x是奇数。 I(x,y)：x=y。“有些自然数是偶数”。 x(F(x)G(x)“既有奇数又有偶数” 。xH(x)yG(y)存在既奇又偶的数” 。x(H(x)G(x)“存在唯一的自然数0”。 !x(F(x)I(x

16、,0),2022/12/8,集合论与图论第2讲,51,个体常项(constant),表示具体的特定对象用小写英文字母a,b,c,来表示例如： a:王大明，b:王小明， G(x,y): x与y是兄弟, “王大明与王小明是兄弟”: G(a,b),2022/12/8,集合论与图论第2讲,52,个体变项(varible),表示不确定的泛指对象用小写英文字母x,y,z,来表示例如： F(x): x是人。G(x): x是数。 “存在着人”: xF(x) “仅有一人”: !xF(x) “万物皆数”: xG(x),2022/12/8,集合论与图论第2讲,53,合式公式（举例）,x(F(x)y(G(y)H(x,

17、y) F(f(a,a),b)约定：省略多余括号最外层优先级递减： , ; ; ,; ,2022/12/8,集合论与图论第2讲,54,命题符号化,个体域(scope): 个体词的取值范围, 缺省(default)采用全总个体域. 全总个体域: 世界上的万事万物特性谓词: 表示所关注的对象的性质两种模式: x(M(x)G(x) x(M(x)G(x) 其中M(x)是特性谓词。,2022/12/8,集合论与图论第2讲,55,命题符号化(举例),例: “有些人是要死的”.解1: 采用全总个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: x(F(x)G(x)解2: 采用全体人

18、作为个体域. 设: G(x): x是要死的. 原命题符号化成: xG(x),2022/12/8,集合论与图论第2讲,56,命题符号化(举例、续),例: “凡人都是要死的”.解1: 采用全总个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: x(F(x)G(x)解2: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: xG(x),2022/12/8,集合论与图论第2讲,57,命题符号化(举例、续),例: “存在最小的自然数”。解1: 设: F(x): x是自然数; G(x,y): xy; 原命题符号化成: x(F(x)y(F(y)G(x,y)

19、解2: 采用全体自然数作为个体域. 设: G(x,y): xy; 原命题符号化成: xyG(x,y)注意量词顺序: yxG(x,y): “没有最小的自然数”.,2022/12/8,集合论与图论第2讲,58,命题符号化(举例、续),例: “不存在最大的自然数”。解: 设: F(x): x是自然数; G(x,y): xy; 原命题符号化成: x(F(x)y(F(y)G(y,x) 或: x(F(x)y(F(y)G(x,y),2022/12/8,集合论与图论第2讲,59,命题符号化(举例、续),例: “火车比汽车快”。解: 设: F(x): x是火车; G(x): x是汽车; H(x,y): x

20、比y快原命题符号化成: x(F(x)y(G(y)H(x,y) 或: xy(F(x)G(y)H(x,y),2022/12/8,集合论与图论第2讲,60,命题符号化(举例、续),例: “有的汽车比火车快”。解: 设: F(x): x是汽车; G(x): x是火车; H(x,y): x比y快原命题符号化成: x(F(x)y(G(y)H(x,y) 或: xy(F(x)G(y)H(x,y),2022/12/8,集合论与图论第2讲,61,命题符号化(举例、续),例: “有些病人相信所有的医生”。解: 设: F(x): x是病人; G(x): x是医生; H(x,y): x相信y 原命题符号化成:

21、x(F(x)y(G(y)H(x,y),2022/12/8,集合论与图论第2讲,62,命题符号化(举例、续),例: “存在唯一的对象满足性质P”。解: 设: P(x): x满足性质P 原命题符号化成: !xP(x) 或: x( P(x) y( P(y)x=y ) ),2022/12/8,集合论与图论第2讲,63,合式公式中的变项,量词辖域: 在xA, xA中, A是量词的辖域. 例如: x(F(x)y(G(y)H(x,y)指导变项: 紧跟在量词后面的个体变项.例如: x(F(x)y(G(y)H(x,y)约束出现: 在辖域中与指导变项同名的变项. 例如: x(F(x)y(G(y)H(x,y)自由

22、出现: 既非指导变项又非约束出现. 例如: y(G(y)H(x,y),2022/12/8,集合论与图论第2讲,64,合式公式中的变项(举例),H(x,y)xF(x)y(G(y)H(x,y)x 与 y 是指导变项 x与y是约束出现 x与 y是自由出现,2022/12/8,集合论与图论第2讲,65,换名(rename)规则,把某个指导变项和其量词辖域中所有同名的约束出现, 都换成某个新的个体变项符号.例如: x(A(x)B(x) y(A(y)B(y) xA(x)xB(x) yA(y)zB(z) H(x,y)xF(x)y(G(y)H(x,y) H(x,y)zF(z)u(G(u)H(x,u),2022

23、/12/8,集合论与图论第2讲,66,代替(substitute)规则,把某个自由变项的所有出现, 都换成某个新的个体变项符号.例如: A(x)B(x) A(y)B(y) xA(x)B(x) xA(x)B(y) H(x,y)xF(x)y(G(y)H(x,y) H(s,t)xF(x)y(G(y)H(s,y),闭式(closed form),闭式: 无自由出现的变项一般来说, 闭式表示的是命题, 例如 F(a) xF(x)F(x)y(G(y)H(x,y)后两个不是闭式,2022/12/8,集合论与图论第2讲,67,2022/12/8,集合论与图论第2讲,68,解释(interpret),对一个合式

24、公式的解释包括给出个体域谓词函数个体常项的具体含义,2022/12/8,集合论与图论第2讲,69,解释(举例),F(f(a,a),b)解释1：个体域是全体自然数; a: 2; b: 4; f(x,y)=x+y; F(x,y): x=y 原公式解释成: “2+2=4”。解释2：个体域是全体实数; a: 3; b: 5; f(x,y)=x-y; F(x,y): xy 原公式解释成: “3-35”。,2022/12/8,集合论与图论第2讲,70,一阶逻辑永真式(tautology),永真式:在各种解释下取值均为真(逻辑有效式)命题逻辑永真式: 在各种赋值下取值均为真(重言式)永假式:在各种解释下

25、取值均为假(矛盾式)命题逻辑永假式: 在各种赋值下取值均为真(矛盾式)可满足式：非永假式,一阶逻辑等值式(定义),等值： AB 读作：A等值于B含义：A与B在各种解释下取值均相等AB 当且仅当 AB是永真式例如： xF(x)xF(x),F, F,2022/12/8,集合论与图论第2讲,71,2022/12/8,集合论与图论第2讲,72,一阶逻辑等值式(来源),命题逻辑等值式的代换实例与量词有关的有限个体域量词消去量词否定量词辖域收缩与扩张量词分配与变项命名有关的换名规则代替规则,2022/12/8,集合论与图论第2讲,73,代换实例,在命题逻辑等值式中, 代入一阶逻辑公式所得到的式子, 称为原

26、来公式的代换实例. 例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/12/8,集合论与图论第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(b,a)F(b,b)F(b,c) (F(c,a)F(c,b)F(c,c),2022/12/8,集

27、合论与图论第2讲,75,量词否定等值式,xA(x)xA(x) xA(x)xA(x),量词否定等值式(举例), N n ( nN |an-a| ) a1,a2,a3,aN ,aN+1,aN+2 ,an , ?,a,2022/12/8,集合论与图论第2讲,76,量词否定等值式(举例、续), N n ( nN |an-a|N |an-a|N |an-a|N |an-a|N |an-a|N |an-a|N |an-a| ),2022/12/8,集合论与图论第2讲,77,2022/12/8,集合论与图论第2讲,78,量词辖域收缩与扩张(),x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(

28、A(x)B) xA(x)Bx(BA(x) BxA(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/12/8,集合论与图论第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/12/8,集合论与图论第2讲,80,量词辖域收缩与扩张(),x(A(x)B) xA

29、(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(BA(x) BxA(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/12/8,集合论与图论第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/12/8,集合论与图论第2讲,82,量词

30、分配,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)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/12/8,集合论与图论第2讲,83,一阶逻辑推理定律(定义),推出： AB 读作：A推出B含义：A为真时, B也为真AB 当且仅当 AB是永真式

31、例如： xF(x) xF(x),F,2022/12/8,集合论与图论第2讲,84,2022/12/8,集合论与图论第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/12/8,集合论与图论第2讲,86,一阶逻辑推理定律(举例),命题逻辑推理定律的代换实例例如: 假言推理规则: (AB )AB 代入 A=F(a), B=G(a), 得到(F(a)G

32、(a)F(a)G(a),2022/12/8,集合论与图论第2讲,87,一阶逻辑推理定律(举例、续),基本等值式生成的推理定律即由 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/12/8,集合论与图论第2讲,88,总结,一阶逻辑等值式（6组）有限个体域量词消去；量词否定；量词辖域收缩与扩张；量词分配；换名规则；代替规则一阶逻辑推理定律,2022/12/8,集合论与图论第2讲,89,习题,1. 设个体域D=a,b,c, 消去下列各式的量词：

33、(1) xy(F(x)G(x) (2) x(F(x,y)yG(y)2. 证明等值式: xF(x)xG(x)xy(F(x)G(y),2022/12/8,集合论与图论第3讲,90,第3讲集合的概念与运算,1. 集合的概念 2. 集合之间的关系 3. 集合的运算 4. 文氏图、容斥原理,集合论(set theory),十九世纪数学最伟大成就之一集合论体系朴素(naive)集合论公理(axiomatic)集合论创始人康托(Cantor),Georg Ferdinand Philip Cantor 1845 1918德国数学家, 集合论创始人.,2022/12/8,集合论与图论第3讲,91,2022/

34、12/8,集合论与图论第3讲,92,什么是集合(set),集合：不能精确定义。一些对象的整体就构成集合，这些对象称为元素(element)或成员(member)用大写英文字母A,B,C,表示集合用小写英文字母a,b,c,表示元素aA：表示a是A的元素，读作“a属于A” aA：表示a不是A的元素，读作“a不属于A”,2022/12/8,集合论与图论第3讲,93,集合的表示,列举法描述法特征函数法,2022/12/8,集合论与图论第3讲,94,列举法(roster),列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来，例如A=a,b,c,d,x,y,z B=0,1,2,3,4,5,6,7

35、,8,9集合中的元素不规定顺序C=2,1=1,2集合中的元素各不相同(多重集除外)C=2,1,1,2=2,1,2022/12/8,集合论与图论第3讲,95,多重集(multiple set),多重集: 允许元素多次重复出现的集合元素的重复度: 元素的出现次数(0). 例如: 设A=a,a,b,b,c是多重集元素a,b的重复度是2 元素c的重复度是1 元素d的重复度是0,2022/12/8,集合论与图论第3讲,96,描述法(defining predicate),用谓词P(x)表示x具有性质P ，用x|P(x)表示具有性质 P 的集合，例如P1 (x): x是英文字母A=x|P1 (x)=x|

36、 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,2022/12/8,集合论与图论第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中的重复度,2

37、022/12/8,集合论与图论第3讲,98,2022/12/8,集合论与图论第3讲,99,常用的数集合,N：自然数(natural numbers)集合N=0,1,2,3,Z：整数(integers)集合Z=0,1,2,=,-2,-1,0,1,2,Q：有理数(rational numbers)集合R：实数(real numbers)集合C：复数(complex numbers)集合,2022/12/8,集合论与图论第3讲,100,集合之间的关系,子集、相等、真子集空集、全集幂集、n元集、有限集集族,2022/12/8,集合论与图论第3讲,101,子集(subset),B包含于A, A包含B:

38、 BA x(xBxA)B不是A的子集: BA x(xBxA)x(xBxA)x(xBxA) x(xBxA)x(xBxA),2022/12/8,集合论与图论第3讲,102,相等(equal),相等: A=B AB BA x(xAxB) A=B ABBA (=定义)x(xAxB)x(xBxA) (定义)x(xAxB)(xBxA)(量词分配)x(xAxB) (等值式),2022/12/8,集合论与图论第3讲,103,包含()的性质,AA 证明: AAx(xAxA) 1若AB,且AB,则 BA 证明: AB (A=B) (ABBA) (定义) (AB) (BA) (德摩根律) AB (已知) BA (即

39、BA) (析取三段论) #,2022/12/8,集合论与图论第3讲,104,包含()的性质(续),若AB,且BC, 则AC证明: AB x(xAxB) x, xA xB (AB) xC (BC) x(xAxC), 即AC. #,2022/12/8,集合论与图论第3讲,105,真子集(proper subset),真子集: B真包含A:AB AB AB AB (AB AB) (定义) (AB) (A=B) (德摩根律) x(xAxB) (A=B) (定义),2022/12/8,集合论与图论第3讲,106,真包含()的性质,AA 证明: A A AA AA 10 0. #若AB,则 BA 证明:

40、(反证) 设BA, 则 AB AB AB AB (化简) BA BA BA BA 所以 AB BA A=B (=定义)但是 AB AB AB AB (化简) 矛盾! #,2022/12/8,集合论与图论第3讲,107,真包含()的性质(续),若AB,且BC, 则AC证明: AB AB AB AB (化简), 同理 BC BC, 所以AC. 假设A=C, 则BCBA, 又AB, 故A=B, 此与AB矛盾, 所以AC. 所以, AC. #,2022/12/8,集合论与图论第3讲,108,空集(empty set),空集:没有任何元素的集合是空集,记作例如, xR|x2 +1=0定理1: 对任意集合

41、A, A 证明: Ax(xxA) x(0 xA)1. #推论: 空集是唯一的. 证明: 设1与2都是空集, 则 12 21 1=2 . #,2022/12/8,集合论与图论第3讲,109,全集,全集: 如果限定所讨论的集合都是某个集合的子集,则称这个集合是全集,记作E全集是相对的, 视情况而定, 因此不唯一.例如, 讨论(a,b)区间里的实数性质时, 可以选E=(a,b), E=a,b), E=(a,b, E=a,b, E=(a,+),E=(-,+)等,2022/12/8,集合论与图论第3讲,110,幂集(power set),幂集: A的全体子集组成的集合,称为A的幂集,记作P(A)P(A)

42、=x|xA注意: xP(A) xA例子: A=a,b, P(A)=,a,b,a,b. #,2022/12/8,集合论与图论第3讲,111,n元集(n-set),n元集: 含有n个元素的集合称为n元集0元集: 1元集(或单元集),如a, b, , ,|A|: 表示集合A中的元素个数, A是n元集 |A|=n有限集 (fimite set): |A|是有限数, |A|, 也叫有穷集,幂集(续),定理: |A|=n |P(A)|=2n. 证明: 每个子集对应一种染色,一共有2n 种不同染色. #,A,a1,a1,a2,a3,an,a1,a3,2022/12/8,集合论与图论第3讲,112,2022/

44、算,并集、交集相对补集、对称差、绝对补广义并集、广义交集,并集(union),并集: AB = x | (xA) (xB) xAB (xA) (xB)初级并:,2022/12/8,集合论与图论第3讲,116,并集(举例),例1: 设An=xR|n-1xn,n=1,2,10,则例2: 设An=xR|0 x1/n,n=1,2,则,2022/12/8,集合论与图论第3讲,117,交集(intersection),交集: AB = x | (xA) (xB) xAB (xA) (xB)初级交:,2022/12/8,集合论与图论第3讲,118,交集(举例),例1: 设An=xR|n-1xn,n=1,2,

45、10,则例2: 设An=xR|0 x1/n,n=1,2,则,2022/12/8,集合论与图论第3讲,119,不相交(disjoint),不相交: AB=互不相交: 设A1,A2,是可数多个集合, 若对于任意的ij, 都有AiAj=, 则说它们互不相交例: 设 An=xR|n-1xn, n=1,2,10, 则 A1,A2,是不相交的,2022/12/8,集合论与图论第3讲,120,相对补集(set difference),相对补集: 属于A而不属于B的全体元素,称为B对A的相对补集, 记作A-BA-B = x | (xA) (xB) ,A-B,A,B,2022/12/8,集合论与图论第3讲,12

47、,3)AB=xR|(0 x1)(2x3)=0,1)2,3),),),),2022/12/8,集合论与图论第3讲,124,2022/12/8,集合论与图论第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= a,b,c,d,e,f,2022/12/8,集合论与图论第3讲,126,广义交集(big intersection),广义交: 设A是集族, A中所有集合的公共元素的全体, 称为A的广义交

48、, 记作A.A = x | z(zAxz) 当A是以S为指标集的集族时A = A|S= A S例: 设 A=1,2,3,1,a,b,1,6,7, 则 A= 1,2022/12/8,集合论与图论第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=, A4=,A5= a, A5= aA6=, A6=E,文氏图(Venn diagram),文氏图: 平面上的n个圆(或椭圆),使得任何可能的相交部分, 都是非空的和连通的

49、John Venn, 18341923例:,2022/12/8,集合论与图论第3讲,128,文氏图(应用),文氏图可表示集合运算(结果用阴影表示),AB,AB,A-B,AB,A,A,A,A,A,A,A,B,B,B,B,B,AB=,2022/12/8,集合论与图论第3讲,129,容斥原理(principle of inclusion/exclusion),容斥原理(或包含排斥原理),2022/12/8,集合论与图论第3讲,130,容斥原理(证明),n=2时的情况:|AB|=|A|+|B|-|AB| 归纳证明: 以n=3为例:|AB C| = |(AB)C|= |AB|+|C|-|(AB)C| =

50、 |A|+|B|-|AB|+|C|-|(AC)(BC)| = |A|+|B|-|AB|+|C| -(|AC|+|BC|-|(AC)(BC)|) = |A|+|B|+|C|-|AB|-|AC|-|BC| +|ABC|,A,B,B,C,A,2022/12/8,集合论与图论第3讲,131,2022/12/8,集合论与图论第3讲,132,容斥原理(举例),例1: 在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少?解: 设 E=xN|1x10000, |E|=10000 A=xE|x=k2kZ, |A|=100 B=xE|x=k3kZ, |B|=21 则 |(AB)|=|E|-|