离散数学试题

1、一、填空题1设会合A,B，其中A1,2,3,B=1,2,则A-B_;(A)-(B)_.2.设有限会合A,|A|=n,则|(AA)|=_.3.设会合A=a,b,B=1,2,则从A到B的所有照耀是_,其中双射的是_.4.已知命题公式G(PQ)R，则G的主析取范式是_.5.设G是完好二叉树，G有7个点，其中4个叶点，则G的总度数为_，分枝点数为_.6设A、B为两个会合,A=1,2,4,B=3,4,则从AB_;AB_;AB_.7.设R是会合A上的等价关系，则R所拥有的关系的三个特色是_,_,_.8.设命题公式G(P(QR)，则使公式G为真的解说有_，_,_.9.设会合A1,2,3,4,A上的关系R=(

2、1,4),(2,3),(3,2),R=(2,1),(3,2),(4,3),则RR=1112_,R2R1=_,2R1=_.10.设有限集A,B，|A|=m,|B|=n,则|(AB)|=_.设A,B,R是三个会合，其中R是实数集，A=x|-1x1,xR,B=x|0 x6(D)下午有会吗345设I是以下一个解说：P(a,a)P(a,b)P(b,a)P(b,b)2Da,b,01011则在解说I下取真值为1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).6.若供选择答案中的数值表示一个简单图中各个极点的度，能画出图的是().(A)(1,2,2,3,4

3、,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7.设G、H是一阶逻辑公式，P是一个谓词，GxP(x),HxP(x),则一阶逻辑公式GH是().(A)恒真的(B)恒假的(C)可满足的(D)前束范式.8设命题公式G(PQ)，HP(QP)，则G与H的关系是()。(A)GH(B)HG(C)GH(D)以上都不是.9设A,B为会合，当()时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拥有()。(A)自反性(B)传达性(C)对称性(D)以上答案都不对11以

4、下对于会合的表示中正确的为()。(A)aa,b,c(B)aa,b,c(C)a,b,c(D)a,ba,b,c12命题xG(x)取真值1的充分必要条件是().对随意x，G(x)都取真值1.(B)有一个x0，使G(x0)取真值1.(C)有某些x，使G(x0)取真值1.(D)以上答案都不对.13.设G是连通平面图，有5个极点，6个面，则G的边数是().(A)9条(B)5条(C)6条(D)11条.14.设G是5个极点的完好图，则从G中删去()条边能够获取树.(A)6(B)5(C)10(D)4.0111115.设图G的相邻矩阵为10100，则G的极点数与边数分别为().110111010110110(A)

5、4,5(B)5,6(C)4,10(D)5,8.三、计算证明题1.设会合A1,2,3,4,6,8,9,12，R为整除关系。画出半序集(A,R)的哈斯图；写出A的子集B=3,6,9,12的上界，下界，最小上界，最大下界；写出A的最大元，最小元，极大元，极小元。2.设会合A1,2,3,4，A上的关系R(x,y)|x,yA且xy,求画出R的关系图；写出R的关系矩阵.设R是实数会合，,是R上的三个照耀，(x)=x+3,(x)=2x,(x)x/4,试求复合照耀，,，.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

6、(a)P(b,f(b);xyP(y,x).设会合A1,2,4,6,8,12，R为A上整除关系。画出半序集(A,R)的哈斯图；写出A的最大元，最小元，极大元，极小元；(3)写出A的子集B=4,6,8,12的上界，下界，最小上界，最大下界.设命题公式G=(PQ)(Q(PR),求G的主析取范式。7.(9分)设一阶逻辑公式：G=(xP(x)yQ(y)xR(x)，把G化成前束范式.9.设R是会合A=a,b,c,d.R是A上的二元关系,R=(a,b),(b,a),(b,c),(c,d),求出r(R),s(R),t(R)；画出r(R),s(R),t(R)的关系图.经过求主析取范式判断以下命题公式能否等价：G

7、=(PQ)(PQR)H=(P(QR)(Q(PR)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)111.计算RS,RS,R,SR四、证明题利用形式演绎法证明：PQ,RS,PR蕴涵QS。2.设A,B为任意会集，证明：(A-B)-C=A-(BC).3.(此题10分)利用形式演绎法证明：AB,CB,CD蕴涵AD。4.(此题10分)A,B为两个任意会集，求证：A(AB)=(AB)B.参照答案一、填空题3;3,1,3,2,3,1,2,3.2n2.1=(a,1),(b,

8、1),2=(a,2),(b,2),3=(a,1),(b,2),4=(a,2),(b,1);3,4.(PQR).12,3.4,1,2,3,4,1,2.自反性；对称性；传达性.(1,0,0),(1,0,1),(1,1,0).(1,3),(2,2),(3,1);(2,4),(3,3),(4,2);(2,2),(3,3).2mn.x|-1x0,xR;x|1x2,xR;x|0 x1,xR.12;6.(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6).x(P(x)Q(x).21.(R(a)R(b)(S(a)S(b).(1,3),(2,2);(1,1),(1,2)

9、,(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.812(1)469231(2)B无上界，也无最小上界。下界1,3;最大下界是3.A无最大元，最小元是1，极大元8,12,90+;极小元是1.(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4).(1)142310001100(2)MR110111113.(1)(x)(x)+32x+32x+3.(2)(x)(x)+3(x+3)+3x+6,(3)(x)(x)+3x/4+3,

10、(4)(x)(x)/42x/4=x/2,(5)()+32x/4+3x/2+3.(1)P(a,f(a)P(b,f(b)=P(3,f(3)P(2,f(2)P(3,2)P(2,3)100.xyP(y,x)=x(P(2,x)P(3,x)(P(2,2)P(3,2)(P(2,3)P(3,3)(01)(01)111.(1)812462(2)无最大元，最小元1，极大元8,12;极小元是1.(3)B无上1界，无最小上界。下界1,2;最大下界2.G=(PQ)(Q(PR)(PQ)(Q(PR)(PQ)(Q(PR)(PQ)(QP)(QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(

11、PQR)(PQR)(PQR)m3m4m5m6m7=(3,4,5,6,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)(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)；关系图:adadadbcbcbc

12、r(R)s(R)t(R)G(PQ)(PQR)(PQR)(PQR)(PQR)m6m7m3(3,6,7)=(P(QR)(Q(PR)(PQ)(QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m6m3m7(3,6,7)G,H的主析取范式相同，所以G=H.101001000010001113.(1)MR001MS0000000000001(2)RS(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蕴涵QS(1)PRP(2)RPQ(1)(3)PQPRQQ(2)(3)QRQ(4)(6)RSP(7)QSQ(5)(6)(8)QSQ(7)证明：(A-B)-C=(AB)CA(BC)A(BC)