離散數(shù)學(xué)形考任務(wù)17試題及答案完整版.docx

《離散數(shù)學(xué)形考任務(wù)17試題及答案完整版.docx》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)形考任務(wù)17試題及答案完整版.docx（29頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、2017年11月上交的離散數(shù)學(xué)形考任務(wù)一 本課程的教學(xué)內(nèi)容分為三個單元，其中第三單元的名稱是（A ）． 選擇一項： A.數(shù)理邏輯 B.集合論 C.圖論 D.謂詞邏輯 題目2 答案已保存 滿分10.00 標(biāo)記題目 題干 本課程的教學(xué)內(nèi)容按知識點將各種學(xué)習(xí)資源和學(xué)習(xí)環(huán)節(jié)進行了有機組合，其中第2章關(guān)系與函數(shù)中的第3個知識點的名稱是（D ）． 選擇一項： A.函數(shù) B.關(guān)系的概念及其運算 C.關(guān)系的性質(zhì)與閉包運算 D.幾個重要關(guān)系 題目3 答案已保存 滿分10.00 標(biāo)記題目 題干 本課程所有教學(xué)內(nèi)容的電視視頻講解集中在VOD點播版塊中，VOD點播

2、版塊中共有（B ）講． 選擇一項： A. 18 B. 20 C. 19 D. 17 題目4 答案已保存 滿分10.00 標(biāo)記題目 題干 本課程安排了7次形成性考核作業(yè)，第3次形成性考核作業(yè)的名稱是（C ）． 選擇一項： A.集合恒等式與等價關(guān)系的判定 B.圖論部分書面作業(yè) C.集合論部分書面作業(yè) D. 網(wǎng)上學(xué)習(xí)問答 題目5 答案已保存 滿分10.00 標(biāo)記題目 題干 課程學(xué)習(xí)平臺左側(cè)第1個版塊名稱是：（C ）． 選擇一項： A.課程導(dǎo)學(xué) B.課程公告 C.課程信息 D.使用幫助 題目6 答案已保存 滿分10.00 標(biāo)記題目 題干

3、 課程學(xué)習(xí)平臺右側(cè)第5個版塊名稱是：（D ）． 選擇一項： A.典型例題 B.視頻課堂 C.VOD點播 D.常見問題 題目7 答案已保存 滿分10.00 標(biāo)記題目 題干 “教學(xué)活動資料”版塊是課程學(xué)習(xí)平臺右側(cè)的第（A ）個版塊． 選擇一項： A. 6 B. 7 C. 8 D. 9 題目8 答案已保存 滿分10.00 標(biāo)記題目 題干 課程學(xué)習(xí)平臺中“課程復(fù)習(xí)”版塊下，放有本課程歷年考試試卷的欄目名稱是：（D ）． 選擇一項： A.復(fù)習(xí)指導(dǎo) B.視頻 C.課件 D.自測 請您按照課程導(dǎo)學(xué)與章節(jié)導(dǎo)學(xué)中安排學(xué)習(xí)進度、學(xué)習(xí)目標(biāo)和學(xué)習(xí)方法設(shè)計自己的學(xué)

4、習(xí)計劃，學(xué)習(xí)計劃應(yīng)該包括：課程性質(zhì)和目標(biāo)（參考教學(xué)大綱）、學(xué)習(xí)內(nèi)容、考核方式，以及自己的學(xué)習(xí)安排，字?jǐn)?shù)要求在100—500字．完成后在下列文本框中提交． 解答：學(xué)習(xí)計劃 學(xué)習(xí)離散數(shù)學(xué)任務(wù)目標(biāo)： 其一是通過學(xué)習(xí)離散數(shù)學(xué)，使學(xué)生了解和掌握在后續(xù)課程中要直接用到的一些數(shù)學(xué)概念和基本原理，掌握計算機中常用的科學(xué)論證方法，為后續(xù)課程的學(xué)習(xí)奠定一個良好的數(shù)學(xué)基礎(chǔ)； 其二是在離散數(shù)學(xué)的學(xué)習(xí)過程中，培養(yǎng)自學(xué)能力、抽象思維能力和邏輯推理能力，解決實際問題的能力，以提高專業(yè)理論水平。 其三是初步掌握處理離散結(jié)構(gòu)所必須的描述工具和方法 離散數(shù)學(xué)的主要內(nèi)容： 第一章節(jié)：主要介紹集合及其運算 第二章節(jié)：

