02 第1章-集合论初步.pptx

第1页：集合论初步 课件封面

集合论初步课件封面

离散数学 Discrete Mathematics，本章为集合论初步。

第2页：第1章集合论初步

第1章集合论初步

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第3页：数学危机与集合论

集合论初步本章学习内容

• 数学危机与集合论
• 集合的基本知识
• 无限集及其性质
• 集合代数的应用

第4页：数学危机与集合论

数学危机与集合论

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第5页：第一次数学危机

第一次数学危机

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第6页：第二次数学危机

第二次数学危机

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第7页：第二次数学危机

第二次数学危机

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第8页：第二次数学危机

第二次数学危机

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第9页：第三次数学危机

第三次数学危机

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第10页：第三次数学危机

第三次数学危机

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第11页：第三次数学危机

第三次数学危机

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第12页：数学危机与集合论

集合论初步本章学习内容

• 数学危机与集合论
• 集合的基本知识
• 无限集及其性质
• 集合代数的应用

第13页：集合的基本知识

集合的基本知识

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第14页：集合的基本知识

集合的基本概念几种特殊的集合集合的运算与性质

第15页：集合论

集合论

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第16页：集合论

集合的概念什么是集合：在朴素集合论中不能精确定义；在公理集合论中通过公理来定义。集合（SET）由指定范围内满足给定条件的所有对象聚集在一起构成。中国所有真皮沙发的聚集指定范围所有对象指定范围内的每一个对象称为这个集合的元素或成员

第17页：集合与元素的关系

集合与元素的关系

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第18页：集合与元素的关系

例：（罗素悖论）在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些不自己理发的人理发。那么，谁给这位理发师理发？

解：设C＝{x|x是不给自己理发的人}，b是这位理发师如bC，则bC；如bC，则bC。集合与元素的关系

第19页：集合的记法

集合的记法

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第20页：集合的表示法

集合的表示法

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第21页：枚举法列出集合中全部元素例题

枚举法列出集合中全部元素或部分元素的方法叫枚举法

例：指出下列集合的表示方法（1）A＝{a，b，c，d}（2）B = {0, 1, 4, 9, 16,…, n2,…}适用场景：一个集合仅含有限个元素一个集合的元素之间有明显关系

第22页：枚举法的优劣是一种显式表示法优点

：具有透明性缺点：在表示具有某种特性的集合或集合中元素过多时受到了一定的局限，而且，从计算机的角度看，显式法是一种“静态”表示法，如果一下子将这么多的“数据”输入到计算机中去，那将占据大量的“内存”。

第23页：描述法通过刻画集合中元素所具备的某种特性

来表示集合的方法称为描述法。表示方法：A＝{x|P(x)}适用场景：含有很多或无穷多个元素；集合的元素之间有容易刻画的共同特征。突出优点：不要求列出集合中全部元素，只要给出集合中元素的特性。X所具有的性质p

第24页：描述法A =例题

描述法A = {x|x是“discrete mathematics”中的所有字母}；Z = {x|x是一个整数}；S = {x|x是整数，并且x2＋1 = 0}；Q+= {x|x是一个正有理数}。

例：指出下列集合的表示方法

第25页：归纳法是通过归纳定义

集合，主要由三部分组成：第一部分：基础。指出某些最基本的元素属于某集合；第二部分：归纳。指出由基本元素造出新元素的方法；第三部分：极小性。指出该集合的界限。注意：第一部分和第二部分指出一个集合至少包括的元素，第三部分指出一个集合至多要包含的元素归纳法

第26页：集合A按如下方式定义例题

例：集合A按如下方式定义，试指出其定义方式。（1）0和1都是A中的元素；（2）如果a, b是A中的元素，则ab, ba也是A中的元（3）有限次使用(1)、(2)后所得到的字符串都是A中的元素。归纳法

第27页：是指通过计算规则定义例题

是指通过计算规则定义集合中的元素的方法

例：设a0＝1，ai+1＝2ai（i0）定义S＝{a0，a1，a2，...}＝{ak| k0}，试写出集合S中的所有元素。递归法

