北京大學(xué) 離散數(shù)學(xué) 2009下學(xué)期期中考試試題及答案

2009下學(xué)期離散數(shù)學(xué)期中考試試題姓名 學(xué)號 計(jì)分總分(21)(22)(23)(24)(25)(26)一選擇題(20%):【將選擇的答案填入下而表格屮】(2)(3)(4)(5)(6)(7)(8)(9)(10)(1)在聯(lián)結(jié)詞八、V、￥、中，具有可結(jié)合性的有( )個⑷2 (B)3 (C)4 (D)5命題形式pVqAr的對偶式是pVqAr(B)pAqVr(C)pA(qVr)(D)-^pA^qV-^r)下而是有關(guān)推理的一些概念，不正確的是( )：—個小一致的推理一定是正確的：呆一個推理形式是AiVA2VA3=>B.A!、A2、A3就是推理的前提。然推理系統(tǒng)P中進(jìn)行證明時，在證明的任何一步，都nJ*以引入任何的前提。任何證叫必須在一個推現(xiàn)系統(tǒng)中進(jìn)行，而且耑逛應(yīng)用相應(yīng)的證明方法。R和S是集合A上的W個關(guān)系，下面命題真值為真的是：( )R和S是自反的，則R?S也是自反的;R和S是對稱的，則R°S也是對稱的;R和S是反對稱的，則RoS也是反對稱的：R和S是傳遞的，則R=S也是傳遞的。有關(guān)關(guān)系的逆關(guān)系的說法不正確的是：( )等價關(guān)系和相容關(guān)系的逆關(guān)系就是其木身：?序關(guān)系的逆關(guān)系仍然是偏序關(guān)系：傘序關(guān)系的逆關(guān)系仍然是個序關(guān)系：tl序關(guān)系的逆關(guān)系仍然S良序關(guān)系；下而是一些運(yùn)算的分妃性表達(dá)式，不成立是( )An(B十C)=(Ar^B)十(AnC)(B) (B十C)=(AuB)十(AuC)(C)(A十B)XC=(AXC)十(BXC)(D)(A—B)XC=(AXC)—(BXC)下而( )不是命題：VxP(x)(B)3xP(x)(C)3x(P(x)VP(y))(D)3x3y(P⑻VP(y))下而說法不止確的是( )：公式A是可滿足式，則A的任何柃換實(shí)例仍然是可滿足式：公式層次S用米描述公式g雜性的一個11個命題變項(xiàng)構(gòu)成的各種命題形式，小M的S.值表有限，只有個。從范式現(xiàn)論米看，pAq可能足簡笮合取式、最小項(xiàng)，也可能S合取范式。SA是以空集為唯一元素的集介，|fljB=p(p(A)).則卜‘而不成立的是