5、主要介紹關(guān)系與函數(shù) 第三章節(jié)：主要介紹圖的基本概念及性質(zhì) 第四章節(jié)：主要介紹幾種特殊圖 第五章節(jié)：主要介紹樹及其應(yīng)用 第六章節(jié)：主要介紹命題邏輯 第七章節(jié)：主要介紹謂詞邏輯 離散數(shù)學(xué)的考核方式分為：了解、理解和掌握。 了解是能正確判別有關(guān)概念和方法；理解是能正確表達 有關(guān)概念和方法的含義；掌握是在理解的基礎(chǔ)上加以靈活應(yīng)用。 離散數(shù)學(xué)形考任務(wù)二 若集合A＝{a,{a},{1,2}}A＝{a,{a},{1,2}}，則下列表述正確的是(C )． 選擇一項： A.{a,{a}∈A{a,{a}∈A B.{1，2}?A{1，2}?A C.{a

6、}?A{a}?A D.?∈A?∈A 題目2 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，則A∪B–C =(A )． 選擇一項： A.{1, 2, 3, 4} B.{1, 2, 3, 5} C.{2, 3, 4, 5} D.{4, 5, 6, 7} 題目3 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)集合A= {1,aa}，則P(A) = (D )． 選擇一項： A.{{1}, {aa}} B.{,{1}, {aa}} C.{{1},{a},{1,a}}{{

7、1},{a},{1,a}} D.,{1},{a},{1,a}},{1},{a},{1,a}} 題目4 答案已保存 滿分10.00 標(biāo)記題目 題干 集合A={1, 2, 3, 4, 5, 6, 7, 8}上的關(guān)系R={|x+y=10且x, y∈A}，則R的性質(zhì)為（B）． 選擇一項： A.自反的 B.對稱的 C.傳遞且對稱的 D.反自反且傳遞的 題目5 答案已保存 滿分10.00 標(biāo)記題目 題干 如果R1和R2是A上的自反關(guān)系，則R1∪R2，R1∩R2，R1-R2中自反關(guān)系有（B）個 選擇一項： A. 0 B. 2 C. 1 D. 3

8、題目6 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除關(guān)系，B={2, 4, 6}，則集合B的最大元、最小元、上界、下界依次為( D)． 選擇一項： A.8、2、8、2 B.8、1、6、1 C.6、2、6、2 D.無、2、無、2 題目7 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)集合A={2, 4, 6, 8}，B={1, 3, 5, 7｝，A到B的關(guān)系R={| y = x +1｝，則R= (A )． 選擇一項： A. {<2, 3>, <4, 5>, <6, 7>} B.

9、 {<2, 1>, <4, 3>, <6, 5>} C.{<2, 1>, <3, 2>, <4, 3>} D.{<2, 2>, <3, 3>, <4, 6>} 題目8 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)集合A={1 , 2, 3}上的函數(shù)分別為：?= {<1, 2>，<2, 1>，<3, 3>}，g= {<1, 3>，<2, 2>，<3, 2>}，h= {<1, 3>，<2, 1>，<3, 1>}， 則h=（A）． 選擇一項： A.??g B.g?? C.??? D.g?g 題目9 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)A、B是兩個任

