24春國(guó)家開(kāi)放大學(xué)《離散數(shù)學(xué)》大作業(yè)參考答案

離散數(shù)學(xué)大作業(yè)姓名：姓名：學(xué)號(hào)：得分：教師簽名：大作業(yè)時(shí)間為第1周到第17周，滿(mǎn)分100分，由兩部分組成。提交作業(yè)方式有以下三種，請(qǐng)務(wù)必與輔導(dǎo)教師溝通后選擇：1.將此次作業(yè)用A4紙打印出來(lái)，手工書(shū)寫(xiě)答題，字跡工整，解答題要有解答過(guò)程，完成作業(yè)后交給輔導(dǎo)教師批閱。注意選擇此種提交方式時(shí)仍然需要在網(wǎng)絡(luò)課提交作業(yè)入口處上傳說(shuō)明文檔，文檔內(nèi)注明“作業(yè)已由線下提交給輔導(dǎo)老師”。2.在線提交word文檔．3.自備答題紙張，將答題過(guò)程手工書(shū)寫(xiě)，并拍照上傳．第一部分一、公式翻譯題（每小題2分，共10分）1.將語(yǔ)句“我會(huì)英語(yǔ)，并且會(huì)德語(yǔ)．”翻譯成命題公式．解：設(shè)P：我會(huì)英語(yǔ)，Q：我會(huì)德語(yǔ)則命題公式為：P∧Q．2.將語(yǔ)句“如果今天是周三，則昨天是周二．”翻譯成命題公式．解：設(shè)P：今天是周三，Q：昨天是周二則命題公式為：P→Q．3.將語(yǔ)句“小王是個(gè)學(xué)生，小李是個(gè)職員．”翻譯成命題公式．解：設(shè)P：小王是個(gè)學(xué)生，Q：小李是個(gè)職員．則命題公式為：P∧Q．4.將語(yǔ)句“如果明天下雨，我們就去圖書(shū)館.”翻譯成命題公式．解：設(shè)P：明天下雨，Q：我們就去圖書(shū)館．則命題公式為：P→Q．5.將語(yǔ)句“當(dāng)大家都進(jìn)入教室后，討論會(huì)開(kāi)始進(jìn)行．”翻譯成命題公式．解：設(shè)P：大家都進(jìn)入教室后，Q：討論會(huì)開(kāi)始進(jìn)行則命題公式為：P∧Q二、計(jì)算題（每小題10分，共50分）1.設(shè)集合A={1,2,3}，B={2,3,4}，C={2,{3}}，試計(jì)算（1）AC；（2）A∩B；（3）(A∩B)×C．解：（1）A-C={1,3}（2）A∩B={2,3}（3）(A∩B)×C={2,3}×{2,{3}}={<2,2>,<2,{3}>,<3,2>,<3,{3}>}2.設(shè)G=<V，E>，V={v1,v2,v3,v4,v5}，E={(v1,v3),(v1,v5),(v2,v3),(v3,v4),(v4,v5)}，試（1）給出G的圖形表示；（2）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（3）畫(huà)出其補(bǔ)圖的圖形．解：（1）G的圖形表示（2）v1，v2，v3，v4，v5結(jié)點(diǎn)的度數(shù)依次為2，1，3，2，2．（3）補(bǔ)圖如下圖3.試畫(huà)一棵帶權(quán)為1,2,3,3,4的最優(yōu)二叉樹(shù),并計(jì)算該最優(yōu)二叉樹(shù)的權(quán)．解：最優(yōu)二叉樹(shù)的權(quán)為：1×3+2×3+3×2+3×2=4×2=294.求出如下所示賦權(quán)圖中的最小生成樹(shù)（要求寫(xiě)出求解步驟），并求此最小生成樹(shù)的權(quán)．v6v1v2v5v3v416245793152解：W(v2,v6)=1,選(v2,v6)W(v4,v5)=1,選(v4,v5)W(v1,v6)=2,選(v1,v6)W(v3,v5)=2,選(v3,v5)W(v2,v3)=4,選(v2,v3)最小生成樹(shù)，如圖生成樹(shù)的權(quán)W(T)=1+1+2+2+4=105.求P→(Q∧R)的析取范式與合取范式.解：P→(Q∧R)??P∨(Q∧R)變成合取析取?(?P∨Q)∧(?P∨R)分配律?(?P∨Q∨(?R∧R))∧(?P∨(?Q∧Q)∨R)補(bǔ)項(xiàng)?((?P∨Q∨?R)∧(?P∨Q∨R))∧(?P∨(?Q∧Q)∨R)分配律2?(?P∨Q∨?R)∧(?P∨Q∨R)∧(?P∨(?Q∧Q)∨R)結(jié)合律?(?P∨Q∨?R)∧(?P∨Q∨R)∧((?P∨?Q∨R)∧(?P∨Q∨R))分配律2?(?P∨Q∨?R)∧(?P∨Q∨R)∧(?P∨?Q∨R)∧(?P∨Q∨R)結(jié)合律?(?P∨Q∨?R)∧(?P∨?Q∨R)∧(?P∨Q∨R)等冪律得到主合取范式，再檢查遺漏的極大項(xiàng)?M?∧M?∧M??∏(4,5,6)??∏(0,1,2,3,7)?∑(0,1,2,3,7)?m?∨m?∨m?∨m?∨m???(P∨Q∨R)∨?(P∨Q∨?R)∨?(P∨?Q∨R)∨?(P∨?Q∨?R)∨?(?P∨?Q∨?R)德摩根定律?(?P∧?Q∧?R)∨(?P∧?Q∧R)∨(?P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R)德摩根定律得到主析取范式第二部分從下列選題中選擇一個(gè)感興趣的主題，自主查閱文獻(xiàn)資料進(jìn)行深入的研究和學(xué)習(xí)，并形成一份至少一千字的總結(jié)報(bào)告。（40分）離散數(shù)學(xué)在各學(xué)科領(lǐng)域的應(yīng)用；集合論的發(fā)展歷史和應(yīng)用；函數(shù)概念的發(fā)展歷史和應(yīng)用；圖論的發(fā)展歷史和應(yīng)用；數(shù)理邏輯的發(fā)展歷史和應(yīng)用；最小生成樹(shù)的兩種算法比較分析；任意自選主題，注意選擇前需經(jīng)過(guò)輔導(dǎo)老師認(rèn)可。參考答案：離散數(shù)學(xué)在各學(xué)科領(lǐng)域的應(yīng)用離散數(shù)學(xué)是數(shù)學(xué)的一個(gè)重要分支，主要研究離散對(duì)象和結(jié)構(gòu)以及它們之間的關(guān)系和規(guī)律。在現(xiàn)代科技的推動(dòng)下，離散數(shù)學(xué)已經(jīng)滲透到各個(gè)學(xué)科領(lǐng)域，成為眾多學(xué)科不可或缺的理論基礎(chǔ)。本文將從多個(gè)方面探討離散數(shù)學(xué)在各學(xué)科領(lǐng)域的應(yīng)用。（一）計(jì)算機(jī)科學(xué)基礎(chǔ)計(jì)算機(jī)科學(xué)的核心概念，如邏輯運(yùn)算、集合論、圖論等，都是離散數(shù)學(xué)的重要組成部分。邏輯運(yùn)算是計(jì)算機(jī)內(nèi)部信息處理的基礎(chǔ)，而集合論和圖論則在數(shù)據(jù)結(jié)構(gòu)、算法分析和系統(tǒng)設(shè)計(jì)等領(lǐng)域發(fā)揮著重要作用。（二）數(shù)據(jù)結(jié)構(gòu)與算法離散數(shù)學(xué)為數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)提供了理論基礎(chǔ)。圖論中的樹(shù)、圖等概念是數(shù)據(jù)結(jié)構(gòu)中的關(guān)鍵要素，如二叉樹(shù)、堆、圖等。同時(shí)，離散數(shù)學(xué)中的組合數(shù)學(xué)、優(yōu)化理論等為算法設(shè)計(jì)提供了有效工具，如動(dòng)態(tài)規(guī)劃、貪心算法等。（三）網(wǎng)絡(luò)與通信網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路可以抽象為離散數(shù)學(xué)中的圖和邊的概念。圖論在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、路由算法、流量控制等方面有著廣泛應(yīng)用。此外，離散數(shù)學(xué)在編碼理論、錯(cuò)誤檢測(cè)與糾正等方面也為通信技術(shù)提供了重要支持。（四）數(shù)據(jù)庫(kù)理論數(shù)據(jù)庫(kù)的設(shè)計(jì)和管理離不開(kāi)離散數(shù)學(xué)的理論支持。關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系、屬性、元組等概念與集合論、關(guān)系代數(shù)緊密相關(guān)。同時(shí)，離散數(shù)學(xué)中的圖論和數(shù)理邏輯也為數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化、事務(wù)處理等提供了理論依據(jù)。（五）人工智能與機(jī)器學(xué)習(xí)人工智能和機(jī)器學(xué)習(xí)領(lǐng)域的許多問(wèn)題都可以轉(zhuǎn)化為離散數(shù)學(xué)問(wèn)題。例如，搜索算法、知識(shí)表示和推理、模式識(shí)別等都與離散數(shù)學(xué)密切相關(guān)。圖論、組合優(yōu)化等離散數(shù)學(xué)理論在機(jī)器學(xué)習(xí)中也有著廣泛的應(yīng)用，如決策樹(shù)、關(guān)聯(lián)規(guī)則挖掘等。（六）密碼學(xué)與信息安全密碼學(xué)是信息安全的核心，而離散數(shù)學(xué)在密碼學(xué)中扮演著舉足輕重的角色。數(shù)論、群論、有限域等離散數(shù)學(xué)理論為加密算法的設(shè)計(jì)提供了堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)。同時(shí)，離散數(shù)學(xué)也在信息隱藏、數(shù)字簽名、身份認(rèn)證等方面發(fā)揮著重要作用。（七）電子商務(wù)與信息系統(tǒng)電子商務(wù)和信息系統(tǒng)的設(shè)計(jì)和優(yōu)化也離不開(kāi)離散數(shù)學(xué)的理論支持。離散數(shù)學(xué)在數(shù)據(jù)建模、信息檢索、數(shù)據(jù)挖掘等方面提供了有效的工具和方法。同時(shí)，離散數(shù)學(xué)在電子商務(wù)的安全性和隱私保護(hù)方面也發(fā)揮著重要作用。（八）社會(huì)科學(xué)與決策分析離散數(shù)學(xué)在社會(huì)科學(xué)和決策分析領(lǐng)域也有廣泛的應(yīng)用。例如，圖論和網(wǎng)絡(luò)分析可以用于社交網(wǎng)絡(luò)分析、輿論傳播等；數(shù)理邏輯和集合論可以用于決策支持系統(tǒng)、知