資源描述：
《離散數(shù)學(xué)網(wǎng)上作業(yè)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院離散數(shù)學(xué)復(fù)習(xí)題復(fù)習(xí)題一一、證明1、對任意兩個(gè)集合，證明2、構(gòu)造下面命題推理的證明如果今天是星期三，那么我有一次英語或數(shù)學(xué)測驗(yàn)；如果數(shù)學(xué)老師有事，那么沒有數(shù)學(xué)測驗(yàn)；今天是星期三且數(shù)學(xué)老師有事，所以我有一次英語測驗(yàn)。二、計(jì)算1、(1)畫一個(gè)有一條歐拉回路和一條漢密頓回路的圖。(2)畫一個(gè)有一條歐拉回路但沒有漢密頓回路的圖(3)畫一個(gè)沒有歐拉回路但有一條漢密頓回路的圖2、設(shè)，求公式：的真值。3、一棵樹有個(gè)結(jié)點(diǎn)度數(shù)為2，個(gè)結(jié)點(diǎn)度數(shù)為3，…，個(gè)結(jié)點(diǎn)度數(shù)為k，問它有幾個(gè)度數(shù)為1的結(jié)點(diǎn)。4、設(shè)集合上的關(guān)系，求出它的自反閉包，對稱閉包和傳遞閉包。三、設(shè)上的整除關(guān)系，是否為上的偏序
2、關(guān)系？若是，則：1、畫出的哈斯圖；2、求。四、用推導(dǎo)法求公式的主析取范式和主合取范式。五、設(shè)實(shí)數(shù)集上的關(guān)系，證明：是上的等價(jià)關(guān)系。六、設(shè)分別是實(shí)數(shù)集和正實(shí)數(shù)集，＋和×分別是普通加法和乘法，定義函數(shù)為，證明的同構(gòu)映射。16七、設(shè)是實(shí)數(shù)集合，，在上定義二元運(yùn)算為：，試證明是一個(gè)群。是否阿貝爾群？復(fù)習(xí)題二一、設(shè)上的整除關(guān)系完成下列各小題。1、證明是上的偏序關(guān)系。2、畫出偏序集的哈斯圖。3、在上定義兩個(gè)二元運(yùn)算和：對任意，，。請?zhí)羁眨ㄔ跈M線上填是或不是）：①代數(shù)系統(tǒng)格。②代數(shù)系統(tǒng)有界格。③代數(shù)系統(tǒng)有補(bǔ)格。④代數(shù)系統(tǒng)分配格。二、求布爾函數(shù)的析取范式和合取范式設(shè)是布爾代數(shù)上的一個(gè)布爾表達(dá)式。試寫出的
3、析取范式和合取范式（用推導(dǎo)法或列函數(shù)表的方法均可）。三、畫出滿足下列要求的圖①有一條歐拉回路和一條漢密爾頓回路。②有一條歐拉回路但沒有漢密爾頓回路。③沒有歐拉回路但有漢密爾頓回路。④既沒有歐拉回路也沒有漢密爾頓回路。四、證明在完全二叉樹中，邊的總數(shù)等于2(n-1)，這里n是葉子數(shù)。五、計(jì)算求帶權(quán)2、3、5、7、11、13的最優(yōu)二叉樹。六、證明在一個(gè)連通平面圖中，若它有n個(gè)結(jié)點(diǎn)，m條邊，且每個(gè)面由k條邊圍成。試證七、證明設(shè)是有限字母表，給定代數(shù)系統(tǒng)，其中是串的連接運(yùn)算。對于任一串，建立16到的映射，。證明是到的一個(gè)滿同態(tài)，且當(dāng)時(shí)，是同構(gòu)映射。八、應(yīng)用給定有限狀態(tài)機(jī)，它的狀態(tài)圖如附圖所示。1
4、、求狀態(tài)的011010的后繼以及可接受狀態(tài)序列。2、求對于激勵(lì)010110的響應(yīng)。3、構(gòu)造一臺與相似的轉(zhuǎn)換賦值機(jī)，畫出的狀態(tài)圖。九、證明考察一個(gè)（8，4）碼C，它的校驗(yàn)位a5，a6，a7，a8滿足下列方程a5=a1+a2+a4a6=a1+a3+a4a7=a1+a2+a3a8=a2+a3+a4其中a1，a2，a3，a4為信息位。求出這個(gè)碼的一致校驗(yàn)矩陣。證明。復(fù)習(xí)題三一、設(shè)集合完成下列各小題。1求的冪集。2證明是偏序集。3畫出偏序集的哈斯圖。4在上定義兩個(gè)二元運(yùn)算和：對任意，，16。請?zhí)羁眨ㄔ跈M線上填是或不是并回答為什么）：①代數(shù)系統(tǒng)格，因?yàn)?。②代?shù)系統(tǒng)有界格，因?yàn)?。③代?shù)系統(tǒng)有補(bǔ)格，因?yàn)?/p>
5、。④代數(shù)系統(tǒng)分配格，因?yàn)?。⑤代?shù)系統(tǒng)布爾代數(shù)，因?yàn)?。二、?jì)算設(shè)是布爾代數(shù)上的一個(gè)布爾表達(dá)式。試寫出的析取范式和合取范式（用列函數(shù)表的方法）。三、回答問題完全圖是否是歐拉圖？是否是哈密爾頓圖？為什么？四、畫圖對于下圖，利用克魯斯克爾算法求一棵最小生成樹。五、計(jì)算一棵樹有兩個(gè)結(jié)點(diǎn)度數(shù)為2，1個(gè)結(jié)點(diǎn)度數(shù)為3，3個(gè)結(jié)點(diǎn)度數(shù)為4，其余結(jié)點(diǎn)度數(shù)為1。問該樹有幾個(gè)度數(shù)為1的結(jié)點(diǎn)。六、證明是無向簡單圖，其中，證明：。證明因?yàn)槭呛唵螆D，所以圖中沒有環(huán)和平行邊，任意兩結(jié)點(diǎn)間最多有一條邊，故。七、證明已知16求證八、設(shè)計(jì)設(shè)計(jì)一臺有限狀態(tài)機(jī)，它的輸出是已經(jīng)輸入符號數(shù)的模3數(shù)（即設(shè)計(jì)模3計(jì)數(shù)器）。九、計(jì)算給定碼C
6、={00000,10001,01100,10101}，求碼C中任兩個(gè)碼字的海明距和。復(fù)習(xí)題四一、填空1、設(shè)A和B為有限集，
7、A
8、=m，
9、B
10、=n，則有個(gè)從A到B的關(guān)系，有個(gè)從A到B的函數(shù)，其中當(dāng)m￡n時(shí)有個(gè)入射，當(dāng)m=n時(shí)，有個(gè)雙射。2、集合（是/不是）可數(shù)的。二、計(jì)算1、用推導(dǎo)法求下列公式的主合取范式和主析取范式：2設(shè)上二元關(guān)系，求其自反閉包、對稱閉包、傳遞閉包。三、證明1、設(shè)是三個(gè)集合，證明：2證明等價(jià)式：四、將下列命題推理符號化并給出形式證明：已知張三或李四的彩票中獎(jiǎng)了；如果張三的彩票中獎(jiǎng)了，那么你是知道的；如果李四的彩票中獎(jiǎng)了，那么王五的彩票也中獎(jiǎng)了；現(xiàn)在你不知道張三的彩票中獎(jiǎng)。
11、所以李四和王五的彩票都中獎(jiǎng)了。五、設(shè)復(fù)數(shù)集合，定義：當(dāng)且僅當(dāng)，證明：為等價(jià)關(guān)系。六、證明：若。七、設(shè)集合，是普通乘法，證明：是一個(gè)群。八、設(shè)實(shí)數(shù)集合R，+和x是普通加法和乘法，定義映射，，證明的單一同態(tài)。復(fù)習(xí)題五一、填空1、實(shí)數(shù)集合R（是/不是）可數(shù)的。2、設(shè)A和B為有限集，
12、A
13、=m，
14、B
15、=n，則有個(gè)從A到B的關(guān)系，有個(gè)從A到B16的函數(shù)，其中當(dāng)m￡n時(shí)有個(gè)入射，當(dāng)m=n時(shí)，有個(gè)雙射。二、計(jì)算1、用推導(dǎo)法求下列公式的主合取范式和