10、意集合，側(cè)A-B =?(B )． 選擇一項： A. A=B B. A ?B C. A ?B D.B= 題目10 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)集合A={1，2，3，4，5}，偏序關(guān)系是A上的整除關(guān)系，則偏序集上的元素5是集合A的（C ）． 選擇一項： A.最大元 B.最小元 C.極大元 D.極小元 離散數(shù)學(xué)作業(yè)3 離散數(shù)學(xué)集合論部分形成性考核書面作業(yè) 一、填空題 1．設(shè)集合，則P(A)-P(B )= {{3}，{1,3}，{2,3}，{1,2,3}} ，A B= {<1,1>,<1

11、,2>,<2,1>,<2,2>,<3,1>,<3.2>} ． 2．設(shè)集合A有10個元素，那么A的冪集合P(A)的元素個數(shù)為 1024 ． 3．設(shè)集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元關(guān)系， 則R的有序?qū)蠟? {<2, 2>，<2, 3>，<3, 2>}，<3,3> ． 4．設(shè)集合A={1, 2, 3, 4 }，B={6, 8, 12}， A到B的二元關(guān)系 R＝ 那么R－1＝ {<6,3>,<8,4>} 5．設(shè)集合A=｛a, b, c, d｝，A上的二元關(guān)系R={,

12、, , }，則R具有的性質(zhì)是　　沒有任何性質(zhì)　　　?。? 6．設(shè)集合A=｛a, b, c, d｝，A上的二元關(guān)系R={, , , }，若在R中再增加兩個元素　{,}　，則新得到的關(guān)系就具有對稱性． 7．如果R1和R2是A上的自反關(guān)系，則R1∪R2，R1∩R2，R1-R2中自反關(guān)系有 2 個． 8．設(shè)A={1, 2}上的二元關(guān)系為R={|xA，yA, x+y =10}，則R的自反閉包為 {<1,1>,<2,2>} ． 9．設(shè)R是集合A上的等價關(guān)系，且1

13、 , 2 , 3是A中的元素，則R中至少包含 <1,1>,<2,2>,<3,3> 等元素． 10．設(shè)集合A={1, 2}，B={a, b}，那么集合A到B的雙射函數(shù)是 {<1, a >, <2, b >}或{<1, b >, <2, a >} ． 二、判斷說明題（判斷下列各題，并說明理由．） 1．若集合A = {1，2，3}上的二元關(guān)系R={<1, 1>，<2, 2>，<1, 2>}，則 (1) R是自反的關(guān)系； (2) R是對稱的關(guān)系． 解：（1）錯誤。R不具有自反的關(guān)系，因

14、為<3,3>不屬于R。 （2）錯誤。R不具有對稱的關(guān)系，因為<2,1>不屬于R。 2．如果R1和R2是A上的自反關(guān)系，判斷結(jié)論：“R-11、R1∪R2、R1∩R2是自反的” 是否成立？并說明理由． 解：成立． 因為R1和R2是A上的自反關(guān)系，即IAR1，IAR2。 由逆關(guān)系定義和IAR1，得IA R1-1； 由IAR1，IAR2，得IA R1∪R2，IA R1R2。 所以，R1-1、R1∪R2、R1R2是自反的。 o o o o a b c d 圖一 o o o g e f h o 3．若偏序集的

15、哈斯圖如圖一所示， 則集合A的最大元為a，最小元不存在． 解：錯誤． 集合A的最大元不存在，a是極大元． 4．設(shè)集合A={1, 2, 3, 4}，B={2, 4, 6, 8}，，判斷下列關(guān)系f是否構(gòu)成函數(shù)f：，并說明理由． (1) f={<1, 4>, <2, 2,>, <4, 6>, <1, 8>}； (2)f={<1, 6>, <3, 4>, <2, 2>}； (3) f={<1, 8>, <2, 6>, <3, 4>, <4, 2,>}． 解： （1）不構(gòu)成函數(shù)。因為對于3屬于A，在B中沒有元素與之對應(yīng)。 （2）不構(gòu)成函數(shù)。因為對于4屬于A

16、，在B中沒有元素與之對應(yīng)。 （3）構(gòu)成函數(shù)。因為A中任意一個元素都有A中唯一的元素相對應(yīng)。 三、計算題 1．設(shè)，求：　 (1) (AB)~C； (2) (AB)- (BA) (3) P(A)－P(C)； (4) AB． 解：(1) (A∩B)∪~C={1}∪{1,3,5}={1,3,5} (2) (A∪B)- (B∩A)={1,2,4,5}-{1}={2,4,5} (3) P(A) ={Φ,{1},{4},{1,4}} P(C)={ Φ,{2},{4},{2,4}} P(A)－P(C)={{1},{1,4}} (4) A⊕B= (A∪B)- (B∩A

17、)= {2,4,5} 2．設(shè)A={{1},{2},1,2}，B={1,2,{1,2}}，試計算 （1）（A-B）； （2）（A∩B）； （3）AB． 解：（1）A-B ={{1},{2}} （2）A∩B ={1,2} （3）AB={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>， <{2},{1,2}>，<1,1>，<1,2>，<1, {1,2}>，<2,1>，<2,2>,<2, {1,2}>} 3．設(shè)A={1，2，3，4，5}，R={|xA

18、，yA且x+y4}，S={|xA，yA且x+y<0}，試求R，S，RS，SR，R-1，S-1，r(S)，s(R)． 解：R={<1,1>,<1,2>,<1,3><2,1><2,2><3,1>} S=空集 R*S=空集 S*R=空集 R-1={<1,1>,<2,1><3,1><1,2><2,2><1,3>} S-1 =空集 r(S)={<1,1><2,2><3,3><4,4><5,5>} s(R)={<1,1><1,2><1,3><2,1><2,2><3,1>} 4．設(shè)A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除關(guān)系，B

