離散數(shù)學(xué)答案(尹寶林版)第一章習(xí)題解答

(完滿版)失散數(shù)學(xué)答案(尹寶林版)第一章習(xí)題解答(完滿版)失散數(shù)學(xué)答案(尹寶林版)第一章習(xí)題解答/(完滿版)失散數(shù)學(xué)答案(尹寶林版)第一章習(xí)題解答第一章命題邏輯習(xí)題與解答⒈判斷以下語句可否為命題，并談?wù)撁}的真值。2x3=0。⑵前進?、侨羰?+7>20，則三角形有四條邊。⑷請勿吸煙！⑸你喜歡魯迅的作品嗎？⑹若是太陽從西方升起，你就可以長生不老。⑺若是太陽從東方升起，你就可以長生不老。解⑶,⑹,⑺表達命題，其中⑶,⑹表達真命題，⑺表達假命題。⒉將以下命題符號化：⑴邏輯不是無聊無味的。⑵我看見的既不是小張也不是老李。⑶他生于1963年或1964年。⑷只有不怕困難，才能戰(zhàn)勝困難。⑸只要上街，我就去書店。⑹若是夜晚做完了作業(yè)并且沒有其他事情，小楊就看電視或聽音樂。⑺若是林芳在家里，那么他不是在做作業(yè)就是在看電視。⑻三角形三條邊相等是三個角相等的充分條件。⑼我進城的必要條件是我有時間。⑽他唱歌的充分必要條件是心情快樂。⑾小王總是在圖書館看書，除非他病了也許圖書館不開門。解⑴p：邏輯是無聊無味的?！斑壿嫴皇菬o聊無味的”符號化為p。p：我看見的是小張。q：我看見的是老李?！拔铱匆姷募炔皇切堃膊皇抢侠睢狈柣癁閜q。p：他生于1963年。q：他生于1964年?！八?963年或1964年”符號化為pq。p：害怕困難。q：戰(zhàn)勝困難。“只有不怕困難，才能戰(zhàn)勝困難”符號化為qp。p：我上街。q：我去書店。“只要上街，我就去書店”符號化為pq。p：小楊夜晚做完了作業(yè)。q：小楊夜晚沒有其他事情。r：小楊夜晚看電視?！叭羰且雇碜鐾炅俗鱬qrs。

s：小楊夜晚聽音樂。業(yè)并且沒有其它事情，

小楊就看電視

或聽音樂

