11离散数学a卷答案

《11离散数学a卷答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上海海洋大学试卷答案学年学期2011~2012学年第1学期考核方式闭卷课程名称离散数学AA/B卷（A）卷课程号1108101学分3学时48题号一二三四五六七八九十总分分数阅卷人姓名：学号：专业班名：一、选择填空题（每空3分，共42分）1、C2、B3、00，10，4、令F(x):x是运动员，G(x):x是强壮的5、6、A7、8、9、答案不唯一11、n为奇数。12、612、90，{000，001，01，10，11}三、（8分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设p：开关A关闭，q：开关B

2、关闭，r：开关C关闭，G表示灯亮。求G的主析取和主合取范式。解：由题意可知主析取范式故G的成真赋值为111，101，011G的成假赋值为000，001，010，100，110主合取范式为第4页，共4页四、（8分）在自然推理系统中，构造并证明下列推理。（命题逻辑推理证明）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，但小李不喜欢物理。所以，小赵喜欢数学。证明：设p:小张喜欢数学，q:小李喜欢数学，r:小赵喜欢数学，s:小李喜欢物理上述符号化为：前提：；结论：证明：（1）前提（7）（3）（6）拒取式（2）（1）

3、化简（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）第4页，共4页六、（10分）设集合，R为A上的整除关系，则R为偏序关系。（1）求该关系的哈斯图；（2）令，求B的最大元、最小元、极大元、极小元。解最大元：6最小元

4、：无极大元：6极小元：2，31234681224八、（5分）已知七人中，会讲的语言分别为：英语、德语，英语、汉语，英语、意大利语、俄语，汉语、日语，意大利语、德语，俄语、日语、法语，德语、法语问能否将他们的座位安排在圆桌旁，使得每个人都能和身边的人交谈？解：令V={}，则可得图G=,由题意即判断右图是否为哈密顿图。显然右图为哈密顿图，且有哈密顿回路Abdfgeca(或abdfcega)按上述方式安排圆桌会议可使每人都和身边的人交谈。abcdefg九、（6分）已知无向赋权图G=,（1）该图是否为欧拉图，如果不是，最少添加几条边可

5、以将其变为欧拉图？请在上图中画出。（2）求该图的最小生成树。解：（1）该图不是欧拉图，有4个奇度顶点。最少添加2条边使其变为欧拉图。第4页，共4页（2）最小生成树为：权为15.3221133第4页，共4页