國(guó)開(kāi)《離散數(shù)學(xué)》大作業(yè)及答案

大作業(yè)及答案1.在線提交word文檔第一部分一、公式翻譯題（每小題2分，共10分）1.將語(yǔ)句“我會(huì)英語(yǔ)，并且會(huì)德語(yǔ)．”翻譯成命題公式．參考答案：設(shè)p.我學(xué)英語(yǔ)Q:我學(xué)法語(yǔ)則命題公式為:pΛQ2.將語(yǔ)句“如果今天是周三，則昨天是周二．”翻譯成命題公式．參考答案：設(shè)P：今天是周三Q：昨天是周二則命題公式為：P→Q3.將語(yǔ)句“小王是個(gè)學(xué)生，小李是個(gè)職員．”翻譯成命題公式．參考答案：設(shè)P：小王是個(gè)學(xué)生Q：小李是個(gè)職員則命題公式為：P∧Q4.將語(yǔ)句“如果明天下雨，我們就去圖書(shū)館.”翻譯成命題公式．參考答案：設(shè)P：如果明天下雨Q：我們就去圖書(shū)館則命題公式為：P→Q5.將語(yǔ)句“當(dāng)大家都進(jìn)入教室后，討論會(huì)開(kāi)始進(jìn)行．”翻譯成命題公式．參考答案：設(shè)P：當(dāng)大家都進(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）A-C；

（2）A∩B；

（3）(A∩B)×C．參考答案：（1）A-C={l,3}；（2）A∩B={2,3}；（3）(A∩B)×C={<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）關(guān)系圖（2）deg(v1)=3deg(v2)=2deg(v3)=3deg(v4)=2deg(v5)=2（3）補(bǔ)圖3．試畫(huà)一棵帶權(quán)為1,

2,

3,

3,

4的最優(yōu)二叉樹(shù),并計(jì)算該最優(yōu)二叉樹(shù)的權(quán)．參考答案：權(quán)為1×3+2×3+3×2+3×2+4×2=294．求出如下所示賦權(quán)圖中的最小生成樹(shù)（要求寫(xiě)出求解步驟），并求此最小生成樹(shù)的權(quán)．參考答案：解：用Kruskal算法求產(chǎn)生的最小生成樹(shù),步驟為: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=10.5.

求P→(Q∧R)的析取范式與合取范式.參考答案：解:(P∨Q)→R?┐(P∨Q)∨R?(┐P∧┐Q)∨R(析取范式)?(┐P∨R)∧(┐Q∨R)(合取范式)第二部分從下列選題中選擇一個(gè)感興趣的主題，自主查閱文獻(xiàn)資料進(jìn)行深入的研究和學(xué)習(xí)，并形成一份至少一千字的總結(jié)報(bào)告。1.離散數(shù)學(xué)在各學(xué)科領(lǐng)域的應(yīng)用；2.集合論的發(fā)展歷史和應(yīng)用；3.函數(shù)概念的發(fā)展歷史和應(yīng)用；4.圖論的發(fā)展歷史和應(yīng)用；5.數(shù)理邏輯的發(fā)展歷史和應(yīng)用；6.最小生成樹(shù)的兩種算法比較分析；參考答案：離散數(shù)學(xué)在各學(xué)科領(lǐng)域的應(yīng)用引言離散數(shù)學(xué)，作為現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，專(zhuān)注于研究離散量的結(jié)構(gòu)及其相互關(guān)系。所謂“離散”，指的是不同的、連接在一起的元素，與連續(xù)變化的量形成鮮明對(duì)比。離散數(shù)學(xué)的研究對(duì)象通常是有限個(gè)或可數(shù)個(gè)元素，這些元素可能以集合、圖、序列等形式出現(xiàn)。離散數(shù)學(xué)的核心概念包括集合論、圖論、代數(shù)結(jié)構(gòu)、組合數(shù)學(xué)以及數(shù)理邏輯等，為理解和分析離散現(xiàn)象提供了強(qiáng)有力的數(shù)學(xué)工具。本文將探討離散數(shù)學(xué)在各學(xué)科領(lǐng)域中的廣泛應(yīng)用。一、計(jì)算機(jī)科學(xué)領(lǐng)域離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中的應(yīng)用尤為廣泛，它是許多計(jì)算機(jī)科學(xué)領(lǐng)域不可或缺的基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)與算法：離散數(shù)學(xué)為數(shù)據(jù)結(jié)構(gòu)（如數(shù)組、鏈表和樹(shù)）和算法（如排序和搜索）的設(shè)計(jì)和分析提供了基礎(chǔ)。例如，集合論用于描述數(shù)據(jù)結(jié)構(gòu)，圖論用于解決路徑問(wèn)題，組合數(shù)學(xué)用于計(jì)算算法復(fù)雜度等。編譯器：離散數(shù)學(xué)用于設(shè)計(jì)編譯器，它們將高層次語(yǔ)言翻譯成計(jì)算機(jī)能夠理解的低層次語(yǔ)言。密碼學(xué)：離散數(shù)學(xué)是密碼學(xué)的基礎(chǔ)，涉及加密和解密信息。代數(shù)結(jié)構(gòu)中的群、環(huán)等概念被用于構(gòu)建加密算法，確保信息的安全傳輸。計(jì)算機(jī)網(wǎng)絡(luò)：離散數(shù)學(xué)用于設(shè)計(jì)和分析計(jì)算機(jī)網(wǎng)絡(luò)的協(xié)議和拓?fù)浣Y(jié)構(gòu)。數(shù)據(jù)庫(kù)系統(tǒng)：離散數(shù)學(xué)用于關(guān)系數(shù)據(jù)庫(kù)的建模、查詢(xún)和優(yōu)化。樹(shù)、圖等結(jié)構(gòu)被廣泛應(yīng)用于數(shù)據(jù)組織、查詢(xún)優(yōu)化等方面。人工智能：離散數(shù)學(xué)用于設(shè)計(jì)用于機(jī)器學(xué)習(xí)和人工智能的算法。數(shù)理邏輯為機(jī)器推理、知識(shí)表示等提供了理論基礎(chǔ)，而組合數(shù)學(xué)則用于解決搜索、優(yōu)化等復(fù)雜問(wèn)題。二、信息技術(shù)和其他學(xué)科領(lǐng)域除了計(jì)算機(jī)科學(xué)，離散數(shù)學(xué)還在其他多個(gè)領(lǐng)域展現(xiàn)出了其強(qiáng)大的應(yīng)用價(jià)值。數(shù)據(jù)挖掘：離散數(shù)學(xué)用于從大型數(shù)據(jù)集提取有意義的信息。圖像處理：離散數(shù)學(xué)用于圖像處理和分析技術(shù)。自然語(yǔ)言處理：離散數(shù)學(xué)用于開(kāi)發(fā)和增強(qiáng)自然語(yǔ)言理解和生成系統(tǒng)。軟件工程：離散數(shù)學(xué)用于軟件系統(tǒng)的建模和驗(yàn)證。物理學(xué)：離散數(shù)學(xué)用于粒子物理學(xué)、統(tǒng)計(jì)物理學(xué)和凝聚態(tài)物理學(xué)中的建模和仿真。經(jīng)濟(jì)學(xué)：離散數(shù)學(xué)用于游戲理論、博弈論和優(yōu)化模型的構(gòu)建。生物學(xué)：離散數(shù)學(xué)用于生物信息學(xué)和計(jì)算生物學(xué)中建模生物系統(tǒng)。運(yùn)籌學(xué)：離散數(shù)學(xué)用于線性規(guī)劃、整數(shù)規(guī)劃和組合優(yōu)化問(wèn)題的解決。金融學(xué)：離散數(shù)學(xué)用于風(fēng)險(xiǎn)管理、投資組合優(yōu)化和金融模型的開(kāi)發(fā)。三、案例分析旅行商問(wèn)題（TSP）：這是圖論中的一個(gè)經(jīng)典問(wèn)題，它要求找到一條經(jīng)過(guò)所有給定城市且每個(gè)城市只經(jīng)過(guò)一次的最短路徑。這個(gè)問(wèn)題在物流優(yōu)化、路徑規(guī)劃等領(lǐng)域有著廣泛的應(yīng)用。四色定理：這是圖著色問(wèn)題中的一個(gè)經(jīng)典案例，它證明了任何平面地圖都可以用四種顏色進(jìn)行著色，使得相鄰區(qū)域的顏色不同。這個(gè)定理在地圖繪制、電路設(shè)計(jì)等領(lǐng)域有著重要的應(yīng)用。四、學(xué)習(xí)離散數(shù)學(xué)的方法學(xué)習(xí)離散數(shù)學(xué)需要掌握一定的方法和技巧。首先，打好基礎(chǔ)是關(guān)鍵。建議從集合論、圖論等基礎(chǔ)知識(shí)開(kāi)始學(xué)習(xí)，逐步深入到代數(shù)結(jié)構(gòu)、組合數(shù)學(xué)等更復(fù)雜的領(lǐng)域。其次，多做練習(xí)是提高學(xué)習(xí)效果的有效途徑。通過(guò)解決實(shí)際問(wèn)題，可以加深對(duì)離散數(shù)學(xué)概念和方法的理解。同時(shí)，利用網(wǎng)絡(luò)資源也是學(xué)習(xí)離散數(shù)學(xué)的好方法。此外，參加學(xué)術(shù)討論和交流活動(dòng)也有助于拓寬視野，了解離散數(shù)學(xué)的最新研究動(dòng)態(tài)和應(yīng)用前景。五、結(jié)論離散數(shù)學(xué)在現(xiàn)代技術(shù)和社會(huì)中發(fā)揮著至