《计算机数学基础》离散数学试题.docVIP

《计算机数学基础(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)＝ ( ) 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((((((的真值为 ． 8. 设A、B为有限集，且((((m,((((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)} 试写出二元关系R的集合表达式，并指出R具有的性质． 14. (1) 求命题公式(P((Q)((P(Q)的成真赋值 (2) 已知集合A上的二元关系R 的关系图如第14题图，试写出R的 集合表达式和R的关系矩阵． 四．计算题(每小题8分，共24分) 15. 已知带权图G，如第15题图所示． 试求图G的最小生成树，并计算该生成树 的权． 16. 设R是实数集，在R上定义二元运算*，(x,y(R，定义 x*y=x+y+2xy 试说明*是否满足结合律、交换律？是否存在单位元？若存在请求出． 17. 已知(L，*，()是格，且二元运算*和(满足分配律，(a,b,c(L，化简表达式 《计算机数学基础(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)