《2018年年電大離散數學(本科)考試試題及答案參考資料小抄》由會員分享，可在線閱讀，更多相關《2018年年電大離散數學(本科)考試試題及答案參考資料小抄（13頁珍藏版）》請在裝配圖網上搜索。

.中央電大離散數學（本科）考試試題一、單項選擇題（每小題 3 分，本題共 15 分）1．若集合 A={1， 2}，B={1，2，{1 ，2}}，則下列表述正確的是( a )．A．A?B，且 A?B B．B ?A，且 A?BC．A?B，且 A?B D．A?B ，且 A?B2．設有向圖（a）、（b）、（c ）與（d）如圖一所示，則下列結論成立的是 ( d )．圖一A．（a）是強連通的 B．（b）是強連通的C．（c ）是強連通的 D．（d）是強連通的3．設圖 G 的鄰接矩陣為 ??????01則 G 的邊數為( b )．A．6 B．5 C．4 D．34．無向簡單圖 G 是棵樹，當且僅當( a )．A．G 連通且邊數比結點數少 1 B．G 連通且結點數比邊數少 1C．G 的邊數比結點數少 1 D．G 中沒有回路．5．下列公式 ( c )為重言式．A．?P ??Q?P?Q B．(Q ?(P?Q)) ?(?Q?(P?Q))C．(P ?(?Q?P))?(?P?(P?Q)) D．( ?P?(P?Q)) ?Q1．若集合 A={a，b}，B={ a，b，{ a，b }}，則（ a ） ．A．A?B ，且 A?B B．A?B，但 A?BC．A?B，但 A?B D．A?B，且 A?B2．集合 A={1, 2, 3, 4, 5, 6, 7, 8}上的關系 R={|x+y=10 且 x, y A}，則 R 的性質為（ b ） ．?A．自反的 B．對稱的C．傳遞且對稱的 D．反自反且傳遞的3．如果 R1 和 R2 是 A 上的自反關系，則 R1∪R 2，R 1∩R 2，R 1-R2 中自反關系有（ b ）個．A．0 B．2 C．1 D．34．如圖一所示，以下說法正確的是 ( d ) ．A．{(a, e)}是割邊 B．{(a, e)}是邊割集C．{(a, e) ,( b, c)}是邊割集 D．{(d, e)}是邊割集圖一5．設 A（x）：x 是人，B（ x）：x 是學生，則命題“不是所有人都是學生”可符號化為（ c ） ．A．( x)(A(x)∧B(x)) B．┐( x)(A(x)∧B(x)) ??C．┐(?x)(A(x) →B(x)) D．┐( x)(A(x)∧┐B(x))1．設 A={a, b}，B={1, 2}，R 1，R 2，R 3 是 A 到 B 的二元關系，且 R1={, } ，R 2={, , }，R3={, }，則（ b ）不是從 A 到 B 的函數．A．R 1 和 R2 B．R 2 C．R 3 D．R 1 和 R32．設 A={1, 2, 3, 4, 5, 6, 7, 8}，R 是 A 上的整除關系，B ={2, 4, 6}，則集合 B 的最大元、最小元、上界、下界依次為 ( b )．A．8、2、8、2 B．無、2、無、2C．6、2、6、2 D．8、1、6、13．若集合 A 的元素個數為 10，則其冪集的元素個數為（ a ） ．A．1024 B．10 C．100 D．14．設完全圖 K 有 n 個結點(n≥2)，m 條邊，當（ c ）時，K 中存在歐拉回路．nA．m 為奇數 B．n 為偶數 C．n 為奇數 D． m 為偶數5．已知圖 G 的鄰接矩陣為 .，則 G 有（ d ） ． A．5 點，8 邊 B．6 點，7 邊 C．6 點，8 邊 D．5 點，7 邊1．若集合 A＝{ a，{a} ，{1，2}}，則下列表述正確的是( c )．A．{a，{a}}?A B．{2}?AC．{a} ?A D．?? A2．設圖 G＝ ，v?V，則下列結論成立的是 ( c ) ．A．deg(v)=2 ?E? B． deg(v)=?E? C． D．Vv)deg(??vV???deg3．命題公式（P∨Q）→R 的析取范式是 ( d )A．?（P∨Q ）∨R B． （P∧Q）∨R C． （P∨Q）∨R D． （?P∧?Q）∨R4．如圖一所示，以下說法正確的是 ( a )．A．e 是割點 B．{a, e} 是點割集C．{b, e}是點割集 D．ievbyqtbdd是點割集5．下列等價公式成立的為( b )．A．?P ??Q?P?Q B．P ?(?Q?P) ??P?(P?Q)C．Q?(P ?Q) ??Q?(P?Q) D．?P? (P?Q) ?Q1．若 G 是一個漢密爾頓圖，則 G 一定是( d )．A．平面圖 B．對偶圖C．歐拉圖 D．連通圖2．集合 A={1, 2, 3, 4}上的關系 R={|x=y 且 x, y A}，則 R 的性質為（ c ） ．?A．不是自反的 B．不是對稱的C．傳遞的 D．反自反3．設集合 A={1，2，3，4，5}，偏序關系? 是 A 上的整除關系，則偏序集上的元素 5 是集合 A 的（ b ） ．A．最大元 B．極大元 C．最小元 D．極小元4．圖 G 如圖一所示，以下說法正確的是 ( c ) ．A．{(a, d)}是割邊 B．{(a, d)}是邊割集C．{(a, d) ,(b, d)}是邊割集 D．{(b, d)}是邊割集圖一5．設 A（x）：x 是人，B（x）： x 是工人，則命題“有人是工人”可符號化為（ a ） ．A．( x)(A(x)∧B(x)) B．( x)(A(x)∧B(x))??C．┐(?x)(A(x) →B(x)) D．┐( x)(A(x)∧┐B(x))?1．若集合 A＝{ a，{a}} ，則下列表述正確的是( a )．A．{a}?A B．{{{a}}}?AC．{a ，{a}} ?A D．??A2．命題公式（P∨ Q）的合取范式是 ( c )A． （P∧Q） B． （P∧Q）∨（P∨Q） C． （P∨Q） D．?（?P∧?Q）3．無向樹 T 有 8 個結點，則 T 的邊數為( b )．A．6 B．7 C．8 D．9 4．圖 G 如圖一所示，以下說法正確的是 ( b )．A．a 是割點 B．{b, c} 是點割集C．{b, d} 是點割集 D．{c} 是點割集圖一5．下列公式成立的為( d )．A．?P ∧ ?Q ? P∨Q B．P ??Q ? ?P?QC．Q?P ? P D．?P∧(P∨Q) ?Q1． “小于 5 的非負整數集合”采用描述法表示為___a___．A．{x?x N, x,,,}?B．{>,>,>,>}C．{, >,, >,, >,, >} D．{{1,2},{a,b},{ }}4．設 A={1, 2, 3, 4, 5, 6, 7, 8}，R 是 A 上的整除關系，B={2, 4, 6}，則集合 B 的最大元、最小元、上界、下界依次為___d___．A．8、1、6、1 B． 8、2、8、2C．6、2、6、2 D．無、2、無、25．有 5 個結點的無向完全圖 K5 的邊數為___a___．A．10 B．20 C．5 D．256．設完全圖 K 有 n 個結點(n≥2)，m 條邊，當___b___時，K 中存在歐拉回路．nA．n 為偶數 B．n 為奇數 C．m 為偶數 D．m 為奇數7．一棵無向樹 T 有 5 片樹葉，3 個 2 度分支點，其余的分支點都是 3 度頂點，則 T 有__c___個頂點．A．3 B．8C．11 D．138．命題公式（P∨Q）→R 的析取范式是___b___．A． （?P∧?Q）∨R B． ?（P∨Q）∨RC． （P∧Q） ∨R D． （P∨Q）∨R9．下列等價公式成立的是___b___．A．?P??Q?P ?Q B． P?(?Q?P) ??P?(P?Q)C．?P? (P?Q) ?Q D．Q?(P?Q) ??Q?(P?Q)10．謂詞公式 的類型是__c____．))()xxx??A．蘊涵式 B．永假式 C．永真式 D．非永真的可滿足式二、填空題（每小題 3 分，本題共 15 分）6．命題公式 的真值是　 T （或 1） ?。?(7．若圖 G=中具有一條漢密爾頓回路，則對于結點集 V 的每個非空子集 S，在 G 中刪除 S 中的所有結點得到的連通分支數為 W，則 S 中結點數|S|與 W 滿足的關系式為 W?|S| ．8．給定一個序列集合{000，001，01，10，0} ，若去掉其中的元素 0 ，則該序列集合構成前綴碼．9．已知一棵無向樹 T 中有 8 個結點，4 度，3 度，2 度的分支點各一個，T 的樹葉數為 5 ．.10．(?x)(P( x)→Q(x )∨R(x ，y))中的自由變元為 R(x，y ) 中的 y6．若集合 A 的元素個數為 10，則其冪集的元素個數為　 1024 ．7．設 A={a，b，c}，B={1，2}，作 f：A→B，則不同的函數個數為 8 ．8．若 A={1,2}，R={|x?A, y?A, x+y=10}，則 R 的自反閉包為{,} ． 9．結點數 v 與邊數 e 滿足 e=v-1 關系的無向連通圖就是樹．6．設集合 A＝{a，b}，那么集合 A 的冪集是{ ?,{a,b},{a},{b }}．7．如果 R1 和 R2 是 A 上的自反關系，則 R1∪R 2，R 1∩R 2，R 1-R2 中自反關系有 2 個． 8．設圖 G 是有 6 個結點的連通圖，結點的總度數為 18，則可從 G 中刪去 4 條邊后使之變成樹．9．設連通平面圖 G 的結點數為 5，邊數為 6，則面數為 3 ．10．設個體域 D＝{a, b}，則謂詞公式(?x )A(x)∧（?x ）B（x）消去量詞后的等值式為 (A (a)∧A (b))∧( B（a）∨B（b）) ．6．設集合 A={0, 1, 2, 3}，B={2, 3, 4, 5} ，R 是 A 到 B 的二元關系， },yy?????且且則 R 的有序對集合為{， ，}，．7．設 G 是連通平面圖，v, e , r 分別表示 G 的結點數，邊數和面數，則 v，e 和 r 滿足的關系式 v-e+r=2 ．8．設 G＝是有 6 個結點， 8 條邊的連通圖，則從 G 中刪去 3 條邊，可以確定圖 G 的一棵生成樹．9．無向圖 G 存在歐拉回路，當且僅當 G 連通且所有結點的度數全為偶數10．設個體域 D＝{1,2}，則謂詞公式 消去量詞后的等值式為 A(1)?A(2))(x?6．命題公式 的真值是　 T （或 1） ?。?(PQ??7．若圖 G=中具有一條漢密爾頓回路，則對于結點集 V 的每個非空子集 S，在 G 中刪除 S 中的所有結點得到的連通分支數為 W，則 S 中結點數|S|與 W 滿足的關系式為 W?|S| ．8．給定一個序列集合{000，001，01，10，0} ，若去掉其中的元素 0 ，則該序列集合構成前綴碼．9．已知一棵無向樹 T 中有 8 個結點，4 度，3 度，2 度的分支點各一個，T 的樹葉數為 5 ．10．(?x)(P( x)→Q(x )∨R(x ，y))中的自由變元為 R(x，y ) 中的 y6．若集合 A 的元素個數為 10，則其冪集的元素個數為　 1024 ．7．設 A={a，b，c}，B={1，2}，作 f：A→B，則不同的函數個數為 8 ．8．若 A={1,2}，R={|x?A, y?A, x+y=10}，則 R 的自反閉包為{,} ． 9．結點數 v 與邊數 e 滿足 e=v-1 關系的無向連通圖就是樹．10．設個體域 D＝{a, b, c}，則謂詞公式 (?x)A(x)消去量詞后的等值式為 A (a) ∧A (b) ∧A （c）6．若集合 A={1，3，5，7}，B={2，4，6，8} ，則 A∩B= 空集（或?） ．7．設集合 A={1，2，3}上的函數分別為： f={,,,}，g={,,,}，則復合函數 g?f ={, , ,}8．設 G 是一個圖，結點集合為 V，邊集合為 E，則 G 的結點度數之和為 2|E|（或“邊數的兩倍” ） 9．無向連通圖 G 的結點數為 v，邊數為 e，則 G 當 v 與 e 滿足 e=v-1 關系時是樹． 10．設個體域 D＝{1, 2, 3}， P(x)為“x 小于 2”，則謂詞公式( ?x)P(x) 的真值為假（或 F，或 0） ．6．設集合 A={2, 3, 4}，B={1, 2, 3, 4} ，R 是 A 到 B 的二元關系，},{yyyR?????且且則 R 的有序對集合為{， ，，}， ，}7．如果 R 是非空集合 A 上的等價關系，a ?A，b?A，則可推知 R 中至少包含， 等元素．8．設 G＝是有 4 個結點， 8 條邊的無向連通圖，則從 G 中刪去 5 條邊，可以確定圖 G 的一棵生成樹．9．設 G 是具有 n 個結點 m 條邊 k 個面的連通平面圖，則 m 等于 n+k?210．設個體域 D＝{1, 2}，A(x )為“x 大于 1”，則謂詞公式 的真值為真（或 T，或 1）()x?11．設集合 A={1,2,3}，用列舉法寫出 A 上的恒等關系 IA，全關系 EA：IA = __ IA ={,,}；EA ={,,,,,,,,}12．設集合 A＝{a，b}，那么集合 A 的冪集是{ ?,{a},,{a,b}}13．設集合 A={1,2,3}，B ={a,b}，從 A 到 B 的兩個二元關系 R={,,}， S={,,}，則 R-S=_ R-S={}．14．設 G 是連通平面圖，v, e, r 分別表示 G 的結點數，邊數和面數，則 v，e 和 r 滿足的關系式 v-e+r=2．15．無向連通圖 G 是歐拉圖的充分必要條件是結點度數均為偶數．16．設 G＝是有 6 個結點， 8 條邊的連通圖，則從 G 中刪去 3 條邊，可以確定圖 G 的一棵生成樹．17．設 G 是完全二叉樹，G 有 15 個結點，其中有 8 個是樹葉，則 G 有____14___條邊，G 的總度數是___28_____，G 的分支點數是____7____．18．設 P，Q 的真值為 1，R，S 的真值為 0，則命題公式 的真值為___0_____．QSP??)(19．命題公式 的合取范式為 析取范式為)(??Q??)()(RP?20．設個體域為整數集，公式 真值為___1_____．)(????yx11．設集合 A={1,2,3,4}，B= {3,4,5,6}， 則 ：___{3,4}_____， _____{1,2,3,4,5,6}_____．??A?12．設集合 A 有 n 個元素，那么 A 的冪集合 P(A)的元素個數為 ．13．設集合 A={a,b,c,d}，B={ x,y,z}，R ={,,,,}則關系矩陣 MR＝ ．??????0114．設集合 A={a,b,c,d,e}， A 上的二元關系 R={,,}， S={,,}， 則 R·S={,,}.15．無向圖 G 存在歐拉回路，當且僅當 G 連通且__所有結點的度數全為偶數16．設連通平面圖 G 的結點數為 5，邊數為 6，則面數為 3 ．17．設正則二叉樹有 n 個分支點，且內部通路長度總和為 I，外部通路長度總和為 E，則有 E=___ I+2n18．設 P，Q 的真值為 0，R，S 的真值為 1，則命題公式 的真值為_____1___．)()(SQRP??19．已知命題公式為 G＝(?P?Q) ?R，則命題公式 G 的析取范式是(P ??Q)?R20．謂詞命題公式(?x )(P(x)→ Q(x)∨R(x，y ))中的約束變元為___x___．三、邏輯公式翻譯（每小題 4 分，本題共 12 分）11．將語句“如果所有人今天都去參加活動，則明天的會議取消． ”翻譯成命題公式．設 P：所有人今天都去參加活動，Q：明天的會議取消， （1 分）P? Q． （4 分）12．將語句“今天沒有人來． ” 翻譯成命題公式．設 P：今天有人來， （1 分）? P． （ 4 分）13．將語句“有人去上課． ” 翻譯成謂詞公式．設 P(x)：x 是人，Q(x)：x 去上課， （1 分）(?x)(P(x) ?Q(x))． （4 分）11．將語句“如果你去了，那么他就不去． ”翻譯成命題公式．設 P：你去， Q：他去， （1 分）P??Q． （4 分）12．將語句“小王去旅游，小李也去旅游． ”翻譯成命題公式．設 P：小王去旅游，Q：小李去旅游， （1 分）P?Q． （4 分）13．將語句“所有人都去工作． ”翻譯成謂詞公式．設 P(x)：x 是人，Q(x)：x 去工作， （ 1 分）(?x)(P(x)?Q(x))． （4 分）11．將語句“他不去學校． ”翻譯成命題公式．設 P：他去學校， （1 分）? P． （ 4 分）12．將語句“他去旅游，僅當他有時間． ”翻譯成命題公式．設 P：他去旅游，Q：他有時間， （1 分）P ?Q． （4 分）13．將語句“所有的人都學習努力． ”翻譯成命題公式．設 P(x)：x 是人，Q(x)：x 學習努力， （1 分）（?x）(P(x) ?Q(x))． （3 分）11．將語句“盡管他接受了這個任務，但他沒有完成好． ”翻譯成命題公式．設 P：他接受了這個任務，Q：他完成好了這個任務， （2 分）P?? Q． （6 分）12．將語句“今天沒有下雨． ”翻譯成命題公式．設 P：今天下雨， （2 分）? P． （6 分）11．將語句“他是學生． ”翻譯成命題公式．設 P：他是學生， （2 分）則命題公式為： P． （6 分）12．將語句“如果明天不下雨，我們就去郊游． ”翻譯成命題公式．設 P：明天下雨，Q：我們就去郊游， （2 分）則命題公式為：? P? Q． （6 分）11．將語句“今天考試，明天放假． ”翻譯成命題公式．設 P：今天考試，Q：明天放假． （2 分）則命題公式為：P∧Q． （6 分）12．將語句“我去旅游，僅當我有時間． ”翻譯成命題公式．設 P：我去旅游， Q：我有時間， （2 分）則命題公式為：P? Q． （6 分）⑴ 將語句“如果明天不下雨，我們就去春游． ”翻譯成命題公式．⑵ 將語句“有人去上課． ” 翻譯成謂詞公式．⑴設命題 P 表示“ 明天下雨” ，命題 Q 表示“我們就去春游”.則原語句可以表示成命題公式 P→Q. （5 分）?⑵設 P(x)：x 是人，Q(x)：x 去上課 則原語句可以表示成謂詞公式 (?x)(P(x) ?Q(x))． 四、判斷說明題（每小題 7 分，本題共 14 分）14．┐P∧（P →┐ Q）∨P 為永真式．正確． （3 分）┐P∧ （ P→┐Q） ∨P 是由┐P∧（ P→┐Q）與 P 組成的析取式，如果 P 的值為真，則┐P ∧（P→┐Q）∨P 為真， （5 分）如果 P 的值為假，則┐P 與 P→┐Q 為真，即┐P∧（P →┐Q）為真，也即┐P∧（P →┐ Q）∨P 為真，所以┐P∧（P →┐ Q）∨P 是永真式． （7 分）.15．若偏序集的哈斯圖如圖一所示，則集合 A 的最大元為 a，最小元不存在．正確． （3 分）對于集合 A 的任意元素 x，均有?R（或 xRa） ，所以 a 是集合 A 中的最大元． （5 分）14．如果 R1 和 R2 是 A 上的自反關系，則 R1∪R2 是自反的．正確． （3 分）R1 和 R2 是自反的，?x ?A， ? R1 ， ?R2 ， 則 ? R1?R2， 所以 R1∪R2 是自反的． （7 分）15．如圖二所示的圖 G 存在一條歐拉回路．正確． （3 分）因為圖 G 為連通的，且其中每個頂點的度數為偶數． （7 分）14．設 N、R 分別為自然數集與實數集， f：N→R，f (x)=x+6，則 f 是單射．正確． （3 分）設 x1，x2 為自然數且 x1?x2，則有 f(x1)= x1+6? x2+6= f(x2)，故 f 為單射． （7 分）15．設 G 是一個有 6 個結點 14 條邊的連通圖，則 G 為平面圖．錯誤． （3 分）不滿足“設 G 是一個有 v 個結點 e 條邊的連通簡單平面圖，若 v≥3，則 e≤3v-6． ” 13．下面的推理是否正確，試予以說明．(1) （? x）F（x）→G（ x） 前提引入(2) F（y）→G（y） US（1） ．錯誤． （3 分）（2）應為 F（y） →G（x） ，換名時，約束變元與自由變元不能混淆． （7 分）14．若偏序集的哈斯圖如圖二所示，則集合 A 的最大元為 a，最小元不存在．錯誤． （3 分）集合 A 的最大元不存在，a 是極大元． （7 分）13．下面的推理是否正確，試予以說明．(1) （? x）F（x）→G（ x） 前提引入(2) F（y）→G（y） US（1） ．錯誤． （3 分）（2）應為 F（y） →G（x） ，換名時，約束變元與自由變元不能混淆． （7 分）14．如圖二所示的圖 G 存在一條歐拉回路．錯誤． （3 分）因為圖 G 為中包含度數為奇數的結點． （7 分）13．如果圖 G 是無向圖，且其結點度數均為偶數，則圖 G 是歐拉圖．錯誤． （3 分）當圖 G 不連通時圖 G 不為歐拉圖． （7 分）14．若偏序集的哈斯圖如圖二所示，則集合 A 的最大元為 a，最小元是 f．圖二錯誤． （3 分）v1v2 v3v5 v4dbacefgh n圖二.集合 A 的最大元與最小元不存在，a 是極大元，f 是極小元， ． 五．計算題（每小題 12 分，本題共 36 分）16．設集合 A={1，2，3，4}，R={|x, y?A；|x? y|=1 或 x?y=0}，試（1）寫出 R 的有序對表示；（2）畫出 R 的關系圖；（3）說明 R 滿足自反性，不滿足傳遞性．（1）R={,,,,,,,,,} （3 分）（2）關系圖為（6 分）（3）因為,,, 均屬于 R，即 A 的每個元素構成的有序對均在 R 中，故 R 在 A 上是自反的。 （9 分）因有與屬于 R，但不屬于 R，所以 R 在 A 上不是傳遞的。 17．求 P?Q?R 的析取范式，合取范式、主析取范式，主合取范式．P→（ R∨Q）?┐P∨(R∨Q)? ┐P∨Q∨R （析取、合取、主合取范式） （9 分）?(┐P∧┐ Q∧┐R)∨(┐P∧┐Q∧R) ∨(┐P∧Q∧R) ∨(P ∧┐Q∧┐R) ∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) （主析取范式） （12 分）18．設圖 G=，V={ v1，v2，v3，v4，v5} ，E={ (v1, v2)，(v1, v3)，(v2, v3) ，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，試畫出 G 的圖形表示；寫出其鄰接矩陣；(3) 求出每個結點的度數；(4) 畫出圖 G 的補圖的圖形．（1）關系圖 （3 分）（2）鄰接矩陣（6 分）??????010（3）deg( v1)=2deg(v2)=3deg(v3)=4deg(v4)=3deg(v5)=2 （9 分）（4）補圖16．設謂詞公式 ，試)(),(),(),( yFzyRzxQyxP?????（1）寫出量詞的轄域； （2）指出該公式的自由變元和約束變元．（1）?x 量詞的轄域為 ， （2 分）,,?z 量詞的轄域為 , （4 分）)(z?y 量詞的轄域為 ． （6 分）yR（2）自由變元為 與 中的 y，以及 中的 z),(zxyx(),(????12 34v1v2v3 v4v5? ????v1v2v3 v4v5? ????.約束變元為 x 與 中的 z，以及 中的 y． （12 分）),(yQ),(zR17．設 A={{1},{2},1,2}，B={1,2,{1,2}}，試計算（1）（A?B）； （2）（A∩B）； （3）A×B．（1）A?B ={{1},{2}} （4 分）（2）A∩B ={1,2} （8 分）（3）A×B={，，，，，，，，，，,} 18．設 G=，V={ v1，v2，v3，v4，v5} ，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) ，(v3,v5)，(v4,v5) }，試（1）給出 G 的圖形表示； （2）寫出其鄰接矩陣；（3）求出每個結點的度數； （4）畫出其補圖的圖形．1）G 的圖形表示為：（3 分）（2）鄰接矩陣：（6 分）??????010（3）v1，v2，v3，v4，v5 結點的度數依次為 1，2，4，3，2 （9 分）（4）補圖如下：16．試求出（P∨ Q）→R 的析取范式，合取范式，主合取范式．（P∨ Q） →R?┐(P∨Q)∨R? (┐P∧┐Q)∨R（析取范式） （3 分）? (┐P∨R)∧ (┐Q∨R)（合取范式） （6 分）? ((┐P∨R)∨(Q∧┐Q))∧ ((┐Q∨R)∨(P∧┐P))? (┐P∨R∨Q) ∧(┐P∨R ∨┐Q) ∧ (┐Q∨R∨P)∧(┐Q∨R∨┐P)? (┐P∨Q∨R)∧(┐P∨┐Q∨R)∧ (P∨┐Q∨R) （主合取范式） （12 分）17．設 A={{a, b}, 1, 2}，B={ a, b, {1}, 1}，試計算（1） （A?B ） （2） （A∪B） （3） （A∪B ）?（A∩B） ．（1） （A?B ）={{a, b}, 2} （4 分）（2） （A∪B）={{a, b}, 1, 2, a, b, {1}} （8 分）（3） （A∪B）? （A∩B）={{a, b}, 2, a, b, {1}} （12 分）18．圖 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）鄰接矩陣：??????0110.（3）粗線表示最小的生成樹， （10 分）權為 7： （12 分）15．求（P∨Q） →（R ∨Q）的合取范式．（P∨ Q） →（R∨ Q）??（P∨ Q）∨（R∨Q） （4 分）?(?P∧ ?Q)∨（R∨Q）?(?P∨ R∨Q) ∧(?Q∨R∨Q)?(?P∨ R∨Q) ∧ R 合取范式 （12 分）16．設 A={0，1， 2，3，4}，R={|x?A，y?A 且 x+y|x ?A，y?A 且 x+y?3}，試求 R，S，R? S，R-1，S-1，r(R) ．R=?, （2 分）S={,,,,,,,,,} （4 分）R?S=?， （6 分）R-1=?， （8 分）S-1= S， （10 分）r(R)=IA． （12 分）17．畫一棵帶權為 1, 2, 2, 3, 4 的最優(yōu)二叉樹,計算它們的權．（10 分）權為 1?3+2?3+2?2+3?2+4?2=27 （12 分）15．求（P∨Q） →R 的析取范式與合取范式．（P∨ Q） →R ? ?（P∨Q）∨R （4 分）? (?P∧?Q)∨R （析取范式） （8 分）? (?P∨R) ∧(?Q∨R) （合取范式） （12 分）16．設 A={0，1， 2，3}，R={|x?A，y?A 且 x+y|x ?A，y?A 且 x+y?2}，試求 R，S，R? S，S -1，r(R)．R=?, S={,,,,,} （3 分）R?S=?， （6 分）S -1= S， （9 分）r(R)=IA={,,,}． （12 分）17．畫一棵帶權為 1, 2, 2, 3, 4 的最優(yōu)二叉樹,計算它們的權．最優(yōu)二叉樹如圖三所示（10 分）圖三權為 1?3+2?3+2?2+3?2+4?2=27 （12 分）15．設謂詞公式 ，試),(),()zxyByxA???（1）寫出量詞的轄域； （2）指出該公式的自由變元和約束變元．（1）?x 量詞的轄域為 ， （3 分）,,?z 量詞的轄域為 , （6 分）)(zxyB（2）自由變元為 中的 y， （9 分）),(zxBA?約束變元為 x 與 z． （12 分）16．設集合 A={{1},1,2}，B={1,{1,2}}，試計算（1） （A?B ） ； （2） （A∩B） ； （3）A×B ．（1）A?B ={{1},2} （4 分）（2）A∩B ={1} （8 分）（3）A×B={，，，，，} （12 分）17．設 G=，V={ v1，v2，v3，v4 }，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) }，試（1）給出 G 的圖形表示； （2）寫出其鄰接矩陣；（3）求出每個結點的度數； （4）畫出其補圖的圖形．?? ??（10分）權為1?3+2?3+2?2+3?2+4?2=27 （12分）???? ?1 22 3347 512?? ?? ? ??? ?1 22 3347 512.（1）G 的圖形表示為(如圖三)：（3 分） （2）鄰接矩陣：（6 分）??????01（3）v1，v2，v3，v4 結點的度數依次為 1，2，3，2 （9 分）（4）補圖如圖四所示：21．化簡下列集合表示式：)()()()( CBACBA???????= ~~~A?= ?= 設 E 為全集E= )()(= = = A22．設 ， ，求 ， ，并畫出其圖像．},21|{Rxx???},0|{RyB???BA?⑴ =B?,|y?= | x??的圖像如下圖 1 所示的陰影部分．圖 1 圖 2⑵ =AB?},1|{},0|{RxxRy?????= ,02| yx???的圖像如上圖 2 所示的陰影部分．23．設 G=，V={ v1，v2，v3，v4，v5} ，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) ，(v3,v5)，(v4,v5) }，試：⑴ 給出 G 的圖形表示； ⑵ 畫出其補圖的圖形． ．⑴ G 的圖形表示見圖 3；⑵ G 的補圖的圖形，見圖 4.圖 3 圖 424．構 造 權 為 2， 3， 4， 4， 5， 5， 7 的 最 優(yōu) 樹 。最優(yōu)樹如下圖 5 所示．21．設 A，B 和 C 是全集 E 的子集，化簡下列集合表示式：)(~)()( CBA???~??= )(~CBA??= = )()(= (= 22．設 A＝{ 1,2,3}，用列舉法給出 A 上的恒等關系 IA，全關系 EA，A 上的小于關系}yxyxL??????及其逆關系和關系矩陣.（2 分）,,,AI}3,,1,3,2,1,, ?????E（2 分）（2 分）321,2{LA 的逆關系 （2 分）},,,?????A. （2 分）??????0AM???????011ALM23．圖 G=，其圖形如右圖 1 所示。⑴ 寫出 G 的鄰接矩陣；⑵ 畫出 G 的權最小的生成樹以及計算出其權值．⑴ G 的鄰接矩陣為： （4 分）??????0101⑵ G 的權最小的生成樹如右上圖 1 所示． （4 分）最小的生成樹的權為：1+1+5+2+3=12． （2 分）六、證明題（本題共 8 分）19．試證明（?x） （P（x）∧R（x） ）? （? x）P（x）∧（? x）R（x） ．證明： （1） （?x） （P（x）∧R（x ） ） P（2）P（a）∧R（a） ES(1) （2 分）（3）P（a） T(2)I 圖 1.（4） （?x）P（x） EG(3) （4 分）（5）R（a） T(2)I（6） （?x）R（x） EG(5) （6 分）（7） （?x）P（x）∧（? x）R（ x） T(5)(6)I （2 分）19．試證明集合等式 A? (B?C)=(A?B) ? (A?C) ．證明：設 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． （4 分）反之，若 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． 19．試證明集合等式 A? (B?C)=(A?B) ? (A?C)．證明：設 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． （4 分）反之，若 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．18．設 G 是一個 n 階無向簡單圖，n 是大于等于 2 的奇數．證明 G 與 中的奇數度頂點個數相等( 是 G 的補圖) ．證明：因為 n 是奇數，所以 n 階完全圖每個頂點度數為偶數， （3 分）因此，若 G 中頂點 v 的度數為奇數，則在 中 v 的度數一定也是奇數， （6 分）所以 G 與 中的奇數度頂點個數相等． （8 分）18．試證明集合等式 A? (B?C)=(A?B) ? (A?C) ．證明：設 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． （4 分）反之，若 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． 18．設 A，B 是任意集合，試證明：若 A?A=B?B，則 A=B．證明：設 x?A，則 ?A?A， （1 分）因為 A?A=B?B，故 ?B?B，則有 x?B， （3 分）所以 A?B． （5 分）設 x?B，則?B?B，