(電大復(fù)習(xí))本科離散數(shù)學(xué)共享資料

1 離散數(shù)學(xué)復(fù)習(xí)資料 2014 年 6 月 一、單項(xiàng)選擇題（每小題 3 分，本題共 15 分） 1若集合 A=1， 2， B=1， 2， 1， 2，則下列表述正確的是 ( A ) A AB，且 AB B BA，且 AB C AB，且 AB D AB，且 AB 2設(shè)有向圖（ a）、（ b）、（ c）與（ d）如 圖一所示 ， 則下列結(jié)論成立的是 ( D ) 圖一 A （ a） 是強(qiáng)連通的 B（ b） 是強(qiáng)連通的 C（ c） 是強(qiáng)連通的 D（ d） 是強(qiáng)連通的 3設(shè)圖 G 的鄰 接 矩陣為 0101010010000011100100110則 G 的邊數(shù)為 ( B ) A 6 B 5 C 4 D 3 4無向簡單圖 G 是棵樹，當(dāng)且僅當(dāng) ( A ) A G 連通且邊數(shù)比 結(jié)點(diǎn) 數(shù)少 1 B G 連通且 結(jié)點(diǎn) 數(shù) 比 邊數(shù)少 1 C G 的邊數(shù)比 結(jié)點(diǎn) 數(shù)少 1 D G 中沒 有回路 5下列公式 ( C )為重言式 A PQPQ B (Q(PQ) (Q(PQ) C (P(QP)(P(PQ) D (P(PQ) Q 6設(shè) A=a, b， B=1, 2， R1， R2， R3是 A 到 B 的二元關(guān)系，且 R1=, ，R2=, , ， R3=, ，則（ B ）不是從 A 到 B 的函數(shù) A R1 和 R2 B R2 C R3 D R1 和 R3 7設(shè) A=1, 2, 3, 4, 5, 6, 7, 8， R 是 A 上的整除關(guān)系， B=2, 4, 6，則集合 B 的最大元、最小元、上界、下界依次為 ( B ) A 8、 2、 8、 2 B無、 2、無、 2 C 6、 2、 6、 2 D 8、 1、 6、 1 8若集合 A 的元素個(gè)數(shù)為 10，則其冪集的元素個(gè)數(shù)為（ A ） A 1024 B 10 C 100 D 1 9設(shè)完全圖 Kn有 n 個(gè)結(jié)點(diǎn) (n 2)， m 條邊，當(dāng)（ C ）時(shí)， Kn中存在歐拉回路 A m 為奇數(shù) B n 為偶數(shù) 2 C n 為奇數(shù) D m 為偶數(shù) 10已知圖 G 的鄰接矩陣為 ， 則 G 有（ D ） A 5 點(diǎn)， 8 邊 B 6 點(diǎn)， 7 邊 C 6 點(diǎn)， 8 邊 D 5 點(diǎn)， 7 邊 11.無向完全圖 K3 的不同構(gòu)的生成子圖的個(gè)數(shù)為（ C ） (A) 6 (B) 5 (C) 4 (D) 3 12 n 階無向完全圖 Kn中的邊數(shù)為（ A ） (A) 2 )1( nn(B) 2 )1( nn(C) n (D)n(n+1) 13.在圖 G 中，結(jié)點(diǎn)總度數(shù)與邊數(shù)的關(guān)系是 ( C ) A deg(vi)=2E (B) deg(vi)=E C VvEv 2)deg( DVvEv )deg( 二、填空題（每小題 3 分，本題共 15 分） 1命題公式 )( PQP 的真值是 1 2 若 A=1,2， R=|xA, yA, x+y, 3已知一棵無向樹 T 中有 8 個(gè) 結(jié)點(diǎn) ， 4 度， 3 度 ， 2 度的分支點(diǎn)各一個(gè)， T 的樹葉數(shù)為 5 4 (x)(P(x) Q(x) R(x， y)中的 自由 變元 為 R(x， y )中的 y 5設(shè)集合 A a， b， 那么集合 A 的冪集是 ,a,b,a,b 6如果 R1和 R2是 A上的自反關(guān)系，則 R1 R2， R1 R2， R1-R2中自反關(guān)系有 2 個(gè) 7設(shè)圖 G 是有 6 個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為 18，則可從 G 中刪去 4 條邊后使之變成樹 8無向圖 G 存 在歐拉回路，當(dāng)且僅當(dāng) G 所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)且 連通 9 設(shè)連通平面圖 G 的結(jié)點(diǎn)數(shù)為 5，邊數(shù)為 6，則面數(shù)為 3 10設(shè)個(gè)體域 D a, b，則謂詞公式 (x)A(x)（ x） B（ x） 消去量詞后的等值式為 (A (a) A (b) (B（ a） B（ b） ) 三、邏輯公式翻譯 （ 每小題 6 分， 本題共 12 分） 1將 語句“雪是黑色的 ”翻譯成命題公式 設(shè) P：雪是黑色的， （ 2 分） 3 則命題公式為： P 2 將 語句“ 他不去學(xué)校 ”翻譯成命題公式 解：設(shè) P：他去學(xué)校， 則命題公式為： P 3 將 語句 “小王是個(gè)學(xué)生，小李是個(gè)職員，而小張是個(gè)軍人 ”翻譯成命題公式 設(shè) P：小王是個(gè)學(xué)生， Q：小李是個(gè)職員， R：小張是個(gè)軍人 （ 2 分） 則命題公式為： P Q R 4 將 語句“如果所有人今天都去參加活動，則明天的會議取消 ”翻譯成命題公式 解：設(shè) P：所有人今天都去參加活動， Q：明天的會議取消， 則命題公式為： P Q 5 將 語句“ 他去旅游，僅當(dāng)他有時(shí)間 ”翻譯成命題公式 解：設(shè) P：他去旅游， Q：他有時(shí)間， 則命題公式為： P Q 6 將 語句“ 41 次列車下午五點(diǎn)開或者六點(diǎn)開 ”翻譯成命題公式 解： 設(shè) P： 41 次列車下午五點(diǎn)開， Q： 41 次列車下午六點(diǎn)開， （ 2 分） 命題公式為：（ P Q） （ P Q） 7 將 語句“小張學(xué)習(xí)努力，小王取得好成績 ”翻譯成命題 設(shè) P：小張學(xué)習(xí)努力， Q：小王取得好成績， （ 2 分） 則命題公式為： PQ 8 將 語句“有人去上課 ” 翻譯成謂詞公式 解： 設(shè) P(x)： x 是人， Q(x)： x 去上課， （ 1 分） (x)(P(x) Q(x) 9 將 語句“所有的人都學(xué)習(xí)努力 ”翻譯成命題公式 解：設(shè) P(x)： x 是人， Q(x)： x 學(xué)習(xí)努力， x） (P(x)Q(x) 四、判斷說明題 （ 每小題 7 分， 本題共 14 分） 判斷下列各題正誤，并說明理由 1設(shè)集合 A=1, 2, 3, 4， B=2, 4, 6, 8，判斷下列關(guān)系 f 是否構(gòu)成函數(shù) f： BA ，并說明理由 (1) f=, , , ； (2)f=, , ； (3) f=, , , 答 ：（ 1）不構(gòu)成函數(shù) 因?yàn)?3 A ，但 3f 沒有定義，所以不構(gòu)成函數(shù) （ 2）不構(gòu)成函數(shù) 因?yàn)?4 A ，但 4f 沒有定義，所以不構(gòu)成函數(shù) （ 3）滿足。 因?yàn)槿我?xA ，都有 f x B 且結(jié)果唯一。 2 若 集合 A = 1， 2， 3上的 二元關(guān)系 R=， ， ，則 4 (1) R 是自反的關(guān)系； (2) R 是對稱的關(guān)系 答 ：（ 1）錯(cuò)誤 因?yàn)?3 3 R， ，所以 R 不是自 反的 （ 2） 錯(cuò)誤 因?yàn)?1 2 R， ，但是 2 1 R， ，所以 R 不是對稱的 3如果 R1和 R2是 A 上的自反關(guān)系，判斷結(jié)論：“ R- 11、 R1 R2、 R1R2 是自反的” 是否成立？并說明理由 答 ：成立 因?yàn)槿我?aA ，有12, , ,a a R a a R所以 1,a a R ，12,a a R R U，12,a a R R IR-11、 R1 R2、 R1R2 是自反的 4若偏序集 的哈斯圖如圖一所示， 則集合 A 的最大元為 a，最小元不存在 答 ：錯(cuò)誤，集合 A 沒有最大元，也沒有最小元 其中 a 是極大元 5若偏序集 的哈斯圖如圖一所示，則集合 A 的最大元為 a，最小元不存在 解：正確 對于集合 A 的任意元素 x，均有 R（或 xRa），所以 a 是集合 A 中的最大元按照最小元的定義，在集合 A 中不存在最小元 6 如果圖 G 是無向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖 G 存在一條歐拉回路 答：錯(cuò)誤 如果圖 G 是無向圖，且圖 G 是連通的，同時(shí)結(jié)點(diǎn)度數(shù)都是偶數(shù) 7 設(shè) G 是一個(gè)連通平面圖， 且 有 6 個(gè)結(jié)點(diǎn) 11 條邊，則 G 有 7 個(gè)面 答案：正確 定理，連通平面圖 G 的結(jié)點(diǎn)數(shù)為 v，邊數(shù)是 e，面數(shù)為 r，則歐拉公式 v-e+r=2成立 所以 r=2-v+e=2-6+11=7 則 G 存在一條歐拉回路 8 設(shè) G 是一個(gè)有 6 個(gè)結(jié)點(diǎn) 14 條邊的連通圖， 則 G 為平面圖 解：錯(cuò)誤 ， 不滿足“ 設(shè) G 是一個(gè)有 v 個(gè)結(jié)點(diǎn) e 條邊的連通簡單平面圖，若 v 3，則 e 3v-6” 9命題公式 P(PQ)P 為永真式 解 ： 正確 因?yàn)?，由真值?P Q P Q PQ P (P Q) P 0 0 1 1 1 1 a b c d 圖一 g e f h 5 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 1 可知，該命題公式為永真式 五計(jì)算題 （每小題 12 分，本題共 36 分 ） 1設(shè)集合 A=a, b, c， B=a, c，試計(jì)算 （ 1）（ AB）； （ 2）（ B A）； （ 3）（ AB） B 解 （ 1）（ AB） =c； （ 2）（ B A） =a； （ 3）（ AB） B=, 2設(shè) A=0， 1， 2， 3， 4， 5， 6， R=|xA， yA 且 x+y|xA， yA且 x+y3，試求 R， S， RS， R-1， S-1， r(R) 解： R= S=, RS=, R-1= S-1= S ） r(R)=IA 3圖 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 的圖形表示為： （ 3 分） （ 2）鄰接矩陣： 0111110110110011100110110（ 6 分） （ 3）粗線 表示最小的生成樹， 6 權(quán)為 7： 4設(shè)圖 G=， V= v1， v2， v3， v4， v5， E= (v1, v2)， (v1, v3)， (v2, v3)， (v2, v4)，(v3, v4)， (v3, v5)， (v4, v5) ，試 (1) 畫出 G 的圖形表示； (2) 求出每個(gè)結(jié)點(diǎn)的度數(shù)； (3) 畫出圖 G 的補(bǔ)圖的圖形 解：（ 1）關(guān)系圖 （ 2） deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2 （ 3） 補(bǔ)圖 5 設(shè)集合 A=1， 2， 3， 4， R=|x, yA； |xy|=1 或 xy=0， 試 （ 1）寫出 R 的有序?qū)Ρ硎荆?（ 2）畫出 R 的關(guān)系圖； （ 3）說明 R 滿足自反性，不滿足傳遞性 解 :（ 1） R=, （ 3 分） （ 2）關(guān)系圖為 （ 3）因?yàn)?,均屬于 R，即 A 的每個(gè)元素構(gòu)成的有序?qū)?R 中，故 R 在 A 上是自反的。 因有 與 屬于 R，但 不屬于 R，所以 R 在 A 上不是傳遞的。 1 2 3 4 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 7 6設(shè)集合 A=1, 2, 3， R=, ,， S=, 試計(jì)算 （ 1） RS； （ 2） R 1； （ 3） r（ R） 解： （ 1） RS =, ,； （ 4 分） （ 2） R 1=, , ； （ 8 分） （ 3） r（ R） =, , , , 7、 求出如 圖一 所示賦權(quán)圖中的最小生成樹（要求寫出求解步驟），并求此最小生成樹的權(quán) 解 用 Kruskal 算法求產(chǎn)生的最小生成樹 步驟為： 1),(71 vvw選711 vve 3),(43 vvw選432 vve 4),(72 vvw選723 vve 9),(73 vvw選734 vve 18),(54 vvw選545 vve 22),(61 vvw選616 vve （ 6 分） 最小生成樹如圖 四 所示： （ 9 分） 圖 四 最小生成樹的權(quán) 為： w(T)=22+1+4+9+3+18=57 （ 12 分） 8試 畫一棵帶權(quán)為 2, 3, 3, 4, 5,的 最優(yōu)二叉樹 ,并計(jì)算該最優(yōu)二叉樹的權(quán) 解： 最優(yōu)二叉樹 如圖二所示 （ 10 分） 圖二 2 3 3 4 5 5 10 7 17 8 權(quán)為 23+33+32+42+52=39 9設(shè)謂詞公式 ),(),(),( zyyCzyxzByxAx ，試 （ 1）寫出量詞的轄域； （ 2）指出該公式的自由變元和約束變元 （ 1） x 量詞的轄域?yàn)?),(),( zyxzByxA ， （ 2 分） z 量詞的轄域?yàn)?),( zyxB , （ 4 分） y 量詞的轄域?yàn)?),( zyC （ 6 分） （ 2）自由變元為 ),(),( zyxzByxA 中的 y，以及 ),( zyC 中的 z （ 9 分） 約束變元為 ),(),( zyxzByxA 中的 x 與 ( , , )B x y z 中的 z，以及 ( , )C y z 中的 y 10設(shè)謂詞公式 ),()(),()( zyxQzyxPx ，試 （ 1）寫出量詞的轄域； （ 2）指出該公式的自 由變元和約束變元 （ 1） x 量詞的轄域?yàn)?),( yxP ， （ 3 分） z 量詞的轄域?yàn)?),( zyxQ , （ 6 分） （ 2）自由變元為公式中的 y 與 ),( zyxQ 中的 x， （ 9 分） 約束變元為 ),( yxP 的 x 與 ),( zyxQ z 11求命題公式 (PQ)(RQ) 的主析取范式、主合取范式 解： P Q R PQ RQ (PQ)(RQ) 極小項(xiàng) 極大項(xiàng) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 PQR PQR PQR PQR PQR PQR PQR PQR 主析取范式（極小項(xiàng)析取）：