例：
1、设A,B是两个集合,B≠￠,试证:若A×B=B×B, 则A=B。
2、设A,B,C,D是任意四个集合，证明： （A∩B)×(C∩D)=(A×C)∩(B×D)
3、某班30名学生中学英语有7人，学日语有5人，这两科都选有3人，问两科都不选的有多少人？
(|AC∩BC|+|A∪B|=30, |AC∩BC|=21人)
4、令N={1,2,3,…}，S:N→N，则
(1)?n?N,S(n)=n+1,Ｓ称为自然数集N上的后继函数。
(2)S(1)=1,?n?N,S(n)=n-1,n≥2,Ｓ称为自然数集N 上的前仆函数。
5、设f:N×N ?N,f((x,y))=xy。则 （1）说明f是否是单射、满射或双射？ （2）求f(N×{1}),f-1({0})。
(1,4)≠(2,2),f((1,4))=f((2,2))=4；
?y?N,f((1,y))=1·y=y,任一元都有原象； [f不是单射,f是满射]
f(N×{1})={n·1|n ?N}=N；
f-1({0})={(x,y)|xy=0}={N×{0}}?{{0}×N}。
6、设R、I、N是实数、整数、自然数集合，下面定义映射f1,f2,f3,f4,f5,f6，试确定它们的性质。 （0 ?N） （1）f1:R?R,f1(x)=2x； （2）f2:I?N,f2(x)=|x|；
f1单射，不是满射。f2不是单射，满射。 （3）f3:N?N,f3(n)=n(mod3)； （4）f4:N?N×N,f4(n)=(n,n+1)；
f3不是单射，不是满射；f4单射，不是满射。 （5）f5:R?R,f5(x)=x+2；
（6）f6:R?R,f6(x)=x2,x≥0,f6(x)=-2,x<0；
1
f5是双射(单射,满射)；f6不是单射,不是满射。
7、证明：在52个正整数中，必有两个整数，使得这两个整数之和或差能被100整除。
8、已知m个整数a1，a2，…，am，试证：存在两个整数k,l,0?k?i?m，使得ak+1+ak+2+…+al能被m整除。
9、设N={1,2,3,…},试构造两个映射f,g:N?N，使得fg=IN，但gf?IN。
10、设N={1,2,3,…},试构造两个映射f,g:N?N，使得gf=IN，但fg?IN。
11、设f:X?Y，证明：
(1)f是单射??F?2X，f–1(f(F))=F； (2)f是满射??E?2Y，f(f–1(E))=E。
12、设f:X?Y，则
(1)若存在唯一的一个映射g:Y?X,使得gf=IX,则f是可逆的吗？ (2)若存在唯一的一个映射g:Y?X,使得fg=IY,则f是可逆的吗？
13、(1)设X={1,2,3},Y={a,b},求X到Y满射的个数; (2)设X={1,2,3,4,5},Y={a,b},求X到Y的满射的个数; (3)设X={1,2,…,n},Y={a,b}，求X到Y的满射的个数;
(4)设X={1,2,…,n},Y={y1,y2,…,ym},n?m,若f:X?Y，求X到Y的满射的个数。
14、设X是一个集合，|X|＝n，求：
(7) X上既不是自反的也不是反自反的关系有多少？
2
(9) X上自反的或对称的关系有多少？
(12)X上既不是对称的也不是反对称的关系有多少？
15、设 A={1,2,3}，R是A的幂集2A上的二元关系且 R={(a,b)|a∩b≠￠}，则R不满足下列哪些性质？为什么？[aRb ?a∩b≠￠] (1) 自反性 (2) 反自反性 (3) 对称性 (4) 反对称性 (5) 传递性
16、设R是复数集合C上的一个二元关系且满足
xRy?x-y=a+bi，a,b为非负整数，试确定R的性质。
17、设R为X上的二元关系，显然若R＝￠，则R是反自反的、对称和传递的；但若R≠￠且R是反自反的和对称的，则R不是传递的。
此题可变形为：但若R≠￠且R是反自反的和传递的,则R是反对称的。
18、设R是集合A上的反对称关系，则t(R)一定是反对称的吗？
19、设R是集合A上的一个自反的和传递的关系；
T是A上的一个关系，使得(a,b)∈T?(a,b)∈R且 (b,a)∈R。证明：T是A上的等价关系。
20、设R是A上的二元关系，S={(a,b)|?c∈A,使得(a,c)∈R且(c,b)∈R}。证明：若R是等价关系，则S也是等价关系。 说明：本题可以证明R＝S。
21、设{A1,A2,…,An}是集合A的划分，若Ai∩B≠φ，1≤i≤n，证明：{A1∩B,A2∩B,…,An∩B}是集合A∩B的划分。
3
22、设S={1,2,3,4},并设A＝S×S,在A上定义关系R为: (a,b)R(c,d)?a+b=c+d。
证明:(1) R是A上的等价关系；(2) 计算A/R。
23、设集合A={a,b,c,d,e}上关系R定义如下：
R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e), (c,c),(c,e),(d,d),(d,e),(e,e)}。 1.写出R的关系矩阵； 2.验证(A,R)是偏序集; 3.画出Hasse图; 4.若A上的关系如下：
R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),
(c,c), (c,d),(c,e),(d,d),(d,e),(e,e)}，则有如何？
24、用对角线方法证明：若A是可数集，则2A是不可数集。
25、用对角线方法证明：所有0,1的无穷序列所构成的集合是不可数集。
26、设T是一棵树,T有3个度为3顶点,1个2度顶点，其余均是1度顶点。则 （1）求T有几个1度顶点？
（2）画出满足上述要求的不同构的两棵树。
27、设T是一棵树且△(T)≥k，证明T中至少有k个度为1顶点。
28、设G是一棵树且Δ(G)≥k，证明：G中至少有k个度为1的顶点。
4
29、一棵树T有n2个度为2的顶点，n3个度为3的顶点，…，nk个度为k的顶点，则T有多少个度为1的顶点？
30、如图所示是彼德森图，回答问题：
（1）图是否是自补图？（2）图是否是偶图？
（3）图是否是欧拉图？（4）图是否是哈密顿图？ （5）图是否是平面图？（6）图的色数是多少？
31、证明：若每个顶点的度数大于等于3时，则不存在有7条边的平面连通图。 (等价命题：证明：不存在7条棱的凸多面体)
32、设G是顶点p≥11的平面图，证明：G的补图Gc是非平面图。
(设G是顶点p≥11的图，证明：G与G的补图Gc至少有一个是非平面图。)
33、设G是边数q<30的平面图,证明:G中存在顶点v， 使得degv≤4。
34、设G是(p,q)平面连通图，f个面，证明： （1）若p≥3，则f≤2p-4；
（2）若δ(G)=4，则G中至少有6个顶点的度数 小于等于5。
证: (1) p-q+f=2,q≤3p-6,从而有:f≤2p-4。
(2) 假设G中至多含有5个顶点的度数≤5，又δ(G)=4,所以5×4+6×(p-5)≤2q ，得q≥3p-5。
而q≤3p-6，从而有：3p-5≤3p-6，矛盾。
故假设不成立，因此G中至少有6个顶点的度数≤5
35、把平面分成n个区域，每两个区域都相邻,问n最大为多少？
证：在每个区域放一个顶点，当两区域相邻时，就在相邻的两个顶点间连一条边，如此构造了一个平面图且是完全平面图，而最大的完全平面图为K４，所以n最大为4。
36、证明:当每个顶点的度数大于等于3时，不存在有7条边的简单连通平面图。 证：设G=(n，m)为简单连通平面图，有r个面。若m=7，由欧拉公式知n+r=m+2=9
5