離散數學習題答案解析

1、精品離散數學習題答案習題一及答案：(P14-15)14、將下列命題符號化：(5)李辛與李末是兄弟解：設p：李辛與李末是兄弟，則命題符號化的結果是p(6)王強與劉威都學過法語解：設p：王強學過法語；q：劉威學過法語；則命題符號化的結果是pq(9)只有天下大雨，他才乘班車上班解：設p：天下大雨；q：他乘班車上班；則命題符號化的結果是qp(11)下雪路滑，他遲到了解：設p：下雪；q：路滑；r：他遲到了；則命題符號化的結果是(pq)r15、設p：2+3=5.q:大熊貓產在中國.r:太陽從西方升起.求下列復合命題的真值：(4)(pqr)(pq)r)解：p=1,q=1,r=0,(pqr)(110)1,(p

2、q)r)(11)0)(00)1(pqr)(pq)r)11119、用真值表判斷下列公式的類型：(pp)q解：列出公式的真值表，如下所示:pqpq(pp)(pp)q001111011010100101110001由真值表可以看出公式有3個成真賦值，故公式是非重言式的可滿足式。20、求下列公式的成真賦值：(4)(pq)q解：因為該公式是一個蘊含式，所以首先分析它的成假賦值，成假賦值的條件是：(pq)1p0q0q0所以公式的成真賦值有：01，10，11。習題二及答案：(P38)5、求下列公式的主析取范式，并求成真賦值：(2)(pq)(qr)解：原式(pq)qrqr(pp)qr(pqr)(pqr)m3m

