學(xué)院系別姓名學(xué)號(hào)………密………封………線………以………內(nèi)………答………題………無………效……第5頁(yè)共6頁(yè)電子科技大學(xué)至學(xué)年第二學(xué)期期末（B卷）課程考試題（分鐘）考試形式：考試日期2005年月日一二三四五六七八九十總分評(píng)卷教師一、選擇題（1～15是單選，16～20是多選，單選每小題1分，多選每小題2分，共計(jì)25分）1.下列公式中，那一個(gè)是永假的（ ）。 A、(P∧Q)→P B、(P∨Q)→P C、P→(P∨Q) D、((P∧Q)→Q）2.下列公式中，哪一個(gè)不是析取范式（ ）。 A、P∨Q B、P∧Q C、(P∨Q) D、(P∧Q)3、如果命題公式G=P∧Q，則下列之一哪一個(gè)等價(jià)（）。A、G=(P→Q) B、G=(P∨Q) C、G=(P→Q) D、G=(P→Q)4、設(shè)X、Y是兩個(gè)集合|X|＝m，|Y|＝n，則從X到Y(jié)可產(chǎn)生（）個(gè)不同的函數(shù)。A、nm B、mn C、m×n D、2m×n5、設(shè)G是具有n個(gè)結(jié)點(diǎn)的有向完全圖，則G中有（）條邊。A、n2 B、n(n－1) C、2n(n－1) D、6、下列公式中，是永真式的是()。A、P∨1 B、P→T C、P∨T D、P∧T7、下列公式中，（）是析取范式。A、(P∧Q) B、(P∨Q) C、(P∨Q) D、(P∧Q)8、下面哪一種格不是特殊格（）。A、子格 B、分配格 C、模格 D、有界格9、5個(gè)結(jié)點(diǎn)7條邊的簡(jiǎn)單圖共有（）種。A、2 B、3 C、5 D、710、下列圖中，（）是平面圖。 A、B、 C、 D、11、每個(gè)無向樹至少有（）片樹葉。A、1B、2 C、3 D、412、每個(gè)無限循環(huán)群有（）個(gè)生成元。A、1 B、2 C、3 D、413、設(shè)R是集合A＝{1,2,3}上的二元關(guān)系，R＝{<2,1>,<2,3>,<1,3>},則下列（）不成立。A、R是自反關(guān)系 B、R是反自反關(guān)系 C、R是反對(duì)稱關(guān)系 D、R是傳遞關(guān)系14、設(shè)G是一個(gè)18階群，a是G中任意一個(gè)元素，則a的周期一定不是（）。A、2 B、4 C、9 D、615、命題公式A與B是等價(jià)的，是指（D）。A、A與B有相同的原子變?cè)? B、A與B是可滿足的C、當(dāng)A的真值為真時(shí)，B的真值也為真 D、A與B有相同的真值16、設(shè)R、S是集合A上的關(guān)系，則下述（ ）不一定成立。A若R、S傳遞，則傳遞 B若R、S對(duì)稱，則對(duì)稱C若R、S自反，則自反 D若R、S反自反，則反自反5142376E若514237617、下列圖中，那些是右圖的強(qiáng)分圖。（）1423142314231436565A B C D E18、下列圖中，存在完美匹配的圖是（）19、下列哈斯圖中，不是格的有（）。 A B C D E20、若<G,*>是一個(gè)群，則運(yùn)算“*”不一定滿足（）。A、交換率 B、消去律 C、冪等律 D、分配律二、名詞解釋（每小題3分，共15分）1、什么叫謂詞公式的解釋。2、試述函數(shù)中滿射函數(shù)的定義。3、敘述極大連通分支的定義。4、試述代數(shù)系統(tǒng)中子代數(shù)的定義。5、試述格的定義三、判斷分析改錯(cuò)題（每小題5分，共10分）1、設(shè)<Z，+>是一個(gè)代數(shù)系統(tǒng)，Z是正整數(shù)集合，“＋”是一般的加法運(yùn)算，Z上的函數(shù)f為：f(x)=5x-7，則函數(shù)f能構(gòu)成代數(shù)系統(tǒng)的自同構(gòu)嗎？為什么？2、設(shè)A，B，C為任意命題公式。已知，問嗎？bacdefgbacdefg1、設(shè)集合A＝｛a,b,c,d,e,f,g｝上的偏序關(guān)系如右圖所示,求A的最大元、最小元、極大元和極小元，并求A的子集B＝｛a,b,c,d｝的上確界和下確界。2、設(shè)個(gè)體域D={a,b,c}，消去以下各式中的量詞：（1）；（2）3、求命題公式(PQ)R的主析取范式和主合取范式。4、設(shè)是群，運(yùn)算“”定義如下：，有：試驗(yàn)證該代數(shù)系統(tǒng)是否是一個(gè)循環(huán)群？如是，請(qǐng)求出該循環(huán)群的全部生成元，幺元，每個(gè)元素的逆元。五、綜合證明題（共18分）將下面的推理符號(hào)化，然后用邏輯推理的方法證明之。 1、每個(gè)在學(xué)校讀書的人都獲得知識(shí)。所以如果沒有人獲得知識(shí)就沒有人在學(xué)校讀書。（個(gè)體域是人的集合）。2、設(shè)<G,*>是群，H，K是其子群，在G上定義二元關(guān)系R：使得。證明：R是G上的等價(jià)關(guān)系.電子科技大學(xué)二零零三至二零零四學(xué)年第二學(xué)期期末（B卷）課程考試題（分鐘）考試形式：考試日期2005年月日一二三四五六七八九十總分評(píng)卷教師一、選擇題（1～15是單選，16～20是多選，單選每小題1分，多選每小題2分，共計(jì)25分）1.D2.C3、B4、A5、B6、A7、D8、B9、B10、C11、A12、B13、A14、B15、D16、A,E17、D,E18、D19、A,B,E20、A,C,D二、名詞解釋（略）三、判斷分析改錯(cuò)題（每小題5分，共10分）1、答：不是。顯然，Z上的函數(shù)f既是單射又是滿射。但是對(duì)，有顯然，，即不滿足同態(tài)條件，因此函數(shù)f不能構(gòu)成代數(shù)系統(tǒng)的自同構(gòu)2、設(shè)A，B，C為任意命題公式。已知，問嗎？答：不一定。因?yàn)楫?dāng)，時(shí)，有同樣的真值T，此時(shí)，成立，但是，卻不成立。四、計(jì)算題（每小題8分，共32分）1、最大元最小元極大元極小元上界下界上確界下確界gdgdgdgd2、解：（1）（2）3、解：方法1PQRP→Q(P→Q)R0001000111010100111110001101001101011111主析取范式為（使公式為1的解釋所對(duì)應(yīng)的極小項(xiàng)的析?。?P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主合取范式為（使公式為0的解釋所對(duì)應(yīng)的極大項(xiàng)的合?。?P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)方法2：(P→Q)R=((P→Q)→R)∧(R→(P→Q))=((P→Q)∨R)∧(R∨(P→Q))=((P∨Q)∨R)∧(R∨P∨Q)=(((P)∧Q)∨R)∧(P∨Q∨R)=((P∧Q)∨R)∧(P∨Q∨R)=(P∨R)∧(Q∨R)∧(P∨Q∨R)=(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)∧(P∨Q∨R)=(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)=(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) 主合取范式=M0∧M2∧M5∧M6=m1∨m3∨m4∨m7=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) 主析取范式4、證明：a,b∈I，顯然a*b=a+b+2∈I，所以“*”關(guān)于I是封閉的。a,b,c∈I,(a*b)*c=(a*b)+c+2=(a+b+2)+c+2=a+(b+c+2)+2=a+(b*c)+2=a*(b*c),所以“*”是可結(jié)合的。存在-2∈I，使得a∈I，都有(-2)*a=a*(-2)=a+(-2)+2=a，所以-2是<I,*>的幺元。a∈I，存在-a-4∈I，使得a*(-4-a)=(-4-a)*a=a+(-4-a)+2=-2，所以-4-a是a的逆元。故<I,*>是群。設(shè)a是<I,*>的生成元，則存在i,j∈I,使得1＝ai＝ia+2(i-1)，2＝aj＝j(luò)a+2(j-1)，所以1＝2-1=ja+2(j-1)-(ia+2(i-1))=a(j-i)+2(j-i)，所以，因?yàn)閍∈I，所以j-i＝1或j-i＝-1，即a＝-1或a＝-3。當(dāng)a＝-1時(shí)，x∈I，存在x+2∈I，使得x=(-1)x+2。當(dāng)a＝-3時(shí)，x∈I，存在-x-2∈I，使得x=(-3)-x-2。故<I,*>是循環(huán)群，全部生成元為-1和-3，幺元為-2，每個(gè)元素a的逆元為-4-a。五、綜合證明題（共18分）將下面的推理符號(hào)化，然后用邏輯推理的方法證明之。 1、解：設(shè)f(x)：x是在學(xué)校讀書；g(x)：x獲得知識(shí)，則句子可以符號(hào)化為：證明：使用CP規(guī)則。P（附加前提）T,(1),EUS,(2)PUS,(4)T,(3),(5),IUG,(6)T,(7),E2、證明：①a∈G，因?yàn)?lt;G,*>是群，存在e∈G，使得a=e*a*e-1，由已知得<a,a>∈R，所以R是自反的。②a,b∈G，若<a,b>∈R，則存在Q,H∈G使得b=Q*a*H，因此a=Q-1*b*H-1。因?yàn)?lt;G,*>是群，Q-1,H-1∈G，因此<b,a>∈R，故R是對(duì)稱的。③a,b,c∈G，若<a,b>,<b,c>∈R，則存在Q1,Q2,Q1-1,Q2-1∈G使得b=Q2-1*a*Q1-1，c=Q2*b*Q1，因此c=Q2*(Q2-1*a*Q1-1)*Q1=e*a*e。因此<a,c>∈R，故R是傳遞的。綜上，由①、②、③知，R是集合G上的等價(jià)關(guān)系。電子科技大學(xué)至學(xué)年第二學(xué)期期末考試離散數(shù)學(xué)課程考試題B卷（120分鐘）考試形式：閉卷考試日期200年月日課程成績(jī)構(gòu)成：平時(shí)分，期中分，實(shí)驗(yàn)分，期末分一二三四五六七八九十合計(jì)一、單選題（四選一）（10×1＝10分）如果命題公式G=P∧Q，則下列之一哪一個(gè)成立（）。1).G=(P→Q) 2).G=(P→Q) 3).G=(P→Q) 4).G=(P→Q)設(shè)Φ是一個(gè)空集，則下列之一哪一個(gè)不成立（）。1).Φ∈Φ 2).ΦΦ 3).Φ∈{Φ} 4).Φ{Φ}謂詞邏輯的推理中，使用的是規(guī)則（ ）。1).ES 2).US 3).UG 4).EG在集合｛0，1｝上可定義（）個(gè)不同的二元運(yùn)算。1).2 2).4 3).8 4).16設(shè)集合A＝{a,b,c}，A上的二元關(guān)系R＝{<a,a>,<b,b>,<c,c>,<a,b>,<c,b>}，則R是A上的（ ）關(guān)系。1).擬序 2).偏序 3).全序 4).良序設(shè)圖G的鄰接矩陣為，則G中長(zhǎng)度為2的回路總數(shù)為（ ）。1).1 2).2 3).4 4).5下列圖中（ ）即非歐拉圖又非哈密爾頓圖。1).2).3).4).設(shè)G是一個(gè)7階群，則該群一定有（）個(gè)不變子群。1).2 2).4 3).6 4).8設(shè)G是連通的平面圖，設(shè)n、m、r分別為G的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)，則有：n－m＋r＝()。1).1 2).2 3).3 4).4設(shè)G是一個(gè)24階群，a是G中任意一個(gè)元素，則a的周期一定不是（）。1).2 2).8 3).16 4).24二、多項(xiàng)選擇題（五選二至五）（5×1＝5分）設(shè)G=PQ是僅含原子P和Q的命題公式，則G是（ ）。1).短語(yǔ)2).析取范式3).合取范式4).主析取范式5).主合取范式下列哈斯圖中，是格的有（）。1). 2). 3). 4). 5). 若<G,*>是一個(gè)13階群，則運(yùn)算“*”一定滿足（）。1).交換律 2).消去律3.冪等律 4).結(jié)合律5).分配律下列謂詞的蘊(yùn)涵公式中，錯(cuò)誤的有（ ）。 1). 2).3). 4).5).非空集合A上的恒等關(guān)系具有（ ）。 1).自反性 2).反自反性 3).對(duì)稱性4).反對(duì)稱性 5).傳遞性三、簡(jiǎn)答題（4×2=8分）1、試述冪集的定義。2、設(shè)R是集合A上的二元關(guān)系，試述R是傳遞性的定義。3、試述樹的定義。4、試述格同態(tài)的定義。四、判斷分析改錯(cuò)題(如果正確，說明理由，如果不正確，舉例說明)（4×5＝20分）“若R，S是集合A上的反自反的二元關(guān)系，則RS也是反自反的二元關(guān)系。”這句話對(duì)嗎？為什么？等價(jià)公式“（x）(G(x)H(x))＝（x）G(x)（x）H(x)”成立嗎？如果成立，說明理由，如果不成立，舉例說明。 “無向簡(jiǎn)單圖中的每條邊都必須在一個(gè)連通分支中。”這句話對(duì)嗎？為什么？“設(shè)<G,>是滿足消去律的二元代數(shù)系統(tǒng)，且幺元存在，則G中除幺元外無其它冪等元?！边@句話對(duì)嗎？為什么？五、計(jì)算題（4×8＝32分）設(shè)有合適公式(x)P(x)(x)Q(f(a)，x)，給定如下解釋：個(gè)體域D＝{1，0}，a＝0，f(1)＝0，f(0)＝1，P(0)＝0，P(1)＝1，Q(1，1)＝1，Q(1，0)＝1，Q(0，1)＝0，Q(0，0)＝0，計(jì)算該合適公式在給定的解釋下的真值。設(shè)A＝{1,2,3,4,5,6,7,8,9},R={<x,y>|x,y∈A且3|(x-y)}，則R是等價(jià)關(guān)系，計(jì)算商集A/R。下圖為一個(gè)無有向圖，用鄰接矩陣計(jì)算該圖中長(zhǎng)度為3的所有通路和回路總數(shù)。設(shè)有代數(shù)系統(tǒng)<Z,*>，其中Z是整數(shù)集合，運(yùn)算“*”定義如下：a,b∈Z，有：a*b=a+b+2。試驗(yàn)證該代數(shù)系統(tǒng)是否存在有幺元，零元，可逆元，如果存在則請(qǐng)求出幺元，零元，每個(gè)元素的逆元。六、證明題（共25分）1、所有的有理數(shù)都是實(shí)數(shù)；所有的無理數(shù)也是實(shí)數(shù)；虛數(shù)不是實(shí)數(shù)。因此，虛數(shù)即不是有理數(shù)也不是無理數(shù)。2、設(shè)是兩個(gè)函數(shù)，證明：(1)若為滿射，則為滿射；(2)若為單射，則為單射設(shè)<L,≤>是一有界分配格，L1是L中所有具有補(bǔ)元的元素構(gòu)成的集合。試證明：<L1,≤>是<L,≤>的子格。學(xué)期離散數(shù)學(xué)期末考試（B卷）標(biāo)準(zhǔn)答案一、單項(xiàng)選擇題：評(píng)分標(biāo)準(zhǔn)：對(duì)1個(gè)給1分(2) (1)(3)(4)(2)(2)(2)(2)(2)(3)二、多項(xiàng)選擇題：評(píng)分標(biāo)準(zhǔn)：完全正確1個(gè)給1分，否則不給分（1，2，3，4，5）（2，3，4）（1，2，4）（2，4，5）（1，3，4，5）三、簡(jiǎn)答題：評(píng)分標(biāo)準(zhǔn)：答對(duì)大意給2分1、答：設(shè)A為集合，把A的全體子集構(gòu)成的集合叫做A的冪集。2、答：設(shè)R是集合A上的二元關(guān)系，對(duì)任意的x,y,z∈A，如果<x,y>∈R且<y,z>∈R，那么<x,z>∈R，則稱關(guān)系R是傳遞的，或稱R具有傳遞性。3、答：連通而不含回路的無向圖稱為無向樹，簡(jiǎn)稱樹。4、答：設(shè)<L,∧,∨>和<S,*,>是兩個(gè)格，ψ是L到S的映射。如果對(duì)任意x,y∈L，都有ψ(x∧y)=ψ(x)*ψ(y)，ψ(x∨y)=ψ(x)ψ(y)則稱ψ為從格<L,∧,∨>到格<S,*,>的格同態(tài)映射，簡(jiǎn)稱格同態(tài)。四、判斷分析改錯(cuò)題：評(píng)分標(biāo)準(zhǔn)：判斷正確給3分，理由正確給2分。判斷錯(cuò)誤則不給分。1、答：不是。例如：A＝{1,2}，A上的關(guān)系R＝{<1,2>}、S＝{<2,1>}均反自反，但RS＝{<1,1>}不反自反。2、答：不成立。例如：①個(gè)體域?yàn)镈={a,b}；②G(a)指定為：1，G(b)指定為：0③H(a)指定為：0，H(b)指定為：1則（x）(G(x)H(x))為0，（x）G(x)（x）H(x)為1。故不等。3、答：對(duì)。假設(shè)無向簡(jiǎn)單圖G中存在一條邊(u,v)不在任何一個(gè)連通分支中。若u、v在同一個(gè)連通分支P中，則P∪(u,v)是G的子圖且仍然是連通的，這與P是連通分支矛盾；若u、v不在同一個(gè)連通分支中，設(shè)u在連通分支P中，v在連通分支Q中，則P∪(u,v)∪Q是G的子圖且然是連通的，這與P是連通分支矛盾。故無向簡(jiǎn)單圖中的每條邊都必須在一個(gè)連通分支中。4、答：對(duì)。假設(shè)a是G中非幺元e的冪等元，即a*a=a，且a≠e。因此a*a=a*e，由消去律知a=e，矛盾。五、計(jì)算題（4×8＝32分，每小題8分）1解(x)P(x)(x)Q(f(a),x)=(P(1)∧P(0))(Q(f(a),1)∨(f(a),1))――（4分）=(P(1)∧P(0))(Q(f(0),1)∨Q(f(0),1))――（1分）=(1∧0)(Q(1,1)∨Q(1,1))――（1分）=(0∧1)(1∨1)――（1分）=01＝1――（1分）2證明(1)對(duì)"x?A，有3|(x-x)，所以<x,x>?R，即R是自反的。――（1分）(2)對(duì)"x,y?A，若<x,y>?R，即3|(x-y)，所以3|(y-x)，所以，<y,x>?R，即R是對(duì)稱的。――（1分）(3)對(duì)"x,y,A?A，若<x,y>?R且<y,z>?R，有3|(x-y)且3|(y-z)，所以由(x-z)=(x-y)+(y-z)得3|(x-z)，所以，<x,z>?R，即R是傳遞的。――（2分）由(1)、(2)、(3)知，R是A上的等價(jià)關(guān)系。因?yàn)閇1]R＝{1,4,7}＝[4]R＝[7]R――（1分）[2]R={2,5,8}＝[5]R=[8]R――（1分）[3]R={3,6,9}=[6]R=[9]R――（1分）所以商集A/R＝{[1]R,[2]R,[3]R}={{1,4,7}，{2,5,8}，{3,6,9}}――（1分）3解右圖的鄰接矩陣為：――(2分)則――(2分)――(2分)從而，――(1分)即右圖中長(zhǎng)度為3的通路(含回路)總數(shù)為48，其中10條為回路。――(1分)4解<Z,*>有么元，可逆元，但沒有零元.――(1分)因?yàn)榇嬖?2∈Z，使得對(duì)任意a∈Z，有a*(-2)=a+(-2)+2=a，2*a=(-2)+a+2=a.故－2是<Z,*>的幺元；――(2分)不存在x∈Z，使得對(duì)任意a∈Z，有a*x=x*a=x.故<Z,*>無零元；――(2分)對(duì)任意a∈Z，存在4-a∈Z，使得a*(-4-a)=a+(-4-a)+2=-2，(-4-a)*a=-4-a+a+2=-2.故a的逆元是-4-a。由a的任意性知，Z中每個(gè)元素都有逆元。――(3分)六、證明題（共25分,第1題9分，第2，3題各8分）1、解：設(shè)Q(x)：x是有理數(shù)；R(x)：x是實(shí)數(shù)；N(x)：x是無理數(shù)；C(x)：x是虛數(shù)，則上述句子可符號(hào)為：(x)(Q(x)→R(x))，(x)(N(x)→R(x))，(x)(C(x)→┐R(x))(x)(C(x)→┐Q(x)∧┐N(x))。――(3分)①(x)(Q(x)→R(x))P②Q(x)→R(x)US，①――(1分)③(x)(N(x)→R(x))P④N(x)→R(x)US，③――(1分)⑤(x)(C(x)→┐R(x))P⑥C(x)→┐R(x)US，⑤――(1分)⑦R(x)→┐C(x)T，⑥，E――(0.5分)⑧Q(x)→┐C(x)T，②，⑦，I