華科離散數(shù)學(xué)試題與答案試卷

1、離散數(shù)學(xué)試卷與答案試卷一一、填空20% （每小題2 分）1 設(shè) A x | ( xN )且( x5), B x | x E 且x7（ N ：自然數(shù)集，E+正偶數(shù)）則A B。2A ，B ， C 表示三個集合，文圖中陰影部分的集合表達(dá)式為。ABC3設(shè) P，Q 的真值為0，R， S 的真值為1，則(P (Q(RP)( RS)的真值 = 。4公式 ( P R)(SR)P 的主合取范式為。5若解釋 I 的論域 D 僅包含一個元素，則xP(x)xP( x) 在 I 下真值為。6設(shè) A=1 ， 2，3， 4 ，A 上關(guān)系圖為則R2=。7設(shè) A=a ， b，c， d ，其上偏序關(guān)系R 的哈斯圖為則R= 。8圖

2、的補(bǔ)圖為。9設(shè) A=a ， b，c， d ， A 上二元運算如下：1/19*abcdaabcdbbcdaccdabddabc那么代數(shù)系統(tǒng) <A ， *> 的幺元是，有逆元的元素為，它們的逆元分別為。10下圖所示的偏序集中，是格的為。二、選擇 20%（每小題 2分）1、下列是真命題的有（）A a a ；B , ；C ,；D 。2、下列集合中相等的有（）A4，3；B，3，4 ；C4， ，3， 3；D 3，4。3、設(shè) A=1 ，2， 3 ，則 A 上的二元關(guān)系有（）個。323322A2 ；B 3 ；C2；D3。4、設(shè) R，S 是集合 A 上的關(guān)系，則下列說法正確的是（）A 若 R， S

3、是自反的，則RS 是自反的；B 若 R， S 是反自反的，則RS 是反自反的；C若 R， S 是對稱的，則D 若 R， S 是傳遞的，則R S 是對稱的；R S 是傳遞的。5、設(shè) A=1 ，2， 3， 4 ， P（ A ）（ A 的冪集）上規(guī)定二元系如下R s,t| s, t p( A)(| s | | t | 則 P（A ） / R=（）A A ； B P(A) ； C 1，1 ， 2 ， 1 ， 2， 3 ， 1 ， 2，3， 4；D ，2， 2 ，3 ， 2， 3， 4 ， A2/196、設(shè) A=， 1 ， 1 ， 3 ， 1 ， 2， 3 則 A 上包含關(guān)系“”的哈斯圖為（）7、下列函

4、數(shù)是雙射的為（）A f : IE , f (x) = 2x ； B f : NNN, f (n) = <n , n+1>；C f : RI , f (x) = x； D f :IN, f (x) = | x | 。（注： I整數(shù)集， E偶數(shù)集，N 自然數(shù)集， R實數(shù)集）8、圖中從v1 到 v3 長度為 3 的通路有（）條。A 0；B 1；C 2；D 3。9、下圖中既不是Eular 圖，也不是Hamilton 圖的圖是（）10、在一棵樹中有7 片樹葉， 3 個 3 度結(jié)點，其余都是4 度結(jié)點則該樹有（）個4 度結(jié)點。A 1；B2； C3； D4 。三、證明 26%、 R 是集合 X

5、上的一個自反關(guān)系，求證：R 是對稱和傳遞的，當(dāng)且僅當(dāng)< a, b> 和 <a , c>在 R 中有 <.b , c>在 R 中。（ 8 分）、 f 和 g 都是群 <G 1 ,>到 < G2, *> 的同態(tài)映射，證明<C , >是 <G 1, >的一個子3/19群。其中C= x | xG1且 f ( x) g(x) (8 分 )、 G=<V, E>(|V| = v， |E|=e ) 是每一個面至少由k（ k3）條邊圍成的連通平面ek(v2)k2Peterson）圖是非平面圖。（11圖，則，由此證明彼

6、得森圖（分）四、邏輯推演 16%用 CP 規(guī)則證明下題（每小題8 分）1、ABCD,DEFA F2、 x(P(x) Q ( x)xP (x)xQ (x)五、計算18%1、設(shè)集合A=a ， b， c， d 上的關(guān)系R=<a , b > ,< b , a > ,< b, c > , < c , d >用矩陣運算求出 R 的傳遞閉包t (R) 。（ 9 分）2、如下圖所示的賦權(quán)圖表示某七個城市v1 ,v2 , , v7 及預(yù)先算出它們之間的一些直接通信線路造價，試給出一個設(shè)計方案，使得各城市之間能夠通信而且總造價最小。（分）試卷一答案：一、填空 20%

7、（每小題2 分）1、0 ， 1，2， 3， 4， 6 ； 2、 ( BC) A；3、1； 4、( P SR) (PS R) ； 5、1； 6、 <1,1>, <1,3>, <2,2>, <2,4> ； 7、<a.b>,<a,c>,<a,d>,<b,d>,<c,d>IA ；8、4/199、 a ； a , b , c ,d ； a , d , c , d ； 10、c。二、選擇20% （每小題2 分）題目12345678910答案C DB、 CCADCADBA三、證明 26%1、 證：“”

8、a, b,cX若< a,b > ,< a, c >R由R對稱性 知< b, a >, < c, aR ，由 R 傳遞性得 < b,c >R“” 若 < a, b >R ， < a, c >R 有 < b, c >R任 意 a,bX， 因< a,a >R 若 < a, b >R< b, a >R 所以 R 是對稱的。若 < a, b >R ， < b, c >R 則 < b, a > Rb, cR< a, c > R 即 R

9、是傳遞的。2、 證a,b C，有f ( a)g (a), f (b)g(b)，又f (b 1 )f1 (b) ,g(b 1 )g1 (b)f (b 1 )f1 (b)g 1 (b)g(b 1 )f (a b 1 )f (a) * f1 (b) g(a) * g(b 1 )g(a b 1 )a b 1C<C,> 是 <G1, >的子群。3、 證：r2e2ed ( Fi ) rkr 設(shè) G 有 r 個 面 ， 則k 。 而 v e r2 故i 1， 即2 ve rv2eek (v2)ek2 。（8分）k 即得ek(v2)彼得森圖為 k5, e15, vk2 不成立，10 ，

10、這樣5/19所以彼得森圖非平面圖。（3 分）二、邏輯推演16%1、 證明： A A BABCD C D D D EDEF F AF2、證明P（附加前提）T IPT IT IT IPT ICP xP( x) P(c)x(P( x)Q(x) P(c) Q(c) Q( c) xQ (x)xP (x)xQ( x)三、計算 18%1、 解：P（附加前提）USPUST IUG CP6/19MMMM010010101010M R20101R0001MR MR00000000 ，00000101R3M R2M R101000000000，1010R4M R3M R0101000000001111M RMR2

11、MR1111t ( R)3MR400100000t (R)=<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > 2、 解：用庫斯克（Kruskal ）算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：樹權(quán) C(T)=23+1+4+9+3+17=57即為總造價。試卷二試卷與答案一、填空20% （每小題2 分）1、 P：你努力， Q：你失敗。“除非你努力，否

12、則你將失敗”的翻譯為；“雖然你努力了，但還是失敗了”的翻譯為。2、論域 D=1 ， 2 ，指定謂詞P7/19P (1,1)P (1,2)P (2,1)P (2,2)TTFF則公式 xyP( y, x) 真值為。2、 設(shè) S=a 1， a2 ， ， a8 ，B i 是 S 的子集，則由B 31 所表達(dá)的子集是。3、 設(shè) A=2，3，4，5，6 上的二元關(guān)系 R x, y | x y x是質(zhì)數(shù) ，則 R=（列舉法）。R 的關(guān)系矩陣M R=。5、設(shè) A=1 ， 2， 3 ，則 A 上既不是對稱的又不是反對稱的關(guān)系R= ； A 上既是對稱的又是反對稱的關(guān)系R= 。6、設(shè)代數(shù)系統(tǒng)<A ， *>

13、; ，其中 A=a ， b， c,*abcaabcbbbccccb則幺元是；是否有冪等性；是否有對稱性。7、 4 階群必是群或群。8、下面偏序格是分配格的是。9、 n 個結(jié)點的無向完全圖K n 的邊數(shù)為，歐拉圖的充要條件是。10、公式 (P ( P Q) ( P Q)R 的根樹表示為。8/19二、選擇20% （每小題2 分）1、在下述公式中是重言式為（）A(PQ)(P Q) ；B (PQ)( PQ)(QP) ；C (P Q) Q； DP (P Q)。2、命題公式( PQ)( Q P) 中極小項的個數(shù)為（），成真賦值的個數(shù)為（）。A0； B1； C2； D3 。3、設(shè)S ,1, 1,2 ，則2S

14、 有（）個元素。A3； B6； C7； D8 。4、設(shè)S 1,2, 3 ，定義 SS 上的等價關(guān)系R a, b, c,d|a, bS S,c, dSS, a dbc 則由 R 產(chǎn)生的S S上一個劃分共有（）個分塊。A4；B5；C6；D9 。5、設(shè) S 1, 2, 3 ，S 上關(guān)系 R 的關(guān)系圖為則 R 具有（）性質(zhì)。A 自反性、對稱性、傳遞性；B反自反性、反對稱性；C反自反性、反對稱性、傳遞性；D自反性。6、設(shè), 為普通加法和乘法，則（）S,是域。A S x | x a b 3 , a,bQ B S x | x 2n , a,b ZC S x | x 2n 1, n ZD S x | x Z

15、x 0 = N 。7、下面偏序集（）能構(gòu)成格。9/198、在如下的有向圖中，從V 1 到 V 4 長度為 3 的道路有（）條。A1；B2；C3；D4 。9、在如下各圖中（）歐拉圖。10、設(shè) R 是實數(shù)集合，“”為普通乘法，則代數(shù)系統(tǒng)<R ， ×> 是（）。A 群；B獨異點；C半群。三、證明46%1、 設(shè) R 是 A 上一個二元關(guān)系，S a, b| (a, b A) (對于某一個 c A, 有 a, cR且c, bR) 試 證明若R是A上一個等價關(guān)系，則 S 也是 A 上的一個等價關(guān)系。（9 分）2、 用邏輯推理證明：所有的舞蹈者都很有風(fēng)度，王華是個學(xué)生且是個舞蹈者。因此有

16、些學(xué)生很有風(fēng)度。（ 11 分）3、 若 f : A B是從A 到 B 的函數(shù)，定義一個函數(shù)g : B 2 A 對任意 b B 有g(shù)(b) x | ( xA)( f ( x) b) ，證明：若f 是 A 到 B 的滿射，則 g 是從 B 到2 A 的單射。（ 10 分）4、 若無向圖 G 中只有兩個奇數(shù)度結(jié)點，則這兩個結(jié)點一定連通。（8 分）m1 (n 1)( n 2)25、設(shè) G是具有n 個結(jié)點的無向簡單圖，其邊數(shù)2，則 G是10/19Hamilton 圖（ 8 分）四、計算14%1、 設(shè) <Z 6,+6> 是一個群，這里 +6 是模 6 加法， Z6 =0， 1 ， 2 ， 3

17、， 4 ，5 ，試求出 <Z 6,+6>的所有子群及其相應(yīng)左陪集。（7 分）2、 權(quán)數(shù)1， 4， 9， 16 ， 25， 36， 49， 64， 81， 100 構(gòu)造一棵最優(yōu)二叉樹。（7分）試卷二答案：一、 填空 20% （每小題2 分）1 、PQ ；PQ 2 、 T3 、B31 B00011111 a4 , a5 ,a6 ,a7 , a8 4 、R=<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6&g

18、t;,<4,5>,<4,6>,<5,2>,<5,111111111100011111113>,<5,4>,<5,5>,<5,6>；00000R=<1,1>,<2,2>,<3,3>6 、 a ；否；有5、R=<1,2>,<1,3>,<2,1>；7、 Klein四元群；循環(huán)群8、 B9 、1 n(n1)2；圖中無奇度結(jié)點且連通10 、二、選擇 20% （每小題2 分）題目12345678910答案B 、 DD；D DBDABBBB 、 C三、證

19、明 46%1、（ 9 分）（ 1）S 自反的aA，由 R 自反，(a, aR)( a, aR) ，a, aS（ 2）S 對稱的11/19a, bAa, bS(a, cR)(c,bR)S 定義(a, cR)(c, bR)R 對稱b, aSR 傳遞（ 3）S 傳遞的a, b, cAa, bSb, cS(a, dR)(d , bR) (b, eR) ( e, cR)(a, bR)(b, cR)R 傳遞a, cSS 定義由（ 1）、（ 2）、（ 3）得； S 是等價關(guān)系。2、11 分證明：設(shè) P(x)： x 是個舞蹈者；Q(x) ： x 很有風(fēng)度； S(x) ：x 是個學(xué)生； a：王華上述句子符號化為

20、：前提：x(P( x)Q(x) S( a)P(a)x(P( x)Q(x) P( a)Q(a) P( a) Q (a). S( a) S( a)Q(a) x(S(x) Q (x)、0分、 S(a)P(a) 結(jié)論：x(S(x)Q (x)3 分PPUST IT IT IT IEG 11 分證明：b1 ,b2B ,(b1b2 )f 滿射a1, a2A使f (a1 )b1 , f (a2 )b2 , 且 f (a1 )f (a2 ), 由于 f是函數(shù) ,a1a2又 g (b1 ) x | (xA)( f ( x)b1 ), g(b2 ) x | ( xA) ( f (x)b2 )a1g(b1 ), a2

21、g(b2 ) 但 a1g(b2 ), a2g(b1 )g(b1 )g (b2 )由b1 , b2 任意性知 ,g為單射 。4、8 分證明：設(shè) G 中兩奇數(shù)度結(jié)點分別為u 和 v，若 u， v 不連通，則G 至少有兩個連通分支 G1、 G2，使得 u 和 v 分別屬于 G1 和 G2，于是 G1 和 G2 中各含有1 個奇數(shù)度結(jié)點，這與圖論基本定理矛盾，因而u， v 一定連通。5、8 分證明：證 G 中任何兩結(jié)點之和不小于n。反證法：若存在兩結(jié)點u， v 不相鄰且 d(u)d (v)n1,令V1 u, v ，則 G-m'1 (n1)(n 2)2(n 1)V1 是具有n-2個結(jié)點的簡單圖，

22、它的邊數(shù)2, 可得m' 1 (n2)(n3) 12，這與 G1=G-V 1 為 n-2個結(jié)點為簡單圖的題設(shè)矛盾，因而G中任何兩個相鄰的結(jié)點度數(shù)和不少于n。12/19所以 G 為 Hamilton圖 .四、計算 14%1、 7分解：子群有 <0,+6>； <0,3,+6>； <0,2,4,+ 6>； <Z 6,+ 6>0 的左陪集： 0 ， 1 ；2， 3； 4， 50 ， 3 的左陪集： 0 ， 3 ； 1 ， 4； 2，50 ， 2 ，4 的左陪集： 0 ， 2 ， 4 ； 1 ，3 ，5Z6 的左陪集： Z6 。2、 7分試卷三試卷與

23、答案一、 填空 20% （每空 2 分）1、 設(shè) f， g 是自然數(shù)集N 上的函數(shù)則 f g( x) 。2、 設(shè) A=a ，b， c ， A 上二元關(guān)系則 s（ R） = 。xN ,f (x)x1 ,g( x)2x ，R=< a, a > , < a, b >,< a, c >, < c, c> ,3、 A=1 ， 2， 3， 4， 5， 6 ， A 上二元關(guān)系 T x, y | x y 是素數(shù) ，則用列舉法T= ；T 的關(guān)系圖為；T 具有性質(zhì)。13/194、集合A, 2,2 的冪集 2A= 。5、 P， Q 真值為0 ； R， S 真值為 1。

24、則 wff(P (R S) (P Q) (R S) 的真值為。6、 wff ( PQ) R)R 的主合取范式為。7、 設(shè) P（ x）： x 是素數(shù)，E(x) ：x 是偶數(shù)， O(x) ： x 是奇數(shù) N (x,y) ：x 可以整數(shù) y。則謂詞 wffx(P( x)y(O ( y) N ( y, x) 的自然語言是。8、 謂詞 wffxy( z( P( x, z) P( y, z)uQ (x, y, u) 的前束范式為。二、 選擇 20% （每小題2 分）1、 下述命題公式中，是重言式的為（）。A 、 ( p q)( p q) ； B、 ( pq)( p q) ( qp) ；C、 ( pq) q

25、 ；D 、 ( pp)q 。2、 wff( p q)r 的主析取范式中含極小項的個數(shù)為（）。A 、2； B、 3；C、5；D、0；E、 8 。3、 給定推理x( F (x)G( x) F ( y) G ( y) xF (x) F ( y) G ( y) xG ( x)x( F (x)G ( x)xG (x)推理過程中錯在（）。PUSPEST IUGA 、 -> 。B、 -> 。C、 -> 。D、 -> 。E、 ->4、 設(shè) S1=1 ， 2， ， 8， 9 ， S2=2 ， 4， 6， 8 ， S3=1 ， 3， 5， 7， 9 ， S4=3 ， 4，5 ，S5=

26、3 ， 5 ，在條件 XS1且XS3 下 X 與（）集合相等。A 、X=S 2 或 S5；B、 X=S 4 或 S5；14/19C、 X=S 1， S2 或 S4； D 、X 與 S1， ， S5 中任何集合都不等。5、設(shè)R和S是P上的關(guān)系，P是所有人的集合，R x, y | x, y P x是y的父親 ， S x, y | x, y Px是 y的母親 則 S 1R 表示關(guān)系（）。A 、 x, y| x, yPx是y的丈夫 ；B、 x, y| x, yPx是y的孫子或?qū)O女 ；C、； D、 x, y| x, yP x是y的祖父或祖母 。6、 下面函數(shù)（）是單射而非滿射。A 、 f : RR, f

27、 ( x)x 22x 1；B、 f : ZR,f ( x) ln x ；C、 f : RZ ,f (x) x, x表示不大于 x的最大整數(shù) ；D、 f : RR, f ( x) 2x 1。+其中 R 為實數(shù)集， Z 為整數(shù)集， R ， Z 分別表示正實數(shù)與正整數(shù)集。則 R 具有（）的性質(zhì)。A 、自反、對稱、傳遞；B 、什么性質(zhì)也沒有；C、反自反、反對稱、傳遞；D 、自反、對稱、反對稱、傳遞。8、 設(shè) S ,1 , 1, 2 ，則有（）S 。A 、1,2； B、 1,2 ； C、 1； D、2 。9、 設(shè) A=1 ,2 ,3 ，則 A 上有（）個二元關(guān)系。A 、23； B、32； C、 223；

28、 D、 232。10、全體小項合取式為（）。A 、可滿足式；B 、矛盾式； C、永真式； D、 A， B，C 都有可能。三、 用 CP 規(guī)則證明16% （每小題8 分）1、ABCD,DEFA F15/192、x(P( x)Q (x)xP(x)xQ( x)四、（ 14%）集合 X=<1,2>, <3,4>, <5,6>, ， R=<<x 1,y1>,<x 2 ,y2>>|x1 +y2 = x2+y 1 。1、 證明 R 是 X 上的等價關(guān)系。（10 分）2、 求出 X 關(guān)于 R 的商集。（ 4 分）五、（ 10%）設(shè)集合 A

29、= a ,b , c , d 上關(guān)系 R=< a, b > , < b , a > , < b , c > , < c , d >要求 1、寫出 R 的關(guān)系矩陣和關(guān)系圖。（4 分）2、用矩陣運算求出R 的傳遞閉包。（6 分）六、（ 20%）1、（ 10 分）設(shè) f 和 g 是函數(shù)，證明 fg 也是函數(shù)。2、（ 10 分）設(shè)函數(shù) g : STf : TS ，證明 f: TS 有一左逆函數(shù)當(dāng)且僅當(dāng)f 是入射函數(shù)。答案：五、填空 20% （每空 2 分）1 、 2(x+1)；2、 a ,a,a , b , a , c,c , c , b , a , c

30、 , a ； 3 、2,1,3,1, 5,1,4,2,6,2 , 6,3；4、反對稱性、反自反性；4、 , ,2, 2,2, 2 ； 5、 1；6、 (PQR)( PQR)( PQR) ； 7、任意x，如果x 是素數(shù)則存在一個y， y是奇數(shù)且y整 除x； 8 、x y z u(P( x, z)P( y, z)Q (x, y, u) 。六、選擇 20% （每小題2 分）題目12345678910答案CCCCABDADC七、證明 16%( 每小題 8 分 )16/191、 AP（附加前提）ABTI ABC DP CDT I DT I DET I DEFP FT I AFCP2、xP( x)xQ (x)(x) P(x)xQ( x)本題可證x( P( x)Q( x)(xP (x)xQ(x)( xP(x)P（附加前提）x( P(x)T EP(a)ESx(P( x)Q(x)P P( a) Q ( a)US Q( a)T IxQ( x)EG( xP( x)xQ(x)CP八、14%（ 1）證明：1、自反性：x, yX ,由于 x yxyx, y,x, yRR自反2、對稱性：x1 , y1X ,x2 , y2X當(dāng) x1, y1 ,x2 , y2R時 即x1y2x2y1 也即 x2 y1 x1 y2故x2 , y2,x1 , y1RR有對