资源描述:
《离散数学习题集(十五套)_免费下载》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、離散數學試題與答案試卷一一、填空20%(每小題2分)1.設(N:自然數集,E+正偶數)則。2.A,B,C表示三個集合,文圖中陰影部分的集合運算式為ABC。3.設P,Q的真值為0,R,S的真值為1,則的真值=。4.公式的主合取範式為。5.若解釋I的論域D僅包含一個元素,則在I下真值為。6.設A={1,2,3,4},A上關係圖為則R2=。7.設A={a,b,c,d},其上偏序關係R的哈斯圖為則R=。8.圖的補圖為。9.設A={a,b,c,d},A上二元運算如下:*abcdabcdabcdbcdacdabdabc那麼代數系統<
2、A,*>的么元是,有逆元的元素為,它們的逆元分別為。10.下圖所示的偏序集中,是格的為。二、選擇20%(每小題2分)1、下列是真命題的有( )A.;B.;C.;D.。2、下列集合中相等的有()A.{4,3};B.{,3,4};C.{4,,3,3};D.{3,4}。3、設A={1,2,3},則A上的二元關係有()個。A.23;B.32;C.;D.。4、設R,S是集合A上的關係,則下列說法正確的是()A.若R,S是自反的,則是自反的;B.若R,S是反自反的,則是反自反的;C.若R,S是對稱的,則是對稱的;D.若R,S是傳
3、遞的,則是傳遞的。5、設A={1,2,3,4},P(A)(A的冪集)上規定二元系如下則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}},{A}}6、設A={,{1},{1,3},{1,2,3}}則A上包含關係“”的哈斯圖為()7、下列函數是雙射的為()A.f:IE,f(x)=2x;B.f:NNN,f(n)=;C.f:RI,f(x)=[x];D.f:IN,f(x)=
4、x
5、。(注:I—整數集
6、,E—偶數集,N—自然數集,R—實數集)8、圖中從v1到v3長度為3的通路有()條。A.0;B.1;C.2;D.3。9、下圖中既不是Eular圖,也不是Hamilton圖的圖是()10、在一棵樹中有7片樹葉,3個3度結點,其餘都是4度結點則該樹有()個4度結點。A.1;B.2;C.3;D.4。三、證明26%1、R是集合X上的一個自反關係,求證:R是對稱和傳遞的,當且僅當和在R中有<.b,c>在R中。(8分)2、f和g都是群到的同態映射,證明是的一個子群。其
7、中C=(8分)3、G=(
8、V
9、=v,
10、E
11、=e)是每一個面至少由k(k3)條邊圍成的連通平面圖,則,由此證明彼得森圖(Peterson)圖是非平面圖。(11分)四、邏輯推演16%用CP規則證明下題(每小題8分)1、2、五、計算18%1、設集合A={a,b,c,d}上的關係R={,,,}用矩陣運算求出R的傳遞閉包t(R)。(9分)2、如下圖所示的賦權圖表示某七個城市及預先算出它們之間的一些直接通信線路造價,試給出一個設計方案,使得各城市之間能夠通信而且總造價最小。 (9分
12、)試卷一答案:一、填空20%(每小題2分)1、{0,1,2,3,4,6};2、;3、1;4、;5、1;6、{<1,1>,<1,3>,<2,2>,<2,4>};7、{,,,,}IA;8、9、a;a,b,c,d;a,d,c,d;10、c;二、選擇20%(每小題2分)題目12345678910答案CDB、CCADCADBA三、證明26%1、證:“”若由R對稱性知,由R傳遞性得“”若,有任意,因若所以R是對稱的。若,則即R是傳遞的。2、證,有,又★★★是的子
13、群。3、證:①設G有r個面,則,即。而故即得。(8分)②彼得森圖為,這樣不成立,所以彼得森圖非平面圖。(3分)一、邏輯推演16%1、證明:①P(附加前提)②T①I③P④T②③I⑤T④I⑥T⑤I⑦P⑧T⑥⑦I⑨CP2、證明①P(附加前提)②US①③P④US③⑤T②④I⑥UG⑤⑦CP二、計算18%1、解:,,t(R)={,,,,,,,,}1、解:用庫斯克(Kruskal)演算法求產生的最優樹。演算法略。結果如圖:樹權C(T)=23+1
14、+4+9+3+17=57即為總造價。試卷二試題與答案一、填空20%(每小題2分)1、P:你努力,Q:你失敗。“除非你努力,否則你將失敗”的翻譯為;“雖然你努力了,但還是失敗了”的翻譯為。2、論域D={1,2},指定謂詞PP(1,1)P(1,2)P(2,1)P(2,2)TTFF則公式真值為。1、設S={a1,a2,…,