2013离散数学II1试卷B答案.doc

中国民航学院2012－2013 学年第 2 学期 《离散数学》试卷B答案 课程编号试卷类型： 考试形式：闭卷 考试日期：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)〕 (5) 设A={ a, b,c}上的关系如下，有传递性的为( ) (A) R1= {a.c, c,e, a,b，b,a}； (B) R2= {a,a,c,a}; (C) R3= {a.b, c,c, b,a，b,c}; (D) R4= {a,a}; 答案 [(4)] (6) 设R和S是非空集A上的等价关系。下述各式哪个是 等价关系( ) (A) (A×A) – S; (B) S2 (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. 四 (10分) 设A={(,{a},{b},{a,b}}上的关系R= “?”, 写出关系R,画出关系R哈斯图，求子集B={(,{a}}的最大元和最小元. 解： 关系R= “?”, 其哈斯图如图1所示. {a,b}