2017年11月上交的離散數(shù)學(xué)形考任務(wù)一本課程的教學(xué)內(nèi)容分為三個單元，其中第三單元的名稱是（A ）選擇一項(xiàng)：A.數(shù)理邏輯B.集合論C.圖論D.謂詞邏輯題目2答案已保存滿分10.00標(biāo)記題目題干本課程的教學(xué)內(nèi)容按知識點(diǎn)將各種學(xué)習(xí)資源和學(xué)習(xí)環(huán)節(jié)進(jìn)行了有機(jī)組合，其中第2章關(guān)系與函數(shù)中的第3個知識點(diǎn)的名稱是（D ）選擇一項(xiàng)：A.函數(shù)B.關(guān)系的概念及其運(yùn)算C.關(guān)系的性質(zhì)與閉包運(yùn)算D.幾個重要關(guān)系題目3答案已保存滿分10.00標(biāo)記題目題干本課程所有教學(xué)內(nèi)容的電視視頻講解集中在VOD點(diǎn)播版塊中，VOD點(diǎn)播版塊中共有（B ）講選擇一項(xiàng)：A. 18B. 20C. 19D. 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í)平臺左側(cè)第1個版塊名稱是：（C ）選擇一項(xiàng)：A.課程導(dǎo)學(xué)B.課程公告C.課程信息D.使用幫助題目6答案已保存滿分10.00標(biāo)記題目題干課程學(xué)習(xí)平臺右側(cè)第5個版塊名稱是：（D ）選擇一項(xiàng)：A.典型例題B.視頻課堂C.VOD點(diǎn)播D.常見問題題目7答案已保存滿分10.00標(biāo)記題目題干“教學(xué)活動資料”版塊是課程學(xué)習(xí)平臺右側(cè)的第（A ）個版塊選擇一項(xiàng)：A. 6B. 7C. 8D. 9題目8答案已保存滿分10.00標(biāo)記題目題干課程學(xué)習(xí)平臺中“課程復(fù)習(xí)”版塊下，放有本課程歷年考試試卷的欄目名稱是：（D ）選擇一項(xiàng)：A.復(fù)習(xí)指導(dǎo)B.視頻C.課件D.自測請您按照課程導(dǎo)學(xué)與章節(jié)導(dǎo)學(xué)中安排學(xué)習(xí)進(jìn)度、學(xué)習(xí)目標(biāo)和學(xué)習(xí)方法設(shè)計(jì)自己的學(xué)習(xí)計(jì)劃，學(xué)習(xí)計(jì)劃應(yīng)該包括：課程性質(zhì)和目標(biāo)（參考教學(xué)大綱）、學(xué)習(xí)內(nèi)容、考核方式，以及自己的學(xué)習(xí)安排，字?jǐn)?shù)要求在100500字完成后在下列文本框中提交解答：學(xué)習(xí)計(jì)劃學(xué)習(xí)離散數(shù)學(xué)任務(wù)目標(biāo)：其一是通過學(xué)習(xí)離散數(shù)學(xué)，使學(xué)生了解和掌握在后續(xù)課程中要直接用到的一些數(shù)學(xué)概念和基本原理，掌握計(jì)算機(jī)中常用的科學(xué)論證方法，為后續(xù)課程的學(xué)習(xí)奠定一個良好的數(shù)學(xué)基礎(chǔ)；其二是在離散數(shù)學(xué)的學(xué)習(xí)過程中，培養(yǎng)自學(xué)能力、抽象思維能力和邏輯推理能力，解決實(shí)際問題的能力，以提高專業(yè)理論水平。其三是初步掌握處理離散結(jié)構(gòu)所必須的描述工具和方法離散數(shù)學(xué)的主要內(nèi)容：第一章節(jié)：主要介紹集合及其運(yùn)算第二章節(jié)：主要介紹關(guān)系與函數(shù)第三章節(jié)：主要介紹圖的基本概念及性質(zhì)第四章節(jié)：主要介紹幾種特殊圖第五章節(jié)：主要介紹樹及其應(yīng)用第六章節(jié)：主要介紹命題邏輯第七章節(jié)：主要介紹謂詞邏輯離散數(shù)學(xué)的考核方式分為：了解、理解和掌握。 了解是能正確判別有關(guān)概念和方法；理解是能正確表達(dá) 有關(guān)概念和方法的含義；掌握是在理解的基礎(chǔ)上加以靈活應(yīng)用。離散數(shù)學(xué)形考任務(wù)二若集合Aa,a,1,2Aa,a,1,2，則下列表述正確的是(C )選擇一項(xiàng)：A.a,aAa,aAB.1，2A1，2AC.aAaAD.AA題目2答案已保存滿分10.00標(biāo)記題目題干設(shè)集合A=1, 2, 3，B=3, 4, 5，C=5, 6, 7，則ABC =(A )選擇一項(xiàng)：A.1, 2, 3, 4B.1, 2, 3, 5C.2, 3, 4, 5D.4, 5, 6, 7題目3答案已保存滿分10.00標(biāo)記題目題干設(shè)集合A= 1,aa，則P(A) = (D )選擇一項(xiàng)：A.1, aaB.,1, aaC.1,a,1,a1,a,1,aD.,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>|x+y=10且x, yA，則R的性質(zhì)為（B）選擇一項(xiàng)：A.自反的B.對稱的C.傳遞且對稱的D.反自反且傳遞的題目5答案已保存滿分10.00標(biāo)記題目題干如果R1和R2是A上的自反關(guān)系，則R1R2，R1R2，R1-R2中自反關(guān)系有（B）個選擇一項(xiàng)：A. 0B. 2C. 1D. 3題目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、2B.8、1、6、1C.6、2、6、2D.無、2、無、2題目7答案已保存滿分10.00標(biāo)記題目題干設(shè)集合A=2, 4, 6, 8，B=1, 3, 5, 7，A到B的關(guān)系R=<x, y>| y = x +1，則R= (A )選擇一項(xiàng)：A. <2, 3>, <4, 5>, <6, 7>B. <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.gB.gC.D.gg題目9答案已保存滿分10.00標(biāo)記題目題干設(shè)A、B是兩個任意集合，側(cè)A-B =(B )選擇一項(xiàng)：A. A=BB. A BC. A BD.B=題目10答案已保存滿分10.00標(biāo)記題目題干設(shè)集合A=1，2，3，4，5，偏序關(guān)系是A上的整除關(guān)系，則偏序集<A，>上的元素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,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那么R1 <6,3>,<8,4> 5設(shè)集合A=a, b, c, d，A上的二元關(guān)系R=<a, b>, <b, a>, <b, c>, <c, d>，則R具有的性質(zhì)是沒有任何性質(zhì)6設(shè)集合A=a, b, c, d，A上的二元關(guān)系R=<a, a >, <b, b>, <b, c>, <c, d>，若在R中再增加兩個元素<c,b>,<d,c>，則新得到的關(guān)系就具有對稱性7如果R1和R2是A上的自反關(guān)系，則R1R2，R1R2，R1-R2中自反關(guān)系有 2 個8設(shè)A=1, 2上的二元關(guān)系為R=<x, y>|xA，yA, x+y =10，則R的自反閉包為 <1,1>,<2,2> 9設(shè)R是集合A上的等價(jià)關(guān)系，且1 , 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)系，因?yàn)?lt;3,3>不屬于R。（2）錯誤。R不具有對稱的關(guān)系，因?yàn)?lt;2,1>不屬于R。 2如果R1和R2是A上的自反關(guān)系，判斷結(jié)論：“R-11、R1R2、R1R2是自反的” 是否成立？并說明理由 解：成立 因?yàn)镽1和R2是A上的自反關(guān)系，即IAR1，IAR2。 由逆關(guān)系定義和IAR1，得IA R1-1； 由IAR1，IAR2，得IA R1R2，IA R1R2。所以，R1-1、R1R2、R1R2是自反的。ooooabcd圖一ooogefho3若偏序集<A，R>的哈斯圖如圖一所示，則集合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ù)。因?yàn)閷τ?屬于A，在B中沒有元素與之對應(yīng)。（2）不構(gòu)成函數(shù)。因?yàn)閷τ?屬于A，在B中沒有元素與之對應(yīng)。（3）構(gòu)成函數(shù)。因?yàn)锳中任意一個元素都有A中唯一的元素相對應(yīng)。三、計(jì)算題1設(shè)，求：(1) (AB)C； (2) (AB)- (BA) (3) P(A)P(C)； (4) AB解：(1) (AB)C=11,3,5=1,3,5(2) (AB)- (BA)=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) AB= (AB)- (BA)= 2,4,52設(shè)A=1,2,1,2，B=1,2,1,2，試計(jì)算（1）（A-B）； （2）（AB）； （3）AB解：（1）A-B =1,2 （2）AB =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=<x，y>|xA，yA且x+y4，S=<x，y>|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=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沒有最大元，最小元是2125641073891112關(guān)系R的哈斯圖123469578101112關(guān)系R的哈斯圖123469578101112關(guān)系R的哈斯圖(2)關(guān)系R的唯斯圖四、證明題1試證明集合等式：A (BC)=(AB) (AC)證明：設(shè)，若xA (BC)，則xA或xBC，即 xA或xB 且 xA或xC即xAB 且 xAC ，即 xT=(AB) (AC)，所以A (BC) (AB) (AC) 反之，若x(AB) (AC)，則xAB 且 xAC， 即xA或xB 且 xA或xC，即xA或xBC，即xA (BC)，所以(AB) (AC) A (BC)因此A (BC)=(AB) (AC)2試證明集合等式A (BC)=(AB) (AC)證明：設(shè)S=A(BC)，T=(AB)(AC)， 若xS，則xA且xBC，即 xA且xB 或 xA且xC， 也即xAB 或 xAC ，即 xT，所以ST 反之，若xT，則xAB 或 xAC， 即xA且xB 或 xA且xC 也即xA且xBC，即xS，所以TS 因此T=S 3對任意三個集合A, B和C，試證明：若AB = AC，且A，則B = C證明： （1） 對于任意<a，b>AB，其中aA，bB,因?yàn)锳B= AC，必有<a,b>AC,其中b C因此BC（2）同理，對于任意<a,c>AC,其中，aA，cC，因?yàn)锳B= AC必有<a,c>AB，其中cB，因此CB有（1）（2）得B=C4試證明：若R與S是集合A上的自反關(guān)系，則RS也是集合A上的自反關(guān)系證明：若R與S是集合A上的自反關(guān)系，則任意xA,x,xR,x,xS,從而x,xRS,注意x是A的任意元素，所以RS也是集合A上的自反關(guān)系離散數(shù)學(xué)形考任務(wù)四設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為(B )選擇一項(xiàng)：A. 6B. 5C. 4D. 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)：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中至多有兩個奇數(shù)度結(jié)點(diǎn)C. G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)D. G連通且至多有兩個奇數(shù)度結(jié)點(diǎn)題目5答案已保存滿分10.00標(biāo)記題目題干若G是一個歐拉圖，則G一定是(C )選擇一項(xiàng)：A. 平面圖B. 漢密爾頓圖C. 連通圖D. 對偶圖題目6答案已保存滿分10.00標(biāo)記題目題干無向樹T有8個結(jié)點(diǎn)，則T的邊數(shù)為(B )選擇一項(xiàng)：A. 6B. 7C. 8D. 9題目7答案已保存滿分10.00標(biāo)記題目題干已知一棵無向樹T中有8個頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個，T的樹葉數(shù)為(A )選擇一項(xiàng)：A. 5B. 8C. 3D. 4題目8答案已保存滿分10.00標(biāo)記題目題干設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為(C )選擇一項(xiàng)：A. 1B. 6C. 7D. 14題目9答案已保存滿分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個結(jié)點(diǎn)n1條邊的無向圖都是樹C. 無向完全圖都是平面圖D. 樹的每條邊都是割邊離散數(shù)學(xué)作業(yè)5離散數(shù)學(xué)圖論部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共3次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型（除單項(xiàng)選擇題外）安排練習(xí)題目，目的是通過綜合性書面作業(yè)，使同學(xué)自己檢驗(yàn)學(xué)習(xí)成果，找出掌握的薄弱知識點(diǎn)，重點(diǎn)復(fù)習(xí)，爭取盡快掌握。本次形考書面作業(yè)是第二次作業(yè)，大家要認(rèn)真及時(shí)地完成圖論部分的綜合練習(xí)作業(yè)。要求：將此作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，要求2010年12月5日前完成并上交任課教師（不收電子稿）。并在05任務(wù)界面下方點(diǎn)擊“保存”和“交卷”按鈕，以便教師評分。一、填空題1已知圖G中有1個1度結(jié)點(diǎn)，2個2度結(jié)點(diǎn)，3個3度結(jié)點(diǎn)，4個4度結(jié)點(diǎn)，則G的邊數(shù)是 15 2設(shè)給定圖G(如右由圖所示)，則圖G的點(diǎn)割集是 3設(shè)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=<V，E>是具有n個結(jié)點(diǎn)的簡單圖，若在G中每一對結(jié)點(diǎn)度數(shù)之和大于等于V ，則在G中存在一條漢密爾頓回路 16161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616161616166若圖G=<V, E>中具有一條漢密爾頓回路，則對于結(jié)點(diǎn)集V的每個非空子集S，在G中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為W，則S中結(jié)點(diǎn)數(shù)|S|與W滿足的關(guān)系式為 7設(shè)完全圖K有n個結(jié)點(diǎn)(n2)，m條邊，當(dāng)n為奇數(shù)時(shí)，K中存在歐拉回路8結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足 e= v1 關(guān)系的無向連通圖就是樹9設(shè)圖G是有6個結(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存在一條歐拉回路答：錯誤。應(yīng)敘述為：“如果圖G是無向連通圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路?！?如下圖所示的圖G存在一條歐拉回路答：錯誤。因?yàn)閳D中存在奇數(shù)度結(jié)點(diǎn)，所以不存在歐拉回路。3如下圖所示的圖G不是歐拉圖而是漢密爾頓圖 G 答：正確。因?yàn)橛?個結(jié)點(diǎn)的度數(shù)為奇數(shù)，所以不是歐拉圖；而對于圖中任意點(diǎn)集中的非空子集，都有V1。其中是從圖中刪除結(jié)點(diǎn)及其關(guān)聯(lián)的邊。4設(shè)G是一個有7個結(jié)點(diǎn)16條邊的連通圖，則G為平面圖答：錯誤。若G是連通平面圖，那么若，而16>376，所以不滿足定理?xiàng)l件，敘述錯誤。 17171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717 5設(shè)G是一個連通平面圖，且有6個結(jié)點(diǎn)11條邊，則G有7個面答：正確。因?yàn)檫B通平面圖滿足歐拉公式。即：。由此題條件知6-11+7=2成立。三、計(jì)算題1設(shè)G=<V，E>，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，試(1) 給出G的圖形表示； (2) 寫出其鄰接矩陣；(3) 求出每個結(jié)點(diǎn)的度數(shù)； (4) 畫出其補(bǔ)圖的圖形答：（1） （2） （3） 1、2、4、3、2（4） 2圖G=<V, E>，其中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及5，試（1）畫出G的圖形； （2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹及其權(quán)值 b c解：（1） 。 。 2 1a。 6 4 2 1 3 。 。 e 5 d （2） （3） 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 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 權(quán)值為65。四、證明題1設(shè)G是一個n階無向簡單圖，n是大于等于3的奇數(shù)證明圖G與它的補(bǔ)圖中的奇數(shù)度頂點(diǎn)個數(shù)相等證明：設(shè)a為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個奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加條邊才能使其成為歐拉圖證明：由定理推論知：在任何圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)個，則k是偶數(shù)。又由歐拉圖的充要條件是圖G中不含奇數(shù)度結(jié)點(diǎn)。因此，只要在每對奇數(shù)度結(jié)點(diǎn)間各加一條邊，使圖G的所有結(jié)點(diǎn)的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖。故最少要加條邊才能使其成為歐拉圖。形考任務(wù)六設(shè)P：我將去打球，Q：我有時(shí)間命題 “我將去打球，僅當(dāng)我有時(shí)間” 時(shí)符號化為(B )選擇一項(xiàng)：A.B.C.D.題目2還未回答滿分10.00標(biāo)記題目題干命題公式(PQ) 的析取范式是 (D )選擇一項(xiàng)：A. (PQ)RB. (PQ)RC. (PQ)RD. (PQ)R題目3還未回答滿分10.00標(biāo)記題目題干命題公式(PQ) 析取范式是(A )選擇一項(xiàng)：A.PQB.C.D.題目4答案已保存滿分10.00標(biāo)記題目題干下列公式成立的為(D )選擇一項(xiàng)：A. PQ PQB. PQ PQC. QP PD. P(PQ)Q題目5答案已保存滿分10.00標(biāo)記題目題干下列公式 (C )為重言式選擇一項(xiàng)：A. PQPQB. (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 ）選擇一項(xiàng)：A.(x)(A(x)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è)個體域D=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 QB.C.D.題目10還未回答滿分10.00標(biāo)記題目題干 A設(shè)個體域D是整數(shù)集合，則命題xy (xy = y)的真值是（A ）選擇一項(xiàng)：A. TB. FC.不確定D.以上說法都不是離散數(shù)學(xué)作業(yè)7離散數(shù)學(xué)數(shù)理邏輯部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共3次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型（除單項(xiàng)選擇題外）安排練習(xí)題目，目的是通過綜合性書面作業(yè)，使同學(xué)自己檢驗(yàn)學(xué)習(xí)成果，找出掌握的薄弱知識點(diǎn)，重點(diǎn)復(fù)習(xí)，爭取盡快掌握。本次形考書面作業(yè)是第三次作業(yè)，大家要認(rèn)真及時(shí)地完成數(shù)理邏輯部分的綜合練習(xí)作業(yè)。要求：將此作業(yè)用A4紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，要求本學(xué)期第17周末前完成并上交任課教師（不收電子稿）。并在07任務(wù)界面下方點(diǎn)擊“保存”和“交卷”按鈕，以便教師評分。一、填空題1命題公式的真值是1或T 2設(shè)P：他生病了，Q：他出差了R：我同意他不參加學(xué)習(xí). 則命題“如果他生病或出差了，我就同意他不參加學(xué)習(xí)”符號化的結(jié)果為 （PQ）R 3含有三個命題變項(xiàng)P，Q，R的命題公式PQ的主析取范式是 (PQR)(PQR) 4設(shè)P(x)：x是人，Q(x)：x去上課，則命題“有人去上課” 可符號化為 x(P(x) Q(x) 5設(shè)個體域Da, b,那么謂詞公式消去量詞后的等值式為 (A(a) A(b) (B(a) B(b) 6設(shè)個體域D1, 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。 2請將語句“小王去旅游，小李也去旅游”翻譯成命題公式 設(shè)P：小王去旅游。 Q：小李去旅游。則PQ 3請將語句“他去旅游，僅當(dāng)他有時(shí)間”翻譯成命題公式設(shè)P：他去旅游。Q：他有時(shí)間。則PQ 4請將語句“41次列車下午五點(diǎn)開或六點(diǎn)開”翻譯成命題公式設(shè)P：41次列車下午五點(diǎn)。Q：41次列車下午六點(diǎn)開。則P或Q 5請將語句 “有人不去工作”翻譯成謂詞公式設(shè) A（x）：x是人B（x）：去工作x(A(x) B(x) 6請將語句“所有人都努力工作”翻譯成謂詞公式設(shè) A（x）：x是人B（x）：努力工作x(A(x) B(x)四、判斷說明題（判斷下列各題，并說明理由） 1命題公式PP的真值是1。答：錯誤。因?yàn)镻和P的否不能同時(shí)為真。 2命題公式中的約束變元為y。 答：錯誤。該式中的約束元為x。3謂詞公式中x量詞的轄域?yàn)镻(x,y) ("z)Q(x,y,z) 。答：錯誤。謂詞公式中x量詞的轄域?yàn)镻(x,y)。若謂詞公式變?yōu)椋瑇量詞的轄域?yàn)镻(x,y) ("z)Q(x,y,z)。 4下面的推理是否正確，請給予說明(1) ("x)A(x) B(x) 前提引入(2) A(y) B(y) US (1)答：錯誤。因?yàn)锽(x)不受全稱量詞"x的約束，不能使用全稱指定規(guī)則。（2）應(yīng)為A(y) B(x)，換名時(shí)，約束元與自由變元不能混淆。四計(jì)算題1 求PQR的析取范式，合取范式、主析取范式，主合取范式PQRPQR （析取范式）（PQR） （合取范式）真值表：PQRP原式極小項(xiàng)極大項(xiàng)00011PPP00111PQR01011PQR01111PQR10000PQR10101PQR11001PQR11101PQR主析取范式（PPP）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR） 主合取范式（PQR）2求命題公式(PQ)(RQ) 的主析取范式、主合取范式真值表：PQR（PQ）RQ原式極小項(xiàng)極大項(xiàng)000101PPP001111PQR010011PQR011011PQR100000PQR101011PQR110011PQR111011PQR主析取范式（PPP）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR） 主合取范式（PQR）3設(shè)謂詞公式（1）試寫出量詞的轄域；（2）指出該公式的自由變元和約束變元答：（1）x的轄域?yàn)镻（x,y）zQ(x,y,z)z的轄域?yàn)镼(x,y,z) y的轄域?yàn)镽(y,z)(2) 約束變元為P（x,y）zQ(x,y,z)中的xQ(x,y,z) 中的 zR(y,z) 中的y自由變元為P（x,y）zQ(x,y,z)中的yR(y,z)中的z 4設(shè)個體域?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)PQPQ（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) )0A (B C) (A B C)故由左邊不可推出右邊A