《離散數(shù)學(xué)》期末試卷（含答案）

學(xué)院姓名學(xué)號(hào)任課老師選課號(hào)………密………封………線………以………內(nèi)………答………題………無(wú)………效……第1頁(yè)共6頁(yè)電子科技大學(xué)二零二至二零二學(xué)年第二學(xué)期期末考試離散數(shù)學(xué)課程考試題B卷（120分鐘）考試形式：閉卷考試日期年月日課程成績(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、試述樹(shù)的定義。4、試述格同態(tài)的定義。四、判斷分析改錯(cuò)題(如果正確，說(shuō)明理由，如果不正確，舉例說(shuō)明)（4×5＝20分）“若R，S是集合A上的反自反的二元關(guān)系，則RS也是反自反的二元關(guān)系?！边@句話對(duì)嗎？為什么？等價(jià)公式“（x）(G(x)H(x))＝（x）G(x)（x）H(x)”成立嗎？如果成立，說(shuō)明理由，如果不成立，舉例說(shuō)明。 “無(wú)向簡(jiǎn)單圖中的每條邊都必須在一個(gè)連通分支中?！边@句話對(duì)嗎？為什么？“設(shè)<G,>是滿足消去律的二元代數(shù)系統(tǒng)，且幺元存在，則G中除幺元外無(wú)其它冪等元。”這句話對(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è)無(wú)有向圖，用鄰接矩陣計(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ù)；所有的無(wú)理數(shù)也是實(shí)數(shù)；虛數(shù)不是實(shí)數(shù)。因此，虛數(shù)即不是有理數(shù)也不是無(wú)理數(shù)。2、設(shè)是兩個(gè)函數(shù)，證明：(1)若為滿射，則為滿射；(2)若為單射，則為單射設(shè)<L,≤>是一有界分配格，L1是L中所有具有補(bǔ)元的元素構(gòu)成的集合。試證明：<L1,≤>是<L,≤>的子格。離散數(shù)學(xué)期末考試標(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、答：連通而不含回路的無(wú)向圖稱為無(wú)向樹(shù)，簡(jiǎn)稱樹(shù)。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è)無(wú)向簡(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是連通分支矛盾。故無(wú)向簡(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,*>有么元，可逆元，但沒(méi)有零元.――(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,*>無(wú)零元；――(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是無(wú)理數(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――(0.5分)⑨N(x)→┐C(x)T，④，⑦，I――(0.5分)⑩(Q(x)→┐C(x))∧(Q(x)→┐C(x))T，⑧，⑨，E――(0.5分)11(C(x)→┐Q(x)∧┐N(x))T，⑩，E――(0.5分)12(x)(C(x)→┐Q(x)∧┐N(x))UG，11――(0.5分)2、證明（1）對(duì)任意cC,由fg是滿射，所以存在aA，使得fg(a)=c,即g(f(a))=c。――(2分)所以存在b=f(a)B，使得g(b)=c，由c的任意性，所以g是滿射。――(2分)（2）對(duì)任意a1,a2C(a1≠a2),由fg是單射，有fg(a1)≠fg(a2),即g(f(a1))≠g(f(a2))。――(3分)因g是函數(shù)，所以，f(a1)≠f(a2)。所以f是單射。――(1分)3、證明設(shè)<L,,,0,1>是有界分配格，并設(shè)A是所有有補(bǔ)元構(gòu)成的集合。――(1分)由于0和1有補(bǔ)元，所以0,1∈A，于是A非空。――(1分)又對(duì)任意的a,b∈A，設(shè)a,b的補(bǔ)元分別是和，因?yàn)?a*b)*()=(a*b*)(a*b*)=((a*)*b)(a*(b*))=(0*b)(a*0)=00=0；――(1.5分)(a