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