【正文】 1 / 11 電大 離散數(shù)學(xué)（ 本 ） 期末復(fù)習(xí)資料小抄 一、單項(xiàng)選擇題 1．設(shè) P： a 是偶數(shù)， Q： b 是偶數(shù)。 R： a + b 是偶數(shù)，則命題“若 a 是偶數(shù)， b 是偶數(shù)，則 a + b 也是偶數(shù)”符號(hào)化為（ D． P Q→ R）。 2．表達(dá)式 ? x（ P（ x， y） ? Q（ z）） ? ? y（ Q（ x， y）→ ? zQ（ z））中 ? x 的轄域是（ P（ x， y） Q（ z） ）。 3．設(shè) )(} ),({},{, 4321 ???????? PSPSSS 則命題為假的是（ 42 SS ? ）。 4．設(shè) G 是有 n 個(gè)結(jié)點(diǎn)的無(wú)向完全圖，則 G 的邊數(shù)（ 1/2 n（ n1） ）。 5．設(shè) G 是連通平面圖，有 v 個(gè)結(jié)點(diǎn)， e 條邊， r 個(gè)面，則 r=（ ev+2）。 6．若集合 A={1， {2}， {1， 2}}，則下列表述正確的是 ( {1}?A )． 7．已知一棵無(wú)向樹 T 中有 8 個(gè)頂點(diǎn)， 4 度、 3 度、 2 度的分支點(diǎn)各一個(gè)， T 的樹葉數(shù)為 ( 5 )． 8．設(shè)無(wú)向圖 G 的鄰接矩陣為????????????????0101110011000011100111110則 G 的邊數(shù)為 ( 7 )． 9．設(shè)集合 A={a}，則 A 的冪集為 ({?， {a}} )． 10．下列公式中 (?A??B ? ?(A?B) )為永真式． 11．若 G 是一個(gè)漢密爾頓圖，則 G 一定是 ( 連通圖 )． 12．集合 A={1, 2, 3, 4}上的關(guān)系 R={x， y|x=y 且 x, y?A}，則 R 的性質(zhì)為（傳遞的 ）． 13．設(shè)集合 A={1， 2， 3， 4， 5}，偏序關(guān)系 ?是 A 上的整除關(guān)系，則偏序集 A， ?上的元素 5 是集合 A 的（極大元 ）． 14．圖 G 如圖一所示，以下說(shuō)法正確的是 ( {(a, d) ,(b, d)}是邊割集 ) ． 圖一 15．設(shè) A（ x）： x 是人， B（ x）： x 是工人，則命題“有人是工人”可符號(hào)化為（ (? x)(A(x)∧ B(x)) ）． 16．若集合 A={1， 2}， B={1， 2， {1， 2}}，則下列表述正確的是 (A?B，且 A?B )． 17．設(shè)有向圖（ a）、（ b）、（ c）與（ d）如圖一所示 ， 則下列結(jié)論成立的是 ( （ d）是強(qiáng)連通的 )． 18．設(shè)圖 G 的鄰接矩陣為????????????????0101010010000011100100110則 G 的邊數(shù)為 ( 5 )． 19．無(wú)向簡(jiǎn)單圖 G 是棵樹，當(dāng)且僅當(dāng) (G 連通且邊數(shù)比結(jié)點(diǎn)數(shù)少 1 )． 20．下列公式 ((P?(?Q?P))?(?P?(P?Q)) )為重言式． 21．若集合 A＝ { a， {a}， {1， 2}}，則下列表述正確的是 ({a}?A)． 22．設(shè)圖 G＝ V, E， v?V， 則下列結(jié)論成立的是 ( EvVv 2)deg( ??? ) ． 23．命題公式（ P∨ Q）→ R 的析取范式是 (（ ?P∧ ?Q）∨ R ) 24．下列等價(jià)公式成立的為 (P?(?Q?P) ??P?(P?Q) )． 25．設(shè) A={a, b}， B={1, 2}， R1， R2， R3是 A 到 B 的二元關(guān)系，且 R1={a， 2, b， 2}， R2={a， 1, a， 2, b， 1}， R3={a， 1, b， 2}，則（ R2 ）不是從 A 到 B 的函數(shù)． 26．設(shè) A={1, 2, 3, 4, 5, 6, 7, 8}， R 是 A 上的整除關(guān)系， B={2, 4, 6}，則集合 B 的最大元、最小元、上界、下界依次為 (無(wú)、 無(wú)、 2)． 2 / 11 27．若集合 A 的元素個(gè)數(shù)為 10，則其冪集的元素個(gè)數(shù)為（ 1024）． 28．如圖一所示，以下說(shuō)法正確的是 (e 是割點(diǎn) )． 圖一 29．設(shè)完全圖 Kn 有 n 個(gè)結(jié)點(diǎn) (n≥ 2)， m 條邊，當(dāng)（ n 為奇數(shù) ）時(shí)， Kn 中存在歐拉回路． 30．已知圖 G 的鄰接矩陣為 ，則 G 有（ 5 點(diǎn)， 7 邊 ）． 二、填空題（每小題 3 分，共 15分） 1．設(shè) A， B為任意命題公式， C為重言式，若 A ? C? B? C，那么 A? B 是 重言 式（重言式、矛盾式或可滿足式）。 2．命題公式（ P→ Q） ? P的主合取范式為 )()( QPQP ???? 。 3．設(shè)集合 A={? ， {a}}，則 P（ A） = }}}{,{}},{{},{,{ aa ??? 。 4．設(shè)圖 G =〈 V， E〉， G ′ =〈 V′， E′〉，若 V′ =V,E′ E ,則 G′是 G的生成子圖。 5．在平面 G =〈 V， E〉中，則 ??ri ir1 )deg(= 2|E| ，其中 ir （ i=1， 2，?， r）是 G的面。 6．命題公式 PP ?? 的真值是 假（或 F，或 0） ． 7．若無(wú)向樹 T 有 5 個(gè)結(jié)點(diǎn)，則 T 的邊數(shù)為 4 ． 8．設(shè)正則 m 叉樹的樹葉數(shù)為 t，分支數(shù)為 i，則 (m1)i= t1 ． 9．設(shè)集合 A={1， 2}上的關(guān)系 R＝ {1, 1,1, 2}，則在 R 中僅需加一個(gè)元素 2, 1 ，就可使新得到的關(guān)系為對(duì)稱的． 10． (?x)(A(x)→ B(x， z)∨ C(y))中的 自由 變?cè)?有 z， y ． 11．若集合 A={1， 3， 5， 7}， B={2， 4， 6， 8}，則 A∩ B= 空集（或 ?） ． 12．設(shè) 集合 A={1， 2， 3}上的函數(shù)分別為： f={1,2,2,1,3,3,}， g={1,3,2,2,3,2,}，則復(fù)合函數(shù) g?f = {1, 2, 2, 3, 3, 2,} ． 13．設(shè) G 是一個(gè)圖，結(jié)點(diǎn)集合為 V，邊集合為 E，則 G 的結(jié)點(diǎn)度數(shù)之和 為 2|E|（或“邊數(shù)的兩倍”） ． 14．無(wú)向連通圖 G 的結(jié)點(diǎn)數(shù)為 v，邊數(shù)為 e，則 G 當(dāng) v 與 e 滿足 e=v1 關(guān)系時(shí)是樹． 15．設(shè)個(gè)體域 D＝ {1, 2, 3}， P(x)為“ x 小于 2”，則謂詞公式 (?x)P(x) 的真值為 假（或 F，或 0） ． 16．命題公式 )( PQP ?? 的真值是 T （或 1） ． 17．若圖 G=V, E中具有一條漢密爾頓回路，則對(duì)于結(jié)點(diǎn)集 V 的每個(gè)非空子集 S，在 G 中刪除 S 中的所有結(jié)點(diǎn)得到的連通分支數(shù)為 W，則 S中結(jié)點(diǎn)數(shù) |S|與 W 滿足的關(guān)系式為 W?|S| ． 18．給定一個(gè)序列集合 {000， 001， 01， 10， 0}，若去掉其中的元素 0 ，則該序列集合構(gòu)成前綴碼． 19．已知一棵無(wú)向樹 T 中有 8 個(gè)結(jié)點(diǎn)， 4 度， 3 度， 2 度的分支點(diǎn)各一個(gè)， T 的樹葉數(shù)為 5 ． 20． (?x)(P(x)→ Q(x)∨ R(x， y))中的 自由 變?cè)?為 R(x， y )中的 y ． 21．設(shè)集合 A={0, 1, 2, 3}， B={2, 3, 4, 5}， R 是 A 到 B 的二元關(guān)系， },{ BAyxByAxyxR ??????? 且且則 R 的有序?qū)蠟? {2, 2， 2, 3， 3, 2}， 3, 3 ． 22．設(shè) G 是連通平面圖， v, e, r 分別表示 G 的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則 v， e 和 r 滿足的關(guān)系式 ve+r=2 ． 23．設(shè) G＝ V, E是有 6 個(gè)結(jié)點(diǎn)， 8 條邊的連通圖，則從 G 中刪去 3 條邊，可以確定圖 G 的一棵生成樹． 24．無(wú)向圖 G 存在歐拉回路，當(dāng)且僅當(dāng) G 連通且 所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) ． 25．設(shè)個(gè)體域 D＝ {1,2}，則謂詞公式 )(xxA? 消去量詞后的等值式為 A(1)?A(2) ． 26．設(shè)集合 A＝ {a， b}， 那么集合 A 的冪集是 {?,{a,b},{a},{b }} ． 27．如果 R1和 R2 是 A 上的自反關(guān)系，則 R1∪ R2， R1∩ R2， R1R2 中自反關(guān)系有 2 個(gè)． 28．設(shè)圖 G 是有 6 個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為 18，則可從 G 中刪去 4 條邊后使之變成樹． 3 / 11 29．設(shè)連通平面圖 G 的結(jié)點(diǎn)數(shù)為 5，邊數(shù)為 6，則面數(shù)為 3 ． 30．設(shè)個(gè)體域 D＝ {a, b}，則謂詞公式 (?x)A(x)∧（ ?x） B（ x） 消去量詞后的等值式為 (A (a)∧ A (b))∧ (B（ a） ∨ B（ b） ) ． 31. 設(shè)集合 A={0， 1 ， 2} ， B={l ， 2 ， 3 ， 剖， R 是 A 到 B 的二元關(guān)系， R= {x ,y |x∈ A 且 y∈ B 且 x， y∈ A∩ B} 則 R 的有序?qū)蠟?___{1,1,1,2,2,1,2,2}___ 32. 設(shè) G 是連通平面圖， v， e ， r 分別表示 G 的結(jié)點(diǎn)數(shù)， 邊數(shù)和面數(shù)， 則 v， e 和 r 滿足的關(guān)系式 __ve+r=2_____ =V,E是有 20 個(gè)結(jié)點(diǎn)， 25 條邊的連通圖 ,則從 G 中刪去 __6__條邊，可以確定圖 G 的一棵生成樹 . 34. 無(wú)向圖 G 存在歐拉回路， 當(dāng)且僅當(dāng) G 所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)且 _ 連通 ____ 35. 設(shè)個(gè)體域 D={ 1, 2 } ， 則謂詞公式 ? xA(x)消去量詞后的等值式為 __A(1)∧ A(2)___ 三、化簡(jiǎn)解答題 11．設(shè)集合 A={1， 2， 3， 4}， A 上的二元關(guān)系 R， R={〈 1， 1〉，〈 1， 4〉，〈 2， 2〉，〈 2， 3〉，〈 3， 2〉，〈 3， 3〉，〈 4， 1〉，〈 4， 4〉 }，說(shuō)明 R 是 A上的等價(jià)關(guān)系。 解 從 R 的表達(dá)式知， ,),(, RxxAx ??? 即 R具有自反性； 三、邏輯公式翻譯 1．將語(yǔ)句 “今天上課． ”翻譯成命題公式． 設(shè) P：今天上課， 則命題公式為： P． 2．將語(yǔ)句 “他去操場(chǎng)鍛煉，僅當(dāng)他有時(shí)間． ”翻譯成命題公式． 設(shè) P：他去操場(chǎng)鍛煉， Q：他有時(shí)間， 則命題公