离散数学试题及答案

离散数学试题及答案一、填空题1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝ ; (A)-(B)＝ .2.设有限集合A,|A|=n,则= .设集合A={a,b},B={1,2},则从A到B所有映射是 ,其中双射的是 .已知命题公式G＝(PQ)∧R，则G的主取范式是 .设G是完全二叉树，G有7个点其中4叶点，则G的总度数为 ，分枝点为 .6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ ; AB＝ ;A－B＝ .设R是集合A上的等价系，则R所具有关系的三个特性是 , , .设命题公式G＝(P(QR))，则使公式G真的解释有 ， , .9.A＝{1,2,3,4}AR1={(1,4),(2,3),(3,2)},R1={(2,1),(3,2),(4,3)},则R1R2= ,R2R1= , R12= .10.设有限集A,B，|A|=m,|B|=n,则||(AB)|= .设A,B,R是三个集合，其中R是数集，A={x|-1≤x≤1,xR},B={x|0≤x<2,xR},则A-B= ,B-A= ,A∩B= ,.设集合A＝{2,3,4,5,6}，R是A上的整则R以集合形式(列举法)记为 .设一阶逻辑公式G=xP(x)xQ(x)，则G的前束范式是 .设G是具有8个顶点的树，则G中增加 条边才能把G变成完全图。第1页共17页设谓词的定义域为{a,b},将表达式xR(x)→xS(x) .17.A＝{12,3,4}，AR＝{(1,1),(1,2),(2,3)},S＝{(1,3),(2,3),(3,2)}RS＝ ,R2＝ .二、选择题1 设集合A={2,{a},3,4}，B={{a},3,4,1}，E为全集，则下列命题正确的是( )(A){2}A (B){a}A (C){{a}}BE (D){{a},1,3,4}B.2 设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备( ).自反性 (B)传递性 (C)对称性 (D)反对称性设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B= {2,3,4,5},则元6521素6为B的(65213下界 (B)上界 (C)最小上界 (D)以上下列语句中，( )是命题。请把门关上 (B)地球外的星球上也有(C)x+5>6 (D)下午有会吗？

4答案都不对I是如下一个解释：D＝{a,b},

P(a,1

0

P(b,a)1

P(b,b)0则在解释I下取真值为1的公式是( ).(A)xyP(x,y) (B)xyP(x,y) (C)xP(x,x) (D)xyP(x,y).若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( (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).HH＝xP(x),GH是( ).恒真的 (B)恒假的 (C)可满足的 (D)前束范式.设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是( )。第2页共17页GH (B)HG (C)G＝H (D)以上都不是.设A,B为集合，当( )时A－B＝B.A＝B (B)AB (C)BA (D)A＝B＝.10 设集合A={1,2,3,4},A上的关系R＝{(1,1),(2,3),(2,4),(3,4)},则R具有( )。(A)自反性 (B)传递性 (C)对称性 (D)以上答案都不对下列关于集合的表示中正确的为( )。(A){a}{a,b,c} (B){a}{a,b,c} (C){a,b,c} (D){a,b}{a,b,c}命题xG(x)取真值1的充分必要条件是( ).对任意x，G(x)都取真值1. (B)有一个x0，使G(x0)取真值(C)有某些x，使G(x0)取真值1. (D)以上答案都不对.设G是连通平面图，有5个顶点，6个面，则G的边数是( (A)9条 (B)5条 (C)6条 (D)条.设G是5个顶点的完全图，则从G中删去( )条边可以得到树.(A)6 (B)5 (C)10 (D)4.0110G的相邻矩阵为1111 00

1100，则G的顶点数与边数分别为( ).11110 1(A)4,5 (B)5,6 (C)4,10 (D)5,8.三、计算证明题1.设集合A＝{1,2,3,4,6,8,9,12}，R为整除关系。画出半序集(A,R)的哈斯图；AB{3,6,9,12}的上界，下界，最小上界，最大下界；A的最大元，最小元，极大元，极小元。2. A＝{1,2,3,4}，AR＝{(x,y)|x,yAxy},求第3页共17页R的关系图；R的关系矩阵.3. R是实数集合，,,R上的三个映射，(x)x+3,(x2x,(x)＝x/4,试求复合映射•，•••，••.I是如下一个解释：D{2,3},abf(2)f(3)P(2,2)P(2,3)P(3,2)P(3,3)32320011试求(1)P(a,f(a))∧P(b,f(b));(2)xyP(y,x).5.A＝{1,24,6,8,12}，RA上整除关系。画出半序集(A,R)的哈斯图；A的最大元，最小元，极大元，极小元；AB{4,6,8,12}的上界，下界，最小上界，最大下界.G(P→Q)∨(Q∧(P→R)),G的主析取范式。(9分)设一阶逻辑公式：G=(xP(x)∨yQ(y))→xR(x)G化成前束范式.9.RA{a,b,c,d}.RA上的二元关系Ra,b),(b,a),(b,cc,d)},(1)求出r(R),s(R),t(R)；(2)画出r(R),s(R),t(R)的关系图.11.通过求主析取范式判断下列命题公式是否等价：(1)G=(P∧Q)∨(P∧Q∧R)(2)H=(P∨(Q∧R))∧(Q∨(P∧R))RSA＝{abcd}R＝{(aa),(ac),(bc),(cd)},S＝{(a,b),(b,c),(b,d),(dd)}.第4页共17页RS的关系矩阵；(2)R•SR∪SR－1S－1•R－1.四、证明题利用形式演绎法证明：{P→QR→SP∨R}Q∨S。A,B为任意集合，证明：(A-B)-CA-(B∪C).(本题10分)利用形式演绎法证明：{A∨B, C→B, C→D}蕴涵A→D。(10分)AB为两个任意集合，求证：A－(A∩B)=(A∪B)－B.

参考答案一、填空题1. {3}; {{3},{1,3},{2,3},{1,2,3}}.2. 2.3. 1={(a,1),(b,1)},2={(a,2),(b,2)},3={(a,1),(b,2)},4={(a,2),(b,1)};3,4.4. (P∧Q∧R).5. 12,3.6. {4},{1,2,3,4},{1,2}.7. 自反性；对称性；传递性.8. (1,0,0),(1,0,1),(1,1,0).9. {(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2mn.11.{x|-1≤x<0,xR};{x|1<x<2,xR};{x|0≤x≤1,xR}.12.12;6.13.{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}.14.x(P(x)∨Q(x)).15.21.第5页共17页16.(R(a)∧R(b))→(S(a)∨S(b)).17.{(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. B.13. A.14.A.15.D三、计算证明题1. 12464623(1) 91B1,3;3.A18,12,90+;1.2.R={(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.1414231 0 0 01 1 0 01110111111011113.(1)•＝((x))＝(x)+3＝2x+3＝2x+3.(2)•＝((x))＝(x)+3＝(x+3)+3＝x+6,(3)•＝((x))＝(x)+3＝x/4+3,(4)•＝((x))＝(x)/4＝2x/4=x/2,(5)••＝•(•)＝•+3＝2x/4+3＝x/2+3.第6页共17页4. (1)P(a,f(a))∧P(b,f(b))=P(3,f(3))∧P(2,f(2))=P(3,2)∧P(2,3)=1∧0=0.(2)xyP(y,x)=x(P(2,x)∨P(3,x))=(P(2,2)∨P(3,2))∧(P(2,3)∨P(3,3))=(0∨1)∧(0∨1)485.(1)48

=1∧1=1.2168124621无最大 元，最小元1，极大元8,12;2168124621B无 上界，无最小上界。下界1,2;最大下界2.6. G=(P→Q)∨(Q∧(P→R))=(P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧P)∨(Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)=m3∨m4∨m5∨m6∨m7=(3,4,5,6,7).第7页共17页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)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)},s(R)＝R∪R－1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)},t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；关系图:abr(R)

ddccdcs(R)

dababc11.G＝(P∧Q)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3＝(3,6,7)H=(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7第8页共17页＝(3,6,7)G,H的主析取范式相同，所以G=H.10R13. (1)M R000

0 1 000 1 00 0 1000 0

0 1 0 010 0 1 1M S 0 0 0 001 01 0 0 (2)R•S＝{(a,b),(c,d)},R∪S＝{(a,a),(a,b),(a,c),(b,c),(b,d),(c,d),(d,d)},R－1＝{(a,a),(c,a),(c,b),(d,c)},S－1•R－1＝{(b,a),(d,c)}.四证明题1.证明：{P→QR→SP∨R}Q∨S(1)P∨RP(2)R→PQ(1)(3)P→QP(4)R→QQ(2)(3)(5)Q→RQ(4)(6)R→SP(7)Q→SQ(5)(6)(8)Q∨SQ(7)2.证明：(A-B)-C=(A∩~B)∩~C=A∩(~B∩~C)=A∩~(B∪C)=A-(B∪C)第9页共17页证明：{A∨B, C→B, C→D}蕴涵A→DA D(附加)A∨B P(3)B Q(1)(2)(4)C→B P(5)B→C (6)C Q(3)(5)(7)C→D P(8)D Q(6)(7)(9)A→D D(1)(8)所以{A∨B, C→B, C→D}蕴涵A→D.证明：A－(A∩B)=A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝∪(A∩~B)＝(A∩~B)＝A－B而=(A∪B)∩~B=(A∩~B)∪(B∩~B)=(A∩~B)∪=A－B第10页共17页所以：A－(A∩B)=(A∪B)－B.离散数学试题（A卷及答案）（10分）A、B、CD423个条件，有几种派法？如何派？ACD1个人；BC不能都去；CD留下。解 设去工作去工作去工作去工作则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此(ACD)∧(B∧C)∧(CD)(A∨(C∧D)∨(C∧D))∧(B∨C)∧(C∨D)(A∨(C∧D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))D∧C∧D)∧C∧D)(C∧D)∨F

(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧DF∨F∨(A∧C)∨F∨F∨(C∧D∧B)∨F∨F∨(C∧D∧B)∨F∨(A∧C)∨(B∧C∧D)∨(C∧D∧B)∨(C∧D)(A∧C)∨(B∧C∧D)∨(C∧D)T故有三种派法：B∧D，A∧C，A∧D。（15分且是工人，有些成员是青年人，所以，有些成员是青年专家。第11页共17页Sx)x是专家；Wx)xYx)xx(S(x)∧W(x))，xY(x)下面给出证明：x(S(x)∧Y(x))(1)xY(x)P(2)Y(c)T(1)，ES(3)x(S(x)∧W(x))P(4)S(c)∧W(c)T(3)，US(5)S(c)T(4)，I(6)S(c)∧Y(c)T(2)(5)，I(7)x(S(x)∧Y(x))T(6)，EG（10分）A、BCAB(BA)。证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)A))