19、={2, 4, 6}． (1) 寫出關(guān)系R的表示式； (2 )畫出關(guān)系R的哈斯圖； (3) 求出集合B的最大元、最小元． 解： (1)R={<1,1><1,2><1,3><1,4><1,5><1,6><1,7><1,8><2,2><2,4><2,6><2,8><3,3><3,6><4,4><4,8><5,5><6,6><7,7><8,8>} (3)集合B沒有最大元，最小元是2 1 2 5 6 4 10 7 3 8 9 11 12 關(guān)系R的哈斯圖 1 2 3 4 6 9 5 7 8 10 11 12 關(guān)系

20、R的哈斯圖 1 2 3 4 6 9 5 7 8 10 11 12 關(guān)系R的哈斯圖 (2)關(guān)系R的唯斯圖 四、證明題 1．試證明集合等式：A (BC)=(AB) (AC)． 證明：設(shè)，若x∈A (BC)，則x∈A或x∈BC， 即 x∈A或x∈B 且 x∈A或x∈C． 即x∈AB 且 x∈AC ， 即 x∈T=(AB) (AC)， 所以A (BC) (AB) (AC)． 反之，若x∈(AB) (AC)，則x∈AB 且 x∈AC， 即x∈A或x∈B 且 x∈A或x∈C， 即x∈A或x∈BC， 即x

21、∈A (BC)， 所以(AB) (AC) A (BC)． 因此．A (BC)=(AB) (AC)． 2．試證明集合等式A (BC)=(AB) (AC)． 證明：設(shè)S=A∩(B∪C)，T=(A∩B)∪(A∩C)， 若x∈S，則x∈A且x∈B∪C，即 x∈A且x∈B 或 x∈A且x∈C， 也即x∈A∩B 或 x∈A∩C ，即 x∈T，所以ST． 反之，若x∈T，則x∈A∩B 或 x∈A∩C， 即x∈A且x∈B 或 x∈A且x∈C 也即x∈A且x∈B∪C，即x∈S，所以TS． 因此T=S． 3．對任

22、意三個集合A, B和C，試證明：若AB = AC，且A，則B = C． 證明： （1） 對于任意∈AB，其中a∈A，b∈B,因為AB= AC， 必有∈AC,其中b ∈C因此BC （2）同理，對于任意∈AC,其中，a∈A，c∈C，因為AB= AC 必有∈AB，其中c∈B，因此CB有（1）（2）得B=C 4．試證明：若R與S是集合A上的自反關(guān)系，則R∩S也是集合A上的自反關(guān)系． 證明： 若R與S是集合A上的自反關(guān)系，則任意x∈A,＜x,x＞∈R,＜x,x＞∈S, 從而＜x,x＞∈R∩S,注意x是A的任意元素，所以R∩S也是集合

23、A上的自反關(guān)系． 離散數(shù)學(xué)形考任務(wù)四 設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為(B )． 選擇一項： A. 6 B. 5 C. 4 D. 3 題目2 答案已保存 滿分10.00 標(biāo)記題目 題干 如圖一所示，以下說法正確的是 (D ) ． 選擇一項： A.{(a,ea,e)}是割邊 B.{(a,ea,e)}是邊割集 C.{(a,e),(b,c)(a,e),(b,c)}是邊割集 D.{(d,ed,e)}是邊割集 題目3 答案已保存 滿分10.00 標(biāo)記題目 題干 如圖三所示，以下說法正確的是 (C ) ． 選擇一項：

