離散數(shù)學(xué)考試模擬試題及詳細(xì)參考答案共四套

1、離散模擬答案11命題符號化(共 6小題，每小題3分，共計18分)1 .用命題邏輯把下列命題符號化a)假如上午不下雨，我去看電影，否則就在家里讀書或看報。b)我今天進(jìn)城，除非下雨。c)僅當(dāng)你走，我將留下。2 .用謂詞邏輯把下列命題符號化a)有些實(shí)數(shù)不是有理數(shù)b)對于所有非零實(shí)數(shù) x,總存在y使彳導(dǎo)xy=1。c) f是從A到B的函數(shù)當(dāng)且僅當(dāng)對于每個aC A存在唯一的bC B,使得f(a)=b.一、簡答題(共6道題，共32分)1 .求命題公式(P一 (QfR) (R一 (Q-P)的主析取范式、主合取范式，并寫出所有成真賦 值。(5分)2 .設(shè)個體域?yàn)?,2,3,求下列命題的真值(4分)a) x y(

2、x+y=4)b) y x (x+y=4)3 .求 x(F(x) 一 G(x) 一( xF(x) 一 xG(x)的前束范式。(4 分)4 .判斷下面命題的真假，并說明原因。(每小題2分，共4分)a)(AB) C=(A-B)(A-C)b)若f是從集合A到集合B的入射函數(shù)，則|A| w |B|5 .設(shè)A是有窮集，|A|=5 ,問(每小題2分，共4分)a) A上有多少種不同的等價關(guān)系？b)從A到A的不同雙射函數(shù)有多少個？6 .設(shè)有偏序集<A,w>,其哈斯圖如圖1,求子集B=b,d,e的最小元，最大元、極大元、 極小元、上界集合、下界集合、上確界、下確界，(5分)圖17 .已知有限集S=a1

