离散数学a卷答案.docVIP

上海海洋大学试卷答案 学年学期 20 11 ~ 20 12学年第 1 学期 考核方式 闭卷 课程名称 离散数学A A/B卷 （ A ）卷 课程号 1108101 学分 3 学时 48 题号 一 二 三 四 五 六 七 八 九 十 总分 分数 阅卷人 姓名： 学号： 专业班名： 一、选择填空题（每空3分，共42分） 1、C 2、B 3、00，10 ， 4、 令F(x):x是运动员，G(x):x是强壮的 5、 6、A 7、 8、 9、 答案不唯一 11、 n为奇数 。 12、6 12、 90 ， {000，001，01，10，11} 三、（8分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设p：开关A关闭，q：开关B关闭，r：开关C关闭，G表示灯亮。求G的主析取和主合取范式。 解：由题意可知 主析取范式 故G的成真赋值为 111，101，011 G的成假赋值为 000，001，010，100，110 主合取范式为 四、（8分）在自然推理系统中，构造并证明下列推理。（命题逻辑推理证明） 若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，但小李不喜欢物理。所以，小赵喜欢数学。 证明：设p:小张喜欢数学，q:小李喜欢数学，r:小赵喜欢数学，s:小李喜欢物理 上述符号化为： 前提：；结论： 证明：（1） 前提 （7） （3）（6）拒取式 （2） （1）化简 （8） (5)(7)析取三段论 （3） （1）化简 （4） 前提 （5） （2）（4）假言推理 （6） 前提 五、设集合，R为A上的二元关系，且， （1）求R的关系矩阵；（3分） （2）求R的性质；（3分） （3）求R的传递闭包t（R）；（4分） （4）设，求；（4分） （5）在关系R中添加最少的有序对使其成为A上的等价关系，不妨令该等价关系为，求及商集。（4分） 解：（1） （2）R具反对称性。 （3）， 所以 （4） （5） 六、（10分）设集合， R为A上的整除关系，则R为偏序关系。（1）求该关系的哈斯图； （2）令，求B的最大元、最小元、极大元、极小元。 解 最大元：6 最小元：无 极大元：6 极小元：2，3 八、（5分）已知七人中，会讲的语言分别为： 英语、德语，英语、汉语，英语、意大利语、俄语，汉语、日语， 意大利语、德语，俄语、日语、法语，德语、法语 问能否将他们的座位安排在圆桌旁，使得每个人都能和身边的人交谈？ 解：令V={}， 则可得图G=V,E, 由题意即判断右图是否为哈密顿图。 显然右图为哈密顿图，且有哈密顿回路 Abdfgeca(或abdfcega) 按上述方式安排圆桌会议可使每人都和 身边的人交谈。 九、（6分）已知无向赋权图G=V,E,W, （1）该图是否为欧拉图，如果不是， 最少添加几条边可以将其变为欧拉图？ 请在上图中画出。 （2）求该图的最小生成树。 解：（1）该图不是欧拉图，有4个奇度顶点。最少添加2条边使其变为欧拉图。 （2）最小生成树为：权为15. 第4页，共4页 1 2 3 4 6 8 12 24 a b c d e f g 3 2 2 1 1 3 3