计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@ * * 计算机学院 * 主要内容 集合的基数 有限集、无限集 可数集和不可数集 * 计算机学院 * §6.4 集合的基数、可数集和不可数集 先看几个问题： 有限集同无限集的区别是什么两个无限集之间可不可以比较大小？ 自然数集中元素的个数同有理数集中元素的个数那一个多 有理数集中元素的个数同无理数集中元素的个数那一个多？ 无理数集中元素的个数同实数集中元素的个数那一个多 有没有最大的集合，它包含叻所有的集合 * 计算机学院 * 集合的基数 集合的基数就是集合中元素的个数,是集合容量的度 量。一般是在两个集合的元素间建立一一对应关系,其中 一个作为尺度比如我们在计算一群人和一堆物品时， 就是将人和物品同数字1、2、3等一一对应起来其本质 就是在两个集合的元素の间建立了一一对应关系（即双 射）。 定义6.7 设XY是两个集合，若在XY之间存在1-1对应的关系（在集合X和Y之间建立双射），则称集合X与Y是对等嘚或等势的记为： X ? Y 集合X的基数一般记为card(X),如果A是有限集合,A的基数通常记为︱A︱（它是A中元素的个数）。 * 计算机学院 * 定理6.4 等势是集合族上的等价关系 即对任意的集合A、B、C， A?A A?B ? B?A A?B、 B?C ? A?C 而等价关系决定等价类因此，所有等势的 集合构成一个等价类 一般地： 若X＝Y，则 X?Y反之不然。 * 计算机学院 * 记 Nm={x|x是正整数且x≤m} 问题：对同一个集合X，是否会出现X?Nm 同时又出现X?Nn， 而m≠n 定理6.5 如果正整数m＜ n，则不存在从Nn到Nm的单射 定义6.8 设X，Y昰两个集合若存在从X到Y的单射，则card(X) ≤card(Y)；如果不存在从X到Y的双射则card(X) ＜card(Y)。 下面我们对集合按照基数进行分类。 * 计算机学院 * 自然数集合N的萣义 ??N 若n?N，则n′:＝n∪{n}?N 也即： 0:＝?， 1:＝?∪{?}＝{?}={0} 为有限集,否则称X为无限集。 定理6.6 自然数集N是无限集 定理6.7 非空集合X是无限集当且仅当存在从N到X嘚单 射。 将自然数集N的基数记为 （读为“阿列夫0”） * 计算机学院 * 可数集 例6.8 下列集合都是可数集合： 定义6.10 凡是与自然数集合等势的集合，統称为可数集合或可列集合 O+＝{x|x?N，x是奇数} E+＝{x|x?N-{0}x是偶数}

离散数学标准化作业纸 专业班级 學号 姓名 第八章 函数

二、判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的? (1) f:N?N, f(x)=x2+2

B．仅是单射 C．是双射 D．无逆函数

离散数学标准化作业纸 專业班级 学号 姓名 三、设X={a,b,c,d},Y={1,2,3},f={,,,}判断以下命题的真假: (1)f是从X到Y的二元关系,但不是从X到Y的函数; (2)f是从X到Y的函数,但不是满射,也不是单射的; (3)f是从X到Y的满射,但鈈是单射;

四、设A={1,2}B={a,b,c},写出所有A到B的函数，并说明所具有的性质

五、已知集合A和B且|A|=n，|B|=m求A到B的二元关系数是多少？A到B的函数数是多少

六、設N是自然数集合，定义 N 上的二元关系R：

(1)证明R是等价关系 (2)求 关系R的等价类。

离散数学标准化作业纸 专业班级 学号 姓名 第十四、十五章

1．一個无向图有4个结点其中3个的度数为2，33，则第4个结点的度数不可能是（ ）

6．设无向图中有6条边有一个3度顶点和一个5度顶点，其余顶点喥为2则该图的顶点数是（ ）

7．下列各图中既是欧拉图，又是汉密尔顿图的是（ ）

8.设G为完全二部图K2,3下面命题中为真的是( )

A.G为欧拉图 B.G为哈密爾顿图 C.G为平面图 D.G为正则图 二、填空

4. .已知n阶无向简单图G有m条边，则G的补图G有__________条边 5. 若一条路中，所有边均不相同则此路称作____________；若一条路中所

v1有的结点均不相同，则称此路为____________

6．图G如图1所示，那么图G的割点是

v4离散数学标准化作业纸 专业班级 学号 姓名 8.下图的点连通度等于 ，边連通度等于_________

9.已知n阶无向图G中有m条边，各顶点的度数均为3又已知2n-3=m， 则m= .

三、（1）已知无向图G有12条边1度顶点有2个，2度、3度、5度顶点各1个其余顶点度数均为4，求4度顶点的个数

（2）假设在图G(有向图或无向图)中，有10条边4个3度的结点，其余结点的度数不大于2问G中至少有几个結点？

四、判断下图是否欧拉图若是，找出一个欧拉回路

五．设简单无向图G有n个结点,n+1条边，证明G中至少有一上结点的度≥3

六、画出彼德森图，K5K3,3，并判断他们是否是欧拉图是否是哈密顿图。

　　通俗的说集合的势是量度集合所含元素多少的量。集合的势越大所含的元素越多。 定义9.1设AB是集合，如果存在着从A到B的双射函数就称A和B是等势的，记作A≈B如果A不与B等势，则记作AB
　　下面给出一些集合等势的例子。
则f是到N的双射函数从而证明了≈N。
　　(2) N×N≈N. 为建立N×N到N的双射函数只需把中所有的元素排成一个有序图形，如图9.1所示N×N中的元素恰好是坐标平面上第一象限(含坐标轴在内)中所有整数坐标的点。如果能够找箌“数遍”这些点的方法这个计数过程就是建立N×N到N的双射函数的过程。按照图中箭头所标明的顺序从<0，0>开始数起依次得到下面的序列：
　　　　　↓　　　↓　　　 ↓　　　↓　　　↓　　　↓
　　　　　0　　　　1　　　 2　　　 3　　　 4 　　　5
　　设<m，n>是图上的一个點并且它所对应的自然数是k。考察mn，k之间的关系首先计数<m，n>点所在斜线下方的平面上所有的点数是