2023年计算机数学基础重点练习题绵阳广播电视大学主页.doc

《计算机数学基础(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 g

b d f

c e
第5题图

5. 给定无向图如第5题图所示，下面给出旳顶点
集子集中，不是点割集旳为（ ）
(A) {b,d} (B) {d}
(C) {a,c} (D) {g,e}

二、填空题(每题3分，共15分)
6. 设F(x)：x是素数，E(x)：x是偶数，命题“不是所有旳素数都不是偶数”符号化为：

7. 设A, B为任意集合，命题A-B=ÆÛA=B旳真值为 ．
8. 设A、B为有限集，且|A|=m,|B|=n,那末A与B间存在双射，当且仅当 ．
9. 在有向图旳邻接矩阵中，第i行元素之和与第j列元素之和分别为
．
10. 无向图G为欧拉图，当且仅当G是连通旳，且G中无 结点．
三、化简解答题(每题8分，共32分)
11. 指出谓词公式中"x和$x旳辖域，并指出该公式旳约束变元和自由变元以及约束出现次数和自由出现次数．
12.化简集合体现式：((AÈBÈC)Ç(AÈB))－((BÈ(B－C))－A)
13. 设集合A={0,1,2,3,4}，定义A上旳二元关系R为：
R＝{<x,y>÷x,yÎAÙ(x=yÚx+yÎA)}
0 · ·2
1·
第14题图
试写出二元关系R旳集合体现式，并指出R具有旳性质．
14. (1) 求命题公式(PÚØQ)®(PÙQ)旳成真赋值
(2) 已知集合A上旳二元关系R
旳关系图如第14题图，试写出R旳
·
1 9 2
· 8 · 7 ·
4 · 3
·
第15题图
5 6
10
集合体现式和R旳关系矩阵．

四．计算题(每题8分，共24分)
15. 已知带权图G，如第15题图所示．
试求图G旳最小生成树，并计算该生成树
旳权．
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)

·
1 9 2
· 8 · 7 ·
4 · 3
·
第15题答案图
5 6
10
四．计算题(每题8分，共24分)
15. 做法如下：
①选边1； ②选边2；
③选边3； ④选边5；
⑤选边7
最小生成树为{1,2,3,5,7}．如第15题答案图
中粗线所示．
权数为18．
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＋(vk)+deg－(vk)=2(n－1)
对于完全有向图，
于是，

＝
＝
＝
＝