”符號化為p：林芳在家里。q：林芳做作業(yè)。r：林芳看電視?！叭羰橇址荚诩依?，那么他不是在做作業(yè)就是在看電視”符號化為pqr。⑻p：三角形三條邊相等。q：三角形三個角相等?！叭切稳龡l邊相等是三個角相等的充分條件”符號化為pq。p：我進城。q：我有時間?！拔疫M城的必要條件是我有時間”符號化為pq。p：他唱歌。q：他心情快樂?！八璧某浞直匾獥l件是心情快樂”符號化為pq。p：小王在圖書館看書。q：小王病了。r：圖書館開門?！靶⊥蹩偸窃趫D書館看書，除非他病了也許圖書館不開門”符號化為(qr)p，也許(qr)p。也可符號化為(qr)p，也許(qr)p。⒊列出除，，，，之外的所有二元聯(lián)系詞的真值表。解共有16個二元聯(lián)系詞，記除，，，，之外的二元聯(lián)系詞為1,2,,11。pqp1qp2qp3qp4qp5qp6q00000001010001101001100011001010pqp7qp8qp9qp10qp11q0011111010011110110111101001⒋求以下公式在真值賦值(p1/1,p/1,p/0,p/0)234下的值：p1(p2p3)⑵(pp2p3)((pp)(pp4))1123⑶(pp2)p3(((pp2)p3)p4)11(4)(pp)(pp)2134⑸(pp3)(p2p4)1⑹p(p2pp)pp41312(7)(p1p3)(p2p4)解記真值賦值(p1/1,p2/1,p3/0,p4/0)為v。⑴v(p(p2p3))1(10)1。1⑵v((ppp3)((pp2)(pp4)))(110)((11)(00))11213⑶v((p1p2)p3(((p1p2)p3)p4))(11)0(((11)0)0)1。(4)v((p2p)(pp))=(11)(00)=01=1。134⑸v((pp3)(p2p4))(10)(10)0。1⑹v(p(pp3p)p2p4)1(101)101。121(7)v((p1p3)(p2p4))=(10)(10)=00=0。用真值表判斷以下公式可否是永真式、永假式、可滿足式。(1)(pr)((qr)(pqr))(2)(pp)p(3)(pq)((pq)p)(4)(p(qr))((pq)(pr))(5)(pq)(pr)(qr)r(6)p(pq)(7)(pq)((pq)p)解(1)將(pr)((qr)(pqr))記為A。pqrprqrpqpqr(qr)(pqr)A000110111001110111010101011011111111100011001101111111110001011111111111(pr)((qr)(pqr))是永真式。(3)將(pq)((pq)p)記為A。pqpqqpq(pq)pA0011100011010010011111110011(pq)((pq)p)是非永真的可滿足式。(6)pqppq(pq)p(pq)001100011100100010110100(pq)是永假式。解(1),(2),(4),(5),(7)是永真式，(6)是永假式，(3)是非永真的可滿足式。指出滿足以下公式的所有真值賦值。(1)(pq)(pr)p(qr(pq))(3)pr(pr)(qr)(4)p(qr)解(1)(p/0,q/0,r/0)，(p/0,q/0,r/1)，(p/0,q/1,r/0)，(p/0,q/1,r/1)，(p/1,q/0,r/1)，(p/1,q/1,r/0)，(p/1,q/1,r/1)。(2)(p/0,q/1,r/0)，(p/1,q/0,r/0)，(p/1,q/0,r/1)，(p/1,q/1,r/0)，(p/1,q/1,r/1)。(p/0,q/0,r/0)，(p/0,q/1,r/0)。(4)任取滿足p(qr)的真值賦值v。若v(p)=0，則v(qr)=1v(q)=v(r)。v(p)=1v(q，v(q)v(r)若，則r)=0。，所以，滿足p(qr)的真值賦值有以下四個：(p/0,q/0,r/0)，(p/0,q/1,r/1)，(p/1,q/0,r/1)，(p/0,q/1,r/0)。7.若公式A既不是永真式，也不是永假式，則A的每個代替實例必然既不是永真式，也不是永假式。對嗎？解不對。若A是非永真的可滿足式，則它的代替實例中既有永真式，也有永假式，也有非永真的可滿足式。設(shè)A中出現(xiàn)的命題變元是p1,,pv1和v2分別是使得A為真的真值賦值和使得A為假n的真值賦值。取公式,,B,C,,CB1n1n以下：Bippv1(pi)1Cippv2(pi)1ppv1(pi)0ppv2(pi)0任取真值賦值v，v(ABp1,,,B,pn)v[p1/v(B1),,pn/v(Bn)](A)v1(A)1，1nv(ACp1,,,,Cpn)v[p1/v(C1),,pn/v(Cn)](A)v2(A)0，1n所以，A的代替實例Ap1,,pn是永真式，A的代替實例Ap1,,pn是永假式。B,,BC,,Cn1n1A自己也是A的代替實例，它是非永真的可滿足式。用真值表證明以低等值式。(1)p(qr)(pq)(pr)pqrqrp(qr)pqpr(pq)(pr)0000000000110000010100000110000010000000101110111101110111100110(2)(3)(4)用等值演算證明以低等值式。(1)p(qr)q(pr)(2)(pq)(pr)pqr(3)(pq)(rq)prq(4)p(qp)p(pq)(5)(pq)(rq)prq(6)(pq)pq解(1)p(qr)p(qr)q(pr)q(pr)(2)(pq)(pr)(pq)(pr)p(qr)pqr(3)(pq)(rq)(pq)(rq)(pr)(qq)(pr)q(pr)qprq(4)p(qp)pqp1ppqp(pq)(5)(pq)(rq)(pq)(rq)(pr)q(pr)qprq(6)(pq)pqpq(pq)(p(q1))1(pq)(11)(pq)0pq用等值演算證明以下公式是永真式。(1)(qp)(pq)p(2)(pq)(rs)(prqs)(3)(pq)(pr)(ps)(pqrs)(4)(pqr)(pr)(qr)解(1)(qp)(pq)p(qp)(pq)ppp1(2)(pq)(rs)(prqs)(pq)(rs)prqs(pq)p(rs)rqsqpsrqs1(3)(pq)(pr)(ps)(pqrs)pqprps(pqrs)pqrspqrs1(4)(pqr)(pr)(qr)((pq)r)prqr((pq)r)pqr(pqpqr)(rpqr)111用等值演算證明以下公式是永假式。(1)(qp)(pq)p(2)(pq)(qr)(pr)解(1)(qp)(pq)p(qp)(pq)ppp0(2)(pq)(qr)(pr)(pq)(qr)(pr)(pq)(qr)pr((pq)p)((qr)r)pqqr012.找出與以下公式等值的盡可能簡單的由{,}生成的公式。13.找出與以下公式等值的盡可能簡單的由{,}生成的公式。(1)pq(rp)(2)(pqr)pqpqp解(1)pq(rp)pq(rp)(pqr)(pqp)pqr(pqr)(2)(pqr)pq(pqr)pq((pqr)pq)(3)pqp(pqp)14.設(shè)A是由{}生成的公式。證明：A是永真式當(dāng)且僅當(dāng)每個命題變元在A中出現(xiàn)偶數(shù)次。證明第一證明：若A是由{}生成的僅出現(xiàn)一個命題變元p的公式，則pAApA對p在A中的出現(xiàn)次數(shù)進行歸納。①若p在A中出現(xiàn)1次，即A為pp。，顯然A②若p在A中出現(xiàn)2次，即A為pp，顯然A1。③設(shè)p在A中的出現(xiàn)nABCpBCk和l，則nkl，次，為，在，中的出現(xiàn)次數(shù)分別為kn且ln。若n為偶數(shù),則k和l的奇偶性相同，B和C等值于同一公式，A1。若n為奇數(shù),則k和l的奇偶性不相同，B和C中一個等值于p，另一個是永真式，所以Ap1p。設(shè)在A中的出現(xiàn)的所有命題變元為p1,,pn，它們的出現(xiàn)次數(shù)分別為k1,,kn。因為AB(AB)(BA)BA，并且(AB)C((AB)C)AB1C1ABC11(A(BC))A(BC)所以滿足交換律和結(jié)合律，存在由{}生成的公式B1,,Bn，使得AB1Bn，并且Bi僅出現(xiàn)命題變元pi，出現(xiàn)次數(shù)為ki，i1,,n。若k1,,kn全為偶數(shù)，則AB1Bn111。若k1,,kn中有kl1,,klm是奇數(shù)，則AB1Bnpl1plm，顯然A不是永真式。15.設(shè)A是由{}A是永假式當(dāng)且僅當(dāng)每個命題變元在A中出現(xiàn)偶數(shù)次。生成的公式。證明：證明第一證明：若A是由{}生成的僅出現(xiàn)一個命題變元p的公式，則pAApA對p在A中的出現(xiàn)次數(shù)進行歸納。①若p在A中出現(xiàn)1次，即A為p，顯然AppAAp。②若在中出現(xiàn)2次，即為pA0，顯然。③設(shè)p在A中出現(xiàn)n次，A為BC，p在B，C中的出現(xiàn)次數(shù)分別為k和l，則n=k+l，k<n且l<n。若n為偶數(shù),則k和l的奇偶性相同，B和C等值于同一公式，0。若n為奇數(shù),則k和l的奇偶性不相同，B和C中一個等值于p，另一個是永假式，所以Ap0p。設(shè)在A中的出現(xiàn)的所有命題變元為p1n，它們的出現(xiàn)次數(shù)分別為1n滿,,pk,,k。因為足交換律和結(jié)合律，所以存在由{}生成的公式B1,,BABBBn，使得1n，i中僅出現(xiàn)命題變元pi，并且出現(xiàn)次數(shù)為ki，i=1,。若1n全為偶數(shù)，則,nk,,kABB000k,,kn中有kl1,klm1n。若1,是奇數(shù)，則AB1Bnpl1plm，顯然A不是永假式。北京、上海、天津、廣州四市乒乓球隊比賽，三個觀眾猜想比賽結(jié)果。甲說：“天津第一，上海第二?！币艺f：“天津第二，廣州第三?！北f：“北京第二，廣州第四?！北荣惤Y(jié)果顯示，每人猜對了一半，并且沒有并列名次。問：實質(zhì)名次怎樣排列？解用字母表示命題以下：p2：北京第二，q2：上海第二，r1：天津第一，r2：天津第二，s3：廣州第三，s4：廣州第四。由已知條件列出以下方程：甲猜對了一半：r12r2324，乙猜對了一半：，丙猜對了一半：；每個城市只能得一個名次：r1r2=0ss=0；34沒有并列名次：p2q=0，pr2=0r2q=022，2。解以上8個方程組成的方程組。r)(rq)=00=0，r=r21=r2(r1q)=(r222212ss=0s=0s=0p將r2=0代入r2s=1得s=1，將s=1代入得代入333344r，將42s=1得p=1p=1代入pq=0得q=0q=0代入q=1得r=1。42，將2222，將2121將p2=r1=s3=1，q2=r2=s4=0代入8個方程考據(jù)它們滿足方程組。所以，天津第一，北京第二，廣州第三，上海第四。某勘探隊取回一塊礦樣，三人判斷以下。甲說：“礦樣不含鐵，也不含銅?！币艺f：“礦樣不含鐵，含錫?！北f：“礦樣不含錫，含鐵?！币呀?jīng)知道，這三人中有一個是專家，一個是老隊員，一個是實習(xí)隊員。化驗結(jié)果表示：這塊礦樣只含一種金屬，專家的兩個判斷皆對，老隊員的判斷一對一錯，實習(xí)隊員的兩個判斷皆錯。問：這三人的身分各是什么？解p:礦樣含鐵，q:礦樣含銅，r:礦樣含錫。甲說的兩句話為：p，q乙說的兩句話為：p，r丙說的兩句話為：r，p若是用一個公式表達出這三人中有一個是專家，一個是老隊員，一個是實習(xí)隊員，公式會特別復(fù)雜。其實我們不用完滿寫出這樣的公式。因為礦樣只含一種金屬，所以pq0，qr0，rp0。甲是實習(xí)隊員，即甲說的兩句話都是錯的，可表示為：pq。乙是實習(xí)隊員，即乙說的兩句話都是錯的，可表示為：pr。丙是實習(xí)隊員，即丙說的兩句話都是錯的，可表示為：rp。甲、乙、丙三人中最少有一個是實習(xí)隊員，可表示為：(pq)(pr)(rp)1因為pq0(pr)(rp)1，即pr1，p和r中恰好有一個為，，所以所以q0。甲是老隊員，即甲說的話一半對一半錯，可表示為：pq。乙是老隊員，即乙說的話一半對一半錯，可表示為：pr。丙是老隊員，即丙說的話一半對一半錯，可表示為：rp。甲、乙、丙三人中有奇數(shù)個老隊員，可表示為：(

p

q)(

p

r)