0cB(B)0eB(C){0，{{0}}}cBD{0,{{0}}}eBf:A-B是可逆的，充耍條件是(A)A=B (B)A和B具有相冋的基數(shù)(C)f是滿射的(D)f是雙射的二填空題(20%):【將相應(yīng)的答案填入卜而表格屮】(11)(12)(13)(14)(15)(16)(17)(18)(19)(20)推理理論中的證叨方法有CP規(guī)則，有時也稱為 定理。A上存在二元關(guān)系，冋時具有H反性和非H反性的，A是 “W為可滿足穴的任何替換實(shí)例是可滿足式，所以承言式的、矛質(zhì)式的任何替換實(shí)例相應(yīng)一定是重言式、矛盾式”，該命題的真值是 命題邏輯的范式理論的u的在r構(gòu)建命題形式的標(biāo)準(zhǔn)形式，而具有唯一性的標(biāo)準(zhǔn)形式是 。個體域{1，2}，謂詞公式Vy3x(x+y=4)的真位是 A={1，2,3,4,5}，A上的二元關(guān)系中有 個等價關(guān)系。偏序集＜A，哈斯閣如閣所示，B是A的子集，B={3,6}B的上確界是 每個人的外泔付都是他付親的付親。設(shè):個體域:人;P(x，y):x是y的外祖母，Q(x.y):x是y的母親，則邏輯符號化為: 一個n個元素的集合A上的偏序關(guān)系，元素最多有 個。謂同邏輯的合式公式屮不#在『1巾變元，該公式被稱為 的。 三根據(jù)要求解答:【(21)?(24)必做，(25)?(26)任選一題，寫在答題紙上】(12%)某三元哀值函數(shù)f(p，q.r)為:f(0,0,0)=0,f(0,0,1)=1,f(0,1，0)=0,f(0,1,1)=1,f(l,0,0)=1,f(L0,1)=1,f(l,1,0)=0.f(l,1，1)=1,試用僅介聯(lián)結(jié)詞o的命題形式來表示f。(15%)每個旅客成少頭等艙成二等艙，毎個旅客當(dāng)且僅當(dāng)他富裕時才少頭等艙，有些旅客富裕但并非所有旅客富裕，所以有些旅客坐二等艙。(15%)己知&和1^2都是A上等價關(guān)系，且RjoR2=R2。Ri，證明Ri，Rz也是A上的等價關(guān)系。(9%)用特征函數(shù)證明下式成立的充要條件：A十B=0。(9%)己知A上的二元關(guān)系R滿足Rn=R,則R，R2，R3，."，Rn中的哪個可確定具有nJ*傳遞性。(9%)'4出{a，b,c}I?.的所有滿足Pf=IA的函數(shù)。2009下學(xué)期離散數(shù)學(xué)期中考試試題答案姓名 學(xué)號 計(jì)分—總分(21)(22)(23)(24)(25)(26)一選擇題(20%):【將選擇的答案填入下而表格屮】(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)CCBADBCADD(1)在聯(lián)結(jié)詞八、V、￥、中，具有可結(jié)合性的有( )個⑷2 (B)3 (C)4 (D)5命題形式pVqAr的對偶式是(A)pVqAr(B)pAqVr(C)pA(qVr)(D)-^pA(->qV-<r)下而是有關(guān)推理的一些概念，不正確的是( )：—個小一致的推理一定是正確的：呆一個推理形式是AiVA2VA3=>B,A!、A2、A3就是推理的前提。(c)在H然推理系統(tǒng)p中進(jìn)行證明時，在證明的任M—步，都II]*以引入任何的前提。(D)任何證叫必須在一個推理系統(tǒng)中進(jìn)行，而且耑逛應(yīng)用相應(yīng)的證明方法。R和S是集合A上的W個關(guān)系，下曲命題K值為真的是：( )R和S是自反的，則R，S也是自反的;R和S是對稱的，則RoS也是對稱的;R和S足反對稱的，則RoS也是反對稱的：R和S是傳遞的，則R=S也是傳遞的。有關(guān)關(guān)系的逆關(guān)系的說法不正確的是：( )等價關(guān)系和相容關(guān)系的逆關(guān)系就是其本身：偏序關(guān)系的逆關(guān)系仍然是偏序關(guān)系：傘序關(guān)系的逆關(guān)系仍然是仝序關(guān)系：tl序關(guān)系的逆關(guān)系仍然S良庁關(guān)系；下而是一些運(yùn)算的分K性表達(dá)式，不成立是( )(A)An(B十C)=(Ar^B)十(AnC)(B) (B十C)=(AuB)十(AuC)(A十B)XC=(AXC)十(BXC)(D)(A—B)XC=(AXC)—(BXC)下而( )不是命題：(A)VxP(x) (B)3xP⑻(C)3x(P(x)VP(y)) (D)3x3y(P⑻VP(y))下而說法不正確的是( )：公式A是可滿足式，則A的任何柃換實(shí)例仍然是可滿足式：公式層次S用米描述公式g雜性的一個11個命題變項(xiàng)構(gòu)成的各種命題形式，小M的ft值表有限，只有^個。從范式現(xiàn)論來看，pAq可能足簡単合取式、最小項(xiàng)，也可能S合取范式。SA是以空集為唯一元素的集介，|fljB=p(p(A)).則卜‘而不成立的是