24、A.{(a,da,d)}是割邊 B.{(a,da,d)}是邊割集 C.{(a,d),(b,d)(a,d),(b,d)}是邊割集 D.{(b,db,d)}是邊割集 題目4 答案已保存 滿分10.00 標(biāo)記題目 題干 無向圖G存在歐拉回路，當(dāng)且僅當(dāng)（C ）. 選擇一項： A. G中所有結(jié)點的度數(shù)全為偶數(shù) B. G中至多有兩個奇數(shù)度結(jié)點 C. G連通且所有結(jié)點的度數(shù)全為偶數(shù) D. G連通且至多有兩個奇數(shù)度結(jié)點 題目5 答案已保存 滿分10.00 標(biāo)記題目 題干 若G是一個歐拉圖，則G一定是(C )． 選擇一項： A. 平面圖 B. 漢密爾

25、頓圖 C. 連通圖 D. 對偶圖 題目6 答案已保存 滿分10.00 標(biāo)記題目 題干 無向樹T有8個結(jié)點，則T的邊數(shù)為(B )． 選擇一項： A. 6 B. 7 C. 8 D. 9 題目7 答案已保存 滿分10.00標(biāo)記題目 題干 已知一棵無向樹T中有8個頂點，4度、3度、2度的分支點各一個，T的樹葉數(shù)為(A )． 選擇一項： A. 5 B. 8 C. 3 D. 4 題目8 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為(C )． 選擇一項： A. 1 B. 6 C. 7 D. 14 題目9

26、 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( D )． 選擇一項： A. （a）只是弱連通的 B. （b）只是弱連通的 C. （c）只是弱連通的 D. （d）只是弱連通的 題目10 答案已保存 滿分10.00 標(biāo)記題目 題干 以下結(jié)論正確的是(D )． 選擇一項： A. 無向完全圖都是歐拉圖 B. 有n個結(jié)點n－1條邊的無向圖都是樹 C. 無向完全圖都是平面圖 D. 樹的每條邊都是割邊 離散數(shù)學(xué)作業(yè)5 離散數(shù)學(xué)圖論部分形成性考核書面作業(yè) 本課程形成性考核書面作業(yè)共

27、3次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型（除單項選擇題外）安排練習(xí)題目，目的是通過綜合性書面作業(yè)，使同學(xué)自己檢驗學(xué)習(xí)成果，找出掌握的薄弱知識點，重點復(fù)習(xí)，爭取盡快掌握。本次形考書面作業(yè)是第二次作業(yè)，大家要認真及時地完成圖論部分的綜合練習(xí)作業(yè)。 要求：將此作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，要求2010年12月5日前完成并上交任課教師（不收電子稿）。并在05任務(wù)界面下方點擊“保存”和“交卷”按鈕，以便教師評分。 一、填空題 1．已知圖G中有1個1度結(jié)點，2個2度結(jié)點，3個3度結(jié)點，4個4度結(jié)點，則G的邊數(shù)是

28、 15 ． 2．設(shè)給定圖G(如右由圖所示)，則圖G的點割集是 ． 3．設(shè)G是一個圖，結(jié)點集合為V，邊集合為E，則 G的結(jié)點 度數(shù)之和 等于邊數(shù)的兩倍． 4．無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且 不含奇數(shù)度結(jié)點 ． 5．設(shè)G=是具有n個結(jié)點的簡單圖，若在G中每一對結(jié)點度數(shù)之和大于等于︱V︱ ，則在G中存在一條漢密爾頓回路． 161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616

29、16161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616166．若圖G=中具有一條漢密爾頓回路，則對于結(jié)點集V的每個非空子集S，在G中刪除S中的所有結(jié)點得到的連通分支數(shù)為W，則S中結(jié)點數(shù)|S|與W滿足的關(guān)系式為 ． 7．設(shè)完全圖K有n個結(jié)點(n2)，m條邊，當(dāng)n為奇數(shù)時，K中存在歐拉回路． 8．結(jié)點數(shù)v與邊數(shù)e滿足 e= v－1 關(guān)系的無向連通圖就是樹

