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. 設A={af b, c), B={1, 2},作/： 4-B,則不同的函數(shù)個數(shù)為 .
8. 假設力={12}，R={\x^A,y^A,x+y=\G},則R 的自反閉包為 ?
9. 結點數(shù)y與邊數(shù)e滿足 關系的無向連通圖就是樹.
10. 設個體域D={
4、a, b,c}9則謂詞公式(VxM(x)消去量詞后的等值式為
三、 邏輯公式翻譯(每題6分，此題共12分)
11. 將語句“盡管他接受了這個任務，但他沒有完成好?〞翻譯成命題公式.
12. 將語句“今天沒有下雨翻譯成命題公式.
四、 判斷說明題(每題7分，木題共14分)
判斷下面各題正誤，并說明理由.
13. 下面的推理是否正確，試予以說明.
(1) (Vx) F(X)-G (x) 前提引入
(2) F (y) -G (y) US (1).
14. 假設偏序集<4, 的哈斯圖如圖二所示，則集合』的最大元為s最小元不存在.
五. 計算題(每題12分，此題共36分)
5、
15. 求(PV。)一(RV。)的合取范式.
16. 設刀={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, L, r(R)?
17. 畫一棵帶權為1, 2, 2, 3, 4的最優(yōu)二叉樹，計算它們的權.
六、 證明題(此題共8分)
18. 設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. 設他接受了這個任務，Q：他完成好了這個任務， [2分 ]
PzQ? [6分 ]
12. 設F：今天下雨， [2分 ]
-yP. [6 分 ]
四、 判斷說明題[每題7分，此題共14分 ]
13. 錯誤. [3分 ]
[2 ]應為F [＞ ] -G [x ],換名時，約束變元與自由變元不能混淆. [7分 ]
14. 錯誤. [3分 ]
集合A的最大
7、元不存在，。是極大元. [7分 ]
五. 計算題[每題12分，此題共36分 ]
15. (PV2)一 (7?Vg)
[4分 ]
[12 分 ]
[2分 ]
[4分 ]
[6分 ]
[8分 ]
[10 分 ]
[12 分 ]
(PV0) V (RV。)
<^(-nPA->e)V (RVQ)
頃V& V o)/\ (2 V R V。)
=(2V&V。)AR 合取范式
16. R=0, 5={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} &?S=0,
E=0,
s'=s,
RR)=L.
8、權為 1x3+2x3+2x2+3x2+4x2=27
[10 分 ]
[12 分 ]
六、證明題[此題共8分 ]
18.證明：因為"是奇數(shù)，所以〃階完全圖每個頂點度數(shù)為偶數(shù)， [3分 ]
因此，假設G中頂點y的度數(shù)為奇數(shù)，則在。中y的度數(shù)一定也是奇數(shù)， [6分 ]
所以G與&中的奇數(shù)度頂點個數(shù)相等.
[8分 ]
【離散數(shù)學】題庫及答案二
一、單項選擇題[每題3分，此題共15分 ]
1.
假設集合4={1,⑵,[1, 2}},則下面表述正確的選項是[ ].
A.
B. {1}曲
C.
D. 2 eA
2.
已知一棵無向樹『中有8個頂點，4度、3度、2
9、度的分支點各一個，『的樹葉數(shù)為[ ].
A.
B. 4
C. 3
D- 5
3.
設無向圖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 .設集合A={a},
則刀的驀集為[
)?
A. {{。}}
B?{。， {a}}
C.
{°，{。}}
D. (0, a}
5-
下面公式中[
]為永真式.
A.
C.
二、填空題[每題3分，此題共15分 ]
6.
10、 命題公式尸a —tP的真值是 .
7. 假設無向樹『有5個結點，則『的邊數(shù)為 ?
8. 設正則也叉樹的樹葉數(shù)為分支數(shù)為j,則["1 ]7 ?
9. 設集合力={1, 2}上的關系7? = [<1,1>,<1,2>},則在&中僅需加一個元素 ,就可使
新得到的關系為對稱的.
10. [Vx ][A[x ]^B[xf z ]VC[y ] ]中的自由變元有 , 三、邏輯公式翻譯[每題6分，此題共12分 ]
11. 將語句“今天上課.〞翻譯成命題公式.
12. 將語句“他去操場鍛煉，僅當他有時間.〞翻譯成命題公式.
四、判斷說明題[每題7分，此題共14分 ]
判斷下面各題正誤，
11、并說明理由.
13. 設集合力={1, 2}, B={3, 4 ],從刀到8的關系為＞[＜1,3＞ ],貝是力到B的函數(shù).
14. 設G是一個有4個結點10條邊的連通圖，則G為平而圖.
五. 計算題[每題12分，此題共36分 ]
15. 試求出[PV。 ]一[RV。 ]的析取范式.
16.設刀={{1},1,2}, 3={1, {2}},試計算
(2) C4UB)
17. 圖 G=,其中 V={ %b,c,d}, E={心)，(。,c),(% d),(b,c),(b, d),(c,力},對應邊的權值依 次為1、2、3、1、4及5,試
[1 ]畫出G的圖形;
[2
12、]寫出G的鄰接矩陣;
[3 ]求出G權最小的生成樹及其權值.
六、證明題[此題共8分 ]
18. 試證明：假設r與s是集合刀上的自反關系，貝U&ns也是集合力上的自反關系.
試題解答
一、單項選擇題[每題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.
設今天上課,
[2分 ]
13、
[6分 ]
12.
設F：他去操場鍛煉，Q：他有時間,
[2分 ]
則命題公式為：P.
[4分 ]
[8分 ]
[12 分 ]
[4分 ]
[8分 ]
[12 分 ]
[6分 ]
則命題公式為：PT0 四、判斷說明題[每題7分，木題共14分 ]
13. 錯誤. [3分 ]
因為力中元素2沒有8中元素與之對應，故/不是力到8的函數(shù). [7分 ]
14. 錯誤. [3分 ]
不滿足“設G是一個有y個結點e條邊的連通簡單平面圖，假設v^3,則eW3/6.〞
[7分 ]
五.計算題[每題12分，此題共36分 ]
15. (PV2)一(RV。)。-I
14、(PV0V (RV。)
= ("E 0V (RV。)
=(1尸人1 g)v7?ve (析取范式)
16. (1) UAB) ={1}
(2) C4U3) ={1,2, {1},{2}}
(3) A- (A QB) =({1}, 1,2}
17. (1) G的圖形表示如圖一所示：
[3分 ]
[6分 ]
。 1 C
圖二
權為：1+1+3=5
圖一
[2 ] 鄰接矩陣：
_o 1 1 r
10 11
110 1
1110
MB MB
[3 ] 最小的生成樹如圖二中的粗線所示:
(10 分)
(12 分)
六、證明題[此題共8分 ]
18.證明：設
15、VxgJ,因為&自反，所以x Rx, BPg7?；
又因為S自反，所以xRx,即eS.
即 Vx, x>eROS
故ACS自反.
[4分 ]
[6分 ]
[8分 ]
【離散數(shù)學】題庫及答案三
一、單項選擇題[每題3分，此題共15分 ]
1.假設集合A = {a, {〃}},則下面表述正確的選項是[ ].
A. {/z}o4
C.
D. 0gA
2.
命題公式[PVQ ]的合取范式是[ ]
A.
(PA2)
B. (PA0) V (PVg)
16、
C.
D. ―i (—P /\—Q)
3.
無向樹r有8個結點,
則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}是點割集
D. {c}是點割集
B. P->-iQ = TtQ
D.「PQ)n。
17、
二、填空題[每題3分，此題共15分 ]
6. 設集合4={2.3,4}, B={1,2, 3,4}, R是刀到8的二元關系,
7? = ( xe A^y e是有4個結點，8條邊的無向連通圖，則從G中刪去 條邊，可以確定圖
G的一棵生成樹.
9. 設G是具有〃個結點m條邊上個面的連通平面圖，則m等于
10. 設個體域。={1,2},刀⑴為％大于1〞，則謂詞公式(3x)A{x)的真值為
三
18、、邏輯公式翻譯(每題6分，木題共12分)
11. 將語句“今天考試，明天放假?〞翻譯成命題公式.
12. 將語句“我去旅游，僅當我有時間?〞翻譯成命題公式.
四、判斷說明題(每題7分，此題共14分)
判斷下面各題正誤，并說明理由.
13. 如果圖G是無向圖，且其結點度數(shù)均為偶數(shù)，則圖G是歐拉圖.
14. 假設偏序集V4,人>的哈斯圖如圖二所示，則集合Z的最大元為最小元是八
五. 計算題(每題12分，此題共36分)
15 .設謂詞公式(女)(刀(x, y) T (Vz)5(y, x, z)),試
(1) 寫出量詞的轄域； (2)指出該公式的自由變元和約束變元.
16.
19、 設集合 /={⑴,1,2}, 8={1,{1,2}},試計算
(1) C4—8) ； (2) C4C1B) ； (3) AXB.
17. 設 G=, V={v\, v2> 巧，v4 ), E={(vi,V3), (v2,v3), (v2,v4)，(巧皿)}，試
(1)給出G的圖形表示； (2)寫出其鄰接矩陣；
(3) 求出每個結點的度數(shù)； (4)畫出其補圖的圖形.
六、證明題(此題共8分)
18. 設力，B是任意集合，試證明：假設Ax4=BxB,則
試題解答[供參考 ]
一、 單項選擇題[每題3分，此題共15分 ]
1. A 2. C 3. B 4. B 5?
20、D
二、 填空題[每題3分，此題共15分 ]
6. [<2, 2>, <2, 3>, <2,4>, <3, 3> ], <3, 4>, <4, 4> ]
7. , < b, b>
8. 5
9 . n+k-2
10. 真[或T,或1 ]
三、 邏輯公式翻譯[每題4分，此題共12分 ]
11. 設P：今天考試，Q：明天放假. [2分 ]
則命題公式為：PA0 [6分 ]
12. 設F：我去旅游，Q：我有時間， [2分 ]
則命題公式為：PT0 [6分 ]
四、 判斷說明題[每題7分，木題共14分 ]
13. 錯誤. [3分 ]
當圖G不連通時圖G不為歐拉
21、圖. [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) Q8={v{1},1>, <{1},{1,2}>,
22、<1, {1,2}>, <2,1>, <2,
17. (1) G的圖形表示為(如圖三)：
[3分 ]
[3 ] n，v2,巧，四結點的度數(shù)依次為1，2, 3, 2
[4 ] 補圖如圖四所示：
[6分 ]
[9分 ]
[12 分 ]
[1分 ]
[3分 ]
[5分 ]
[6分 ]
[7分 ]
[8分 ]
六、證明題[此題共8分 ]
18. 證明：設 xeAf 則Vv, x>eAxA,
因為 AxA=BxB,故x>gBxB9 則有 所以A^B.
設 則Vx, x>gBxB,
因為 4xA=BxB,故Vx, x>eAxA
23、,則有 xeA,所以 故得A=B.
【離散數(shù)學】題庫及答案四
一、單項選擇題[每題3分，此題共15分 ]
1. 設 A=(1，3.5,7,9).R=(2?，6),A 到 H 的關系 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}
24、 .則公式(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ù)的結點 B.G存在一個奇數(shù)度數(shù)的常點
GG不存在奇數(shù)度數(shù)的結點 D.G存。偶數(shù)度數(shù)的結點
乩n階無向完全圖K.的邊數(shù)及每個結點的度敬分別是( ).
A?"(n —1)與九 11 ji(w-*1)/2與 〞一1
C w — 1 與 n D. n(n — 1)與 ? —
25、 I
二、 填空題(每題3分，此題共15分)
6. 設堡 & 1一{1.2.3)?〃 =,：2.3).(/=口.4,?刪.41)(3一(?)= ?
7. 設Af 08F.2L" 從，利8的畫數(shù)/ =7V「1>?VO.2>}.從B
到C的函數(shù)拜=(<1.6>?<2心>).荊曠/等于 .
8. 設G = VV?E>職一個圖.|E| = M.則“的捎點度敝之和為 ?
9. 設G是代有〃 花邊&個而的連通平面圖.則刀+*-2= ?
1D，設中怵城本=1.？.3..?1J)為\的2倍大于站.刖周刊公式IV那.4(/)的底值為
三、 邏輯公式翻譯(每題6分，此題共12分)
11. 將
26、語句“如果他掌握了計算機的用法，那么他就能完成這項工作?〞翻譯成命題公式.
12. 將語句“前天下雨，昨天還是下雨?〞翻譯成命題公式.
四、 判斷說明題(判斷各題正誤，并說明理由.每題7分，此題共14分)
13. 段.1 = % , A. c ) ? R — ( V。，〃 > ? < A . /，A ? V r? ? V 以，6 > ? V 內, 〃 > , V 右，4 A ? VrM>} ?姻R是等價關系.
14. ( Vx)CP< r)AQ【y)f Rtr>)中世詞 丫 的轄帔為(P。)AQ( y)L
五、計算題(每題12分，此題共36分)
15. 設陞臺八=?d)?Hr站日
27、)，試〞算
(1)4 UBi (2)A—/h (3)AXB.
'St V，? E >,V* = < H?T?,?口,.}?￡ = {[叫."c ]?[玖,饑 ].[叫.口、 ].【化. 5 >,
? s ] ] ?試
[l>紛出G的圖形&示， 12>耳出其鄰也如所，
【3 ]求出每個靖點的度％ 【，>踴出北補圖的圖形.
I 7.試利用Kruskn W ?未出如卜所況M技圖中的/?小生成俐[要求寫出求解3項，.井 未此條小生成列的枳.
試題答案
一?單項選擇BH每題3分,本18共恃分 ]
1.0 2.A 3.B 4.C 5.H
二. 填空】![每小超3分.本弛共15
28、分 ]
6. [1.2.3 ]
7. [<. ]
?. 2。[或：2|E| ]
9?m
10. 假[或F.或。 ]
三. 謠輻公式翩澤[每小聘6分.本息［共12分 ]
IL i? PJlfctW了計算機的用法,Q：他推完成這項工作- [2分 ]
刪命題公式為，PfQ? [6分 ]
12. 設P,前天下雨.Q沖天還是下闌. [2分 ]
則命88公式為：PAQ.； [6分 ]
四、判斷說明網(wǎng)[督小18 7分,本18共M分 ]
13. 部誤. [3分 ]
R不是等價關系.因R中包含^，但不包含V<2/>?故不滿足傳遞性?
：[1 分
29、]
14. 銷誤“ 心分 ]
暗域為緊惟St詞V之后的梭小子公式[P[x ]AQC.y ]-R[x ] ]. 【7分 ]
五?計算1![每小12分,本11共36分 ]
15. n ]AUB =[a0?c?d ]i [4 分〉
[2〉A — 8 = [c ?..,..? Vd g >? Vd E>)
J6.[i ]g的圖形&示ftn圖一所示,
[3分 ]
(2〉郊接矩陣，
0 1 1 1
10 10
110 1
1
30、0 10
【6分 ]
(3)deg(vi )~3, drg(-v：J - 2? dvg(Vi)&3.
[9分 ]
degE ) = 2
(4〉補圖如圖二所示,
o
[12 分 ]
17. 用Kruskal ?法求產生的最小生成樹.步驟為,
w(vi ?v: ?3i J =i/i^r
[6分 ]
w( v> ? v? ^^4 ?選 ft =山巧 w【m.m)r9,選 = w【m?s>=l8 .遺 w3?3=22.ii e.=y?
最小生小樹州圖三所示,
圖三
[9分 ]
戒樹的杖 m =
31、 1 十3 +『+94 18+22=57
六.證明題[本J?共X分 ]
(!) P VQ
<1分 ]
⑵尸
(3)Q
ptvnin 前撾〉
T(D(2>r
以分〉
-3
(r/P AQ
Tf2)(3)/
T(l)E
(0)f( Pf 二 Q>
T(5>E
CP電則
[5分 ]
[6分 ]
[7分 ]
[8分 ]
<7 ]P
IftlUhiailE刪過慢中.公式引用的次序訶以不同?般引用的提正瓊特1分.利川倆個公K 團出有效結伯格1成2分,眼后同出站論得2或1分?
另.可以用頁值表臉證.
【離散數(shù)學】題庫及答案五
單項選擇題[每題3分，此題共15分
32、 ]
1. 設 A = {1.2,3,，，8= (2,3,4},A 到 B 的關系 R - {> 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.
33、假設集合A = M?6,r.d).則下面表述正的的是< 〉.
A.06A
C?{??M.d}￡A D. U.6JGA
3 .設個體域為整數(shù)韭.燃公式(Vx)(3y)(x->=2>的解釋可為( ).
A. 存在一整數(shù)工有整數(shù)y滿足x-y-2
B. 存在一建數(shù)工對任意整數(shù)y滿足工一y = 2
C. 對任一整數(shù)工存在整數(shù)】滴足x-y-2
D. 任一整數(shù)1對任意整數(shù)〉滿足x-> = 2
4. "階無向完全圖K,的邊數(shù)及每個結點的度數(shù)分別是( ).
A. n(w —與〃 B. n( w 1)與 〃一1
C?n —】與〞 D. w(n —1)/2 與 rr —1
5. 設G為連通無
34、向圖.則( 〉時?弓中存在歐拉回路.
A.G不存在奇數(shù)度數(shù)的結點 B.G存在一個新數(shù)度數(shù)的結點
C.G存在兩個奇數(shù)度數(shù)的結點 D.G存在偶數(shù)度數(shù)的結點
評卷人
二、填空題[每小18 3分,本a［共15分 ]
6. 設集含工是小于4的正整數(shù) ] ?用集合的列舉法.
7. 設 A = [l,2 ],T2 ],CTl,2}.從 A 到 B 的函數(shù)/ = [Vl?u>,V2,Q>}.從 B
到C的函致g = [,V6.l>}.則復合函數(shù) .
8. 設G-是一個圖，結或度敬之和為30.則G的邊數(shù)為 ?
9. 設G是具有，，個結點桁條邊▲個面的連通平面圖
35、，姻〞+A-2= .
10. 設個體域D = [2,3.4>.A[i ]為七小于3〞，則謂同公式[VjHAG ]的真值為
得分
評卷人
三?!！福公式小IS 6分，本原共12分 ]
11. 將語句“如果今天下雨.那么明天的比賽就要延期.〞疆譯成命題公式.
得分
評卷人
12. 將語句“地球是倒的，太陽也是圓的.〞翻譯成命題公式.
四、判斷說明IH[判斷各題正誤，井說明理由?每小H 7分，此題共
14分 ]
13. 設 A^{a.b.c.d} .R^{9,9.},則 R 是等 價關系.
14
36、. ( Vx)(P(x)AQ(y))-R(x)中量詞 V 的轄域為(P(x> AQ(>)).
得分
評卷入
五■計算?[每小MS 12分.本通共36分 ]
15. 設集合A = k?/>?c).B = (3?c,次).試計算 (l)A(JHi (3)AXB.
16. 設 G —VV?E>? V — (V| t vt ? ) ? E = {(V| ? ) < (vj t (vi. v<) > (1/1 ti?i )?
(l>給出G的圖形衰示8 (2)寫出其鄰接矩陣I
(3)戒出每個站點的度數(shù), (4)?出其補圖的圖形.
17. 試利用Kru9kd算法求出如下所示賦
37、權圖中的1ft小生或樹(妻求寫出求薪步轅〉，并 求此最小生成樹的權.
得分
評卷人
六、證明18(此題共8分)
18.成征明r [P-「Q ].
試題及答案
-■?項iswHim小m3分,本ai共is分 ]
I. B 2.D 3.C 4. D &A
二, 堵空JB[每小HI 3分.本恥共15分 ]
6. [I.2.3 ]
7. <<1.2>.<2.1?
9. m
10. fl
三、 il輯公式小H6分.本HI共12分 ]
H.?今天下Ifl.QZI天的比賽就要14期. [2分 ]
副命MS公式為【6分 ]
12.仗卜?地球屈圓的，。
38、■太陽是圓的. 【2分 ]
WlifrM公式為lP^Q. [6 分〉
四、 判斷說明18[每小JW 7分,本JB共14分 ]
IX WiM. [3 分 ]
R不是等價關系.因R中不含V〃M>.故不fMMfl反性. [7分 ]
M.正確. “分 ]
之后的 Jft 小子公 X[P[Jc ]AQ[y> ]. [7 分 ]
五小H技分.本H共36分 ]
15. ⑴AU8?M.y.,9..t.
39、1 )G的圖形表如圖一所不:
(2〉鄰接矩陣,
Vi
W W4
圖一
(3分)
d i i r
10 10
110 1
10 10
■ _
(6分〉
(3) = 2
(4〉補09如圖二所示i
【9分)
圖二
曰2分)
17. 用Kruskal W法求產生的最小生成樹?步曩為：
W(V| .vr) = l
W(Vr ? ) = 1
w(vj fVS) = 2
w(v> =3
選宜=ss 選 C：—VfV. 選 ei = Viv< 選 c4 —
W(V
40、t ? VF ) = 4 選 Cs =VjV? w (Vj f Vt > = 5 ij ci 33 v$v? 最小生成鈣如圖三所示.
【6分 ]
圖三
[9分 ]
最小生成樹的權W(T) = 1 + 1 + 2 + 3 + 4 + 5=16.
[12 分 ]
說明，用其他方法.結果正確參照給分.
六■證明18[本境共8分 ]
18.證明：
(l)P-Q
[1分 ]
(3)Q
(4)PAQ
(5UP V 9
(6U「Q)
P[附加前提 ]
T(2)(3)/
T(4)E
T(5>E
[2分 ]
[4分 ]
【5分 ]
[6分〉
[7分 ]
(7〉
41、P—r(?rQ〉
[8分 ]
說明：因BE明過程中,公式引用的次序可以不同?一般引用前提正確得1分,利用兩個公式 得出有效結論得1或2分，景后得出結論得2或1分.
另?可以用真值表驗證.
【離散數(shù)學】題庫及答案六
一、單項選擇題[每題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. 假設無向圖。的結點度數(shù)之和為20,則r；的邊數(shù)為( >?
A. 10 a 20
C.30 D.5
X無向圖G是根樹，結成數(shù)為1【)?的(；的邊數(shù)為( >?
A.
42、S R. 10
Q9 DJI
4. ft A(^)：j是人〞(了)口是學生,刪母甌“村的人是學生〞可荷門化為(
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)( 3 -r)F( J )-*G (x )
前提引入
(2)F(y)—G(y)
US(\).
C. (1)( 3^)(F( f >-*G(±>)
的提
43、引人
⑵FJM。())
ES(1).
D. (1)( 3JXF(x)-*Glr))
前捉引人
(2)F(ylt；【y)
ES(D.
二、 填空題(每題3分，此題共15分)
6. 設A = “.2}.Bu 1.2.3} ?則A到B上不同的函散個散為 ?
7. fin個靖點的無向完全圖的邊數(shù)為 ?
%假設無向圖G中存在歐枚路但不存在歐拉回路，則6的布散度敬的結點有
9. 設(；是a 10個結點的無向連通圖.結點的度教之和為3。，則從G中JH去 條邊后使之變成樹-
10. 設個體域D = < 1.2.3.1).則明詞公式(如 >人M )酒去旬俱后的等值式為
三、
44、邏輯公式翻譯(每題6分，此題共12分)
11. 將語句“昨天下雨〞翻譯成命題公式.
12. 將語句“小王今天上午或者去看電影或者去打球〞翻譯成命題公式.
四、 判斷說明題[判斷各題正誤，并說明理由.每題7分，木題共14分 ]
IX存在果合A與使得與同時成立.
14, 完全圖K,是平面圖.
五、 計算題[每題12分，此題共36分 ]
15. 墳偏序集VA,R＞的哈斯圖如F.B為A的升集.共中日=f仇〞.城
；!＞與出R的關宓表達式;
[2,凱出關系R的關系圖，
[3〉求出H的最大元,極大元.上界.
16. 1殳圖 G V = (納 g?s Mg )?Eu〔叫f
V
45、 I)> C v . th ) >.試
口 ]兩出 【；的圖形表示j
[2 ] 寫出其鄰樓用陣；
[3 ] 求出每個苗點的度數(shù)，
[4 ] 畫出圖G的樸踞的胡形.
17. 求P-[QAK＞的合取范式與主合取范式.
六、證明題[此題共8分 ]
18. 設A./3電任意集合.試訕明，看A = B.
試題答案及評分標準
[供參考 ]
一、■項選捧H[每小■ 3分，本聘共15分 ]
I. A 2. A 3LC
Z.W2H[B小H 3分.本JS共15分 ]
G?9
6.1
也6 .
lO.A[l ] VACZ>VA[3 ]V.4[1 ]
三, 邏Ml公每小趣6分.本贓
46、共I2分 ]
1L設ZS昨天TW. [2分〉
SH佑日公式為必 傍分 ]
12. 設P］小王今天上午去看電物
Q,小王今天上午去打璋 [2分 ]
峭命12公式丸r[P?-Q>.
或哲V【PA rQ ] [6 分 ]
四、 判唏說明18[每小18 7分，本Jg共H分 ]
13. 正確， 【3分 ]
例，設 [5 分 ]
WIW A€B 且 AC& *7 分〉
說明I畢山襯合條件的例均靖分.
1，正嘛? [3分 ]
完全兇K.燧平面圈. _
如K.可成611F圖示城人平而.
【7分〉
五、計??(?小部12分，此題矣36分)
15.
47、=^.<6.6>..< J ... . )? (4 分>
3】關系圖
[8分 ]
[3 ]集合B無最大元，耿太元為心與。?無上界- 〞2分 ]
16. M：
H ]關系圖
[3分 ]
[2 ]鄰樓平警
[ ]
O ]dc?[vj ] =3
dcg[ vt ]?2
<1心頃。=2
dc&[M ]= 2
[9分 ]
coibffl
<12 分、
17. PTQRR〉
?-PVCQAK> [2 分 ]
DT r P V Q> A【r P V R ] 合取范式 [5分】
m-
48、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 分，
q[rVVQVR ]人[rPVQV ??R ]A[，PV，QVR ] 主合取他式 32 分〉 大?ii明18[本H共M分 ]
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 分 ]
(2022更新）國家開放大學電大《離散數(shù)學本》期末題庫及答案
