(電大復習)本科離散數(shù)學共享資料

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