3、,a2,an,N為自然數(shù)集合，R為實(shí)數(shù)集合，求下列集合的基數(shù)S;P(S);N,N n;P(N);R,R X R,o,1 N (寫出即可)(6 分)二、證明題(共3小題，共計40分)1 .使用構(gòu)造性證明，證明下面推理的有效性。(每小題5分，共10分)a) Z (BAC),(E 一 F) 一 C, B 一 (A A S) B一 Eb) x(P(x) - Q(x), x(Q(x) V R(x) , x R(x) x P(x)2 .設(shè)Ri是A上的等價關(guān)系，R2是B上的等價關(guān)系，A豐 且BW ，關(guān)系R滿足： <<x1,y1>,<x2,y2>> C R,當(dāng)且僅當(dāng) <

4、; x 1, x2> C R1 且<y 1,y2> C R2。試證明：R 是 AXB 上的 等價關(guān)系。(10分)3 .用伯恩斯坦定理證明(0,1和(a,b)等勢。(10分)4 .設(shè)R是集合A上的等價關(guān)系，A的元素個數(shù)為n, R作為集合有s個元素，若A關(guān)于R 的商集A/R有r個元素，證明：rs>n2o (10分)三、應(yīng)用題( 10 分)在一個道路上連接有8 個城市，分別標(biāo)記為 a,b,c,d,e,f,g,h 。城市之間的直接連接的道路是單向的，有a-b, a -c, b -g, g -b, c - f, f -e, b -d, d -f.對每一個城市求出從它出發(fā)所能夠到達(dá)

5、的所有其他城市。離散數(shù)學(xué) 考試題答案一、命題符號化(共6 小題，每小題 3 分，共計 18 分)1. 用命題邏輯把下列命題符號化a)設(shè)P表示命題“上午下雨” ，Q表示命題“我去看電影”，R表示命題“在家里讀書”，S表示命題“在家看報” ，命題符號化為： ( P? Q)(P? R S)b)設(shè)P表示命題“我今天進(jìn)城”，Q表示命題“天下雨"，命題符號化為：CH P或 A Qc)設(shè)P表示命題“你走” ，Q表示命題“我留下"，命題符號化為：Q-P2. 用謂詞邏輯把下列命題符號化a) 設(shè) R(x) 表示“ x 是實(shí)數(shù)” ， Q(x) 表示“ x 是有理數(shù)” ，命題符號化為：x(R(x)

6、 Q(x)或 x(R(x) -Q(x)b) 設(shè) R(x) 表示“ x 是實(shí)數(shù)” ， E(x,y) 表示“ x=y ” ,f(x,y)=xy, 命題符號化為：x(R(x) E(x,0) - y(R(y) E(f(x,y),1)c)設(shè)F(f)表示“ f是從A至ij B的函數(shù)”,A(x)表布 “ x C A”，B(x)表布 “ x C B ”，E(x,y)表不x=y ” , 命題符號化為：F(f)? a(A(a)f b(B(b) E(f(a),b)c(S(c) E(f(a),c) - E(a,b)6 道題，共 32 分)1. (P-(Qf R)(Rf (Qf P)( P Q R)(P Q R)(P

7、Q R) - (P Q R)(P Q R)-P Q R) ).( ( P QR)(P(P Q R) ( P公式的所有成真賦值為Q R)( P Q R) ( P Q R) )Q R) 這是主合取范式000,001,010,100,101,111, 故主析取范式為P Q R (PQR ( PQ R (PQ R (P QR (PQR2. a) T b) F3. x(F(x) - G(x) - ( xF(x) - xG(x) x(F(x) - G(x) - ( yF(y) - zG(z) x(F(x) -G(x)- y z(F(y) -G(z) x y z(F(x) - G(x) - (F(y) -G

8、(z)4. a) 真命題。因?yàn)? A B) C=(A B)C= (A C)(B C) =(A-C )(B-C)b)真命題。因?yàn)槿绻鹒是從集合A到集合B的入射函數(shù)，則|ranf|=|A|,且ranf B,故命 題成立。5. a) 52 b) 5!=1206. B的最小元是b,無最大元、極大元是d和e、極小元是b、上界集合是g、下界集合是a,b、上確界是g、下確界是b.7. KS=n;KP(S)=2n ;KN= o,KN n= o,KP(N)=；KR= , K=R 乂 R=,K0,1N=# / 2oi.a)證(D BP(附加條件)(2) B-(AA S) P(3) AA S T(i)(2) I(4

9、) AT(3) I(5) A一 (BAC)P(6) BA CT(4)(5) ICT(6) I(8) (E一 F) 一 C P(9)(E - F)T(8) I(i0) EA FT(9) E(ii) ET(i0) I(i2) B一 ECPb)證(i)x R(x)P(2)R(c)ES(i)(3)x(Q(x) V R(x) P(4) Q(c)V R(c) US(3)(5) Q(c)T(2)(4) I(6)x(P(x) - Q(x) P P(c)一 Q(c) US(6)(8)P(c)T(5) I(9)x P(x)EG(8)2.證任取<x,y>,三、證明題（共3小題，共計40分）<x,y

10、>C AX B xC A y C B 任取 <<x,y>,<u,v>>,<x,x> e Ri <y,y> £ R2<<x,y>,<x,y>> C R,故 R是自反的<<x,y >,<u,v>> £ R <x,u> £ Ri <y,v> £ R2 <u,x> £ Ri <v,y> £ R2 <<u,v>,<x,y>>

11、C R.故 R是對稱的。任取 <<x,y >,<u,v>>,<<u,v>,<s,t>>CR<<x,y >,<u,v>>,<<u,v>,<s,t>> CR <x,u> C Ri <y,v> C R2 <u,s> Ri <v,t> R2 (<x,u> £ Ri <u,s> C Ri) (<y,v> C R2 <v,t> e R2) <x,s>

12、; Ri <y,t> C R2 <<x,y>,<s,t>> C R,故 R 是傳遞的。綜上所述R是AXB上的等價關(guān)系。a3.證 構(gòu)造函數(shù) f: (0,i 一(a,b) , f(x)= xb一,顯然f是入射函數(shù)2構(gòu)造函數(shù) g: (a,b) 一 (0,i , g(x)顯然g是入射函數(shù),故（0,i和（a,b）等勢。m,m2r2mr2n2r4.證 設(shè)商集A/R的r個等價類的元素個數(shù)分別為mi,m2,mr,由于一個劃分對應(yīng)一個等11 / 202mr，一22價關(guān)系，mi+m2+mr=n, mi m22m2m-m2叱 (r個數(shù)的平方的平均值大于等于這r2 sn

13、or個數(shù)的平均值的平方)，所以 ，即rs n2 r r四、應(yīng)用題(10分)解把8個城市作為集合 A的元素，即A=a,b,c,d,e,f,g,h,在A上定義二元關(guān)系R, <x,y>C R當(dāng)且僅當(dāng)從x到y(tǒng)有直接連接的道路，即R=<a,b>,<a,c>,<b,g>,<g,b>,<c,f>,<f,e>,<b,d>,<d,f> 那么該問題即變?yōu)榍?R的傳遞閉包。0 11111100 0 0 1 1 1 1 00 0 0 0 1 1 0 00利用 Warshal算法，求得t(R尸00 0 110 0

14、0 0 0 0 0 00 0 0 00 10 10 0 0 010 0 011100 0 0 0那么從城市x出發(fā)能到達(dá)的城市為(t(R) I A) xy | x, yt(R) x y,故有(t(R) I A) ab,c,d,e, f ,g(t(R) I a )bd,e, f,g(t(R) I a)c e, f(t(R) IA)d e, f(t(R) Ia) fe(t(R) I a) gb,d,e, f(t(R) I a)e(t(R) I a )e離散考試模擬試題及答案 2一、填空題1 設(shè)集合 A,B,其中 A = 1,2,3, B= 1,2, 則 A - B =(B)= 2 .設(shè)有限集合 A,

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

16、4, A 上的關(guān)系 Ri = (1,4),(2,3),(3,2), R 1 = (2,1),(3,2),(4,3),則R1?R2 = ,R 2?R1 =,R12 =.10 . 設(shè)有限集 A, B ， |A| = m, |B| = n, 則| | (A B)| = .11 設(shè) A,B,R 是三個集合，其中 R 是實(shí)數(shù)集，A = x | -1 <x< 1, x R, B = x | 0 <x < 2, x R,則 A-B = , B-A = ,APB = ,.13 .設(shè)集合A = 2, 3, 4, 5, 6, R是A上的整除，則R以集合形式(列舉法)記為.14 . 設(shè)一階邏

17、輯公式G = xP(x) xQ(x) ， 則 G 的前束范式是15 .設(shè) G 是具有 8個頂點(diǎn)的樹，則 G 中增加 條邊才能把G 變成完全圖。16 .設(shè)謂詞的定義域?yàn)閍, b,將表達(dá)式 xR(x)f xS(x)中量詞消除，寫成與之對應(yīng)的命題公式是 .17 .設(shè)集合 A = 1,2, 3, 4 , A 上的二元關(guān)系 R=(1,1),(1,2),(2,3), S = (1,3),(2,3),(3,2)。則RS=,R2=.、選擇題設(shè)集合A=2,a,3,4 , B = a,3,4,1 , E為全集，則下列命題正確的是 ()o(A)2 A (B)a A (C)a B E (D)a,1,3,4 B.設(shè)集合

18、 A=1,2,3,A 上的關(guān)系 R=(1,1),(2,2),(2,3),(3,2),(3,3)，則 R 不具備().(A)自反性(B)傳遞性(C)對稱性(D)反對稱性設(shè)半序集(A, W)關(guān)系w的哈斯圖如下所示，若A的子集B = 2,3,4,5,則元素6為B的)。(A)下界卜列語句中，( (A)請把門關(guān)上 (C)x + 5 > 6(B)上界(C)最小上界(D)以上答案都不對)是命題。(B)地球外的星球上也有人(D)下午有會嗎？設(shè)I是如下一個解釋：D=a,b,P(a,a) P(a,b) P(b,a) P(b,b)則在解釋I下取真值為1的公式是(A) x yP(x,y) (B) x yP(x,

19、y) (C)0 ). xP(x,x)(D) x yP(x,y).6.若供選擇答案中的數(shù)值表示一個簡單圖中各個頂點(diǎn)的度，能畫出圖的是).(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).7.設(shè)G、H是階邏輯公式,P是一個謂詞，G =xP(x), H= xP(x)，則一階邏輯公式 G H是().(A)恒真的設(shè)命題公式(A)G H(B)恒假的G= (P Q)(B)H G(C)可滿足的H = P (QP),則(D)前束范式.G與H的關(guān)系是()o10設(shè)A, B為集合，當(dāng)(A)A = B (B)A B 設(shè)集合 A = 1,2,3,

20、4, A(C)G = H)時 A B = B.(C)B A(D)以上都不是.(D)A=B=.上的關(guān)系 R=(1,1),(2,3),(2,4),(3,4),則 R 具有(1112(A)自反性(B)傳遞性下列關(guān)于集合的表示中正確的為(A)a a,b,c(B)a a,b,c命題xG(x)取真值1的充分必要條件是(C)對稱性)。(D)以上答案都不對(C)a,b,c().(D)a,b a,b,c(A)對任意x, G(x)都取真值1.(C)有某些x,使G(x0)取真值1.13.設(shè)G是連通平面圖，有 5個頂點(diǎn),(A) 9 條(B) 5 條14 .設(shè)G是5個頂點(diǎn)的完全圖,(A)6(B)5(C)100115 .

21、設(shè)圖G的相鄰矩陣為 ，111(C) 6 條(B)有一個xo,使G(xo)取真值1.(D)以上答案都不對.6個面，則G的邊數(shù)是().(D) 11 條.則從 G中刪去()條邊可以得到樹.10100(D)4.110111010110 ,則G的頂點(diǎn)數(shù)與邊數(shù)分別為().110(A)4, 5、計算證明題(B)5, 6(C)4, 10(D)5, 8.1.設(shè)集合 A = 1,2, 3, 4, 6, 8, 9, 12 , R 為整除關(guān)系。(1)畫出半序集(A,R)的哈斯圖;(2)寫出A的子集B = 3,6,9,12的上界，下界，最小上界，最大下界;(3)寫出A的最大元，最小元，極大元，極小元。2. 設(shè)集合 A

22、= 1,2, 3, 4, A 上的關(guān)系 R= (x,y) | x, y A 且 x y,求(1)畫出R的關(guān)系圖；(2)寫出R的關(guān)系矩陣.3.設(shè)R是實(shí)數(shù)集合，映射？，？，？，,是R上的三個映射， ? ,? ?.(x) = x+3,(x) = 2x,(x)=x/4,試求受H4.設(shè)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)AP(b,f(b);(2) x y P (y, x).5 .設(shè)集合人=1,2, 4, 6, 8,12, R為A上整除關(guān)系。(1)畫出半序集(A,R)的哈斯圖；(

23、2)寫出A的最大元，最小元，極大元，極小元；(3)寫出A的子集B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.6 .設(shè)命題公式 G = (P-Q)V(QA( P-R),求G的主析取范式。7 . (9分)設(shè)一階邏輯公式：G = ( xP(x)V yQ(y)一 xR(x),把G化成前束范式.9 .設(shè) R 是集合 A = a, b, c, d. R 是 A 上的二元關(guān)系,R = (a,b), (b,a), (b,c), (c,d),(1)求出 r(R), s(R), t(R);(2)畫出r(R), s(R), t(R)的關(guān)系圖.11.通過求主析取范式判斷下列命題公式是否等價：(1)

24、G = (P A Q) V ( PAQAR)(2) H = (P V (Q A R) A (Q V ( PA R)13.設(shè) R和 S是集合 A=a, b, c, d上的關(guān)系,其中 R=(a, a),(a, c),(b, c),(c, d),S= ( a, b),(b, c),(b, d),(d, d).(1)試寫出R和S的關(guān)系矩陣；(2)計算 R?S, RU S, R 1, S 1?R 1.四、證明題1 .利用形式演繹法證明：P-Q, R-S, PVR蘊(yùn)涵QVS。2 .設(shè)A,B為任意集合，證明：(A-B)-C = A-(B U C).3 .(本題10分)利用形式演繹法證明： A VB, C-

25、B, C-D蘊(yùn)涵A-D。4 .(本題10分)A, B為兩個任意集合，求證：A - (A n B) = (A U B)-B .參考答案一、填空題1. 3；3,1,3,2,3,1,2,3.2.22n3. 1= (a,1), (b,1),2= ( a,2), (b,2), 3= ( a,1), (b,2), 4= ( a,2), (b,1); 3,4. (PA QA 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,

26、2); (2,2),(3,3).4.10.2m n11. x | -1 < x < 0, x R; x | 1 < x < 2, x R; x | 0 <x< 1, x R.12. 12; 6.13. (2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6).14. x( P(x) V Q(x).15. 21.16. (R(a) A R(b) 一 (S(a) V S(b).17. (1, 3),(2, 2); (1, 1),(1,2),(1, 3).二、選擇題1.C.2.D.3.B.4.5.D.6.C.7

27、.C.8. A. 9. D. 10. B. 11.13. A. 14. A. 15. D三、計算證明題B.B.1.(2) B無上界，也無最小上界。下界 1, 3;最大下界是3.(3) A無最大兀，最小兀是 1,極大兀8, 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).(2) Mr4210 0 0110 0111011113) (1) ?= ( (x)= (x)+3 =2x+3 =2x+3.(2) ? = ( (x)= (x)+3 = (x+3)+3 =x+6,(3) ? = ( (

28、x)= (x)+3 = x/4+3,(4) ? = ( (x) = (x)/4 = 2x/4 = x/2,(5) ? ? = ?( ?)= ? +3=2x/4+3 =x/2+3.4) (1) P(a, f (a) A P(b, f (b) = P(3, f (3) A P(2, f (2)=P(3, 2) A P(2, 3)=1 A 0=0.5) ) x y P (y, x) = x (P (2, x) V P (3, x)=(P (2, 2) VP (3, 2) A (P (2, 3) VP (3, 3)=(0 V1)A (0V 1)=1.5. (1)(2)無最大6) ) B無上元，最小元1

29、,極大元8,12;極小元是1.界，無最小上界。下界 1,2;最大下界2.6. G =(P-Q)V(QA( PfR)13 / 20=(PV Q) V (QA (PV R)=(PA Q) V(QA (PVR)=(PA Q) V (Q A P)V (QA R)=(P AQAR) V (PAQAR) V(PAQA R) V (PA QAR) V (PA Q A R) V( PAQA R)=(P AQAR) V (PAQAR) V(PAQA R) V (PA QAR) V ( PA Q AR)=m3Vm4Vm5Vm6Vm7 = (3, 4, 5, 6, 7).7.xP(x) V yQ(y) 一 xR(x

30、)(xP(x) V yQ(y) V xR(x)=(xP(x) AyQ(y)V xR(x)=(x P(x) Ay Q(y)v zR(z)=x y z( P(x)A Q(y)VR(z) 9. (1) r(R) = RU lA = (a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R) = RU R 1 = (a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(R) = RUR2U R3U R4= (a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d),

31、 (c,d);(2)關(guān)系圖：r(R)s(R)t(R)11. G=(PA Q) V ( PA QA R)=(PA QA R)V(PAQ AR)V( PA QA R)=m6Vm7Vm3=(3, 6, 7)H = (PV(QAR)A(QV( PAR)= (PAQ)V(QAR) V( PA QA R)=(PA QA R) V (PA Q AR)V( PA QA R) V (PA Q A R) V ( PA QA R)=(PA QA R) V ( PAQ AR)V(PAQAR)=m6Vm3Vm7G = H.MS SG,H 的主析取范式相同，所以013. (1)MR0(2)R?S=( a, b),(c,

32、d),RU 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-Q, RfS, PVR蘊(yùn)涵 QVS(1) P V R(2)Rf PQ(1)(3) P-Q(4) Rf QQ(2)(3)(5) Qf RQ(4)(6) Rf S(7) Q-SQ(5)(6)(8) Q V SQ(7)2.證明： (A-B)-C = (AnB) nc=a n (b n c)=a n (B u C)證明： AVB,Cf B(1) AD( 附加

33、 )(2)A V BP(3) BQ(1)(2)(4)Cf BP(5) Bf CQ(4)(6) CQ(3)(5)=A-(B U C)3.,CfD蘊(yùn)涵 A-DCfDD(1)(8)(8) DQ(6)(9) A - D所以 A VB,C 一 B, C一D蘊(yùn)涵A一D.4.證明：A - (A A B)=a n (a n B)=A n (A UB)=(A n A) u (A n B) =U (A n B) =(A n B) = A-B而(A U B) - B=(A U B) n B=(An B) u (B n B)=(An B) u=A-B所以：A - (A n B) = (A U B) - B.離散考試模

34、擬試題及答案 3一、填空題：)1 .設(shè)A 2,a,3,4, B a , 3,4,1,請在下列每對集合中填入適當(dāng)?shù)姆?1) aB ,(2) a ,4 ,3 A。0 , x是奇數(shù)，2 .設(shè)A 0,1 , N為自然數(shù)集，f (x)口,中如 若f： A A,則f是1, x是偶數(shù)。射的，若f: NA ,則f是 射的。3 .設(shè)圖G = < V , E >中有7個結(jié)點(diǎn)，各結(jié)點(diǎn)的次數(shù)分別為2, 4, 4, 6, 5, 5, 2,則G中有 條邊，根據(jù) 。4 .兩個重言式的析取是, 一個重言式和一個矛盾式的合取27 / 205 .設(shè)個體域?yàn)樽匀粩?shù)集，命題“不存在最大自然數(shù)” 符號化為 6 .設(shè)S為非

35、空有限集，代數(shù)系統(tǒng) 2S,中幺元為 ，零元為 7 .設(shè)P、Q為兩個命題，其De-Morden律可表示為 8 .當(dāng)G| 8時，群 G , 只能有 階非平凡子群，不能階子群，平凡子群為 。二、單項(xiàng)選擇題：（每小題1分，本大題共15分）1.設(shè)A x | x是整數(shù)且x2 16,下面哪個命題為假（）。A、0,1, 2,4C、A ;2.設(shè) A , B A、 ;A ;B、 3, 2, 1 A ;D、x x是整數(shù)且|x 4 Ao, ,則 B-A 是（）。B、 ；C、, ； D、。3 .下圖描述的偏序集中，子集 b , e , f的上界為 （）。A、b, c ; B、a,b ；貫cC、b ； D、a,b,c。J

36、、/之口d4 .設(shè)f和g都是X上的雙射函數(shù)，則（f g）1為（）。-11-1A、f g ； B、（g f） ; C、5.下面集合（）關(guān)于減法運(yùn)算是封閉的。A、N ; B、2x x I ; C、2x6.具有如下定義的代數(shù)系統(tǒng)G ,（A、G 1,10 ,*是模 11 乘；C、G Q （有理數(shù)集），*是普通加法11g f1 x ID、g f 。D、x x是質(zhì)數(shù)。）不構(gòu)成群。B、G 1,3,4,5,9, *是模 11 乘；D、G Q （有理數(shù)集），*是普通乘法。7.設(shè) G 2m3nm, n I ,*為普通乘法。則代數(shù)系統(tǒng)的幺元為（A、不存在B、e 2030 ；C、eD、8.下面集合（）關(guān)于整除關(guān)系構(gòu)成

37、格。12, 24, 36;B、1 ，2,4, 612；C、1 ， 2,5, 6, 15,30D、3,6,12。9.設(shè)Va,b,c,d,e, f a ,bc,f ,e ,則有向圖A、強(qiáng)連通的; B、單側(cè)連通的C、弱連通的；D、不連通的。10.下面那一個圖可一筆畫出（11.在任何圖中必定有偶數(shù)個A、度數(shù)為偶數(shù)的結(jié)點(diǎn)B、入度為奇數(shù)的結(jié)點(diǎn)C、度數(shù)為奇數(shù)的結(jié)點(diǎn)D、出度為奇數(shù)的結(jié)點(diǎn)12.含有3個命題變元的具有不同真值的命題公式的個數(shù)為A、23 ；B、32 ;C、 223D、23213.下列集合中哪個是最小聯(lián)結(jié)詞集（A、 ； B、C、D、14.下面哪個命題公式是重言式（A、(P Q) (Q R);B、(PQ

38、)C、( P Q) (P Q)D、(PQ)15.在謂詞演算中，下列各式哪個是正確的A、 xyA(x,y) yxA(x,y) ； B、 xyA(x,y) y xA(x, y)；C、 x yA(x, y) y xA(x, y) ；D、A(a) xA(x)。三、判斷改正題：(每小題2分，本大題共20分)A B A B- a1 .設(shè) A 1,2 , B a,則 222。(其中 2A為 (A)()2 .設(shè) A 0,1, B 1,2,則A2 B 0,1,1 , 0,1,2 , 1,0,1 , 1,0,2o ()3 .集合A上的恒等關(guān)系是一個雙射函數(shù)。()4 .設(shè)Q為有理數(shù)集，Q上運(yùn)算*定義為a b max

39、(a,b),則 Q, 是半群。()5 .階數(shù)為偶數(shù)的有限群中，周期為2的元素的個數(shù)一定為偶數(shù)。()6 .在完全二元樹中，若有 t片葉子，則邊的總數(shù) e 2t 1 o()7 .能一筆畫出的圖不一定是歐拉圖。()8 .設(shè)P, Q是兩個命題，當(dāng)且僅當(dāng) P, Q的真值均為T時，P Q的值為T。()9 .命題公式(P (P Q) Q是重言式。()10.設(shè)P(x)： x是研究生，Q(x)：x曾讀過大學(xué),命題“所有的研究生都讀過大學(xué)”x(P(x)Q(x)四、簡答題：(25分)1.設(shè)Aa ,b ,c , A上的關(guān)系r(),s()和1()。2.集合A 2,3,6,12,24,36上的偏序關(guān)系為整除關(guān)系。設(shè)B 6

40、,12,C 2,3,6,試畫出的哈斯圖，并求B , C的最大兀素、極大元素、下界、上確界。G, 7 是否構(gòu)成群？是否為循3 .圖給出的賦權(quán)圖表示五個城市Vi , V2 , V3 , V4 , V5及對應(yīng)兩城鎮(zhèn)間公路的長度。試給出一個最優(yōu)化的設(shè)計 方案使得各城市間能夠有公路連通。4 .已知G 1,2,3,4,5,6,7為模7乘法。試說明環(huán)群？若是，生成元是什么?5 .給定命題公式(P ( Q R) ( S W),試給出相應(yīng)的二元樹。五、證明題：(25分)1 .如果集合 A上的關(guān)系R和S是反自反的、對稱的和傳遞的，證明：R S是A上的等價關(guān)系。2 .用推理規(guī)則證明P(a) G(a)是x(P(x)

41、(Q(x) R(x),(Q(a) R(a) , S(a) , x(S(x) G(x)的有效結(jié)論。3 .若有n個人，每個人都恰有三個朋友，則n必為偶數(shù)。4 .設(shè)G是(11, m)圖，證明G或其補(bǔ)圖G是非平面圖。一、填空題1. (1),4.重言式，矛盾式離散考試模擬試題及答案42.雙射，滿射。3. 14 ,deg(M) 2Evi V5. x y(y x) , 6., S。7. (P Q) P Q, (P Q) P Q;P (P Q) P , P (P Q) P o8. 2, 4; 3, 5, 6, 7;e, G,。1. X2A B2A 2B、單項(xiàng)選擇題題號123456789101112131415答案ACBCBDBCCACCABA三、判斷改正題2. x2A B 0,0,1,0,0,2,0,1,1,0,1,2,1,1,1,1,0,1,1,0,2,1,1,23.