：名姓 装 订 ： 线号学 ：级班 哈尔滨工程大学试卷 考试科目：离散数学（061121，061131） 题号 一 二 三 四 五 总分 分数 评卷人 一、 填空题（每小题3分，共15分） 1. 谓词公式?xF(x)???yG(x，y)的前束范式为 ． 2. 设有群?Z12，??和?Z3，??，令? ：Z12? Z3，?(x)=(x) mod3，则?是?Z12，??到?Z3，?? 的 ． 3. 已知n阶无向简单图G有m条边，则G的补图有 条边． 4. 有理数集上定义二元运算*为a*b=a+b-ab，则运算*的单位元为 ，零元为 ． 5. 设无向连通图G有6个顶点10条边，T为G的生成树，对应T的基本割集系统中的基本割集个数为 ，基本回路系统中的基本回路个数为 ． 二、 选择题（每小题3分，共15分） 1. 命题公式?(p?q)?(p??q)的类型是 【 】 A．重言式． B．非重言式的可满足式． C．矛盾式． D．简单析取式． 2. 无向树T中有4度，3度，2度顶点各1个，其余顶点都是树叶，则T中树叶片数为 【 】 A．1． B．8． 第1页 共2页 C．7． D．5．
3. 素数阶群一定是 【 】
A．无限群． B．循环群，也是Abel群． C．非交换群． D．循环群．
4. 下列图中那一个是欧拉图 【 】
A．K4，4． B．K4． C．K3，4． D．K3，3．
5. 下列图中是哈密尔顿图的是 【 】
A．K3，4． B．K5． C．K2． D．K1，1．
三、 计算与简答题（每小题10分，共50分）
1. 利用等值演算方法求命题公式((p?q)?(p?q))?(q?p) 的主析取范式；并指出该公式的成真赋值和成假赋值．
第2页 共 2页
2. 求群?Z20，??的所有生成元和子群．
3. 设集合Ａ={a，b，c，d}上的二元关系R={?a，b?，?b，a?，?b，c?，?c，d?}，利用集合运算求R的传递闭包t(R)．
4. (1) 给出具有4个顶点的所有自补图．
第3页 共4页
(2) 给出具有5个顶点的所有自补图．
5. 若R1，R2均是非空集合A上的等价关系，那么R1，R2的交R1∩R2、并R1∪R2和复合R1○ R2也是A上的等价关系吗？简要说明理由．
四、 证明题（每小题10分，共20分）
第4页 共 4页
装 订 线 ：名姓 装 订 ： 线号学 ：级班 1. 在一阶逻辑中构造下面推理的证明 前提：?x(F(x)? G(x))，??x(F(x)?H(x)) 结论：?x(F(x) ?G(x) ?? H(x))
2. 设H?G，?a，b?G，定义?a，b??R?ab-1?H，证明R是G上的等价关系，求出等价关系R的等价类．
第5页 共6页
第6页 共 6页
相关推荐：
loading