國開電大《離散數(shù)學(xué)》形考任務(wù)+大作業(yè)

國開電大《離散數(shù)學(xué)》形考任務(wù)+大作業(yè)離散數(shù)學(xué)（本）·形考任務(wù)一1.若集合A＝{a，{a}，{1，2}}，則下列表述正確的是(

)．A.{a，{a}}?AB.{1，2}?A

C.{a}íA

D.??A正確答案：C2.若集合A＝{1,2,3,4}，則下列表述正確的是()．A.{1,2}?A

B.{1,2,3}íAC.Aì{1,2,3}D.{1,2,3}?A正確答案：B3.若集合A＝{2，a，{a}，4}，則下列表述正確的是(

)．A.{a，{a}}?AB.?AC.{2}?A

D.{a}íA正確答案：D4.若集合A={1，2}，B={1，2，{1，2}}，則下列表述正確的是(

)．A.AìB，且A?BB.BìA，且A?BC.AìB，且A?BD.A?B，且A?B正確答案：A5.若集合A={a，b}，B={a，{a，b}}，則下列表述正確的是(

)．A.AìB

B.BìAC.A?B

D.A?B正確答案：D6.若集合A的元素個(gè)數(shù)為5，則其冪集的元素個(gè)數(shù)為（

）．A.5B.16C.32D.64正確答案：C7.設(shè)集合A＝｛1,2,3,4,5,6｝，B={1,2,3}，A到B的關(guān)系R＝{<x,y>|xA,yB且x=y2}，則R=(

)．A.{<1,1>,<2,4>}

B.{<1,1>,<4,2>}C.{<1,1>,<6,3>}

D.{<1,1>,<2,1>}正確答案：B8.設(shè)集合A={2,4,6,8}，B={1,3,5,7｝，A到B的關(guān)系R={<x,y>|xA,yB且

y=x

+1｝，則R=()．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>}正確答案：A9.設(shè)A＝｛1,2,3｝，B={1,2,3,4}，A到B的關(guān)系R＝｛〈x,y〉|x?A,y?B，x=y｝，則R=(

)．A.{<1,2>,<2,3>}B.{<1,1>,<1,2>,<1,3>,<1,4>,<1,5>}C.{<1,1>,<2,1>}

D.{<1,1>,<2,2>,<3,3>}正確答案：D10.設(shè)A={a，b，c}，B={1，2}，作f：A→B，則不同的函數(shù)個(gè)數(shù)為（）A.2B.3C.6D.8正確答案：D11.空集的冪集是空集．（）A.正確B.錯(cuò)誤正確答案：B12.存在集合A與B，可以使得A?B與AíB同時(shí)成立．A.正確B.錯(cuò)誤正確答案：A13.集合的元素可以是集合．A.正確B.錯(cuò)誤正確答案：A14.如果A是集合B的元素，則A不可能是B的子集．A.正確B.錯(cuò)誤正確答案：B15.設(shè)集合A＝{a}，那么集合A的冪集是{?,{a}}A.正確B.錯(cuò)誤正確答案：A16.若集合A的元素個(gè)數(shù)為4，則其冪集的元素個(gè)數(shù)為16A.正確B.錯(cuò)誤正確答案：A17.設(shè)A={1,2,3｝，B={1,2,3,4}，A到B的關(guān)系R={<x,y>|x?A,y?B，x>y｝，則R={<2,1>,<3,1>,<3,2>}A.正確B.錯(cuò)誤正確答案：A18.設(shè)A＝｛1,6,7｝，B={2,4,8,10}，A到B的關(guān)系R＝｛〈x,y〉|x?A,y?B，且x=y｝，則R={<2,2>,<4,4>,<8,8>,<10,10>}A.正確B.錯(cuò)誤正確答案：B19.設(shè)A={a，b，c}，B={1，2，3}，作f：A→B，則共有9個(gè)不同的函數(shù).A.正確B.錯(cuò)誤正確答案：B20.設(shè)A={1，2}，B={a,b,c}，則A′B的元素個(gè)數(shù)為8．（

）A.正確B.錯(cuò)誤正確答案：B離散數(shù)學(xué)（本）·形考任務(wù)二1.n階無向完全圖Kn的邊數(shù)是（

）．A.n

B.n(n-1)/2C.n-1

D.n(n-1)正確答案：B2.n階無向完全圖Kn每個(gè)結(jié)點(diǎn)的度數(shù)是（

）．A.nB.n(n-1)/2C.n-1

D.n(n-1)正確答案：C3.已知無向圖G的結(jié)點(diǎn)度數(shù)之和為20，則圖G的邊數(shù)為（

）．A.5B.15C.20D.10正確答案：D4.已知無向圖G有15條邊，則G的結(jié)點(diǎn)度數(shù)之和為（）．A.10B.20C.30D.5正確答案：C5.圖G如圖所示，以下說法正確的是(

)．A.{(a,e)}是割邊B.{(a,e)}是邊割集C.{(a,e),(b,c)}是邊割集D.{(d,e)}是邊割集正確答案：D6.若圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),(b,c),(b,d)}，則該圖中的割點(diǎn)為（

）．A.aB.bC.cD.d正確答案：B7.設(shè)無向完全圖K有n個(gè)結(jié)點(diǎn)(n≥2)，m條邊，當(dāng)（

）時(shí)，K中存在歐拉回路．A.m為奇數(shù)

B.n為偶數(shù)C.n為奇數(shù)

D.m為偶數(shù)正確答案：C8.設(shè)G是歐拉圖，則G的奇數(shù)度數(shù)的結(jié)點(diǎn)數(shù)為(

)個(gè)．A.0B.1C.2D.4正確答案：A9.設(shè)G為連通無向圖，則（

）時(shí)，G中存在歐拉回路．A.G不存在奇數(shù)度數(shù)的結(jié)點(diǎn)

B.G存在偶數(shù)度數(shù)的結(jié)點(diǎn)C.G存在一個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)