(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈(BA)。（15分）A＝{1，2，3，4，5}，RAR＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>}R2＝{<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>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 it(R)＝R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，i1第12页共17页1>，<5，4>，<5，5>}。（10分）RARr(Rt(R的。证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。下证对任意正整数n，Rn对称。因RR2(xR∧)(Rx∧R)R2R2Rn对称，xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1Rn1Rn对称。xmyt(R)x是对称的。（10分）f：A→Bf－1：B→A是双射。证明因为f：A→Bf－1BAf－1是双射。对x∈Ay∈Bf(x)＝yf－1(y)＝xf－1是满射。1 1 2 1 2 1 y、y∈Bf－1(y)＝f－1(y)＝xf(x)＝y，f(x)＝yf：A→B1 1 2 1 2 1 综上可得，f－1：B→A是双射。（10设<S，*>Sa*a＝a证明因为<S，*>是一个半群，对任意的b∈S，由*的封闭性可知，b2＝b*b∈S，b3＝b2*b∈S，…，bn∈S，…。S，使得bi＝bj，则bj＝bp*bjq≥i，有bq＝bp*bq。因为p≥1k≥1p≥ibkp∈Sbkp＝bp*bkp＝bp*(bp*bkp)＝…＝bkp*bkp。a＝bkpa∈Sa*a＝a。（20分（1）若G是连通的平面图，且G的每个面的次数至少为(≥3)，则G第13页共17页的边数m与结点数n有如下关系：

m≤l (n－2)。l2rr证明设Gr2m＝dfi≥lrn－m＋r＝2mi1≤l (n－2)。l2（2）G＝<V，E，F>是自对偶图，则|E|＝2(|V|－1)。证明设G*＝<V*，E*>是连通平面图G＝<V，E，F>的对偶图，则G*G，于是|F|＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。第14页共17页离散数学试题（B卷及答案）一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R证明 因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。R PR P(3)P T(1)(2)，I(4)P∨Q P(5)Q T(3)(4)，I(6)QS P(7)S T(5)(6)，I(8)RS CP(9)S∨R T(8)，E（15分设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的个体域人的集合则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x)) ∧B(x))。(1)x(P(x)Q(x)) P(2)x(P(x)∨Q(x)) T(1)，E(3)x(P(x)∧Q(x)) T(2)，E(4)P(a)∧Q(a) T(3)，ES(5)P(a) T(4)，I(6)Q(a) T(4)，I(7)x(P(x)(A(x)∨B(x)) P(8)P(a)(A(a)∨B(a)) T(7)，US(9)A(a)∨B(a) T(8)(5)，I(10)x(A(x)Q(x)) P(11)A(a)Q(a) T(10)，US(12)A(a) T(11)(6)，I(13)B(a) T(12)(9)，I第15页共17页(14)P(a)∧B(a) T(5)(13)，I(15)x(P(x)∧B(x)) T(14)，EG（10分526个会打网球的人都会打另外一种球，求不会打这三种球的人数。解 设A、B、C分别表示会打排球、网球和球的学生集合。则：|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所3以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。3（10分）A1、A2U的子集，则形如()A1、i1A2和A3产生的小项。试由A1、A2和A3所产的所有非空小项的集合构成全集U的一个划。证明 小项共8个，设有r非空小项s1、s2…、sr(r≤8)。a∈aaa3 r r r rasiUsi。又显然有siUU＝si。i1

i1

i1

i1

i1spsqsp≠sqspsqsp∩sq＝。综上可知，{s1，s2，…，sr}是U的一个划分。（15分）RA上的二元关系，则：RR*RR。证明 (5)若R是传递的，则<x，y>∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得即有<x，y>∈R，所以R*RR。R*RRx、y、z∈AxRzzRy，则<x，y>∈R*R，于是有<x，y>∈RR是传递的。（15分）Gn－m＋r＝2，其中，n、m、rG证明 对G的边数m