離散數(shù)學(xué)習(xí)題答案(最新)（精編版）

1、離散數(shù)學(xué)習(xí)題答案習(xí)題一及答案： p14-1514、將以下命題符號(hào)化：5李辛與李末是兄弟解：設(shè) p：李辛與李末是兄弟，則命題符號(hào)化的結(jié)果是p6王強(qiáng)與劉威都學(xué)過法語解：設(shè) p：王強(qiáng)學(xué)過法語； q：劉威學(xué)過法語；則命題符號(hào)化的結(jié)果是pq9只有天下大雨，他才乘班車上班解：設(shè) p：天下大雨； q：他乘班車上班；則命題符號(hào)化的結(jié)果是qp11下雪路滑，他遲到了解：設(shè) p：下雪； q：路滑； r ：他遲到了；則命題符號(hào)化的結(jié)果是( pq)r15、設(shè) p：2+3=5.q：大熊貓產(chǎn)在中國. r ：太陽從西方升起.求以下復(fù)合命題的真值： 4 (pqr )(pq)r )解： p=1 ， q=1 ， r=0 ，(pqr

2、 )(110)1 ，(pq)r )(11)0)(00)1學(xué)習(xí)文檔 僅供參考(pqr )(pq)r )11119、用真值表判斷以下公式的類型： 2 ( pp)qpqpq解：列出公式的真值表，如下所示：( pp)( pp)q001111011010100101110001由真值表可以看出公式有3 個(gè)成真賦值，故公式是非重言式的可滿足式。20、求以下公式的成真賦值：4( pq)q解：因?yàn)樵摴绞且粋€(gè)蘊(yùn)含式，所以首先分析它的成假賦值，成假賦值的條件是：( pq)1p0q0q0所以公式的 成真賦值有： 01，10， 11。習(xí)題二及答案： p385、求以下公式的主析取范式，并求成真賦值：2(p q)( q

3、r )解：原式( pq)q rqr(pp)qr(pqr )( pqr )m3m7 ，此即公式的主析取范式，所以成真賦值為011，111。6、求以下公式的主合取范式，并求成假賦值：2( pq)(pr )解：原式( ppr )(所以成假賦值為100。pqr )(pqr )m 4 ，此即公式的主合取范式，7、求以下公式的主析取范式，再用主析取范式求主合取范式：1( pq)r解：原式pq(rr )(p p)(q q)r )( pqr )( pqr )(pqr )(pqr )( pqr )( pqr )(pqr )(pqr )( pqr )( pqr )( pqr )m1m3m5m6m7 ，此即主析取范

4、式。主析取范式中沒出現(xiàn)的極小項(xiàng)為m0 ，m2 ，m4 ，所以主合取范式中含有三個(gè)極大項(xiàng)m 0 ， m 2 ，m 4 ，故原式的主合取范式m 0m 2m 4 。9、用真值表法求下面公式的主析取范式：1( pq)(pr )解：公式的真值表如下：( pq)(pr )00010000011011010110101111111000101101010111001011110101pqrppqpr由真值表可以看出成真賦值的情況有7 種，此 7 種成真賦值所對(duì)應(yīng)的極小項(xiàng)的析取即為主析取范式，故主析取范式m1m2m3m4m5m6m7習(xí)題三及答案： p52-5411、填充下面推理證明中沒有寫出的推理規(guī)則。前提：

5、結(jié)論： s證明：pq,qr , rs, p p前提引入pq前提引入 q析取三段論qr前提引入 r析取三段論rs前提引入 s假言推理15、在自然推理系統(tǒng)p 中用附加前提法證明下面推理：2前提： ( pq)(rs),( st)u結(jié)論： pu證明：用附加前提證明法。 p附加前提引入pq附加( pq)( rs)前提引入r ss假言推理化簡(jiǎn)st附加(st)u前提引入 u假言推理故推理正確。16、在自然推理系統(tǒng)p 中用歸謬法證明下面推理：1前提： pq，rq ， rs結(jié)論：p證明：用歸謬法 p結(jié)論的否認(rèn)引入pq前提引入q假言推理rq前提引入r析取三段論rs前提引入 r化簡(jiǎn) rr合取由于 rr0 ，所以推理

