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

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