2013离散数学II1试卷B答案

第 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= {, , }; (B) R2= {,};

(C) R3= {, , < b,a>,}; (D) R4= {}; 答案 [(4)]

(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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4