当前位置：文档之家 › 离散数学教学PPT第四章

离散数学教学PPT第四章

  • 格式：pptx
  • 大小：1.91 MB
  • 文档页数：43

下载文档原格式

  / 43

合集下载

离散数学第四章课件

离散数学第四章课件
8
5元关系的实例—数据库实体模型
员工号 301 302 303 304 … 姓名 张 林 王晓云 李鹏宇 赵 辉 … 年龄 50 43 47 21 … 性别 男 女 男 男 … 工资 1600 1250 1500 900 …
5元组： <301,张林,50,男,1600>，<302,王晓云,43,女,1250>
11
A上重要关系的实例（续）
小于等于关系LA, 整除关系DA, 包含关系R定义如下： 定义4.7 LA={<x,y>| x,y∈A∧ x≤y}, 这里AR，R为实数集合 DB={<x,y>| x,y∈B∧ x整除y}, BZ*, Z*为非0整数集 R={<x,y>| x,y∈A∧ xy}, 这里A是集合族. 例如 A={1,2,3}, B={a,b}, 则 LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>} DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>} A=P(B)={,{a},{b},{a,b}}, 则A上的包含关系是 R={<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>, <{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>} 类似的还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等等.
22
关系运算的性质（补）
•设R1是从A到B的关系，R2和R3是从B到C的关系， R4是从C到D的关系，则： （1）R1(R2R3)=R1R2R1R3 （2）R1(R2R3)R1R2R1R3 （3）(R2R3)R4=R2R4R3R4 （4）(R2R3)R4R2R4R3R4

《离散数学讲义》课件

《离散数学讲义》课件
离散概率分布的定义
离散概率分布是描述随机事件在有限或可数无限的可 能结果集合中发生的概率的数学工具。
离散概率分布的种类
常见的离散概率分布包括二项分布、泊松分布、几何 分布等。
离散概率分布的应用
离散概率分布在统计学、计算机科学、物理学等领域 都有广泛的应用。
参数估计和假设检验
参数估计
参数估计是根据样本数据推断总体参数的过 程，包括点估计和区间估计两种方法。
假设检验
假设检验是用来判断一个假设是否成立的统计方法 ，包括参数检验和非参数检验两种类型。
参数估计和假设检验的应 用
在统计学中，参数估计和假设检验是常用的 数据分析方法，用于推断总体特征和比较不 同总体的差异。
方差分析和回归分析
方差分析
方差分析是一种用来比较不同组数据的平均值是否存在显著差异 的统计方法。
《离散数学讲义》ppt课件
目 录
• 离散数学简介 • 集合论 • 图论 • 离散概率论 • 逻辑学 • 离散统计学 • 应用案例分析
01
离散数学简介
离散数学的起源和定义
起源
离散数学起源于17世纪欧洲的数学研 究，最初是为了解决当时的一些实际 问题，如组合计数和图论问题。
定义
离散数学是研究离散对象（如集合、 图、树、逻辑等）的数学分支，它不 涉及连续的变量或函数。
联结词：如与(&&)、或(||)、非(!)等，用 于组合简单命题。
03
04
命题公式：由简单命题通过联结词组合而 成的复合命题。
命题逻辑的推理规则
05
06
肯定前件、否定后件、析取三段论、合取 三段论等推理规则。
谓词逻辑
个体词
表示具体事物的符号。

《离散数学》完整课件

《离散数学》完整课件

第三节 复合关系与逆关系
本节讨论关系的复合运算与逆运算极其 性质;主要考虑了下列问题:
1.关系的复合是否满足交换律、结合律、 关系的复合对于集合的并(交)是否有分 配律;
2.关系的复合运算与逆运算在关系图和 关系矩阵上的反应;
3.关系的复合运算与关系的逆运算之间 的运算规律.
返回本章首页
11 2021/6/7
|A|<|B|三条中有且仅有一条成立；
2.Bernstein定理:设A,B是两个集合,若|A|≥|B| 且|A| ≤ |B|,则集合A,B等势;
3.设A是任意集合,P(A)为A的幂集,则P(A)的基 数大于A的基数.
返回本章首页
23 2021/6/7
本章小结
本章的主要内容有：集合的等势、有限 集与无限集、可数集与不可数集、较为 常见的集合的基数等.集合的基数反映了 集合的元素的多少，它是集合的一种性 质，一种与该集合等势的集合构成的集 合族的共同性质.
返回本章首页
17 2021/6/7
第九节 复合映射与逆映射
映射的复合就是关系的复合,须注意的是 复合的次序,主要内容有:
1.映射的复合具有结合律,但不符合交换律; 2.区分了左逆与右逆；给出里左逆、右逆
与单射、满射之间的关系； 3.可逆与左、右逆之间的关系.
返回本章首页
18 2021/6/7
本章小结
1.本节首先给出了公式的蕴涵关系的三个等价定 义,及蕴涵关系具有的性质,给出了15个基本蕴 涵式；
2.把蕴涵概念推广,得到公式的逻辑结果的定义；
3.为了研究推理，还引进演绎的概念；
4.用实例说明推理方法.
返回本章首页
30 2021/6/7
第六节 形式演绎

精品课程《离散数学》PPT课件(全)

精品课程《离散数学》PPT课件(全)

言1
为什么学习离散数学？
离散数学是现代数学的一个重要分支，是计算机科学与技术 的理论基础，所以又称为计算机数学，是计算机科学与技术 专业的核心、骨干课程。
它以研究离散量的结构和相互间的关系为主要目标，其研 究对象一般是有限个或可数个元素，因此它充分描述了计算 机科学离散性的特点。
离散数学是什么课？
真值为1
25
1.1 命题符号化及联结词
以下命题中出现的a是给定的一个正整数： (3) 只有 a能被2整除， a才能被4整除。
(4) 只有 a能被4整除， a才能被2整除。
解： 令r： a能被4整除， s： a能被2整除。 真值不确定 (3)符号化为 s r (4)符号化为 r s
真值为1
26
19
1.1 命题符号化及联结词
3.析取词 设p,q为二命题，复合命题“p或q” 称为p与q的析取式，记作p ∨ q，符号∨称 为析取联结词。 运算规则：
p 0 0 1 1 q 0 1 0 1 p∨q 0 1 1 1
20
1.1 命题符号化及联结词
析取运算特点：只有参与运算的二命题全为假时，运算结果才 为假，否则为真。 相容或：二者至少有一个发生，也可二者都发生 排斥或：二者只有一个发生，即非此即彼 例如： （1）小王爱打球或爱跑步。 设p：小王爱打球。 q：小王爱跑步。 则上述命题可符号化为：p ∨ q （2）张晓静是江西人或湖南人。 设p：江西人。 q：湖南人。 则上述命题就不可简单符号化为：p ∨ q 而应描述为(p∧ q) ∨( p∧q)(也可用异或联接词∨)

（1）星期天天气好，带儿子去了动物园； （2）星期天天气好，却没带儿子去动物园； （3）星期天天气不好，却带儿子去了动物园； （4）星期天天气不好，没带儿子去动物园。

离散数学第四章课件ppt

离散数学第四章课件ppt

例1 设R＝{<x，y>|x、y∈N∧y＝x2}和S＝{<x，y>|x、 y∈N∧y＝x＋1}是N上的关系，求R-1、R*S、S*R。
解 R-1＝{<y，x>|x、y∈N∧y＝x2}
R*S＝{<x，y>|x、y∈N∧y＝x2＋1}
S*R＝{<x，y>|x、y∈N∧y＝(x＋1)2}
定理4.9 设R和S为任意两个二元关系，则： (1)(R-1)-1＝R。 (2)(R∪S)-1＝R-1∪S-1。 (3)(R∩S)-1＝R-1∩S-1。 (4)(R－S)-1＝R-1－S-1。 (5)(A×B)-1＝B×A。 证 (2)因为<x，y>∈(R∪S)-1<y，x>∈(R∪S) 明 <y，x>∈R∨<y，x>∈S
注： (1)当x≠y时，<x，y>≠<y，x>； (2)<x，y>＝ <u，v>当且仅当x＝u∧y＝v； (3)序偶<x，y>与集合 {x，y}不同。
定义4.2 n个元素x1、x2、…、xn按一定的 次序排列组成的有序序列称为有序n元组，记 作<x1，x2，…，xn>。
例如，表示时间的年月日组成一个三元组。
证 明
(2)因为y∈R[A∩B] x(x∈A∩B∧xRy) c∈A∧c∈B∧cRy
(c∈A∧cRy)∧(c∈B∧cRy)
y∈R[A]∧y∈R[B] y∈R[A]∩R[B]， 所以R[A∩B] R[A]∩R[B]。
4.2.2关系矩阵与关系图
定义4.11 设A＝{x1，x2，…，xn}，B＝{y1，

定理4.10 设R、S和T为任意三个二元关 系，则： (1)DR*SDR，RR*SRS。 (2)RS∧TWR*TS*W。 (3)R*(S∪T)＝(R*S)∪(R*T)。 (4)R*(S∩T)(R*S)∩(R*T)。 (5)R*S－R*TR*(S－T)。 (6)(R*S)-1＝S-1*R-1。 (7)(R*S)*T＝R*(S*T)。

离散数学ppt

离散数学ppt

如果X Y，则将A中的X用Y置换所得到 的命题公式B与A等价。 例题： 1、证明：(PQ) (P Q) P 2、证明：(PQ) (Q R) (P Q) R 对偶式： 对偶的概念： 对偶定理：设A，B是命题公式，如果 A B，则A* B*
第四节 主析取范式与主合取范式 命题公式的规范化 1、命题联结的归约：最小命题联结词组 2、命题范式 定义1：一个命题公式称为合取范式，如果它具 有如下形式：A1 A2 …An，其中A1 ， A2 ， …，An都是由命题变元或其否定所组成 的析取式。 定义1：一个命题公式称为析取范式，如果它具 有如下形式：A1 A2 … An，其中A1 ，
注： ①双条件联结词与自然语言中的
“当且仅当”，“充分必要”类似， 但也不尽相同。
②二元运算
命题联结词除了上述五个之外，还有不可 兼析取、条件否定、与非、或非联结词。 在一个复合命题中往往含有多个命题联结 词，其运算的次序是：、、、、 第二节 命题公式及其分类 直观地说，由命题变元、命题常量、命题 联结词、括号组成的一个有意义的式子 成为命题公式。
类似于主析取范式，也有主合取范式。 定义：n个命题变元的析取式，称为布尔大 项或析取，如果每个命题变元或其否定 不能同时出现，但二者必须出现且仅出 现一个。 注：①n个命题变元构成的布尔 大项有2n个 ②布尔大项的编码：命题变元-0，其否定-1 布尔大项的常见性质： 1、每个大项当其真值指派与编码相同时，
的量词。 例子： 所有人都要呼吸：(x)M(x)H(x) 每个学生都要参加考试： (x)P(x)Q(x) 2、存在量词－ 用以表示“有一些”，“至少有一个”等 概念的量词。 例子： 有些人是聪明的：
有的人早饭吃面包： 全称量词与存在量词统称为量词。 在上面的例子中，每个由量词确定的表达 式，都与个体域有关。我们通常总是在 全总个体域中考虑问题，因此就要通过 相应的谓词对个体变元的取值范围加以 说明，这就是特性谓词。一般地，对全 称量词，特性谓词常做蕴含的前件；对 存在量词，特性谓词常作合取项。

离散数学第四章课件

离散数学 第四章 函数
1
目录
4-1 函数的基本概念 4-2 逆函数和复合函数 4-4 基数的概念 4-5 可数集与不可数集 4-6 基数的比较 小结 习题
2
函数是一个基本的数学概念，应用的范围很广，在计算机 科学的理论中，如计算理论 、开关理论、编译理论、数 据库理论、软件工程、计算机安全保密，操作系统等都 用到函数。函数---输入和输出间的关系。也叫变换、映 射。
h={<x,y>|x,y∈R∧y= x2 }
r ={<x,y>|x,y∈R∧y=lgx }
v ={<x,y>|x,y∈R∧y= √ x }
可见这里所说的函数与以前的数学中函数有区别。
6
4-1 函数的基本概念
自变元与函数值(像源与映像) ：f:XY, 如果<x,y>∈f, 称x是自变元(像源)，称 y是x 的函数值(x的映像) 。 <x,y>∈f y=f(x) f:xy
.定义域、值域和陪域(共域) ：f:XY, f的定义域(domain)，记作dom f，或Df 即 Df =dom f={x|x∈X∧y(y∈Y∧<x,y>f)} =X f的值域(range) ：记作ran f， 或Rf 即或f(X) Rf =ran f=f(X)={y| y∈Y∧x(x∈X∧<x,y>f)} 前面例中Rh =ran h=h(R)=R+, R+是非负实数。 f的陪域(codomain):即是Y称之为f的陪域。
用有向图复合:
1X。 2。 3。
f
。Y 。1 。2 。3
4
g X。1
。2 。3 。4 。5
g f
X 1。 2。

离散数学(第4讲PPT课件


•
（～Ｐ∧Ｐ）∨Q=Q
• 将命题变元P补进去，并利用分配律展开，然后合 并相同的子句，此时得到的子句将是标准的极大项。
• （8）利用幂等律将相同的极小项和极大项合并，
同时利用交换律进行顺序调整，由此可转换成标准
的主析取范式和主合取范式。
28
第28页/共33页
例1-5.4
利用公式的等价求G＝(P→Q)∧R的主合取范式和主析取范式。
解：G＝(P→Q)∧R＝(～P∨Q)∧R（蕴涵）
＝(～P∨Q∨(R∧～R))∧
((～P∧P)∨(～Q∧Q)∨R)（添加R、P、Q）
＝(～P∨Q∨R)∧(～P∨Q∨～R)∧ (～P∨～Q∨R)∧(～P∨Q∨R)∧
(P∨～Q∨R)∧(P∨Q∨R) （分配律）
＝(P∨Q∨R)∧(P∨～Q∨R)∧(～P∨Q∨R)∧
第24页/共33页
例1-5.3（续）
• 2)、求公式的主合取范式
P Q R (P→Q)
R
000 0 001 1 010 0 011 1 100 1 101 0 110 0 111 1
极大项
P∨Ｑ∨Ｒ
极大项
P∨～Ｑ∨Ｒ
极大项 极大项
～P∨Ｑ∨～Ｒ ～P∨～Ｑ∨Ｒ
2021/4/22
25
第25页/共33页
4种不同的组合极大项对于n个命题变元共有2个不同的极大项记为2020310计算机学院16极大项公式成假赋值名称2020310计算机学院17没有两个不同的极小项是等价的且每个极小项只有一组真值指派使该极小项的真值没有两个不同的极大项是等价的且每个极大项只有一组真值指派使该极大项的真值2020310计算机学院182020310计算机学院19极大项取值0当且仅当
要解决这个问题，我们引入范式(公式的标准型)的概念。

离散数学讲义ppt课件


课程概况
教材：
《离散数学（第三版）》，耿素云等编著 清华大学出版社，2004年3月
参考书：
（1） 《离散数学(第二版)》及其配套参考书《离散 数学题解》作者：屈婉玲，耿素云，张立昂 清华大学出版社
（2） 《离散数学》焦占亚主编 电子工业出版社 2005年1月
2
课程概况
选修课/必修课：选修 周学时：3（学时） 上课周：1－16周 总学时：48（学时）
3
课程内容及学时安排
第一篇 数理逻辑（14学时）
第一章 命题逻辑（8） 第二章 谓词逻辑（6）
第二篇 集合论（12学时）
第三章 集合（4） 第四章 二元关系与函数（8）
第四篇 图论（14学时）
第七章 图论（8） 第八章 一些特殊图（4） 第九章 树 （2）
4
课程考核
第四篇 代数系统（8学时）
第5、6章 图论（8）
所以，伊勒克持拉既知道并且又不知道这个人是她的 哥哥。
20
NO.3 M：著名的理发师悖论是伯特纳德·罗素提出的。一个理发 师的招牌上写着： 告示：城里所有不自己刮脸的男人都由我给他们刮脸，我 也只给这些人刮脸。 M：谁给这位理发师刮脸呢？ M：如果他自己刮脸，那他就属于自己刮脸的那类人。但 是，他的招牌说明他不给这类人刮脸，因此他不能自己来 刮。 M：如果另外一个人来给他刮脸，那他就是不自己刮脸的 人。但是，他的招牌说他要给所有这类人刮脸。因此其他 任何人也不能给他刮脸。看来，没有任何人能给这位理发 师刮脸了！
P
Q
PQ
P
0
0
0
1
0
1
0
1
1
0
0
0
1
1
1

离散数学课件第4章.ppt

【example】设R是英语字母串的集合上的关系并且使得 aRb当且仅当l(a)=l(b),其中l(x)是x的长度。R是等价关系吗？
Solution：
因为l(a)=l(b),从而只要a是一个串，就有aRa,故aR是自反的 其次，假设aRb，即l(a)=l(b)。那么有bRa，因为l(a)=l(b),因 此R是对称的。 最后假设aRb和bRc，那么有l(a)=l(b)和l(b)=l(c)。因此 l(a)=l(c)，即aRc，从而R使传递的。 由于R是自反的、对称的和传递的，R是等价关系。
系的所有元素的集合叫做a的等价类。 A的关于R的等价类记作[a]R 当只有一个关系被考虑时，我们将省去下标R并把这个等价类
写作[a]. 换句话说，如果R是集合A上的等价关系，元素a的等价类是
[a]R={s|(a,s)∈ R} 如果b∈ [a]R，b叫做这个等价类的代表元。
一个等价类的任何元素都可以作为这个类的代表元。也就是 说，对作为这个类的代表元所选择的特定元素没有特殊要求。
【example】对于模4同余关系，0和1的等价类是什么？
Solution： 0的等价类包含使得a ≡ 0( mod 4)的所有整数a。这个类中的
整数是被4整除的那些整数。因此，对于这个关系0的等价类是 [0]={…, -8, -4, 0, 4, 8,…}
－上述关系R图就是由三个独立的完全图构成的。
下面给出八个关系如图所示，根据等价关系有向图的特点， 判断哪些是等价关系。
下面是A ={1,2,3}中关系：
1。
1。
1。
1。
2。 。3
R1
1。
2。 。3
R2
1。
2。 。3 2。 。3
R3
1。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
再往后，平方数在自然数中所占的比例越来越小；
但是从另一个角度看，每一个自然数都对应着一个平 方数；
所以，自然数和平方数是一样多的， 这 “一一对应” 的 规则也就是判断集合是否一样大的标准。
8
任何一个有限集合不能与其真子集等势。 另一种有限集、无限集的定义方法； 定义：如果存在一一对应的f: S→S，使得f(S)⊂S，
证明：必要条件已经在前面证明，下面证明其充分 条件。
反证法：
鸽洞原理
设一集合M含有与其等势的真子集M’，若M’为有限集， 设其元素个数为n，即|M|=n，则此时必有n>m；
但此时M与M’间由于元素个数不同而无法建立一一对应 的关系而产生矛盾。
17
有限集和无限集的重要定义 定义4.5 一集合存在与其等势的真子集，则称为无 限集，否则称为有限集。
“全体正整数的集合和全体有 理数的集合等势”是在数学上 很重要的一个例子，说明一个 实数中的稠密集可以和一个离 散集等势（稠密：在任意两个 元素之间存在第三个元素）
22
因为每个有理数都可以写成一个分数形式如下：
... -3/1 -2/1 --1/1 0/1 1/1 2/1 3/1 ... ... -3/2 -2/2 -1/2 0/2 1/2 2/2 3/2 ... ... -3/3 -2/3 -1/3 0/3 1/3 2/3 3/3 ...
任意一个小于1 的非负小数，取其二进制形式，比如 0.1101001， 如果将小数点后第 i 位对应的 0/1 看成是自然数 i 在某个集合中的 无/有，那么0.1101001就对应自然数的一个子集 {1, 2, 4, 7}；
所以，任一个小数可以对应一个自然数的子集，当然，自然数的 一个子集，也可以很容易写出一个小数： [0,1) 之间的小数与自然 数 N 的所有子集的一一对应关系；
14
定理4.7 一个集合为无限集，则它必会有与它等势 的真子集。 说明：
无限集的另一个定义； 该无限集减去这个真子集后得到的差集，可以是无限
集，可以是有限集。
设M是一个无限集，现在需要证明：
必存在另一个无限集M’，M⊃ M’且M~ M’； 因为M不一定是可列集，因此才要这样证明，即：
M=(一个可列集)⋃(另一个集合)
... -3/4 -2/4 -1/4 0/4 1/4 2/4 3/4 ...
... ... ... ... ...
... ...
可以从0/1开始按照箭头指定次序排列Q中元素
(如果这个有理数在前面出现，就跳过去)， 2
所以Q是可数集。
1
另外 I×I~N如右图所示。
-3 -2 -1 0 1 2 3
同理可证 N×N~N
2 | i | i 0
f(i)＝ 0
i 0 是Ｉ到Ｎ的双射。
2i 1 i 0 因此Ｉ是可列集。
-3 -2 -1 0
1
2
3
21
定理4.11 有理数集Q是可列集
证明：一切有理数均呈的形式，现将所有按下列次序排列，
① 正分数按其分子分母之和的大小顺序排列：从小到大
② 正分数的分子分母之和相同者按照分子大小顺序排列：从大到小
xi =0.ai1ai2ai3 …… i=1,2,3,….. 即 0＜ xi＜1 aik∈{0,1,2,3,4,5,6,7,8,9} k=1,2,3,4,… 令 x1 =0.a11a12a13a14…... x2 =0.a21a22a23a24…... x3 =0.a31a32a33a34…...
………...
11
对于无限集合，可用下面的例子说明
自然数集合N={0,1,2,...}与其子集S={1,3,…}均 为无限集，且N~S；
可得无限集的一个特性：S⊂N及S~N； 即表明S是N的一个真子集，并且同时S与N等
势； 这种特性在有限集是不可能存在的。
12
集合间的等势关系“~”是个等价关系
证明：令S是个集合族(即“所有集合构成的集合”)， 在S上的等势关系~，满足： ⑴自反性：因为任何集合A，存在双射
27
说明：
• 这种方法称为：康托对角线法 • 对角线法并非康托尔关于实数不可数的第一个证
明，而是发表在他第一个证明的三年后； • 他的第一个证明既未用到十进制展开，也未用到
任何其它数字系统； • 自从该技巧第一次使用以来，在很大范围内的证
明中都用到了类似的证明构造方法。
28
由前面这些定理可知：
实数集比可列集要大； 可列集的基数可表示为0 （Aleph 0，阿列夫零）； 实数集的基数用1或c表示，称作连续统的势。
即f(S)是S的真子集，则S是无限集合，否则S是有 限集合。
9
定理4.1 自然数集N是无限集。
证明：设函数f: N→N，定义为f(x)=2x，显然f是一 一对应，而且f(N)⊂N ，因此N是无限集。
定理4.2 常数集R是无限集。 证明：设函数f: R→R，为
显然f(x)是一一对应的， 而且显然有f(R)⊂R，因 此R是无限的。
xn =0.an1an2an3an4…... ..……..
26
构造一个数b=0.b1b2b3b4…bn……， 其中 ：
于是
b1≠a11 b2 ≠ a22 b3≠a33…
b≠x1, b≠ x2, b≠ x3 ... 因此： b(0,1)
bn≠ ann... b ≠ xn …
但是b这样的形式应该是属于集合(0,1)的，因此产生 矛盾，所以(0,1)是不可数的。
a0，a1，a2，。。。 由此可得一个无限集A’={a0,a1,a2,...} 集合A’为可列集
19
定理4.9 可列集的无限子集仍为一可列集。
证明：设有一可列集A={a0,a1,a2,...}，依次顺序取 一个任意的无限集A’={am0,am1,am2,...}，A’与N一 一对应；
N: 0 1 2 3 4 L bbbbb
无限子集可做进一步划分：可列集和不可列集。
定义4.6 与自然数集N等势的集合称为可列集。
能和自然数集合N建立一一对应关系的集合是可列集； 可排成一列，能一个一个数下来的集合； 也称为可数集。
18
定理4.8 无限集必包含可列集。
证明：
设一无限集A，由A中取出一个元素a0，再从其剩 余部分取出一个元素a1，如此继续进行，可得一 素的个数称为该集合的基数； 满足包含排斥原理。
无限集合
元素无限多，如：自然数集合N、整数集I、实数集R等。
问题：
对于这样的集合有没有基数呢？ 如果有，基数是多少？ 无限集合之间有无大小的差别?
本章主要借助于函数（对应）讨论集合的所谓“大小”问 题。这里用到自然数集合这个重要的概念讨论无限集。
第二个旅游团客人住的房间编号为
5, 52 , 53 ,L , 5n ,L
接着是
7, 72 , 73 ,L , 7n ,L
6
这样不仅安排了无穷多个旅游团的住宿，而且还 空出了很多房间！
无限多个房间可住无穷多个具有无穷多个游客的 旅游团！
对于一个无穷集合，向其中添加有限个元素，甚至 “无穷多个”元素得到的新集合，其势不变
10
例1：证明 N={0,1,2,3,4,…...} 与下列集合等势 A={0,2,4,6,8,…...} B={1,3,5,7,9,…...} C={100,10,102,103,104,,…...}
证： f:NA，f(x)=2x g:NB， g(x)=2x+1 h:NC， h(x)=10x 是双射， 故N与A、B、C等势 可见：无限集合与其真子集等势。
一个集合A，若真子集B ：B⊂A，B与A等势，则A 一定是无限集
7
Hilbert旅馆的内涵
如果把自然数集合中的元素数量记为z， 那么z不管加 上多大的数，乘以多少，它始终是一个无穷，不会变 大或变小。
问题：自然数和平方数谁要更多？
用普通人的眼光来看，前10个数字中不过4和9两个数， 前100个数中也不过10个；
店主人的方法： • #1房的客人移到#2房 • #2房的客人移到#4房 • #3房的客人移到#6房 •… • 所有奇数号的房间全部腾空了，新
的无限多个客人就全住进了旅店。
5
紧接着发生了更为严重的情况，来了无穷多个具有无穷多 名游客的旅游团，怎么办？
第一个旅游团客人按如下房间编号住
3, 32 , 33 ,L , 3n ,L
令M2=M-M1，即M中除去M1后得到的集合， 则M=M1∪ M2， 做另一集合M’={m2,m3,…} ∪M2，显然M⊃M’且M’~M，因此存在如
下一一对应的关系： 对于M的每个mi对应mi+1，对于M中的每个m∈ M2，对应M’中的
m。
16
推论：一集合为无限集的充分必要条件是它包含有 与它等势的真子集。
定义4.2 集合A和集合B的元素间，如果存在一一对 应的关系，则说A和B是等势（Cardinality）的，记 作A~B
说明：
对有限集来说，两集合等势即说明两个集合的元素的 个数相同；
集合的势：Cardinality of Sets
3
Hilbert旅馆
问题：
一旅店有无穷多个房间，各房间编号依次为：
15
证明过程：
构造一个集合M，先从M中任取一个元素m1，这样剩余部分也是 一个集合M-{m1}，并且是无限集；
再从此无限集M-{m1}中任取一个元素m2，剩余部分为M-{m1， m2}也是一个无限集；
• 如此继续，可取出m3,m4,m5,…无限多个元素，则可得到另一个集合 M1={m1,m2,…}；
-1
-2
23
之前出现过了
24
定理4.12 实数集R不是可列集。
思路：首先证明R~(0,1)， 然后证明(0,1)不是可列集。
0
证明： 构造函数f: (0,1) R f(x)=tg(πx-π/2) 显然 f是双射，所以R~(0,1).