离散数学试题答案.doc

1 《计算机数学基础》离散数学试题一、单项选择题( 每小题 2 分,共 10分) 1. 命题公式 QQP??)( 为() (A) 矛盾式(B) 可满足式(C) 重言式(D) 合取范式 (x ):x 是国家级运动员,G(x ):x 是健壮的, 则命题“没有一个国家级运动员不是健壮的”可符号化为() ))()(()A(xGxCx????))()(()B(xGxCx????))()(()C(xGxCx????))()(()D(xGxCx???? 3. 设集合 A ={{1,2,3}, {4,5}, {6,7,8}} ,则下式为真的是() (A) 1?A (B) {1,2, 3}?A (C) {{4,5}} ?A (D) ??A = {1,2}, B ={a,b,c },C ={c,d },则A×(B?C )=() (A) {<1, c >,<2, c >} (B) {<c ,1>,<2, c >} (C) {<c ,1>< c ,2>,} (D) {<1, c >,< c ,2>} 5. 如第 5 题图所示各图,其中存在哈密顿回路的图是() 二、填空题( 每小题 3 分,共 15分) 6. 设集合 A ={?,{a }} ,则 A 的幂集 P(A )= 7. 设集合A ={1,2,3,4 },B ={6,8,12}, A到B 的关系R=},,2,{ByAxxyyx?????,那么 R -1= 如第 8 题图所示, 那么图 G 的割点是 9. 连通有向图 D 含有欧拉回路的充分必要条件是. 10. 设X={a,b,c},R是X 上的二元关系,其关系矩阵为 M R=??????????001 001 101 ,那么 R 的关系图为三、化简解答题( 每小题 8 分,共 24分) 11. 简化表达式)( ))) (() ))( (((ACABBACBA????????. 12. 设代数系统(R *, ?), 其中 R* 是非 0 实数集, 二元运算?为: ?a,b ?R,a ?b= ab. 试问?是否满足交换律、结合律,并求单位元以及可逆元素的逆元. 13. 化简布尔表达式)(bacbaa????. ( 每小题 8 分,共 32分) 14. 求命题公式)()(QPQP?????的真值表. 15. 试求谓词公式),( )),(),()((yxAyx yR yx xQ xPx??????中, ?x,?x,?y 的辖域,试(A) ?(B) ??(C) ??(D) ??????????????第 5题图 a??bf??ce??d 第 8题图 2 问R(x,y)和A(x,y)中x,y 是自由变元,还是约束变元? 16. 设R 1是A 1= {1,2} 到A 2=(a,b,c) 的二元关系, R 2是A 2到A 3={??, } 的二元关系, R 1= {<1, a >,<1, b >,<2, c >}, R 2 ={< a,?>,< b,?>} 试用关系矩阵求 R 1?R 2 1 v 2v 5v 6v 8v 7 v 4v 3 第 17题图五、证明题(第 18题 10 分,第 19题9分) 18. 证明SSPRRQQP???????????))()) (()( 19. 设G为9 个结点的无向图,每个结点的度数不是 5 就是