(A)0cB(B)0eB(C){0，{{0}}}cBD{0，{{0}}}eBf:A-B是可逆的，充?條件是(A)A=B (B)A和B具有相同的基數(shù)(C)f是滿射的(D)f是雙射的二填空題(20%):【將相應(yīng)的答案填入卜而表格中】(")演繹(12)0(13)T(14)主合取范式、主析取范式(15)F(16)67(即劃分?jǐn)?shù))(17)6(18)VxVy(P(x.y)^3z(Q(x,z)AQ(z，y))(19)n(n+l)/2(20)封閉推理理論中的證明方法有CP規(guī)則，有時也稱為 定理。A上存在二元關(guān)系，冋時具有H反性和非H反性的，A是 “W為可滿足忒的任何替換實(shí)例是可滿足式，所以承言式的、矛盾式的任何替換實(shí)例相應(yīng)一定是重言式、矛盾式”，該命題的真值是 命題邏輯的范式理論的u的/i:r構(gòu)建命題形忒的標(biāo)準(zhǔn)形式，而具有唯一性的標(biāo)準(zhǔn)形式是 個體域{1,2}，謂詞公式Vy3x(x+y=4)的真位是 A={1，2,3,4,5}，A上的二元關(guān)系中有 個等價關(guān)系。偏序集＜A，＜＞哈斯W如W所示，B是A的子集，B={3,6}，B的上確界每個人的外祖付都是他付親的母親。設(shè):個體域：人;P(x，y):x是y的外祖母，Q(x，y):x是y的母親，則邏輯符號化為: 一個n個元累的集合A上的偏序關(guān)系，元素最多有 個。誚同邏輯的合式公式屮不#在flltl變元，該公式被稱為 的。 三根據(jù)要求解答:【(21)?(24)必做，(25)?(26)任選一題，寫在答題紙上】(12%)某三元哀值函數(shù)f(p，q.r)為：f(0.0,0)=0,f(0,0,1)=1,f(0,1，0)=0,f(0,1,1)=1,f(l,0,0)=1,f(L0,1)=1,f(l,1,0)=0.f(l,1，1)=1,試用僅介聯(lián)結(jié)詞o的命題形式來表示f。(15%)每個旅客成少頭等艙成二等艙，毎個旅客當(dāng)且僅當(dāng)他富裕時才少頭等艙，有些旅客宮裕但并非所有旅客富裕，所以有些旅客坐二等艙。(15%)己知&和R2都是A上等價關(guān)系，且卽R2=R2°Ru證明Ri。R2也是A上的等價關(guān)系。(9%)用特征函數(shù)證明下式成立的充要條件：A十B=0。(9%)己知A上的二元關(guān)系R滿足Rn=R,則R,R2，R3，."，Rn中的哪個可確定具有nJ*傳遞性。(9%)寫出{a，b，c}I?.的所有滿足f°f=IA的函數(shù)。(21)解：因?yàn)槌烧尜x值較多，較為簡便的是采川主合取范式，得到一種形式fo(pVqVr)A(pV-^qVr)A(-.pV-^qVr)O(pVqVr)A(-iqVi.)<=>((pVq)A->q)VrO(pA^q)Vr (可以用卡諾圖直接得到)<=>-n(-,pVq)Vr(22)解：符號化P(x):x坐頭等艙，Q⑻:x坐二等艙，R(x):x富裕；個體域：所有旅客。前提：Vx(P⑻vQ⑻)，Vx(P(x>~>R(x))，彐xR(x)a-iVxR(x)：結(jié)論：3xQ(x)證明：TOC\o"1-5"\h\z彐xR(x)a-iVxR(x) P-.VxR(x) T(1)I3x-,R(x) T(2)E-.R(a) T(3)￡ZVx(P(x)<->R(x)) PP(a)^>R(a) T(5)67(P(a) R(a))a(R(a) Q(a))T(6)EP(a)R(a) T(7)I-P(a) T(4)(8)IVx(P(x)vQ(x)) PP(a)vQ(a) T⑽W⑽ P(a)vQ(a) T(H)IQ(a) T(9)(12)I3xQ(x) T⑽沉(23)證明等價關(guān)系，就是證明JC具有H反、對稱、傳遞性質(zhì)。久和^是等價關(guān)系，所以都具有H反、對稱、傳遞性。(A)自反性：對于任何的xEA.因?yàn)镽:和R:都是H反的，<x,x>ER:，<x，x>eR:，所以〈X，x>eR1R;,具有A反性。B對稱性：對丁?任何的x，yEA，<x，y>eR.°R;3<x,y>￡RlcR2=R:°R:=>3t(<X,t>^R±A<t,y>FR:)(如果不清楚用還是O,則盡可能用=>3t?t,x>eR：a<y,t>eR:)(R1和R2是對稱的)<y,x〉ER，R2R，R:具有對稱性。C可傳遞性：對于任何的x，y,zEA.如果<x,y>eRx0R:,<y,z>^R2則<x,z>GR^R2oR.cR2=RioRjoR,-^Cl:直接應(yīng)用關(guān)系式Ri^RiCR：因?yàn)镽,,R:是可傳遞的，所以R”R2-R2cr2<x,z〉E么。!^。^。!^彐t(<x,t>GR：°R1a<t,z>GR;oR;)=>3t?x,t>eRta<t,z>eR2)(因?yàn)镽rR:R”R2^R2CR:)=><x,z>eRxcR,C2:也可按照步驟一步一步的證明：<x,z〉EHR，R:=>彐t(<x,t>GRx°Ria<t，z>ER:°R：)=>3t(3ti?x,ti>^RiA<ti,t>GRi)A彐t：(<t,t:>GR;A<t：,Z>GR;))=>3t?x,t>GR;A<t,z>eR,)(因?yàn)镽pR2是可傳遞的)=><x,z>^Ri°R2)R：°R：具有可傳迎性。所以匕見是等價關(guān)系。XAeB=0XAuB-A^B=0Xa+Xb-XaXb—(Xa+Zb—XaZb)XaXb=0Xa+Xb-XaXb-XaXaXb+XbXaXb~XAXbXaXb=0Xa+Xb一XaZb一XaXb+XaZb一XaZb=0XaZa+Xb/b-XaXb-Xa/b=0(Xa-Xb)2=0Xa=XbA=B沒 可傳遞性，則RX?RX^Rxx是1，2