離散數(shù)學(xué)習(xí)題答案

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

2、 19、用真值表q (2)解：列出公式的真(p p)(p p) q(pqr)(110)1,(pq)r)(11)(pqr)(pq)判斷下列公式的類型：(pp)值表，如下所示：ppqq0 0 1 1 1 1 0 1 1 0 1 0100101110001由真值表可以看出公式有3個(gè)成真賦值，故公式是非重言式的可滿足式。20、求下列公式的成真賦值：(4)(pq)q解：因?yàn)樵摴绞且粋€(gè)蘊(yùn)含式，所以首先分析它的成假賦值，成假賦值的條件是：p0(pq)1q0q0成真賦值有：01,10)11。所以公式的習(xí)題二及答案：(P38)5、求下列公式的主析取范式，并求成真賦值：(2)(pq)(q)解：原式整理文檔(pq

3、)qr(pp)qrqr)此即公式的主析取范式,mm(pqr)(pqr)37所以成真賦值為011,111o*6、求下列公式的主合取范式，并求成假賦值：(2)(pq)(pr)解：原式，此即公式的主合取范式，M(ppr)(pqr)(pqr)4所以成彳及賦值為100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：(1)(pq)r解：原式pq(rr)(pp)(qq)r)(pqr)(pq)r(pq)r(pq)r(pq)r(pqr(pqr)(pq)r(pq)r(pq)r(pqr)此即主析取范式。mmmmm13567主析取范式中沒出現(xiàn)的極小項(xiàng)為，所以主合取范式中含有三個(gè)極大項(xiàng)，MMmmm02024)

4、故原式的主合取范式。MMMM40249、用真值表法求下面公式的主析取范式：(1)(pq)(pr)解：公式的真值表如下：pppqprqr(pq)(pr)00010000011011010110101111111000101101010111001011110101由真值表可以看出成真賦值的情況有7種，此7種成真賦值所對(duì)應(yīng)的極小項(xiàng)的析取即為主析取范式，故主析取范式mmmmmmm1234567習(xí)題三及答案：(P52-5e11、填充下面推理證明中沒有寫出的推理規(guī)則。前提：pq,qr,rs,p結(jié)論：s證明：p前提引入前提引入pqq析取三段論前提引入qrr析取三段論rs前提弓以s假言推理15、在自然推理系

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

6、殺嫌犯。解：設(shè)p:A到過受害者房間，q：A在11點(diǎn)以前離開，r：A是謀殺嫌犯，s:看門人看見過Aos則前提：，pqs(pq)r結(jié)論：r證明：前提引入耐引入前提引入p合取引意前提引東q)假言推理r習(xí)題四及答案：(P65-67)5、在一階邏輯中將下列命題符號(hào)化：(2)有的火車比有的汽車快。解：設(shè)F(x):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

