《离散数学》试题及答案详解.pdf

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

1、一、填空题一、填空题1 1 设集合 A,B，其中A1，2，3,B=1，2,则 A B_3_；（A)-(B)_3,1，3,2，3，1,2,3 _。2.2.设有限集合 A,A=n，则(AA）=_3.3.设集合A=a,b,B=1,2，则从A到B的所有映射是_1=(a,1）,(b,1）,2=（a,2)，（b，2），3=(a,1），(b,2)，4=(a,2）,（b，1)；_，其中双射的是_3，4。_4。已知命题公式G（PQ)R，则 G 的主析取范式是 _（PQR）_.5.设 G 是完全二叉树，G 有 7 个点，其中 4 个叶点，则 G 的总度数为_12_，分枝点数为_3_.6 6 设 A、B 为 两 个

2、 集 合,A=1，2,4，B=3,4，则 从 AB _4_;AB_1,2,3,4_；AB _1,2_.3.7 7。设 R 是集合 A 上的等价关系，则 R 所具有的关系的三个特性是_自反性;对称性；传递性_.8 8.设命题公式 G（P（QR）)，则使公式 G 为真的解释有_（1,0,0)_，_（1，0,1)_，_（1,1，0）_。9.设集合 A1，2,3，4,A上的关系 R1=(1,4）,（2，3)，(3，2），R1=（2，1)，（3,2）,（4,3)，则R1R2=_(1，3）,（2，2）,（3,1)_，R2R1=_(2,4）,(3,3）,(4,2)_,(3,3）_。4.10。设有限集 A,B

3、,A=m，|B|=n，则|（AB）=_2mn_.1111 设A,B,R是三个集合，其中R是实数集，A=x 1x1,xR，B=x|0 x 2，xR,则 AB=_x|1x 0,xR_，B-A=_x|1 x 6(D)下午有会吗?5 5 设 I 是如下一个解释：Da，b，1则在解释 I 下取真值为 1 的公式是（D）.(A）xyP（x，y）（B）xyP（x,y)（C）xP（x，x）（D)xyP（x，y）。6。若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是(C）.（A）（1，2，2，3，4,5）（B)（1，2，3,4,5,5）（C）(1，1,1,2，3）（D）（2，3，3，4,5,6）。

4、7.设 G、H 是一阶逻辑公式,P 是一个谓词,GxP(x）,HxP（x)，则一阶逻辑公式 GH是(C).(A)恒真的（B）恒假的(C）可满足的(D)前束范式.8 8设命题公式 G(PQ)，HP（QP），则 G 与 H 的关系是（A)。（A）GH（B)HG(C）GH(D）以上都不是。9设 A,B 为集合,当（D)时 ABB。（A）AB（B)AB（C)BA(D）AB。10设集合 A=1,2,3，4，A 上的关系 R （1，1),(2,3），(2,4),(3,4)，则 R 具有(B）。(A）自反性(B）传递性(C）对称性(D）以上答案都不对1111下列关于集合的表示中正确的为(B）。（A）aa，b

5、,c（B）aa，b，c(C）a,b，c（D)a，ba,b,c1212 命题xG（x）取真值 1 的充分必要条件是（）。(A)对任意 x,G（x）都取真值 1。（B)有一个 x0，使 G(x0）取真值 1.（C）有某些 x,使 G(x0)取真值 1.（D)以上答案都不对。13.设 G 是连通平面图,有 5 个顶点,6 个面，则 G 的边数是(A）。（A）9 条(B)5 条(C）6 条(D）11条.14.设 G 是 5 个顶点的完全图,则从 G 中删去(A）条边可以得到树.（A)6（B）5(C）10(D)4。15。设图 G 的相邻矩阵为，则G 的顶点数与边数分别为(D)。（A）4，5(B)5，6（

6、C)4，10（D)5，8.三、计算证明题三、计算证明题1 1。设集合 A1,2,3，4,6，8，9,12，R 为整除关系。(1)画出半序集(A,R)的哈斯图；(2)写出 A 的子集 B=3,6，9,12的上界，下界，最小上界,最大下界；(3)写出 A 的最大元，最小元，极大元，极小元。（1)(2)B 无上界，也无最小上界。下界1,3;最大下界是 3.(3)A无最大元，最小元是1，极大元 8，12，90+；极小元是 1.2.设集合 A1,2,3，4，A 上的关系 R(x，y)x,yA 且 x y,求(1)画出 R 的关系图；(2)写出 R 的关系矩阵。R=(1,1）,（2，1),(2,2），(3

7、,1),(3，2)，（3，3）,(4，1),(4，2),（4,3），(4，4)。(1)（2)3.设 R=，是实数集合，是 R 上的三个映射,（x)x+3，（x)=2x,(x)x/4，试求复合映射,，。(1）（x)）(x)+32x+32x+3。(2)(x）)(x）+3(x+3）+3x+6，（3）（(x）)（x)+3x/4+3,（4)（(x）)(x)/42x/4=x/2，（5）（)+32x/4+3x/2+3。4.设 I 是如下一个解释:D=2，3,a3b2f（2）3f(3)2P(2,2)0P（2，3)P（3，2）01P(3,3)1试求(1）P(a，f（a)）P(b,f(b);(2)xy P（y，x

8、）.(1)P（a，f(a)P(b,f（b）)=P（3,f（3）P(2，f（2）)=P(3，2）P(2,3）=10=0。(2)xy P（y，x）=x(P(2，x)P（3,x)=(P（2,2)P(3,2）（P（2,3)P(3,3）)=(01)（01）=11=1。5.设集合 A1，2，4,6，8,12，R 为 A 上整除关系。(1)画出半序集(A,R)的哈斯图；(2)写出 A 的最大元,最小元,极大元，极小元；(3)写出 A 的子集 B=4,6，8,12的上界，下界,最小上界，最大下界。1)（2)无最大(3)B 无上界，6.设 命 题 公析取范式。G=（PQ)=（P=（PQ)（Q（PR)=(PQ)（

9、QP)（QR)=（PQR）（PQR)（PQR)（PQR)(PQR)（P元,最小元 1，极大元 8，12；极小元是 1。无最小上界。下界 1，2;最大下界 2.式 G=(PQ）(Q(PR)，求 G 的主(Q（PR)）Q)（Q(PR)QR)=(PQR)（PQR）（PQR)（PQR)（PQR)=m3m4m5m6m7=(3，4，5，6，7）.7.（9 分)设一阶逻辑公式:G=(xP(x）yQ（y）)xR（x），把 G 化成前束范式.G=(xP（x)yQ(y)xR（x)=（xP(x）yQ(y)xR（x)=(xP(x）yQ（y）xR（x)=(xP(x)yQ(y)zR(z)=xyz(P（x)Q(y）R（z）

10、)9.设 R 是集合 A=a,b，c,d。R 是 A 上的二元关系，R=(a，b),(b,a)，（b,c）,(c，d），(1)求出 r（R)，s(R)，t(R)；(2)画出 r（R)，s（R),t（R）的关系图。(1）r（R)RIA(a,b)，（b,a),（b,c），（c,d）,(a,a）,（b，b），（c,c),(d，d),s（R)RR1（a，b），（b，a),（b,c)，(c，b)（c,d)，(d,c)，t(R）RR2R3R4(a，a），（a,b),(a,c），(a，d),（b,a）,（b，b)，(b，c）,（b,d），（c,d）；(2)关系图：1111。取 范命 题价：通过求主析式判断下

11、列公式是否等(1)G=Q）(P（PQR）(2）H=(P（QR）(Q(PR)G（PQ）(PQR)（PQR）(PQR）(PQR）m6m7m3（3,6,7)H=(P(QR)）（Q(PR)（PQ）(QR）(PQR）(PQR)（PQR)（PQR）(PQR）(PQR）(PQR)(PQR)（PQR）m6m3m7(3,6,7)G,H 的主析取范式相同，所以G=H。13。设 R 和 S 是集合 Aa，b,c,d上的关系，其中R（a,a）,(a，c）,（b，c），(c,d),S(a,b），（b，c)，（b,d),（d,d)。（1）试写出 R 和 S 的关系矩阵；(2）计算 RS,RS，R1，S1R1。(1）（2）

12、R S(a,b),(c,d),RS（a,a),(a,b)，（a,c)，（b,c），(b，d)，（c,d），(d,d）,R1（a,a），（c，a），(c，b),（d,c）,S1R1（b,a)，(d,c）.四、证明题1.利用形式演绎法证明:PQ,RS，PR蕴涵 Q S。证明：PQ,RS,PR蕴涵 Q S（1）PRP（2）RPQ(1)（3)PQP(4)RQQ（2）（3）(5）Q RQ（4)（6)RSP（7）Q SQ(5）（6）（8)Q SQ（7)2.设 A,B 为任意集合，证明：（A B）C=A(BC）.证明：（A B)C=(A B）C=A(BC)=A（BC）=A(BC)3.（本题 10 分）利用形

13、式演绎法证明：A B，C B，证明：A B，C B,CD蕴涵 A D(1）AD(附加）(2)A BP（3)BQ(1)(2）(4）C BP（5)B CQ（4)（6）CQ（3)(5）(7)C DP(8)DQ（6）(7)CD 蕴涵 A D。（9）ADD（1)（8）所以 AB,CB,CD蕴涵 AD.4.(本题 10 分)A，B 为两个任意集合，求证：A(AB)=(AB）B。4.证明：A(AB)=A(AB）A(AB）(AA）（AB)（AB)(AB)AB而(AB)B=(AB)B=（AB)(BB)=（AB）=AB所以：A(AB）=(AB)B.参考答案参考答案一、填空题1.3;3,1,3,2,3，1,2，3.

14、2。7.1=（a，1），(b,1）,2=(a,2），(b，2),3=（a，1），（b，2）,4=(a,2），（b,1);3,4.8.(PQR）.9.12，3.10.4,1,2，3,4,1,2。11.自反性；对称性;传递性。12.(1,0，0），(1，0,1）,（1,1，0)。13.(1,3),(2,2）,(3，1);（2,4),(3，3),（4，2）；（2，2），（3,3）.14.2mn.15.x|1x 0，xR；x|1 x 2,xR；x|0 x1,xR。16.12；6。17.(2,2），(2,4)，(2,6),（3，3），(3，6）,(4，4），(5，5），（6，6).18.x(P(x）Q（

15、x)。19.21。20.（R(a)R（b)（S(a)S（b)。21.(1,3）,（2，2);（1，1)，（1，2),(1,3)。二、选择题二、选择题1.C。2。D。3。B。4。B.5.D。6。C。7.C。8。A。9.D。10.B.11。B.13。A.14.A。15.D三、计算证明题三、计算证明题1.（1)（2）B 无上界，也无最小上界.下界 1,3;最大下界是 3.(3)A无最大元，最小元是1，极大元 8,12，90+；极小元是 1。2 2。R=(1,1),（2,1）,(2,2），(3，1),（3，2）,(3，3)，(4，1),(4,2)，（4,3),（4，4）.（1）(2)3。（1)(x)(

16、x)+32x+32x+3。（2)（(x)（x）+3(x+3)+3x+6，(3)(x）)(x）+3x/4+3,（4）(x）(x)/42x/4=x/2，(5)（)+32x/4+3x/2+3.4.（1)P（a，f（a)P(b,f(b）=P(3,f（3)）P(2，f（2)=P(3，2)P（2，3）=10=0.(2)xy P（y，x)=x(P(2，x）P（3，x）)=(P（2,2)P(3,2）)(P（2,3)P(3，3）=（01）(01)=11=1。元,最小元 1,极大元 8，12;极小元是 1.上界,无最小上界.下界 1,2;最大下界 2。Q)(Q(PR)）Q）（Q(PR）Q）(Q(PR)）Q）(QP

17、)(QR)5.5.(1）(2）无最大（3）B 无6。G=(P=(P=（P=(P=(PQR）(PQR）(PQR）（PQR）(PQR）(PQR）=(PQR）（PQR)(PQR）(PQR）(PQR）=m3m4m5m6m7=（3，4,5，6，7）.7。G=（xP(x）yQ(y）)xR（x）=(xP（x)yQ(y）xR(x)=(xP(x）yQ（y)）xR(x)=(xP(x)yQ（y)）zR(z）=xyz(P(x）Q(y)R(z）)9.（1)r（R)RIA（a，b），（b,a），（b，c）,(c，d），（a，a),(b，b），(c，c），(d,d)，s（R)RR1（a，b)，（b，a),（b,c），(c，

18、b)(c，d),（d,c),t(R)RR2R3R4（a,a），(a，b），(a，c），（a，d)，（b，a），(b，b)，(b,c),（b,d)，（c，d);（2)关系图：1111。G（PQ)(P Q R)(PQR)（PQR）（PQR）m6m7m3（3,6,7）H=(P（QR)）(Q（PR）（PQ)（QR）)（PQR)(PQR）（PQR)（PQR)(PQR)（PQR)(PQR)(PQR）(PQR)m6m3m7(3，6，7）G,H 的主析取范式相同，所以G=H.13.(1)(2)R S（a，b）,（c,d），RS(a，a）,（a，b)，（a,c），（b，c），(b，d）,(c,d)，（d，d)，

19、R1（a,a），(c，a),（c,b)，（d,c），S1R1(b，a）,（d,c).四四 证明题证明题1.证明：PQ，RS，PR蕴涵 QS(1）PRP(2）RP（3）PQ(4)RQQ(1）PQ(2)（3)Q(4)P（5)QR（6）RS（7）QS(8）QSQ（5）(6）Q（7)2。证明:(A-B）-C=（AB)C=A（BC)=A（BC）=A（BC)3.证明：AB,CB，CD蕴涵 AD（1)AD（附加）PQ(1)(2)PQ(4)(2）AB（3）B（4）CB（5）BC（6）C(7）CD（8)DQ（3)（5）PQ（6）(7）D（1）（8）(9）AD所以 AB，CB，CD蕴涵 AD.5.证明:A（AB）=A(AB）A(AB)(AA）(AB)(AB）（AB）AB而(AB）B=(AB)B=(AB）（BB)=(AB）=AB所以:A(AB）=（AB)B。