華東交大 離散數(shù)學(xué)試卷一試題與答案

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

2、;a,d>,<b,d>,<c,d> IA 。8圖的補(bǔ)圖為 。9設(shè)A=a，b，c，d ，A上二元運(yùn)算如下：*a b c dabcda b c db c d ac d a bd a b c那么代數(shù)系統(tǒng)<A，*>的幺元是 a ，有逆元的元素為 a , b , c ,d ，它們的逆元分別為 a , d , c , d 。10下圖所示的偏序集中，是格的為 c 。二、選擇 20% （每小題 2分）1、下列是真命題的有（C、 D）A ； B；C ； D 。2、下列集合中相等的有（ B、C） A4，3； B，3，4；C4，3，3； D 3，4。3、設(shè)A=1，2，3，則

3、A上的二元關(guān)系有（ C ）個(gè)。 A 23 ； B 32 ； C ； D 。4、設(shè)R，S是集合A上的關(guān)系，則下列說法正確的是（A） A若R，S 是自反的， 則是自反的； B若R，S 是反自反的， 則是反自反的； C若R，S 是對(duì)稱的， 則是對(duì)稱的； D若R，S 是傳遞的， 則是傳遞的。5、設(shè)A=1，2，3，4，P（A）（A的冪集）上規(guī)定二元系如下則P（A）/ R=（ D）AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、設(shè)A=，1，1，3，1，2，3則A上包含關(guān)系“”的哈斯圖為（ C ）7、下列函數(shù)是雙射的為（ A ）Af : IE , f (x)

4、 = 2x ； Bf : NNN, f (n) = <n , n+1> ；Cf : RI , f (x) = x ； Df :IN, f (x) = | x | 。（注：I整數(shù)集，E偶數(shù)集， N自然數(shù)集，R實(shí)數(shù)集）8、圖 中 從v1到v3長(zhǎng)度為3 的通路有（ D ）條。A 0；B 1；C 2；D 3。9、下圖中既不是Eular圖，也不是Hamilton圖的圖是（B）10、在一棵樹中有7片樹葉，3個(gè)3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)則該樹有（ A ）個(gè)4度結(jié)點(diǎn)。A1；B2；C3；D4 。三、證明 26%1. R是集合X上的一個(gè)自反關(guān)系，求證：R是對(duì)稱和傳遞的，當(dāng)且僅當(dāng)< a, b>

5、; 和<a , c>在R中有<.b , c>在R中。（8分）2. f和g都是群<G1 ,>到< G2, *>的同態(tài)映射，證明<C , >是<G1, >的一個(gè)子群。其中C= (8分)3. G=<V, E> (|V| = v，|E|=e ) 是每一個(gè)面至少由k（k3）條邊圍成的連通平面圖，則， 由此證明彼得森圖（Peterson）圖是非平面圖。（11分）四、邏輯推演 16%用CP規(guī)則證明下題（每小題 8分）1、2、五、計(jì)算 18%1、設(shè)集合A=a，b，c，d上的關(guān)系R=<a , b > ,< b

6、, a > ,< b, c > , < c , d >用矩陣運(yùn)算求出R的傳遞閉包t (R)。 （9分）2、如下圖所示的賦權(quán)圖表示某七個(gè)城市及預(yù)先算出它們之間的一些直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。（分）三、證明 26%1、 證：“” 若由R對(duì)稱性知，由R傳遞性得 “” 若，有 任意 ，因若 所以R是對(duì)稱的。若， 則 即R是傳遞的。2、 證，有 ，又 < C , > 是 < G1 , >的子群。3、 證：設(shè)G有r個(gè)面，則，即 。而 故即得 。（8分）彼得森圖為，這樣不成立，所以彼得森圖非平面圖。（3分） 四、 邏輯推演 16%a) 證明：P（附加前提）TIPTITITIPTICP2、證明 P（附加前提）USPUSTIUGCP五、計(jì)算 18%b) 解： ， ，t (R)=<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b ,