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

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

2、;a,d>,<b,d>,<c,d> IA 。8圖的補圖為 。9設A=a，b，c，d ，A上二元運算如下：*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、設A=1，2，3，則

3、A上的二元關系有（ C ）個。 A 23 ； B 32 ； C ； D 。4、設R，S是集合A上的關系，則下列說法正確的是（A） A若R，S 是自反的， 則是自反的； B若R，S 是反自反的， 則是反自反的； C若R，S 是對稱的， 則是對稱的； D若R，S 是傳遞的， 則是傳遞的。5、設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、設A=，1，1，3，1，2，3則A上包含關系“”的哈斯圖為（ 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ù)集）8、圖 中 從v1到v3長度為3 的通路有（ D ）條。A 0；B 1；C 2；D 3。9、下圖中既不是Eular圖，也不是Hamilton圖的圖是（B）10、在一棵樹中有7片樹葉，3個3度結點，其余都是4度結點則該樹有（ A ）個4度結點。A1；B2；C3；D4 。三、證明 26%1. R是集合X上的一個自反關系，求證：R是對稱和傳遞的，當且僅當< a, b>

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

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