离散数学——有限集与无限集(课件)

那么Fk包括所有这样的函数, 其象是包含在B的枚举的前k个元素
组成的集合中; |Fk|=kn。 因为A是有限的, 对每一函数f:A→B存在某
m∈N, 如果取k＞m, 那么f∈Fk; 所以
。 但每一集合Fk
是有限的因而BA是可数的。证毕。
5.1.3 基数c
不是所有无限集都是可数无限的, 下一定理说明需要新的无 限集基数。
。
(b) 设Σ={a,b}, S是Σ上以a带头的有限串集合, 考虑S的基数。 因为
f: Σ*→S, f(x)=ax
是一个双射函数。所以, |S|=|Σ*|=
。
第一个定理叫做三歧性定律。
定理5.2-2(Zermelo) 成立:
A和B是集合,那么下述情况恰有一个
N所
属等价类的名称。
(ii) 要证明一个集合S有基数α, 只需选基数为α的任意集合S′, 证明从S到S′或从S′到S存在一双射函数。选取集合S′的原则是使 证明尽可能容易。
例1 (a) 设E是正偶数集合, 考虑E的基数。因为
f: I+→E, f(x)=2x
是从I+到E的双射函数, 所以, |E|=|I+|=
(b) ｜(0,1)｜=｜［0,1］｜。这两个集合的不同仅在于区间 的两端点; 为了构造从［0,1］到(0,1)的一个双射函数, 我们必须 在(0,1)中找出0和1的象而保持映射是满射的。定义集合A是
, 定义映射f如下:
图 5.1-4
(c) ｜R｜=c。 我们定义一个从(0,1)到R的双射函数如下:
是Ai的枚举; 如果Ai是有限的我们用无限重复枚举。如果Ai= ,
我们置第i行等于第i-1行。这样, 数组包含所有A的元素而无其它
元素。A元素的一个枚举由图5.1-3中的有向路径指定。 从定理

(3)至于p为0即“我期终考了年级不是前 10”时,无论q为1或为0，即无论"我老妈 奖励1000元"或不奖励，都不能说老妈的 话是假的，故善意的认为pq为1均为1
1.1 命题及联结词
定义1.5双条件:当p与q值相同时,pq为1,不同 为0。 称p当且仅当q
“普通老师赚了100万当且仅当他 中了100万的彩票”， 普通老师赚了100万 普通老师买彩票中了100万大奖
故pq为0
1.1 命题及联结词
定义1.4条件式当p是1 ,q是0时,pq为0,即 10为0,其他情况为1。 p称为前件,q称为后件
(1)当p为1即“我期终考了年级前10”
q为0即“我老妈没有奖励1000元” 这时老妈的话为假，即pq为0 (2)当p为1即“我期终考了年级前10” q为1即“我老妈奖励1000元” 这时妈妈的话就对了，即pq为1
由于所有内容(整数，实数，字符，汉字，图片，声 音，视频，网页，……)进入电脑后，全是01组成的字 符串，从而都可以用布尔运算即逻辑运算实现，命题逻 辑成为计算机的基础。
命题逻辑将数学由连续变到离散，由高数进入离散。
Google采用逻辑运算进行搜索：数字之美 吴军 杨圣洪 000100010001110000 两者对应位置与运算。 离散数学 100100000000100001
陈述句(6)的正确性，到2018年12月时能确定的，若届 时建成了则它是对的、为真命题，否为假命题。
1.1 命题及联结词
对错确定的陈述语句称为命题。如：
(7) x与y之和为100，其中x为整数，y为整数 (8)1加1等于10 (7)的对错不确定。当x为50、y为50时是对的，当x为 51、y为52时是错的。 (8)的对错是不确定的，为二进制时正确，当为八进制、 十进制时是错的，因此这两个陈述句不是命题。 (9)青枫峡的红叶真美呀！ (10)动作快点！ (11)你是杨老师吗？ 这三个语句不是陈述语句，因此不是命题。