6、正確。17、在自然推理系統(tǒng)p 中構(gòu)造下面推理的證明：只要 a 曾到過受害者房間并且11 點(diǎn)以前沒離開， a 就是謀殺嫌犯。 a 曾到過受害者房間。如果 a 在 11 點(diǎn)以前離開，看門人會(huì)看見他?？撮T人沒有看見他。所以，a 是謀殺嫌犯。解：設(shè) p：a 到過受害者房間， q： a 在 11 點(diǎn)以前離開， r： a 是謀殺嫌犯， s：看門人看見過 a。則前提： ( pq)結(jié)論： r證明：r ， p ， qs ，sqs前提引入s前提引入q拒取式p前提引入pq合取引入( pq)r前提引入r假言推理習(xí)題四及答案： p65-675、在一階邏輯中將以下命題符號(hào)化：2有的火車比有的汽車快。解： 設(shè) f(x)：

7、x 是火車， g(y)： y 是汽車， h(x,y) ： x 比 y 快；則命題符號(hào)化的結(jié)果是：xy( f ( x)g ( y)h ( x,y)3不存在比所有火車都快得汽車。解： 設(shè) f(x)： x 是汽車， g(y)： y 是火車， h(x,y) ： x 比 y 快；則命題符號(hào)化的結(jié)果是：x( f ( x)y(g( y)h ( x,y) 或x( f ( x)y(g( y)h ( x, y)9、給定解釋i 如下：(a) 個(gè)體域?yàn)閷?shí)數(shù)集合r 。(b) 特定元素 a0 。(c) 函數(shù)f ( x, y)xy, x,yr 。(d) 謂詞f ( x, y) :xy, g( x,y) :xy, x, yr

8、 。給出以下公式在i 下的解釋，并指出它們的真值：2xy( f ( f( x, y), a)g( x,y)解：解釋是：xy( xy0xy)，含義是：對(duì)于任意的實(shí)數(shù)x， y，假設(shè) x-y=0 則 x<y 。該公式在i 解釋下的真值為假。14、證明下面公式既不是永真式也不是矛盾式：1x( f ( x)y(g( y)h ( x, y)解：取解釋i 如下：個(gè)體域?yàn)槿倐€(gè)體域，f (x) ： x 是兔子，g( y) ： y 是烏龜，h ( x, y) ： x 比 y 跑得快 ，則該公式在解釋i 下真值是1；取解釋i ' 如下：h ( x, y) ： x 比 y 跑得慢，其它同上，則該公式在

9、解釋i ' 下真值是0；故公式 1既不是永真式也不是矛盾式。此題答案不唯一，只要證明公式既不是永真式也不是矛盾式的每個(gè)解釋合理即可。習(xí)題五及答案： p80-8115、在自然推理系統(tǒng)n中，構(gòu)造下面推理的證明：3前提：x(f ( x)g( x) ，xg (x)結(jié)論： 證明：xf ( x)xg( x)xg( x)g(c)前提引入置換 ui 規(guī)則x( f (x)g(x)前提引入f (c)g(c)ui 規(guī)則f (c)析取三段論xf ( x)eg 規(guī)則22、在自然推理系統(tǒng)n中，構(gòu)造下面推理的證明：2凡大學(xué)生都是勤奮的。王曉山不勤奮。所以王曉山不是大學(xué)生。解：設(shè) f(x)： x 為大學(xué)生， g(x)

10、 ：x 是勤奮的， c：王曉山則前提：x(f ( x)g (x) ，g(c)結(jié)論： 證明：f (c)x( f (x)g( x)前提引入f (c)g(c)ui 規(guī)則g(c)前提引入f (c)拒取式25、在自然推理系統(tǒng)n中，構(gòu)造下面推理的證明：每個(gè)科學(xué)工作者都是刻苦鉆研的，每個(gè)刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學(xué)工作者， 并且是聰明的。所以， 王大海在他的事業(yè)中將獲得成功。 個(gè)體域?yàn)槿祟惣辖猓涸O(shè) f(x)：x 是科學(xué)工作者， g(x)：x 是刻苦鉆研的， h(x) ：x 是聰明的， i(x) ：x 在他的事業(yè)中獲得成功， c：王大海則前提：x(f ( x)g (x) ，x(

11、g( x)h ( x)i ( x) ，f (c)h (c)結(jié)論： 證明：i (c)f (c)h (c)前提引入f (c)化簡(jiǎn)h (c)化簡(jiǎn)x( f (x)g( x)前提引入f (c)g(c)ui 規(guī)則g(c)假言推理g(c)h (c)合取引入x(g(x)h (x)i (x)前提引入g(c)h (c)i (c) ui 規(guī)則i (c)假言推理習(xí)題六及答案習(xí)題七及答案： p132-135 *22 、給定 a1,2,3,4，a 上的關(guān)系 r1,3 , 1,4 , 2,3 , 2,4 , 3,4，試1畫出 r 的關(guān)系圖；2說明 r 的性質(zhì)。解：11234稱的；2r 的關(guān)系圖中每個(gè)頂點(diǎn)都沒有自環(huán)，所以r

12、是反自反的，不是自反的；r 的關(guān)系圖中任意兩個(gè)頂點(diǎn)如果有邊的都是單向邊，故r 是反對(duì)稱的，不是對(duì)r 的關(guān)系圖中沒有發(fā)生頂點(diǎn)x 到頂點(diǎn) y 有邊、頂點(diǎn)y 到頂點(diǎn) z 有邊，但頂點(diǎn)x到頂點(diǎn) z 沒有邊的情況，故r 是傳遞的。26 設(shè) a1,2,3,4,5,6， r 為 a 上的關(guān)系， r 的關(guān)系圖如圖 7.13 所示：1求 r2 , r3 的集合表達(dá)式；2求 r(r), s(r), t(r) 的集合表達(dá)式。2解：1由 r 的關(guān)系圖可得 r1,5 , 2,5 , 3,1 , 3,3 , 4,52所以 rr r3,1 , 3,3 , 3,5， r3rr3,1 , 3,3 , 3,5，可得 rn3,1

13、, 3,3 , 3,5,當(dāng)n>=2 ；2r(r)=ri a1,5 , 2,5 , 3,1 , 3,3 , 4,5 , 1,1 , 2,2 , 4,4 , 5,5 , 6,6，s( r)rr 11,5, 5,1 , 2,5 , 5,2 , 3,1 , 1,3 , 3,3 , 4,5 , 5,4t( r)rr2r 3.rr21,5 , 2,5 , 3,1 , 3,3 , 3,5 , 4,546、分別畫出以下各偏序集a, r的哈斯圖， 并找出 a 的極大元、極小元、最大元和最小元。1 ra, d ,a,c, a, b ,a, e ,b, e ,c, e ,d, ei a解：哈斯圖如下：ebcd

14、afa 的極大元為 e、f，極小元為 a、f； a 的最大元和最小元都不存在。48、設(shè)a, r 和b,s為偏序集，在集合 ab 上定義關(guān)系 t 如下：a1, b1, a2 ,b2ab,a1, b1ta2 ,b2a1ra2b1sb2證明 t 為ab 上的偏序關(guān)系。證明：1自反性：任取 a1,b1ab，則：r為偏序關(guān)系，具有自反性， s為偏序關(guān)系，具有自反性，a1ra1 b1sb1a1ra1b1sb1又 a1 ,b1ta2 , b2a1ra2b1sb2，a1, b1ta1 ,b1，故t具有自反性2反對(duì)稱性：任取 a1,b1, a2 ,b2ab，若a1 ,b1ta2, b2且 a2 , b2ta1

15、,b1，則有：a1 ra2 a2 ra1b1sb2 b2sb1（1）（2）a1ra2 b1 sb2a2 ra1，又r為偏序關(guān)系，具有反對(duì)稱性，所以a1a2b2 sb1，又s為偏序關(guān)系，具有反對(duì)稱性，所以b1b2a1, b1a2 ,b2，故t具有反對(duì)稱性3傳遞性：任取a1,b1, a2 ,b2，a3 ,b3ab，若a1 ,b1ta2, b2且a2, b2ta3 ,b3，則有：a1,b1 a2 ,b2ta2 ,b2ta3 , b3a1ra2 a2 ra3b1sb2 b2sb3a1ra2a2 ra3 , 又r為偏序關(guān)系，具有傳遞性，所以a1ra3b1 sb2b2 sb3 ,又s為偏序關(guān)系，具有傳遞性

16、，所以b1sb3a1ra3b1sb3a1, b1ta3 ,b3，故t具有傳遞性。綜合 123知 t 具有自反性、反對(duì)稱性和傳遞性，故t 為 ab 上的偏序關(guān)系。習(xí)題九及答案： p179-180 8、s=qq,q 為有理數(shù)集，為s上的二元運(yùn)算，a,b,x,ys有a,bx,yax,ay+b1運(yùn)算在s上是否可交換、可結(jié)合？是否為冪等的？2運(yùn)算是否有單位元、零元？如果有，請(qǐng)指出，并求出s中所有可逆元素的逆元。解：1x, ya,bxa,xb+yax,bx+ya,b運(yùn)算不具有交換律x, yx, ya,bc,dax,bx+yc,d acx,adx+bx+y而 x, y x, ya,bc,d*ac,ad+bx

17、ac,xad+xb+yacx,adx+bx+yx, ya,bc,d運(yùn)算有結(jié)合律任取 a,bs，則有：a,ba,ba2 , adb運(yùn)算無冪等律2a,b令 a,b *x, ya,b 對(duì)a,bs均成立則有： ax,ay+ba,b 對(duì)a,bs均成立axaa x10 對(duì)aybbay0x10x1a,b 成立必定有y0y0運(yùn)算的右單位元為運(yùn)算的單位元為1，01，0，可驗(yàn)證1，0也為運(yùn)算的左單位元，令 a,b *x, yx, y，若存在x, y使得對(duì)a,bs上述等式均成立，則存在零元，否則不存在零元。由 a,b *x, yx, yax,ay+baxx aybyx, ya1 x0a1 y+b0由于 a1 y+b

18、0不可能對(duì)a,bs均成立，故 a,b *x, yx, y不可能對(duì)a,bs均成立，故不存在零元；設(shè)元素a,b的逆元為x, y1，則令a,b *x, ye1，0ax1xa（當(dāng)a0）ayb0yb a當(dāng)a0時(shí)，a,b的逆元不存在；當(dāng)a0時(shí)，a,b 的逆元是1 ,baa11、設(shè)s1，2，.,10，問下面的運(yùn)算能否與s構(gòu)成代數(shù)系統(tǒng)s， ?如果能構(gòu)成代數(shù)系統(tǒng)則說明運(yùn)算是否滿足交換律、結(jié)合律，并求運(yùn)算的單位元和零元。3 xy =大于等于 x和y的最小整數(shù)；解：3由* 運(yùn)算的定義可知：xy=max(x,y) ，x,ys,有xys，故運(yùn)算在s上滿足封閉性，所以運(yùn)算與非空集合s能構(gòu)成代數(shù)系統(tǒng)；任取x,ys,有xy=

19、max(x,y)=max(y,x)=yx,所以運(yùn)算滿足交換律；任取x,y,zs,有( xy)z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z)=x(yz), 所以運(yùn)算滿足結(jié)合律；任取xs，有 x1=max(x,1)=x=max(1,x)=1x,所以運(yùn)算的單位元是1；任取xs，有 x10=max(x,10)=10=max(10,x)=10x,所以運(yùn)算的零元是10；16、設(shè)v11, 2,3, ,1 , 其中xy表示取x和y之中較大的數(shù)。v 25,6,6，其中xy表示取x和y之中較小的數(shù)。求出v1和v 2的所有的子代數(shù)。指出哪些是平凡的子代數(shù)，哪些是真子代數(shù)。解：

20、（ 1） v1的所有的子代數(shù)是：1,2,3, ,1 ,1 , ,1 ,1,2 , ,1 ,1,3 , ,1 ；v1的平凡的子代數(shù)是：1,2,3, ,1 ,1 , ,1 ；v1的真子代數(shù)是：1 , ,1 ,1,2 , ,1 ,1,3 , ,1 ；（ 2） v 2的所有的子代數(shù)是：5,6,6， 6 ,6 ；v 2的平凡的子代數(shù)是：5,6,6， 6 ,6；v 2的真子代數(shù)是：6 ,6。習(xí)題十一及答案： p218-2191、圖 11.11給出了 6 個(gè)偏序集的哈斯圖。判斷其中哪些是格。如果不是格，說明理由解： a、c、f 是格；因?yàn)槿我鈨蓚€(gè)元素構(gòu)成的集合都有最小上界和最大下界； b不是格，因?yàn)閐,e 的最大下界不存在； d不是格，因?yàn)閎,c 的最小上界不存在； e不是格，因?yàn)閍,b 的最大下界不存在。2、以下各集合低于整除關(guān)系都構(gòu)成偏序集，判斷哪些偏序集是格。 1 l=1 ， 2， 3， 4， 5 ； 2 l=1 ， 2， 3，