30、． 9．設(shè)圖G是有6個結(jié)點的連通圖，結(jié)點的總度數(shù)為18，則可從G中刪去 條邊后使之變成樹． 10．設(shè)正則5叉樹的樹葉數(shù)為17，則分支數(shù)為i = 4 ． 二、判斷說明題（判斷下列各題，并說明理由．） 1．如果圖G是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路．． 答：錯誤。應(yīng)敘述為：“如果圖G是無向連通圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路。” 2．如下圖所示的圖G存在一條歐拉回路． 答：錯誤。因為圖中存在奇數(shù)度結(jié)點，所以不存在歐拉回路。 3．如下圖所示的圖G不是歐拉圖而是漢密爾頓圖． G

31、 答：正確。因為有4個結(jié)點的度數(shù)為奇數(shù)，所以不是歐拉圖；而對于圖中任意點集中的非空子集，都有V1。其中是從圖中刪除結(jié)點及其關(guān)聯(lián)的邊。 4．設(shè)G是一個有7個結(jié)點16條邊的連通圖，則G為平面圖． 答：錯誤。若G是連通平面圖，那么若， 而16>37－6，所以不滿足定理條件，敘述錯誤。 171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171

32、71717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717 5．設(shè)G是一個連通平面圖，且有6個結(jié)點11條邊，則G有7個面． 答：正確。因為連通平面圖滿足歐拉公式。即：。由此題條件知6-11+7=2成立。 三、計算題 1．設(shè)G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，試 (1) 給出G的圖形表示

33、； (2) 寫出其鄰接矩陣； (3) 求出每個結(jié)點的度數(shù)； (4) 畫出其補圖的圖形． 答：（1） （2） （3） 1、2、4、3、2 （4） 2．圖G=，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，對應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及

34、5，試 （1）畫出G的圖形； （2）寫出G的鄰接矩陣； （3）求出G權(quán)最小的生成樹及其權(quán)值． b c 解：（1） 。 。 2 1 a。 6 4 2 1 3 。 。 e 5 d （2） （3）

35、 b。 。c 2 1 a。 1 e。 3 。d 其權(quán)值為：7 3．已知帶權(quán)圖G如右圖所示． (1) 求圖G的最小生成樹； (2)計算該生成樹的權(quán)值． 答：(1) 1 2

36、 7 5 3 (2) 權(quán)值為18。 4．設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31，試畫出相應(yīng)的最優(yōu)二叉樹，計算該最優(yōu)二叉樹的權(quán)． 解： 65 17 48 5 12 17 31 2 3 5 7

37、 權(quán)值為65。 四、證明題 1．設(shè)G是一個n階無向簡單圖，n是大于等于3的奇數(shù)．證明圖G與它的補圖中的奇數(shù)度頂點個數(shù)相等． 證明：設(shè)a為G中任意一個奇數(shù)度頂點，由定義，a仍為頂點，為區(qū)分起見，記為a’, 則deg(a)+deg(a’)=n-1, 而n為奇數(shù)，則a’必為奇數(shù)度頂點。由a的任意性，容易得知結(jié)論成立。 2．設(shè)連通圖G有k個奇數(shù)度的結(jié)點，證明在圖G中至少要添加條邊才能使其成為歐拉圖． 證明：由定理推論知：在任何圖中，度數(shù)為奇數(shù)的結(jié)點必是偶數(shù)個，則k是偶數(shù)。又由歐拉圖的充要條件是圖G中不含奇數(shù)度結(jié)點。因此，只要在每對奇數(shù)度結(jié)點間各加

38、一條邊，使圖G的所有結(jié)點的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖。故最少要加條邊才能使其成為歐拉圖。 形考任務(wù)六 設(shè)P：我將去打球，Q：我有時間．命題 “我將去打球，僅當(dāng)我有時間” 時符號化為(B )． 選擇一項： A. B. C. D. 題目2 還未回答 滿分10.00 標(biāo)記題目 題干 命題公式(PQ) 的析取范式是 (D ) 選擇一項： A. (PQ)R B. (PQ)R C. (PQ)R D. (PQ)R 題目3 還未回答 滿分10.00 標(biāo)記題目 題干 命題公式(PQ) 析取范式是(A )． 選擇一項： A.PQ B. C. D. 題目4