3、7，此即公式的主析取范式，所以成真賦值為011，111。*6、求下列公式的主合取范式，并求成假賦值：(2)(pq)(pr)解：原式(ppr)(pqr)(pqr)M4，此即公式的主合取范式，所以成假賦值為100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：(1)(pq)r解：原式pq(rr)(pp)(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m5m6m7，此即主析取范式。主析取范式中沒出現的極小項為m0，m2，m4，所以主合取范式中含有三個極大項M0，M2，M4，故原式的主合取范式M0M2M4。9、

4、用真值表法求下面公式的主析取范式：(1)(pq)(pr)解：公式的真值表如下:pqrppqpr(pq)(pr)000100000110110101101011111110001011；010110111001011110101由真值表可以看出成真賦值的情況有7種，此7種成真賦值所對應的極小項的析取即為主析取范式，故主析取范式m1m2m3m4m5m6m7習題三及答案：(P52-54)11、填充下面推理證明中沒有寫出的推理規(guī)則。前提：pq,qr,rs,p結論：s證明：p前提引入pq前提引入q析取三段論qr前提引入r析取三段論rs前提引入s假言推理15、在自然推理系統(tǒng)P中用附加前提法證明下面推理:(

5、2)前提：(pq)(rs),(st)u結論：pu證明：用附加前提證明法。p附加前提引入 pq附加 (pq)(rs)前提引入 rs假言推理 s化簡 st附加 (st)u前提引入 u假言推理故推理正確。16、在自然推理系統(tǒng)P中用歸謬法證明下面推理：(1)前提：pq，rq，rs結論：p證明：用歸謬法 p結論的否定引入 pq前提引入 q假言推理 rq前提引入 r析取三段論 rs前提引入 r化簡 rr合取由于rr0，所以推理正確。17、在自然推理系統(tǒng)P中構造下面推理的證明：只要A曾到過受害者房間并且11點以前沒離開，A就是謀殺嫌犯。A曾到過受害者房間。如果A在11點以前離開，看門人會看見他?？撮T人沒有看

6、見他。所以，A是謀殺嫌犯。解：設p：A到過受害者房間，q：A在11點以前離開，r：A是謀殺嫌犯，s：看門人看見過A。則前提：(pq)r，p，qs，s結論：r證明： qs前提引入 s前提引入 q拒取式前提引入pq合取引入(pq)r前提引入r假言推理習題四及答案：(P65-67)5、在一階邏輯中將下列命題符號化：(2)有的火車比有的汽車快。解：設F(x):x是火車，G(y):y是汽車，H(x,y):x比y快；則命題符號化的結果是：xy(F(x)G(y)H(x,y)(3)不存在比所有火車都快的汽車。解：方法一：設F(x):x是汽車，G(y):y是火車，H(x,y):x比y快；則命題符號化的結果是：x

7、(F(x)y(G(y)H(x,y)或x(F(x)y(G(y)H(x,y)方法二：設F(x):x是火車，G(y):y是汽車，H(x,y):x比y快；則命題符號化的結果是：x(G(x)y(F(y)H(x,y)或xy(G(x)(F(y)H(x,y)9、給定解釋I如下：(a) 個體域為實數集合R。(b) 特定元素a0。(c) 函數f(x,y)xy,x,yR。(d) 謂詞F(x,y):xy,G(x,y):xy,x,yR。給出以下公式在I下的解釋，并指出它們的真值：(2)xy(F(f(x,y),a)G(x,y)解：解釋是：xy(xy0xy)，含義是：對于任意的實數x，y，若x-y=0則x<y。該公式

8、在I解釋下的真值為假。14、證明下面公式既不是永真式也不是矛盾式：(1)x(F(x)y(G(y)H(x,y)解：取解釋I如下：個體域為全總個體域，F(x)：x是兔子，G(y)：y是烏龜，H(x,y)：x比y跑得快，則該公式在解釋I下真值是1；''取解釋I如下：H(x,y)：x比y跑得慢，其它同上，則該公式在解釋I下真值是0；故公式(1)既不是永真式也不是矛盾式。此題答案不唯一，只要證明公式既不是永真式也不是矛盾式的每個解釋合理即可。習題五及答案：(P79-81)5、給定解釋I如下：(a) 個體域D=3,4(b) f(x):f(3)4,f(4)3(c) F(x,y):F(3,3)

9、F(4,4)0,F(3,4)F(4,3)1試求下列公式在I下的真值：(1) xyF(x,y)解：方法一：先消去存在量詞xyF(x,y)x(F(x,3)F(x,4)(F(3,3)F(3,4)(F(4,3)F(4,4)(01)(10)115、在自然推理系統(tǒng)N中，構造下面推理的證明：(3)前提：x(F(x)結論：xF(x)證明： xG(x) xG(x) G(c) x(F(x)G(x) F(c)G(c) F(c)G(x) ， xG(x)前提引入置換UI規(guī)則前提引入 UI 規(guī)則析取三段論EG規(guī)則 xF(x)*22、在自然推理系統(tǒng)N中，構造下面推理的證明：(2)凡大學生都是勤奮的。王曉山不勤奮。所以王曉山

10、不是大學生。解：設F(x)：x為大學生，G(x)：x是勤奮的，c：王曉山則前提：x(F(x)G(x)，G(c)結論：F(c)證明： x( F (x)G(x)前提引入 F (c) G(c) UI 規(guī)則 G(c)前提引入F (c)拒取式25、在自然推理系統(tǒng)N中,構造下面推理的證明:每個科學工作者都是刻苦鉆研的，每個刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學工作者， 并且是聰明的。所以， 王大海在他的事業(yè)中將獲得成功。 (個體域為人類集合)解：設F(x) : x是科學工作者，G(x) : x是刻苦鉆研的，H(x) : x是聰明的，I(x) : x在他的事業(yè)中獲得成功， c ：王大海則

11、前提： x(F(x) G (x) ， x(G(x) H(x) I(x) ， F(c) H(c)結論： I (c)證明： F (c) H (c)前提引入 F (c)化簡 H (c)化簡 x( F (x)G(x)前提引入 F (c) G(c) G(c) G(c) H(c) UI 規(guī)則假言推理合取引入 x(G(x) H (x) I (x) 前提引入 G(c)H(c)I(c)UI規(guī)則 I(c)假言推理習題六及答案(P99-100)28、化簡下述集合公式：(3)(AB)C)(AB)C)(AB)C)(AB)C)解：(AB)C)(AB)C)(AB)C)(AB)C)(AB)(AB)A30、設A,B,C代表任意

12、集合，試判斷下面命題的真假。如果為真，給出證明；如果為假，給出反例。(6)(AB)AB解：該命題為假，(AB)ABA，如果BA，則BAB，否則BAB，故BAB為假。舉反例如下：A1,2,B1,3,則(AB)A3B。(8)ABACBC解：該命題為假，舉反例如下：如果B，C都是A的子集，則ABAC一定成立，但bC不一定成立，例如：A1,2,B1,C2,則ABACA,但BC。33、證明集合恒等式：(1)A(B:A)BA證明：A(B:A)(AB)(A:A)(AB)ABBA習題七及答案：(P132-135)26設A1,2,3,4,5,6,R為A上的關系，R的關系圖如圖7.13所示：(1)求R2,R3的集

13、合表達式；(2)求r(R),s(R),t(R)的集合表達式。解：(1)由R的關系圖可得R(1,5),(2,5),(3,1),3,3),(4,5)所以R2RR(3,1),3,3),(3,5)，R3R2R(3,1),(3,3),(3,5)，可得Rn(3,1),<3,3),3,5)，當n>=2;(2) r(R尸RUIa(1,5),2,5),(3,1),3,3),4,5),(1,11,(2,2),(4,4),(5,5),(6,6),s(R)RUR1；1,5,5,1;,.2,5.,5,2：,3,1,1,3：,3,3,4,5：,5,4,t(R)RUR2UR3URUR2；1,5,2,5；,3,1

14、,3,3；,3,5；,4,5：41、設A=1,2,3,4,R為AA上的二元關系，a,b,c,dAA,a,bRc,dabcd(1)證明R為等價關系；(2)求R導出的劃分。(1)只需證明R具有自反性、對稱性和傳遞性即可，證明過程如下:(a)任取a,ba,b R a,b ，所以r具有自反性;(b)任取a,b ,c, dA A,若 a,b R c,d ,則有a bc,d Ra,b,所以R具有對稱性;(c)任取a,b ,c,d ,e, fA A,若a, bR c,d且 c,d R e, f則有a ba,b Re, f ，所以R具有傳遞性,綜合(a) (b)(c)可知：R為集合AA上的等價關系;感謝下載載

15、(2)先求出集合AA的結果：3,3 , 3,4 , 4,1 , 4,2 , 4,3 , 4,4 AA(1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,再分別求集合AA各元素的等價類，結果如下：1,1r1,1,1,2r2,1r1,2,2,1,1,3 r 2,2 r3,1r1,3,2,2,3,1,1,4 r2,4 r3,3 r4,2 r 2,4 , 3,34,2 ,3,4 r 4,3 r 3,44,3 ,2,3r3,2r4,1r1,4,2,3,3,2,4,1,4,4r4,4。等價關系R導出的劃分就是集合A關于R的商集A/R,而集合A關于R的商集A/R是由R的所有等價

16、類作為元素構成的集合，所以等價關系R導出的劃分是：1,1,1,2,2,1,1,3,2,2,3,1,1,4,2,3,3,2,4,1,2,4,3,3,4,2,3,4,4,3,4,446、分別畫出下列各偏序集(A,R)的哈斯圖，并找出A的極大元、極小元、最大元和最小元。(1) R(a,d),(a,c),(a,b),(a,e),(b,e),(c,e),(d,e)UIa解：哈斯圖如下:bA的極大元為e、f,極小元為a、f；A的最大元和最小元都不存在。*22、給定A1,2,3,4,A上的關系R(1,3),1,4),(2,3,2,4),3,4),試(D(2)畫出R的關系圖;說明R的性質。解：(1)(2) R

17、的關系圖中每個頂點都沒有自環(huán)，所以R是反自反的，不是自反的；的關系圖中任意兩個頂點如果有邊的都是單向邊，故R是反對稱的，不是對稱的；R的關系圖中沒有發(fā)生頂點x到頂點y有邊、頂點y到頂點z有邊，但頂點x到頂點z沒有邊的情況，故R是傳遞的。*48、設(A,R)和但S)為偏序集，在集合AB上定義關系T如下：a，bi：，a，b2：AB,：a1,bT：a2,b2；a1Ra2b1Sb2證明T為AB上的偏序關系。證明：(1)自反性：任取國心)AB,則：QR為偏序關系，具有自反性，aiRaiQS為偏序關系，具有自反性，biSb,aFabiSb又d,b1T包心；aiRa2bSb2,(ai,h)T(ai,2,故T

18、具有自反性(2)反對稱性：任取儂心),上2口2AB,若(a川T(a2,t2且,2心)丁(濟川,則有：aiRa2WSb(i)a2Rab2Sb(2)aiRa2a2Ra1,又R為偏序關系，具有反對稱性，所以aia2biSbBSb,又S為偏序關系，具有反對稱性，所以bib2(ai,b)(a2,b2),故T具有反對稱性(3)傳遞性：任取卜,6),12掃2),k3也aB,若(ai,bi)T(a2,b2)且(a2,b2)T回),則有：ai,b1)T:a2,b2):aiRa2b1st2a2，b2；T3,0；a2Ra3bzSAaiRa2a2Ra3,又R為偏序關系，具有傳遞性，所以aiRa3b1sb2dS*又S為

19、偏序關系，具有傳遞性，所以b1sb3aiRa3b1sb3包上斤(a3,b3)，故T具有傳遞性。綜合(1)(2)(3)知T具有自反性、反對稱性和傳遞性，故T為AB上的偏序關系。習題九及答案：(P179-180)8、S=Q Q,Q為有理數集，為S上的二元運算，(a,b),(x,y) S有：a,b；: ： x,y ；: ax,ay+b ：(1)運算在S上是否可交換、可結合？是否為曷等的？(2)運算是否有單位元、零元？如果有，請指出，并求出 S中所有可逆元素的逆元解：(1)：x, y) ；a,b； :.xa,xb+y )ax,bx+y ： a,b, :x, y .運算不具有交換律x,y ；a,b； 1

20、c,d； ax,bx+y： ：c,d acx,adx+bx+y.而：x,y：a,b； ：c,d；x, y * ac,ad+bxac,xad+xb+y； acx,adx+bx+y ；x,y' ：a,b；：c,d；運算有結合律任取.'a，b s,則有：a,b； ab:a2,ab b； :a,b運算無幕等律(2)令a,b*(x, y) (a,b)對(a,b)則有：、ax,ay+b： ,©,：對 ；a,b.ax aay b bax 10 對ay 0s均成立s均成立a,b成立必定有運算的右單位元為(1,0),可驗證(1,0)也為運算的左單位元,運算的單位元為.：1,0；-令(a

21、,b)*(x,y)(x,y),若存在(x,y)使得又t(a,b)s±述等式均成立,則存在零元，否則不存在零元。由a,b*x,y：x,yax,ay+b；x,yaxxa1x0aybya1y+b0由于a1y+b0不可能對：a,b;s均成立，故(a,b)*(x,y)(x,y)不可能對(a,b)s均成立，故不存在零元；1x a （當 a 0） by a設兀素：a,b：的逆兀為；x,y.,則令.a,b；：*'；x,y)eJ,0.ax1ayb0當a0時,(a,b)的逆元不存在；當a0時，ab；的逆元是1,:11、設S1,2,10,問下面的運算能否與S構成代數系統(tǒng)(S,)?如果能構成代數系統(tǒng)

22、則說明運算是否滿足交換律、結合律，并求運算的單位元和零元。(3)x丫=大于等于x和y的最小整數；解：(3)由*運算的定義可知：xy=max(x,y),x,yS,有xyS,故運算在S上滿足封閉性，所以運算與非空集合S能構成代數系統(tǒng)；任取x,yS,有xy=max(x,y)=max(y,x)=yx,所以運算滿足交換律；任取x,y,zS,有(xy)z=max(max(x,y),z尸max(x,y,z尸max(x,max(y,z)尸x(yz),所以運算滿足結合律;任取xS,有x1=max(x,1)=x=max(1,x)=1x,所以運算的單位元是1;任取xS,有x10=max(x,10)=10=max(1

23、0,x)=10x,所以運算的零元是10;16、設V111,2,3,1),其中xy表示取x和y之中較大的數。V2(5,6,6%其中xy表示取x和y之中較小的數。求出乂和V2的所有的子代數。指出哪些是平凡的子代數，哪些是真子代數。解：(1)Vi中運算的單位元是1,V的所有的子代數是：(1,2,3,1),(1,1),(1,2,1),(1,3,1);M的平凡的子代數是：j1,2,3,1.,：1,1;M的真子代數是：1,1,：1,2,111,3,1；;(2) 丫2中運算的單位元是6,V 2的所有的子代數是：(5,6,6),(6,6);V 2的平凡的子代數是：(5,6,6),6,6)；V 2的真子代數是：(6,6)。習題H一及答案：(P218-219)1、圖11.11給出了6個偏序集的哈斯圖。判斷其中哪些是格。如果不是格，說明理由解：(a)、(c)、(f)是格；因為任意兩個元素構成的集合都有最小上界和最大下界；(b)不是格，因為d,e的最大下界不存在；(d)不是格，因為b,c的最小上界不存在；(e)不是格，因為a,b的最大下界不存在。2、下列各集合低于整除關系都構成偏序集，判斷哪些偏序集是格。(1)L=1,2,3,4,5;L=1,2,3,6,12;解：畫出哈斯圖即可判斷出：(1)不是格，(2)是格。4、設L是格，