D.G存在兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)正確答案：A10.設(shè)連通平面圖G有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則．A.v+e-r=2

B.r+v-e=2C.v+e-r=4

D.v+e–r=–4正確答案：B11.已知圖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ù)是15．(

)A.正確B.錯(cuò)誤正確答案：A12.設(shè)G是一個(gè)無向圖，結(jié)點(diǎn)集合為V，邊集合為E，則G的結(jié)點(diǎn)度數(shù)之和為2|E|．(

)A.正確B.錯(cuò)誤正確答案：A13.若圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,d),(b,c),(b,d)}，則該圖中的割邊為(b,c)．(

)

A.正確B.錯(cuò)誤正確答案：A14.邊數(shù)相等與度數(shù)相同的結(jié)點(diǎn)數(shù)相等是兩個(gè)圖同構(gòu)的必要條件.A.正確B.錯(cuò)誤正確答案：A15.若圖G中存在歐拉路，則圖G是一個(gè)歐拉圖．A.正確B.錯(cuò)誤正確答案：B16.無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且結(jié)點(diǎn)度數(shù)都是偶數(shù)．(

)A.正確B.錯(cuò)誤正確答案：A17.設(shè)G是具有n個(gè)結(jié)點(diǎn)m條邊k個(gè)面的連通平面圖，則n-m=2-k.A.正確B.錯(cuò)誤正確答案：A18.設(shè)G是一個(gè)有6個(gè)結(jié)點(diǎn)13條邊的連通圖，則G為平面圖．A.正確B.錯(cuò)誤正確答案：B19.完全圖K5是平面圖．A.正確B.錯(cuò)誤正確答案：B20.設(shè)G是漢密爾頓圖，S是其結(jié)點(diǎn)集的一個(gè)子集，若S的元素個(gè)數(shù)為6，則在G-S中的連通分支數(shù)不超過6A.正確B.錯(cuò)誤正確答案：A離散數(shù)學(xué)（本）·形考任務(wù)三1.無向圖G是棵樹，邊數(shù)為12，則G的結(jié)點(diǎn)數(shù)是（