第28页：文氏图解法是一种利用平面上点的集合作成的

对集合的图解。一般用平面上的圆形或方形表示一个集合。AA文氏图法

第29页：元素的基本性质

元素的基本性质

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第30页：集合的基本知识的定理与性质

例：设E={x|(x-1)(x-2)(x-3)=0, x∈R}F={x|(x∈ Z+)且(x2＜12)}。试指出集合E和F中的元素。集合之间的关系

定理：（外延性原理）集合A与B相等当且仅当A与B具有相同的元素，记为：A=B，否则A与B不相等，记为AB。§1相等关系

第31页：集合之间的关系相等关系的性质⑴自反性

• ：对任何集合A，有A=A。
• 传递性：对任何集合A、B、C，如果有A=B且B=C，则A=C。
• 对称性：对任何集合A、B，如果有A=B，则B=A。

第32页：集合的基本知识的定义

§2包含关系

定义

设A,B是任意两个集合，如果B的每个元素都是A的元素，则称B是A的子集(Subset)，亦称A包含B，或称B被A包含。记作AB或BA。集合之间的关系上述包含定义可用数学语言描述为：BA对任意x，如xB，则xA。

第33页：集合的基本知识的定理与性质

例：设A = {BASIC, PASCAL, ADA}，B = {ADA, BASIC, PASCAL}，请判断A和B之间的包含关系。

定理：设A、B是任意两个集合，则AB，BAA=B集合之间的关系

第34页：集合之间的关系包含关系的性质⑴自反性

• ：对任何集合A，有AA。
• 传递性：对任何集合A、B、C，如果有AB且BC，则AC。
• 反对称性：对任何集合A、B，如果有AB且BA，则A=B。

第35页：集合的基本知识的定义

定义

设A,B是任意两个集合，如果BA并且A≠B则称B是A的真子集(Proper Subset )，记作BA。真子集的符号描述为：BA对任意x，如xB，则xA，并且存在yA，但是yB集合之间的关系§3真包含关系BA

第36页：试判断下列集合之间的包含关系例题

例：试判断下列集合之间的包含关系。（1）{a, b}和{a, b, c, d}；（2）{a, b, c, d}和{a, b, c, d}。例题

例：设A = {a}是一个集合，B = {{a}, {{a}}}，试问{A}∈B和{A}B同时成立吗？

第37页：集合的基本知识

集合的基本知识

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第38页：集合的基本知识

集合的基本概念几种特殊的集合集合的运算与性质

第39页：空集的定义

空集可以符号化为：Φ = {x|x≠x}空集是客观存在的。

例：设A = {x|(x∈R)且(x2<0)}，试列举集合A中的所有元素。空集的概念与性质

空集

不含任何元素的集合叫做空集(EmptySet)，记作Φ。

第40页：集合的基本知识的定理与性质

定理：（1）空集是一切集合的子集；（2）空集是绝对唯一的。

例：指出下列结论中哪些是错误的（1）ΦΦ;（2）Φ∈Φ;（3）Φ{Φ};（4）Φ∈{Φ}空集的概念与性质

第41页：全集或论集的定义

全集或论集

在一个相对固定的范围内，包含此范围内所有元素的集合，称为全集或论集(UniversalSet)，用U或E表示。U全集的概念与性质全集可用文氏图描述为:

定理：全集是相对唯一的.

第42页：集合A的基数的定义

如果|A|是有限的，则称集合A为有限集，如果|A|是无限的，则称集合A为无限集。有限集和无限集

集合A的基数

集合A中元素的数目称为集合A的基数（base number)，记为|A|。

第43页：集合的基本知识

集合的基本知识

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第44页：集合的基本知识的定义

例：设A={a,b,c}，求出其全部m元子集，并证明n元集合的子集总数为2n或2|A|m元子集

定义