39、 答案已保存 滿分10.00 標(biāo)記題目 題干 下列公式成立的為(D )． 選擇一項： A. PQ PQ B. PQ PQ C. QP P D. P(PQ)Q 題目5 答案已保存 滿分10.00 標(biāo)記題目 題干 下列公式 (C )為重言式． 選擇一項： A. PQPQ B. (Q(PQ)) (Q(PQ)) C. (P(QP))(P(PQ)) D. (P(PQ)) Q 題目6 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)A（x）：x是人，B（x）：x是教師，則命題“有人是教師”可符號化為（D ）． 選擇一項： A.(ョx)(A(x)

40、∧B(x))(ョx)(A(x)∧B(x)) B.(?x)(A(x)∧B(x))(?x)(A(x)∧B(x)) C.(?x)(A(x)→B(x))(?x)(A(x)→B(x)) D.(ョx)(A(x)∧B(x))(ョx)(A(x)∧B(x)) 題目7 還未回答 滿分10.00 標(biāo)記題目 題干表達式("x)(P(x,y) Q(z)) y(R(x,y))→"z Q(z))中 ("x) 中轄域是(B )． 選擇一項： A.P(x,y) B.P(x,y) Q(z) C.R(x,y) D. 題目8 答案已保存 滿分10.00 標(biāo)記題目 題干 A 設(shè)個體域D={

41、a,b,c}，那么謂詞 公式去量詞后的等值式為A． 選擇一項： A. (A(a)A(b)A(c))(B(a)B(b)B(b)) B. (A(a)A(b)A(c))(B(a)B(b)B(b)) C. (A(a)A(b)A(c))(B(a)B(b)B(b)) D. (A(a)A(b)A(c))(B(a)B(b)B(b)) 題目9 還未回答 滿分10.00 標(biāo)記題目 題干 A 下列等價公式成立的為(A )． 選擇一項： A.PP Q Q B. C. D. 題目10 還未回答 滿分10.00 標(biāo)記題目 題干 A 設(shè)個體域D是整數(shù)集合，則命題?xy (x

42、y = y)的真值是（A ）． 選擇一項： A. T B. F C.不確定 D.以上說法都不是 離散數(shù)學(xué)作業(yè)7 離散數(shù)學(xué)數(shù)理邏輯部分形成性考核書面作業(yè) 本課程形成性考核書面作業(yè)共3次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型（除單項選擇題外）安排練習(xí)題目，目的是通過綜合性書面作業(yè)，使同學(xué)自己檢驗學(xué)習(xí)成果，找出掌握的薄弱知識點，重點復(fù)習(xí)，爭取盡快掌握。本次形考書面作業(yè)是第三次作業(yè)，大家要認真及時地完成數(shù)理邏輯部分的綜合練習(xí)作業(yè)。 要求：將此作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，要求本學(xué)

43、期第17周末前完成并上交任課教師（不收電子稿）。并在07任務(wù)界面下方點擊“保存”和“交卷”按鈕，以便教師評分。 一、填空題 1．命題公式的真值是　1或T 　． 2．設(shè)P：他生病了，Q：他出差了．R：我同意他不參加學(xué)習(xí). 則命題“如果他生病或出差了，我就同意他不參加學(xué)習(xí)”符號化的結(jié)果為 （PQ）R 3．含有三個命題變項P，Q，R的命題公式PQ的主析取范式是 (PQR)(PQR) 4．設(shè)P(x)：x是人，Q(x)：x去上課，則命題“有人去上課．” 可符號化為 x(P(x) Q(x)) ．