）．A.12B.24C.11D.13正確答案：D2.無向圖G是棵樹，邊數(shù)是12，則G的結(jié)點(diǎn)度數(shù)之和是（

）．A.12B.13C.24D.6正確答案：C3.無向圖G是棵樹，結(jié)點(diǎn)數(shù)為10，則G的邊數(shù)是（

）．A.9B.10C.11D.12正確答案：A4.設(shè)G是有10個(gè)結(jié)點(diǎn)，邊數(shù)為20的連通圖，則可從G中刪去（

）條邊后使之變成樹.A.12B.9C.10D.11正確答案：D5.設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的(

)條邊，才能確定G的一棵生成樹．A.m-n+1B.m-nC.m+n+1D.n-m+1正確答案：A6.設(shè)A(x)：x是金屬，B(x)：x是金子，則命題“有的金屬是金子”可符號(hào)化為（

）．A.(x)(A(x)∧B(x))

B.┐("x)(A(x)→B(x))C.(x)(A(x)∧B(x))

D.┐(x)(A(x)∧┐B(x))正確答案：C7.設(shè)A（x）：x是學(xué)生，B（x）：x去跑步，則命題“所有人都去跑步”可符號(hào)化為（

）．A.($x)(A(x)∧B(x))B.("x)(A(x)→B(x))C.($x)(A(x)∧┐B(x))

D.("x)(A(x)∧B(x))正確答案：B8.設(shè)A（x）：x是書，B（x）：x是數(shù)學(xué)書，則命題“不是所有書都是數(shù)學(xué)書”可符號(hào)化為（

）．A.┐("x)(A(x)→B(x))

B.┐($x)(A(x)∧B(x))C.("x)(A(x)∧B(x))D.┐($x)(A(x)∧┐B(x))正確答案：A9.("x)(P(x，y)∨Q(z))∧($y)(R(x,y)→("z)Q(z))中量詞“"”的轄域是()．A.P(x,y)

B.P(x,y)∨Q(z)

C.R(x,y)

D.P(x,y)∧R(x,y)正確答案：B10.設(shè)個(gè)體域D={a,b,c}，那么謂詞公式($x)A(x)∨("y)B(y)消去量詞后的等值式為(

)．A.(A(a)∨A(b)∨A(c))∨(B(a)∧B(b)∧B(c))B.(A(a)∧A(b)∧A(c))∨(B(a)∨B(b)∨B(c))C.(A(a)∨A(b)∨A(c))∨(B(a)∨B(b)∨B(c))D.(A(a)∧A(b)∧A(c))∨(B(a)∧B(b)∧B(c))正確答案：A11.若無向圖G的邊數(shù)比結(jié)點(diǎn)數(shù)少1，則G是樹．A.正確B.錯(cuò)誤正確答案：B12.無向圖G是樹當(dāng)且僅當(dāng)無向圖G是連通圖．A.正確B.錯(cuò)誤正確答案：B13.無向圖G是棵樹，結(jié)點(diǎn)度數(shù)之和是20，則G的邊數(shù)是9A.正確B.錯(cuò)誤正確答案：B14.設(shè)G是有8個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的度數(shù)之和為24，則可從G中刪去5條邊后使之變成樹．A.正確B.錯(cuò)誤正確答案：A15.設(shè)個(gè)體域D＝{1,2,3}，則謂詞公式("x)A(x)消去量詞后的等值式為A(1)∧A(2)∧A(3)．A.正確B.錯(cuò)誤正確答案：A16.設(shè)個(gè)體域D＝{1,2,3,4}，則謂詞公式($x)A(x)消去量詞后的等值式為A(1)∨A(2)∨A(3)∨A(4)A.正確B.錯(cuò)誤正確答案：A17.設(shè)個(gè)體域D＝{1,2}，則謂詞公式("x)P(x)∨（$x）Q（x）消去量詞后的等值式為(P(1)∧P(2))∨(Q（1）∨Q（2)).A.正確B.錯(cuò)誤正確答案：A18.("x)(P(x)∧Q(y)→R(x))中量詞“"”的轄域?yàn)?P(x)∧Q(y))．A.正確B.錯(cuò)誤正確答案：B19.("x)(P(x)∧Q(y))→R(x)中量詞“"”的轄域?yàn)?P(x)∧Q(y))．A.正確B.錯(cuò)誤正確答案：A20.設(shè)A（x）：x是人，B（x）：x是學(xué)生，則命題“有的人是學(xué)生”可符號(hào)化為┐(x)(A(x)∧┐B(x))A.正確B.錯(cuò)誤正確答案：B大作業(yè)1.在線提交word文檔第一部分一、公式翻譯題（每小題2分，共10分）1.將語句“我會(huì)英語，并且會(huì)德語．”翻譯成命題公式．參考答案：設(shè)p.我學(xué)英語Q:我學(xué)法語則命題公式為:pΛQ2.將語句“如果今天是周三，則昨天是周二．”翻譯成命題公式．參考答案：設(shè)P：今天是周三Q：昨天是周二則命題公式為：P→Q3.將語句“小王是個(gè)學(xué)生，小李是個(gè)職員．”翻譯成命題公式．參考答案：設(shè)P：小王是個(gè)學(xué)生Q：小李是個(gè)職員則命題公式為：P∧Q4.將語句“如果明天下雨，我們就去圖書館.”翻譯成命題公式．參考答案：設(shè)P：如果明天下雨Q：我們就去圖書館則命題公式為：P→Q5.將語句“當(dāng)大家都進(jìn)入教室后，討論會(huì)開始進(jìn)行．”翻譯成命題公式．參考答案：設(shè)P：當(dāng)大家都進(jìn)入教室后Q：討論會(huì)開始進(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）畫出其補(bǔ)圖的圖形．參考答案：（1）關(guān)系圖（2）deg(v1)=3deg(v2)=2deg(v3)=3deg(v4)=2deg(v5)=2（3）補(bǔ)圖3．試畫一棵帶權(quán)為1,2,3,3,4的最優(yōu)二叉樹,并計(jì)算該最優(yōu)二叉樹的權(quán)．參考答案：權(quán)為1×3+2×3+3×2+3×2+4×2=294．求出如下所示賦權(quán)圖中的最小生成樹（要求寫出求解步驟），并求此最小生成樹的權(quán)．參考答案：解：用Kruskal算法求產(chǎn)生的最小生成樹,步驟為: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)最小生成樹如圖所示:最小生成樹的權(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ù)學(xué)在各學(xué)科領(lǐng)域的應(yīng)用引言離散數(shù)學(xué)，作為現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，專注于研究離散量的結(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è)計(jì)和分析提供了基礎(chǔ)。例如，集合論用于描述數(shù)據(jù)結(jié)構(gòu)，圖論用于解決路徑問題，組合數(shù)學(xué)用于計(jì)算算法復(fù)雜度等。編譯器：離散數(shù)學(xué)用于設(shè)計(jì)編譯器，它們將高層次語言翻譯成計(jì)算機(jī)能夠理解的低層次語言。密碼學(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ù)庫系統(tǒng)：離散數(shù)學(xué)用于關(guān)系數(shù)據(jù)庫的建模、查詢和優(yōu)化。樹、圖等結(jié)構(gòu)被廣泛應(yīng)用于數(shù)據(jù)組織、查詢優(yōu)化等方面。人工智能：離散數(shù)學(xué)用于設(shè)計(jì)用于機(jī)器學(xué)習(xí)和人工智能的算法。數(shù)理邏輯為機(jī)器推理、知識(shí)表示等提供了理論基礎(chǔ)，而組合數(shù)學(xué)則用于解決搜索、優(yōu)化等復(fù)雜問題。二、信息技術(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é)用于