2018年年電大離散數(shù)學(xué)(本科)考試試題及答案參考資料小抄

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

.中央電大離散數(shù)學(xué)（本科）考試試題一、單項(xiàng)選擇題（每小題 3 分，本題共 15 分）1若集合 A=1， 2，B=1，2，1 ，2，則下列表述正確的是( a )AAB，且 AB BB A，且 ABCAB，且 AB DAB ，且 AB2設(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 )A6 B5 C4 D34無(wú)向簡(jiǎn)單圖 G 是棵樹(shù)，當(dāng)且僅當(dāng)( a )AG 連通且邊數(shù)比結(jié)點(diǎn)數(shù)少 1 BG 連通且結(jié)點(diǎn)數(shù)比邊數(shù)少 1CG 的邊數(shù)比結(jié)點(diǎn)數(shù)少 1 DG 中沒(méi)有回路5下列公式 ( c )為重言式AP QPQ B(Q (PQ) (Q(PQ)C(P (QP)(P(PQ) D( P(PQ) Q1若集合 A=a，b，B= a，b， a，b ，則（ a ） AAB ，且 AB BAB，但 ABCAB，但 AB DAB，且 AB2集合 A=1, 2, 3, 4, 5, 6, 7, 8上的關(guān)系 R=|x+y=10 且 x, y A，則 R 的性質(zhì)為（ b ） A自反的 B對(duì)稱(chēng)的C傳遞且對(duì)稱(chēng)的 D反自反且傳遞的3如果 R1 和 R2 是 A 上的自反關(guān)系，則 R1R 2，R 1R 2，R 1-R2 中自反關(guān)系有（ b ）個(gè)A0 B2 C1 D34如圖一所示，以下說(shuō)法正確的是 ( 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é)生”可符號(hào)化為（ 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ù)AR 1 和 R2 BR 2 CR 3 DR 1 和 R32設(shè) A=1, 2, 3, 4, 5, 6, 7, 8，R 是 A 上的整除關(guān)系，B =2, 4, 6，則集合 B 的最大元、最小元、上界、下界依次為 ( b )A8、2、8、2 B無(wú)、2、無(wú)、2C6、2、6、2 D8、1、6、13若集合 A 的元素個(gè)數(shù)為 10，則其冪集的元素個(gè)數(shù)為（ a ） A1024 B10 C100 D14設(shè)完全圖 K 有 n 個(gè)結(jié)點(diǎn)(n2)，m 條邊，當(dāng)（ c ）時(shí)，K 中存在歐拉回路nAm 為奇數(shù) Bn 為偶數(shù) Cn 為奇數(shù) D m 為偶數(shù)5已知圖 G 的鄰接矩陣為 .，則 G 有（ d ） A5 點(diǎn)，8 邊 B6 點(diǎn)，7 邊 C6 點(diǎn)，8 邊 D5 點(diǎn)，7 邊1若集合 A a，a ，1，2，則下列表述正確的是( c )Aa，aA B2ACa A D A2設(shè)圖 G ，vV，則下列結(jié)論成立的是 ( c ) Adeg(v)=2 E B deg(v)=E C DVv)deg(vVdeg3命題公式（PQ）R 的析取范式是 ( d )A（PQ ）R B （PQ）R C （PQ）R D （PQ）R4如圖一所示，以下說(shuō)法正確的是 ( a )Ae 是割點(diǎn) Ba, e 是點(diǎn)割集Cb, e是點(diǎn)割集 Dd是點(diǎn)割集5下列等價(jià)公式成立的為( b )AP QPQ BP (QP) P(PQ)CQ(P Q) Q(PQ) DP (PQ) Q1若 G 是一個(gè)漢密爾頓圖，則 G 一定是( d )A平面圖 B對(duì)偶圖C歐拉圖 D連通圖2集合 A=1, 2, 3, 4上的關(guān)系 R=|x=y 且 x, y A，則 R 的性質(zhì)為（ c ） A不是自反的 B不是對(duì)稱(chēng)的C傳遞的 D反自反3設(shè)集合 A=1，2，3，4，5，偏序關(guān)系 是 A 上的整除關(guān)系，則偏序集上的元素 5 是集合 A 的（ b ） A最大元 B極大元 C最小元 D極小元4圖 G 如圖一所示，以下說(shuō)法正確的是 ( c ) A(a, d)是割邊 B(a, d)是邊割集C(a, d) ,(b, d)是邊割集 D(b, d)是邊割集圖一5設(shè) A（x）：x 是人，B（x）： x 是工人，則命題“有人是工人”可符號(hào)化為（ 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 )AaA BaACa ，a A DA2命題公式（P Q）的合取范式是 ( c )A （PQ） B （PQ）（PQ） C （PQ） D（PQ）3無(wú)向樹(shù) T 有 8 個(gè)結(jié)點(diǎn)，則 T 的邊數(shù)為( b )A6 B7 C8 D9 4圖 G 如圖一所示，以下說(shuō)法正確的是 ( b )Aa 是割點(diǎn) Bb, c 是點(diǎn)割集Cb, d 是點(diǎn)割集 Dc 是點(diǎn)割集圖一5下列公式成立的為( d )AP Q PQ BP Q PQCQP P DP(PQ) Q1 “小于 5 的非負(fù)整數(shù)集合”采用描述法表示為_(kāi)a_Axx N, x,B,C, , , , D1,2,a,b, 4設(shè) A=1, 2, 3, 4, 5, 6, 7, 8，R 是 A 上的整除關(guān)系，B=2, 4, 6，則集合 B 的最大元、最小元、上界、下界依次為_(kāi)d_A8、1、6、1 B 8、2、8、2C6、2、6、2 D無(wú)、2、無(wú)、25有 5 個(gè)結(jié)點(diǎn)的無(wú)向完全圖 K5 的邊數(shù)為_(kāi)a_A10 B20 C5 D256設(shè)完全圖 K 有 n 個(gè)結(jié)點(diǎn)(n2)，m 條邊，當(dāng)_b_時(shí)，K 中存在歐拉回路nAn 為偶數(shù) Bn 為奇數(shù) Cm 為偶數(shù) Dm 為奇數(shù)7一棵無(wú)向樹(shù) T 有 5 片樹(shù)葉，3 個(gè) 2 度分支點(diǎn)，其余的分支點(diǎn)都是 3 度頂點(diǎn)，則 T 有_c_個(gè)頂點(diǎn)A3 B8C11 D138命題公式（PQ）R 的析取范式是_b_A （PQ）R B （PQ）RC （PQ） R D （PQ）R9下列等價(jià)公式成立的是_b_APQP Q B P(QP) P(PQ)CP (PQ) Q DQ(PQ) Q(PQ)10謂詞公式 的類(lèi)型是_c_)()xxxA蘊(yùn)涵式 B永假式 C永真式 D非永真的可滿足式二、填空題（每小題 3 分，本題共 15 分）6命題公式 的真值是 T （或 1） )(7若圖 G=中具有一條漢密爾頓回路，則對(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| 8給定一個(gè)序列集合000，001，01，10，0 ，若去掉其中的元素 0 ，則該序列集合構(gòu)成前綴碼9已知一棵無(wú)向樹(shù) T 中有 8 個(gè)結(jié)點(diǎn)，4 度，3 度，2 度的分支點(diǎn)各一個(gè)，T 的樹(shù)葉數(shù)為 5 .10(x)(P( x)Q(x )R(x ，y)中的自由變?cè)獮?R(x，y ) 中的 y6若集合 A 的元素個(gè)數(shù)為 10，則其冪集的元素個(gè)數(shù)為 1024 7設(shè) A=a，b，c，B=1，2，作 f：AB，則不同的函數(shù)個(gè)數(shù)為 8 8若 A=1,2，R=|xA, yA, x+y=10，則 R 的自反閉包為, 9結(jié)點(diǎn)數(shù) v 與邊數(shù) e 滿足 e=v-1 關(guān)系的無(wú)向連通圖就是樹(shù)6設(shè)集合 Aa，b，那么集合 A 的冪集是 ,a,b,a,b 7如果 R1 和 R2 是 A 上的自反關(guān)系，則 R1R 2，R 1R 2，R 1-R2 中自反關(guān)系有 2 個(gè) 8設(shè)圖 G 是有 6 個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為 18，則可從 G 中刪去 4 條邊后使之變成樹(shù)9設(shè)連通平面圖 G 的結(jié)點(diǎn)數(shù)為 5，邊數(shù)為 6，則面數(shù)為 3 10設(shè)個(gè)體域 Da, 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é)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則 v，e 和 r 滿足的關(guān)系式 v-e+r=2 8設(shè) G是有 6 個(gè)結(jié)點(diǎn)， 8 條邊的連通圖，則從 G 中刪去 3 條邊，可以確定圖 G 的一棵生成樹(shù)9無(wú)向圖 G 存在歐拉回路，當(dāng)且僅當(dāng) G 連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)10設(shè)個(gè)體域 D1,2，則謂詞公式 消去量詞后的等值式為 A(1)A(2)(x6命題公式 的真值是 T （或 1） )(PQ7若圖 G=中具有一條漢密爾頓回路，則對(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| 8給定一個(gè)序列集合000，001，01，10，0 ，若去掉其中的元素 0 ，則該序列集合構(gòu)成前綴碼9已知一棵無(wú)向樹(shù) T 中有 8 個(gè)結(jié)點(diǎn)，4 度，3 度，2 度的分支點(diǎn)各一個(gè)，T 的樹(shù)葉數(shù)為 5 10(x)(P( x)Q(x )R(x ，y)中的自由變?cè)獮?R(x，y ) 中的 y6若集合 A 的元素個(gè)數(shù)為 10，則其冪集的元素個(gè)數(shù)為 1024 7設(shè) A=a，b，c，B=1，2，作 f：AB，則不同的函數(shù)個(gè)數(shù)為 8 8若 A=1,2，R=|xA, yA, x+y=10，則 R 的自反閉包為, 9結(jié)點(diǎn)數(shù) v 與邊數(shù) e 滿足 e=v-1 關(guān)系的無(wú)向連通圖就是樹(shù)10設(shè)個(gè)體域 Da, b, c，則謂詞公式 (x)A(x)消去量詞后的等值式為 A (a) A (b) A （c）6若集合 A=1，3，5，7，B=2，4，6，8 ，則 AB= 空集（或） 7設(shè)集合 A=1，2，3上的函數(shù)分別為： f=,，g=,，則復(fù)合函數(shù) gf =, , ,8設(shè) G 是一個(gè)圖，結(jié)點(diǎn)集合為 V，邊集合為 E，則 G 的結(jié)點(diǎn)度數(shù)之和為 2|E|（或“邊數(shù)的兩倍” ） 9無(wú)向連通圖 G 的結(jié)點(diǎn)數(shù)為 v，邊數(shù)為 e，則 G 當(dāng) v 與 e 滿足 e=v-1 關(guān)系時(shí)是樹(shù) 10設(shè)個(gè)體域 D1, 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 上的等價(jià)關(guān)系，a A，bA，則可推知 R 中至少包含， 等元素8設(shè) G是有 4 個(gè)結(jié)點(diǎn)， 8 條邊的無(wú)向連通圖，則從 G 中刪去 5 條邊，可以確定圖 G 的一棵生成樹(shù)9設(shè) G 是具有 n 個(gè)結(jié)點(diǎn) m 條邊 k 個(gè)面的連通平面圖，則 m 等于 n+k210設(shè)個(gè)體域 D1, 2，A(x )為“x 大于 1”，則謂詞公式 的真值為真（或 T，或 1）()x11設(shè)集合 A=1,2,3，用列舉法寫(xiě)出 A 上的恒等關(guān)系 IA，全關(guān)系 EA：IA = _ IA =,；EA =,12設(shè)集合 Aa，b，那么集合 A 的冪集是 ,a,b,a,b13設(shè)集合 A=1,2,3，B =a,b，從 A 到 B 的兩個(gè)二元關(guān)系 R=,， S=,，則 R-S=_ R-S=14設(shè) G 是連通平面圖，v, e, r 分別表示 G 的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則 v，e 和 r 滿足的關(guān)系式 v-e+r=215無(wú)向連通圖 G 是歐拉圖的充分必要條件是結(jié)點(diǎn)度數(shù)均為偶數(shù)16設(shè) G是有 6 個(gè)結(jié)點(diǎn)， 8 條邊的連通圖，則從 G 中刪去 3 條邊，可以確定圖 G 的一棵生成樹(shù)17設(shè) G 是完全二叉樹(shù)，G 有 15 個(gè)結(jié)點(diǎn)，其中有 8 個(gè)是樹(shù)葉，則 G 有_14_條邊，G 的總度數(shù)是_28_，G 的分支點(diǎn)數(shù)是_7_18設(shè) P，Q 的真值為 1，R，S 的真值為 0，則命題公式 的真值為_(kāi)0_QSP)(19命題公式 的合取范式為 析取范式為)(Q)()(RP20設(shè)個(gè)體域?yàn)檎麛?shù)集，公式 真值為_(kāi)1_)(yx11設(shè)集合 A=1,2,3,4，B= 3,4,5,6， 則 ：_3,4_， _1,2,3,4,5,6_A12設(shè)集合 A 有 n 個(gè)元素，那么 A 的冪集合 P(A)的元素個(gè)數(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=,， 則 RS=,.15無(wú)向圖 G 存在歐拉回路，當(dāng)且僅當(dāng) G 連通且_所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)16設(shè)連通平面圖 G 的結(jié)點(diǎn)數(shù)為 5，邊數(shù)為 6，則面數(shù)為 3 17設(shè)正則二叉樹(shù)有 n 個(gè)分支點(diǎn)，且內(nèi)部通路長(zhǎng)度總和為 I，外部通路長(zhǎng)度總和為 E，則有 E=_ I+2n18設(shè) P，Q 的真值為 0，R，S 的真值為 1，則命題公式 的真值為_(kāi)1_)()(SQRP19已知命題公式為 G(PQ) R，則命題公式 G 的析取范式是(P Q)R20謂詞命題公式(x )(P(x) Q(x)R(x，y )中的約束變?cè)獮開(kāi)x_三、邏輯公式翻譯（每小題 4 分，本題共 12 分）11將語(yǔ)句“如果所有人今天都去參加活動(dòng)，則明天的會(huì)議取消 ”翻譯成命題公式設(shè) P：所有人今天都去參加活動(dòng)，Q：明天的會(huì)議取消， （1 分）P Q （4 分）12將語(yǔ)句“今天沒(méi)有人來(lái) ” 翻譯成命題公式設(shè) P：今天有人來(lái)， （1 分） P （ 4 分）13將語(yǔ)句“有人去上課 ” 翻譯成謂詞公式設(shè) P(x)：x 是人，Q(x)：x 去上課， （1 分）(x)(P(x) Q(x) （4 分）11將語(yǔ)句“如果你去了，那么他就不去 ”翻譯成命題公式設(shè) P：你去， Q：他去， （1 分）PQ （4 分）12將語(yǔ)句“小王去旅游，小李也去旅游 ”翻譯成命題公式設(shè) P：小王去旅游，Q：小李去旅游， （1 分）PQ （4 分）13將語(yǔ)句“所有人都去工作 ”翻譯成謂詞公式設(shè) P(x)：x 是人，Q(x)：x 去工作， （ 1 分）(x)(P(x)Q(x) （4 分）11將語(yǔ)句“他不去學(xué)校 ”翻譯成命題公式設(shè) P：他去學(xué)校， （1 分） P （ 4 分）12將語(yǔ)句“他去旅游，僅當(dāng)他有時(shí)間 ”翻譯成命題公式設(shè) P：他去旅游，Q：他有時(shí)間， （1 分）P Q （4 分）13將語(yǔ)句“所有的人都學(xué)習(xí)努力 ”翻譯成命題公式設(shè) P(x)：x 是人，Q(x)：x 學(xué)習(xí)努力， （1 分）（x）(P(x) Q(x) （3 分）11將語(yǔ)句“盡管他接受了這個(gè)任務(wù)，但他沒(méi)有完成好 ”翻譯成命題公式設(shè) P：他接受了這個(gè)任務(wù)，Q：他完成好了這個(gè)任務(wù)， （2 分）P Q （6 分）12將語(yǔ)句“今天沒(méi)有下雨 ”翻譯成命題公式設(shè) P：今天下雨， （2 分） P （6 分）11將語(yǔ)句“他是學(xué)生 ”翻譯成命題公式設(shè) P：他是學(xué)生， （2 分）則命題公式為： P （6 分）12將語(yǔ)句“如果明天不下雨，我們就去郊游 ”翻譯成命題公式設(shè) P：明天下雨，Q：我們就去郊游， （2 分）則命題公式為： P Q （6 分）11將語(yǔ)句“今天考試，明天放假 ”翻譯成命題公式設(shè) P：今天考試，Q：明天放假 （2 分）則命題公式為：PQ （6 分）12將語(yǔ)句“我去旅游，僅當(dāng)我有時(shí)間 ”翻譯成命題公式設(shè) P：我去旅游， Q：我有時(shí)間， （2 分）則命題公式為：P Q （6 分） 將語(yǔ)句“如果明天不下雨，我們就去春游 ”翻譯成命題公式 將語(yǔ)句“有人去上課 ” 翻譯成謂詞公式設(shè)命題 P 表示“ 明天下雨” ，命題 Q 表示“我們就去春游”.則原語(yǔ)句可以表示成命題公式 PQ. （5 分）設(shè) P(x)：x 是人，Q(x)：x 去上課 則原語(yǔ)句可以表示成謂詞公式 (x)(P(x) Q(x) 四、判斷說(shuō)明題（每小題 7 分，本題共 14 分）14P（P Q）P 為永真式正確 （3 分）P （ PQ） P 是由P（ PQ）與 P 組成的析取式，如果 P 的值為真，則P （PQ）P 為真， （5 分）如果 P 的值為假，則P 與 PQ 為真，即P（P Q）為真，也即P（P Q）P 為真，所以P（P Q）P 是永真式 （7 分）.15若偏序集的哈斯圖如圖一所示，則集合 A 的最大元為 a，最小元不存在正確 （3 分）對(duì)于集合 A 的任意元素 x，均有R（或 xRa） ，所以 a 是集合 A 中的最大元 （5 分）14如果 R1 和 R2 是 A 上的自反關(guān)系，則 R1R2 是自反的正確 （3 分）R1 和 R2 是自反的，x A， R1 ， R2 ， 則 R1R2， 所以 R1R2 是自反的 （7 分）15如圖二所示的圖 G 存在一條歐拉回路正確 （3 分）因?yàn)閳D G 為連通的，且其中每個(gè)頂點(diǎn)的度數(shù)為偶數(shù) （7 分）14設(shè) N、R 分別為自然數(shù)集與實(shí)數(shù)集， f：NR，f (x)=x+6，則 f 是單射正確 （3 分）設(shè) x1，x2 為自然數(shù)且 x1x2，則有 f(x1)= x1+6 x2+6= f(x2)，故 f 為單射 （7 分）15設(shè) G 是一個(gè)有 6 個(gè)結(jié)點(diǎn) 14 條邊的連通圖，則 G 為平面圖錯(cuò)誤 （3 分）不滿足“設(shè) G 是一個(gè)有 v 個(gè)結(jié)點(diǎn) e 條邊的連通簡(jiǎn)單平面圖，若 v3，則 e3v-6 ” 13下面的推理是否正確，試予以說(shuō)明(1) （ x）F（x）G（ x） 前提引入(2) F（y）G（y） US（1） 錯(cuò)誤 （3 分）（2）應(yīng)為 F（y） G（x） ，換名時(shí)，約束變?cè)c自由變?cè)荒芑煜?（7 分）14若偏序集的哈斯圖如圖二所示，則集合 A 的最大元為 a，最小元不存在錯(cuò)誤 （3 分）集合 A 的最大元不存在，a 是極大元 （7 分）13下面的推理是否正確，試予以說(shuō)明(1) （ x）F（x）G（ x） 前提引入(2) F（y）G（y） US（1） 錯(cuò)誤 （3 分）（2）應(yīng)為 F（y） G（x） ，換名時(shí)，約束變?cè)c自由變?cè)荒芑煜?（7 分）14如圖二所示的圖 G 存在一條歐拉回路錯(cuò)誤 （3 分）因?yàn)閳D G 為中包含度數(shù)為奇數(shù)的結(jié)點(diǎn) （7 分）13如果圖 G 是無(wú)向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖 G 是歐拉圖錯(cuò)誤 （3 分）當(dāng)圖 G 不連通時(shí)圖 G 不為歐拉圖 （7 分）14若偏序集的哈斯圖如圖二所示，則集合 A 的最大元為 a，最小元是 f圖二錯(cuò)誤 （3 分）v1v2 v3v5 v4dbacefgh n圖二.集合 A 的最大元與最小元不存在，a 是極大元，f 是極小元， 五計(jì)算題（每小題 12 分，本題共 36 分）16設(shè)集合 A=1，2，3，4，R=|x, yA；|x y|=1 或 xy=0，試（1）寫(xiě)出 R 的有序?qū)Ρ硎荆唬?）畫(huà)出 R 的關(guān)系圖；（3）說(shuō)明 R 滿足自反性，不滿足傳遞性（1）R=, （3 分）（2）關(guān)系圖為（6 分）（3）因?yàn)? 均屬于 R，即 A 的每個(gè)元素構(gòu)成的有序?qū)?R 中，故 R 在 A 上是自反的。 （9 分）因有與屬于 R，但不屬于 R，所以 R 在 A 上不是傳遞的。 17求 PQR 的析取范式，合取范式、主析取范式，主合取范式P（ RQ）P(RQ) PQR （析取、合取、主合取范式） （9 分）(P QR)(PQR) (PQR) (P QR) (PQR) (PQR) (PQR) （主析取范式） （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) ，試畫(huà)出 G 的圖形表示；寫(xiě)出其鄰接矩陣；(3) 求出每個(gè)結(jié)點(diǎn)的度數(shù)；(4) 畫(huà)出圖 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）寫(xiě)出量詞的轄域； （2）指出該公式的自由變?cè)图s束變?cè)?）x 量詞的轄域?yàn)?， （2 分）,z 量詞的轄域?yàn)?, （4 分）)(zy 量詞的轄域?yàn)?（6 分）yR（2）自由變?cè)獮?與 中的 y，以及 中的 z),(zxyx(),(12 34v1v2v3 v4v5 v1v2v3 v4v5 .約束變?cè)獮?x 與 中的 z，以及 中的 y （12 分）),(yQ),(zR17設(shè) A=1,2,1,2，B=1,2,1,2，試計(jì)算（1）（AB）； （2）（AB）； （3）AB（1）AB =1,2 （4 分）（2）AB =1,2 （8 分）（3）AB=，, 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）寫(xiě)出其鄰接矩陣；（3）求出每個(gè)結(jié)點(diǎn)的度數(shù)； （4）畫(huà)出其補(bǔ)圖的圖形1）G 的圖形表示為：（3 分）（2）鄰接矩陣：（6 分）010（3）v1，v2，v3，v4，v5 結(jié)點(diǎn)的度數(shù)依次為 1，2，4，3，2 （9 分）（4）補(bǔ)圖如下：16試求出（P Q）R 的析取范式，合取范式，主合取范式（P Q） R(PQ)R (PQ)R（析取范式） （3 分） (PR) (QR)（合取范式） （6 分） (PR)(QQ) (QR)(PP) (PRQ) (PR Q) (QRP)(QRP) (PQR)(PQR) (PQR) （主合取范式） （12 分）17設(shè) A=a, b, 1, 2，B= a, b, 1, 1，試計(jì)算（1） （AB ） （2） （AB） （3） （AB ）（AB） （1） （AB ）=a, b, 2 （4 分）（2） （AB）=a, b, 1, 2, a, b, 1 （8 分）（3） （AB） （AB）=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) ，對(duì)應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4 及 5，試（1）畫(huà)出 G 的圖形； （2）寫(xiě)出 G 的鄰接矩陣；（3）求出 G 權(quán)最小的生成樹(shù)及其權(quán)值（1）G 的圖形表示為： （3 分）（2）鄰接矩陣：0110.（3）粗線表示最小的生成樹(shù)， （10 分）權(quán)為 7： （12 分）15求（PQ） （R Q）的合取范式（P Q） （R Q）（P Q）（RQ） （4 分）(P Q)（RQ）(P RQ) (QRQ)(P RQ) R 合取范式 （12 分）16設(shè) A=0，1， 2，3，4，R=|xA，yA 且 x+y|x A，yA 且 x+y3，試求 R，S，R S，R-1，S-1，r(R) R=, （2 分）S=, （4 分）RS=， （6 分）R-1=， （8 分）S-1= S， （10 分）r(R)=IA （12 分）17畫(huà)一棵帶權(quán)為 1, 2, 2, 3, 4 的最優(yōu)二叉樹(shù),計(jì)算它們的權(quán)（10 分）權(quán)為 13+23+22+32+42=27 （12 分）15求（PQ） R 的析取范式與合取范式（P Q） R （PQ）R （4 分） (PQ)R （析取范式） （8 分） (PR) (QR) （合取范式） （12 分）16設(shè) A=0，1， 2，3，R=|xA，yA 且 x+y|x A，yA 且 x+y2，試求 R，S，R S，S -1，r(R)R=, S=, （3 分）RS=， （6 分）S -1= S， （9 分）r(R)=IA=, （12 分）17畫(huà)一棵帶權(quán)為 1, 2, 2, 3, 4 的最優(yōu)二叉樹(shù),計(jì)算它們的權(quán)最優(yōu)二叉樹(shù)如圖三所示（10 分）圖三權(quán)為 13+23+22+32+42=27 （12 分）15設(shè)謂詞公式 ，試),(),()zxyByxA（1）寫(xiě)出量詞的轄域； （2）指出該公式的自由變?cè)图s束變?cè)?）x 量詞的轄域?yàn)?， （3 分）,z 量詞的轄域?yàn)?, （6 分）)(zxyB（2）自由變?cè)獮?中的 y， （9 分）),(zxBA約束變?cè)獮?x 與 z （12 分）16設(shè)集合 A=1,1,2，B=1,1,2，試計(jì)算（1） （AB ） ； （2） （AB） ； （3）AB （1）AB =1,2 （4 分）（2）AB =1 （8 分）（3）AB=， （12 分）17設(shè) G=，V= v1，v2，v3，v4 ，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) ，試（1）給出 G 的圖形表示； （2）寫(xiě)出其鄰接矩陣；（3）求出每個(gè)結(jié)點(diǎn)的度數(shù)； （4）畫(huà)出其補(bǔ)圖的圖形 （10分）權(quán)為13+23+22+32+42=27 （12分） 1 22 3347 512 1 22 3347 512.（1）G 的圖形表示為(如圖三)：（3 分） （2）鄰接矩陣：（6 分）01（3）v1，v2，v3，v4 結(jié)點(diǎn)的度數(shù)依次為 1，2，3，2 （9 分）（4）補(bǔ)圖如圖四所示：21化簡(jiǎn)下列集合表示式：)()()()( CBACBA= A= = 設(shè) E 為全集E= )()(= = = A22設(shè) ， ，求 ， ，并畫(huà)出其圖像,21|Rxx,0|RyBBA =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 的圖形表示； 畫(huà)出其補(bǔ)圖的圖形 G 的圖形表示見(jiàn)圖 3； G 的補(bǔ)圖的圖形，見(jiàn)圖 4.圖 3 圖 424構(gòu) 造 權(quán) 為 2， 3， 4， 4， 5， 5， 7 的 最 優(yōu) 樹(shù) 。最優(yōu)樹(shù)如下圖 5 所示21設(shè) A，B 和 C 是全集 E 的子集，化簡(jiǎn)下列集合表示式：)()()( CBA= )(CBA= = )()(= (= 22設(shè) A 1,2,3，用列舉法給出 A 上的恒等關(guān)系 IA，全關(guān)系 EA，A 上的小于關(guān)系yxyxL及其逆關(guān)系和關(guān)系矩陣.（2 分）,AI3,1,3,2,1, E（2 分）（2 分）321,2LA 的逆關(guān)系 （2 分）,A. （2 分）0AM011ALM23圖 G=，其圖形如右圖 1 所示。 寫(xiě)出 G 的鄰接矩陣； 畫(huà)出 G 的權(quán)最小的生成樹(shù)以及計(jì)算出其權(quán)值 G 的鄰接矩陣為： （4 分）0101 G 的權(quán)最小的生成樹(shù)如右上圖 1 所示 （4 分）最小的生成樹(shù)的權(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 (BC)=(AB) (AC) 證明：設(shè) S= A (BC)，T=(AB) (A C)，若 xS，則 xA 或 xB C，即 xA 或 xB 且 xA 或 xC也即 xA B 且 xAC ，即 xT，所以 ST （4 分）反之，若 xT，則 xAB 且 xAC，即 xA 或 xB 且 xA 或 xC ，也即 xA 或 xBC，即 xS ，所以 TS因此 T=S 19試證明集合等式 A (BC)=(AB) (AC)證明：設(shè) S= A (BC)，T=(AB) (A C)，若 xS，則 xA 或 xB C，即 xA 或 xB 且 xA 或 xC也即 xA B 且 xAC ，即 xT，所以 ST （4 分）反之，若 xT，則 xAB 且 xAC，即 xA 或 xB 且 xA 或 xC ，也即 xA 或 xBC，即 xS，所以 TS18設(shè) G 是一個(gè) n 階無(wú)向簡(jiǎn)單圖，n 是大于等于 2 的奇數(shù)證明 G 與 中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等( 是 G 的補(bǔ)圖) 證明：因?yàn)?n 是奇數(shù)，所以 n 階完全圖每個(gè)頂點(diǎn)度數(shù)為偶數(shù)， （3 分）因此，若 G 中頂點(diǎn) v 的度數(shù)為奇數(shù)，則在 中 v 的度數(shù)一定也是奇數(shù)， （6 分）所以 G 與 中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等 （8 分）18試證明集合等式 A (BC)=(AB) (AC) 證明：設(shè) S= A (BC)，T=(AB) (A C)，若 xS，則 xA 或 xB C，即 xA 或 xB 且 xA 或 xC也即 xA B 且 xAC ，即 xT，所以 ST （4 分）反之，若 xT，則 xAB 且 xAC， 即 xA 或 xB 且 xA 或 xC，也即 xA 或 xBC，即 xS ，所以 TS因此 T=S 18設(shè) A，B 是任意集合，試證明：若 AA=BB，則 A=B證明：設(shè) xA，則 AA， （1 分）因?yàn)?AA=BB，故 BB，則有 xB， （3 分）所以 AB （5 分）設(shè) xB，則BB，