第 1 页 共 6 页
－――――― ― ― ― ― ― ― 室―教―场―考― ― ― ― ― ― ― ― ― ―师―教―课―任― ― ― 线 订 ： 号装证―考―准― ― ― ― ― ― ― ― ―：―名―姓― ― ― ― ― ― ― ― ― ―：―级―班 ―中国民航学院2012－2013 学年第 2 学期
《离散数学》试卷B答案
课程编号：03401519 试卷类型： 考试形式：闭卷 考试日期：2013年6月26日(15:30-17:30) 南1-103 题号 一 二 三 四 五 六 总分 得分 注意事项：1. 答题写在试卷上，后一页为草稿纸，可以撕下；2.不准携带任何书籍、资料、纸张等。
一 (40分) 选择填空
(1）下列语句中哪个结论是对的( ) (A) “3x+5y=0” 是一个命题
(B) 命题公式(P∧(P→Q) )→Q是矛盾式。 (C) 命题函数是一个命题 (D) n元谓词就是有n个客体变元的命题函数，当: n=o时，它本身就
是命题。
(2) 设P:天正在下雪； Q:我将进城； R:我有空。 将下列句子：
(A)我将进城去当且仅当我有空且天不下雪。
(B)虽然天正在下雪，但我将进城去。
(C)天正在下雪当且仅当我有空。 (D)天不下雪且我没有空。
符号化为：
(A) Q→(R∧┑P) ; (B) P∧Q (C) (Q→R)∧(R→Q); (D) ┑(R∨P).
其中，哪一个是错的 ( )
答案:〔(1)〕
(3) 下列判断中哪个结论是对的( )
(A) 谓词公式(?x)P(x)∧(?y) ┒P(y)是不可满足的。 答案: Y;
(B) 对公式(?z) (P(z)∧Q(x, z)∧M(z, y))∨R(z)中的约束变元z改名后，得到的等价公式为: (?t) (P(t)∧Q(x, t)∧M(t, y))∨R (t)。 答案: N。;
(C) 对公式(?z) (P(z)∧Q(x, z)∧M(z, y))∨R(z)中自由变元代入后，有: (?z) (P(z)∧Q(a, z)∧M(z, b))∨R(z)。 答案: N。;
(D) 设论域S={a,b,c}消去公式((?x)┒P(x)∨(?x)P(x)中量词为: ┒(P(a)∨P(b)∧P(c))∨(P(a) ∧P(b) ∧P(c))。 答案: Y。
(4) 下列各式哪个是错的 ( )
(A) ???; (B) ???; (C) ??{?}; (D) ??{?}.
答案.〔(2)〕
第 2 页 共 6 页
(5) 设A={ a, b,c}上的关系如下，有传递性的为( ) (A) R1= {
(C) R3= {
(6) 设R和S是非空集A上的等价关系。下述各式哪个是 等价关系( ) (A) (A×A) – S; (B) S
(C) R-S; (D) r(R-S) 答案:[ (2)]
(7) 若f、g都是满射的，则复合函数gof必是( ) (A)映射; (B) 入射 (C)满射; (D)双射. 答案:[(3)]
(8) 求A? (┒P→Q)∧(Q→P)。的主析取范式(编码表示)，A的主析取范式为A?m11∨m10，____________.
二 （10分）用基本等价公式证明下述结论是否正确：
P,Q→R,R∨S?Q→S
证明：
((P∧(Q→R)∧(R∨S))→(Q→S)
=┑P∨┑(┑Q∨R)∨┑(R∧S)∨(┑Q∨S) =┑P∨(Q∧┑R)∨(┑R∨┑S)∨(┑Q∨S)
=┑P∨(┑R∧(Q∧┑S))∨(┑Q∨S)=┑P∨┑R∨┑Q∨S≠1
所以:P,Q→R,R∨S?Q→S
三 （10分）证明
P→（Q→R）?（S→Q）→（P→（S→R））
证：构造公式序列如下
⑴P→（Q→R） 前提 ⑵S→Q 假设 ⑶P 假设 ⑷S 假设 ⑸Q （4），（2）；分 ⑹Q→R （3），（1）；分 ⑺R （5），（6）；分 所以，（S∧Q）→R，┑R∨P，┑P ?S→┑Q.
2
2
第 3 页 共 6 页
四 (10分) 设A={?,{a},{b},{a,b}}上的关系R= “?”, 写出关系R,画出关系R哈斯图，求子集B={?,{a}}的最大元和最小元. 解：
关系R= “?”, 其哈斯图如图1所示.
{a,b}
{a} {b}
? 图1关系R哈斯图
子集B={?,{a}}的 最大元：｛a｝；最小元：? 五（15分)证明
? x?yA(x,y)? ? y?xA(x,y).
证:先证明? x?yA(x,y) ? ? y?xA(x,y) ⑴?x?yA(x,y) 前提 ⑵?yA(s,y) (1);US ⑶A(s,t) (2);US ⑷?xA(x,t) (3);UG ⑸?y?xA(x,y) (4);UG 所以，? x?yA(x,y) ? ? y?xA(x,y) 再证明?y ? xA(x,y) ? ?x? y A(x,y) ⑴?y?xA(x,y) 前提 ⑵?xA(x,t) (1);US ⑶A(s,t) (2);US ⑷?yA(s,y) (3);UG ⑸?x?yA(x,y) (4);UG 所以，?y ? xA(x,y) ? ?x? y A(x,y) 综合即得：? x?yA(x,y) ? ? y?xA(x,y).
六 (15分) 设R是集合A上的关系，证明或否定下述论断：
若R是传递的，则 r（R），s（R）是传递的。 证明
①对任意x，y，z∈A，若〈x，y〉∈r（R）=R∪I，〈y，x〉∈r（R）=R
∪I，则有（〈x，y〉∈R或〈x，y〉∈I）并且（〈y，z〉∈R或〈y，z〉∈I）。
若〈x，y〉∈R且〈y，z〉∈R，则由R是传递的，所
以〈x，z〉∈R。又因为R r（R），所以〈x，z〉∈r（R）
若〈x，y〉∈I或〈y，z〉∈I，则x=y或又因为I r（R）， 则由〈x，x〉∈r（R）及〈x，z〉∈r（R），有〈x，z〉∈r（R）。
3
第 4 页 共 6 页
则由〈x，z〉∈r（R）及〈z，z〉∈r（R），有〈x，z〉∈r（R）。
所以〈x，z〉∈r（R）。
无论是哪一种情况，都有〈x，z〉∈r（R），即r（R）是传递的。
②结论不一定成立。
如R={〈1，2〉}，则R可传递，但s（R）={〈1，2〉，
〈2，1〉}不可传递。
4
第 5 页 共 6 页
5