電大-離散數(shù)學(xué)-形考作業(yè)答案3-5-7合集

《電大-離散數(shù)學(xué)-形考作業(yè)答案3-5-7合集》由會(huì)員分享，可在線閱讀，更多相關(guān)《電大-離散數(shù)學(xué)-形考作業(yè)答案3-5-7合集（14頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

形成性考核作業(yè) 1電大離散數(shù)學(xué)作業(yè)答案 3-7 合集離散數(shù)學(xué)作業(yè) 3離散數(shù)學(xué)集合論部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共 3 次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型（除單項(xiàng)選擇題外）安排練習(xí)題目，目的是通過綜合性書面作業(yè)，使同學(xué)自己檢驗(yàn)學(xué)習(xí)成果，找出掌握的薄弱知識(shí)點(diǎn)，重點(diǎn)復(fù)習(xí)，爭(zhēng)取盡快掌握。本次形考書面作業(yè)是第一次作業(yè)，大家要認(rèn)真及時(shí)地完成集合論部分的綜合練習(xí)作業(yè)。要求：將此作業(yè)用 A4 紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，要求 2010 年 11 月 7 日前完成并上交任課教師（不收電子稿）。并在 03 任務(wù)界面下方點(diǎn)擊“保存”和“交卷”按鈕，完成并上交任課教師。一、填空題1設(shè)集合 ，則 P(A)-P(B )= 3，1,3 ，2,3，1,231,2AB1,2,3 ，A B= , 2設(shè)集合 A 有 10 個(gè)元素，那么 A 的冪集合 P(A)的元素個(gè)數(shù)為 10243設(shè)集合 A=0, 1, 2, 3，B=2, 3, 4, 5，R 是 A 到 B 的二元關(guān)系，,yxxyR且且則 R 的有序?qū)蠟?， 4設(shè)集合 A=1, 2, 3, 4 ，B=6, 8, 12， A 到 B 的二元關(guān)系R ,2,yxyx那么 R1 , 5設(shè)集合 A=a, b, c, d，A 上的二元關(guān)系 R=, , , ，則 R 具有的性質(zhì)是沒有任何性質(zhì)6設(shè)集合 A=a, b, c, d，A 上的二元關(guān)系 R=, , , ，若在 R 中再增加兩個(gè)元素,，則新得到的關(guān)系就具有對(duì)稱性7如果 R1 和 R2 是 A 上的自反關(guān)系，則 R1R 2，R 1R 2，R 1-R2 中自反關(guān)系有 2 個(gè)8設(shè) A=1, 2上的二元關(guān)系為 R=|xA，yA, x+y =10，則 R 的自反閉包為 , 9設(shè) R 是集合 A 上的等價(jià)關(guān)系，且 1 , 2 , 3 是 A 中的元素，則 R 中至少包含 , 等元素姓 名： 學(xué) 號(hào)： 得 分： 教師簽名： 形成性考核作業(yè) 210設(shè) A=1，2 ，B=a，b，C =3，4，5，從 A 到 B 的函數(shù) f =, ，從 B 到 C 的函數(shù) g=, ，則 Ran(g f)= 3,4 二、判斷說明題（判斷下列各題，并說明理由）1若集合 A = 1，2，3上的二元關(guān)系 R=， ，則(1) R 是自反的關(guān)系； (2) R 是對(duì)稱的關(guān)系（1） 錯(cuò)誤。R 不具有自反的關(guān)系，因?yàn)椴粚儆?R。（2） 錯(cuò)誤。R 不具有對(duì)稱的關(guān)系，因?yàn)椴粚儆?R。2設(shè) A=1，2，3，R=, , ，則 R 是等價(jià)關(guān)系 錯(cuò)誤。因?yàn)?3 是 A 的一個(gè)元素，但3，3不在關(guān)系 R 中。等價(jià)關(guān)系 R 必須有：對(duì) A 中任意元素 a，R 含a，a .3若偏序集的哈斯圖如圖一所示，則集合 A 的最大元為 a，最小元不存在解：錯(cuò)誤集合 A 的最大元不存在，a 是極大元4設(shè)集合 A=1, 2, 3, 4，B=2, 4, 6, 8，判斷下列關(guān)系 f 是否構(gòu)成函數(shù)f： ，并說明理由B(1) f=, , , ； (2)f=, , ；(3) f=, , , （1）不構(gòu)成函數(shù)。因?yàn)閷?duì)于 3 屬于 A，在 B 中沒有元素與之對(duì)應(yīng)。（2）不構(gòu)成函數(shù)。因?yàn)閷?duì)于 4 屬于 A，在 B 中沒有元素與之對(duì)應(yīng)。（3）構(gòu)成函數(shù)。因?yàn)?A 中任意一個(gè)元素都有 A 中唯一的元素相對(duì)應(yīng)。三、計(jì)算題1設(shè) ，求：4,2,51,4,53,2 CE(1) (AB)C； (2) (AB)- (BA) (3) P(A)P(C)； (4) AB解：（1）(A B)C=1 5,31,（3） 4,2,4)(CPA, ab cd圖一ge fh 形成性考核作業(yè) 3（4）AB =(AB) （A B）= 5,4215,42（2）=1，2,4,5-1=2,4,52設(shè) A=1,2,1,2，B=1,2,1,2，試計(jì)算（1）（AB）； （2）（AB）； （3）A B解：（1）AB =1,2 （2）AB =1,2 （3）AB=， ， ，,3設(shè) A=1，2，3，4，5，R=|x A，yA 且 x+y4，S=|xA，yA 且 x+y,S=空集 R*S=空集 S*R=空集 R-1=,S-1 =空集r(S)=s(R)=4設(shè) A=1, 2, 3, 4, 5, 6, 7, 8，R 是 A 上的整除關(guān)系，B=2, 4, 6(1) 寫出關(guān)系 R 的表示式； (2 )畫出關(guān)系 R 的哈斯圖；(3) 求出集合 B 的最大元、最小元 (1) R=(2) 哈斯圖如下：(3)集合 B 沒有最大元，最小元是 2四、證明題1248 63 5 7 形成性考核作業(yè) 41試證明集合等式：A (B C)=(AB) (AC)1證明：設(shè)，若 xA (B C)，則 xA 或 xB C，即 xA 或 xB 且 xA 或 xC即 xAB 且 xA C ，即 xT=(A B) (AC)，所以 A (BC) (AB) (AC) 反之，若 x(A B) (AC)，則 xAB 且 xA C，即 xA 或 xB 且 xA 或 xC，即 xA 或 xBC，即 xA (B C)，所以(A B) (AC) A (BC)因此A (B C)=(AB) (AC)2試證明集合等式 A (BC)=(AB) (AC)2證明：設(shè) S=A(BC)，T=(A B)(AC)， 若 xS，則 xA 且xB C，即 xA 且 x B 或 xA 且 xC ，也即 xAB 或 xAC ，即 xT，所以 ST 反之，若 xT，則 xAB 或 xAC，即 xA 且 xB 或 xA 且 xC也即 xA 且 xBC，即 xS ，所以 TS因此 T=S 3對(duì)任意三個(gè)集合 A, B 和 C，試證明：若 A B = A C，且 A ，則 B = C （1） 對(duì)于任意AB，其中 aA，bB,因?yàn)?AB= AC，必有AC,其中 b C 因此 BC（2）同理，對(duì)于任意AC,其中，aA，cC，因?yàn)?AB= AC必有AB，其中 cB，因此 CB有（1）（2）得 B=C4試證明：若 R 與 S 是集合 A 上的自反關(guān)系，則 RS 也是集合 A 上的自反關(guān)系若 R 與 S 是集合 A 上的自反關(guān)系，則任意 xA, x,xR,x,xS,從而x,xRS,注意 x 是 A 的任意元素，所以 RS 也是集合 A 上的自反關(guān)系 形成性考核作業(yè) 5離散數(shù)學(xué)作業(yè) 5離散數(shù)學(xué)圖論部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共 3 次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型（除單項(xiàng)選擇題外）安排練習(xí)題目，目的是通過綜合性書面作業(yè)，使同學(xué)自己檢驗(yàn)學(xué)習(xí)成果，找出掌握的薄弱知識(shí)點(diǎn)，重點(diǎn)復(fù)習(xí)，爭(zhēng)取盡快掌握。本次形考書面作業(yè)是第二次作業(yè)，大家要認(rèn)真及時(shí)地完成圖論部分的綜合練習(xí)作業(yè)。要求：將此作業(yè)用 A4 紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，要求 2010 年 12 月 5 日前完成并上交任課教師（不收電子稿）。并在 05 任務(wù)界面下方點(diǎn)擊“保存”和“交卷”按鈕，以便教師評(píng)分。一、填空題1已知圖 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 2設(shè)給定圖 G(如右由圖所示)，則圖 G 的點(diǎn)割集是f 3設(shè) G 是一個(gè)圖，結(jié)點(diǎn)集合為 V，邊集合為 E，則G 的結(jié)點(diǎn) 度數(shù)之和 等于邊數(shù)的兩倍4無向圖 G 存在歐拉回路，當(dāng)且僅當(dāng) G 連通且 等于出度 5設(shè) G=是具有 n 個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若在 G 中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于 n-1 ，則在 G 中存在一條漢密爾頓路6若圖 G=中具有一條漢密爾頓回路，則對(duì)于結(jié)點(diǎn)集 V 的每個(gè)非空子集 S，在 G 中刪除 S 中的所有結(jié)點(diǎn)得到的連通分支數(shù)為 W，則 S 中結(jié)點(diǎn)數(shù)|S|與 W 滿足的關(guān)系式為 W(G-V1) V1 7設(shè)完全圖 K 有 n 個(gè)結(jié)點(diǎn)(n2)，m 條邊，當(dāng) n 為奇數(shù) 時(shí)，K中存在歐拉回路n8結(jié)點(diǎn)數(shù) v 與邊數(shù) e 滿足 e=v-1 關(guān)系的無向連通圖就是樹9設(shè)圖 G 是有 6 個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為 18，則可從 G 中刪去姓 名： 學(xué) 號(hào)： 得 分： 教師簽名： 形成性考核作業(yè) 64 條邊后使之變成樹10設(shè)正則 5 叉樹的樹葉數(shù)為 17，則分支數(shù)為 i = 5 二、判斷說明題（判斷下列各題，并說明理由）1如果圖 G 是無向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖 G 存在一條歐拉回路(1) 不正確，缺了一個(gè)條件，圖 G 應(yīng)該是連通圖，可以找出一個(gè)反例，比如圖 G 是一個(gè)有孤立結(jié)點(diǎn)的圖。2如下圖所示的圖 G 存在一條歐拉回路(2) 不正確，圖中有奇數(shù)度結(jié)點(diǎn)，所以不存在是歐拉回路。3如下圖所示的圖 G 不是歐拉圖而是漢密爾頓圖 解：正確因?yàn)閳D中結(jié)點(diǎn) a，b，d， f 的度數(shù)都為奇數(shù)，所以不是歐拉圖。如果我們沿著(a,d,g,f,e,b,c,a)，這樣除起點(diǎn)和終點(diǎn)是 a 外，我們經(jīng)過每個(gè)點(diǎn)一次僅一次，所以存在一條漢密爾頓回路，是漢密爾頓圖4設(shè) G 是一個(gè)有 7 個(gè)結(jié)點(diǎn) 16 條邊的連通圖，則 G 為平面圖解：(1) 錯(cuò)誤假設(shè)圖 G 是連通的平面圖，根據(jù)定理，結(jié)點(diǎn)數(shù) v，邊數(shù)為 e，應(yīng)滿足 e 小于等于 3v-6，但現(xiàn)在 16 小于等于 3*7-6，顯示不成立。所以假設(shè)錯(cuò)誤。5設(shè) G 是一個(gè)連通平面圖，且有 6 個(gè)結(jié)點(diǎn) 11 條邊，則 G 有 7 個(gè)面(2) 正確根據(jù)歐拉定理，有 v-e+r=2，邊數(shù) v=11，結(jié)點(diǎn)數(shù) e=6，代入公式求出面數(shù)r=7G 形成性考核作業(yè) 7三、計(jì)算題1設(shè) G=，V= v 1，v 2，v 3，v 4，v 5，E = (v1,v3)，( v2,v3)，(v 2,v4)，(v3,v4)， (v3,v5)，( v4,v5) ，試(1) 給出 G 的圖形表示； (2) 寫出其鄰接矩陣；(3) 求出每個(gè)結(jié)點(diǎn)的度數(shù)； (4) 畫出其補(bǔ)圖的圖形解：(1)(2) 鄰接矩陣為 010010(3) v1 結(jié)點(diǎn)度數(shù)為 1，v 2 結(jié)點(diǎn)度數(shù)為 2，v 3 結(jié)點(diǎn)度數(shù)為 3，v 4 結(jié)點(diǎn)度數(shù)為 2，v 5 結(jié)點(diǎn)度數(shù)為 2(4) 補(bǔ)圖圖形為2圖 G=，其中 V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，對(duì)應(yīng)邊的權(quán)值依次為 2、1、2 、3、6、1、4 及 5，試（1）畫出 G 的圖形； （2）寫出 G 的鄰接矩陣；（3）求出 G 權(quán)最小的生成樹及其權(quán)值（1）G 的圖形如下： v1 v5v2v3 v4 v1 v5v2v3 v4 形成性考核作業(yè) 8（2）寫出 G 的鄰接矩陣（3）G 權(quán)最小的生成樹及其權(quán)值3已知帶權(quán)圖 G 如右圖所示 (1) 求圖 G 的最小生成樹； (2)計(jì)算該生成樹的權(quán)值解：(1) 最小生成樹為 形成性考核作業(yè) 91 2357(2) 該生成樹的權(quán)值為 (1+2+3+5+7)=184設(shè)有一組權(quán)為 2, 3, 5, 7, 17, 31，試畫出相應(yīng)的最優(yōu)二叉樹，計(jì)算該最優(yōu)二叉樹的權(quán)35251071731173465 形成性考核作業(yè) 10權(quán)為 2*5+3*5+5*4+7*3+17*2+31=131四、證明題1設(shè) G 是一個(gè) n 階無向簡(jiǎn)單圖，n 是大于等于 3 的奇數(shù)證明圖 G 與它的補(bǔ)圖 中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等證明：設(shè) ， 則 是由 n 階無向完全圖 的邊刪去 E,VE,E nK所得到的所以對(duì)于任意結(jié)點(diǎn) ，u 在 G 和 中的度數(shù)之和等于 u 在 中Vn的度數(shù)由于 n 是大于等于 3 的奇數(shù)，從而 的每個(gè)結(jié)點(diǎn)都是偶數(shù)度的（nK度），于是若 在 G 中是奇數(shù)度結(jié)點(diǎn)，則它在 中也是奇數(shù)度結(jié)1 (2)n G點(diǎn)故圖 G 與它的補(bǔ)圖 中的奇數(shù)度結(jié)點(diǎn)個(gè)數(shù)相等2設(shè)連通圖 G 有 k 個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖 G 中至少要添加 條邊才2k能使其成為歐拉圖證明：由定理 3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)，可知 k 是偶數(shù)又根據(jù)定理 4.1.1 的推論，圖 G 是歐拉圖的充分必要條件是圖 G 不含奇數(shù)度結(jié)點(diǎn)因此只要在每對(duì)奇數(shù)度結(jié)點(diǎn)之間各加一條邊，使圖 G 的所有結(jié)點(diǎn)的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖故最少要加 條邊到圖 G 才能使其成為歐拉圖2k離散數(shù)學(xué)作業(yè) 7離散數(shù)學(xué)數(shù)理邏輯部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共 3 次，內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí)，基本上是按照考試的題型（除單項(xiàng)選擇題外）安排練習(xí)題目，目的是通過綜合性書面作業(yè)，使同學(xué)自己檢驗(yàn)學(xué)習(xí)成果，找出掌握的薄弱知識(shí)點(diǎn)，重點(diǎn)復(fù)習(xí)，爭(zhēng)取盡快掌握。本次形考書面作業(yè)是第三次作業(yè)，大家要認(rèn)真及時(shí)地完成數(shù)理邏輯部分的綜合練習(xí)作業(yè)。姓 名： 學(xué) 號(hào)： 得 分： 教師簽名： 形成性考核作業(yè) 11要求：將此作業(yè)用 A4 紙打印出來，手工書寫答題，字跡工整，解答題要有解答過程，要求本學(xué)期第 17 周末前完成并上交任課教師（不收電子稿）。并在 07 任務(wù)界面下方點(diǎn)擊“保存”和“交卷”按鈕，以便教師評(píng)分。一、填空題1命題公式 的真值是1 或 T ()PQ2設(shè) P：他生病了，Q：他出差了R：我同意他不參加學(xué)習(xí). 則命題“如果他生病或出差了，我就同意他不參加學(xué)習(xí)”符號(hào)化的結(jié)果為 （P Q） R 3含有三個(gè)命題變項(xiàng) P，Q，R 的命題公式 PQ 的主析取范式是 (P Q R) (P Q R) 4設(shè) P(x)：x 是人，Q(x) ：x 去上課，則命題“有人去上課” 可符號(hào)化為 x(P(x) Q(x) 5設(shè)個(gè)體域 Da, b,那么謂詞公式 消去量詞后的等值式為 )()(yBxA(A(a) A(b) (B(a) B(b) 6設(shè)個(gè)體域 D1, 2, 3，A( x)為“x 大于 3”，則謂詞公式(x)A (x) 的真值為 0(F) 7謂詞命題公式(x)(A(x)B(x) C(y)中的自由變?cè)獮?y 8謂詞命題公式(x)( P(x) Q(x) R(x，y) 中的約束變?cè)獮?x 三、公式翻譯題1請(qǐng)將語(yǔ)句“今天是天晴”翻譯成命題公式設(shè) P：今天是晴天。則 P2請(qǐng)將語(yǔ)句“小王去旅游，小李也去旅游”翻譯成命題公式 設(shè) P：小王去旅游。Q：小李去旅游。則 PQ3請(qǐng)將語(yǔ)句“他去旅游，僅當(dāng)他有時(shí)間”翻譯成命題公式設(shè) P：他去旅游。Q：他有時(shí)間。則 P Q4.將語(yǔ)句“41 次列車下午五點(diǎn)開或者六點(diǎn)開”翻譯成命題公式。 形成性考核作業(yè) 125請(qǐng)將語(yǔ)句 “有人不去工作”翻譯成謂詞公式設(shè) A（x）：x 是人B（x）：去工作x(A(x) B(x)6請(qǐng)將語(yǔ)句“所有人都努力工作”翻譯成謂詞公式設(shè) A（x）：x 是人B（x）：努力工作x(A(x) B(x)四、判斷說明題（判斷下列各題，并說明理由）1命題公式PP 的真值是 1解：錯(cuò)。因?yàn)?P 和 P 的否不能同時(shí)為真。2(x)(P (x)Q(y )R(z)中的約束變?cè)獮?y 解：錯(cuò)。(x)(P(x) Q(y)R(z)中的約束變?cè)獮椤?謂詞公式 中x 量詞的轄域?yàn)?,(),zQx,),y解：錯(cuò)。因?yàn)榫o接于量詞之后最小的子公式稱為量詞的轄域，所以x 的轄域p(x,y)。4下面的推理是否正確，請(qǐng)給予說明(1) (x)A(x) B(x) 前提引入(2) A(y) B(y) US (1)答：錯(cuò)誤。（2）應(yīng)為 A(y) B(x)，換名時(shí)，約束變?cè)c自由變?cè)荒芑煜?。四?jì)算題1 求 PQR 的析取范式，合取范式、主析取范式，主合取范式PQR PQR （析取范式）（ PQR） （合取范式）真值表：P Q R P 原式 極小項(xiàng) 及大項(xiàng)0 0 0 1 1 P P P0 0 1 1 1 P Q R0 1 0 1 1 P Q R0 1 1 1 1 P Q R1 0 0 0 0 PQR 形成性考核作業(yè) 131 0 1 0 1 P Q R1 1 0 0 1 P Q R1 1 1 0 1 P Q R主 析取范式 （ P P P）（ P Q R） （ P Q R） （P Q R）（P Q R） （P Q R）（P Q R） 主 合取范式（ PQR）2求命題公式(P Q)(RQ) 的主析取范式、主合取范式真值表：P Q R （ PQ）RQ 原式 極小項(xiàng) 及大項(xiàng)0 0 0 1 0 1 P P P0 0 1 1 1 1 P Q R0 1 0 0 1 1 P Q R0 1 1 0 1 1 P Q R1 0 0 0 0 0 PQR1 0 1 0 1 1 P Q R1 1 0 0 1 1 P Q R1 1 1 0 1 1 P Q R主 析取范式 （ P P P）（ P Q R） （ P Q R） （P Q R）（P Q R） （P Q R）（P Q R） 主 合取范式（ PQR）3設(shè)謂詞公式 (),(),)(,)xyzyxyz（1）試寫出量詞的轄域；（2）指出該公式的自由變?cè)图s束變?cè)穑海?） x 的轄域?yàn)?P（x,y） zQ(x,y,z)z 的轄域?yàn)?Q(x,y,z) y 的轄域?yàn)?R(y,z)(2) 約束變?cè)獮镻（x,y） zQ(x,y,z)中的 xQ(x,y,z) 中的 zR(y,z) 中的 y自由變?cè)獮镻（x,y） zQ(x,y,z)中的 y 形成性考核作業(yè) 14R(y,z)中的 z4設(shè)個(gè)體域?yàn)?D=a1, a2，求謂詞公式y(tǒng)xP(x ,y)消去量詞后的等值式；答：謂詞公式y(tǒng) xP(x,y)消去量詞后的等值式為（R（ a,a） R（a,b） ） (R（b,a） R（b,b）)五、證明題1試證明 (P(QR)PQ 與 (PQ)等價(jià)證明：(P (QR)PQ P(QR)PQPQ（P Q）