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

學院姓名學號任課老師選課號………密………封………線………以………內(nèi)………答………題………無………效……第1頁共6頁電子科技大學二零二至二零二學年第二學期期末考試離散數(shù)學課程考試題B卷（120分鐘）考試形式：閉卷考試日期年月日課程成績構(gòu)成：平時分，期中分，實驗分，期末分一二三四五六七八九十合計一、單選題（四選一）（10×1＝10分）如果命題公式G=P∧Q，則下列之一哪一個成立（）。1).G=(P→Q) 2).G=(P→Q) 3).G=(P→Q) 4).G=(P→Q)設(shè)Φ是一個空集，則下列之一哪一個不成立（）。1).Φ∈Φ 2).ΦΦ 3).Φ∈{Φ} 4).Φ{Φ}謂詞邏輯的推理中，使用的是規(guī)則（ ）。1).ES 2).US 3).UG 4).EG在集合｛0，1｝上可定義（）個不同的二元運算。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中長度為2的回路總數(shù)為（ ）。1).1 2).2 3).4 4).5下列圖中（ ）即非歐拉圖又非哈密爾頓圖。1).2).3).4).設(shè)G是一個7階群，則該群一定有（）個不變子群。1).2 2).4 3).6 4).8設(shè)G是連通的平面圖，設(shè)n、m、r分別為G的頂點數(shù)，邊數(shù)和面數(shù)，則有：n－m＋r＝()。1).1 2).2 3).3 4).4設(shè)G是一個24階群，a是G中任意一個元素，則a的周期一定不是（）。1).2 2).8 3).16 4).24二、多項選擇題（五選二至五）（5×1＝5分）設(shè)G=PQ是僅含原子P和Q的命題公式，則G是（ ）。1).短語2).析取范式3).合取范式4).主析取范式5).主合取范式下列哈斯圖中，是格的有（）。1). 2). 3). 4). 5). 若<G,*>是一個13階群，則運算“*”一定滿足（）。1).交換律 2).消去律3.冪等律 4).結(jié)合律5).分配律下列謂詞的蘊涵公式中，錯誤的有（ ）。 1). 2).3). 4).5).非空集合A上的恒等關(guān)系具有（ ）。 1).自反性 2).反自反性 3).對稱性4).反對稱性 5).傳遞性三、簡答題（4×2=8分）1、試述冪集的定義。2、設(shè)R是集合A上的二元關(guān)系，試述R是傳遞性的定義。3、試述樹的定義。4、試述格同態(tài)的定義。四、判斷分析改錯題(如果正確，說明理由，如果不正確，舉例說明)（4×5＝20分）“若R，S是集合A上的反自反的二元關(guān)系，則RS也是反自反的二元關(guān)系?！边@句話對嗎？為什么？等價公式“（x）(G(x)H(x))＝（x）G(x)（x）H(x)”成立嗎？如果成立，說明理由，如果不成立，舉例說明。 “無向簡單圖中的每條邊都必須在一個連通分支中?！边@句話對嗎？為什么？“設(shè)<G,>是滿足消去律的二元代數(shù)系統(tǒng)，且幺元存在，則G中除幺元外無其它冪等元?！边@句話對嗎？為什么？五、計算題（4×8＝32分）設(shè)有合適公式(x)P(x)(x)Q(f(a)，x)，給定如下解釋：個體域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，計算該合適公式在給定的解釋下的真值。設(shè)A＝{1,2,3,4,5,6,7,8,9},R={<x,y>|x,y∈A且3|(x-y)}，則R是等價關(guān)系，計算商集A/R。下圖為一個無有向圖，用鄰接矩陣計算該圖中長度為3的所有通路和回路總數(shù)。設(shè)有代數(shù)系統(tǒng)<Z,*>，其中Z是整數(shù)集合，運算“*”定義如下：a,b∈Z，有：a*b=a+b+2。試驗證該代數(shù)系統(tǒng)是否存在有幺元，零元，可逆元，如果存在則請求出幺元，零元，每個元素的逆元。六、證明題（共25分）1、所有的有理數(shù)都是實數(shù)；所有的無理數(shù)也是實數(shù)；虛數(shù)不是實數(shù)。因此，虛數(shù)即不是有理數(shù)也不是無理數(shù)。2、設(shè)是兩個函數(shù)，證明：(1)若為滿射，則為滿射；(2)若為單射，則為單射設(shè)<L,≤>是一有界分配格，L1是L中所有具有補元的元素構(gòu)成的集合。試證明：<L1,≤>是<L,≤>的子格。離散數(shù)學期末考試標準答案一、單項選擇題：評分標準：對1個給1分(2) (1)(3)(4)(2)(2)(2)(2)(2)(3)二、多項選擇題：評分標準：完全正確1個給1分，否則不給分（1，2，3，4，5）（2，3，4）（1，2，4）（2，4，5）（1，3，4，5）三、簡答題：評分標準：答對大意給2分1、答：設(shè)A為集合，把A的全體子集構(gòu)成的集合叫做A的冪集。2、答：設(shè)R是集合A上的二元關(guān)系，對任意的x,y,z∈A，如果<x,y>∈R且<y,z>∈R，那么<x,z>∈R，則稱關(guān)系R是傳遞的，或稱R具有傳遞性。3、答：連通而不含回路的無向圖稱為無向樹，簡稱樹。4、答：設(shè)<L,∧,∨>和<S,*,>是兩個格，ψ是L到S的映射。如果對任意x,y∈L，都有ψ(x∧y)=ψ(x)*ψ(y)，ψ(x∨y)=ψ(x)ψ(y)則稱ψ為從格<L,∧,∨>到格<S,*,>的格同態(tài)映射，簡稱格同態(tài)。四、判斷分析改錯題：評分標準：判斷正確給3分，理由正確給2分。判斷錯誤則不給分。1、答：不是。例如：A＝{1,2}，A上的關(guān)系R＝{<1,2>}、S＝{<2,1>}均反自反，但RS＝{<1,1>}不反自反。2、答：不成立。例如：①個體域為D={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、答：對。假設(shè)無向簡單圖G中存在一條邊(u,v)不在任何一個連通分支中。若u、v在同一個連通分支P中，則P∪(u,v)是G的子圖且仍然是連通的，這與P是連通分支矛盾；若u、v不在同一個連通分支中，設(shè)u在連通分支P中，v在連通分支Q中，則P∪(u,v)∪Q是G的子圖且然是連通的，這與P是連通分支矛盾。故無向簡單圖中的每條邊都必須在一個連通分支中。4、答：對。假設(shè)a是G中非幺元e的冪等元，即a*a=a，且a≠e。因此a*a=a*e，由消去律知a=e，矛盾。五、計算題（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)對"x?A，有3|(x-x)，所以<x,x>?R，即R是自反的。――（1分）(2)對"x,y?A，若<x,y>?R，即3|(x-y)，所以3|(y-x)，所以，<y,x>?R，即R是對稱的。――（1分）(3)對"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上的等價關(guā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分)即右圖中長度為3的通路(含回路)總數(shù)為48，其中10條為回路。――(1分)4解<Z,*>有么元，可逆元，但沒有零元.――(1分)因為存在-2∈Z，使得對任意a∈Z，有a*(-2)=a+(-2)+2=a，2*a=(-2)+a+2=a.故－2是<Z,*>的幺元；――(2分)不存在x∈Z，使得對任意a∈Z，有a*x=x*a=x.故<Z,*>無零元；――(2分)對任意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中每個元素都有逆元。――(3分)六、證明題（共25分,第1題9分，第2，3題各8分）1、解：設(shè)Q(x)：x是有理數(shù)；R(x)：x是實數(shù)；N(x)：x是無理數(shù)；C(x)：x是虛數(shù)，則上述句子可符號為：(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）對任意cC,由fg是滿射，所以存在aA，使得fg(a)=c,即g(f(a))=c。――(2分)所以存在b=f(a)B，使得g(b)=c，由c的任意性，所以g是滿射。――(2分)（2）對任意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是所有有補元構(gòu)成的集合。――(1分)由于0和1有補元，所以0,1∈A，于是A非空。――(1分)又對任意的a,b∈A，設(shè)a,b的補元分別是和，因為(a*b)*()=(a*b*)(a*b*)=((a*)*b)(a*(b*))=(0*b)(a*0)=00=0；――(1.5分)(a