(

r

p)1由教材上的等值式可獲取(p(p01

q)p)(q

((1

prp)

r)r)

(r(qqp

p)p)又知道

q

0，所以

p

1。因為

r

p0

，所以

r

0。所以，甲說的話一半對一半錯，甲是老隊員。乙說的話全錯，乙是實習(xí)隊員。丙說的話全對，丙是專家。先用等值演算證明以低等值式，再用對偶定理得出新等值式。(1)(pq)(pq)p(2)(pq)(pq)(pq)(pq)(3)q((pq)p)1解(1)(pq)(pq)(pq)(pq)p(qq)p由對偶定理得(pq)(pq)p。(2)(pq)(pq)(pq)(p(qq))(pq)p(pq)(pp)(pq)pq(pq)由對偶定理得(pq)(pq)(pq)(pq)。(3)19.設(shè)A是由{0,1,,,}生成的公式，A*與A互為對偶式。若A是永真式，則A*是永假式。若A是永假式，則A*是永真式。證明(1)設(shè)A是永真式，則A1，由對偶定理得A*0，所以A*是永假式。(2)設(shè)A是永假式，則A0，由對偶定理得A*1，所以A*是永真式。證明以下聯(lián)系詞會集是極小完滿集。(1){0,}(2){,}(3){,,}(4){,,}{0,}證明(1)pp0p0，因為{,}是完滿集，所以是完滿集。任p取由{0}生成的不出現(xiàn)除命題變元之外的命題變元的公式A，令真值賦值v=(p/0)，則v(A)=0，而v(p)=1，所以{0}不能夠定義。所以{0}不是完滿集。任取由{}生成的僅出現(xiàn)命題變元p的公式Av=(p/1)，則v(A)=1，而v(p)=0，所以{}，令真值賦值不能夠定義。所以{}不是完滿集。所以{0,}是極小完滿集。(2)pp1p(pp)，因為{,}是完滿集，所以{,}是完滿集。任取由{}生成的僅出現(xiàn)命題變元p的公式A，令真值賦值v=(p/0)，則v(A)=0，而v(p)=1，所以{}不能夠定義。所以{}不是完滿集。{}不是完滿集。所以{,}是極小完滿集。(3)p}p1p(pp)，因為{,}是完滿集，所以{,,}是完滿集。任取由{,生成的僅出現(xiàn)命題變元p的公式Av=(p/0)v(A)=0，而，令真值賦值，則v(p)=1，所以{,}不能夠定義。所以{,}不是完滿集。任取由{,}生成的僅出}現(xiàn)命題變元p的公式A，令真值賦值v=(p/1)，則v(A)=1v(p)=0{,，而，所以不能夠定義。所以{,}不是完滿集。{,}不是完滿集。所以{,,}是極小完滿集。(4)pp1p(pp)，因為{,}是完滿集，所以{,,}是完滿集。任取由{,}生成的僅出現(xiàn)命題變元p的公式A，令真值賦值v=(p/0)，則v(A)=0，而v(p)=1，所以{,}不能夠定義。所以{,}不是完滿集。任取由{,}生成的僅出}現(xiàn)命題變元p的公式A，令真值賦值v=(p/1)，則v(A)=1v(p)=0{,，而，所以不能夠定義。所以{,}不是完滿集。{,}不是完滿集。所以{,,}是極小完滿集。證明以下聯(lián)系詞會集不是完滿集。(1){,,,}(2){,,}證明(1)任取由{,,,}生成的僅出現(xiàn)命題變元p的公式Av(p/1)，，令真值賦值則v(A)1，而v(p)0，所以{,,,}不能夠定義。所以{,,,}不是完全集。(2)任取由{,,}生成的僅出現(xiàn)命題變元p的公式A，令真值賦值v(p/0)，則v(A)0，而v(p)1，所以{,,}不能夠定義。所以{,,}不是完滿集。22.二元聯(lián)系詞（稱為“與非”）和（稱為“或非”）的真值表以下。pqpqpq0011011010101100證明：{}是完滿集。{}是完滿集。(3)若是二元聯(lián)系詞且{}是完滿集，則是或。證明(1)ppp,pq(pq)(pq)(pq)(pq)，因為{,}是完滿集，所以{}是完滿集。(2)ppp,pq(pq)(pq)(pq)(pq)，因為{,}是完滿集，所以{}是完滿集。(3)若00=0或11=1，則不能夠由{}定義。所以，00=1且11=0。若0110，則的真值表的最后一列有偶數(shù)個1，真值表最后一列有奇數(shù)個1的不能夠由{}定義。所以，01=1001=10=1是。若。若，則01=10=0，則是。23.三元聯(lián)系詞的真值表以下。pqr(p,q,r)00010011010001101000101011011110證明{}是極小完滿集。證明pqpqq，因為{}是完滿集，所以{}是極小完滿集。24.在以下公式中，哪些是析取范式，哪些是合取范式?p，pq，(pq)r，pr，pp，((pq)q)r解p，pq，pr，pp是析取范式，p，pq，pr，(pq)r，pp是合取范式。25.在以下公式中，哪些是關(guān)于p,q,r的主析取范式，哪些是關(guān)于p,q,r的主合取范式？pqr,pqr,(pqr)(pqr),p(qr),(ppq)(pqr)解pqr是關(guān)于p,q,r的主析取范式，pqr是關(guān)于p,q,r的主合取范式?？煞裼羞@樣的公式，它既是主合取范式，又是主析取范式？若是有，舉出一例。解有。p既是關(guān)于p的主析取范式，又是關(guān)于p的主合取范式。求以下公式的主范式，進而判斷其可否永真式、永假式、可滿足式。pqr(2)(pq)r(3)pq(pq)(4)p(pq(qr))(5)(pqr)(pqr)(6)pq(pq)解(1)pqr(pq)rpqrpqr的主合取范式是pqr，包含一個極大項，所以它是非永真的可滿足式。(2)(pq)r(pq)r(pq)r(pr)(qr)(p(qq)r)((pp)qr)(pqr)(pqr)(pqr)(pq)r的主合取范式是(pqr)(pqr)(pqr)，包含了三個極大項，所以它是非永真的可滿足式。(3)pq(pq)(pq)((pq)(pq))(pq)(pq)(pq)pqpqq(pq)的主合取范式為pq，包含了一個極大項，所以它是非永真的可滿足式。(4)p(pq(qr))p(pq(qr))1p(pq(qr))的主合取范式為1，不包含任何極大項，所以它是永真式。(5)(pqr)(pqr)(p(qr))(p(qr))(pp)(pqr)(qrp)(qrqr)(

p

q

r)

(p

q

r)(p

qr)

(p

q

r)

的主析取范式為

(

p

q

r)

(p

q

r)，包含了兩個極小項，所以它是非永真的可滿足式。(6)p

q

(

p

q)(p(pp

(qq)q(

q))(pp

((pp)q)(pq)(pq)(pq)q)的主合取范式為(pq)

q)(p

q)(p

q)

(

p

q)，包含了所有的四個極大項，所以它是永假式。用主范式證明以低等值式。(1)(pq)pq(pp)(rp)(2)(pq)(pr)pqr解(1)(pq)pq(pq)(pq)(pq)(pq)(pq(rr))(pq(rr))(p

q

r)

(p

(

qp

r))p)

(p(r

q

r)p)(

(p

qr)pp)

(r

p)p(p

r)

p

p(q

q)

(r

r)(p

q

r)

(p

qr))

(p

q

r)

(p

qr)(p

q)

pq和(p

p)

(r

p)等值于同一個關(guān)于

p,q,

r

的主析取范式(p(2)(p

qq)

r)(p

(pr)

qr))(pq)(p(p

(pqpqq)(pq(r

r)(r)r))

(pp(p

qp)(q

r)，所以，(rp)。q)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)pqrp(qr)(pq)(pr)(pq(rr))(p(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pq)(pr)和pqr的主合取范式相同，所以，(pq)(pr)pqr。判斷以下關(guān)系可否成立，并說明原由。(1)pq,p|qpq,,q|p(3)p1q1,p2q2,p1p2|q1q2(4)pq,qp|pq(5)pqr,pqr|pqr解(1)若真值賦值v使得v(pq)v(p)1，則v(q)1。所以pq,p|q。(2)真值賦值v(p/0,q/1)使得v(pq)v(pq)v(q)1，但v(p)0，所以q,pq,q|/p。(3)若真值賦值v使得v(pq)v(p2q2)v(pp)1，則v(p)v(p2)1，11121所以v(q)v(q)1，v(qq2)