第一篇：離散數(shù)學(xué)期末考試試題及答案
離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個重要分支。下面是小編整理的離散數(shù)學(xué)期末考試試題及答案，歡迎閱讀參考！
一、【單項選擇題】
(本大題共15小題，每小題3分，共45分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在答題卷相應(yīng)題號處。
1、在由3個元素組成的集合上，可以有()種不同的關(guān)系。
[A] 3 [B] 8 [C]9 [D]272、設(shè)A1,2,3,5,8,B1,2,5,7,則AB()。
[A] 3,8 [B]3 [C]8 [D]3,83、若X是Y的子集，則一定有()。
[A]X不屬于Y [B]X∈Y
[C]X真包含于 Y [D]X∩Y=X4、下列關(guān)系中是等價關(guān)系的是()。
[A]不等關(guān)系 [B]空關(guān)系
[C]全關(guān)系 [D]偏序關(guān)系
5、對于一個從集合A到集合B的映射，下列表述中錯誤的是()。
[A]對A的每個元素都要有象 [B] 對A的每個元素都只有一個象
[C]對B的每個元素都有原象 [D] 對B的元素可以有不止一個原象
6、設(shè)p:小李努力學(xué)習(xí)，q:小李取得好成績，命題“除非小李努力學(xué)習(xí)，否則他不能取得好成績”的符號化形式為()。
[A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、設(shè)A={a,b,c},則A到A的雙射共有()。
[A]3個 [B]6個 [C]8個 [D]9個
8、一個連通G具有以下何種條件時，能一筆畫出：即從某結(jié)點(diǎn)出發(fā)，經(jīng)過中每邊僅一次回到該結(jié)點(diǎn)()。
[A] G沒有奇數(shù)度結(jié)點(diǎn) [B] G有1個奇數(shù)度結(jié)點(diǎn)
[C] G有2個奇數(shù)度結(jié)點(diǎn) [D] G沒有或有2個奇數(shù)度結(jié)點(diǎn)
9、設(shè)〈G,*〉是群，且|G|>1，則下列命題不成立的是()。
[A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外無其他冪等元
10、令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為()
[A] p→┐q [B] p∨┐q
[C] p∧q [D] p∧┐q11、設(shè)G=的結(jié)點(diǎn)集為V={v1,v2,v3},邊集為E={,}.則G的割(點(diǎn))集是()。
[A]{v1} [B]{v2} [C]{v3} [D]{v2,v3}
12、下面4個推理定律中，不正確的為()。
[A]A=>(A∨B)(附加律)[B](A∨B)∧┐A=>B(析取三段論)
[C](A→B)∧A=>B(假言推理)[D](A→B)∧┐B=>A(拒取式)
13、在右邊中過v1,v2的初級回路有多少條()
[A] 1 [B] 2 [C] 3 [D]
414、若R，是環(huán)，且R中乘法適合消去律，則R是()。
[A]無零因子環(huán)
[C]整環(huán) [B]除環(huán) [D]域
15、無向G中有16條邊，且每個結(jié)點(diǎn)的度數(shù)均為2，則結(jié)點(diǎn)數(shù)是()。
[A]8 [B]16 [C]4 [D]
32二、【判斷題】
(本大題共8小題，每小題3分，共24分)正確的填T，錯誤的填F，填在答題卷相應(yīng)題號處。
16、是空集。()
17、設(shè)S,T為任意集合，如果S—T=，則S=T。()
18、在命題邏輯中，任何命題公式的主合取范式都是存在的，并且是唯一的。()
19、關(guān)系的復(fù)合運(yùn)算滿足交換律。()
20、集合A上任一運(yùn)算對A是封閉的。()
21、0,1,2,3,4,max,min是格。()
22、強(qiáng)連通有向一定是單向連通的。()
23、設(shè)都是命題公式，則(PQ)QP。()
三、【解答題】
(本大題共3小題，24、25每小題10分，26小題11分，共31分)請將答案填寫在答題卷相應(yīng)題號處。
24、設(shè)集合A={a, b, c}，B={b, d, e}，求
(1)BA;(2)AB;(3)A-B;(4)BA.25、設(shè)非空集合A，驗證(P(A)，,~，A)是布爾代數(shù)
26、如果他是計算機(jī)系本科生或者是計算機(jī)系研究生，那么他一定學(xué)過DELPHI語言而且學(xué)過C++語言。只要他學(xué)過DELPHI語言或者C++語言，那么他就會編程序。因此如果他是計算機(jī)系本科生，那么他就會編程序。請用命題邏輯推理方法，證明該推理的有效結(jié)論。
離散數(shù)學(xué)試題答案
一、【單項選擇題】(本大題共15小題，每小題3分，共45分)
BDDCCCBABDADCBB
二、【判斷題】(本大題共8小題，每小題3分，共24分)
FFTFTTTF
三、【解答題】(本大題共3小題，24、25每小題10分，26小題11分，共31分)
24、設(shè)集合A={a, b, c}，B={b, d, e}，求(1)BA;(2)AB;(3)A-B;(4)BA.標(biāo)準(zhǔn)答案：(1)BA={a, b, c}{b, d, e}={ b }
(2)AB={a, b, c}{b, d, e}={a, b, c, d, e }
(3)A-B={a, b, c}-{b, d, e}={a, c}
(4)BA= AB-BA={a, b, c, d, e }-{ b }={a, c, d, e }
復(fù)習(xí)范圍或考核目標(biāo)：考察集合的基本運(yùn)算，包括交集，并集,見課件第一章第二節(jié),集合的運(yùn)算。
25、設(shè)非空集合A，驗證(P(A)，,~，A)是布爾代數(shù)
標(biāo)準(zhǔn)答案：證明 因為集合A非空，故P(A)至少有兩個元素，顯然，是P(A)上的二元運(yùn)算.由定理10，任給B,C,DP(A), H1 BD=DC CD=DC
H2 B(CD)=(BC)(BD)B(CD)=(BC)(BD)
H3 P(A)存在和A，BP(A), 有B=B，BA=B
H4，BP(A), BA，存在A~B，有
BA~B)= A B(A～B)=
所以(P(A)，,~，A)是布爾代數(shù).復(fù)習(xí)范圍或考核目標(biāo)：考察布爾代數(shù)的基本概念，集合的運(yùn)算，見課件代數(shù)系統(tǒng)中布爾代數(shù)小節(jié)。
26、如果他是計算機(jī)系本科生或者是計算機(jī)系研究生，那么他一定學(xué)過DELPHI語言而且學(xué)過C++語言。只要他學(xué)過DELPHI語言或者C++語言，那么他就會編程序。因此如果他是計算機(jī)系本科生，那么他就會編程序。請用命題邏輯推理方法，證明該推理的有效結(jié)論。
標(biāo)準(zhǔn)答案：令p：他是計算機(jī)系本科生
q：他是計算機(jī)系研究生 r：他學(xué)過DELPHI語言
s:他學(xué)過C++語言
t:他會編程序
前提：(p∨q)→(r∧s),(r∨s)→t
結(jié)論：p→t
證①p P(附加前提)
②p∨q T①I
③(p∨q)→(r∧s)P(前提引入)
④r∧s T②③I
⑤r T④I
⑥r(nóng)∨s T⑤I
⑦(r∨s)→t P(前提引入)
⑧t T⑤⑥I
第二篇：離散數(shù)學(xué)期末考試
一、單項選擇題（本大題共10小題，每小題2分，共20分）
1、設(shè)集合M={a，?}，N ={{a}，?}則M?N=（）。A、? B、{?} C、{a} D、{{a}，?，a}
2、設(shè)關(guān)系F={<1，a >，<2，2>，
A、{<1，b>，<1，c>，
B、{
D、{
3、設(shè)集合H={1，2，3，4}，則H上的關(guān)系R={
。x +y是偶數(shù)}具有（）A、自反性、反對稱性和傳遞性
B、反自反性、反對稱性和傳遞性
C、反自反性、對稱性和傳遞性
D、自反性、對稱性和傳遞性
4、設(shè)T是一棵完全二叉樹，則T的每個結(jié)點(diǎn)都（）。
A、至少有兩個子結(jié)點(diǎn)
B、至多有兩個子結(jié)點(diǎn)
C、恰有兩個子結(jié)點(diǎn)
D、可以有任意多個子結(jié)點(diǎn)
5、設(shè)R是實(shí)數(shù)集，“+，—，A、 ?>是群 B、 ? >是半群 D、 6、下面關(guān)系中，函數(shù)關(guān)系是（）。 A、{ B、{ D、{ 7、設(shè) A、結(jié)合律 B、交換律 C、分配律 D、冪等律 8、設(shè)Z是整數(shù)集，“—”是整數(shù)減法，則下列說法正確的是（）。A、 B、 C、 D、 9、設(shè)L是無向圖G中的一條通路，L中的頂點(diǎn)各不相同，則L是一條（）。A、簡單通路 B、初級通路 C、簡單回路 D、初級回路 10、設(shè)G有6個3度點(diǎn)，2個4度點(diǎn)，其余頂點(diǎn)的度數(shù)均為0，則G的邊數(shù)是（）。A、10 B、13 C、11 D、6 二、填空題(本大題共8題，共10個空，每空2分，共20分) 1、設(shè)關(guān)系R={ 2、在代數(shù)系統(tǒng) 3、設(shè)集合M={1，2，3，5}，則M的冪集P（M）包含___________個元素。 4、設(shè)T是一棵有n(n?2)個頂點(diǎn)的樹，則T有_____________條邊。 5、設(shè) 6、設(shè) 7、設(shè)D是有向圖，若D的基圖是連通圖，則稱D是_________________圖 8、既不含________________也不含____________________的無向圖稱為簡單圖。 三、計算題(本大題共3小題，每小題10分，共30分) 1、用等值演算法求公式A=(p??q)?(p?r)的主析取范式。 2、求公式?x(Q(x)?G(x，s))?(?yP(y)??zH(y，z))的前束范式。 3、設(shè)集合A={1，2，3，4，5}，關(guān)系R={ R； （3）求偏序集 四、應(yīng)用題(本大題共2小題，每小題5分，共10分) 1、用命題公式將下列命題符號化： 2和5是偶數(shù)，當(dāng)且僅當(dāng)5>2。 2、用謂詞公式將下列命題符號化： 每個計算機(jī)專業(yè)的學(xué)生都要學(xué)《編譯原理》，但有些計算機(jī)專業(yè)的學(xué)生不學(xué)《經(jīng)濟(jì)學(xué)》。 五、證明題（本大題共2小題，每小題10分，共20分） 1、在命題邏輯系統(tǒng)中用歸結(jié)法證明下列推理是有效的： 前提：?s?q，p??q，s 結(jié)論：?p 2、在謂詞邏輯系統(tǒng)中寫出下列推理的（形式）證明： 前提：?x(M(x)?P(x))，?x(M(x)?G(x))，?x(?G(x))結(jié)論：?xP(x) 計算題 6.設(shè)命題公式G = ?(P→Q)∨(Q∧(?P→R)), 求G的主析取范式。 7.(9分)設(shè)一階邏輯公式：G =(?xP(x)∨?yQ(y))→?xR(x)，把G化成前束范式.9.設(shè)R是集合A = {a, b, c, d}.R是A上的二元關(guān)系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；(2)畫出r(R), s(R), t(R)的關(guān)系圖.11.通過求主析取范式判斷下列命題公式是否等價： (1)G =(P∧Q)∨(?P∧Q∧R) (2)H =(P∨(Q∧R))∧(Q∨(?P∧R))13.設(shè)R和S是集合A＝{a, b, c, d}上的關(guān)系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝ {(a, b),(b, c),(b, d),(d, d)}.(1)試寫出R和S的關(guān)系矩陣；(2)計算R?S, R∪S, R1, S1?R1.－ － －證明題 1.利用形式演繹法證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S。2.設(shè)A,B為任意集合，證明：(A-B)-C = A-(B∪C).3.(本題10分)利用形式演繹法證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D。4.(本題10分)A, B為兩個任意集合，求證： A－(A∩B)=(A∪B)－B.答案： 1-5 BADBB 6-10 BBABB 1.{<1，a>，<1，2>， 環(huán) 三． ??(p??q)?(p?r)?(?p?q)?(p?r)1.?(?p?q?r)?(?p?q??r)?(p?q?r)?(p??q?r)?m011?m010?m111?m1012.??x(Q(x)?G(x,s))??y?z(P(y)?H(y,z)) ??y?z?x((Q(x)?G(x,s))?(P(y)?H(y,z))3.(1)R?{?1,1?,?2,2?,?3,3?,?4,4?,?5,5?,?1,2?,?1,3?,?1,4?,?1,5?,?2,4?} ??1??2(2)MR???3?4???512345?11111??01010?? （3）最小元=1 極小元=1 極大元=5 00100?00010??00001??四 1.令p表示2是偶數(shù)；令q表示5是偶數(shù)；r表示5>2； (p?q)?r 2.S（x）：x是計算機(jī)專業(yè)的學(xué)生；G（x）：x要學(xué)《編譯原理》； F（x）：x學(xué)經(jīng)濟(jì)學(xué)； ?x(S(x)?G(x))??x(S(x)??F(x)) 五 1，（1） s 前提引入（2） ?s?q 前提引入（3） q??s 置換規(guī)則 （4） q 1,3析取三段論（5） p??q 前提引入（6） ?p 4,5拒取 （1） ?x(M(x)?G(x)) 前提引入（2） M（x）v G（x） EI規(guī)則（3） ?x(?G(x)) 前提引入（4） ?G(x)（5） M(x) AI規(guī)則 2,4析取三段論 （6） ?x(M(x)?P(x)) 前提引入（7） M(x)→P（x） AI規(guī)則（8） P（x） 5,7假言推理（9） ?xP(x) EG規(guī)則 6.G = ?(P→Q)∨(Q∧(?P→R)) = ?(?P∨Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧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)∨(?P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = ?(3, 4, 5, 6, 7).7.G =(?xP(x)∨?yQ(y))→?xR(x) = ?(?xP(x)∨?yQ(y))∨?xR(x)=(??xP(x)∧??yQ(y))∨?xR(x)=(?x?P(x)∧?y?Q(y))∨?zR(z)= ?x?y?z((?P(x)∧?Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}, －t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2) 關(guān)系圖: abr(R)dcabs(R)dabt(R)dc c 11.G＝(P∧Q)∨(?P∧Q∧R)＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)＝m6∨m7∨m3 ＝?(3, 6, 7)H =(P∨(Q∧R))∧(Q∨(?P∧R))＝(P∧Q)∨(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)＝m6∨m3∨m7 ＝?(3, 6, 7)G,H的主析取范式相同，所以G = H.?1?013.(1)MR???0??0000011000??0?00?? MS??1??0??0??0100001000?1?? 0??1?(2)R?S＝{(a, b),(c, d)}, R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R1＝{(a, a),(c, a),(c, b),(d, c)}, －S1?R1＝{(b, a),(d, c)}.－－四 證明題 1.證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S (1)P∨R (2)?R→P(3)P→Q(4)?R→Q(5)?Q→R(6)R→S P Q(1)P Q(2)(3)Q(4)P (7)?Q→S(8)Q∨S Q(5)(6)Q(7)2.證明：(A-B)-C =(A∩~B)∩~C 3.= A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D(1)A D(附加)P(2)?A∨B(3)B Q(1)(2)P Q(4)(4)?C→?B(5)B→C(6)C Q(3)(5)P(7)C→D(8)D Q(6)(7)D(1)(8)(9)A→D 所以 {?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D.1.證明：A－(A∩B) = A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝?∪(A∩~B)＝(A∩~B)＝A－B 而(A∪B)－B =(A∪B)∩~B =(A∩~B)∪(B∩~B)=(A∩~B)∪? = A－B 所以：A－(A∩B)=(A∪B)－B. 第二章 二元關(guān)系 1.設(shè)A={1,2,3,4},A上二元關(guān)系 R={(a,b)|a=b+2}，S={(x,y)|y=x+1 or y= x2} 求R?S,S?R,S?R?S,S2,S 3,S?Rc。 R?S={(3,2),(4,3),(4,1)} S?R={(2,1),(3,2)} S?R?S={(2,2),(3,3),(3,1)} S2={(1,1),(1,3),(2,2),(2,4),(3,2),(4,1),(4,3)} S3={(1,2),(1,4),(2,1),(2,2),(2,3),(3,1),(3,3),(4,2),(4,4)} S?Rc={(1,4),(2,3),(4,4)} 2．A={a,b,c,d,e,f,g,h}，給定A上關(guān)系R的 關(guān)系圖如下： 圖3－14 求最小正整數(shù)ｍ，ｎ，ｍ＜ｎ，使Ｒm＝Ｒn。 Ｒ1＝Ｒ16 這是因為R15是8個頂點(diǎn)以及8個自回路，相 當(dāng)于左圖的點(diǎn)各走了5圈，左圖的點(diǎn)各走了3圈，R16就成了原來的R． ３．證明： (1)(InA)?IA?(a,a)?I2nA,a?A,(a,a)?IA,...,(a,a)?IA, ?(b,b)?InA,b?A,(b,b)?IA.(2)IA?R?R?IA?R?(a,b)?R,?a,b?A,(a,a)?IA,(b,b)?IA,?(a,b)?IA?R,(a,b)?R?IA,即R?I A?R,R?R?IA;?(a,b)?IA?R,若(a,b)?R,則(a,b)?IA?R,矛盾,得IA?R?R;同理,R?IA?R.事實(shí)上，當(dāng)|A|有限時，R與IA復(fù)合，相當(dāng)于矩陣與 單位矩陣相乘，不會變化。 (3)(R?In2nA)?IA?R?R?...?Rn?1(R?IA)?IA?R;設(shè)(R?Ik2A)?IA?R?R?...?Rk (R?Ik?1?(I2A)...?RkA?R?R?)(R?IA)?(R?R2?...?Rk?1)?(I2A?R?R?...?Rk)?I?R2?...?Rk?Rk?1A?R ４．判斷下列等式是否成立（Ｒ,Ｒ1,Ｒ2均是Ａ到Ｂ的 二元關(guān)系） (1)(Rccc1?R2)?R1?R2對,(a,b)?(Rc1?R2)?(b,a)?R1?R2?(b,a)?R 1or(b,a)?R2?(a,b)?Rc1or(a,b)?Rc2?(a,b)?Rcc1?R2 (2)(Rcc1?R2)?R1?Rc2對(a,b)?(Rc1?R2)?(b,a)?R1?R2?(b,a)?R 1and(b,a)?R2?(a,b)?Rcc1and(a,b)?R2?(a,b)?Rcc1?R2 (3)(R1?R2)?R1?R2對cccc(a,b)?(R1?R2)?(R1?R2)c?(b,a)?R1?R2?(b,a)?R1,(b,a)?R2 ?(a,b)?Rc1,(a,b)?Rc2?(a,b)?Rcccc1?R2?R1?R2(4)(A?B)c?A?B否,例:A?{1,2},B?{3,4},A?B?{(1,3),(2,3),(1,4),(2,4)} (A?B)c?{(3,1),(3,2),(4,1),(4,2)}(5)?c??否,?c 與?的定義域,值域?qū)Q了一下.(6)(R)c?(Rc)對,(a,b)?(R)c?(b,a)?R?(b,a)?R?(a,b)?Rc?(a,b)?Rc(7)(Rcc1?R2)?R2?Rc1否,R2的定義域不一定與R1的值域相同(8)如果Rcc1?R2,則R1?R2對,?(a,b)?Rc1,(b,a)?R1?R2,(a,b)?Rc2.(9)如果R1?Rcc2,則R1?R2對,?(a,b)?Rc1,(b,a)?R1?R2,(a,b)?Rc2，R1?R2,?(c,d)?R2,(c,d)?R1,(d,c)?Rc2,而(d,c)?Rc1..? (10)R1?R2?R2?R1否,R 2的定義域不一定與R1的值域相同.5.設(shè)R1,R2是集合A上的二元關(guān)系，如果R2?R1，其中r,s,t分別是自反閉包，對稱閉包，傳遞閉包的 記號。試證明:(1)r(R2)?r(R1)?R2?R1,IA?IA, ?R2?IA?R1?IA (2)s(R2)?s(R1)?R2?Rcc1,R2?R1 ?Rcc2?R2?R1?R1 (3)t(R2)?t(R1)?R222?R1?(R2)1?(R1)1(即R2?R2?R1?R1)?(a,b)?R(a,b)?(R?2?R1?(R1)1b)?R22)1?(a,2,?c?A,(a,c),(c,b)?R2?R1,??(a,b)?R21,(a,b)?(R1)1?(a,b)?t(R2),?k,使(a,b)?(R2)k?(R1)k?t(R1).6.設(shè)R1,R2,R3,R4分別是A到B，B到C，B到C，Ｃ到D的二元關(guān)系，證明 (1)R1?(R2?R3)?R1?R2?R1?R3(x,y)?R1?(R2?R3)??z,(x,z)?R1,(z,y)?R2or(z,y)?R3??z,(x,z)?R1,(z,y)?R2or(x,z)?R 1,(z,y)?R3?(x,y)?R1?R2or(x,y)?R1?R3?(x,y)?R1?R2?R1?R3 (2)R1?(R2?R3)?R1?R2?R1?R3?(x,y)?R1?(R2?R3)??z,(x,z)?R1,(z,y)?R2and(z,y)?R3??z,(x,z)?R 1,(z,y)?R2and(x,z)?R1,(z,y)?R3?(x,y)?R1?R2and(x,y)?R1?R3?(x,y)?R1?R2?R1?R3(3)(4)類(1)(2)證明。 7.設(shè)R是A上的二元關(guān)系，證明對任意自然數(shù)m,n，(1)Rm?Rn?Rm?n(2)(Rm)n?Rm?n 由歸 (1)1)n?1,Rm?1?Rm?R2)假定Rm?Rn?Rm?n?{(a,b)|?c?A,(a,c)?Rm,(c,b)?Rn}n?1Rm?R?{(a,b)|?c?A,(a,c)?Rm,(c,b)?Rn?1}其中,Rn?1?{(c,b)|?d?A,(c,d)?Rn,(d,b)?R}Rm?Rn?1?{(a,b)|?c,d?A,(a,c)?Rm,(c,d)?Rn,(d,b)?R}?{(a,b)|?d?A,(a,d)?Rm?n,(d,b)?R}?Rm?n?R?R(m?n)?1?Rm?(n?1) (2)1)n?1,Rm?Rm2)假定(Rm)n?Rm?n(Rm)n?1?(Rm)n?Rm?Rm?n?Rm 由(1)Rm?n?m?Rm?(n?1)8.設(shè)R是A上的二元關(guān)系，｜A｜＝n，證明存在 自然數(shù)s,t，使Rs?Rt,且0?s?t?2n2，其中定義 R0?{(a,a)|a?A}。 ??0(ai,aj)?R證:R?(rij)n?n,rij????1(ai,aj)?R至多有2n2個不同的Rk(k?N)出現(xiàn), 0?k?2n2,由鴿洞原理,(2n2?1)個Rk中必存在s,t,0?s?t?2n2,Rs?Rt.9.R1，R2是Ａ上的二元關(guān)系，判別下列命題正確與否 (1)如果R1，R2自反，則R1?R2也自反。 對,?a?A,(a,a)?R1,(a,a)?R2,?(a,a)?R 1?R2 (2)如果R1，R2反自反，則R1?R2也反自反。 否,若(a,b)?R1,(b,a)?R2,(a,a)?R1?R2 (3)如果R1，R2對稱，則R1?R2也對稱。 否,例:A?{1,2,3},R1?{(1,2),(2,1)},R2?{(2,3),(3,2)},(1,2)?R 1,(2,3)?R2,(1,3)?R1?R2,而(3,1)?R1?R2 (4)如果R1，R2反對稱，則R1?R2也反對稱。 否,例:A?{1,2,3},R1?{(1,2),(3,2)},R2?{(2,3),(2,1)},(1,2)?R,3)?R，1,(22,(1,3)?R1?R2(3,2)?R1,(2,1)?R2,(3,1)?R1?R2 (5)如果R1，R2傳遞，則R1?R2也傳遞。 否,例:A?{1,2,3,4},R1?{(1,1),(2,3)},R2?{(1,2),(3,3)},(1,1)?R1,(1,2)?R2,(1,2)?R1?R2，(2,3)?R1,(3,3)?R2,(2,3)?R1?R2,但(1,3)?R1?R2 10.設(shè)A={a,b,c}，以下分別給出一個P(A)上的二元 關(guān)系，確定它們哪些是自反的，反自反的，對稱的，反對稱的，傳遞的。 P(A)={?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}（１）ｘ是ｙ的一個真子集 R1?{(x,y)|x?y,x,y?P(A)} 反自反，不對稱，反對稱，傳遞（２）ｘ與ｙ不相交 R2?{(x,y)|x?y??,x,y?P(A)} 不自反，也不反自反(?????)，對稱，不傳遞（３）x?y?A R3?{(x,y)|x?y?A,x,y?P(A)} 不自反，也不反自反{a,b,c}?{a,b,c}?A，對稱，不傳遞。 11.設(shè)R是A上二元關(guān)系，證明R是傳遞的當(dāng)且僅當(dāng) R2?R。 任(a,b)∈R2,?C,(a,c)(c,b)∈R ,由R傳遞(a,b)∈R , 即R2 ? R;若(a,b)∈R,(b,c)∈R , 即(a,c)∈R2? R , 所以R傳遞。 12.R是A上反對稱的二元關(guān)系，問t(R)總是反對稱 的嗎？ ?010??111?否, 例： R???001??,t(R)???111?? ??100????111?? 13．設(shè)R是A上的一個自反關(guān)系，證明當(dāng)且僅當(dāng)(a,b)和(a,c)屬于R推出(b,c)屬于R時，R是一個等價 關(guān)系。 若(a,b)∈R，又自反(a,a)∈R, 推出(b,a)∈R, 所以對稱； 若(a,b)(b,c)∈R , 由對稱(b,a)(b,c)∈R , 推出(a,c)∈R ,所以傳遞。若R等價,(a,b)(a,c)∈R , 由對稱性(b,a)(a,c)∈R , 由傳遞性 ,(b,c)∈R。 14.設(shè)R是A上的一個對稱和傳遞的關(guān)系，證明如果對A中的每個a，在A中存在b，使得(a,b)∈R，則R是一個等價關(guān)系。 ?a?A,?b?A,(a,b)?R,由對稱性,(b,a)?R,又由傳遞性,(a,a)?R.15.設(shè)R是A上的一個傳遞和自反的關(guān)系，設(shè)T是 A上的一個二元關(guān)系，使得當(dāng)且僅當(dāng)(a,b)和(b,a)同時 屬于R時，(a,b)∈T，證明T是一個等價關(guān)系。 ?a(a,a)∈R,(a,a)∈R =>(a,a)∈T 若(a,a)∈T,(a,b)(b,a)∈R , 即(b,a)(a,b)∈R =>(b,a)∈T 若(a,b)(b,c)∈T,(a,b)(b,a)(b,c)(c,b)∈R =>(a,c)∈R,(c,a)∈R =>(a,c)∈T 16.設(shè)R是A上一個二元關(guān)系，設(shè) S={(a,b)｜對某個C，(a,c)∈R且(c,b)∈R｝ 證明如果R是等價關(guān)系，則Ｓ也是等價關(guān)系。 ?a,(a,a)∈R,(a,a)∈R =>(a,a)∈S 若(a,b)∈S , 存在c,(a,c)(c,b)∈R 由R對稱,(b,c)(c,a)∈R , 所以(b,a)∈S 若(a,b)(b,c)∈S 存在d,e (a,d)(d,b)(b,e)(e,c)∈R 由R傳遞(a,b)(b,c)∈R 所以(a,c)∈S 17.設(shè)R是A上的二元關(guān)系，對所有的xi,xj,xk∈A，如果xiRxj∧xjRxk?xkRxi，則稱R為循環(huán)關(guān)系，試證明當(dāng)且僅當(dāng)R是等價關(guān)系時，R才是自反的和循環(huán)的。（其中aRb表示(a,b)∈Ｒ）。 R等價, 當(dāng)然自反，如果xiRxj且xjRxk則由傳遞性，xiRxk, 由對稱性xkRxi，R是自反, 循環(huán)的； 若(a,b)∈R, 由R自反 ?a,(a,a)∈R, 又(a,b)∈R, 由循環(huán)(b,a)∈R，對稱，若(a,b)(b,c)∈R，由循環(huán)(c,a)∈R, 由對稱(a,c)∈R，傳遞。 18．設(shè)R1，R2是A上二元關(guān)系，證明(1)r(R1?R2)?r(R1)?r(R2)(2)s(R1?R2)?s(R1)?s(R2)(3)t(R1?R2)?t(R1)?t(R2)(1)r(R1?R2)?(R1?R2)?IA?R1?IA?R2?R1?(IA?IA)?R2?(R1?IA)?(IA?R2)?(R1?IA)?(R2?IA)?r(R1)?r(R2)(2)s(Rc1?R2)?(R1?R2)?(R1?R2)?Rcc1?R2?R1?R2 ?(Rcc1?R1)?(R2?R2)?s(R1)?s(R2)(3)(R1?R2)2?{(a,b)|?c,(a,c)?R1orR2,(c,b)?R1orR2}?R221?R2?R1?R2?R2?R1 29 R2221?R2?(R1?R2)用歸納法可證RnRnn1?2?(R1?R2) n??,可得t(R1)?t(R2)?t(R1?R2) 19.設(shè)A={a,b,c,d},A上二元關(guān)系 R={(a,b),(b,a),(b,c),(c,d)} （１）用矩陣算法和作圖法求r(R),s(R),t(R)。（２）用Warshall算法求t(R)。 ?1100??0100??1111?? r(R)=?1110????1010????1111???0011? s(R)= ?0101? t(R)=?0001???0001????0010????0000?? ?0100??100??1110???1010?i?10??110?i?2???1110???000???11?0001???0001? ??0000?j?2???0000?j?1,2???0000??i?3?1111?111??1111????1110?i?3?1????1111?i?4???1111??j?2?0001??0001???0001???0000?j?2???0000?j?1,2,3???0000?? 20.討論正實(shí)數(shù)集上二元關(guān)系Ｒ的幾何意義。（１）Ｒ是自反的（２）Ｒ是對稱的（３）Ｒ是傳遞的 （提示：以第一象限的點(diǎn)討論） (1)第一象限角平分線 (2)關(guān)于對角平分線對稱的點(diǎn)對集合 (3)若有P1(x1,y1)、P2(x2,y2), 若x2=y1，必有第三個點(diǎn)P3(x1,y2) 離散數(shù)學(xué)習(xí)題參考答案 第一章 集合 １．分別用窮舉法，描述法寫出下列集合（１）偶數(shù)集合 （２）36的正因子集合（３）自然數(shù)中3的倍數(shù)（４）大于１的正奇數(shù) (1)E={?，-6，-4，-2，0，2，4，6，?} ={2 i | i? I } (2)D= { 1, 2, 3, 4, 6, } = {x>o | x|36 } (3)N3= { 3, 6, 9, ```} = { 3n | n?N } (4)Ad= {3, 5, 7, 9, ```} = { 2n+1 | n?N } ２．確定下列結(jié)論正確與否（１）φ?φ ×（２）φ?｛φ｝√（３）φ?φ√（４）φ?｛φ｝√（５）φ?｛ａ｝×（６）φ?｛ａ｝√ （７）｛ａ，ｂ｝?｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝×（８）｛ａ，ｂ｝?｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝√（９）｛ａ，ｂ｝?｛ａ，ｂ，｛｛ａ，ｂ｝｝｝×（１０）｛ａ，ｂ｝?｛ａ，ｂ，｛｛ａ，ｂ｝｝｝√ ３．寫出下列集合的冪集（１）｛｛ａ｝｝ {φ, {{ a }}} (2)φ {φ}（３）｛φ，｛φ｝｝ {φ, {φ}, {{φ}}, {φ,{φ}} }（４）｛φ，ａ，｛ａ，ｂ｝｝ {φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}，{a, {a b }}, {φ,a,{ a, b }} }（５）Ｐ（Ｐ（φ）） {φ, {φ}, {{φ}}, {φ,{φ}} } ４．對任意集合Ａ，Ｂ，Ｃ，確定下列結(jié)論的正確與否（１）若Ａ?Ｂ，且Ｂ?Ｃ，則Ａ?Ｃ√（２）若Ａ?Ｂ，且Ｂ?Ｃ，則Ａ?Ｃ×（３）若Ａ?Ｂ，且Ｂ?Ｃ，則Ａ?Ｃ×（４）若Ａ?Ｂ，且Ｂ?Ｃ，則Ａ?Ｃ × ５．對任意集合Ａ，Ｂ，Ｃ，證明 (1)A?(B?C)?(A?B)?(A?C)左差A(yù)?(B?C)差A(yù)?(B?C)D.MA?(B?C) 分配(A?B)?(A?C)?右(2)A?(B?C)?(A?B)?(A?C)1)左差A(yù)?(B?C)(1)的結(jié)論(A?B)?(A?C)差(A?B)?(A?C)?右 2)左差A(yù)?(B?C)D.MA?(B?C)分配(A?B)?(A?C)差(A?B)?(A?C)?右(3)A?(B?C)?(A?B)?(A?C)左差A(yù)?(B?C)D.MA?(B?C)冪等(A?A)?(B?C) 結(jié)合,交換(A?B)?(A?C)?右(4)(A?B)?B?A?B 左差(A?B)?B對稱差((A?B)?B)?((A?B)?B) 分配,結(jié)合((A?B)?(B?B))?(A?(B)?B)) 互補(bǔ)((A?B)?U)?(A??) 零一 (A?B)???(A?B)?右(5)(A?B)?C?A?(B?C)左差(A?B)?C結(jié)合A?(B?C) D.MA?(B?C)差A(yù)?(B?C)(6)(A?B)?C?(A?C)?B左差(A?B)?C結(jié)合A?(B?C)交換A?(C?B)結(jié)合(A?C)?B 差(A?C)?B?右(7)(A?B)?C?(A?C)?(B?C)右(5)A?(C?(B?C))差A(yù)?(C?(B?C))分配A?((C?B)?(C?C))互補(bǔ)A?((C?B)?U) 零一A?(C?B)交換A?(B?C)(5)(A?B)?C?左 ６．問在什么條件下，集合Ａ，Ｂ，Ｃ滿足下列等式 (1)A?(B?C)?(A?B)?C左?(A?B)?(A?C)?右若要右?左,須C?A?(B?C)，?C?A時等式成立? (2)A?B?A左?右是顯然的,A?A?B?A?B,A?B，?A?B??時等式成立? (3)A?B?BA?B?B,B?B,B??,代入原式得A????，?A?B??時等式成立? (4)A?B?B?AA?B?B?A,只能??A?B??,A?B, B?A??,B?A,?A?B時等式成立? (5)A?B?AB??,若B??,?b?B，當(dāng)b?A,b?A?B?A矛盾;當(dāng)b?A,b?A?B?A矛盾? (6)A?B?A?B右?左是顯然的,A?B?A?B,??A?A?B,A?B?B?A?B,B?A?A?B?A?B時等式成立? (7)(A?B)?(A?C)?A左?(A?B)?(A?C)?A?(B?C)?A?(B?C)?A?(B?C)?A ?A?B?C??時等式成立? (8)(A?B)?(A?C)??左?(A?B)?(A?C)?A?(B?C)?A?(B?C)?A?(B?C)?? A?(B?C),?A?B,A?C時等式成立? (9)(A?B)?(A?C)??左?(A?B)?(A?C)?A?(B?C)?A?(B?C)?A?(B?C)?? ?A?(B?C)時等式成立? (10)(A?B)?(A?C)??((A?B)?(A?C))?((A?B)?(A?C))??(A?B)?(A?C)?(A?B)?(A?C) 由(6)知,(A?B)?(A?C),A?B?A?C,?A?B?A?C時等式成立? (11)A?(B?A)?BA?(B?A)?(A?B)?(A?A)?(A?B)?U?(A?B)?B ?A?B時等式成立? ７．設(shè)Ａ＝｛ａ，ｂ，｛ａ，ｂ｝，｝，求下列各式（１）φ∩｛φ｝=φ（２）｛φ｝∩｛φ｝={φ} （３）｛φ，｛φ｝｝－φ={φ,{φ}}（４）｛φ，｛φ｝｝－｛φ｝= {{φ}}（５）｛φ，｛φ｝｝－｛｛φ｝｝={φ}（６）Ａ－｛ａ，ｂ｝={{a,b}, φ}（７）Ａ－φ = A（８）Ａ－｛φ｝={a,b,{a,b}}（９）φ－Ａ=φ（１０）｛φ｝－Ａ=φ ８．在下列條件下，一定有Ｂ＝Ｃ嗎？（１）A?B?A?C 否，例：A={1，2，3}，B={4}，C={3,4}, A?B?A?C?{1,2,3,4},而B?C。 （２）A?B?A?C 否，例：A={1，2，3}，B={2，3}，C={2，3，4} A?B?A?C?{2,3},而B?C。 （３）A?B?A?C 對,若B?C,不妨,?a?B,a?C,若a?A,a?A?B,a?A?B,a?A?B,a?A?C,a?A?C,a?A?C;若a?A,a?A?B,a?A?B,a?A?B,a?A?C,a?A?C,a?A?C矛盾?（４）A?B?A?C且A?B?A?C ?b?B,若b?A,b?A?B?A?C,b?C,若b?A,b?A?B?A?C,b?C，?B?C,同理,C?B,?B?C? 9.(1)(A?B)?(B?C)?A?B 證:?a?左,a?(B?C),a?B,a?B;a?(A?B),而a?B,a?A,?a?A?B? (2)若A?(B?C)且B?(A?C),則B??。 若B??,?a?B?(A?C)?(A?C),a?A?(B?C),?a?C,?a?B即a?B,矛盾? 10．化簡 ((A?B?C)?(A?B))?((A?(B?C))?A)?(A?B)?A?(A?B)?A ?(A?A)?(B?A)???(B?A)?B?A11.設(shè)A={2，3，4}，B={1，2}，C={4，5，6}，求（１）A?B?{1, 3, 4} （２）A?B?C?{1,3,5,6}（３）(A?B)?(B?C)?{2,3,5,6} 12.設(shè)A={1，2，3，4}，B={1，2，5}，求 (1)P(A)?P(B)?{φ,{1},{2},{1,2}} (2)P(A)?P(B)? {φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}, {1,2,3,},{1,2,4,},{1,3,4,},{2,3,4},{1,2,3,4,},{5},{1,5}, {2,5},{1,2} } (3)P(A)?P(B)? { {3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}，{2,3,4},{1,2,3,4} } (4)P(A)?P(B)? {{3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}, {2,3,4},{1,2,3,4},{5},{1,5},{2,5},{1,2,5} } 離散數(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)有：A?C?D，?(B∧C)，C??D必須同時成立。因此 (A?C?D)∧?(B∧C)∧(C??D) ?(?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ù)會議的每個成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。 解：論域：所有人的集合。S(x)：x是專家；W(x)：x是工人；Y(x)：x是青年人；則推理化形式為： ?x(S(x)∧W(x))，?xY(x)?x(S(x)∧Y(x)) 下面給出證明： (1)?xY(x)P (2)Y(c)T(1)，ES (3)?x(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)?x(S(x)∧Y(x))T(6)，EG 三、（10分）設(shè)A、B和C是三個集合，則A?B??(B?A)。 證明：A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A) ???x(x∈A∧x?B)∧??x(x?B∨x∈A)???x(x∈A∧x?B)∨??x(x∈A∨x?B) ??(?x(x∈A∧x?B)∧?x(x∈A∨x?B))??(?x(x∈A∧x?B)∧?x(x∈B→x∈A)) ??(B?A)。 四、（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＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R t(R)＝?Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i?1?4232－ 15>}。 五、（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，R對稱。 因R對稱，則有xRy??z(xRz∧zRy)??z(zRx∧yRz)?yRx，所以R對稱。若Rn對稱，則xRn?1y??z(xRnz∧zRy)??z(zRnx∧yRz)?yRn?1x，所以Rn?1對稱。因此，對任意正整數(shù)n，Rn對稱。對任意的x、y∈A，若xt(R)y，則存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是對稱的。 六、（10分）若f：A→B是雙射，則f：B→A是雙射。 證明因為f：A→B是雙射，則f是B到A的函數(shù)。下證f是雙射。 對任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f(y)＝x，所以f是滿射。 對任意的y1、y2∈B，若f(y1)＝f(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因為f：A→B是函數(shù)，則y1＝y(tǒng)2。所以f是單射。 綜上可得，f：B→A是雙射。 七、（10分）設(shè) 證明因為 因為S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j(luò)－i，則bj＝bp*bj。所以對q≥i，有bq＝bp*bq。 因為p≥1，所以總可找到k≥1，使得kp≥i。對于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。 令a＝bkp，則a∈S且a*a＝a。 八、（20分）（1）若G是連通的平面圖，且G的每個面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點(diǎn)數(shù)n有如下關(guān)系： m≤ rl(n－2)。l?2l證明設(shè)G有r個面，則2m＝ 2)。?d(f)≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤l?2(n－ii? 1（2）設(shè)平面圖G＝ 證明設(shè)G＝ 離散數(shù)學(xué)考試試題（B卷及答案） 一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R 證明因為S∨R??R?S，所以，即要證(P∨Q)∧(P?R)∧(Q?S)?R?S。 (1)?R附加前提 (2)P?RP (3)?PT(1)(2)，I (4)P∨QP (5)QT(3)(4)，I (6)Q?SP (7)ST(5)(6)，I (8)?R?SCP (9)S∨RT(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，|A?B?C|＝25－20＝5。故，不會打這三種球的共5人。 四、（10分）設(shè)A1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱為由A1、A2和 i?1 3A3產(chǎn)生的小項。試證由A1、A2和A3所產(chǎn)生的所有非空小項的集合構(gòu)成全集U的一個劃分。 證明小項共8個，設(shè)有r個非空小項s1、s2、…、sr(r≤8)。 對任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個成立，取Ai?為包含元素a的Ai或Ai，則a∈?Ai?，i?13即有a∈?si，于是U??si。又顯然有?si?U，所以U＝?si。 i?1i?1i?1i?1rrrr 任取兩個非空小項sp和sq，若sp≠sq，則必存在某個Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝?。綜上可知，{s1，s2，…，sr}是U的一個劃分。 五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的?R*R?R。 證明(5)若R是傳遞的，則 反之，若R*R?R，則對任意的x、y、z∈A，如果xRz且zRy，則 六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點(diǎn)數(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é)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為n?、m?和r?。對e分為下列情況來討論： 若e為割邊，則G?有兩個連通分支G1和G2。Gi的結(jié)點(diǎn)數(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)f?g是A到C的函數(shù)； (2)對任意的x∈A，有f?g(x)＝f(g(x))。 證明(1)對任意的x∈A，因為g：A→B是函數(shù)，則存在y∈B使 對任意的x∈A，若存在y1、y2∈C，使得 綜上可知，f?g是A到C的函數(shù)。 (2)對任意的x∈A，由g：A→B是函數(shù)，有 八、（15分）設(shè) 一個等價關(guān)系，且[a]R＝aH。 證明對于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以 若 若 －1*c∈H，故 綜上可得，R是G中的一個等價關(guān)系。 對于任意的b∈[a]R，有 [a]R?aH。對任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H， ＝aH。第三篇：離散數(shù)學(xué)期末復(fù)習(xí)試題及答案(二)
第四篇：離散數(shù)學(xué)期末復(fù)習(xí)試題及答案(一)
第五篇：離散數(shù)學(xué)習(xí)題及答案
![下載離散數(shù)學(xué)期末考試試題及答案[5篇范文]word格式文檔](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
點(diǎn)擊咨詢 