離散數(shù)學模擬題及答案

1、一、 填空1不能再分解的命題稱為_，至少包含一個聯(lián)結詞的命題稱為_。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冪集 P(P(Æ) _。5設A為任意集合，請?zhí)钊脒m當運算符，使式子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，其中

2、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，ØQR，R®SÞP®S。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|

3、x,yA(y=x+1y=)，S=x,y|x,yA（x=y+2）。試求RSR。4證明：R是傳遞的ÛR*RÍR。5設R是A上的二元關系，S=<a, b>| 存在cA，使<a, c>R，且<c, b>R。證明：若R是等價關系，則S也是等價關系。6若f:AB和g:BC是雙射，則（gof）-1=f-1og-1。7符號化下列命題，并證明結論的有效性。只要今天天氣不好，就一定有考生不能提前進入考場，當且僅當所有考生提前進入考場，考試才能準時進行。所以，如果考試準時進行，那么天氣就好。8畫出集合S=1,2,3,4,5,6在偏序關系“整除”下的哈斯圖，并討

4、論：1）寫出 1,2,3,4,5,6的最大(小)元和極大(小)元；2）分別寫出2,3,6和2,3,5的上(下)界、上(下)確界。9. 設R是A=1,2,3,4,5上的二元關系，R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>，求r(R)、s(R)和t(R)，并作出它們及R的關系圖。參考答案一、填空1原子命題；復合命題2；3a,d,e4Æ,Æ5Å；60，3，6；0，3，67S1S2SnS； SiSjÆ,1i<jn8重言；永假910. <a,a>

5、;,<b,b>,<b,c>,<c,b>,<c,c>二、證明及求解1解：(Øp®q)®( Øqp)ÛØ(Øp®q)(pØq)ÛØ(pq)(pØq)Û(ØpØq)(pØq) Û(ØppØq)(ØqpØq)Û(pØq)ÛM1Ûm0m2m321）證明：(1)P 附加前提(2)ØPQ P(3)Q T(

6、1)(2)，I(4)ØQR P(5)R T(3)(4)，I(6)R®S P(7)S T(5)(6)，I(8)P®S 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=<0,1>,<1,2>,

7、<2,3>,<0,0>,<2,1>,S=<2,0>,<3,1>，RS=<1,0>,<2,1>,RSR=<1,1>,<1,0>,<2,2>4證明 若R是傳遞的，則<x，y>R*RÞ$z(xRzzSy)ÞxRccSy，由R是傳遞的得xRy，即有<x，y>R，所以R*RÍR。反之，若R*RÍR，則對任意的x、y、zA，如果xRz且zRy，則<x，y>R*R，于是有<x，y>R，即有xRy，所以R

8、是傳遞的。5證明 由R是A上的等價關系，知<a,a>R，故存在aA，使<a,a>R，且<a,a>R，故<a,a>S。若<a, b>S，則存在cA，使<a,c>R，且<c,b>R，由R的對稱性，<b,c>R，且<c,a>R，故<b,a>S。若<a, b>S，<b,c>S，存在dA，使<a,d>R，且<d,b>R，存在eA，使<b,e>R，且<e,c>R，由R的傳遞性，故存在eA，使<a,e>R，

9、且<e,c>R，所以<a, c>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(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-1

10、og-1)(c) 由1)，2)可知 f-1og-1(gof)-17解 設P：今天天氣好，Q：考試準時進行，A(e)：e提前進入考場，個體域：考生的集合，則命題可符號化為：ØP®$xØA(x)，"xA(x)«QÞQ®P。(1)ØP®$xØA(x) P(2)ØP®Ø"xA(x) T(1)，E(3)"xA(x)®P T(2)，E (4)"xA(x)«Q P(5)("xA(x)®Q)(Q®&qu

11、ot;xA(x) T(4)，E(6)Q®"xA(x) T(5)，I(7)Q®P T(6)(3)，I81）最大元：無；最小元：1；極大元：4，5，6；極小元：12）2,3,6的上界：6；下界：1；上確界：6；下確界：1。2,3,5的上界：無；下界：1；上確界：無；下確界：1。9. 解：r(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3>,<5,5>s(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>R2=R5=<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>R3=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>R4=<2,2>,<2,4>,<