7、(y)H(x,y)或方法二：設(shè)F(x):x是火車，G(y):y是汽車，H(x,y):x比y快；則命題符號(hào)化的結(jié)果是：x(G(x)y(F(y)H(x,y)xy(G(x)(F(y)H(x,y)或9、給定解釋I如下：(a)個(gè)體域?yàn)閷?shí)數(shù)集合Roa0(b)特定元素。f(x,y)xy,x,yR(c)函數(shù)。F(x,y):xy,G(x,y):xy,x,yR(d)謂詞。給出以下公式在I下的解釋，并指出它們的真值：xy(F(f(x,y),a)G(x,y)(2)xy(xy0xy)解：解釋是：，含義是：對(duì)于任意的實(shí)數(shù)x,y,若x-y=0則x=2(2),r(R)=RI1,52,5,3,1,3,3,4,5,1,122,4

8、,4,5,5,6,6A1s(R)RR1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4232t(R)RRR.RR1,5,2,5,3,1,3,3,3,5,4,41、設(shè)A=1,2,3,4,RAAa,b,c,dAA上的二元關(guān)系，a,bRc,dabcd(1)證明R為等價(jià)關(guān)系；(2)求R導(dǎo)出的劃分。(1)只需證明R具有自反性、對(duì)稱性和傳遞性即可，證明過程如下：a,bAAa,bRa,babab(a)任取，有，所以R具有自反性;a,b,c,dAAa,bRc,d(b)任取，若，c,dRa,babcdcdab則有，所以R具有對(duì)稱性；a,b,c,d,e,fAAa,bRc,dc,dRe,f(c)

9、任取，若且，cdefabefa,bRe,fabcd則有且，所以R具有傳遞性，AA綜合(a)(b)(c)可知：R為集合上的等價(jià)關(guān)系；AA(2)先求出集合的結(jié)果：AA1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4AA再分別求集合各元素的等價(jià)類，結(jié)果如下：1,11,1,R1,22,11,2,2,1,RR1,32,23,11,3,2,2,3,1,RRR1,42,33,24,11,4,2,3,3,2,4,1,RRRR2,43,34,22,4,3,3,4,2,RRR3,44,33,4,4,3,RR4,44,4。RA/RA/R等

10、價(jià)關(guān)系R導(dǎo)出的劃分就是集合A關(guān)于R的商集，而集合A關(guān)于R的商集是由R的所有等價(jià)類作為元素構(gòu)成的集合，所以等價(jià)關(guān)系R導(dǎo)出的劃分是：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,4A,R46、分別畫出下列各偏序集的哈斯圖，并找出A的極大元、極小元、最大元和最小元。（1）Ra,d,a,c,a,b,a,e,b,e,c,e,d,eA解：哈斯圖如下：ebcdfaA的極大元為e、f,極小元為a、f;A的最大元和最小元都不存在。A1,2,3,422、給定，A上的關(guān)系，試R1,3,1,4,2,3,2,4,3,4（1）畫出R的關(guān)系圖；（

11、2）說明R的性質(zhì)。解：（1）1234（2）R的關(guān)系圖中每個(gè)頂點(diǎn)都沒有自環(huán)，所以R是反自反的，不是自反的；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是傳遞的。A,R和B,S*48、設(shè)為偏序集，在集合上定義關(guān)系T如下：ABa,b,a,bAB,1122a,bTa,baRabSb11221212ffi明T為上的偏序關(guān)系。AB證明：(1)自反性：任取a,bAB,則：11R為偏序關(guān)系，具有自反性，aRa11S為偏序關(guān)系，具有自反性，bSb11aRabSbllll又a,bTa,baR

12、abSb,11221212a,bTa,b,故T具有自反性1111反對(duì)稱性：任取a,b,a,bAB,若a,bTa,b且a,bTa,b,則有：112211222211aRabSb(1)1212aRabSb(2)2121aRaaRa又R為偏序關(guān)系，具有反對(duì)稱性，所以aa122112bSbbSb,又S為偏序關(guān)系，具有反對(duì)稱性，所以bb122112a,ba,b,故T具有反對(duì)稱性1122(3)傳遞性：任取a,b,a,ha,bAB,若a,bTa,b且a,bTa,b,貝U有：11223311222233a,bTa,baRabSb11221212a,bTa,baRabSb22332323aRaaRa又R為偏序關(guān)

13、系，具有傳遞性，所以aRa122313bSbbSb又S為偏序關(guān)系，具有傳遞性，所以bSb122313aRabSba,bTa,b,故T具有傳遞性。13131133綜合(1)(2)(3)知T具有自反性、反對(duì)稱性和傳遞性，故T為上的偏序關(guān)系。AB習(xí)題九及答案：（P179-18。8、S=QQ,Q為有理數(shù)集，為S上的二元運(yùn)算，a,b,x,ys有a,bx,yax,ay+b（1）運(yùn)算在S上是否可交換、可結(jié)合？是否為塞等的？（2）。運(yùn)算是否有單位元、零元？如果有，請(qǐng)指出，并求出S中所有可逆元素的逆元解：（1）x,ya,bxa,xb+yax,bx+ya,bx,y運(yùn)算不具有交換律x,ya,bc,dax,bx+yc

14、,dacx,adx+bx+y而x,ya,bc,dx,y*ac,ad+bxac,xad+xb+yacx,adx+bx+yx,ya,bc,d運(yùn)算有結(jié)合律任取a,bs,則有：2a,ba,ba,abba,b運(yùn)算無(wú)塞等律（2）令a,b*x,ya,b對(duì)a,bs均成立則有：ax,ay+ba,b對(duì)a,bs均成立axaax10對(duì)a,b成立aybbay0x10x1必定有y0y0運(yùn)算的右單位元為1,0,可當(dāng)證1,0也為運(yùn)算的左單位元，運(yùn)算的單位元為1,0令a,b*x,yx,y,若存在x,y使得對(duì)a,bs上述等式均成立，則存在零元，否則不存在零元。由a,b*x,yx,yax,ay+bx,ya1x0axxa1y+b0a

15、yby由于a1y+b0不可能對(duì)a,bs均成立，故a,b*x,yx,y不可能對(duì)a,bs均成立，故不存在零元；設(shè)元素a,b的逆元為x,y,則令a,b*x,ye1,01xax1a（當(dāng)a0）ayb0bya當(dāng)a0時(shí)，a,b的逆元不存在；1b當(dāng)a0時(shí)，a,b的逆元是，aa11設(shè)S12,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=max(x,

16、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è)V1,2,3,1,其中xy表示取x和y之中較大的數(shù)。V5,6,6,12其中xy表示取x和y之中較小的數(shù)。求出V和V的所有的子代數(shù)。12指出哪些是平凡的子代數(shù)，哪些是真子代數(shù)。解：(1)V中運(yùn)算的單位元是1,1V的

17、所有的子代數(shù)是：1,2,3,1,1,1,1,2,1,1,3,1;1V的平凡的子代數(shù)是:1,2,3,1,1,1；1V的真子代數(shù)是：1,1,1,2,1,1,3,1;1（2）V中運(yùn)算的單位元是6,2V的所有的子代數(shù)是：5,6,6,6,6;2V的平凡的子代數(shù)是：5,6,6,6,6;2V的真子代數(shù)是：6,6。2習(xí)題十一及答案：(P218-2191、圖11.11給出了 6個(gè)偏序集的哈斯圖。判斷其中哪些是格。如果不是格，說明理由角星:（a）、（c）、（f）是格；因?yàn)槿我鈨蓚€(gè)元素構(gòu)成的集合都有最小上界和最大下界；（b）不是格，因?yàn)閐,e的最大下界不存在；（d）不是格，因?yàn)閎,c的最小上界不存在；（e）不是格，

18、因?yàn)閍,b的最大下界不存在。2、下列各集合低于整除關(guān)系都構(gòu)成偏序集，判斷哪些偏序集是格。(1)L=1,2,3,4,5;(2)L=1,2,3,6,12;解：畫出哈斯圖即可判斷出：(1)不是格，(2)是格。4、設(shè)L是格,式：a (ba (b 為：， a,b,c 格， 明：c)參見La且,bc) (a(a b)求以下公式的對(duì)偶b) (a c) (2)(a c)解：對(duì)偶式P208頁(yè)定義b ca證明。c, bb,11.2。c6、設(shè)L為b, a b b,證9、針對(duì)圖11.11中的每個(gè)格，如果格中的元素存在補(bǔ)元，則求出這些補(bǔ)元。解：(a)圖：a,d互為補(bǔ)元，其中a為全下界，d為全上界，b和c都沒有補(bǔ)元；(c)圖：a,f互為補(bǔ)元，其中a為全下界，f為全上界，c和d的補(bǔ)元都是b和e,b和e的補(bǔ)元都是c和d；(f)圖：a,f互為補(bǔ)元，其中a為全下界，f為全上界，b和e互為補(bǔ)元，c和d都沒有補(bǔ)元。10、說明圖11.11中每個(gè)格是否為分配格、有補(bǔ)格和布爾格，并說明理由。解：(a)圖：是一條鏈，所以是分配格