数学试题练习题教案学案课件计算机数学基础离散数学试题(1)
《计算机数学基础》离散数学试题(1)
(210)
1. 命题公式为 ( ) (P,Q),Q
(A) 矛盾式 (B) 可满足式 (C) 重言式 (D) 合取范式
2. 设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是
健壮的”可符号化为 ( )
(A)，,x(C(x),，G(x))(B)，,x(C(x),，G(x))
(C)，，x(C(x),，G(x))(D)，，x(C(x),，G(x))
3.设集合A={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是( )
(A) 1,A (B) {1,2, 3},A
(C) {{4,5}},A (D) ,,A
4. 设A＝{1,2},B={a,b,c},C={c,d}, 则A×(B,C)= ( )
(A) {<1,c>,<2,c>} (B) {
,<2,c>} (C) {,} (D) {<1,c>,}
5. 如第5题图所示各图，其中存在哈密顿回路的图是 ( )
A、, B、, , C、, , D、, , , , , , , , 第5题图 , , , , , , (315)
6. 设集合A={,,{a}}，则A的幂集P(A)=
7. 设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R＝
{,x,y,y,2x,x,A,y,B},那么
－1R＝ a, ,b
8.图G如第8题图所示， f, ,c 那么图G的割点是 e, ,d
第8题图
9. 连通有向图D含有欧拉回路
的充分必要条件是 .
10.设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为
101，， M,,＝，那么R的关系图为 100R,,
,,100，，
(824)
11. 简化表达式(((A,(B,C)),A),(B,(B,A))),(C,A).
12. 设代数系统(R*, :)，其中R*是非0实数集，二元运算:为：,a,b,R, a:b=ab. 试问:
是否满足交换律、结合律，并求单位元以及可逆元素的逆元.
13. 化简布尔表达式a，a,b(c,a，b).
(832)
14. 求命题公式(P,Q),(，P,，Q)的真值表.
1
15.试求谓词公式中，,x,，x,，y的辖域，试,x(P(x),，xQ(x,y),，yR(x,y)),A(x,y)问R(x,y)和A(x,y)中x,y是自由变元，还是约束变元？
16.设R是A＝{1,2}到A＝(a,b,c)的二元关系，R是A到A＝{}的二元关系， ,,,112223
R= {<1,a>,<1,b>,<2,c>}, R={,} 12
试用关系矩阵求R,R的集合表达式. 12
v1 3 v2 12 6 17 图G如第17题图 4 求图G的最小生成树. v v 567 9 9 13 10
v v 875 8 7
v v 4 3
第17题图
(1810199)
18. 证明 (P,Q),((，Q,R),，R),(P,，S)),，S
19. 设G为9个结点的无向图，每个结点的度数不是5就是6，试证明G中至少有5个度数为6的结点，或者至少有6个度数为5的结点.
《计算机数学基础》离散数学试题
之五解答
(215)
1.B 2.D 3. C 4.A 5.C a, (315) ,c 6. {,,{,},{{a}},{,,{a}}} b, 7.{<6,3>,<8,4> } 8.a, f 第10题答案图
9. D中每个结点的入度＝出度.
10. 见第10题答案图.
(824)
11 (((A,(B,C)),A),(B,(B,A))),(C,A)
,(A,(B,(~B,A))),(C,A)（2分）
,(A,(A,B)),(C,A)（4分） ,A,C,~A)（6分）
,,（8分）
12. ,a,b,c,R*, a:b=ab=ba=b:a，可交换； (2分)
(a:b):c=ab:c=abc=a(bc)=a:(bc)=a:(b:c)，可结合. (4分)
易见，单位元为1. (6分)
1－－－－ 对,a,R*, a:a1111,1=aa=1=aa＝a:a，故a的逆元： (8分) ,aa
2
a，a,b(c,a，b)13.
＝ (2分) a，a,b,c,a，a,b
＝ (5分) a，a,b
＝(a，a),(a，b),a，b (8分)
(832)
14.
P Q P,Q ，P ，Q ，P,，Q (P,Q),(，P,，Q)
0 0 0 1 1 1 0
0 1 0 1 0 1 0
1 0 0 0 1 1 0
1 1 1 0 0 0 0
表中最后一列的数中，每对1个数得2分.
15. ,x的辖域： (2分) (P(x),，xQ(x,y),，yR(x,y))
，x的辖域：Q(x,y) (4分)
，y的辖域：R(x,y) (6分)
R(x,y)中的x,y是约束变量，A(x,y)中的x,y是自由变量. (8分)
110，，16. M,, (2分) R,,1001，，
01，，
,, (4分) M,01R2,,
,,00，，
01，，01，，110，，,, M, (6分) 01,R,R,,,,12,,00100，，，，,,00，，
R,R,{,1,,,} (8分) 12
v3 v1 2
6 17 图G的最小生 4 成树， v v 56 如第17题答案图. ,v) 127 首先选对边(v得2分，
再每选对一条边得 v v 87
1分. 5 8 7 v v 4 3
第17题答案图
(181019919)
18.
?，Q,R P （2分）
?，R P (4分)
?，Q ?，?析取三段论
?P,Q P (7分)
3
? ?，?拒取式 ，P
?P,，S P
?，S ?，?析取三段论 (10分)
19. 由第5章定理1(握手定理)的推论，G中度数为5的结点个数只能是0,2,4,6,8五种情况； (3分) 此时，相应的结点度数为6的结点个数分别为9，7，5，3，1个， (6分) 以上五种对应情况(0,9),(2,7),(4,5),(6,3),(8,1)，每对情况，两数之和为9，且满足第2个数大于或等于5，或者第1个数大于或等于6，意即满足至少有度数为6的结点5个，或者至少有度数为5的结点6个, (9分)
4
浙公网安备 33021202002483