如果一个集合A含有n个元素，则称集合A为n元集，称A的含有m个(0≤m≤n)元素的子集为A的m元子集。分析：对于n元集，它的m（0mn）元子集有C(n,m)个，所以不同的子集总数有：C(n,0)+ C(n,1)+ … + C(n,n)＝(1+1)n＝2n

第45页：集族的定义

幂集的概念与性质

集族

设A为任一集合，称A的所有不同子集构成的集合为A的幂集(power set)，记为P(A)或2A。上述幂集定义可用数学语言描述为：P(A)＝{x|一切xA}通常将以集合为元素的集合称为集族(family of set)。显然，幂集是集族。

第46页：幂集集合{0例题

幂集

例：集合{0，1，2}的幂集合是什么？

解：幂集合P({0,1,2})是{0，1，2}所有子集的集合。因此有：P({0,1,2})={Φ,{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}}

第47页：空集的幂集合是什么？例题

例题

例：空集的幂集合是什么？集合{Φ}的幂集合是什么？

解：空集只有一个子集，这就是它自己。因此有：P(Φ)={Φ}集合{Φ}有两个子集，即Φ和集合{Φ}自身。故有：P({Φ})={Φ, {Φ}}

第48页：集合的基本知识

集合的基本概念几种特殊的集合集合的运算与性质

第49页：A与B的交集的定义

交运算

A与B的交集

(交运算∩)设A,B为任意两个集合，A∩B称为A与B的交集，定义为:A∩B=｛x∣x∈A且x∈B｝交运算的文氏图表示为：ABU

第50页：交运算交运算的性质

• 幂等律对任何集合A，有A∩A=A。
• 交换律对任何集合A、B，有A∩B=B∩A
• 结合律对任何集合A、B、C，有(A∩B)∩C=A∩(B∩C)。
• 同一律对任何集合A，有A∩E=A。
• 零律对任何集合A，有A∩Φ=Φ。
• ABA∩B=A

第51页：A与B的并集的定义

并运算

A与B的并集

(并运算∪)设A,B为任意两个集合，A∪B称为A与B的并集，定义为:A∪B=｛x∣x∈A或x∈B｝ABU并运算的文氏图表示为：

第52页：并运算并运算的性质

• 幂等律对任何集合A，有A∪A=A
• 交换律对任何集合A、B，有A∪B=B∪A
• 结合律对任何集合A、B、C，有(A∪B)∪C=A∪(B∪C)
• 同一律对任何集合A，有A∪Φ=A
• 零律对任何集合A，有A∪U =U

第53页：并运算并运算的性质

• （续）
• 分配律对任何集合A、B、C，有A∩(B∪C) =(A∩B)∪(A∩C)。A∪(B∩C) =(A∪B)∩(A∪C)。
• 吸收律对任何集合A、B，有A∪(A∩B)=A A∩(A∪B)=A。
• ABA∪B=B。

第54页：A的补集的定义

AU绝对补运算

A的补集

(补运算)设A为任一集合，称为A的补集，定义为:=U-A =｛x∣x∈U且xA｝补运算的文氏图表示为：

第55页：绝对补运算补运算的性质

• ~U=Φ
• ~Φ=U
• ~(~A)=A
• A∩~A=Φ
• A∪~A=U
• A-B=A∩~B
• ~(A∩B)=~A∪~B
• (A∪B)=~A∩~B
• AB~B~A
• ~A=B当且仅当A∪B=U且A∩B=Φ

第56页：A与B的差集的定义

相对补运算

A与B的差集

(差运算)设A,B为任意两个集合，A-B称为A与B的差集，定义为:A-B =｛x∣x∈A且xB｝ABU差运算为亦称为相对补运算，其文氏图为：

第57页：相对补运算差运算的性质

• A-Φ=A
• Φ-A=Φ
• A-A=Φ
• A-BA
• ABA-B=Φ
• (A-B)-C=(A-C)-(B-C)
• A-(B∩C)=(A-B)∪(A-C)
• A-(B∪C)=(A-B)∩(A-C)
• A∩(B-C)=(A∩B)-(A∩C)注意：∪对-是不可分配的，如A∪(A-B)=A而(A∪A)-(A∪B)=Φ

第58页：A与B的环和或对称差的定义

环和运算

A与B的环和或对称差

(环和运算)设A,B为任意两个集合，AB称为A与B的环和或对称差，定义为:AB = (A-B)∪(B-A)环和运算的文氏图表示为：ABU

第59页：环和运算对称差运算的性质

• 交换律AB=BA
• 结合律(AB)C=A(BC)
• 同一律AΦ=A
• AA=Φ
• ∩对可分配A∩(BC)=(A∩B)(A∩C)

第60页：集合的基本知识

A1∪A2∪A3∪……∪An={x|(xA1)或(xA2)或……或(xAn)}＝A1∩A2∩A3∩……∩An＝{x|(xA1)且(xA2)且……且(xAn)}推广到多个集合

第61页：推广到无限个集合＝A1∪A2∪A3∪…＝

A1∩A2∩A3∩…

第62页：（1）等幂律

• :Ａ∪Ａ=Ａ；Ａ∩Ａ=Ａ；
• 交换律:Ａ∪Ｂ=Ｂ∪Ａ;Ａ∩Ｂ=Ｂ∩Ａ
• 结合律:Ａ∪(Ｂ∪Ｃ)=(Ａ∪Ｂ)∪Ｃ；Ａ∩(Ｂ∩Ｃ)=(Ａ∩Ｂ)∩Ｃ；
• 同一律:Ａ∪Φ=Ａ；Ａ∩Ｕ=Ａ；
• 零律:Ａ∪Ｕ=Ｕ；Ａ∩Φ=Φ；
• 分配律:Ａ∩(Ｂ∪Ｃ)=(Ａ∩Ｂ)∪(Ａ∩Ｃ)Ａ∪(Ｂ∩Ｃ)=(Ａ∪Ｂ)∩(Ａ∪Ｃ)
• 吸收律:A∩(A∪B)=A; A∪(A∩B)=A；集合运算的基本性质

第63页：（8）矛盾律

• ：A∩＝Φ；
• 排中律：A∪＝U。
• 否定律：；
• DeMorgan律：；集合运算的基本性质

第64页：集合的基本知识

DeMorgan律：分析根据定理2设A、B是任意两个集合，则AB，BAA=B证明示例

第65页：证明（1）式由①、②知，①②

证明（1）式由①、②知，①②

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第66页：证明（2）式在中

证明（2）式在中

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第67页：数学危机与集合论

集合论初步本章学习内容

• 数学危机与集合论
• 集合的基本知识
• 无限集及其性质
• 集合代数的应用

第68页：无限集及其性质

无限集及其性质

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第69页：无限集及其性质

无限集的基本概念自然数的集合定义可数集与不可数集

第70页：问题一、下列哪个集合中的元素比较多？

1.{1,2,3,…}2.{12,22,32,…}无限集的度量问题问题二、伽利略悖论

第71页：质变无限集合无法用确切的个数来描述无限集

的度量问题该怎么解决？度量无限集合的尺子是什么？有限集无限集量变无限集的度量问题

第72页：无限集及其性质的定义

723.3集合定义的自然数和归纳法证明等势的概念

定义

(设A，B是两个集合，若在A，B之间存在1-1对应的关系：ψ：A→B则称集合A与B等势(equipotent)，记为：AB。

注意：若A＝B，则AB。若AB，则A＝B（×）（∨）

第73页：两个有限集合等势当且仅当它们有相同的元素

个数；有限集合不能与其任何真子集等势；可数集合可以和其可数的真子集等势。等势的性质

第74页：无限集及其性质

无限集的基本概念自然数的集合定义可数集与不可数集

第75页：基本思路

基本思路

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第76页：无限集及其性质的定义

763.3集合定义的自然数和归纳法证明

定义

（1）称空集为自然数，记为0。（2）称A'＝A{A}为集合A的直接后继。

例：{a,b}'＝{a,b, {a,b}}'＝{}={}{}'= {}{{}}={,{}}{,{}}'={,{},{,{}}}集合的后继

第77页：自然数的基本特点

自然数的基本特点

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第78页：无限集及其性质的定义

定义

归纳定义自然数集N：（l）基础条款：N。（2）归纳条款：若xN，则x′=x{x}N。3.3集合定义的自然数和归纳法证明自然数的归纳定义

第79页：即给出自然数一个有趣的定义

：0＝，1＝{}＝{0}，2＝{,{}}＝{0,1}...n＝{0,1,2,3,...n-1}...故有：N＝{0,1,2,3,...,n,...}自然数的归纳定义

第80页：无限集及其性质

无限集的基本概念自然数的集合定义可数集与不可数集

第81页：可数集合的定义

可数集合

凡是与自然数集合等势的集合，统称为可数集合(可列集)(Countable Set )。可数集合记为：א0(读作阿列夫零)。

例：下列集合都是可数集合：1)O+＝{x|xN，x是正奇数};2)P＝{x|xN，x是素数};3)有理数集合Q.可数集合

