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

離散數(shù)學(xué)習(xí)題答案習(xí)題一及答案：（P14-15）14、將下列命題符號化：（5）李辛與李末是兄弟解：設(shè)p：李辛與李末是兄弟，則命題符號化的結(jié)果是p（6）王強與劉威都學(xué)過法語pq解：設(shè)p：王強學(xué)過法語；q：劉威學(xué)過法語；則命題符號化的結(jié)果是（9）只有天下大雨，他才乘班車上班qp解：設(shè)p：天下大雨；q：他乘班車上班；則命題符號化的結(jié)果是（11）下雪路滑，他遲到了解：設(shè)p：下雪；q：路滑；r：他遲到了；則命題符號化的結(jié)果是(pq)r15、設(shè)p：2+3=5.q：大熊貓產(chǎn)在中國.r：太陽從西方升起.求下列復(fù)合命題的真值：(pqr)((pq)r)（4）解：p=1，q=1，r=0，(pqr)(110)1，((pq)r)((11)0)(00)1(pqr)((pq)r)11119、用真值表判斷下列公式的類型：(pp)q（2）解：列出公式的真值表，如下所示：ppqq(pp)(pp)q001111011010100101110001由真值表可以看出公式有3個成真賦值，故公式是非重言式的可滿足式。20、求下列公式的成真賦值：（4）(pq)q解：因為該公式是一個蘊含式，所以首先分析它的成假賦值，成假賦值的條件是：p0(pq)1q0q0成真賦值有：01，10，11。所以公式的習(xí)題二及答案：（P38）5、求下列公式的主析取范式，并求成真賦值：（2）(pq)(qr)解：原式(pq)qr(pp)qrqr，此即公式的主析取范式，mm(pqr)(pqr)37所以成真賦值為011，111。*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)的極小項為，，，所以主合取范式中含有三個極大項，，MMmmm02024，故原式的主合取范式。MMMM40249、用真值表法求下面公式的主析取范式：（1）(pq)(pr)解：公式的真值表如下：pppqprqr(pq)(pr)00010000011011010110101111111000101101010111001011110101由真值表可以看出成真賦值的情況有7種，此7種成真賦值所對應(yīng)的極小項的析取即為主析取范式，故主析取范式mmmmmmm1234567習(xí)題三及答x(F(x)y(G(y)H(x,y)))（1）I解：取解釋如下：個體域為全總個體域，F(xiàn)(x)H(x,y)G(y)：x是兔子，：y是烏龜，：x比y跑得快，則該公式在解釋I下真值是1；''IIH(x,y)取解釋如下：：x比y跑得慢，其它同上，則該公式在解釋下真值是0；故公式（1）既不是永真式也不是矛盾式。此題答案不唯一，只要證明公式既不是永真式也不是矛盾式的每個解釋合理即可。習(xí)題五及答案：（P79-81）5、給定解釋I如下：(a)個體域D={3,4}f(x):f(3)4,f(4)3(b)F(x,y):F(3,3)F(4,4)0,F(3,4)F(4,3)1(c)試求下列公式在I下的真值：xyF(x,y)(1)解：方法一：先消去存在量詞xyF(x,y)x(F(x,3)F(x,4))(F(3,3)F(3,4)F)((4F,3)(01)(10)115、在自然推理系統(tǒng)中，構(gòu)造下面推理的證明：N（3）前提：，x(F(x)G(x))xG(x)結(jié)論：xF(x)證明：①前提引入xG(x)②①置換xG(x)③②UI規(guī)則G(c)④前提引入x(F(x)G(x))⑤④UI規(guī)則F(c)G(c)⑥③⑤析取三段論F(c)⑦⑥EG規(guī)則xF(x)*22、在自然推理系統(tǒng)中，構(gòu)造下面推理的證明：N（2）凡大學(xué)生都是勤奮的。王曉山不勤奮。所以王曉山不是大學(xué)生。解：設(shè)F(x)：x為大學(xué)生，G(x)：x是勤奮的，c：王曉山則前提：，x(F(x)G(x))G(c)結(jié)論：F(c)證明：①前提引入x(F(x)G(x))②①UI規(guī)則F(c)G(c)③前提引入G(c)④②③拒取式F(c)25、在自然推理系統(tǒng)中，構(gòu)造下面推理的證明：N每個科學(xué)工作者都是刻苦鉆研的，每個刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學(xué)工作者，并且是聰明的。所以，王大海在他的事業(yè)中將獲得成功。（個體域為人類集合）解：設(shè)F(x)：x是科學(xué)工作者，G(x)：x是刻苦鉆研的，H(x)：x是聰明的，I(x)：x在他的事業(yè)中獲得成功，c：王大海則前提：，，x(F(x)G(x))x(G(x)H(x)I(x))F(c)H(c)結(jié)論：I(c)證明：①前提引入F(c)H(c)②①化簡F(c)③①化簡H(c)④前提引入x(F(x)G(x))⑤④UI規(guī)則F(c)G(c)⑥②⑤假言推理G(c)⑦③⑥合取引入G(c)H(c)⑧前提引入x(G(x)H(x)I(x))⑨⑧UI規(guī)則G(c)H(c)I(c)⑩⑦⑨假言推理I(c)習(xí)題六及答案（P99-100）28、化簡下述集合公式：((AB)C)((AB)C)((AB)C)((AB)C)（3）((AB)C)((AB)C)((AB)C)((AB)C)解：(AB)(AB)A30、設(shè)A,B,C代表任意集合，試判斷下面命題的真假。如果為真，給出證明；如果為假，給出反例。(AB)AB（6）(AB)ABABABBA，如果，則解：該命題為假，，否則BABBAB，故為假。(AB)A{3}BA{1,2},B{1,3},舉反例如下：則。ABACBC（8）ABAC一定成立，解：該命題為假，舉反例如下：如果B，C都是A的子集，則B{1}C{2}1,2}A{ABACABC但不一定成立，例如：，則，,，BC但。33、證明集合恒等式：A(BA)BA（1）A(BA)證明：(AB)(AA)(AB)BAAB習(xí)題七及答案：（P132-135）A1,2,3,4,5,626設(shè)，R為A上的關(guān)系，R的關(guān)系圖如圖7.13所示：23（1）求的集合表達式；R,R（2）求r(R),s(R),t(R)的集合表達式。解：（1）由R的關(guān)系圖可得R1,5,2,5,3,1,3,3,4,5232所以，，RRR3,1,3,3,3,5RRR3,1,3,3,3,5n可得；R3,1,3,3,3,5,當(dāng)n>=2（2），r(R)=RI1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,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,541、設(shè)A={1，2，3，4}，R為AAa,b,c,dAA上的二元關(guān)系，，a,bRc,dabcd（1）證明R為等價關(guān)系；（2）求R導(dǎo)出的劃分。（1）只需證明R具有自反性、對稱性和傳遞性即可，證明過程如下：a,bAAa,bRa,babab（a）任取，有，，所以R具有自反性；a,b,c,dAAa,bRc,d（b）任取，若，c,dRa,babcdcdab則有，，，所以R具有對稱性；a,b,c,d,e,fAAa,bRc,dc,dRe,f（c）任取，若且，cdefabefa,bRe,fabcd則有且，，，所以R具有傳遞性，AA綜合（a）（b）（c）可知：R為集合上的等價關(guān)系；AA（2）先求出集合的結(jié)果：AA{1,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,4}AA再分別求集合各元素的等價類，結(jié)果如下：[1,1]{1,1},R[1,2][2,1]{1,2,2,1},RR[1,3][2,2][3,1]{1,3,2,2,3,1},RRR[1,4][2,3][3,2][4,1]{1,4,2,3,3,2,4,1},RRRR[2,4][3,3][4,2]{2,4,3,3,4,2},RRR[3,4][4,3]{3,4,4,3},RR[4,4]{4,4}。RA/RA/R等價關(guān)系R導(dǎo)出的劃分就是集合A關(guān)于R的商集，而集合A關(guān)于R的商集是由R的所有等價類作為元素構(gòu)成的集合，所以等價關(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,4}}A,R46、分別畫出下列各偏序集的哈斯圖，并找出A的極大元、極小元、最大元和最小元。（1）Ra,d,a,c,a,b,a,e,b,e,c,e,d,eIA解：哈斯圖如下：ebcdfaA的極大元為e、f，極小元為a、f；A的最大元和最小元都不存在。A1,2,3,4*22、給定，A上的關(guān)系，試R1,3,1,4,2,3,2,4,3,4（1）畫出R的關(guān)系圖；（2）說明R的性質(zhì)。解：（1）12●●●●34（2）R的關(guān)系圖中每個頂點都沒有自環(huán)，所以R是反自反的，不是自反的；R的關(guān)系圖中任意兩個頂點如果有邊的都是單向邊，故R是反對稱的，不是對稱的；R的關(guān)系圖中沒有發(fā)生頂點x到頂點y有邊、頂點y到頂點z有邊，但頂點x到頂點z沒有邊的情況，故R是傳遞的。A,R和B,S*48、設(shè)為偏序集，在集合上定義關(guān)系T如下：ABa,b,a,bAB,1122a,bTa,baRabSb11221212證明T為上的偏序關(guān)系。AB證明：（1）自反性：任取a,bAB，則：11R為偏序關(guān)系，具有自反性，aRa11S為偏序關(guān)系，具有自反性，bSb11aRabSb1111又a,bTa,baRabSb，11221212a,bTa,b，故T具有自反性1111（2）反對稱性：任取a,b,a,bAB，若a,bTa,b且a,bTa,b，則有：112211222211aRabSb（1）1212aRabSb（2）2121aRaaRa，又R為偏序關(guān)系，具有反對稱性，所以aa122112bSbbSb，又S為偏序關(guān)系，具有反對稱性，所以bb122112a,ba,b，故T具有反對稱性1122（3）傳遞性：任取a,b,a,b，a,bAB，若a,bTa,b且a,bTa,b，則有：11223311222233a,bTa,baRabSb11221212a,bTa,baRabSb22332323aRaaRa,又R為偏序關(guān)系，具有傳遞性，所以aRa122313bSbbSb,又S為偏序關(guān)系，具有傳遞性，所以bSb122313aRabSba,bTa,b，故T具有傳遞性。13131133綜合（1）（2）（3）知T具有自反性、反對稱性和傳遞性，故T為上的偏序關(guān)系。AB習(xí)題九及答案：（P179-180）8、S=QQ,Q為有理數(shù)集，為S上的二元運算，a,b,x,yS有a,bx,yax,ay+b（1）運算在S上是否可交換、可結(jié)合？是否為冪等的？（2）。運算是否有單位元、零元？如果有，請指出，并求出S中所有可逆元素的逆元解：（1）x,ya,bxa,xb+yax,bx+ya,bx,y運算不具有交換律x,ya,bc,dax,bx+yc,dacx,adx+bx+y而x,ya,bc,dx,y*ac,ad+bxac,xad+xb+yacx,adx+bx+yx,ya,bc,d運算有結(jié)合律任取a,bs，則有：2a,ba,ba,abba,b運算無冪等律（2）令a,b*x,ya,b對a,bs均成立則有：ax,ay+ba,b對a,bs均成立axaax10對a,b成立aybbay0x10x1必定有y0y0運算的右單位元為1，0，可驗證1，0也為運算的左單位元，運算的單位元為1，0令a,b*x,yx,y，若存在x,y使得對a,bs上述等式均成立，則存在零元，否則不存在零元。由a,b*x,yx,yax,ay+bx,ya1x0axxa1y+b0ayby由于a1y+b0不可能對a,bs均成立，故a,b*x,yx,y不可能對a,bs均成立，故不存在零元；設(shè)元素a,b的逆元為x,y，則令a,b*x,ye1，01xax1a（當(dāng)a0）ayb0bya當(dāng)a0時，a,b的逆元不存在；1b當(dāng)a0時，a,b的逆元是,aa11、設(shè)S12，，...,10，問下面的運算能否與S構(gòu)成代數(shù)系統(tǒng)S，?如果能構(gòu)成代數(shù)系統(tǒng)則說明運算是否滿足交換律、結(jié)合律，并求運算的單位元和零元。（3）；xy=大于等于x和y的最小整數(shù)解：（3）由*運算的定義可知：，xy=max(x,y)x,yS,有xyS，故運算在S上滿足封閉性，所以運算與非空集合S能構(gòu)成代數(shù)系統(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),所以運算滿足結(jié)合律；任取xS，有x1=max(x,1)=x=max(1,x)=1x,所以運算的單位元是1；任取xS，有x10=max(x,10)=10=max(10,x)=10x,所以運算的零元是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中運算的單位元是1，1V的所有的子代數(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中運算的單位元是6，2V的所有的子代數(shù)是：5,6,,6，6,,6；2V的平凡的子代數(shù)是：5,6,,6，6,,6；2V的真子代數(shù)是：6,,6。2習(xí)題十一及答案：（P218-219）1、圖11.11給出了6個偏序集的哈斯圖。判斷其中哪些是格。如果不是格，說明理由解：（a）、（c）、（f）是格；因為任意兩個元素構(gòu)成的集合都有最小上界和最大下界；（b）不是格，因為{d,e}的最大下界不存在；（d）不是格，因為{b,c}的最小上界不存在；（e）不是格，因為{a,b}的最