2013离散数学ii1试卷b答案

《2013离散数学ii1试卷b答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、s题号二三四五六总分得分屮国民航学院2012—2013学年第2学期《离散数学》试卷B答案课程编号：03401519试卷类型：考试形式：闭卷考试日期：2013年6月260(15:30-17:30)南1-103注意事项:1.答题写在试卷上，后一页为草稿纸，可以撕下；2.不准携带任何书籍、资料、纸张等。-(40分)选择填空(1)下列语句屮哪个结论是对的()(A)“3x+5y=0”是一个命题(B)命题公式(P八(P-*Q))-*Q是矛盾式。(C)命题函数是一个命题(D)n元谓词就是有n个客体变元的命题函数，当:是命题。(2)设P:天正在下雪；Q:我将进城；R:我

2、有空。将下列句子：(A)我将进城去当且仅当我有空且天不下雪。(B)虽然天正在下雪，但我将进城去。(0天正在下雪当且仅当我有空。(D)天不下雪且我没有空。符号化为：(A)Q->(RAnP);(B)PAQ(0(Q->R)A(R->Q);(D)-i(RVP).其屮，哪一个是错的()答案:〔⑴)(3)下列判断中哪个结论是对的()(A)谓词公式(Vx)P(x)八(3y)iP(y)是不可满足的。答案：Y;(B)对公式(彐z)(P(z)AQ(x,z)八M(z,y))VR(z)中的约束变元z改名后，得到的等价公式为:(彐t)(P(t)AQ(x,t)AM(t,y))VR(

3、t)o答案：N。；(C)对公式(3z)(P(z)AQ(x,z)AM(z,y))VR(z)中自由变元代入后，有:(彐z)(P(z)AQ(a,z)AM(z,b))VR(z)o答案：No;(D)设论域S={a，b，c}消去公式((Vx)iP(x)V(Vx)P(x)中量词为:-i(P(a)VP(b)AP(c))V(P(a)AP(b)AP(c))。答案：Yo(4)下列各式哪个是错的()(A)0^0;(B)0G0;(00^{0}:(D)0^{0}.K1JZ⑵rk篆答(5)设A={a,b，c}上的关系如下，有传递性的为()(A)Rl={,,

4、>,}:(B)R2={,};(C)R3={〈a.b>,,,};(D)R4={

5、>R,RVS=>Q->S证明：((PA(Q->R)A(RVS))->(Q->S)二-iPVn(nQVR)Vn(RAS)V(nQVS)=-iPV(QAnR)V(nRVnS)V(nQVS)=nPV(nRA(QAnS))V(nQVS)=nPVnRVnQVS矣1所以：P,Q->R,RVS^Q-*S三(10分)证明P-(Q-R)(S—Q)—(P—(S-R))证：构造公式序列如下提设设设4)前假假假<(1)P->(Q-R)(2)S->Q(3)P(4)S分分分(5)Q(6)Q->R(7)R所以，(SAQ)->R,nRVP,nP=>S->qQ.四(10分)设八=｛0，｛

6、a｝，｛b｝，｛a,b｝｝上的关系尺=写出关系R,画出关系K哈斯阁，求子集B=｛0，｛a｝｝的最大元和最小元.解：关系R=“G”，其哈斯图如图1所示.阁1关系K哈斯阁子集BH0,｛a｝｝的最大元：｛a｝；最小元：0五(15分)证明VxVyA(x,y)<=>VyVxA(x,y).证:先证明VxVyA(x,y)=>VyVxA(x,y)(1)VxVyA(x,y)前提(2)VyA(s,y)(1)；US(3)A(s,t)(2);US⑷VxA(x,t)(3);UG(5)VyVxA(x,y)⑷；UG所以，VxVyA(x,y)=>VyVxA(x,y)再证明VyVxA(x

7、,y)=>VxVyA(x,y)⑴VyVxA(x,y)前提⑵VxA(x,t)(1);US(3)A(s,t)(2);US(4)VyA(s,y)(3);UG⑸VxVyA(x,y)(4);UG所以，VyVxA(x，y)3VxVyA(x，y)练合即得：VxVyA(x,y)<=>VyVxA(x,y).六(15分)设R是集合A上的关系，证明或否定下述论断:若R是俾递的，则r(R),s(R)是俾递的。证明①对任意y,zeA,若〈x,y〉er(K)=RUI,er(R)=RUI,则有(〈x,y〉ER或〈x，y〉GI)并且(ER或〈y,z〉EI)O若〈x,

8、y〉ER且〈y,z〉GR,则由R是俾递的，所以〈x，z〉ER。又因为Rr(R),