第82页：在O+与N之间建立如下1-1对应关系

：N０１２３４...ｎ...ｆ↓↓↓↓↓...↓...O+１３５７９... 2n+1 ...所以，O+是可数集合。O+是可数集合

第83页：P是可数集合在P与N之间建立如下1-1对

应关系N０１２３４...ｆ↓↓↓↓↓...P２３５７11 ...所以，P是可数集合。

第84页：Q是可数集合

Q是可数集合

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第85页：不可数集合的定义

不可数集合

不可数集合

开区间(0,1)称为不可数集合，其基数设为א(读作阿列夫)；凡是与开区间(0,1)等势的集合都是不可数集合。

例：(1)闭区间[0,1]是不可数集合；(2)实数集合R是不可数集合。

第86页：在闭区间[0,1]和开区间(0,1)之间

建立如下对应关系：[0,1]是不可数集合

第87页：在实数集R和开区间(0,1)之间建立如下

对应关系：R是不可数集合

第88页：数学危机与集合论

集合论初步本章学习内容

• 数学危机与集合论
• 集合的基本知识
• 无限集及其性质
• 集合代数的应用

第89页：集合代数的应用

集合代数的应用

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第90页：集合代数的应用

一、集合在计算机中的表示二、几个应用实例

第91页：集合的计算机表示

