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

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

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

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

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

5、主要介紹關(guān)系與函數(shù) 第三章節(jié)：主要介紹圖的基本概念及性質(zhì) 第四章節(jié)：主要介紹幾種特殊圖 第五章節(jié)：主要介紹樹及其應(yīng)用 第六章節(jié)：主要介紹命題邏輯 第七章節(jié)：主要介紹謂詞邏輯 離散數(shù)學(xué)的考核方式分為：了解、理解和掌握。 了解是能正確判別有關(guān)概念和方法；理解是能正確表達(dá) 有關(guān)概念和方法的含義；掌握是在理解的基礎(chǔ)上加以靈活應(yīng)用。 離散數(shù)學(xué)形考任務(wù)二 若集合A＝{a,{a},{1,2}}A＝{a,{a},{1,2}}，則下列表述正確的是(C )． 選擇一項(xiàng)： 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 )． 選擇一項(xiàng)： 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 )． 選擇一項(xiàng)： 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）． 選擇一項(xiàng)： A.自反的 B.對(duì)稱的 C.傳遞且對(duì)稱的 D.反自反且傳遞的 題目5 答案已保存 滿分10.00 標(biāo)記題目 題干 如果R1和R2是A上的自反關(guān)系，則R1∪R2，R1∩R2，R1-R2中自反關(guān)系有（B）個(gè) 選擇一項(xiàng)： 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)． 選擇一項(xiàng)： 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 )． 選擇一項(xiàng)： 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）． 選擇一項(xiàng)： A.??g B.g?? C.??? D.g?g 題目9 答案已保存 滿分10.00 標(biāo)記題目 題干 設(shè)A、B是兩個(gè)任

10、意集合，側(cè)A-B =?(B )． 選擇一項(xiàng)： 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 ）． 選擇一項(xiàng)： 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個(gè)元素，那么A的冪集合P(A)的元素個(gè)數(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中再增加兩個(gè)元素　{,}　，則新得到的關(guān)系就具有對(duì)稱性． 7．如果R1和R2是A上的自反關(guān)系，則R1∪R2，R1∩R2，R1-R2中自反關(guān)系有 2 個(gè)． 8．設(shè)A={1, 2}上的二元關(guān)系為R={|xA，yA, x+y =10}，則R的自反閉包為 {<1,1>,<2,2>} ． 9．設(shè)R是集合A上的等價(jià)關(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是對(duì)稱的關(guān)系． 解：（1）錯(cuò)誤。R不具有自反的關(guān)系，因

14、為<3,3>不屬于R。 （2）錯(cuò)誤。R不具有對(duì)稱的關(guān)系，因?yàn)?2,1>不屬于R。 2．如果R1和R2是A上的自反關(guān)系，判斷結(jié)論：“R-11、R1∪R2、R1∩R2是自反的” 是否成立？并說明理由． 解：成立． 因?yàn)镽1和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，最小元不存在． 解：錯(cuò)誤． 集合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ù)。因?yàn)閷?duì)于3屬于A，在B中沒有元素與之對(duì)應(yīng)。 （2）不構(gòu)成函數(shù)。因?yàn)閷?duì)于4屬于A

16、，在B中沒有元素與之對(duì)應(yīng)。 （3）構(gòu)成函數(shù)。因?yàn)锳中任意一個(gè)元素都有A中唯一的元素相對(duì)應(yīng)。 三、計(jì)算題 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}}，試計(jì)算 （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．對(duì)任

22、意三個(gè)集合A, B和C，試證明：若AB = AC，且A，則B = C． 證明： （1） 對(duì)于任意∈AB，其中a∈A，b∈B,因?yàn)锳B= AC， 必有∈AC,其中b ∈C因此BC （2）同理，對(duì)于任意∈AC,其中，a∈A，c∈C，因?yàn)锳B= 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 )． 選擇一項(xiàng)： A. 6 B. 5 C. 4 D. 3 題目2 答案已保存 滿分10.00 標(biāo)記題目 題干 如圖一所示，以下說法正確的是 (D ) ． 選擇一項(xiàng)： 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 ) ． 選擇一項(xiàng)：

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 ）. 選擇一項(xiàng)： A. G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) B. G中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) C. G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) D. G連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) 題目5 答案已保存 滿分10.00 標(biāo)記題目 題干 若G是一個(gè)歐拉圖，則G一定是(C )． 選擇一項(xiàng)： A. 平面圖 B. 漢密爾

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

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

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

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

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

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

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

32、71717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717 5．設(shè)G是一個(gè)連通平面圖，且有6個(gè)結(jié)點(diǎn)11條邊，則G有7個(gè)面． 答：正確。因?yàn)檫B通平面圖滿足歐拉公式。即：。由此題條件知6-11+7=2成立。 三、計(jì)算題 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) 求出每個(gè)結(jié)點(diǎn)的度數(shù)； (4) 畫出其補(bǔ)圖的圖形． 答：（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) }，對(duì)應(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)計(jì)算該生成樹的權(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)二叉樹，計(jì)算該最優(yōu)二叉樹的權(quán)． 解： 65 17 48 5 12 17 31 2 3 5 7

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

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

39、 答案已保存 滿分10.00 標(biāo)記題目 題干 下列公式成立的為(D )． 選擇一項(xiàng)： A. PQ PQ B. PQ PQ C. QP P D. P(PQ)Q 題目5 答案已保存 滿分10.00 標(biāo)記題目 題干 下列公式 (C )為重言式． 選擇一項(xiàng)： 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是教師，則命題“有人是教師”可符號(hào)化為（D ）． 選擇一項(xiàng)： 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)記題目 題干表達(dá)式("x)(P(x,y) Q(z)) y(R(x,y))→"z Q(z))中 ("x) 中轄域是(B )． 選擇一項(xiàng)： A.P(x,y) B.P(x,y) Q(z) C.R(x,y) D. 題目8 答案已保存 滿分10.00 標(biāo)記題目 題干 A 設(shè)個(gè)體域D={

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

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

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

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

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

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

47、 前提引入 (2) A(y) B(y) US (1) 答：錯(cuò)誤。 因?yàn)锽(x)不受全稱量詞"x的約束，不能使用全稱指定規(guī)則。 （2）應(yīng)為A(y) B(x)，換名時(shí)，約束元與自由變?cè)荒芑煜? 四．計(jì)算題 1． 求PQR的析取范式，合取范式、主析取范式，主合取范式． PQRPQR （析取范式） （PQR） （合取范式） 真值表： P Q R P 原式 極小項(xiàng) 極大項(xiàng) 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 原式 極小項(xiàng) 極大項(xiàng) 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）指出該公式的自由變?cè)图s束變?cè)? 答：（1）x的轄域?yàn)镻（x,y）zQ(x,y,z) z的轄域?yàn)镼(x,y,z

50、) y的轄域?yàn)镽(y,z) (2) 約束變?cè)獮? P（x,y）zQ(x,y,z)中的x Q(x,y,z) 中的 z R(y,z) 中的y 自由變?cè)獮? P（x,y）zQ(x,y,z)中的y R(y,z)中的z 4．設(shè)個(gè)體域?yàn)镈={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)等價(jià)． 證明：(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