《计算机数学基础(1)》离散数学试题
一、单项选择题(每小题2分，共10分)
1. 命题公式P?(P??P)的类型是（） （A）永真式（B）矛盾式
（C）非永真式的可满足式 （D）析取范式 2. 设个体域是整数集合，P代表?x?y((x?y)?(x?y?x))，下面4个命题中为真的是() (A) P是真命题(B) P是假命题
(C) P是一阶逻辑公式，但不是命题(D) P不是一阶逻辑公式 3. 设A, B, C都是集合，如果A?C＝B?C，则有( ) (A) A＝B (B) A?B (C) 当A－C＝B－C时,有A=B (D) 当C=U时, 有A?B
矚慫润厲钐瘗睞枥庑赖。 4. 设集合A＝{?，a}，则P(A)＝ ( )
(A){?,{a},{?,a}}(B){{?},{a},{?,a}}
(C){?,{?},{a},{?,{a}}},A}(D){?,{?},{a},{?,a}} 5. 给定无向图如第5题图所示，下面给出的顶点 集子集中，不是点割集的为（ ） (A) {b,d} (B) {d} (C) {a,c} (D) {g,e}
a g
b d f
c e 第5题图
二、填空题(每小题3分，共15分)
6. 设F(x)：x是素数，E(x)：x是偶数，命题“不是所有的素数都不是偶数”符号化为：
7. 设A, B为任意集合，命题A?B??????的真值为．
8. 设A、B为有限集，且????m,????n,那末A与B间存在双射，当且仅当． 9. 在有向图的邻接矩阵中，第i行元素之和与第j列元素之和分别为 ．
10. 无向图G为欧拉图，当且仅当G是连通的，且G中无结点． 三、化简解答题(每小题8分，共32分)
11. 指出谓词公式?x((P(x)?Q(x,y))??xR(x))?S(x)中?x和?x的辖域，并指出该公式的约束变元和自由变元以及约束出现次数和自由出现次数． 聞創沟燴鐺險爱氇谴净。 12.化简集合表达式：((A?B?C)?(A?B))－((B?(B－C))－A)
13. 设集合A={0,1,2,3,4}，定义A上的二元关系R为： R＝{
试写出二元关系R的集合表达式，并指出R具有的性质．残骛楼諍锩瀨濟溆塹籟。 14. (1) 求命题公式(P??Q)?(P?Q)的成真赋值 0 ? ? 2
1? (2) 已知集合A上的二元关系R
第14题图 的关系图如第14题图，试写出R的
集合表达式和R的关系矩阵．酽锕极額閉镇桧猪訣锥。 ?
1 9 2
? 8 ? 7 ?
四．计算题(每小题8分，共24分) 5 6 4 10 ? 3 15. 已知带权图G，如第15题图所示．
? 试求图G的最小生成树，并计算该生成树
第15题图
1
的权． 16.设R是实数集，在R上定义二元运算*，?x,y?R，定义
x*y=x+y+2xy
试说明*是否满足结合律、交换律？是否存在单位元？若存在请求出． 17. 已知(L，*，?)是格，且二元运算*和?满足分配律，?a,b,c?L，化简表达式
((a*b)?(a*c))* ((a*b)?(b*c))
五、证明题(第18题10分，第19题9分) 18. 证明命题公式(P?(Q??R))??P?Q与?（P??Q）等值． 19.证明在任何有向完全图中，所有结点的入度平方之和等于所有结点的出度平方之和． 《计算机数学基础(1)》离散数学试题答案 一、单项选择题(每小题2分，共10分)
1. A 2. B 3. C 4. D 5. A 二、填空题(每小题3分，共15分)
6. ??x(F(x)??E(x))或?x（F（x）?E（x）） 7. 0 8. m=n彈贸摄尔霁毙攬砖卤庑。 9. 结点vi的出度与结点vj的入度 10. 奇数度 三、化简解答题(每小题8分，共32分)
11. ?x的辖域为：(P(x)?Q(x))??xR(x) ?x的辖域为：R(x)
x既是约束变元，也是自由变元，约束出现3次，自由出现1次．y是自由变元，自由出现1次．.
12. ((A?B?C)?(A?B))－((B?(B－C))－A)
＝(A?B)－(B－A） =(A?B)?(～B?A) =A?(B?～B) =A??=A
13. 由题设，
R＝IA?{<0,1>,<1,0>,<0,2>,<2,0>,<0,3>,<3,0>,
<0,4>,<4,0>,<1,2>,<2,1>,<1,3>,<3,1>}
易知，R具有自反性和对称性．
14. (1) (P??Q)?(P?Q)?(?P?Q)?(P?Q)?(?P?P)?Q?Q 可见(P??Q)?(P?Q)的成真赋值为(0,1)，(1,1)． (2) R?{?0,0?,?2,2?,?0,2?,?2,0?}
?101??
MR??000????101??四．计算题(每小题8分，共24分)謀荞抟箧飆鐸怼类蒋薔。 ? 15. 做法如下：
1 9 2 ①选边1； ②选边2；
? 8 ? 7 ? 5 6 ③选边3； ④选边5；
4 10 ? 3 ⑤选边7
? 最小生成树为{1,2,3,5,7}．如第15题答案图
第15题答案图
中粗线所示．
权数为18．
2
16.?x,y,z?R，
①(x*y)*z=(x+y+2xy)*z=(x+y+2xy)+z+2(x+y+2xy)z
=x+(y+z+2yz)+ 2x(y+z+2yz)=x*(y*z)
可结合.
②x*y=x+y+2xy=y*x 可交换.
③ 设单位元为e，?x?R, e*x=x*e=x+e+2xe=x，由x的任意性,得e=0?R,单位元 为0.
17. ((a*b)?(a*c))*((a*b)?(b*c))
＝(a*b)? ( (a*c)* (b*c))(分配律) =(a*b) ?((a*b)*c) (幂等律) =a*b(吸收律)
五、证明题(第18题10分，第19题9分)
18. (P?(Q??R))??P?Q?(?P?(Q??R))??P?Q ?(?P??P?Q)?(Q??P?Q)?(?R??P?Q) ?(?P?Q)?(?P?Q)?(?P?Q??R) ??P?Q
??(P??Q) 19. 假设完全有向图D有n个结点．对任意结点vk?D, 有 deg＋(v－
k)+deg(vk)=2(n－1) n对于完全有向图，?ndeg?(vk)?k?1?deg?(vk)?n(n?1)
k?1于是，
?nn(deg?(v2k))?n?1)?deg?(vk))2
k?1?(2(k?1n ＝
?(4(n?1)2?4(n?1)deg?(v?2k))?(deg(vk))
k?12nn ＝4n(n?1)?4(n?1)?deg?(vk)?(deg?(vk))2
k?1?k?1 ＝4n(n?1)2?4(n?1)?n(n?1)??n(deg?(vk))2
k?1 ＝?n(deg?(v2k))
k?1
3
《计算机数学基础》离散数学考试
