【正文】 (2)1,1,2,2。(3)a=4, b=5。 u185。10 解得n179。(2)1,2,2,3解(1).(2)能例2 已知圖G有10條邊, 4個3度頂點, 其余頂點的度數(shù)均小 于等于2, 問G至少有多少個頂點? 解 ，4180。(x+2)2gof(x)=237。3fog(x)=237。 x3238。238。)=f0, f({1})=f1, f({2})=f2, f({3})=f3，f({1,2})=f4, f({1,3})=f5, f({2,3})=f6, f({1,2,3})=f7 例4A=[0,1]B=[1/4,1/2] 構造雙射 f : A→B解令f : [0,1]→[1/4,1/2]f(x)=(x+1)/4例5A=Z, B=N，構造雙射 f : A→B將Z中元素以下列順序排列并與N中元素對應： Z：0112233 …   ↓↓↓↓↓↓↓ N：0 1 2 4 5 6 … 則這種對應所表示的函數(shù)是： x179。（4）f : R→R, f(x)=2x+1（5）f : R+→R+, f(x)=(x2+1)/x, 其中R+(1)f : R→R, f(x)= x2+2x1在x=.(2)f : Z+→R, f(x)=lnx單調上升, , ranf={ln1, ln2, …}.(3)f : R→Z, f(x)= 235。A={, , , , , , ，, , , , , , ，}根據(jù)有序對的 x+y=2,3,4,5,6,7,8 將A180。,{a, b},{c, d}}，p 6={{a,{a}},{b, c, d}} 則p 1和p 2是A的劃分, 給出A＝{1,2,3}上所有的等價關系求解思路：先做出A的所有劃分, 然后根據(jù)劃分寫出 分之間的對應：p 4對應于全域關系EA p 5對應于恒等關系IA p 1, p 2和p 3分別對應于等價關系 R1, R1={,}∪IAR2={,}∪IAR3={,}∪IA 例5設A={1,2,3,4}，在A180。 206。R , 則 R 在 A 任取，206。R∩R 1 222。R 217。R 217。R 1 222。 206。R，則 R 在 A 任取x，x206。000235。234。01000000000235。234。M=234。234。01 234。0100249。235。234。234。N, x+y={, , , , , }(2)C={ | x,y206。P(A)180。 y=2, x= 3 例2A={0, 1}, B={a, b, c}A180。G(y))量詞轄域擴張 219。y216。 xF(x)$216。G(x)量詞否定等值式 219。217。F(x))219。F(x))量詞否定等值式219。 216。 0 例4 證明下列等值式:216。(1217。(L(2,2)217。(0217。(F(f(3))217。F(c,c))例3 給定解釋I:(a)D={2,3},(b)(c):x是奇數(shù)，: x=2 218。F(b,b)217。(F(a,a)217。G(c))(3)$xyF(x,y)219。F(b)217。yG(y))219。(F(b)174。 $yG(x,y,z))代替規(guī)則 例2 設個體域D={a,b,c}, 消去下面公式中的量詞:(1)x(F(x)174。 $yG(x,y,z))219。 xF(x,u,z)174。 uF(u,y,z)174。(p174。 $yG(y)這是216。p218。(xF(x))218。y+2=x)假命題(3)xy$zF(f(x,y),z)xy$z(x+y=z)真命題(4)$xF(f(x,x),g(x,x))$x(2x=x2)真命題(5)F(f(x,a), g(x,a))x+2=2x不是命題(6)x(F(x,y)174。yG(x,y,z))，指導變元為x $y的轄域:G(x,y,z)，指導變元為y x的兩次出現(xiàn)均為約束出現(xiàn)y的第一次出現(xiàn)為自由出現(xiàn), 第二次出現(xiàn)為約束出現(xiàn) 公式 x(F(x)$174。 $x$y(F(x)217。H(x,y)))(3)216。G(x))M(x)稱作特性謂詞例4 將下列命題符號化, 并討論其真值:(1)對任意的x, 均有x23x+2=(x1)(x2)(2)存在x, 使得x+5=3 分別取(a)個體域D1=N,(b)個體域D2=R 解 記F(x): x23x+2=(x1)(x2), G(x): x+5=3(a)(1)x F(x)真值為1(2)$x G(x)真值為0(b)(1)x F(x)真值為1(2)$x G(x)真值為1 例5 將下面命題符號化:(1)兔子比烏龜跑得快(2)有的兔子比所有的烏龜跑得快(3)并不是所有的兔子都比烏龜跑得快(4)不存在跑得一樣快的兔子和烏龜解用全總個體域，令F(x): x是兔子, G(y): y是烏龜，H(x,y): x比y跑得快，L(x,y): x和y跑得一樣快(1)xy(F(x)217。(216。r, 216。q218。(p217。s)219。(216。q)174。s 219。r)217。216。p218。q)174。s 結論:(p174。q是有效結論例6 用歸結證明法構造下面推理的證明: 前提:(p174。q⑥置換⑧ 216。(p217。r②③拒取式 ⑤ 216。s, p 結論: 216。(p217。q218。s 結論: p174。p218。s 結論: 216。q)是有效結論例3 構造推理的證明: 若明天是星期一或星期三, 我就有 , , 明天 設 p:明天是星期一, q:明天是星期三，r:我有課，s:我備課 前提:(p218。r前提引入⑦ r⑤⑥假言推理 ⑧ r217。s前提引入② 216。s, 216。m2218。q)218。216。p217。 216。p218。q174。p219。q174。q218。q219。216。q)217。q219。p174。M4217。m3218。(p217。(216。p216。q)218。174。p217。r，(3)(p216。(2)若B去, 則C不能去。q)218。r)219。q217。q217。q216。q)218。m7p217。 m1218。r)218。r)218。r)218。(216。r)218。r 219。r 與 p217。q)174。 m2218。217。q)218。q)219。m3(216。q)218。q218。(p217。 m5218。r)219。q217。q217。q217。r)218。p216。217。q)218。r 219。m3重言式(3)C 219。 1 219。 216。217。 p218。q)174。 p174。 216。M5217。r 219。M6217。218。(216。p216。q216。q218。r)的主合取范式解 216。p217。 m5218。 m7 得A219。r)219。q217。q217。q217。 m1r 219。p216。q217。217。q 219。q217。q)218。M7 可記作219。218。 M3217。218。218。r同一律, 矛盾律219。p)216。218。r)分配律219。(p216。(p218。217。218。218。(216。r 219。 S(0,2,4,5,6)(2)216。 m2218。q)216。 m2218。q216。q216。217。r)218。p216。q)216。p218。 m4218。(p216。217。(216。1同一律219。q 219。q)216。218。218。218。218。q)216。218。 216。(p174。(p174。1217。218。q))217。r)解((p217。q)218。(216。p)（蘊涵等值式）219。p218。q216。174。 0（零律）該式為矛盾式.(2)(p174。217。217。p218。q)219。(p174。r)(p174。(p217。 216。p216。(216。(q174。r)219。 p2)000是成真賦值，001是成假賦值公式B=(p174。 p2217。p(8)174。p(5)除非天冷，174。q(2)因為天冷，174。u)∨(216。n)結論成立, 要證結論 對n++1是素數(shù), 則結論成立。1, 1+2+ … +n=n(n+1)/2 證=1時, 1=1180。C, 則B=反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有A199。B217。B217。B(AB=A)219。B 222。B 219。B198。BA199。~A)=(A200。(~B200。(A200。~B)200。 x206。A222。B, 則P(A)205。x207。A證 x x206。x206。A199。A200。A218。A200。C)(A200。 ~C(交換律,結合律)=(A – B)– C(補交轉換律)例6 證明(A200。)(矛盾律)= A 199。 ~C 199。 ~B)200。 ~C)199。 ~C)(補交轉換律)=(A 199。E)(交換律)= A199。B)(同一律)= A199。(A199。 x206。E(交的定義)219。E219。x206。 x206。 x206。C)(并,交的定義)(3)A200。x206。(x206。(x206。(x206。(B199。B)199。B200。B218。A218。A(交換律)證 xx206。B={ x | x是外地走讀生}(AB)199。故對任意f∈F，d(f)＝3。證明由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是229。)＝a*b＝x?！蔊也是a*x＝b的解，則x162。證明 設e是群的幺元。(3)顯然當|m|＝|n|時，才存在雙射。五、（15分）令X＝{x1，x2，…，xm}，Y＝{y1，y2，…，yn}。(4)不成立。(2)不成立。(5)若R和S是自反的，則R∩S是自反的。0，{{0}}，{0，{0}}四、（15分）設R和S是集合A上的任意關系，判斷下列命題是否成立？(1)若R和S是自反的，則R*S也是自反的。{0}，{{0}}，{0，{0}} P(B)197。1}，{198。B。Q(a)T(1)，US(5)S(a)T(2)，I(6)Q(a)T(4)(5)，I(7)H(a)T(2)，I(8)Q(a)∧H(a)T(6)(7)，I(9)x(Q(x)∧H(x)174。H(x)：x是身體健康的；S(x)：x是事業(yè)獲得成功的人；F(x)：x是事業(yè)半途而廢的人；則推理化形式為：x(S(x)174。二、（15分）在謂詞邏輯中構造下面推理的證明：每個科學家都是勤奮的，每個勤奮又身體健康的人在事業(yè)中都會獲得成功。Q)174。(P∨Q∨R)∧(P∨Q∨216。Q)∧(P∨Q∨R)219。Q∧R))219。R))219。（2）因為(P175。Q)174。P∧Q)219。Q)∨(216。216。Q)174。(P∧216。(P171。mm1m1，所以n≤m2/4。九、（10分）給定二部圖G＝，且|V1∪V2|＝m，|E|＝n，證明n≤m/4。任取a∈H，由e、a∈H得a－1＝e*a－1∈H。對任意的a、b∈H有a*b－1∈H。0247。247。1231。(3)對于R的關系矩陣，由于對角線上不全為1，R不是自反的；由于對角線上存在非0元，R不是反自反的；由于矩陣不對稱，R不是對稱的；經過計算可得 230。 0247。1232。231。(2)寫出R的關系矩陣。(2)對任意的∈RR，令x＝uw2u+w2－1，y＝uw2，則f()＝u+w2＋uw2，u+w2－＝，所以f是滿射。(2)證明f是滿射。由數(shù)學歸納法知，對任意的正整數(shù)n，Rn＝R。R。設n＝k時，Rk＝R。B＝A197。C。B222。C；當x207。A197。x207。(3)成立。解(1)不一定。(2)若A∩B＝A∩C，則B＝C。216。C(x)T(1)，E(3)216。B(x))，x(B(x)∨C(x))，216。有的人不喜歡騎自行車，因而有的人不喜歡步行。(T174。((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))219。x(P(x)174。F)∧(T174。(T174。((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))219。解：設論域為{1，2}。M2∧M4∧M6 219。Q∨R)∧(P∨216。Q∨R)219。(216。(P∨Q)∨R219。R)。T 所以，(P174。(P∨Q∨216。P∨R))219。(P∧216。(P∧216。((216。R))174。R)（2）求(P∨Q)174。參考文獻[1] 屈婉玲,耿素云,[M].北京:.[2] 黃巍,金國祥.”離散數(shù)學”課程教學改革的探討[J].中國電力教育,2009(8):8283.[3] 周小燕,[J].浙江科技學院學報,2007,19(2):156158.[4] 龍浩,《離散數(shù)學》課[J].貴陽學院學報,2007,2(1):5357.[5] [J].湖南工業(yè)職業(yè)技術學院學報,2008,8(5)://第四篇：離散數(shù)學離散數(shù)學試題（A卷答案）一、（10分）（1）證明(P174。必要時,教師可以批改一部分作業(yè),其他作業(yè)讓同學們之間互相檢查和批改,不僅可以督促學生學習,更能讓學生在批改其他同學作業(yè)時逐步認識到自身的缺陷和不足,以備今后更有針對性地學習。3 合理布置作業(yè),認真批改作業(yè),有針對性地安排習題課和課后答疑學數(shù)學就要做數(shù)學，《離散數(shù)學》的學習也不例外。很多人認為,大學教學課時緊,內容多,關鍵靠學生自主學習,我卻認為并不完全是這樣的。對于離散數(shù)學中比較重要、比較抽象的概念和定理,如邏輯的推理理論、關系的性質、群、圖等,認真分析,用多種方式和方法深入講解,可以使用解析法、圖示法、矩陣法舉實例等多種方法講解。認真?zhèn)湔n,合理準備教學內容和安排教學環(huán)節(jié),優(yōu)化教學方式方法備好課是教學取得預期效果的前提和基礎,針對學生學習具體情況,合理準備教學內容和安排教學環(huán)節(jié),使用恰當?shù)慕虒W方法,在教學中可以起到事半功倍的效果。離散數(shù)學課程在課堂教學難度、教學時間等方面的原因,很多學校都出現(xiàn)師生、學生之間的交流較少，從而使學生學習困難。方法性強：離散數(shù)學的特點是抽象思維能力的要求較高。通過一學期的學習和專研,我積累了少許經驗,總結了一些關于離散數(shù)學的教學方法，僅供大家參考。本文從離散數(shù)學內容、學生學習興趣的激發(fā)、教學內容的安排、教學方式方法的使用等方面,探討了如何上好、學好離散數(shù)學課。 空集, ∪ 并, ∩ 交,⊕ 對稱差,～ 絕對補,∑ 累加或主析取范式表達式縮寫 , － 普通減法, 247。（2）人固有一死。（2）如果 2 ＞ 3，則 2 ＞ 5。所以，明天沒有上體育課。65)為選擇題,將正確者填入[] 令 p：經一塹；q：長一智。（4）符號化為：（﹃p ∧ q）∨（p ∧ ﹃q）。（兼容或）（4）你明天不去上海，就去北京。[真命題]（6）今天沒有下雨，也沒有太陽，是陰天。（1）2月 17 號新學期開始。563..4。30%。54以下給出的符號串集合中，那些是前綴碼？將結果填入[] = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非]55(是非判斷題)11階無向連通圖G中17條邊，其任一棵生成樹 T 中必有6條樹枝 [非]56(是非判斷題)二元正則樹有奇數(shù)個