集合的计算机表示

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第92页：二进制编码方法

二进制编码方法

本页源文件仅提取到标题文字，正文以图示呈现，建议对照原课件图片补充本页要点说明。

第93页：二进制编码方法

例：令U={1, 2, 3, 4, 5, 6, 7, 8, 9, 10},并且U的元素从小到大排序，即ai=i。（1）表示U中所有奇数的子集A、所有偶数的子集B和不超过5的整数的子集C的位串是什么？（2）计算A∪B，A∩C二进制编码方法

第94页：用H代表硬币正面例题

例：用H代表硬币正面，T代表硬币反面。试写出当扔出三个硬币时可能出现的结果所组成的集合。

解：8种可能：{HHH，HHT，HTH，HTT，THH，THT，TTH，TTT}。但这三个硬币没有顺序之分，即HHT和HTH是同一个元素，所以A = {HHH，HHT，HTT，TTT}。几个应用实例

第95页：一个正三角形被均分为三个例题

例：一个正三角形被均分为三个小三角形，如图1所示。用黑、白二色对小三角形着色（经旋转能使之重合的算一种）。写出不同图像构成的集合。图112345678图3图2几个应用实例

第96页：因为每个小三角形均可着色例题

解：因为每个小三角形均可着色，三个小三角形共有2×2×2 = 8种着色方案。因为经旋转能使之重合的图像算一种，如图2，所以共有4种不同的着色方案。因此由不同图像构成的集合为{1,2,5,8}。1258几个应用实例

第97页：集合论初步 本章小结

集合论初步小结

本节内容到此结束，谢谢大家！