離散數(shù)學(xué)考試題詳細(xì)答案

1、離散數(shù)學(xué)考試題(后附詳細(xì)答案)一、命題符號(hào)化(共 6小題，每小題3分，共計(jì)18分)1 .用命題邏輯把下列命題符號(hào)化a)假如上午不下雨，我去看電影，否則就在家里讀書或看報(bào)。設(shè)P表示命題“上午下雨” ，Q表示命題“我去看電影” ，R表示命題“在家里讀書” ，S表示 命題“在家看報(bào)”，命題符號(hào)化為：(P? Q (P? R S) b)我今天進(jìn)城，除非下雨。設(shè)P表示命題“我今天進(jìn)城”，Q表示命題“天下雨"，命題符號(hào)化為：CH P或P Qc)僅當(dāng)你走，我將留下。設(shè)P表示命題“你走” ，Q表示命題“我留下"，命題符號(hào)化為：Q-P2 .用謂詞邏輯把下列命題符號(hào)化a)有些實(shí)數(shù)不是有理數(shù)設(shè)R(

2、x)表示“ x是實(shí)數(shù)"，Q(x)表示“ x是有理數(shù)"，命題符號(hào)化為：x(R(x) Q(x) 或 x(R(x) - Q(x)b)對(duì)于所有非零實(shí)數(shù) x,總存在y使彳導(dǎo)xy=1。設(shè)R(x)表示“x是實(shí)數(shù)”，E(x,y)表示"x=y"，f(x,y)=xy,命題符號(hào)化為：x(R(x) E(x,0) - y(R(y) E(f(x,y),1)c) f是從A到B的函數(shù)當(dāng)且僅當(dāng)對(duì)于每個(gè)aC A存在唯一的be B,使得f(a)=b.設(shè)F表示“f是從A到B的函數(shù)"，A(x)表示“xC A”，B(x)表示“xC B”，E(x,y)表示“x=y”，命題符號(hào)化為：F(f)

3、? Va(A一三b(B(b) AE(f(a),b) aVc(S(c) a E(f(a),c) - E(a,b)、簡答題(共6道題，共32分)1.求命題公式(P 一 (Q-R)(R- (Q-P)的主析取范式、主合取范式，并寫出所有成真賦值。(5分)(P- (Q-R)(R一 (Q-P)( P(P QR) 一 (PQQR)(PR)(PQ R)Q R) 一(P,g、 R)(P(P Q R)(Q R)八(P處R)( PP Q R)這是主合取范式P QR).QR)公式的所有成真賦值為000,001,010,100,101,111,故主析取范式為(Pa Q R)( Pa QR)(P Q RPaQx R)(P

4、a Qy R)(P Q R2.設(shè)個(gè)體域?yàn)?,2,3,求下列命題的真值(4分)a) xy(x+y=4)b) yx (x+y=4)a) T b) F3.求 x(F(x) 一G(x) 一( xF(x) 一 xG(x)的前束范式。(4 分)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(z)4 .判斷下面命題的真假，并說明原因。(每小題2分，共4分)a)(AB) C=(A-B)(A-C)b)若f是從集合A到集合B

5、的入射函數(shù)，則|A| w |B|a)真命題。因?yàn)?A B) C= (A B)C= (AC)(B C) = (A-C)(B-C)b)真命題。因?yàn)槿绻鹒是從集合A到集合B的入射函數(shù)，則|ranf|=|A|,且ranf B,故 命題成立。5 .設(shè)A是有窮集，|A|=5 ,問(每小題2分，共4分)a) A上有多少種不同的等價(jià)關(guān)系？b)從A到A的不同雙射函數(shù)有多少個(gè)？a) 52 b) 5!=1206 .設(shè)有偏序集<A, w>,其哈斯圖如圖1,求子集B=b,d,e的最小元，最大元、極大元、 極小元、上界集合、下界集合、上確界、下確界，(5分)圖1b、上界集合是g、下界集合是a,b、B的最小兀是

