上海海洋大学试卷答案
学年学期 课程名称 课程号 题号 分数 阅卷人
姓名： 学号： 专业班名：
一 1108101 二 三 四 20 11 ~ 20 12学年第 1 学期 离散数学A 学分 五 六 3 七 考核方式 A/B卷 学时 八 九 闭卷 （ A ）卷 48 十 总分 一、选择填空题（每空3分，共42分） 1、C 2、B
3、00，10 ， (p??q)?(?p??q)
4、 令F(x):x是运动员，G(x):x是强壮的 ?x(F(x)?G(x x 或))??x(F(x?)?G (5、?x?y(P(x)?Q(y)) 6、A 7、 (1,2?)[3 , 8、 f1,f3 9、{?1,1?,?2,2?} 答案不唯一 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?(p?r)?(q?r)
?(p?q?r)?(p??q?)r ?(p?q?r)?(p??q?)r故G的成真赋值为 111，101，011 G的成假赋值为 000，001，010，100，110 主合取范式为
G?(p?q?r)?(p?q??r)?(p??q?r)?(?p?q?r)?(?p??q?r)
?(p?q?)r?(?p(??p q??r ?q 主析取范式)?r
第1页，共4页
四、（8分）在自然推理系统中，构造并证明下列推理。（命题逻辑推理证明） 若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，但小李不喜欢物理。所以，小赵喜欢数学。
证明：设p:小张喜欢数学，q:小李喜欢数学，r:小赵喜欢数学，s:小李喜欢物理 上述符号化为：
前提：p?q?r,q?s,p??s；结论：r
证明：（1）p??s 前提 （7）?q （3）（6）拒取式 （2）p （1）化简 （8）r (5)(7)析取三段论 （3）?s （1）化简 （4）p?q?r 前提
（5）q?r （2）（4）假言推理 （6）q?s 前提
五、设集合A?{a,b,c,d}，R为A上的二元关系，且R?{(a,b),(b,c),(c,a),(d,d)}， （1）求R的关系矩阵；（3分） （2）求R的性质；（3分）
（3）求R的传递闭包t（R）；（4分）
（4）设S?{(a,c),(c,b),(d,c)}，求S?1?R；（4分）
（5）在关系R中添加最少的有序对使其成为A上的等价关系，不妨令该等价关系为R*，求R*及商集A/R*。（4分）
?0100???0010? ???1000???0001??解：（1）MR（2）R具反对称性。
（3）R2?{(a,c),(b,a),(c,b),(d,d)}，R3?{(a,a),(b,b),(c,c),(d,d)}
(c,)c,(a,)d, (d, R4?{(a,b),b)}所以
t(R)?R?R?R?R234?{(a,b),(b,c),(c,a),(d,d),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c)}
（4）S?1?{(c,a),(b,c),(c,d)}
b,a),b( d, S?1?R?{(a,c),()}（5）R*?{(a,b),(b,c),(c,a),(d,d),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c)}
A/R?{{a,b,c},{d}}
*第2页，共4页
六、（10分）设集合A?{1,2,3,4,6,8,12,24}， R为A上的整除关系，则R为偏序关系。（1）求该关系的哈斯图； （2）令B?{2,3,6}，求B的最大元、最小元、极大元、极小元。 解
24 最大元：6 8 最小元：无 极大元：6 极小元：2，3
1
2
3 4
6 12
八、（5分）已知a,b,c,d,e,f,g七人中，会讲的语言分别为：
a:英语、德语，b:英语、汉语，c:英语、意大利语、俄语，d:汉语、日语， e:意大利语、德语，f:俄语、日语、法语，g:德语、法语
问能否将他们的座位安排在圆桌旁，使得每个人都能和身边的人交谈？ 解：令V={a,b,c,d,e,f,g}，E?{(u,v)|u与v可交谈} 则可得图G=
a b 由题意即判断右图是否为哈密顿图。 显然右图为哈密顿图，且有哈密顿回路 g c Abdfgeca(或abdfcega)
按上述方式安排圆桌会议可使每人都和 e 身边的人交谈。
九、（6分）已知无向赋权图G=
（1）该图是否为欧拉图，如果不是， 最少添加几条边可以将其变为欧拉图？ 请在上图中画出。
（2）求该图的最小生成树。
解：（1）该图不是欧拉图，有4个奇度顶点。最少添加2条边使其变为欧拉图。
第3页，共4页
f d
（2）最小生成树为：权为15. v1 v2 v6
3
2 v4
v8
1 2
3
v3
3 v5 1 v7
第4页，共4页
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库11离散数学a卷答案在线全文阅读。
相关推荐：