【正文】 2； C．3； D．4。三、證明 26%R是集合X上的一個自反關(guān)系，求證：R是對稱和傳遞的，當且僅當 a, b 和在R中有在R中。（8分）f和g都是群到 G2, *的同態(tài)映射，證明是的一個子群。其中C=(8分)G=(|V| = v，|E|=e)是每一個面至少由k（k 3）條邊圍成的連通平面圖，則，由此證明彼得森圖（Peterson）圖是非平面圖。（11分）四、邏輯推演 16%用CP規(guī)則證明下題（每小題 8分）五、計算 18%設(shè)集合A={a，b，c，d}上的關(guān)系R={ , b , a , b, c , c , d }用矩陣運算求出R的傳遞閉包t(R)。（9分）如下圖所示的賦權(quán)圖表示某七個城市 及預先算出它們之間的一些直接通信線路造價，試給出一個設(shè)計方案，使得各城市之間能夠通信而且總造價最小。（9分）試卷一答案：一、填空 20%（每小題2分）{0，1，2，3，4，6}；2；1；4； 1；{, , , }；{,} IA ；a ；a , b , c ,d ；a , d , c , d ；c。二、選擇 20%（每小題 2分）題目 1 2 3 4 5 6 7 8 9 10答案 C D B、C C A D C A D B A三、證明 26%證：“ ” 若 由R對稱性知，由R傳遞性得“ ” 若，有 任意，因 若 所以R是對稱的。若，則 即R是傳遞的。證，有，又★ ★★ C , ★ 是 G1 , ★的子群。證：①設(shè)G有r個面，則，即。而 故 即得。（8分）②彼得森圖為，這樣 不成立，所以彼得森圖非平面圖。（3分）二、邏輯推演 16%證明：① P（附加前提）② T①I ③ P④ T②③I ⑤ T④I ⑥ T⑤I ⑦ P⑧ T⑥⑦I ⑨ CP證明① P（附加前提）② US①③ P ④ US③⑤ T②④I ⑥ UG⑤⑦ CP三、計算 18%解：，t(R)={ , , a , c , , , b ,b , b , c. , b , d , c , d }解： 用庫斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：樹權(quán)C(T)=23+1+4+9+3+17=57即為總造價。第五篇：離散數(shù)學試題+答案 專注于收集各類歷年試卷和答案一、單項選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。，如果它的所有結(jié)點的度數(shù)都是偶數(shù)，那么它具有一條（） ，G中有11個頂點5個面，則G中的邊是（） ，表達式(a∧b)∨(a∧b∧c)∨(b∧c)的等價式是（）∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)，是復數(shù)乘法運算，則G=是群，下列是G的子群是（）A.B.〈{1},〉C.〈{i},〉D.〈{i},〉，A為集合，A的冪集為P(A),+、/為數(shù)的加、減、除運算，∩為集合的交運算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有（）A.〈Z，+，/〉B.〈Z，/〉 C.〈Z，，/〉D.〈P(A)，∩〉 （）A.〈Q，*〉Q是全體有理數(shù)集，*是數(shù)的乘法運算B.〈Mn(R),*〉,Mn(R)是全體n階實矩陣集合，*是矩陣乘法運算 C.〈Z，o〉，Z是整數(shù)集，o定義為xoxy=xy,x,y∈Z D.〈Z，+〉，Z是整數(shù)集，+是數(shù)的加法運算={1,2,3}，A上二元關(guān)系R的關(guān)系圖如下： R具有的性質(zhì)是 ={a,b,c}，A上二元關(guān)系R={〈a,a〉，〈b,b〉〈,a,c〉}，則關(guān)系R的對稱閉包S(R)是（）∪IA∪{〈c,a〉}∩IA ={a,b,c},Ix是X上恒等關(guān)系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R為X上的等價關(guān)系，R應(yīng)?。ǎ〢.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉} （）∈198?，瓹.{198。}205。198。D.{198。}∈198。：論域D為實數(shù)集，a=0,f(x,y)=xy,A(x,y):x 專注于收集各類歷年試卷和答案D.(x)(y)(A(x,y)→A(f(x,a),a))，謂詞公式(x)(A(x)→B)等價于（）A.($x)A(x)→BB.(x)A(x)→B (x)→BD.(x)A(x)→(x)B (x)(P(x,y))→($z)Q(x,z)∧(y)R(x,y)中變元x（） ：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號化為（）∨Q∧┐Q→┐Q∨┐Q ，為永假式的是（）→(p∨q∨r)B.(p→┐p)→┐p C.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)二、填空題(每空1分，共20分)，僅有一個結(jié)點的入度為______，稱為樹根，其余結(jié)點的入度均為______。={1,2,3,4}上二元關(guān)系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的關(guān)系矩陣MR中m24=______,m34=______?！磗,*〉是群，則那么s中除______外，不可能有別的冪等元；若〈s,*〉有零元，則|s|=______。，P(A)為A的冪集，則〈P(A)，是格，若x,y∈P(A),則x,y最大下界是______，205?！底钚∩辖缡莀_____。:X→Y,如果對X中的任意兩個不同的x1和x2，它們的象y1和y2也不同，我們說f是______函數(shù)，如果ranf=Y，則稱f是______函數(shù)。，其等價類記為〔x〕R。x,y∈A，若〈x,y〉∈R，則 〔x〕R與〔y〕R的關(guān)系是______，而若〈x,y〉207。R，則〔x〕R∩〔y〕R=______。($x)($y)(A(x)∧B(y))219。($x)A(x)∧($y)B(y)成立的條件是______不含有y，______不含有x。(x):x是人，D(s):x是要死的，則命題“所有的人都是要死的”可符號化為(x)______,其中量詞(x)的轄域是______?！腍2∧?∧Hn是______，則稱H1,H2,?Hn是相容的，若H1∧H2∧?∧Hn是______，則稱H1,H2,?Hn是不相容的。，首先要看它是否為，然后再看它是否具有唯一的。三、計算題(共30分)26.(4分)設(shè)有向圖G=(V,E)如下圖所示，試用鄰接矩陣方法求長度為2的路的總數(shù)和回路總數(shù)。27.(5)設(shè)A={a,b},P(A)是A的冪集，197。是對稱差運算，可以驗證是群。設(shè)n是正整數(shù)，求({a}1{a})n197。{a}nn{a}n 28.(6分)設(shè)A={1,2,3,4,5},A上偏序關(guān)系R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA。 專注于收集各類歷年試卷和答案(1)作出偏序關(guān)系R的哈斯圖(2)令B={1,2,3,5}，求B的最大，最小元，極大、極小元，上界，下確界，下界，下確界。29.(6分)求┐(P→Q)219。(P→┐Q)的主合取范式并給出所有使命題為真的賦值。30.(5分)設(shè)帶權(quán)無向圖G如下，求G的最小生成樹T及T的權(quán)總和，要求寫出解的過程。31.(4分)求公式┐((x)F(x,y)→($y)G(x,y))∨($x)H(x)的前束范式。四、證明題(共20分)32.(6分)設(shè)T是非平凡的無向樹，T中度數(shù)最大的頂點有2個，它們的度數(shù)為k(k≥2),證明T中至少有2k2片樹葉。33.(8分)設(shè)A是非空集合，F(xiàn)是所有從A到A的雙射函數(shù)的集合，o是函數(shù)復合運算。證明：〈F, o〉是群。34.(6分)在個體域D={a1,a2,?，an}中證明等價式：($x)(A(x)→B(x))219。(x)A(x)→($x)B(x)五、應(yīng)用題(共15分)35.(9分)如果他是計算機系本科生或者是計算機系研究生，那么他一定學過DELPHI語言而且學過C++語言。只要他學過DELPHI語言或者C++語言，那么他就會編程序。因此如果他是計算機系本科生，那么他就會編程序。請用命題邏輯推理方法，證明該推理的有效結(jié)論。36.(6分)一次學術(shù)會議的理事會共有20個人參加，他們之間有的相互認識但有的相互不認識。但對任意兩個人，他們各自認識的人的數(shù)目之和不小于20。問能否把這20個人排在圓桌旁，使得任意一個人認識其旁邊的兩個人?根據(jù)是什么?參考答案一、單項選擇題(本大題共15小題，每小題1分，共15分)二、填空題 0 ∩yx∪y 滿射21.［x］R=［y］R (x)B(y)23.(M(x)→D(x))M(x)→D(x) 專注于收集各類歷年試卷和答案永假式(或矛盾式)真值三、計算題=237。253。1011239。239。239。238。0011239。254。236。2239。2239。M=237。239。2239。238。1110252。111239。239。253。121239。011239。254。M2ij=18,ij=6 229。M2i=1229。229。i=1j=144G中長度為2的路總數(shù)為18，長度為2的回路總數(shù)為6。，x∈P(A),xn=198。當n是奇數(shù)時，x∈P(A),xn=x于是：當n是偶數(shù)，(｛a｝1｛b｝｛a｝)n197。｛a｝n｛b｝n｛a｝n=198。197。(｛a｝1)n｛b｝n｛a｝n=198。197。198。=198。當n是奇數(shù)時，(｛a｝1｛b｝｛a｝)n197。｛a｝n｛b｝n｛a｝n=｛a｝1｛b｝｛a｝197。(｛a｝1)n｛b｝n｛a｝n=｛a｝1｛b｝｛a｝197。｛a｝1｛b｝｛a｝=198。 28.(1)偏序關(guān)系R的哈斯圖為(2)B的最大元：無，最小元：無；極大元：2，5，極小元：1，3下界：4，下確界4；上界：無，上確界：無(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))(┐(P∧┐Q)∨(P∧┐Q))(P∧Q)∨(P∧┐Q)P∧(Q∨┐Q)P∨(Q∧┐Q)(P∨Q)∧(P∨┐Q)命題為真的賦值是P=1,Q=0和P=1,Q=1 專注于收集各類歷年試卷和答案=(v1,v3)，e2=(v4,v6)e3=(v2,v5)，e4=(v3,v6)e5=(v2,v3)，e6=(v1,v2)e7=(v1,v4)，e8=(v4,v3)e9=(v3,v5)，e10=(v5,v6)令ai為ei上的權(quán)，則a1取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的總權(quán)和=1+2+3+4+5=15 ┐(x1F(x1,y)→$y1G(x,y1))∨$x2H(x2)(換名)219。┐$x1$y1(F(x1,y)→G(x,y1))∨$x2H(x2)219。x1y1┐(F(x1,y1)→G(x,y1))∨$x2H(x2)219。x1y1$x2(┐(F(x1,y1)→G(x,y1))∨H(x2)四、證明題，y個分支點。于是T中有x+y個頂點，有x+y1 條邊，由握手定理知T中所有頂點的度數(shù)之的x+y229。d(vi)=2(x+y1)。i=又樹葉的度為1，任一分支點的度大于等于2且度最大的頂點必是分支點，于是x+y229。d(vi)≥x1+2(y2)+k+k=x+2y+2K4 i=1從而2(x+y1)≥x+2y+2k4x≥2k2 ：由于集合A是非空的，故顯然從A到A的雙射函數(shù)總是存在的，如A上恒等函數(shù)，因此F非空(1)f,g∈F,因為f和g都是A到A的雙射函數(shù)，故fog也是A到A的雙射函數(shù)，從而集合F關(guān)于運算o是封閉的。(2)f,g,h∈F,由函數(shù)復合運算的結(jié)合律有fo(goh)=(fog)oh故運算o是可結(jié)合的。(3)A上的恒等函數(shù)IA也是A到A的雙射函數(shù)即IA∈F,且f∈F有IAof=foIA=f,故IA是〈F，o〉中的幺元(4)f∈F,因為f是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有fof1=f1of=IA,因此f1是f的逆元由此上知〈F，o〉是群($x)(A(x)→B(x))219。 $x(┐A(x)∨B(x)) 專注于收集各類歷年試卷和答案219。(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨?∨(┐A(an)∨B(an)))219。(┐A(a1)∨A(a2)∨?∨┐A(an)∨(B(a1)∨B(a2)∨?∨(B(an))219。┐(A(a1)∧A(a2)∧?∧A(an))∨(┐B(a1)∨B(a2)∨?∨(B(an))219。┐(x)A(x)∨($x)B(x)219。(x)A(x)→($x)B(x)五、應(yīng)用題：他是計算機系本科生q：他是計算機系研究生r：他學過DELPHI語言s:他學過C++語言t:他會編程序前提：(p∨q)→(r∧s),(r∨s)→t結(jié)論：p→t證①pP(附加前提)②p∨qT①I③(p∨q)→(r∧s)P(前提引入)④r∧sT②③I⑤rT④I⑥r(nóng)∨sT⑤I⑦(r∨s)→tP(前提引入)⑧tT⑤⑥I ，使得任一人認識其旁邊的兩個人。根據(jù)：構(gòu)造無向簡單圖G=,其中V={v1,v2,?，V20}是以20個人為頂點的集合，E中的邊是若任兩個人vi和vj相互認識則在vi與vj之間連一條邊。Vi∈V,d(vi)是與vi相互認識的人的數(shù)目，由題意知vi,vj∈V有d(vi)+d(vj)179。20,于是G中存在漢密爾頓回路。設(shè)C=Vi1Vi2?Vi20Vi1是G中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。