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

1、一、填空題1 設集合A,B,其中A=1,2,3,B=1,2,則A-B=；(A)-(B)=.2 .設有限集合A,|A|=n,則|(AXA)|=.3 .設集合A=a,b,B=1,2,則從A到B的所有映射是,其中雙射的是.4 .已知命題公式G=(PQ)AR,則G的主析取范式是.5 .設G是完全二叉樹，G有7個點，其中4個葉點，則G的總度數(shù)為,分枝點數(shù)為.6 設A、B為兩個集合，A=1,2,4,B=3,4,則從AB=;AB=;A-B=.7 .設R是集合A上的等價關系，則R所具有的關系的三個特性是,8 .設命題公式G=(P(QR),則使公式G為真的解釋有9 .設集合A=1,2,3,4,A上的關系R=(1

2、,4),(2,3),(3,2),R=(2,1),(3,2),(4,3),則RR2=,R2R=,R2=.10 .設有限集A,B,|A|=m,|B|=n,則|(AB)|=.11設A,B,R是三個集合，其中R是實數(shù)集，A=x|-1<x<1,xR,B=x|0<x<2,xR,則A-B=,B-A=,AAB=,.13 .設集合A=2,3,4,5,6,R是A上的整除，則R以集合形式(列舉法)記為.14 .設一階邏輯公式G=xP(x)xQ(x),則G的前束范式是15 .設G是具有8個頂點的樹，則G中增加條邊才能把G變成完全圖。16 .設謂詞的定義域為a,b,將表達式xR(x)fxS(x)

3、中量詞消除，寫成與之對應的命題公式是17.設集合 A= 1,2, 3,4,A上的二元關系R=(1,1),(1,2),(2,3),S(1,3),(2,3),(3,2)。則RS=、選擇題1 設集合 A=2,a,3,4, B = a,3,4,1,E為全集，則下列命題正確的是 ()(A)2 A (B)a2 設集合 A=1,2,3,AA (C)a B E (D)a,1,3,4上的關系 R=(1,1),(2,2),(2,3),(3,2),(3,3)B.,則R不具備().(A)自反性 (B)傳遞性 (C)對稱性 (D)反對稱性 3設半序集(A, W)關系W的哈斯圖如下所示，若 A的子集B = 2,3,4,5

4、, ()。(A)下界 (B)上界 (C)最小上界(D)以上答案都不對4下列語句中，()是命題。(A)請把門關上(B)地球外的星球上也有人(C)x + 5 > 6 (D)下午有會嗎？5 設 I 是如下一個解釋：D= a,b, P(a,a) P(a,b) P(b,a) P(b,b)1010則在解釋I下取真值為1的公式是().(A) x yP(x,y) (B) x yP(x,y) (C) xP(x,x) (D)6 .若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點的度，能畫出圖的是則元素6為B的4x yP(x,y).().(A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(

5、1,1,1,2,3) (D)(2,3,3,4,5,6).7 .設G H是一階邏輯公式，P是一個i1詞，G=xP(x), H=xP(x),則一階邏輯公式 G H是().(A)恒真的(B)恒假的 (C)可滿足的 (D)前束范式.8設命題公式G=(P Q), H= P (Q P),則G與H的關系是()。(A)G H (B)H G (C)G =H (D)以上都不是.9設A, B為集合，當()時A B=B.(A)A = B (B)A B (C)B A (D)A = B=.10 設集合 A = 1,2,3,4,A上的關系 R= (1,1),(2,3),(2,4),(3,4),則 R具有()。(A)自反性

6、(B)傳遞性 (C)對稱性 (D)以上答案都不對11下列關于集合的表示中正確的為()。(A)aa,b,c (B)aa,b,c(C)a,b,c (D)a,ba,b,c12命題 xG(x)取真值1的充分必要條件是().(A)對任意x, G(x)都取真值1. (B) 有一個x。，使G(x。)取真值1.(C)有某些x,使G(x。)取真值1. (D)以上答案都不對.13 .設G是連通平面圖，有 5個頂點，6個面，則G的邊數(shù)是().(A) 9 條(B) 5 條 (C) 6 條(D) 11 條.14 .設G是5個頂點的完全圖，則從G中刪去()條邊可以得到樹(A)6 (B)5 (C)10 (D)4.15.設圖

7、G的相鄰矩陣為0 11110 10110 110 1010 1110 ,則G的頂點數(shù)與邊數(shù)分別為110().(A)4, 5(B)5, 6(C)4, 10(D)5, 8.三、計算證明題1.設集合人=1,2,3,4,6,8,9,12,R為整除關系。(1)畫出半序集(A,R)的哈斯圖；(2)寫出A的子集B=3,6,9,12的上界，下界，最小上界，最大下界；(3)寫出A的最大元，最小元，極大元，極小元。2. 設集合A=1,2,3,4,A上的關系R=(x,y)|x,yA且xy,求(1)畫出R的關系圖；(2)寫出R的關系矩陣.3. 設R是實數(shù)集合，是R上的三個映射，(x)=x+3,(x)=2x,(x)=x

8、/4,試求復合映射？，？，？，？，？.4. 設I是如下一個解釋：D=2,3,abf(2)f(3)P(2,2)P(2,3)P(3,2)P(3,3)四、證明題1 .利用形式演繹法證明：P-Q2S,PVF蘊涵QVSo2 .設A,B為任意集合，證明：(A-B)-C=A-(BUC).3 .(本題10分)利用形式演繹法證明：AVB,C-B,CfD蘊涵4 .(本題10分)A,B為兩個任意集合，求證：A-(AnB)=(AUB)-B.參考答案一、填空題1. 3;3,1,3,2,3,1,2,3.22. 2n.3. 1=(a,1),(b,1),2=(a,2),(b,2),3=(a,1),(b,2),4=3,4.4.

9、 (PAQAR).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|0WxW1,x12. 12;6.13. (2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6).14. x(P(x)VQ(x).15. 21.16. (R(a)AR(b)f(S(a)VS(b).17. (1,

10、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.Af D=( a,2),(b,1);R.13.A.14.A.15.D三、計算證明題1.(2) B無上界，也無最小上界。下界1,3;最大下界是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).(2) Mr3. (1)? =( (x)=(2) ?=(x)=(3) ?=(x)=(4) ?=(x)=(5)

11、 ? = ?(?4. (1)Ra,f ( a)AP(b,110011101111(x)+3=2x+3=2x+3.(x)+3=(x+3)+3=x+6,(x)+3=x/4+3,(x)/4=2x/4=x/2,)=?+3=2x/4+3=x/2+3.f(b)=P(3,f(3)AR2,f(2)=P(3,2)AP(2,3)=0.(2)xyP(y,x)=x(P(2,x)VP(3,x)=(P(2,2)VP(3,2)A(P(2,3)VP(3,3)=(0V1)A(0V1)=1A1=1.5.(1)(2) 無最大元，最小元1,極大元8,12;極小元是1.(3) B無上界，無最小上界。下界1,2;最大下界2.6.G=(P

12、-Q)V(QA(P-R)=(PVQ)V(QA(PVR)=(PAQ)V(QA(PVR)=(PAQ)V(QAP)V(QAR)=(PAQAR)V(PAQR)V(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)=(PAQAR)V(PAQR)V(PAQAR)V(PAQAR)V(PAQAR)=m3VmVmVm6Vm=(3,4,5,6,7).7.G=(xP(x) V yQy)- xR(x)(xP(x)VyQy)VxR(x)xP(x)AyQy)vxRx)=(x P(x) Ay Qy) v zRz)=x y z(P(x) A Qy) VRz)11. G=(PAQ)V(PAQAR)=(PAQAR)V(

13、PAQAR)V(PAQAR)=naVmVm=(3,6,7)H=(PV(QAR)A(QV(PAR)=(PAQ)V(QAR)V(PAQAR)PA QA R)=(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)V(=(PAQAR)V(PAQAR)V(PAQAR)=m6VmVm=(3,6,7)G,H的主析取范式相同，所以G=H.1010001013.(1)Mr000100000100MsS00110000d),2.證明：(A-B)-C=(AnB)nC=an(bnc)=an(BuC)=A-(BUC)3.證明:AVB,CfB,CfD蘊涵ZDD（附加）AVBQ(1)(2)CfB(5)BQ(4)(

14、6)CQ(3)(5)(8)DQ(6)(7)(9)AD(1)(8)所以AVB,CfB,CfD蘊涵A-D.4.證明：A-(AAB)=an(anB)=An(AUB)=(An-a)u(An-b)=U(An-B)=(An-b)=A-B而(AUB)-B=(AUB)nB=(An-b)u(Bn-b)=(An-B)u=A-B所以：A-(APB)=(AUB)B.32320011試求(1)Ra,f(a)AP(b,f(b);(2)xyP(y,x).5.設集合A=1,2,4,6,8,12,R為A上整除關系。(1)畫出半序集(A,R)的哈斯圖；(2)寫出A的最大元，最小元，極大元，極小元；(3)寫出A的子集B=4,6,8

15、,12的上界，下界，最小上界，最大下界6.設命題公式G=(P-Q)V(QA(PR),求G的主析取范式。7.(9分)設一階邏輯公式：G=(xRx)VyQ(y)一xR(x),把G化成前束范式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)的關系圖.11.通過求主析取范式判斷下列命題公式是否等價：(1)G=(PAQ)V(PAQAR)(2)H=(PV(QAR)A(QV(PAR)13.設R和S是集合A=a,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)計算R?S,RUS,R*12,S1?R1.9.(1)r(R)=RUIA=(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d),s(R)=RUR1=(a,b),(b,a),(b,c),(c,b)(c,d),(d,c),t(R)=RUR2UR3UR4=(a,a),(