第四章 有限集与无限集 有限集S的元素的个数称为S的基数，可记为|S|。 自然数集N是无限集。 实数集R是无限集。 基数是与集合的元素数量有关的概念。在有限集中， 基数即是元素的个数，而在无限集中，集合基数就 变得复杂了。理论上讲，无限集中元素数量为无限， 但这太笼统了，因为个数中其浓度与密度是不同的。 如：实数与自然数同为无限个元素，但是实数无限浓 度高于自然数的无限浓度。
有限集 性质1：如果A和B是分离的有限集合，则有 |A∪B|＝|A|＋|B|。
A B
性质2：如果A和B是有限集合，则有 |A∪B|＝|A|＋|B|－|A∩B|。
A B
有限集
性质3：如果A、B和C是有限集合，则有 |A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C| －|B∩C|＋ |A∩B∩C|。
无限集的这个特性可以用来区分有限集和无限集。 性质2：一集合为无限集的充分必要条件是有与其等 势的真子集。
无限集的性质
定义：一集合若存在与其等势的真子集称为无限集； 否则，称为有限集。
定义：凡与自然数集N等势的集合称为可列集。
也可以将有限集与可列集合称为可数集，
故可列集也可称为可数无限集。
性质：可列集的无限子集仍为一可列集。
A C
B
有限集
例：120个学生中有100个学生至少要学法、德、英三 种语言中的一种，假定有65人学法语，45人学德语， 42人学英语，20个人学法语和德语，25人学法语和 英语，15人学德语和英语，请问同时学三种语言的 有多少人？ 解：令A、B、C表示学法语学、德语和英语的人数 100＝65＋45＋42－20－25－15＋|A∩B∩C| 所以 |A∩B∩C|＝8。
可列集是无限集中的最小集合。
无限集的性质 例如：整数集I是可列集。 N={0,1, 2, 3, 4, 5, 6……}

性质：设º 是A上的一个n元运算，S1、S2 A，º 对 S1、S2均封闭，an S1∩S2, ∵ a1,a2…an S1 且运算º在S1上封闭 ∴ º a1,a2…an ） S1，又∵ a1,a2…an S2 且 （ 运算º在S2上封闭 ∴ º a1,a2…an ） S2 （ º a1,a2…an) S1∩S2， ( ∴ º对S1∩S2是封闭的 三、二元运算的若干性质 (设º 和*是A上的两个二元运算) 1 可交换性：a1º a2=a2º (N上的加、乘运算) a1 2 可结合性: (a1º a3=a1º a3) a2)º (a2º (N上的加、乘运算)
14
3 可数集的基数≤任何无限集的基数 ∵任何一个无限集均包含一个可数集
∴无限集的基数中的最小者是可数集 4 可数集的基数<不可数集的基数
即‫< 0א‬
‫1א‬
对任何集合A，有|A|<|2A| ∴不存在最大基的集合，即无论一个集合的基 数多么大，一定有一个更大基数的集合存在。
15
第四章 代数系统
13
1 定义：设A ’ B(不等势)，但A与B的一个 真子集等势，则称A的基数小于B的基数，记为 #A<#B Ne={2,4,6,…} , N={1,2,3,…} NeN #Ne<#N (×) 2 性质：若A1A，B1B，AB1，BA1， 则AB 证明： ∵ AB1，而B1B ∴|A|≤|B| 又∵ BA1 ，且A1A ∴|B| ≤|A| ∴|A|=|B| ∴ AB
4 集合A、B均可数， A∩B= ，则A∪B可数 (正整数∪负整数)
6
证明：设A={a1, a2, a3, …}, B={b1, b2, b3, …} ∵ A∩B= ∴ A∪B= {a1,b1,a2, b2, a3, b3,…} ∵ A∪B 可排成一个序列 ∴ A∪B可数