東北農(nóng)業(yè)大學(xué)(2014版)《離散數(shù)學(xué)》網(wǎng)上作業(yè)題及答案

《東北農(nóng)業(yè)大學(xué)(2014版)《離散數(shù)學(xué)》網(wǎng)上作業(yè)題及答案》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院離散數(shù)學(xué)復(fù)習(xí)題復(fù)習(xí)題一一、證明1、對任意兩個集合，證明答：證明：2、構(gòu)造下面命題推理的證明如果今天是星期三，那么我有一次英語或數(shù)學(xué)測驗(yàn)；如果數(shù)學(xué)老師有事，那么沒有數(shù)學(xué)測驗(yàn)；今天是星期三且數(shù)學(xué)老師有事，所以我有一次英語測驗(yàn)。答：符號化為：證明：(1)P(2)T(1)I(3)T(1)I(4)P(5)T(2)(4)I(6)P(7)T(3)(6)I(8)T(5)(7)I55二、計(jì)算1、(1)畫一個有一條歐拉回路和一條漢密頓回路的圖。(2)畫一個有一條歐拉回路但沒有漢密頓回路的圖(3)畫一個沒有歐拉回路但有一條漢密頓回路的圖答：

2、三種圖如下：2、設(shè)，求公式：的真值。答：3、一棵樹有個結(jié)點(diǎn)度數(shù)為2，個結(jié)點(diǎn)度數(shù)為3，…，個結(jié)點(diǎn)度數(shù)為k，問它有幾個度數(shù)為1的結(jié)點(diǎn)。答：設(shè)它有個度數(shù)為1的結(jié)點(diǎn)，則：1*＋2*＋3*＋…＋k*=2*（+++…+-1）得：=＋2*＋…＋(k-2)*+24、設(shè)集合上的關(guān)系，求出它的自反閉包，對稱閉包和傳遞閉包。答：55三、設(shè)上的整除關(guān)系，是否為上的偏序關(guān)系？若是，則：1、畫出的哈斯圖；答：是上的偏序關(guān)系。的哈斯圖：2、求。答：。四、用推導(dǎo)法求公式的主析取范式和主合取范式。答：五、設(shè)實(shí)數(shù)集上的關(guān)系，證明：是上的等價關(guān)系。55答：證明：因此是自反的因此是

3、對稱的因此是傳遞的。綜上：是上的等價關(guān)系。六、設(shè)分別是實(shí)數(shù)集和正實(shí)數(shù)集，＋和×分別是普通加法和乘法，定義函數(shù)為，證明的同構(gòu)映射。答：證明：因此。，所以的同構(gòu)映射。七、設(shè)是實(shí)數(shù)集合，，在上定義二元運(yùn)算為：，試證明是一個群。是否阿貝爾群？答：證明：因此，運(yùn)算是封閉的55綜上：是一個群。不是阿貝爾群。復(fù)習(xí)題二一、設(shè)上的整除關(guān)系完成下列各小題。1、證明是上的偏序關(guān)系。答：證明。55綜上，是上的偏序關(guān)系。1、畫出偏序集的哈斯圖。答：偏序集的哈斯圖如右圖所示。2、在上定義兩個二元運(yùn)算和：對任意，，。請?zhí)羁眨ㄔ跈M線上填是或不是）：①代數(shù)系統(tǒng)是格。②代數(shù)系統(tǒng)

4、是有界格。③代數(shù)系統(tǒng)是有補(bǔ)格。④代數(shù)系統(tǒng)不是分配格。二、求布爾函數(shù)的析取范式和合取范式設(shè)是布爾代數(shù)上的一個布爾表達(dá)式。試寫出的析取范式和合取范式（用推導(dǎo)法或列函數(shù)表的方法均可）。答：方法1推導(dǎo)法析取范式為：55合取范式為：方法2列函數(shù)表法布爾表達(dá)式對應(yīng)的函數(shù)表為：<0,0,0><0,0,1><0,1,0><0,1,1><1,0,0><1,0,1><1,1,0><1,1,1>01010111析取范式為：合取范式為：三、畫出滿足下列要求的圖①有一條歐拉回路和一條漢密爾頓回路。②有一條歐拉回路但沒有漢密爾頓回路。55③沒有歐拉回路但有漢密爾頓回路。

5、④既沒有歐拉回路也沒有漢密爾頓回路。四、證明在完全二叉樹中，邊的總數(shù)等于2(n-1)，這里n是葉子數(shù)。答：證明設(shè)分枝點(diǎn)數(shù)為i。因?yàn)樵谕耆玬叉樹中，有(m-1)i=n-1，所以，當(dāng)m=2時有i=n-1。又因?yàn)樵谕耆鏄渲校總€分枝點(diǎn)射出兩條邊，所以邊的總數(shù)是2i，即邊的總數(shù)是2(n-1)。五、計(jì)算求帶權(quán)2、3、5、7、11、13的最優(yōu)二叉樹。答：解23571113所求最優(yōu)二叉樹為55711131071113171113172441六、證明在一個連通平面圖中，若它有n個結(jié)點(diǎn)，m條邊，且每個面由k條邊圍成。試證答：在一個連通平面圖中，若它有n個結(jié)

6、點(diǎn)，m條邊，且每個面由k條邊圍成。試證55證明設(shè)此平面圖有r個面。又，從而有。將其代入歐拉公式得整理得七、證明設(shè)是有限字母表，給定代數(shù)系統(tǒng)，其中是串的連接運(yùn)算。對于任一串，建立到的映射，。證明是到的一個滿同態(tài)，且當(dāng)時，是同構(gòu)映射。答：證明對于中任意兩字符串和，因?yàn)?，所以，對于任一正整?shù)，取，則，所以，，是到的一個滿同態(tài)。當(dāng)時，設(shè)，，，是雙射，因此，是一個同構(gòu)映射。55八、應(yīng)用給定有限狀態(tài)機(jī)，它的狀態(tài)圖如附圖所示。1、求狀態(tài)的011010的后繼以及可接受狀態(tài)序列。答：因?yàn)樗誀顟B(tài)的011010的后繼狀態(tài)是，可接受狀態(tài)序列是。2、求對于激勵010

7、110的響應(yīng)。答：對于激勵010110的響應(yīng)是。3、構(gòu)造一臺與相似的轉(zhuǎn)換賦值機(jī)，畫出的狀態(tài)圖。答：與相似的轉(zhuǎn)換賦值機(jī)，其中：55的狀態(tài)圖為：九、證明考察一個（8，4）碼C，它的校驗(yàn)位a5，a6，a7，a8滿足下列方程a5=a1+a2+a4a6=a1+a3+a4a7=a1+a2+a355a8=a2+a3+a4其中a1，a2，a3，a4為信息位。求出這個碼的一致校驗(yàn)矩陣。證明。答：證明一致校驗(yàn)矩陣為：矩陣中無零列向量，且任意兩個、三個列向量之和不等于零向量。而第一、二、六、八列向量之和為零向量，所以，復(fù)習(xí)題三一、設(shè)集合完成下列各小題。1求的冪集。

8、答：2證明是偏序集。答：。55綜上，是偏序集。3畫出偏序集的哈斯圖。答：偏序集的哈斯圖如圖1。4在上定義兩個二元運(yùn)算和：對任意，，。請?zhí)羁眨ㄔ跈M線上填是或不是并回答