《离散数学》综合复习资料
一、判断题
1．如果有限集合A有n个元素，则其幂集p(A)有R2也是反自反的。
3．“这朵玫瑰花多美丽呀！”是一个命题。
4．A、B、C是任意集合，如果A(B及B(C，则A(C。
5．“中国有四大发明”是一个命题。
6．对任意集合A，A。
7．集合A的一个划分确定A的元素间的一个等价关系。
8．含有幺元的半群为独异点。
9．每个图中，边数等于结点度数总和两倍。
二、基本题
1.将下列命题符号化
（1）4是偶数和合数。
（2）如果天不下雨，王荣就去图书馆。
（3）所有人都是要死的。
2.求命题公式P((P(Q)的主合取范式。
3.举出A={a,b,c}上的二元关系R和S满足：
（1）R是自反的、对称的；
（2）S是对称的、传递的。
4.已知图G的邻接矩阵M如下，结点集为{v1,v2,v3,v4,v5}，试画出该图，并求V2的入度d-(V2)和出度d+(V2)。
M=
5.将下列命题符号化
（1）如果张三和李四都不去，她就去。
（2）今天要么是晴天，要么是雨天。
（3）每一个有理数都是实数。
6.求命题公式((P(Q)的主析取范式。
7.举出A={a,b,c}上的二元关系R和S满足：
（1）R既不是自反的又不是反自反的；
（2）S既不是对称的又不是反对称的。
8.已知图G的邻接矩阵M如下，结点集为{v1,v2,v3,v4,v5}，试画出该图，并求V2的入度d-(V2)和出度d+(V2)。
M=
9.举出A={a,b,c}上的二元关系R和S满足：
（1）R是自反的、传递的；
（2）S是反自反的、传递的。
10.设集合为A={1，3，4，12，24}，其上的偏序关系为整除，试列出相应的关系并画出哈斯图。
11.二元运算ab=a+b-ab在实数集R上是否满足交换律和结合律?
12.设集合为A={1，2，5，10，20}，其上的偏序关系为整除，试列出相应的关系并画出哈斯图。
13.二元运算ab=a+b-3在实数集R上是否满足交换律和结合律?
三、证明题
1.试证明：A(B,((BC)((A
2.设R,S是A上的等价关系，证明R(S也是A上的等价关系。
3.设是一群，。定义：，。证明也是一群。
4.试证明：A((B(C),(DA,B(D(C
5.在任何有向图中，所有结点的入度之和等于所有结点的出度之和。
6.试证明：(AB,C((B(A((C
7.设R，S是A上的相容关系，证明R(S也是A上的相容关系。
8.设G=有11个结点，m条边，证明G或者其补图G’是非平面图。
9.设f是从A到B的一个函数，定义A上的关系R：aRb当且仅当f(a)=f(b)，证明R是A上的等价关系。
10.试证明代数系统
a b c d a a b c d b b a d c c c d a b d d c b a 11.在有6个结点12条边的连通简单平面图中，每个面由3条边围成。
《离散数学》综合复习资料参考答案
一、判断题
题目 1 2 3 4 5 6 7 8 9 答案 错误 正确 错误 正确 正确 错误 正确 正确 错误 二、基本题
1.答案：
（1）（p∧q）
（2）（p→q）
（3（((x)(R(x)(Q(x))）
2.答案：
解：原式(P(((P(Q)
((P(((Q(Q))(((P(Q)
((P((Q)((P(Q)(((P(Q)
3.答案：
解：此题答案不唯一
（1）R={,,,,}
（2）S={,,}
4.答案：
解：该矩阵不对称，所以G是有向图，如右图。
d-(V2)=2，d+(V2)=1
5.答案：
（1）（（(P((Q）(R）
（2）（PQ）
（3）(((x)(R(x)(Q(x)))
6.答案：
解：((P(Q)
((((P(Q)
(P((Q
7.答案：
解：此题答案不唯一
（1）R={,}
（2）S={,}
8.答案：
解：该矩阵不对称，所以G是有向图，如右图。
d-(V2)=1，d+(V2)=2
9.答案：
解：此题答案不唯一
（1）R={,,}
（2）S={,,}
10.答案：
解：RA={<1,1><1,3><1,4>,<1,12>,<1,24>,<3,3>,<3,12>,<3,24>, <4,4>,<4,12>,<4,24>,<12,12>,<12,24>,<24,24>}
11.答案：
解：1）交换律：ab=a+b-ab=b+a-ba=ba所以满足交换律
2）结合律：(ab)c=(a+b-ab)c=a+b-ab+c-(a+b-ab)c
=a+b+c-ab-ac-bc+abc
a(bc)=a(b+c-bc)=a+b+c-bc-a(b+c-bc)
=a+b+c-ac-ab-bc+abc
所以
所以满足结合律。
12.答案：
解：RA={<1,1><1,2><1,5>,<1,10>,<1,20>,<2,2>,<2,10>, <2,20>,<5,5>,<5,10>,<5,20>,<10,10>,<10,20>,<20,20>}
13.答案：
解：1）交换律：ab=a+b-3=b+a-3=ba所以满足交换律
2）结合律：(ab)c=(a+b-3)+c–3=a+b+c-6
a(bc)=a+(b+c-3)-3=a+b+c-6
所以
所以满足结合律。
三、证明题
1.答案：
证明：(1)A(B P
(2)A P(附加前提)
T(1),(2)I
(4)((BC) P
(5)(B((CT(4)E
(6)(B T(6)I
(7)B((B(矛盾T(3),(6)I
2.答案：
证明：a)自反性：对任意a(A，因为(A,(S，
所以(R(S，即R(S具有自反性。
b)对称性：对任意a,b(A，如果有(R(S，则(R且(S。
因为R,S是等价关系，所以具有对称性，
所以(R且(S。
所以(R(S，即R(S具有对称性。
c)传递性：对任意a,b,c(A，若有,(R(S
则,(R且,(S
则因为R,S是等价关系，所以具有传递性，
所以(R且(S
所以(R(S，即R(S具有传递性。
所以R(S是A上的等价关系。
3.答案：
证明：显然是上的二元运算（即满足封闭性），要证是群，需证结合律成立，同时有幺元，每个元素有逆元。
（1），有
所以运算是可结合的。
（2）是的幺元。事实上，，有
；
（3），是在中的逆元。事实上，
由以上证明，是群。
4.答案：
证明：(1)D P（附加前提）
(2)(DAP
(3)A T(1)(2)I
(4)A((B(C)P
(5)(B(C)T(3)(4)I
(6)B P
(7)C T(5)(6)I
(8)D(C CP
5.答案：
证明：因为有向图中，
每条有向边必对应一个入度和一个出度，
所以，结点入度之和等于边数，出度之和也等于边数，
因此，所有有入度之和等于出度之和。
6.答案：
证明：(1)(AB P
(2)A(B T(1)E
(3)C((B P
(4)(C(B T(3)E
(5)(B(C T(4)E
(6)B((C T(5)E
(7)A((C T(2)(6)I
7.答案：
证明：a)自反性：对任意a(A，因为(A,(S，
所以(R(S，即R(S具有自反性。
b)对称性：对任意a,b(A，如果有(R(S，则(R并且(S。
因为R,S是相容关系，所以具有对称性，
所以(R并且(S。
所以(R(S，即R(S具有对称性。
所以R(S是A上的相容关系。
8.答案：
证明：设G’中有m’条边，则m+m’=11(11-1)/2=55。
若G,G’均为平面图，则m<=311-6=27，m’<=311-6=27
则m+m’<=27+27=54与上矛盾，
所以G或G’是非平面图。
9.答案：
证明：a)自反性：对任意a(A，f(a)=f(a)，所以aRa，即R是自反的。
b)对称性：对任意a，b(A，若aRb，即f(a)=f(b)，
即f(b)=f(a)，故bRa，即R是对称的。
c)传递性：对任意a，b，c(A，若aRb，bRc，即f(a)=f(b)，f(b)=f(c)
即f(a)=f(b)=f(c)，故aRc，即R是传递的。
所以R是A上的等价关系。
10.答案：
证明：
由运算表可知运算满足封闭性
由运算表可知a为幺元
所以
11.答案：
证明：由欧拉公式v-e+r=2知：6-12+r=2解得r=8。
又每个面至少由三条边围成，所以212>=3r得r<=8。
因此每个面恰由三条边围成。
01000
00010
10000
00001
01000
01110
00011
00000
00001
10000
|
|
