P113习题

25.设X?{1,2,3},Y?{1,2},S?{f|f:X?Y}。?是S上的二元关系：

?f,g?S,f?g?Im(f)?Im(g)。

证明：（1）?是S上的等价关系；（2）求等价类的集合。

26. 设X?{1,2,3},Y?{1,2},S?{f|f:X?Y}。?是S上的二元关系：

?f,g?S,f?g?f(1)?f(2)?f(3)?g(1)?g(2)?g(3)。

证明：（1）?是S上的等价关系；（2）求等价类数。

27. 设X?{1,2,3},Y?{1,2},S?{f|f:X?Y}。?是S上的二元关系：

?f,g?S,f?g?{f?1(y)|y?Y}?{g?1(y)|y?Y}。

证明：（1）?是S上的等价关系；（2）求等价类。

11

?1228.由置换????36354568127?8上的一个关系?,8}?确定了X?{1,2,7?4?:i,j?X,i?当且仅当ji与j在?的循环分解式中的同一循环置换中，证明：?是X上的等价关系，求X/?。

29．给出X＝{1,2,3,4}上两个等价关系R与S，使得R?S不是等价关系。

R是等价关系?若(a,b)?R且(a,c)?R，30．设R是X上的一个自反关系，证明：

则(b,c)?R。

35．设X是一个集合，X?n，试求：

（1）X上自反二元关系的个数；（2）X上反自反二元关系的个数； （3）X上对称二元关系的个数；（4）X上自反或对称关系的个数。

P125习题

38.存在一个偏序关系?，使得(X,?)中有唯一的极大元素，但没有最大元素？若有请给出一个具体例子；若没有，请证明之。

39．令S＝｛1，2，…，12｝，画出偏序集（S,|）的Hass图， 其中“|”是整除关系，它有几个极大（小）元素？列出这些 极大（小）元素。

12

第四章 无穷集合及其基数习题

1. 设A为由序列a1,a2,?,an,?

的所有项组成的集合，则A是否是可数的？为什么？

2.证明：直线上互不相交的开区间的全体所构成的集合至多可数。

3.证明：单调函数的不连续点的集合至多可数。

4.任一可数集A的所有有限子集构成的集族是可数集合。

5．判断下列命题之真伪：

(1)若f:X?Y且f是满射，则只要X是可数的，那么Y是至多可数的； (2)若f:X?Y且f是单射，那么只要Y是可数的，则X也是可数的； (3)可数集在任一映射下的像也是可数的；

7. 设?为一个有限字母表，?上所有字（包括空字）之集记为??。证明??是 可数集

13

P142习题

1.找一个初等可数f(x)，使得它是(0,1)到实数R的一一对应。

4. 利用康托的对角线法证明2A是不可数集，其中A为可数集。

5．利用康托的对角线法证明所有的0，1的无穷序列是不可数集。

14

第六章 图的基本概念

P206习题

1．画出具有4个顶点的所有无向图(同构的只算一个)。

2．画出具有3个顶点的所有有向图(同构的只算一个)。

3．画出具有4个、6个、8个顶点的三次图。

4．某次宴会上，许多人互相握手。证明：握过奇数次手的人数为偶数(注意，0是偶数)。

P209习题

1．设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹)，则G中是否有圈？

2．证明：一个连通的(p，q)图中q≥p-1。

3．设G是一个（p，q）图，且q?(p?1)(p?2)/2，则G是连通的。

15