.中央電大離散數(shù)學（本科）考試試題一、單項選擇題（每小題 3 分，本題共 15 分）1若集合 A=1， 2，B=1，2，1 ，2，則下列表述正確的是( a )AAB，且 AB BB A，且 ABCAB，且 AB DAB ，且 AB2設有向圖（a）、（b）、（c ）與（d）如圖一所示，則下列結(jié)論成立的是 ( d )圖一A（a）是強連通的 B（b）是強連通的C（c ）是強連通的 D（d）是強連通的3設圖 G 的鄰接矩陣為 01則 G 的邊數(shù)為( b )A6 B5 C4 D34無向簡單圖 G 是棵樹，當且僅當( a )AG 連通且邊數(shù)比結(jié)點數(shù)少 1 BG 連通且結(jié)點數(shù)比邊數(shù)少 1CG 的邊數(shù)比結(jié)點數(shù)少 1 DG 中沒有回路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上的關系 R=|x+y=10 且 x, y A，則 R 的性質(zhì)為（ b ） A自反的 B對稱的C傳遞且對稱的 D反自反且傳遞的3如果 R1 和 R2 是 A 上的自反關系，則 R1R 2，R 1R 2，R 1-R2 中自反關系有（ b ）個A0 B2 C1 D34如圖一所示，以下說法正確的是 ( 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 的函數(shù)AR 1 和 R2 BR 2 CR 3 DR 1 和 R32設 A=1, 2, 3, 4, 5, 6, 7, 8，R 是 A 上的整除關系，B =2, 4, 6，則集合 B 的最大元、最小元、上界、下界依次為 ( b )A8、2、8、2 B無、2、無、2C6、2、6、2 D8、1、6、13若集合 A 的元素個數(shù)為 10，則其冪集的元素個數(shù)為（ a ） A1024 B10 C100 D14設完全圖 K 有 n 個結(jié)點(n2)，m 條邊，當（ c ）時，K 中存在歐拉回路nAm 為奇數(shù) Bn 為偶數(shù) Cn 為奇數(shù) D m 為偶數(shù)5已知圖 G 的鄰接矩陣為 .，則 G 有（ d ） A5 點，8 邊 B6 點，7 邊 C6 點，8 邊 D5 點，7 邊1若集合 A a，a ，1，2，則下列表述正確的是( c )Aa，aA B2ACa A D A2設圖 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如圖一所示，以下說法正確的是 ( a )Ae 是割點 Ba, e 是點割集Cb, e是點割集 Dd是點割集5下列等價公式成立的為( b )AP QPQ BP (QP) P(PQ)CQ(P Q) Q(PQ) DP (PQ) Q1若 G 是一個漢密爾頓圖，則 G 一定是( d )A平面圖 B對偶圖C歐拉圖 D連通圖2集合 A=1, 2, 3, 4上的關系 R=|x=y 且 x, y A，則 R 的性質(zhì)為（ 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 )AaA BaACa ，a A DA2命題公式（P Q）的合取范式是 ( c )A （PQ） B （PQ）（PQ） C （PQ） D（PQ）3無向樹 T 有 8 個結(jié)點，則 T 的邊數(shù)為( b )A6 B7 C8 D9 4圖 G 如圖一所示，以下說法正確的是 ( b )Aa 是割點 Bb, c 是點割集Cb, d 是點割集 Dc 是點割集圖一5下列公式成立的為( d )AP Q PQ BP Q PQCQP P DP(PQ) Q1 “小于 5 的非負整數(shù)集合”采用描述法表示為_a_Axx N, x,B>,>,>,>C, >, >, >, > D1,2,a,b, 4設 A=1, 2, 3, 4, 5, 6, 7, 8，R 是 A 上的整除關系，B=2, 4, 6，則集合 B 的最大元、最小元、上界、下界依次為_d_A8、1、6、1 B 8、2、8、2C6、2、6、2 D無、2、無、25有 5 個結(jié)點的無向完全圖 K5 的邊數(shù)為_a_A10 B20 C5 D256設完全圖 K 有 n 個結(jié)點(n2)，m 條邊，當_b_時，K 中存在歐拉回路nAn 為偶數(shù) Bn 為奇數(shù) Cm 為偶數(shù) Dm 為奇數(shù)7一棵無向樹 T 有 5 片樹葉，3 個 2 度分支點，其余的分支點都是 3 度頂點，則 T 有_c_個頂點A3 B8C11 D138命題公式（PQ）R 的析取范式是_b_A （PQ）R B （PQ）RC （PQ） R D （PQ）R9下列等價公式成立的是_b_APQP Q B P(QP) P(PQ)CP (PQ) Q DQ(PQ) Q(PQ)10謂詞公式 的類型是_c_)()xxxA蘊涵式 B永假式 C永真式 D非永真的可滿足式二、填空題（每小題 3 分，本題共 15 分）6命題公式 的真值是 T （或 1） )(7若圖 G=中具有一條漢密爾頓回路，則對于結(jié)點集 V 的每個非空子集 S，在 G 中刪除 S 中的所有結(jié)點得到的連通分支數(shù)為 W，則 S 中結(jié)點數(shù)|S|與 W 滿足的關系式為 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設 A=a，b，c，B=1，2，作 f：AB，則不同的函數(shù)個數(shù)為 8 8若 A=1,2，R=|xA, yA, x+y=10，則 R 的自反閉包為, 9結(jié)點數(shù) v 與邊數(shù) e 滿足 e=v-1 關系的無向連通圖就是樹6設集合 Aa，b，那么集合 A 的冪集是 ,a,b,a,b 7如果 R1 和 R2 是 A 上的自反關系，則 R1R 2，R 1R 2，R 1-R2 中自反關系有 2 個 8設圖 G 是有 6 個結(jié)點的連通圖，結(jié)點的總度數(shù)為 18，則可從 G 中刪去 4 條邊后使之變成樹9設連通平面圖 G 的結(jié)點數(shù)為 5，邊數(shù)為 6，則面數(shù)為 3 10設個體域 Da, 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 的有序?qū)蠟椋?，7設 G 是連通平面圖，v, e , r 分別表示 G 的結(jié)點數(shù)，邊數(shù)和面數(shù)，則 v，e 和 r 滿足的關系式 v-e+r=2 8設 G是有 6 個結(jié)點， 8 條邊的連通圖，則從 G 中刪去 3 條邊，可以確定圖 G 的一棵生成樹9無向圖 G 存在歐拉回路，當且僅當 G 連通且所有結(jié)點的度數(shù)全為偶數(shù)10設個體域 D1,2，則謂詞公式 消去量詞后的等值式為 A(1)A(2)(x6命題公式 的真值是 T （或 1） )(PQ7若圖 G=中具有一條漢密爾頓回路，則對于結(jié)點集 V 的每個非空子集 S，在 G 中刪除 S 中的所有結(jié)點得到的連通分支數(shù)為 W，則 S 中結(jié)點數(shù)|S|與 W 滿足的關系式為 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設 A=a，b，c，B=1，2，作 f：AB，則不同的函數(shù)個數(shù)為 8 8若 A=1,2，R=|xA, yA, x+y=10，則 R 的自反閉包為, 9結(jié)點數(shù) v 與邊數(shù) e 滿足 e=v-1 關系的無向連通圖就是樹10設個體域 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設集合 A=1，2，3上的函數(shù)分別為： f=,，g=,，則復合函數(shù) gf =, , ,8設 G 是一個圖，結(jié)點集合為 V，邊集合為 E，則 G 的結(jié)點度數(shù)之和為 2|E|（或“邊數(shù)的兩倍” ） 9無向連通圖 G 的結(jié)點數(shù)為 v，邊數(shù)為 e，則 G 當 v 與 e 滿足 e=v-1 關系時是樹 10設個體域 D1, 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 的有序?qū)蠟椋?， ，7如果 R 是非空集合 A 上的等價關系，a A，bA，則可推知 R 中至少包含， 等元素8設 G是有 4 個結(jié)點， 8 條邊的無向連通圖，則從 G 中刪去 5 條邊，可以確定圖 G 的一棵生成樹9設 G 是具有 n 個結(jié)點 m 條邊 k 個面的連通平面圖，則 m 等于 n+k210設個體域 D1, 2，A(x )為“x 大于 1”，則謂詞公式 的真值為真（或 T，或 1）()x11設集合 A=1,2,3，用列舉法寫出 A 上的恒等關系 IA，全關系 EA：IA = _ IA =,；EA =,12設集合 Aa，b，那么集合 A 的冪集是 ,a,b,a,b13設集合 A=1,2,3，B =a,b，從 A 到 B 的兩個二元關系 R=,， S=,，則 R-S=_ R-S=14設 G 是連通平面圖，v, e, r 分別表示 G 的結(jié)點數(shù)，邊數(shù)和面數(shù)，則 v，e 和 r 滿足的關系式 v-e+r=215無向連通圖 G 是歐拉圖的充分必要條件是結(jié)點度數(shù)均為偶數(shù)16設 G是有 6 個結(jié)點， 8 條邊的連通圖，則從 G 中刪去 3 條邊，可以確定圖 G 的一棵生成樹17設 G 是完全二叉樹，G 有 15 個結(jié)點，其中有 8 個是樹葉，則 G 有_14_條邊，G 的總度數(shù)是_28_，G 的分支點數(shù)是_7_18設 P，Q 的真值為 1，R，S 的真值為 0，則命題公式 的真值為_0_QSP)(19命題公式 的合取范式為 析取范式為)(Q)()(RP20設個體域為整數(shù)集，公式 真值為_1_)(yx11設集合 A=1,2,3,4，B= 3,4,5,6， 則 ：_3,4_， _1,2,3,4,5,6_A12設集合 A 有 n 個元素，那么 A 的冪集合 P(A)的元素個數(shù)為 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 連通且_所有結(jié)點的度數(shù)全為偶數(shù)16設連通平面圖 G 的結(jié)點數(shù)為 5，邊數(shù)為 6，則面數(shù)為 3 17設正則二叉樹有 n 個分支點，且內(nèi)部通路長度總和為 I，外部通路長度總和為 E，則有 E=_ I+2n18設 P，Q 的真值為 0，R，S 的真值為 1，則命題公式 的真值為_1_)()(SQRP19已知命題公式為 G(PQ) 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 分）PQ （4 分）12將語句“小王去旅游，小李也去旅游 ”翻譯成命題公式設 P：小王去旅游，Q：小李去旅游， （1 分）PQ （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 分）則命題公式為：PQ （6 分）12將語句“我去旅游，僅當我有時間 ”翻譯成命題公式設 P：我去旅游， Q：我有時間， （2 分）則命題公式為：P Q （6 分） 將語句“如果明天不下雨，我們就去春游 ”翻譯成命題公式 將語句“有人去上課 ” 翻譯成謂詞公式設命題 P 表示“ 明天下雨” ，命題 Q 表示“我們就去春游”.則原語句可以表示成命題公式 PQ. （5 分）設 P(x)：x 是人，Q(x)：x 去上課 則原語句可以表示成謂詞公式 (x)(P(x) Q(x) 四、判斷說明題（每小題 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 分）對于集合 A 的任意元素 x，均有R（或 xRa） ，所以 a 是集合 A 中的最大元 （5 分）14如果 R1 和 R2 是 A 上的自反關系，則 R1R2 是自反的正確 （3 分）R1 和 R2 是自反的，x A， R1 ， R2 ， 則 R1R2， 所以 R1R2 是自反的 （7 分）15如圖二所示的圖 G 存在一條歐拉回路正確 （3 分）因為圖 G 為連通的，且其中每個頂點的度數(shù)為偶數(shù) （7 分）14設 N、R 分別為自然數(shù)集與實數(shù)集， f：NR，f (x)=x+6，則 f 是單射正確 （3 分）設 x1，x2 為自然數(shù)且 x1x2，則有 f(x1)= x1+6 x2+6= f(x2)，故 f 為單射 （7 分）15設 G 是一個有 6 個結(jié)點 14 條邊的連通圖，則 G 為平面圖錯誤 （3 分）不滿足“設 G 是一個有 v 個結(jié)點 e 條邊的連通簡單平面圖，若 v3，則 e3v-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 為中包含度數(shù)為奇數(shù)的結(jié)點 （7 分）13如果圖 G 是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖 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, yA；|x y|=1 或 xy=0，試（1）寫出 R 的有序?qū)Ρ硎?；?）畫出 R 的關系圖；（3）說明 R 滿足自反性，不滿足傳遞性（1）R=, （3 分）（2）關系圖為（6 分）（3）因為, 均屬于 R，即 A 的每個元素構(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設圖 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 的補圖的圖形（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 分）)(zy 量詞的轄域為 （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）（AB）； （2）（AB）； （3）A×B（1）AB =1,2 （4 分）（2）AB =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）求出每個結(jié)點的度數(shù)； （4）畫出其補圖的圖形1）G 的圖形表示為：（3 分）（2）鄰接矩陣：（6 分）010（3）v1，v2，v3，v4，v5 結(jié)點的度數(shù)依次為 1，2，4，3，2 （9 分）（4）補圖如下：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設 A=a, b, 1, 2，B= a, b, 1, 1，試計算（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) ，對應邊的權值依次為2、1、2、3、6、1、4 及 5，試（1）畫出 G 的圖形； （2）寫出 G 的鄰接矩陣；（3）求出 G 權最小的生成樹及其權值（1）G 的圖形表示為： （3 分）（2）鄰接矩陣：0110.（3）粗線表示最小的生成樹， （10 分）權為 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設 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畫一棵帶權為 1, 2, 2, 3, 4 的最優(yōu)二叉樹,計算它們的權（10 分）權為 13+23+22+32+42=27 （12 分）15求（PQ） R 的析取范式與合取范式（P Q） R （PQ）R （4 分） (PQ)R （析取范式） （8 分） (PR) (QR) （合取范式） （12 分）16設 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畫一棵帶權為 1, 2, 2, 3, 4 的最優(yōu)二叉樹,計算它們的權最優(yōu)二叉樹如圖三所示（10 分）圖三權為 13+23+22+32+42=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） （AB ） ； （2） （AB） ； （3）A×B （1）AB =1,2 （4 分）（2）AB =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）求出每個結(jié)點的度數(shù)； （4）畫出其補圖的圖形 （10分）權為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é)點的度數(shù)依次為 1，2，3，2 （9 分）（4）補圖如圖四所示：21化簡下列集合表示式：)()()()( CBACBA= A= = 設 E 為全集E= )()(= = = A22設 ， ，求 ， ，并畫出其圖像,21|Rxx,0|RyBBA =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構(gòu) 造 權 為 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 分）,AI3,1,3,2,1, E（2 分）（2 分）321,2LA 的逆關系 （2 分）,A. （2 分）0AM011ALM23圖 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 (BC)=(AB) (AC) 證明：設 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)證明：設 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設 G 是一個 n 階無向簡單圖，n 是大于等于 2 的奇數(shù)證明 G 與 中的奇數(shù)度頂點個數(shù)相等( 是 G 的補圖) 證明：因為 n 是奇數(shù)，所以 n 階完全圖每個頂點度數(shù)為偶數(shù)， （3 分）因此，若 G 中頂點 v 的度數(shù)為奇數(shù)，則在 中 v 的度數(shù)一定也是奇數(shù)， （6 分）所以 G 與 中的奇數(shù)度頂點個數(shù)相等 （8 分）18試證明集合等式 A (BC)=(AB) (AC) 證明：設 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設 A，B 是任意集合，試證明：若 AA=BB，則 A=B證明：設 xA，則 AA， （1 分）因為 AA=BB，故 BB，則有 xB， （3 分）所以 AB （5 分）設 xB，則BB，