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