中央電大離散數(shù)學(xué)考試試題

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請(qǐng)聯(lián)系刪除，謝謝！中央電大離散數(shù)學(xué)（本科）考試試卷31．若集合，2}，B={1，2，{1，2}}，則下列表述正確的是(a)．．B，且BB．B，且BC．B，且BD．B，且B2．設(shè)有向圖（）、（b）與（d）如圖一所示，則下列結(jié)論成立的是(d)．．（）是強(qiáng)連通的C．（）是強(qiáng)連通的B．（b）是強(qiáng)連通的D．（d）是強(qiáng)連通的G0100111000001001011100100則G的邊數(shù)為(b)．．6B．54．無向簡(jiǎn)單圖G是棵樹，當(dāng)且僅當(dāng)(a)．C．4D．3．G連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1C．G的邊數(shù)比結(jié)點(diǎn)數(shù)少1B．G連通且結(jié)點(diǎn)數(shù)比邊數(shù)少1D．G中沒有回路．5．下列公式(c)為重言式．．PPQC．(P(P))(P(PQ))1．若集合Aab}，B={ab，{ab}}，則（a）．．AB，且ABB．AB，但ABC．AB，但BD．AB，且AB．(Q(PQ))((PQ))D．(P(PQ))Q2．集合A={1,2,3,4,5,6,7,8}上的關(guān)系R，>|x=10且,yA}，則R的性質(zhì)為（b）．．自反的B．對(duì)稱的C．傳遞且對(duì)稱的．反自反且傳遞的3．如果R和R是A上的自反關(guān)系，則R∪R，R∩R，RR中自反關(guān)系有（b）個(gè)．12121212．0B．2C1D．34．如圖一所示，以下說法正確的是(d)．．{(a,e)}是割邊C．{(a,e)b,c)}是邊割集B．{(a,)}是邊割集．{(d,)}是邊割集5．設(shè)（）：x是人，B（x）：x是學(xué)生，則命題“不是所有人都是學(xué)生”可符號(hào)化為（c）．．(∧B(x))B(∧B(x))C．┐(x)(A(x)→B(x))D．┐(∧┐B(x))1．設(shè)Aab}，B={1,2}，RR，R是A到B的二元關(guān)系，且Ra，2>,b，2>}，Ra，1>,12312a，2>,<b，1>}，Ra1>,b，2>}，則（b）不是從A到B的函數(shù)．3．R和RB．RC．RDR和R1223132．設(shè)A={1,2,3,4,5,6,7,8}，R是A上的整除關(guān)系，B={2,4,，則集合B的最大元、最小元、上界、下界依次為(b)．．8、2、8、2B．無、22C．62、62D．81、、13．若集合A的元素個(gè)數(shù)為10，則其冪集的元素個(gè)數(shù)為（a）．．1024B．10C．100D14．設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n2)，m條邊，當(dāng)（c）時(shí)，K中存在歐拉回路．nn．m為奇數(shù)B．n為偶數(shù)C．n為奇數(shù)D．m為偶數(shù)5．已知圖G的鄰接矩陣為1/13，則G有（d）．．5點(diǎn)，8邊B．6點(diǎn)，7邊C．6點(diǎn)，8邊．57邊1．若集合＝{a，{a}，{1，2}}，則下列表述正確的是(c)．．，{a}}．{2}AC．{a}A．A2．設(shè)圖＝E>，V，則下列結(jié)論成立的是(c)．deg(v)2Ev)E．deg(v)=2EB．deg(v)=EC．vVD．vV3P∨）→R的析取范式是(d)．（P∨）∨RC．（P∨）∨R．（P∧）∨R．（P∧）∨R4．如圖一所示，以下說法正確的是(a)．．e是割點(diǎn)C．{b,e}是點(diǎn)割集B．{a,是點(diǎn)割集．rgrrgkq是點(diǎn)割集5．下列等價(jià)公式成立的為(b．．PPQBP(P)P(PQ)C．(PQ)(PQ)．P(PQ)Q1．若G是一個(gè)漢密爾頓圖，則G一定是(d)．．平面圖B．對(duì)偶圖C．歐拉圖．連通圖2．集合A={1,2,3,4}上的關(guān)系，y>|x=y且x,y，則R的性質(zhì)為（c）．．不是自反的B．不是對(duì)稱的C．傳遞的．反自反3．設(shè)集合，2，3，4，偏序關(guān)系是A上的整除關(guān)系，則偏序集，上的元素5是集合A的（b）．．最大元B．極大元C．最小元D．極小元4．圖G如圖一所示，以下說法正確的是(c)．．{(a,d)}是割邊B．{(a,d)}是邊割集C．{(a,d),(b,d)}是邊割集D．{(b,d)}是邊割集圖一5．設(shè)（）：x是人，B（x）：x是工人，則命題“有人是工人”可符號(hào)化為（a）．．(∧B(x))B．(∧B(x))C．┐(x)(A(x)→B(x))D．┐(∧┐B(x))1．若集合＝{a，{a}}，則下列表述正確的是(a)．．{a}．{{{a}}}AC．，{a}}A．A2P∨）的合取范式是(c)．（P∧）C．（P∨）BP∧P∨Q）．（P∧）3．無向樹T有8個(gè)結(jié)點(diǎn)，則T的邊數(shù)為(b)．．6B7C．84．圖G如圖一所示，以下說法正確的是(b)．D．9．a(chǎn)是割點(diǎn)C．{b,d}是點(diǎn)割集B．{b,c}是點(diǎn)割集D．{c}是點(diǎn)割集圖一5．下列公式成立的為(d)．．P∧QP∨Q．PQPQC．PPP∧(P∨Q)Q1．“小于5的非負(fù)整數(shù)集合”采用描述法表示為___a___．2/13．xN,x<5}B．xR,x<5}C．xZ,x<5}D．xQ,x<5}2．設(shè)R1，R2是集合A={a,b,c,d}上的兩個(gè)關(guān)系，其中R1={(a,a),(b,b),(b,c),(d,d)}，R2={(a,a),(b,b),(b,c),(c,b),(d,d)}，則R2是R1__b____閉包．．自反C．傳遞B．對(duì)稱．以上答案都不對(duì)3．設(shè)函數(shù)：R→R，f(a)=2a+1；：R→R，g(a)=a2，則___c___有反函數(shù)．．fgC．fB．gfD．gGG．0100010001110101110111110．5點(diǎn)，8邊C．68邊B．6點(diǎn)，7邊D5點(diǎn)7邊5．無向完全圖K4是．．漢密爾頓圖C．非平面圖B．歐拉圖D．樹6．在5個(gè)結(jié)點(diǎn)的完全二叉樹中，若有4條邊，則有___b___片樹葉．．2C．4B．3．57．無向樹T有7片樹葉，3個(gè)3度結(jié)點(diǎn)，其余的都是4度結(jié)點(diǎn)，則T有__c___個(gè)4度結(jié)點(diǎn)．．3C．1B．2．08．與命題公式P（）等值的公式是___a___．．(PQ)RB．Q)RC．(PQ)((P(Q()()xPxyQx9．謂公式()(中量詞x的轄域是___b___．xPxy()()PxyRy．B．Q(x)CP(x)D．xP(x)(xQ(x)xQ(x))10．謂詞公式．蘊(yùn)涵式C．永真式的類型是___c___．B．永假式D．非永真的可滿足式1．設(shè)A={1,2,3,4}，B={1,3}C={-1,0,1,2}___a___．BABABCBC．C．B．D．2．若集合A的元素個(gè)數(shù)為10，則其冪集的元素個(gè)數(shù)為___b___．．1000C．1B．1024D．10(AB)C__c____．3．設(shè)集合A={1,2}，B={a,b}，C={}，則．{<1,a,>,<1,b,>,<2,a,>,<2,b,>}B．{<1,<a,>>,<1,<b,>>,<2,<a,>>,<2,<b,>>}C．{<<1,a>,>,<<1,b>,>,<<2,a>,>,<<2,b>,>}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___．．8、1、61C．62、62B．8、28、2D2、無、25．有5個(gè)結(jié)點(diǎn)的無向完全圖K5的邊數(shù)為___a___．．10C．5B．20．256．設(shè)完全圖K有n個(gè)結(jié)點(diǎn)2)，m條邊，當(dāng)___b___時(shí)，K中存在歐拉回路．nn．n為偶數(shù)C．m為偶數(shù)B．n為奇數(shù)D．m為奇數(shù)7．一棵無向樹T有5片樹葉，3個(gè)2度分支點(diǎn)，其余的分支點(diǎn)都是3度頂點(diǎn)，則T有__c___個(gè)頂點(diǎn)．．3B8C．11138P∨）→R的析取范式是___b___．．（P∧）∨RCP∧）∨RB．（P∨）∨R．（P∨）∨R9．下列等價(jià)公式成立的是___b___．．PPQC．P(PQ)Q10．謂詞公式．蘊(yùn)涵式C．永真式B．(P)P(PQ)．(PQ)(PQ)xP(x)(xQ(x)xQ(x))的類型是__c____．B．永假式D．非永真的可滿足式3PQP)6．命題公式的真值是T（或1）．7．若圖G=<V,中具有一條漢密爾頓回路，則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S，在G中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為，則S中結(jié)點(diǎn)數(shù)S|與W滿足的關(guān)系式為S|．3/138．給定一個(gè)序列集合{000，，01100}，若去掉其中的元素碼．0，則該序列集合構(gòu)成前綴9．已知一棵無向樹T中有84度，3度，2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為5．10．()(P()→()∨R(，))中的自由變?cè)獮镽(，y)中的y6．若集合A的元素個(gè)數(shù)為10，則其冪集的元素個(gè)數(shù)為1024．．7．設(shè)Aab，}，B={1，，作f：A→B，則不同的函數(shù)個(gè)數(shù)為88．若A={1,2}，R={<,A,A,y=10}，則R的自反閉包為{<1,1>,<2,2>}．9．結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足e=v1關(guān)系的無向連通圖就是樹．6．設(shè)集合A＝{ab}，那么集合A的冪集是{,{,bab．7．如果R和R是A上的自反關(guān)系，則R∪R，R∩R，RR中自反關(guān)系有2個(gè)．121212128．設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18，則可從G中刪去4條邊后使之變成樹．9．設(shè)連通平面圖G的結(jié)點(diǎn)數(shù)為5，邊數(shù)為6，則面數(shù)為3．10．設(shè)個(gè)體域＝{a,b}()A()∧（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)系，R,yxy,yA}則R的有序?qū)蠟閧<2,2>，<2,3>，<3,2>}，<3,3>．7．設(shè)G是連通平面圖，,,r分別表示G的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則，e和r滿足的關(guān)系式-=2．8．設(shè)＝V,E是有68條邊的連通圖，則從G中刪去3條邊，可以確定圖G的一棵生成樹．9．無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)(x)10．設(shè)個(gè)體域＝{1,2}，則謂詞公式6．命題公式消去量詞后的等值式為A(1)A(2)PQP)的真值是T（或1）．7．若圖G=<V,中具有一條漢密爾頓回路，則對(duì)于結(jié)點(diǎn)集V的每個(gè)非空子集S，在G中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為，則S中結(jié)點(diǎn)數(shù)S|與W滿足的關(guān)系式為S|．8．給定一個(gè)序列集合{000，，01100}，若去掉其中的元素0，則該序列集合構(gòu)成前綴碼．9．已知一棵無向樹T中有84度，3度，2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為10．()(P()→()∨R(，))中的自由變?cè)獮镽(，y)中的y5．6．若集合A的元素個(gè)數(shù)為10，則其冪集的元素個(gè)數(shù)為1024．．7．設(shè)Aab，}，B={1，，作f：A→B，則不同的函數(shù)個(gè)數(shù)為88．若A={1,2}，R={<,A,A,y=10}，則R的自反閉包為{<1,1>,<2,2>}．9．結(jié)點(diǎn)數(shù)v與邊數(shù)e滿足e=v1關(guān)系的無向連通圖就是樹．10．設(shè)個(gè)體域＝a,b,}()A()消去量詞后的等值式為A(a)∧A(b)∧A（）6．若集合A=，35，7}，={2，4，68}，則A∩B）．7．設(shè)集合A={1，23}上的函數(shù)分別為：f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，則復(fù)合函數(shù)gf={<1,2>,<2,3>,<3,2>,}8．設(shè)G是一個(gè)圖，結(jié)點(diǎn)集合為V，邊集合為E，則G的結(jié)點(diǎn)度數(shù)之和為E（或“邊數(shù)的兩倍”）9．無向連通圖G的結(jié)點(diǎn)數(shù)為，邊數(shù)為，則G當(dāng)v與e滿足e=v-1關(guān)系時(shí)是樹．10．設(shè)個(gè)體域＝{1,2,3}，P)為“x小于2”，則謂詞公式()P()的真值為假（或F，或0）．6．設(shè)集合A={2,3,4}，B={1,2,3,4}，R是A到B的二元關(guān)系，R,yxyx}則R的有序?qū)蠟閧<2,2>，<2,3>，<2,4>，<3,3>}，<3,，<4,4>}7．如果R是非空集合A上的等價(jià)關(guān)系，aA，bA，則可推知R中至少包含a,a>，<b,b等元素．8．設(shè)＝V,E是有48條邊的無向連通圖，則從G中刪去5條邊，可以確定圖G的一棵生成樹．9．設(shè)G是具有n個(gè)結(jié)點(diǎn)m條邊k個(gè)面的連通平面圖，則m等于n2(x)(x)10．設(shè)個(gè)體域＝{1,2}，A()為“x大于1”，則謂詞公式的真值為真（或，或1）．設(shè)集合A={1,2,3}，用列舉法寫出A上的恒等關(guān)系I，全關(guān)系E：AAI=__I={<1,1>,<2,2>,<3,3>}；AAE={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}A12．設(shè)集合A＝a，b}，那么集合A的冪集是{,{a},,{a,b}}13．設(shè)集合A={1,2,3}，B={a,b}，從A到B的兩個(gè)二元關(guān)系R={<1,a>,<2,b>,<3,a>}，S={<1,a>,<2,a>,<3,a>}，則R-S=_R-S={<2,b>}．14．設(shè)G是連通平面圖，,,r分別表示G的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則，e和r滿足的關(guān)系式v-e+r=2．15．無向連通圖G是歐拉圖的充分必要條件是結(jié)點(diǎn)度數(shù)均為偶數(shù)．16．設(shè)＝V,E是有68條邊的連通圖，則從G中刪去3成樹．條邊，可以確定圖G的一棵生17．設(shè)G是完全二叉樹，G有15個(gè)結(jié)點(diǎn)，其中有8個(gè)是樹葉，則G有____14___G的總度數(shù)是___28_____，G的分支點(diǎn)數(shù)是____7____．18．設(shè)P，Q的真值為1，R，S的真值為0，則命題公式___0_____．(PQ)RSQ的真值為PQR)的合取范式為P(QR)析取范式為(PQ)(PR)19．命題公式4/1320．設(shè)個(gè)體域?yàn)檎麛?shù)集，公式y(tǒng)(xy真值為___1_____．．設(shè)集合A={1,2,3,4}，B={3,4,5,6}，則：ABAB_____{1,2,3,4,5,6}_____．___{3,4}_____，12．設(shè)集合A有n個(gè)元素，那么A的冪集合P(A)的元素個(gè)數(shù)為．13．設(shè)集合A={a,b,c,d}，B={x,y,z}，R={<a,x>,<a,z>,<b,y>,<c,z>,<d,y>}101010則關(guān)系矩陣M＝．R14．設(shè)集合A={a,bc,,e}，A上的二元關(guān)系R={<a,b>,<c,d>,<b,b>}，S={<d,b>,<b,e>,<c,a>}，則R·S={<a,e>,<c,b>,<b,e>}01015．無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且__所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)16．設(shè)連通平面圖G的結(jié)點(diǎn)數(shù)為5，邊數(shù)為6，則面數(shù)為17．設(shè)正則二叉樹有n個(gè)分支點(diǎn)，且內(nèi)部通路長(zhǎng)度總和為I，外部通路長(zhǎng)度總和為E，則有E=___In3．(PR)QS)18．設(shè)P，Q的真值為0，，S的真值為1，則命題公式的真值為_____1___．19．已知命題公式為＝()R，則命題公式G的析取范式是(PQ)R20．謂詞命題公式()(P()→()∨R(，))中的約束變?cè)獮開__x___．三、邏輯公式翻譯4．將語句“如果所有人今天都去參加活動(dòng)，則明天的會(huì)議取消．”翻譯成命題公式．設(shè)P：所有人今天都去參加活動(dòng)，：明天的會(huì)議取消，（1分）PQ．4分）12．將語句“今天沒有人來．”翻譯成命題公式．設(shè)P：今天有人來，P．1分）4分）13．將語句“有人去上課．”翻譯成謂詞公式．設(shè)P(x)：x是人，Q(x)：x去上課，（1分）(x)(P(x)Q(x))．（4分）．將語句“如果你去了，那么他就不去．”翻譯成命題公式．設(shè)P：你去，：他去，P．（1分）4分）12．將語句“小王去旅游，小李也去旅游．”翻譯成命題公式．設(shè)P：小王去旅游，Q：小李去旅游，（1分）P．（4分）13．將語句“所有人都去工作．”翻譯成謂詞公式．設(shè)P(x)：x是人，Q(x)：x去工作，(x)(P(x)Q(x))．1分）（4分）．將語句“他不去學(xué)校．”翻譯成命題公式．設(shè)P：他去學(xué)校，P．1分）（4分）12．將語句“他去旅游，僅當(dāng)他有時(shí)間．”翻譯成命題公式．設(shè)P：他去旅游，：他有時(shí)間，P．（1分）4分）13．將語句“所有的人都學(xué)習(xí)努力．”翻譯成命題公式．設(shè)P(x)：x是人，Q(x)：x學(xué)習(xí)努力，（）(P(x)Q(x))．1分）（3分）．將語句“盡管他接受了這個(gè)任務(wù)，但他沒有完成好．”翻譯成命題公式．設(shè)P：他接受了這個(gè)任務(wù)，：他完成好了這個(gè)任務(wù)，（2分）PQ．（6分）12．將語句“今天沒有下雨．”翻譯成命題公式．設(shè)P：今天下雨，P．（2分）6分）．將語句“他是學(xué)生．”翻譯成命題公式．設(shè)P：他是學(xué)生，2分）6分）則命題公式為：P．12．將語句“如果明天不下雨，我們就去郊游．”翻譯成命題公式．設(shè)P：明天下雨，：我們就去郊游，則命題公式為：PQ．2分）（6分）．將語句“今天考試，明天放假．”翻譯成命題公式．設(shè)P：今天考試，：明天放假．則命題公式為：P∧．2分）6分）12．將語句“我去旅游，僅當(dāng)我有時(shí)間．”翻譯成命題公式．設(shè)P：我去旅游，Q：我有時(shí)間，則命題公式為：PQ．2分）（6分）⑴將語句“如果明天不下雨，我們就去春游．”翻譯成命題公式．⑵將語句“有人去上課．”翻譯成謂詞公式．⑴設(shè)命題P表示“明天下雨”，命題Q表示“我們就去春游”.則原語句可以表示成命題公式P→Q.（5分）⑵設(shè)P(x)：x是人，Q(x)：x去上課則原語句可以表示成謂詞公式(x)(P(x)Q(x))．四、判斷說明題714PP→┐P為永真式．5/13正確．（3分）┐PP→┐PP∧（P→┐Q）與P組成的析取式，如果P的值為真，則┐PP→┐）∨P為真，如果P的值為假，則┐P與PQ為真，即┐PP→┐）為真，也即┐PP→┐P為真，（5分）所以┐PP→┐P是永真式．7分）15．若偏序集，R>的哈斯圖如圖一所示，則集合A的最大元為，最小元不存在．正確．3分）對(duì)于集合A的任意元素，均有<x,R（或），所以a是集合A中的最大元．（5分）14．如果R1和R2是A上的自反關(guān)系，則R1∪R2是自反的．正確．3分）R1和R2是自反的，，<x,x>R1，<x,x>R2，則<x,x>R1R2，所以R1∪R2是自反的．（7分）15．如圖二所示的圖G存在一條歐拉回路．5d4eg1cnfha2b3正確．（3分）因?yàn)閳DG為連通的，且其中每個(gè)頂點(diǎn)的度數(shù)為偶數(shù)．14．設(shè)、R分別為自然數(shù)集與實(shí)數(shù)集，：→R，f(x)=x+6，則f是單射．正確．（3分）（7分）設(shè)x1，x2為自然數(shù)且x1x2，則有f(x1)=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)單平面圖，若≥3，則≤3v-6．”13．下面的推理是否正確，試予以說明．(1)（）F（）→（）前提引入(2)F（）→（）US（1）．錯(cuò)誤．（2）應(yīng)為F（）→（），換名時(shí)，約束變?cè)c自由變?cè)荒芑煜?4．若偏序集，R>的哈斯圖如圖二所示，則集合A的最大元為，最小元不存在．（3分）（7分）錯(cuò)誤．集合A的最大元不存在，a是極大元．（3分）7分）13．下面的推理是否正確，試予以說明．(1)（）F（）→（）前提引入(2)F（）→（）US（1）．錯(cuò)誤．（3分）（2）應(yīng)為F（）→（），換名時(shí)，約束變?cè)c自由變?cè)荒芑煜?分）14．如圖二所示的圖G存在一條歐拉回路．錯(cuò)誤．因?yàn)閳DG為中包含度數(shù)為奇數(shù)的結(jié)點(diǎn)．（3分）7分）13．如果圖G是無向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G是歐拉圖．錯(cuò)誤．當(dāng)圖G不連通時(shí)圖G不為歐拉圖．（3分）7分）6/1314．若偏序集，R>的哈斯圖如圖二所示，則集合A的最大元為，最小元是．錯(cuò)誤．集合A的最大元與最小元不存在，a是極大元，f是極小元，．（3分）五．計(jì)算題16．設(shè)集合，2，34}R={<x,y>|x,y；y|=1或x，試（1）寫出R的有序?qū)Ρ硎荆唬?）畫出R的關(guān)系圖；（3）說明R滿足自反性，不滿足傳遞性．（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}（3分）（2）關(guān)系圖為12346（3）因?yàn)?lt;1,1>,<2,2>,<3,3>,<4,4>均屬于R，即A的每個(gè)元素構(gòu)成的有序?qū)赗中，故R在A上是自反的。（9分）因有<2,3>與<3,4>屬于R，但<2,4>不屬于R，所以R在A上不是傳遞的。17．求PR的析取范式，合取范式、主析取范式，主合取范式．P→（R∨）┐P∨(R∨Q)┐P∨∨R（析取、合取、主合取范式）（9分）(┐P∧┐∧┐R)∨(P∧R)∨(┐P∧∧R)∨∧┐R)∨(P∧┐∧R)∨∧∧┐R)∨(P∧Q∧R)（主析取范式）（12分）18．設(shè)圖，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)(v3,v4)，(v3,v5)，(v4,v5)}，試畫出G的圖形表示；寫出其鄰接矩陣；(3)求出每個(gè)結(jié)點(diǎn)的度數(shù)；(4)畫出圖G的補(bǔ)圖的圖形．v1v2v53v4360101101101101101010110100v1vvvv23v4195v257/13v4316．設(shè)謂詞公式x(P(x,y)zQ(y,x,zyR(y,z)F(y)，試（1）寫出量詞的轄域；）指出該公式的自由變?cè)图s束變?cè)?）x量詞的轄域?yàn)閦量詞的轄域?yàn)?P(x,y)zQ(y,x,z，2分）Q(y,x,z),（4分）6分）R(y,z)y量詞的轄域?yàn)椋?）自由變?cè)獮椋?P(x,y)zQ(y,x,zF(y)Q(y,x,z)中的，以及R(y,z)中的z與R(y,z)中的．約束變?cè)獮閤與中的，以及（12分）17．設(shè)A={{1},{2},1,2}，B={1,2,{1,2}}，試計(jì)算（1）（AB）；（2）（AB）；3）A×B．（1）B={{1},{2}}（2）∩B={1,2}（4分）8分）（3）A×B={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>，<{2},{1,2}>，<1,1>，<1,2>，<1,{1,2}>，<2,1>，<2,2>,<2,{1,2}>}18．設(shè)，E>，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，試（1）給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（4）畫出其補(bǔ)圖的圖形．1）G的圖形表示為：360001101101101101000110100（3）v1，v2，v3，v4，v5結(jié)點(diǎn)的度數(shù)依次為1，24，32（4）補(bǔ)圖如下：9分）16P∨）→R的析取范式，合取范式，主合取范式．（P∨）→R┐(P∨Q)∨R(┐P∧┐Q)∨R（析取范式）（3分）(┐P∨R)∧(┐∨R)（合取范式）（6分）((┐P∨R)∨(Q∧┐Q))∧((Q∨R)∨(PP))(┐P∨R∨Q)∧(P∨RQ)∧(┐∨R∨P)∧(┐∨R∨┐P)(┐P∨∨R)∧(P∨┐R)∧(P∨┐Q∨R)（主合取范式）12分）17．設(shè)A={{a,b},1,2}，B={a,b,{1},，試計(jì)算（1）（B）（2）（∪B）（3）（∪B）（∩B）．（1）（B）={{a,b},2}（4分）（2）（∪B）={{a,b},1,2,a,b,{1}}（3）（∪B）（∩B）={{a,b},2,a,b,{1}}8分）（12分）18．圖E>，其中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、12、36、1、4及5，試（1）畫出G的圖形；（2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹及其權(quán)值．（1）G的圖形表示為：30100111001101101111110110權(quán)為7：15P∨）→（R∨Q）的合取范式．（P∨）→（R∨）（P∨）∨（R∨）4分）(P∧Q)∨（R∨Q）(P∨R∨Q)∧(Q∨R∨Q)(P∨R∨Q)∧R合取范式（12分）16．設(shè)，1，2，34}，y>|x，A且x+y<0}，，，A且3}，試求R，S，RS，R-1，S-1，．,（2分）S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>}（4分）RS=，R-1=，S-1=S，．6分）（8分）（10分）（12分）17．畫一棵帶權(quán)為1,2,2,3,4,計(jì)算它們的權(quán)．53342115P∨）→R的析取范式與合取范式．（P∨）→RP∨R2（4分）(P∧Q)∨R（析取范式）(P∨R)∧(∨R)（合取范式）（8分）（12分）16．設(shè)，1，23}，，y>|x，A且x+y<0}，，y>|x，A且x+y2}，試求R，S，RS，S-1，r(R)．,S={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}3分）RS=，S-1=S，（6分）（9分）r(R)=IA={<0,0>,<1,1>,<2,2>,<3,3>}．12分）17．畫一棵帶權(quán)為1,2,2,3,4,計(jì)算它們的權(quán)．最優(yōu)二叉樹如圖三所示75334212(x(x,y)z)B(y,x,z15．設(shè)謂詞公式，試（1）寫出量詞的轄域；）指出該公式的自由變?cè)图s束變?cè)?(x,y)z)B(y,x,z（1）x量詞的轄域?yàn)椋?分）（9分）B(y,x,z)z量詞的轄域?yàn)?（6分）中的，((x,y)z)B(y,x,z（2）自由變?cè)獮榧s束變?cè)獮閤與．（12分）9/1316．設(shè)集合A={{1},1,2}，B={1,{1,2}}，試計(jì)算（1）（B）；（2）（∩B）；（3）．（1）B={{1},2}（2）∩B={1}4分）8分）（3）A×B={<{1},1>，<{1},{1,2}>，<1,1>，<1,{1,2}>，<2,1>，<2,{1,2}>}（12分）17．設(shè)，E>，V={v1，v2，v3，v4}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)}，試（1）給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（4）畫出其補(bǔ)圖的圖形．（1）G的圖形表示為(如圖三)：3600011110101100103）v1，v2，v3，v4結(jié)點(diǎn)的度數(shù)依次為1，23，2（4）補(bǔ)圖如圖四所示：9分）(ABC)AB)C)(ABC)(ABC)(~B~C)(~BC)(AB~C)(ABC)=~B)CCAB)CC=~B)E)AB)E)==設(shè)E(~B)(AB)BB)=A=A=AEA{x|1xx}B{y|yy}，ABBA，⑴AB{x|1xx}{y|yy}=x,y|1xyx,y}=AB1圖1⑵B圖2A{y|yy}{x|1xx}==y,x|1xyx,y}BA223．設(shè)，E>，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)(v3,v5)，10/13(v4,v5)}，試：⑴給出G的圖形表示；⑵畫出其補(bǔ)圖的圖形．．⑴G的圖形表示見圖3；⑵G的補(bǔ)圖的圖形，見圖4圖3圖42，3，4，4，5，5，75B和CE(ABC)(~BC)ABC)(ABC)(~BC)ABC)(ABC)(~BC)(ABC)ABC)====AC)(B~B~)(BCAC)E)(E(BC(AC)(BC)(AB)C=AIEAAAL,y