44、 5．設(shè)個體域D＝{a, b},那么謂詞公式消去量詞后的等值式為 (A(a) A(b)) ((B(a) B(b)) ． 6．設(shè)個體域D＝{1, 2, 3}，A(x)為“x大于3”，則謂詞公式($x)A(x) 的真值為0(F) ． 7．謂詞命題公式("x)((A(x)B(x)) C(y))中的自由變元為 y ． 8．謂詞命題公式("x)(P(x) Q(x) R(x，y))中的約束變元為 x ． 三、公式翻譯題 1．請將語句“今天是天晴”翻譯成命題公式． 設(shè)P：今天是晴天。 則P。

45、 2．請將語句“小王去旅游，小李也去旅游．”翻譯成命題公式． 設(shè)P：小王去旅游。 Q：小李去旅游。 則PQ 3．請將語句“他去旅游，僅當(dāng)他有時間”翻譯成命題公式． 設(shè)P：他去旅游。 Q：他有時間。 則PQ 4．請將語句“41次列車下午五點開或六點開．”翻譯成命題公式． 設(shè)P：41次列車下午五點。 Q：41次列車下午六點開。 則P或Q 5．請將語句 “有人不去工作”翻譯成謂詞公式． 設(shè) A（x）：x是人 B（x）：去工作 x(A(x) B(x)) 6．請將語句“所有人都努力工作．”翻譯成謂詞公式． 設(shè) A（x）：x是人

46、B（x）：努力工作 x(A(x) B(x)) 四、判斷說明題（判斷下列各題，并說明理由．） 1．命題公式PP的真值是1。 答：錯誤。因為P和P的否不能同時為真。 2．命題公式中的約束變元為y。 答：錯誤。該式中的約束元為x。 3．謂詞公式中x量詞的轄域為 P(x,y) ("z)Q(x,y,z) 。 答：錯誤。謂詞公式中x量詞的轄域為P(x,y)。 若謂詞公式變?yōu)椋?，x量詞的轄域為P(x,y) ("z)Q(x,y,z)。 4．下面的推理是否正確，請給予說明． (1) ("x)A(x) B(x)

47、 前提引入 (2) A(y) B(y) US (1) 答：錯誤。 因為B(x)不受全稱量詞"x的約束，不能使用全稱指定規(guī)則。 （2）應(yīng)為A(y) B(x)，換名時，約束元與自由變元不能混淆。 四．計算題 1． 求PQR的析取范式，合取范式、主析取范式，主合取范式． PQRPQR （析取范式） （PQR） （合取范式） 真值表： P Q R P 原式 極小項 極大項 0 0 0 1 1 PPP 0 0 1 1 1 PQR 0 1

48、 0 1 1 PQR 0 1 1 1 1 PQR 1 0 0 0 0 PQR 1 0 1 0 1 PQR 1 1 0 0 1 PQR 1 1 1 0 1 PQR 主析取范式（PPP）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR） 主合取范式（PQR） 2．求命題公式(PQ)(RQ) 的主析取范式、主合取范式． 真值表： P Q R （PQ） RQ 原式 極小項 極大項 0 0 0 1 0 1 PPP 0 0 1 1 1 1

49、PQR 0 1 0 0 1 1 PQR 0 1 1 0 1 1 PQR 1 0 0 0 0 0 PQR 1 0 1 0 1 1 PQR 1 1 0 0 1 1 PQR 1 1 1 0 1 1 PQR 主析取范式（PPP）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR） 主合取范式（PQR） 3．設(shè)謂詞公式． （1）試寫出量詞的轄域； （2）指出該公式的自由變元和約束變元． 答：（1）x的轄域為P（x,y）zQ(x,y,z) z的轄域為Q(x,y,z

50、) y的轄域為R(y,z) (2) 約束變元為 P（x,y）zQ(x,y,z)中的x Q(x,y,z) 中的 z R(y,z) 中的y 自由變元為 P（x,y）zQ(x,y,z)中的y R(y,z)中的z 4．設(shè)個體域為D={a1, a2}，求謂詞公式"y$xP(x,y)消去量詞后的等值式； 答：謂詞公式"y$xP(x,y)消去量詞后的等值式為 =$xP（x, a1）$xP（x, a2） =P (a1, a2） P (a1, a2）(P(a1, a2） P (a1, a2)) 五、證明題 1．試證明 (P(QR))PQ與 (PQ)等價． 證明：(P(QR))PQ P(QR))PQ PQ （PQ） 2．試證明(AB) (BC) CA 證明：(AB) (BC) C (AB) (BC) C (AB) (B C) (C C) (AB) ((BC) 0) (AB) (BC) (A (B C) )( B (B C)) (A (B C) )0 A (B C) (A B C) 故由左邊不可推出右邊A