3、生”可符號化為( ).
A. ( V x)(^4(a) A5(x)) B. (3x)(24(x)AB(x))
C? n (Vx)(?l(x) fg(x)) D. -] (3x)(^(x)A-| 5(x))
二、填空題(每小題3分，本題共15分)
6. 若集合力的元素個數(shù)為10,則其驀集的元素個數(shù)為.
7. 設(shè)A={af b, c), B={1, 2},作/： 4-B,則不同的函數(shù)個數(shù)為.
8. 若力={12}，R={\x^A,y^A,x+y=\G},則R 的自反閉包為?
9. 結(jié)點數(shù)y與邊數(shù)e滿足 關(guān)系的無向連通圖就是樹.
10. 設(shè)個體域D={a, b,c}9則謂
4、詞公式(VxM(x)消去量詞后的等值式為
三、 邏輯公式翻譯(每小題6分，本題共12分)
11. 將語句“盡管他接受了這個任務(wù)，但他沒有完成好?”翻譯成命題公式.
12. 將語句“今天沒有下雨翻譯成命題公式.
四、 判斷說明題(每小題7分，木題共14分)
判斷下列各題正誤，并說明理由.
13. 下面的推理是否正確，試予以說明.
(1) (Vx) F(X)-G (x) 前提引入
(2) F (y) -G (y) US (1).
14. 若偏序集<4, 的哈斯圖如圖二所示，則集合』的最大元為s最小元不存在.
g
五. 計算題(每小題12分，本題共36分)
15. 求(P
5、V。)一(RV。)的合取范式.
16. 設(shè)刀={0, 1, 2, 3, 4), 7?=(\x^A, yeA _H. x+y<0), S={\xeA, yeA x+y<3},試 求 R, S, R,S, R-i, S) r(R)?
17. 畫一棵帶權(quán)為1, 2, 2, 3, 4的最優(yōu)二叉樹，計算它們的權(quán).
六、 證明題(本題共8分)
18. 設(shè)G是一個〃階無向簡單圖，〃是大于等于2的奇數(shù).證明G與&中的奇數(shù)度頂點個數(shù)相等(° 是G的補圖).
試題解答
一、 單項選擇題（每小題3分，本題共15分）
1. A 2. B 3. B 4. D 5. C
二、 填空
6、題（每小題3分，本題共15分）
6. 1024
7. 8
8. （<1,1>,<2,2>}
9. e=v~\
10. A （a） /\A （b） （ u）
三、 邏輯公式翻譯（每小題6分，本題共12分）
11. 設(shè)他接受了這個任務(wù)，Q：他完成好了這個任務(wù)， （2分）
PzQ? （6分）
12. 設(shè)F：今天下雨， （2分）
-yP. （6 分）
四、 判斷說明題（每小題7分，本題共14分）
13. 錯誤. （3分）
（2）應(yīng)為F （>） -G （x）,換名時，約束變元與自由變元不能混淆. （7分）
14. 錯誤. （3分）
集合A的最大元不存在，。是極大元. （7分
7、）
五、 計算題（每小題12分，本題共36分）
15. （PV2）一 （7?Vg）
—（PV0） V （RV。） （4 分）
<^（-nPA->e）V （RVQ）
頃V& V。）/\ （2 V R V。）
=（寸V&V。）AR 合取范式 （12分）
16. R=0, （2 分）
5={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>） （4 分）
&?S=0, （6 分）
&'=0, （8 分）
S】=S, （10 分）
KR）=Ia? （12 分）
權(quán)為 1x3+2x3+2x2+3x2+4x2=2
8、7 （12 分）
六、證明題（本題共8分）
18.證明：因為"是奇數(shù)，所以〃階完全圖每個頂點度數(shù)為偶數(shù)， （3分）
因此，若G中頂點y的度數(shù)為奇數(shù)，則在。中y的度數(shù)一定也是奇數(shù)， （6分）
所以G與。中的奇數(shù)度頂點個數(shù)相等. （8分）
《離散數(shù)學(xué)》題庫及答案二
一、單項選擇題（每小題3分，本題共15分）
1.
若集合4={1,⑵,（1, 2}},則下列表述正確的是（ ）.
A.
B. {1}曲
C.
D. 2 eA
2.
已知一棵無向樹『中有8個頂點，4度、3度、2度的分支點各一個，『的樹葉數(shù)為（）.
A.
B. 4
C. 3
D- 5
3.
設(shè)無向圖
9、G的鄰接矩陣為
0
1
1
1
1
1
0
0
1
1
1
0
0
0
0
1
1
0
0
1
1
1
0
1
0
則G的邊數(shù)為（
)?
A. 1
B. 7
C. 6
D. 14
4 .設(shè)集合A={a},
則刀的驀集為（
)?
A. {{。}}
B?{。， {a}}
C.
{°，{。}}
D. (0, a}
5-
下列公式中（
）為永真式.
A.
C.
二、 填空題（每小題3分，本題共15分）
6. 命題公式尸a —tP的真值是.
7. 若無向樹『有5個結(jié)點，則『的邊數(shù)為?
8. 設(shè)正則也叉樹
10、的樹葉數(shù)為分支數(shù)為j,則（"1）7 ?
9. 設(shè)集合力={1, 2}上的關(guān)系7? = （<1,1>,<1,2>},則在&中僅需加一個元素,就可使 新得到的關(guān)系為對稱的.
10. （Vx）（A（x）^B（xf z）VC（y））中的自由變元有,
三、 邏輯公式翻譯（每小題6分，本題共12分）
11. 將語句“今天上課.”翻譯成命題公式.
12. 將語句“他去操場鍛煉，僅當(dāng)他有時間.”翻譯成命題公式.
四、判斷說明題（每小題7分，本題共14分） 判斷下列各題正誤，并說明理由.
13. 設(shè)集合力={1, 2}, B={3, 4）,從刀到8的關(guān)系為＞（＜1,3＞）,貝是力到B的函數(shù).
11、14. 設(shè)G是一個有4個結(jié)點10條邊的連通圖，則G為平而圖.
五. 計算題（每小題12分，本題共36分）
15. 試求出（PV。）一（RV。）的析取范式.
16. 設(shè)刀={{1},1,2}, 3={1, {2}},試計算
(2) C4UB)
17. 圖 G=,其中 V={ %b,c,d}, E={心)，(。,c),(% d), (b, c), (b, d),(c,力},對應(yīng)邊的權(quán)值依 次為1、2、3、1、4及5,試
（1）畫出G的圖形;
（2）寫出G的鄰接矩陣;
（3）求出G權(quán)最小的生成樹及其權(quán)值.
六、證明題（本題共8分）
18. 試證明：若r與s是集合刀上的
12、自反關(guān)系，貝U&ns也是集合力上的自反關(guān)系.
試題解答
一、單項選擇題（每小題3分，本題共15分）
1- B 2. D 3. B 4. C 5. B
二、填空題（每小題3分，本題共15分）
6.
假（或F,或0）
7.
8.
9.
<2, 1>
10.
z, y
三、
邏輯公式翻譯（每小題6分，本題共12分）
11.
設(shè)今天上課,
（2分）
（6分）
則命題公式為：P.
12.
設(shè)F：他去操場鍛煉，Q：他有時間,
（2分）
則命題公式為：PT0
（6分）
四、判斷說明題（每小題7分，本題共14分）
13.錯誤.
（3分）
13、因為力中元素2沒有3中元素與之對應(yīng)，故/不是刀到3的函數(shù).
（7分）
14.錯誤.
（3分）
不滿足“設(shè)G是一個有v個結(jié)點e條邊的連通簡單平面圖，若
則 eW3v?6. ”
(7分)
五.計算題（每小題12分，本題共36分）
15.
(PV0) 一(&") -| (PV0V (RV。)
(4分)
16.
(1)
17.
(2)
(3)
(2)
(3)
(1)
（8分）
<=>(nPAn 0V7?V0 (析取范式)
C4U3) ={1,2, {1},{2}}
A- C4C3) =({!}, 1,2}
G的圖形表示如圖一所示:
圖一
鄰接矩陣:
14、0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
最小的生成樹如圖二中的粗線所示:
（12 分）
(4分)
（8分）
（12 分）
（3分）
（6分）
3
0
（10 分）
b 1 c
圖二
（12 分）
權(quán)為：1+1+3=5
六、證明題（本題共8分）
18.證明：設(shè)VxgJ,因為&自反，所以x Rx, BPg7?；
又因為S自反，所以xRx,即eS.
即 Vx, x>eROS
故ACS自反.
（4分）
（6分）
（8分）
《離散數(shù)學(xué)》題庫及答案三
一、單項選擇題（每小題3分，本
15、題共15分）
1.若集合A = {a, {〃}},則下列表述正確的是（ ）.
A. {/z}o4
C.
D. 0gA
2.
命題公式（PVQ）的合取范式是（ ）
A.
(PA2)
B. (PA0) V (PVg)
C.
D. ―i (—P /\—Q)
3.
無向樹r有8個結(jié)點,
則T的邊數(shù)為（）.
A.
Be 7
C. 8
D.
A.
C.
5.
A.
C.
4.圖G如圖一所示,
以下說法正確的是（）.
a是割點
{缶d}是點割集
圖一
下列公式成立的為（）.
「P/\「Q = P\/Q
Q—PnP
B. 0 c}是點割集
16、
D. {c}是點割集
B. P->-iQ = TtQ
D.「PQ)n。
二、填空題（每小題3分，本題共15分）
6. 設(shè)集合4={2.3,4}, B={1,2, 3,4}, R是刀到8的二元關(guān)系,
7? = ( xe A^y e是有4個結(jié)點，8條邊的無向連通圖，則從G中刪去 條邊，可以確定圖
G的一棵生成樹.
9. 設(shè)G是具有〃個結(jié)點m條邊《個面的連通平面圖，則m等于
10. 設(shè)個體域。={1,2},刀⑴為％大于1”，則謂
17、詞公式(3x)A{x)的真值為
三、邏輯公式翻譯(每小題6分，木題共12分)
11. 將語句“今天考試，明天放假?”翻譯成命題公式.
12. 將語句“我去旅游，僅當(dāng)我有時間?”翻譯成命題公式.
四、判斷說明題(每小題7分，本題共14分)
判斷下列各題正誤，并說明理由.
13. 如果圖G是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖G是歐拉圖.
14. 若偏序集V4,人>的哈斯圖如圖二所示，則集合Z的最大元為最小元是人
五. 計算題(每小題12分，本題共36分)
15 .設(shè)謂詞公式(女)(刀(x, y) T (Vz)5(y, x, z)),試
(1) 寫出量詞的轄域； (2)指出該公式
18、的自由變元和約束變元.
16. 設(shè)集合 /={⑴,1,2}, 8={1,{1,2}},試計算
(1) C4—8) ； (2) C4C1B) ； (3) AXB.
17. 設(shè) G=, V={v\, v2> 巧，v4 ), E={(vi,V3), (v2,v3), (v2,v4)，(巧皿)}，試
(1) 給出G的圖形表示； (2)寫出其鄰接矩陣；
(3) 求出每個結(jié)點的度數(shù)； (4)畫出其補圖的圖形.
六、證明題(本題共8分)
18. 設(shè)力，B是任意集合，試證明：若Ax4=BxB,則
試題解答（供參考）
一、 單項選擇題（每小題3分，本題共15分）
1. A 2.
19、C 3. B 4. B 5. D
二、 填空題（每小題3分，本題共15分）
6. （<2, 2>, <2, 3>, <2,4>, <3, 3>）, <3, 4>, <4, 4>）
7. , < h, b>
8. 5
9 . n+k-2
10. 真（或T,或1）
三、 邏輯公式翻譯（每小題4分，本題共12分）
11. 設(shè)P：今天考試，Q：明天放假. （2分）
則命題公式為：PA0 （6分）
12. 設(shè)F：我去旅游，Q：我有時間， （2分）
則命題公式為：PT0 （6分）
四、 判斷說明題（每小題7分，木題共14分）
13. 錯誤. （3分）
當(dāng)圖G不連通
20、時圖G不為歐拉圖. （7分）
14. 錯誤. （3分）
集合力的最大元與最小元不存在，
a是極大元，/是極小元，? （7分）
五. 計算題（每小題12分，本題共36分）
15. （1）女量詞的轄域為以（x,v）T（Vz）33,x,z））, （3 分）
Vz量詞的轄域為x, z）, （6分）
（2）自由變元為以（x,v）t（Vz）33,x,z））中的〉， （9分）
約束變元為x與z? （12分）
16. （1） Z—3={{1},2} （4 分）
（2） ACIB={1} （8 分）
(3) 4x8={v{1},1>, v{1},{1,2}>, vl,l>, vl, {1
21、,2}>, <2,1>, v2, {1,2}>} (12 分)
17. (1) G的圖形表示為(如圖三)：
V3
（2）鄰接矩陣:
0 0 10
0 0 11
110 1
0 110
(3) V,, v2, v3, v4結(jié)點的度數(shù)依次為b 2, 3, 2
（9分）
（4）補圖如圖四所示:
圖四
六、證明題（本題共8分）
18. 證明：設(shè) xeA9 則v?x, x>eAxA,
（1分）
因為 AxA=BxB,故x>wBxB,則有
（3分）
所以AqB.
（5分）
（6分）
因為AxA=BxB,故V》，x>eAxA,則有xeA,所以
（7分）
22、
故得A=B.
（8分）
《離散數(shù)學(xué)》題庫及答案四
一、單項選擇題（每小題3分，本題共15分）
1. 設(shè) A=(1，3.5,7,9).R=(2?，6),A 到 H 的關(guān)系 R-，：Vz .》>! r-y-1) .則 R=( >.
A. (,<2.3>.<3.4>> H?(Vl.2>,V3.4>?V5.6>}
G {<1.1>,<2,2>.<3.6>) 「).(V3.2>?V5?4>,V??6>)
2. 若餐合A = .則下列表芯正確的是( ).
A. (ci EMcOWA
C. (u,b}6A D.0eA
3. 段個體it為集合(1.2.3?4.5} .則公式
23、(V『)《3少(工+》=5)的解釋可為( ).
A.存在一整數(shù)g有整數(shù)y滴足x+>=5
a對任一整數(shù)工存在整數(shù)y滴足*+》=5
C. 存在一整數(shù)4對任恿整數(shù)y滿足工+》=5
D. 任一整數(shù)工對任意整致y清足x+y=5
4. 沒仁為連通無向圖.蝸( 〉時,a中存在歐拉回用.
A.G存在兩個tSfttJM數(shù)的結(jié)點 B.G存在一個奇數(shù)度數(shù)的常點
GG不存在奇數(shù)度數(shù)的結(jié)點 D.G存。偶數(shù)度數(shù)的結(jié)點
乩n階無向完全圖K.的邊數(shù)及每個結(jié)點的度敬分別是( ).
A. Jt(n — 1)與 n 11 ji(w-*1)/2 與 ”一1
C w — 1 與 n D. n(n — 1)與 ? —
24、 I
二、 填空題(每小題3分，本題共15分)
6. 設(shè)堡 & 1一{1.2.3)?〃 =,：2.3).(/=口.4,?刪.41)(3一(?)=?
7. 設(shè)Af 08F.2L" H 從\到B的畫數(shù)/ =7V「1>?VO.2>}.從B 到C的函數(shù)拜=(<1.6>?<2心>).荊曠/等于.
8. 設(shè)G = VV?E>職一個圖.|E| = M.則“的捎點度敝之和為?
9. 設(shè)G是代有〃 茶邊&個而的連通平面圖.則刀+*-2=?
1D，設(shè)中怵城本=1.？.3..?1J)為\的2倍大于站.刖周刊公式IV那.4(/)的底值為
三、 邏輯公式翻譯(每小題6分，本題共12分)
11. 將語
25、句“如果他掌握了計算機的用法，那么他就能完成這項工作?”翻譯成命題公式.
12. 將語句“前天下雨，昨天還是下雨?”翻譯成命題公式.
四、 判斷說明題(判斷各題正誤，并說明理由.每小題7分，本題共14分)
13. 段.1 = % , A. c ) ? R — ( V ? , 〃 > ? < A . /，A ? V r? ? V 以，6 > ? V 內(nèi), 〃 > , V 右，4 A ? VrM>} ?姻R是等價關(guān)系.
14. ( Vx)CP< r)AQ《y)f Rtr>)中世詞 丫 的轄帔為(P。)AQ( y)L
五、計算題(每小題12分，本題共36分)
15. 設(shè)陞臺八=la,/
26、，” .d)?Hr站日)，試”算
(1)4 UBi (2)A—/h (3)AXB.
'St V，? E > , V* = < H ? T?，,口,. }? ￡ = {（叫."c ）?（玖,饑）.（叫.口、）.《化. 5 > ,
（■? 2.））.試
（l>紛出G的圖形&示， 12>耳出其鄰也如所，
《3）求出每個靖點的度％ 《，>踴出北補圖的圖形.
I 7.試?yán)肒ruskn W伏未出如卜所況M技圖中的/?小生成俐（要求寫出求解3項，.井 未此條小生成列的枳.
試題答案
一?單項選探BH每小題3分,本18共恃分）
1.0 2.A 3.B 4.C 5.H
二. 填空》!（每小
27、超3分.本弛共15分）
6. （1.2.3）
7. （<.）
?. 2。（或：2|E|）
9?m
10. 假（或F.或。）
三. 謠輻公式翩澤（每小聘6分.本息［共12分）
IL i? PJlfctW了計算機的用法,Q：他推完成這項工作- （2分）
刪命題公式為，PfQ? （6分）
12. 設(shè)P,前天下雨.Q沖天還是下闌. （2分）
則命88公式為：PAQ.； （6分）
四、判斷說明網(wǎng)（督小18 7分,本18共M分）
13. 部誤. （3分）
R不是等價關(guān)系.因R中包含^，但不包含V<2/>?故不滿足傳遞性?
：（1 分）
1
28、4. 銷誤“ 心分）
暗域為緊惟St詞V之后的梭小子公式（P（x）AQC.y）-R（x））. 《7分）
五?計算1!（每小12分,本11共36分）
15. n）AUB =（a0?c?d）i （4 分〉
（2〉A(chǔ) — 8 = （c ?..,..? Vd g >? Vd E>)
J6.（i）g的圖形&示ftn圖一所示,
(2〉郊接矩陣， 0 1 1 1 10 10 110 1 10 10
圖一
（3分）
《6分）
(3)血只(口)= 3.
drg(i>j) - 2>
29、
drg(vj)&3t
degE ) = 2
(4〉補圖如圖二所示,
（9分）
O
（12 分）
（6分）
圖二
17. 用Kruskal算往求產(chǎn)生的最小生&樹.步界為:
1 .選小=1/1?
uH戲?t/?）=3?選小=
w( v> ? v? ^^4 ?選 ft =山巧 w《m.m)r9 ,選 = w《m?s>=l8 .遺 w3?3=22.ii e.=y?
囹三 （9分）
IA小生應(yīng)用的權(quán) m=I十3 + 1 + 94 IR+22=57? < 12分）
六. 證明題（本JS共&分H
18, M Wt
(!) P VQ
P
（1分）
⑵P
30、
POU fill前提〉
以分》
⑶Q
TCD(2)r
M分)
AQ
Tf2)(3)/
（5分）
⑸-(-P V 9
r(nE
Ch分)
(6)f 1 P-* 二 Q >
T(5)E
（7分）
<7)P 一Q)
CP埸則
<8分)
IftlUhlHiiE刪過慢中.公式引用的次序訶以不同?般引用的提正琦特1分.利川倆個公K 團(tuán)出有效結(jié)伯格1成2分,眼后同出站論得2或1分?
另.可以用頁值表臉證.
《離散數(shù)學(xué)》題庫及答案五
單項選擇題（每小題3分，本題共15分）
1. 設(shè) A = {1.2,3,1),8= (2,3,4},A 到 B 的關(guān)系 R - {<
31、x .>> I z 6 A G B .且.r + y
= 5}.tt!R = ( ).
A. <<]?2>.V1?3>,V2?3>) EL {<1.4>.<2.3>.<3?2>>
(：.(V1.1>,V2.2>,V3,2>) D. (<3.2>,<2,4>.<3,4>>
2. 若集合A = M?6,r.d).則下列表述正的的是< 〉.
A.06A
C?{??M.d}￡A D. U.6JGA
3 .設(shè)個體域為整數(shù)韭.燃公式(Vx)(3y)(x->=2>的解釋可為( ).
A. 存在一整數(shù)工有整數(shù)y滿足x-y-2
B. 存在一建數(shù)工對任意整數(shù)y滿足工一y = 2
C. 對任一整
32、數(shù)工存在整數(shù)》滴足x-y-2
D. 任一整數(shù)1對任意整數(shù)〉滿足x-> = 2
4. "階無向完全圖K,的邊數(shù)及每個結(jié)點的度數(shù)分別是( ).
A. n(w —與〃 B. n( w 1)與 〃一1
C?n —】與” D. w(n —1)/2 與 rr —1
5. 設(shè)G為連通無向圖.則( 〉時?弓中存在歐拉回路.
A.G不存在奇數(shù)度數(shù)的結(jié)點 B.G存在一個新數(shù)度數(shù)的結(jié)點
C.G存在兩個奇數(shù)度數(shù)的結(jié)點 D.G存在偶數(shù)度數(shù)的結(jié)點
甫分
評卷人
二、填空題（每小18 3分,本a［共15分）
6. 設(shè)集含工是小于4的正整數(shù)） ?用集合的列舉法.
7. 設(shè) A = （
33、l,2）,T2）,CTl,2}.從 A 到 B 的函數(shù)/ = （Vl?u>,V2,Q>}.從 B
到C的函致g = （,V6.l>}.則復(fù)合函數(shù).
8. 設(shè)G-是一個圖，結(jié)或度敬之和為30.則G的邊數(shù)為?
9. 設(shè)G是具有，，個結(jié)點桁條邊▲個面的連通平面圖，姻”+A-2=.
10. 設(shè)個體域D = （2,3.4>.A（i）為七小于3”，則謂同公式（VjHAG ）的真值為
得分
評卷人
三?!！福公式小IS 6分，本原共12分）
11. 將語句“如果今天下雨.那么明天的比賽就要延期.”疆譯成命題公式.
得分
評卷人
12.
34、將語句“地球是圓的，太陽也是圓的.”翻譯成命題公式.
四、判斷說明IH（判斷各題正誤，井說明理由?每小H 7分，本題共
14分）
13. 設(shè) A^{a.b.c.d} .R^{9,9.},則 R 是等 價關(guān)系.
14. ( Vx)(P(x)AQ(y))-R(x)中量詞 V 的轄域為(P(x> AQ(>)).
得分評卷入
五■計算魁（每小H 12分.本慧共36分）
15. 設(shè)集合A = = 試計算
(l)A(JHi
(2)4-3, (3)AXB.
16. 設(shè) G = t V ? (V| t vt ? ) ? E = {
35、(V| ? ) < (vj t (vi. v<) > (1/1 ti?i )?
(l>給出G的圖形衰示8 (2)寫出其鄰接矩陣I
(3)戒出每個站點的度數(shù), (4)?出其補圖的圖形.
17. 試?yán)肒ru9kd算法求出如下所示賦權(quán)圖中的1ft小生或樹(妻求寫出求薪步轅〉，并 求此最小生成樹的權(quán).
得分
評卷人
六、證明18(本題共8分)
18.成征明r （P-「Q）.
試題及答案
-■?項iswHim小m3分,本ai共is分）
I. B 2.D 3.C 4. D &A
二, 堵空J(rèn)B（每小1?3分.本1?共15分）
6. （I.2.3）
7. <<1.
36、2>.<2.1?
9. m
10. fl
三、 il輯公式小H6分.本HI共12分）
H.?今天下Ifl.QZI天的比賽就要14期. （2分）
副命MS公式為《6分）
12.仗卜?地球屈圓的，?！鎏柺菆A的. 《2分）
WlifrM公式為lP^Q. （6 分〉
四、 判斷說明18（每小JW 7分,本JB共14分）
IX WiM. （3 分）
R不是等價關(guān)系.因R中不含V〃M>.故不fMMfl反性. （7分）
M.正確. “分）
之后的 Jft 小子公 X（P（Jc）AQ（y>）. （7 分）
五小H技分.本H共36分）
15. ⑴AU8?M.y
37、 （4 分）
（2M-B-（ah （8 分）
（3）A XB {.,9..t. = 2
(4〉補09如圖二所示I
《9分)
圖二
W(V| .vr) = l
選 e(
W(Vr ? ) = 1
38、
選 Cl —V?1F4
w(vj fVS) = 2
選 = V|V<
w(v> =3
選 ％ =
17.用Kruskal W法求產(chǎn)生的感小生成樹.步驟為,
W(Vt ? VF ) = 4 選 Cs =VjV? w (Vj f Vt > = 5 ij ci 33 v$v? 最小生成鈣如圖三所示.
《6分）
圖三
（9分）
最小生成樹的權(quán)W(T) = 1 + 1 + 2 + 3 + 4 + 5=16.
（12 分）
說明，用其他方法.結(jié)果正確參照給分.
六■證明18（本境共8分）
18.證明：
(l)P-Q
（1分）
(3)Q
(4)PAQ
(5U
39、P V 9
(6U「Q)
P（附加前提）
T(2)(3)/
T(4)E
T(5>E
（2分）
（4分）
《5分）
（6分〉
（7分）
(7〉P—r(?rQ〉
（8分）
說明：因BE明過程中,公式引用的次序可以不同?一般引用前提正確得1分,利用兩個公式 得出有效結(jié)論得1或2分，景后得出結(jié)論得2或1分.
另?可以用真值表驗證.
《離散數(shù)學(xué)》題庫及答案六
一、單項選擇題（每小題3分，本題共15分）
若集臺人=(1.2.3.U .則下列我還不正確的M(
A」2.3)￡A B. A^{ 1.2,3.1)
C, (1.2?3,4)W人 D. leA
2. 若無向
40、圖。的結(jié)點度數(shù)之和為20,則r；的邊數(shù)為( >?
A. 10 a 20
C.30 D.5
X無向圖G是根樹，結(jié)成數(shù)為1《)?的(；的邊數(shù)為( >.
A.S R. 10
Q9 DJI
4. ft A(^)：j是人”(了)口是學(xué)生,刪母甌“村的人是學(xué)生”可荷門化為(
A. r ( v?t)(惑〔_r)f ))
B. ( 3^)(A(x) AB(x))
C (Yx)(A(x) AB(x))
I), r < A r HJ > 】
5. 下面的推理正唏的是( ).
A* < 1H V x)F(x)-^7(x)
前提引人
<2)F(>)-*G(y)
US (1>.
&《1)
41、( 3 -r)F( J )-*G (x )
前提引入
(2)F(y)—G(y)
US(\).
C. (1)( 3^)(F( f >-*G(±>)
的提引人
⑵FJM。())
ES(1).
D. (1)( 3JXF(x)-*Glr))
前捉引人
(2)F(ylt；《y)
ES(D.
二、填空題(每小題3分，本題共15分)
6. 設(shè)A = “.2}.Bu 1.2.3} ?則A到B上不同的函散個散為?
7. fin個靖點的無向完全圖的邊數(shù)為?
%若無向圖G中存在歐枚路但不存在歐拉回路，則6的布散度敬的結(jié)點有
9. 設(shè)(；是a 10個結(jié)點的無向連通圖.結(jié)點的度教之和
42、為30,則從G中JH去
條邊后使之變成樹-
10, 設(shè)個體域D = < 1.2.3.1).則明詞公式(如 >人M )酒去旬俱后的等值式為 三、邏輯公式翻譯(每小題6分，本題共12分)
11. 將語句“昨天下雨"翻譯成命題公式.
12. 將語句“小王今天上午或者去看電影或者去打球”翻譯成命題公式.
四、 判斷說明題（判斷各題正誤，并說明理由.每小題7分，木題共14分）
IX存在果合A與使得與同時成立.
14, 完全圖K,是平面圖.
五、 計算題（每小題12分，本題共36分）
15. 墳偏序集VA,R＞的哈斯圖如F.B為A的升集?共中日=f仇”.城
；!＞與出R的關(guān)備艘達(dá)式;
43、
（2,凱出關(guān)系R的關(guān)系圖，
（3〉求出H的最大元,極大元.上界.
16. 1殳圖 G V = (納 g?s Mg )?Eu〔叫f
V I)> C v . th ) >.試
口）兩出《；的圖形表示j
（2） 寫出其鄰樓用陣；
（3） 求出每個苗點的度數(shù)，
（4） 畫出圖G的樸踞的胡形.
17. 求P-（QAK＞的合取范式與主合取范式.
六、證明題（本題共8分）
18. 設(shè)A./3電任意集合.試訕明，看A = B.
試題答案及評分標(biāo)準(zhǔn)
（供參考）
一、■項選捧H（每小■ 3分，本聘共15分）
I. A 2< A XC 4.
?。? 3 分.本18共 15 分）.
44、
G.9
7.M（rt-D/2（f?C：>
0.6 .
!O.A（I）VA（2）VA（3）VA（4）
三■邏Ml公式?母（每小趣6分.本贓共12分）
1L設(shè)尸：咋天Tffi- （2分〉
刪仙跳公式抓P. 傍分）
12. 設(shè)尸,小王令夫上午去看電物
Q*小王今天上午去打球 （2分）
W^rtt公式為L（P?“n.
成#<-PAQ）V（PA rQ\ （6 分）
四、判唏說明（8（每小IS 7分，本Jg共14分）
13. 正確， 《3分）
例，設(shè) AfSIWuS."}} （5 分）
州有A€B且《7分） 說明［畢山N合蚤件的例均靖分.
1，正編. （3分〉
完仝兇K.
45、燧平面圈. _ （5 ?）
如K.可成611F圖示城人平而.
《7分〉
五、計??(?小部12分，本題矣36分)
15. .<6.6>..< J ... . )? (4 分>
3》關(guān)系圖
（8分）
（3）集合B無最大元，耿太元為心與。?無上界- ”2分）
16. M：
H）關(guān)系圖
（3分）
（2）鄰模平警
1 Q 1 0 0 o 1 d o 1 10 0 0 0 10 10 0 ■
（3）dcK（ih）=3
dcg*2
1
dc^（v ） —2
（9分
46、，
<12 分'
17, P-^（QAR）
?-PVCQAK> （2 分）
Dr r P V Q> A《r P V R） 合取范式 C5分》
m-PVQ>V（R/\ rR）A《r PVR） 3 分》
—f VQ> V《A A F> A（「p VR） V（QA「Q） （9 分,
DiU'VQVR）/H *PVQV - ADAC^PVKVQJAC-F VKV-'Q） "1 分，
a（rVVQVR）人（rPVQV ??R）A（，PV，QVR） 主合取他式 32 分〉 六、il明6 分）
10證奶.
? z6A.H?]6AxA. <1 分）
因 AXA-HXH.故 V ,r ,x>€ HXH.WJff rGB. <3 分）
侃此AGH. 心分）
段 了68,WKx?@>6HXH. C6 分，
W A X4 ft 2G4.1M 此 BG .A. （7 分）
故W A-B. X8 分）
國家開放大學(xué)電大《離散數(shù)學(xué)(本)》期末題庫及答案