6、 b,無最大兀、極大兀是d和e、極小兀是 上確界是g、下確界是b.7 .已知有限集S=a1,a2,an,N為自然數(shù)集合，R為實(shí)數(shù)集合，求下列集合的基數(shù)S;P(S);N,N n;P(N);R,R X R,o,1 N (寫出即可)(6 分)KS=n;KP(S)= 2n ; KN=0KN n=0, KP(N)=; KR=, K=R X R=,K0,1 Nl=三、證明題(共3小題，共計(jì)40分)1.使用構(gòu)造性證明，證明下面推理的有效性。(每小題5分，共10分)a) 2 (BAC),(E 一 F) 一b) x(P(x) -Q(x),a)證(1) B P(C, Bf(AA S) x(Q(x) VR(x),

7、附加條件)BfEx R(x)x P(x)(2) B-(AA S) P(3) A AS T(1)(2) I(4) A T(3) I一 (BAC)P(6) BC(8) (E(9)(10) E(11) E(12) B b)證(1)(2)(3)(4) Q(c)(5) Q(c)(6)(7) P(c)(8)(9)A C T(4)(5) IT(6) I一F) 一C P(E - F)T(8) IA F T(9) ET(10) I一 ECPx R(x)PR(c) ES(1)x(Q(x) V R(x) PV R(c) US(3)T(2)(4) Ix(P(x) -Q(x) P一 Q(c)US(6)P(c) T(5)

8、 Ix P(x)EG(8)2.設(shè)Ri是A上的等價(jià)關(guān)系，R2是B上的等價(jià)關(guān)系，A豐 且Bw ，關(guān)系R滿足： <<x1,y1>,<x2,y2>> C R,當(dāng)且僅當(dāng) < x 1, x2> C Ri且<y 1,y2> C R2。試證明：R 是 AXB 上的 等價(jià)關(guān)系。(10分)證任取<x,y>,<x,y>CAXB xCA yCB <x,x> C Ri<y,y> R2 <<x,y>,<x,y>> CR,故 R是自反的任取 <<x,y >,<

9、;u,v>>,<<x,y >,<u,v>> C R <x,u> C Ri<y,v> 6 R2 <u,x> C Ri<v,y> e R2 <<u,v>,<x,y>> C R.故R是對(duì)稱的。任取 <<x,y >,<u,v>>,<<u,v>,<s,t>>CR<<x,y >,<u,v>>,<<u,v>,<s,t>> CR <

10、x,u> C Ri <y,v>R2<u,s> C R1<v,t> C R2(<x,u> £ Ri <u,s> £ R1) (<y,v> £ R2<v,t> £ R2) <x,s> Ri <y,t> £ R2 <<x,y>,<s,t>>e r,故r是傳遞的。綜上所述R是AX B上的等價(jià)關(guān)系。3.用伯恩斯坦定理證明(0,1和(a,b)等勢(shì)。(10分)ab證 構(gòu)造函數(shù)f: (0,1 一(a,b) , f

11、(x)= -x+ ，顯然f是入射函數(shù)22x - a構(gòu)造函數(shù)g: (a,b) 一(0,1 , g(x)=，顯然g是入射函數(shù),b a故(0,1和(a,b)等勢(shì)。22.2由于-m2 mr_r22s n,所以一> r r4.設(shè)R是集合A上的等價(jià)關(guān)系，A的元素個(gè)數(shù)為n, R作為集合有s個(gè)元素，若A關(guān)于R的商集A/R有r個(gè)元素，證明：rs>n2o （10分）證 設(shè)商集A/R的r個(gè)等價(jià)類的元素個(gè)數(shù)分別為mi,m2,mr,由于一個(gè)劃分對(duì)應(yīng)一個(gè)等價(jià)關(guān)系，mi+m2+mr=n, m2m1m2 一 一 mr由于-2rim1+m2 +mr |! （r個(gè)數(shù)的平方的平均值大于等于這r個(gè)數(shù)的平均值的平方），所以

12、2n 口口2> ,即 rs > nr四、應(yīng)用題（10分）在一個(gè)道路上連接有 8個(gè)城市，分別標(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.對(duì)每一個(gè)城市求出從它出發(fā) 所能夠到達(dá)的所有其他城市。解 把8個(gè)城市作為集合 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&

13、gt;,<f,e>,<b,d>,<d,f> 那么該問題即變?yōu)榍?R的傳遞閉包。利用 Warshal算法，求得t（R尸11110 11110 0 110 0 0 110 0 0 0 0 0 0 0 10 0 0 11110 0 0 0 0 0那么從城市x出發(fā)能到達(dá)的城市為(t(R) I a)x =y|< x,y* t(R)AX# y,故有(t(R) -I A)a =b,c,d,e, f,g (t(R) -lA)b =d,e, f,g(t(R) Ta)c =e, f(t(R) -lA)d =e,f(t(R) TA)f =e(t(R) TA)g =b,d,e

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

15、;，命題符號(hào)化為：x(R(x) Q(x) 或 x(R(x)- Q(x)b)設(shè)R(x)表示“x是實(shí)數(shù)”，E(x,y)表示"x=y "，f(x,y尸xy,命題符號(hào)化為：x(R(x) E(x,0) - y(R(y) E(f(x,y),1)c)設(shè)F(f)表示“ f是從A至ij B的函數(shù)” “x=y"，命題符號(hào)化為：,A(x)表布 “ x C A ”，B(x)表不“ xC B”,E(x,y)表不F？ Va(A一三b(B(b)八 E(f(a),b)A Vc(S(c) A E(f(a),c) - E(a,b)二、簡答題(共6道題，共32分)1. (P - (Q-R)(P(PaQ

16、-x(R - (Q-P)QR) 一 (PP QR)(PR)(PR)(R)(PR)(PQP Q R)R)這是主合取范式QR)- PR)1PQQR).R)公式的所有成真賦值為(PaQxR)(P Q R2. a) T b) F000,001,010,100,101,111,故主析取范式為PaQR)(Pa QxR)(PQxR)3.x(F(x) x(F(x)G(x) 一(一 G(x)一xF(x) 一 xG(x) y z(F(y) - G(z)x(F(x) - G(x) 一( x y z(F(x)yF(y) - zG(z)>G(x) 一 (F(y)G(z)4.a)b)真命題。(B-C)真命題。因?yàn)?

17、AB) C= (A B)因?yàn)槿绻鹒是從集合A到集合BC= (AC)(B C) = (A-C)的入射函數(shù)，則|ranf|=|A|,且ranf B,故5.6.命題成立。a) 52 b) 5!=120B的最小元是b,無最大元、極大元是d和e、極小元是b、上界集合是g、下界集合是a,b、上確界是g、下確界是b.7. KS=n;KP(S)= 2 n ; KN=0,KN n=。, KP(N)=； KR=, K=R X R尸,K0,1上三、證明題(共3小題，共計(jì)40分)i.a)證(i) BP(附加條件)(2) B-(AAS) P(3) AA ST(i)(2) I(4) AT(3) I(5) A一 (BAC)

18、 P(6) BACT(4)(5) ICT(6) I(8) (E一 FF) 一 C P(9)(JF) 丁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)(7) I(9)x P(x)EG(8)2.證任取<x,y>,<x,y>CAXB xCA yCB <x,x> C Ri <y,y&g

19、t; R2<<x,y>,<x,y>> CR,故 R是自反的任取 <<x,y >,<u,v>>,<<x,y >,<u,v>> C R <x,u> C Ri<y,v> 6 R2<u,x> C Ri <v,y> 6 R2<<u,v>,<x,y>> C R.故R是對(duì)稱的。任取 <<x,y >,<u,v>>,<<u,v>,<s,t>>CR<

20、;<x,y >,<u,v>>,<<u,v>,<s,t>> CR <x,u> Ri<y,v> C R2<u,s> C Ri <v,t> C R2(<x,u> £ Ri<u,s> £ Ri) (<y,v> £ R2 <v,t> £ R2) <x,s> Ri <y,t> £ R2<<x,y>,<s,t>>e r,故r是傳遞的。綜上所述R是AX B上的等價(jià)關(guān)系。ab 一3.證 構(gòu)造函數(shù)f: (0,i 一(a,b) , f(x)= x+ ，顯然f是入射函數(shù)22x -a構(gòu)造函數(shù)g: (a,b) 一(0,i , g(x)=，顯然g是入射函