《離散數(shù)學(xué)試題及答案 .doc》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)試題及答案 .doc（11頁珍藏版）》請在裝配圖網(wǎng)上搜索。

離散數(shù)學(xué)考試試題（A卷及答案） 一、（10分）某項工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？ (1)若A去，則C和D中要去1個人； (2)B和C不能都去； (3)若C去，則D留下。 解 設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：ACD，(B∧C)，CD必須同時成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D) F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三種派法：B∧D，A∧C，A∧D。 二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會議的每個成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。 解：論域：所有人的集合。()：是專家；()：是工人；()：是青年人；則推理化形式為： (()∧())，()(()∧()) 下面給出證明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）設(shè)A、B和C是三個集合，則AB(BA)。 證明：AB"x(x∈A→x∈B)∧$x(x∈B∧xA)"x(xA∨x∈B)∧$x(x∈B∧xA) $x(x∈A∧xB)∧"x(xB∨x∈A)$x(x∈A∧xB)∨"x(x∈A∨xB) ($x(x∈A∧xB)∧"x(x∈A∨xB))($x(x∈A∧xB)∧"x(x∈B→x∈A)) (BA)。 四、（15分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。 五、（10分）R是非空集合A上的二元關(guān)系，若R是對稱的，則r(R)和t(R)是對稱的。 證明 對任意的x、y∈A，若xr(R)y，則由r(R)＝R∪IA得，xRy或xIAy。因R與IA對稱，所以有yRx或yIAx，于是yr(R)x。所以r(R)是對稱的。 下證對任意正整數(shù)n，Rn對稱。 因R對稱，則有xR2y$z(xRz∧zRy)$z(zRx∧yRz)yR2x，所以R2對稱。若對稱，則xy$z(xz∧zRy)$z(zx∧yRz)yx，所以對稱。因此，對任意正整數(shù)n，對稱。 對任意的x、y∈A，若xt(R)y，則存在m使得xRmy，于是有yRmx，即有yt(R)x。因此，t(R)是對稱的。 六、（10分）若f：A→B是雙射，則f－1：B→A是雙射。 證明 因為f：A→B是雙射，則f－1是B到A的函數(shù)。下證f－1是雙射。 對任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f－1(y)＝x，所以f－1是滿射。 對任意的y1、y2∈B，若f－1(y1)＝f－1(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因為f：A→B是函數(shù)，則y1＝y(tǒng)2。所以f－1是單射。 綜上可得，f－1：B→A是雙射。 七、（10分）設(shè)是一個半群，如果S是有限集，則必存在a∈S，使得a*a＝a。 證明 因為是一個半群，對任意的b∈S，由*的封閉性可知，b2＝b*b∈S，b3＝b2*b∈S，…，bn∈S，…。 因為S是有限集，所以必存在j＞i，使得＝。令p＝j(luò)－i，則＝*。所以對q≥i，有＝*。 因為p≥1，所以總可找到k≥1，使得kp≥i。對于∈S，有＝*＝*(*)＝…＝*。 令a＝，則a∈S且a*a＝a。 八、（20分）（1）若G是連通的平面圖，且G的每個面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點數(shù)n有如下關(guān)系： m≤(n－2)。 證明 設(shè)G有r個面，則2m＝≥lr。由歐拉公式得，n－m＋r＝2。于是， m≤(n－2)。 （2）設(shè)平面圖G＝是自對偶圖，則| E|＝2(|V|－1)。 證明 設(shè)G*＝是連通平面圖G＝的對偶圖，則G*@ G，于是|F|＝|V*|＝|V|，將其代入歐拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。 離散數(shù)學(xué)考試試題（B卷及答案） 一、（10分）證明(P∨Q)∧(PR)∧(QS)S∨R 證明 因為S∨RRS，所以，即要證(P∨Q)∧(PR)∧(QS)RS。 (1)R 附加前提 (2)PR P (3)P T(1)(2)，I (4)P∨Q P (5)Q T(3)(4)，I (6)QS P (7)S T(5)(6)，I (8)RS CP (9)S∨R T(8)，E 二、（15分）根據(jù)推理理論證明：每個考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。 設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個體域：人的集合，則命題可符號化為："x(P(x)(A(x)∨B(x)))，"x(A(x)Q(x))，"x(P(x)Q(x))$x(P(x)∧B(x))。 (1)"x(P(x)Q(x)) P (2)"x(P(x)∨Q(x)) T(1)，E (3)$x(P(x)∧Q(x)) T(2)，E (4)P(a)∧Q(a) T(3)，ES (5)P(a) T(4)，I (6)Q(a) T(4)，I (7)"x(P(x)(A(x)∨B(x)) P (8)P(a)(A(a)∨B(a)) T(7)，US (9)A(a)∨B(a) T(8)(5)，I (10)"x(A(x)Q(x)) P (11)A(a)Q(a) T(10)，US (12)A(a) T(11)(6)，I (13)B(a) T(12)(9)，I (14)P(a)∧B(a) T(5)(13)，I (15)$x(P(x)∧B(x)) T(14)，EG 三、（10分）某班有25名學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)。 解 設(shè)A、B、C分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。則： |A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。 因為|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不會打這三種球的共5人。 四、（10分）設(shè)A1、A2和A3是全集U的子集，則形如Ai(Ai為Ai或)的集合稱為由A1、A2和A3產(chǎn)生的小項。試證由A1、A2和A3所產(chǎn)生的所有非空小項的集合構(gòu)成全集U的一個劃分。 證明 小項共8個，設(shè)有r個非空小項s1、s2、…、sr(r≤8)。 對任意的a∈U，則a∈Ai或a∈，兩者必有一個成立，取Ai為包含元素a的Ai或，則a∈Ai，即有a∈si，于是Usi。又顯然有siU，所以U＝si。 任取兩個非空小項sp和sq，若sp≠sq，則必存在某個Ai和分別出現(xiàn)在sp和sq中，于是sp∩sq＝。 綜上可知，{s1，s2，…，sr}是U的一個劃分。 五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的R*RR。 證明 (5)若R是傳遞的，則∈R*R$z(xRz∧zSy)xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*RR。 反之，若R*RR，則對任意的x、y、z∈A，如果xRz且zRy，則∈R*R，于是有∈R，即有xRy，所以R是傳遞的。 六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點數(shù)、邊數(shù)和面數(shù)。 證明 對G的邊數(shù)m作歸納法。 當(dāng)m＝0時，由于G是連通圖，所以G為平凡圖，此時n＝1，r＝1，結(jié)論自然成立。 假設(shè)對邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。 設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G，并設(shè)其結(jié)點數(shù)、邊數(shù)和面數(shù)分別為n、m和r。對e分為下列情況來討論： 若e為割邊，則G有兩個連通分支G1和G2。Gi的結(jié)點數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由歸納假設(shè)有n1－m1＋r1＝2，n2－m2＋r2＝2，從而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。 若e不為割邊，則n＝n，m＝m－1，r＝r－1，由歸納假設(shè)有n－m＋r＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。 由數(shù)學(xué)歸納法知，結(jié)論成立。 七、（10分）設(shè)函數(shù)g：A→B，f：B→C，則： (1)fog是A到C的函數(shù)； (2)對任意的x∈A，有fog(x)＝f(g(x))。 證明 (1)對任意的x∈A，因為g：A→B是函數(shù)，則存在y∈B使∈g。對于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復(fù)合關(guān)系的定義，由∈g和∈f得∈g*f，即∈fog。所以Dfog＝A。 對任意的x∈A，若存在y1、y2∈C，使得、∈fog＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因為g：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個元素對應(yīng)C中惟一的元素。 綜上可知，fog是A到C的函數(shù)。 (2)對任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝fog。又因fog是A到C的函數(shù)，則可寫為fog(x)＝f(g(x))。 八、（15分）設(shè)是的子群，定義R＝{|a、b∈G且a－1*b∈H}，則R是G中的一個等價關(guān)系，且[a]R＝aH。 證明 對于任意a∈G，必有a－1∈G使得a－1*a＝e∈H，所以∈R。 若∈R，則a－1*b∈H。因為H是G的子群，故(a－1*b)－1＝b－1*a∈H。所以∈R。 若∈R，∈R，則a－1*b∈H，b－1*c∈H。因為H是G的子群，所以(a－1*b)*(b－1*c)＝a－1*c∈H，故∈R。 綜上可得，R是G中的一個等價關(guān)系。 對于任意的b∈[a]R，有∈R，a－1*b∈H，則存在h∈H使得a－1*b＝h，b＝a*h，于是b∈aH，[a]RaH。對任意的b∈aH，存在h∈H使得b＝a*h，a－1*b＝h∈H，∈R，故aH[a]R。所以，[a]R＝aH。 發(fā)到哪？給個郵箱啊~~~~~~~一、填空 20% （每小題2分） 1．設(shè) （N：自然數(shù)集，E+ 正偶數(shù)） 則 。 2．A，B，C表示三個集合，文圖中陰影部分的集合表達(dá)式為 。 3．設(shè)P，Q 的真值為0，R，S的真值為1，則 的真值= 。 4．公式 的主合取范式為 。 5．若解釋I的論域D僅包含一個元素，則 在I下真值為 。 6．設(shè)A={1，2，3，4}，A上關(guān)系圖為 則 R2 = 。 7．設(shè)A={a，b，c，d}，其上偏序關(guān)系R的哈斯圖為 則 R= 。 8．圖 的補圖為 。 9．設(shè)A={a，b，c，d} ，A上二元運算如下： * a b c d a b c d a b c d b c d a c d a b d a b c 那么代數(shù)系統(tǒng)的幺元是 ，有逆元的元素為 ，它們的逆元分別為 。 10．下圖所示的偏序集中，是格的為 。 二、選擇 20% （每小題 2分） 1、下列是真命題的有（ ） A． ； B． ； C． ； D． 。 2、下列集合中相等的有（ ） A．{4，3} ；B．{ ，3，4}；C．{4， ，3，3}；D． {3，4}。 3、設(shè)A={1，2，3}，則A上的二元關(guān)系有（ ）個。 A． 23 ； B． 32 ； C． ； D． 。 4、設(shè)R，S是集合A上的關(guān)系，則下列說法正確的是（ ） A．若R，S 是自反的， 則 是自反的； B．若R，S 是反自反的， 則 是反自反的； C．若R，S 是對稱的， 則 是對稱的； D．若R，S 是傳遞的， 則 是傳遞的。 5、設(shè)A={1，2，3，4}，P（A）（A的冪集）上規(guī)定二元系如下 則P（A）/ R=（ ） A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}； D．{{ }，{2}，{2，3}，{{2，3，4}}，{A}} 6、設(shè)A={ ，{1}，{1，3}，{1，2，3}}則A上包含關(guān)系“ ”的哈斯圖為（ ） 7、下列函數(shù)是雙射的為（ ） A．f : I E , f (x) = 2x ； B．f : N N N, f (n) = ； C．f : R I , f (x) = [x] ； D．f :I N, f (x) = | x | 。 （注：I—整數(shù)集，E—偶數(shù)集， N—自然數(shù)集，R—實數(shù)集） 8、圖 中 從v1到v3長度為3 的通路有（ ）條。 A． 0； B． 1； C． 2； D． 3。 9、下圖中既不是Eular圖，也不是Hamilton圖的圖是（ ） 10、在一棵樹中有7片樹葉，3個3度結(jié)點，其余都是4度結(jié)點則該樹有（ ）個4度結(jié)點。 A．1； B．2； C．3； D．4 。 三、證明 26% 1、 R是集合X上的一個自反關(guān)系，求證：R是對稱和傳遞的，當(dāng)且僅當(dāng) < a, b> 和在R中有<.b , c>在R中。（8分） 2、 f和g都是群到< G2, *>的同態(tài)映射，證明是的一個子群。其中C= (8分) 3、 G= (|V| = v，|E|=e ) 是每一個面至少由k（k 3）條邊圍成的連通平面圖，則 ， 由此證明彼得森圖（Peterson）圖是非平面圖。（11分） 四、邏輯推演 16% 用CP規(guī)則證明下題（每小題 8分） 1、 2、 五、計算 18% 1、設(shè)集合A={a，b，c，d}上的關(guān)系R={ ,< b , a > ,< b, c > , < c , d >}用矩陣運算求出R的傳遞閉包t (R)。 （9分） 2、如下圖所示的賦權(quán)圖表示某七個城市 及預(yù)先算出它們之間的一些直接通信線路造價，試給出一個設(shè)計方案，使得各城市之間能夠通信而且總造價最小。 （9分） 試卷一答案： 一、填空 20% （每小題2分） 1、{0，1，2，3，4，6}； 2、 ；3、1； 4、 ； 5、1；6、{<1,1>, <1,3>, <2,2>, <2,4> }；7、{,,,,} IA ；8、 9、a ；a , b , c ,d ；a , d , c , d ；10、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% 1、 證： “ ” 若 由R對稱性知 ，由R傳遞性得 “ ” 若 ， 有 任意 ，因 若 所以R是對稱的。 若 ， 則 即R是傳遞的。 2、 證 ，有 ，又 ★ ★ ★ < C , ★> 是 < G1 , ★>的子群。 3、 證： ①設(shè)G有r個面，則 ，即 。而 故 即得 。（8分） ②彼得森圖為 ，這樣 不成立， 所以彼得森圖非平面圖。（3分） 二、 邏輯推演 16% 1、 證明： ① P（附加前提） ② T①I ③ P ④ T②③I ⑤ T④I ⑥ T⑤I ⑦ P ⑧ T⑥⑦I ⑨ CP 2、證明 ① P（附加前提） ② US① ③ P ④ US③ ⑤ T②④I ⑥ UG⑤ ⑦ CP 三、 計算 18% 1、 解： ， ， t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > } 2、 解： 用庫斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖： 樹權(quán)C(T)=23+1+4+9+3+17=57即為總造價。 面給出證明: (1) Some x is Y(x) P (2) Y(c) (1) T(1)，ES (3)Some(S(x)∧W(x)) P (4)S(c)∧W(c) T(3),US (5)S(c) T(4),I (6)S(c)∧Y(c) T(2)(5),I (7)(Every)S((x)∧Y(x)) T(6),EG