离散数学模拟题及答案.doc

《离散数学模拟题及答案.doc》由会员分享，可在线阅读，更多相关《离散数学模拟题及答案.doc（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date离散数学模拟题及答案华北电力大学(北京) 2005-2006学年第一学期考试试卷(A)一、 填空1不能再分解的命题称为_，至少包含一个联结词的命题称为_。2一个命题公式A(P, Q, R)为真的所有真值指派是000, 001, 010, 100，则其主析取范式是_，其主合取范式是_。3设 A=a,b,c，B=b,c,d,e，C=b,c，则( A B ) C _。4幂集

2、 P(P() _。5设A为任意集合，请填入适当运算符，使式子A_A=；A_A=成立。6设A=0，1，2，3，6，R=x,y|xy(x,yA)yx(mod 3)，则D(R)=_，R(R)=_。7称集合S是给定非空集合A的覆盖：若S=S1，S2，Sn，其中SiA，Si，i=1，2，n，且_ _；进一步若_ _，则S是集合A的划分。8两个重言式的析取是_ _式，一个重言式和一个永假式的合取式是 式。9公式 (PQ) (PQ)的主析取范式是 。10. 已知=ab,c是A=a,b,c的一个划分，由决定的A上的一个等价关系是 。二、 证明及求解1求命题公式（PQ）（QP）的主析取范式。2推理证明题1）PQ

3、，QR，RSPS。2) (x)(P(x)Q(y)R(x)，($x)P(x)Q(y)($x)(P(x)R(x)3设A=0，1，2，3，R=x,y|x,yA(y=x+1y=)，S=x,y|x,yA（x=y+2）。试求RSR。4证明：R是传递的R*RR。5设R是A上的二元关系，S=| 存在cA，使R，且R。证明：若R是等价关系，则S也是等价关系。6若f:AB和g:BC是双射，则（gof）-1=f-1og-1。7符号化下列命题，并证明结论的有效性。只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。8画出集合S=1,2,

4、3,4,5,6在偏序关系“整除”下的哈斯图，并讨论：1）写出 1,2,3,4,5,6的最大(小)元和极大(小)元；2）分别写出2,3,6和2,3,5的上(下)界、上(下)确界。9. 设R是A=1,2,3,4,5上的二元关系，R=,，求r(R)、s(R)和t(R)，并作出它们及R的关系图。参考答案一、填空1原子命题；复合命题2；3a,d,e4,5；60，3，6；0，3，67S1S2SnS； SiSj,1ijn8重言；永假910. ,二、证明及求解1解：(pq)( qp)(pq)(pq)(pq)(pq)(pq)(pq) (ppq)(qpq)(pq)M1m0m2m321）证明：(1)P 附加前提(2

5、)PQ P(3)Q T(1)(2)，I(4)QR P(5)R T(3)(4)，I(6)RS P(7)S T(5)(6)，I(8)PS CP2) 证明(1)$xP(x)P(2)P(a)ES(1)(3)x(P(x)Q(y)R(x)P(4)P(a)Q(y)R(a)US(3)(5)Q(y)R(a)T(2)(4),I(6)Q(y)T(5),I(7)R(a)T(5),I(8)P(a)R(a)T(2)(7),I(9)$x(P(x)R(x)EG(8)(10)Q(y)$x(P(x)R(x)T(6)(9),I3解：R=,S=,，RS=,RSR=,4证明 若R是传递的，则R*R$z(xRzzSy)xRccSy，由R

6、是传递的得xRy，即有R，所以R*RR。反之，若R*RR，则对任意的x、y、zA，如果xRz且zRy，则R*R，于是有R，即有xRy，所以R是传递的。5证明 由R是A上的等价关系，知R，故存在aA，使R，且R，故S。若S，则存在cA，使R，且R，由R的对称性，R，且R，故S。若S，S，存在dA，使R，且R，存在eA，使R，且R，由R的传递性，故存在eA，使R，且R，所以S。故S是等价关系。6证明：1)因为f:AB和g:BC均是双射，故f-1和g-1均存在，且f-1：BA，g-1：CB，所以f-1og-1：CA。由f和g是双射，可知gof也是双射，故（gof）-1存在且（gof）-1：CA。D(

7、f-1og-1)=D(gof)-1=C2) 对任意cC存在唯一bB，使得g(b)=c存在唯一aA，使得f(a)=b，故 (f-1og-1)(c)= (f-1(g-1(c)=f-1(b)=a 但（gof）(a)=g(f(a)=g(b)=c 故（gof）-1(c)=a 因此对任意cC有：(gof)-1(c)= (f-1og-1)(c) 由1)，2)可知 f-1og-1(gof)-17解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：P$xA(x)，xA(x)QQP。(1)P$xA(x) P(2)PxA(x) T(1)，E(3)xA(x)P T(2)，E (4)xA(x)Q P(5)(xA(x)Q)(QxA(x) T(4)，E(6)QxA(x) T(5)，I(7)QP T(6)(3)，I81）最大元：无；最小元：1；极大元：4，5，6；极小元：12）2,3,6的上界：6；下界：1；上确界：6；下确界：1。2,3,5的上界：无；下界：1；上确界：无；下确界：1。9. 解：r(R)=,s(R)=,R2=R5=,R3=,R4=,t(R)=,图请同学自己画出。-