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

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

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