(完整版)離散數(shù)學(xué)答案(尹寶林版)第一章習(xí)題解答最新（精華版）

1、第一章命題邏輯習(xí)題與解答 判斷下列語(yǔ)句是否為命題，并討論命題的真值。 2x3 = 0。 前進(jìn)！ 如果 8 + 7 20 ，則三角形有四條邊。 請(qǐng)勿吸煙！ 你喜歡魯迅的作品嗎？ 如果太陽(yáng)從西方升起，你就可以長(zhǎng)生不老。 如果太陽(yáng)從東方升起，你就可以長(zhǎng)生不老。解 , , 表達(dá)命題，其中 , 表達(dá)真命題，表達(dá)假命題。 將下列命題符號(hào)化： 邏輯不是枯燥無(wú)味的。 我看見的既不是小張也不是老李。 他生于 1963 年或 1964 年。 只有不怕困難，才能戰(zhàn)勝困難。 只要上街，我就去書店。 如果晚上做完了作業(yè)并且沒有其它事情，小楊就看電視或聽音樂(lè)。 如果林芳在家里，那么他不是在做作業(yè)就是在看電視。 三角形三條

2、邊相等是三個(gè)角相等的充分條件。 我進(jìn)城的必要條件是我有時(shí)間。 他唱歌的充分必要條件是心情愉快。 小王總是在圖書館看書，除非他病了或者圖書館不開門。解 p：邏輯是枯燥無(wú)味的。“邏輯不是枯燥無(wú)味的”符號(hào)化為p。p：我看見的是小張。 q：我看見的是老李?！拔铱匆姷募炔皇切堃膊皇抢侠睢狈?hào)化為pq 。p：他生于 1963 年。 q：他生于 1964 年?！八?1963 年或 1964 年”符號(hào)化為 pq。p：害怕困難。 q：戰(zhàn)勝困難。“只有不怕困難，才能戰(zhàn)勝困難”符號(hào)化為qp。p：我上街。 q：我去書店?！爸灰辖?，我就去書店”符號(hào)化為pq。p：小楊晚上做完了作業(yè)。q：小楊晚上沒有其它事情。r：

3、小楊晚上看電視。 s：小楊晚上聽音樂(lè)?！?如果晚上 做完了作 業(yè)并 且沒有其它事情， 小楊 就看電視或聽音樂(lè) ”符 號(hào)化為pqrs 。p：林芳在家里。 q：林芳做作業(yè)。 r：林芳看電視?！叭绻址荚诩依铮敲此皇窃谧鲎鳂I(yè)就是在看電視”符號(hào)化為p：三角形三條邊相等。q：三角形三個(gè)角相等。pqr ?！叭切稳龡l邊相等是三個(gè)角相等的充分條件”符號(hào)化為p：我進(jìn)城。 q：我有時(shí)間?！拔疫M(jìn)城的必要條件是我有時(shí)間”符號(hào)化為pq。p：他唱歌。 q：他心情愉快。pq 。“他唱歌的充分必要條件是心情愉快”符號(hào)化為 pq 。p：小王在圖書館看書。q：小王病了。 r：圖書館開門?！靶⊥蹩偸窃趫D書館看書，除非他病了或

4、者圖書館不開門”符號(hào)化為(qr)p，或者(qr)p。也可符號(hào)化為(qr)p，或者 (qr)p。10 qp11q 列出除，之外的所有二元聯(lián)結(jié)詞的真值表。解共有16 個(gè)二元聯(lián)結(jié)詞，記除，之外的二元聯(lián)結(jié)詞為1 ,2 ,11 。pqp1qp2 qp3 qp4 qp5qp6 q00000001010001101001100011001010pqp7 qp8qp9qp0011111010011110110111101001 求下列公式在真值賦值( p1 / 1, p2 / 1, p3 / 0, p4 / 0)下的值：p1( p2p3 ) ( p1p2p3 )( p1p2 )( p3p4 )( p1p2 )

5、p3(p1p2 )p3 )p4 )(p2p1)(p3p4( p1p3)(p2p4 )(4)p1( p 2p3p1)p2p4(7)(p1p3)(p2p4)解記真值賦值 ( p1 / 1, p2 / 1, p3 / 0, p4 / 0)為 v。 v( p1( p2p3 )1(10)1 。 v( p1p2p3 )( p1p2 )( p3p4 )(110)(11)(00)1 v( p1p2 )p3(p1p2 )p3 )p4 )(11)0(11)0)0)1 。(4)v (p2p1)(p3p4) = (11)(00) = 01 = 1。 v( p1p3 )(p2p4 )(10)(10)0 。 v( p1(

6、 p2p3p1 )p2p 4)1(101)101 。pqpqqpq(pq)pa0011100(7)v (p1p3)(p2p4) = (10)(10) = 00 = 0。5. 用真值表判斷以下公式是不是永真式、永假式、可滿足式。(1)(pr )(qr )(pqr )(2) ( p(3) (pp)q)(ppq)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)a0001101110011101110101010110111

7、11111100011001101111111110001011111111111(3) 將(pq)(p (pr )q)(qp)r)記為(pqr) 是永真式。a。011010010011111110011(pq)( pq)p)是非永真的可滿足式。(6)pqppq(pq)p(pq)001100011100100010110100p(pq) 是永假式。解(1), (2), (4), (5), (7) 是永真式， (6) 是永假式， (3) 是非永真的可滿足式。6. 指出滿足下列公式的所有真值賦值。(1) ( pq)(pr )(2) p( qr( pq)(3)pr( pr )(qr )(4)p(qr

8、 )解(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) 。(3) (3)( p / 0 , q

9、 / 0 ,r / 0) ， ( p / 0, q /1, r/ 0) 。(4) 任取滿足 p(qr ) 的真值賦值v。若 v (p) = 0，則 v (q r ) = 1， v (q) = v (r )。若 v (p) = 1，則 v (q r ) = 0， v (q) v (r )。所以，滿足 p (q r) 的真值賦值有以下四個(gè)：( 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 的每個(gè)替換實(shí)例一定既不是

10、永真式，也不是永假式。對(duì)嗎？解不對(duì)。若 a 是非永真的可滿足式，則它的替換實(shí)例中既有永真式，也有永假式，也有非永真的可滿足式。設(shè) a 中出現(xiàn)的命題變?cè)莗1, pn，v1 和 v2 分別是使得 a 為真的真值賦值和使得a 為假的真值賦值。取公式b1, bn, c1, cn 如下：pbip)任取真值賦值v，p若 v1 ( pi )1c p若 v1 ( pi )0pp若ipp若v2 ( pi )1v2 ( pi )0v( ap1 ,b1 , pn,b nv p1/ v(b1), pn/ v(bn)( a)v1 ( a)1，v( a)p1 ,c1 , pn,cnv p1/ v(c1), pn/ v(

11、cn)( a)v2 ( a)0 ，所以， a 的替換實(shí)例p1 ,ab1 , pn, bn是永真式， a 的替換實(shí)例p1 ,ac1 , pn,c n是永假式。a 本身也是 a 的替換實(shí)例，它是非永真的可滿足式。8. 用真值表證明以下等值式。(1) p(qr )(pq)( pr )pqrqrp(qr )pqpr(pq)( pr )0000000000110000010100000110000010000000101110111101110111100110(2)(3)(4)9. 用等值演算證明以下等值式。(1) p( qr )q( pr )(2) ( pq)( pr )pqr(3) (pq)(rq

12、)prq(4) p( qp)p( pq)(5) ( pq)( rq)p rq(6) (pq)pq(qr )q(pr )q( pr )pq)(pr )p(qr )pqr解(1)p(qr )p(2)( pq)( pr )(pq)(rq)(pr)(qq) ( pr)qprq(3)(pq)(rq)(pr)q(4)p( qp)pq(5)( pq)(rq)p1ppqp( pq)(pq)(rq)(pr )q( pr )qprq(6)(pq)pqpq(pq)(p(q1)1(pq)(11)(pq)0pq10. 用等值演算證明以下公式是永真式。(1) (qp)(pq)p(2) (pq)(rs)(prqs)(3)

13、( pq)( pr )( ps)( pq rs)(4) ( pqr )( pr )(qr )解(1)(qp)(pq)p(qp) ( pq) pp p1(2)( pq)(rs)( prq s)(pq)(rs)prqs(pq)p(rs)rqsqpsrqs1pq)( pr )( ps)( pqrs)(3)(pqprps( pqrs)pqrspqrs1(4)( pqr )( pr )(qr )( pq)r )prqr( pq)r )pqr( pqpqr )(rpqr )11111. 用等值演算證明以下公式是永假式。(1) (qp)(pq)p(2) ( pq)( qr )( pr )解(1)( qp)(

14、pq)p(qp)( pq)ppp0(2)( pq)(qr )( pr )(pq)(qr )(p(ppqq)q(qrr )0pr(pq)p)(qr )r )r )12. 找出與下列公式等值的盡可能簡(jiǎn)單的由,生成的公式。13. 找出與下列公式等值的盡可能簡(jiǎn)單的由,生成的公式。(1) pq(rp)(2) ( pqr )pq(3) pqp解 (1)pq(rp)pq(rp)(ppqqr )r(p( pqqp)r )(2) ( pqr )pq(pqr )pq(pqr )pq)(3) pqp(pqp)14. 設(shè) a 是由 生成的公式。證明： a 是永真式當(dāng)且僅當(dāng)每個(gè)命題變?cè)赼 中出現(xiàn)偶數(shù)次。證明首先證明：

15、若 a 是由 生成的僅出現(xiàn)一個(gè)命題變?cè)猵 的公式，則1ap對(duì) p 在 a 中的出現(xiàn)次數(shù)進(jìn)行歸納。若p在a中出現(xiàn)偶數(shù)次若p在a中出現(xiàn)奇數(shù)次若 p 在 a 中出現(xiàn) 1 次，即 a 為 p，顯然 ap 。若 p 在 a 中出現(xiàn) 2 次，即 a 為 pp ，顯然 a1。設(shè) p 在 a中的出現(xiàn) n 次，a 為 bc ，p 在 b，c 中的出現(xiàn)次數(shù)分別為k 和 l ，則 nkl ，kn且 ln 。若 n 為偶數(shù) , 則 k 和 l 的奇偶性相同， b 和 c 等值于同一公式，a1。若 n 為奇數(shù) , 則 k 和 l 的奇偶性不同， b 和 c 中一個(gè)等值于 p，另一個(gè)是永真式，因此ap1p 。設(shè)在 a 中

16、的出現(xiàn)的所有命題變?cè)獮閜1, pn ，它們的出現(xiàn)次數(shù)分別為k1 ,kn 。因?yàn)閍b( ab)( ba)b( ab)c(aa ，并且b)c)ab1c1abc11( a(bc )a(bc)所 以滿 足 交 換 律 和 結(jié) 合 律 ， 存 在 由 生 成 的 公 式b1, bn， 使 得ab1bn ，并且bi 僅出現(xiàn)命題變?cè)猵i ，出現(xiàn)次數(shù)為ki ， i1,n 。若k1 , kn全 為 偶 數(shù) ， 則 ab1bn111 。 若k1, kn 中 有kl1 , klm 是奇數(shù)，則 ab1bnpl1pl m ，顯然 a 不是永真式。15. 設(shè) a 是由 生成的公式。 證明：a 是永假式當(dāng)且僅當(dāng)每個(gè)命題變?cè)?/p>

17、在a 中出現(xiàn)偶數(shù)次。證明首先證明：若a 是由 生成的僅出現(xiàn)一個(gè)命題變?cè)猵 的公式，則0若 p 在ap若 p 在a中出現(xiàn)偶數(shù)次a中出現(xiàn)奇數(shù)次對(duì) p 在 a 中的出現(xiàn)次數(shù)進(jìn)行歸納。若 p 在 a 中出現(xiàn) 1 次，即 a 為 p，顯然 ap。若 p 在 a 中出現(xiàn) 2 次，即 a 為 pp，顯然 a0。設(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 等值于同一公式， a 0。若 n 為奇數(shù) , 則 k 和 l 的奇偶性不同， b 和 c 中一個(gè)等值

18、于 p，另一個(gè)是永假式， 因此 a p 0 p。設(shè)在 a 中的出現(xiàn)的所有命題變?cè)獮?p1, , pn，它們的出現(xiàn)次數(shù)分別為 k1, kn。因?yàn)?滿足交換律和結(jié)合律，所以存在由 生成的公式 b1, bn，使得 a b1 bn， bi中僅出現(xiàn)命題變?cè)?pi ，并且出現(xiàn)次數(shù)為 ki ， i = 1, , n。若 k1, kn 全為偶數(shù)，則ab1bn000。若 k1, kn 中有kl1 , kl m 是奇數(shù)，則ab1bnpl1plm ，顯然 a 不是永假式。16. 北京、上海、天津、廣州四市乒乓球隊(duì)比賽，三個(gè)觀眾猜測(cè)比賽結(jié)果。甲說(shuō)：“天津第一，上海第二。 ”乙說(shuō)：“天津第二，廣州第三。 ” 丙說(shuō)：“北

19、京第二，廣州第四。 ”比賽結(jié)果顯示，每人猜對(duì)了一半，并且沒有并列名次。問(wèn)：實(shí)際名次怎樣排列？解用字母表示命題如下：p2：北京第二， q2：上海第二， r 1：天津第一，r 2：天津第二， s3：廣州第三， s4：廣州第四。由已知條件列出以下方程：甲猜對(duì)了一半： r 1q2 = 1，乙猜對(duì)了一半：r 2s3 = 1，丙猜對(duì)了一半： p2s4 = 1； 每個(gè)城市只能得一個(gè)名次：r 1r 2 = 0， s3s4 = 0；沒有并列名次： p2q2 = 0， p2r 2 = 0， r2q2 = 0。解以上 8個(gè)方程組成的方程組。r 2 = r21 = r2(r1q2) = (r 2r1 )( r2q2)

20、 = 00 = 0，將 r2 = 0 代入 r2s3 = 1 得 s3 = 1，將 s3 = 1 代入 s3s4 = 0 得 s4 = 0，將 s4 = 0 代入 p2s4 = 1 得 p2 = 1，將 p2 = 1 代入 p2q2 = 0 得 q2 = 0，將 q2 = 0 代入 r1q2 = 1 得 r 1 = 1。將 p2 = r 1 = s3 = 1， q2 = r2 = s4 = 0 代入 8 個(gè)方程驗(yàn)證它們滿足方程組。因此，天津第一，北京第二，廣州第三，上海第四。17. 某勘探隊(duì)取回一塊礦樣，三人判斷如下。甲說(shuō)：“礦樣不含鐵，也不含銅。 ”乙說(shuō)：“礦樣不含鐵，含錫。 ”丙說(shuō)：“礦樣

21、不含錫，含鐵。 ”已經(jīng)知道，這三人中有一個(gè)是專家，一個(gè)是老隊(duì)員，一個(gè)是實(shí)習(xí)隊(duì)員?；?yàn)結(jié)果表明：這塊礦樣只含一種金屬，專家的兩個(gè)判斷皆對(duì)，老隊(duì)員的判斷一對(duì)一錯(cuò)，實(shí)習(xí)隊(duì)員的兩個(gè)判斷皆錯(cuò)。問(wèn)：這三人的身分各是什么？解p : 礦樣含鐵，q : 礦樣含銅，r : 礦樣含錫。甲說(shuō)的兩句話為：p ， q 乙說(shuō)的兩句話為：p ， r 丙說(shuō)的兩句話為：r ， p如果用一個(gè)公式表達(dá)出這三人中有一個(gè)是專家，一個(gè)是老隊(duì)員，一個(gè)是實(shí)習(xí)隊(duì)員，公式會(huì)非常復(fù)雜。其實(shí)我們不必完全寫出這樣的公式。因?yàn)榈V樣只含一種金屬，所以 pq0 ，qr0 ，rp0 。甲是實(shí)習(xí)隊(duì)員，即甲說(shuō)的兩句話都是錯(cuò)的，可表示為：pq 。乙是實(shí)習(xí)隊(duì)員，即乙說(shuō)

22、的兩句話都是錯(cuò)的，可表示為：p r 。丙是實(shí)習(xí)隊(duì)員，即丙說(shuō)的兩句話都是錯(cuò)的，可表示為： rp 。甲、乙、丙三人中至少有一個(gè)是實(shí)習(xí)隊(duì)員，可表示為：( pq)( pr )(rp)1因?yàn)?pq 0 ，所以 ( pr )(rp) 1 ，即 pr 1 ， p 和 r 中恰好有一個(gè)為 1，因此 q0 。甲是老隊(duì)員，即甲說(shuō)的話一半對(duì)一半錯(cuò)，可表示為：pq 。乙是老隊(duì)員，即乙說(shuō)的話一半對(duì)一半錯(cuò)，可表示為：pr 。丙是老隊(duì)員，即丙說(shuō)的話一半對(duì)一半錯(cuò)，可表示為：rp 。甲、乙、丙三人中有奇數(shù)個(gè)老隊(duì)員，可表示為：(pq)(pr )(rp)1由教材上的等值式可得到(pq)(pr )(rp)(pp)(rr )(qp)0

23、1(q1p)qp又知道 q0 ，所以 p1 。因?yàn)?rp 0 ，所以 r0 。因此，甲說(shuō)的話一半對(duì)一半錯(cuò)，甲是老隊(duì)員。乙說(shuō)的話全錯(cuò)，乙是實(shí)習(xí)隊(duì)員。丙說(shuō)的話全對(duì)，丙是專家。18. 先用等值演算證明下列等值式，再用對(duì)偶定理得出新等值式。(1) (pq)(pq)p(2) ( pq) ( pq)(pq)(pq)(3)q(pq)p)1解(1)(pq)(pq)( pq)( pq)p( qq) p由對(duì)偶定理得(pq)(pq)p 。(2)( pq)( pq)(pq)( p(qq)(pq)p(pq)( pp)( pq)pq(pq)(3)由對(duì)偶定理得( pq)( pq)(pq)(pq) 。19. 設(shè) a 是由 0

24、, 1, 生成的公式， a*與 a 互為對(duì)偶式。(1) 若 a 是永真式，則 a*是永假式。(2) 若 a 是永假式，則 a*是永真式。證明(1) 設(shè) a 是永真式，則 a1，由對(duì)偶定理得 a*0，因此 a* 是永假式。(2) 設(shè) a 是永假式，則 a0，由對(duì)偶定理得a*1，因此 a*是永真式。20. 證明以下聯(lián)結(jié)詞集合是極小完全集。(1) 0,(2) ,(3) ,(4) ,證明(1)pp0p0，因?yàn)?, 是完全集，所以 0, 是完全集。任取由 0 生成的不出現(xiàn)除命題變?cè)猵 之外的命題變?cè)墓絘，令真值賦值v = (p/0)，則v(a) = 0，而 v(p) = 1，因此 0 不能定義。所以

25、 0 不是完全集。任取由 生成的僅出現(xiàn)命題變?cè)猵 的公式 a，令真值賦值v = (p/1)，則 v(a) = 1 ，而 v(p) = 0 ，因此 不能定義。所以 不是完全集。所以0, 是極小完全集。(2) pp1p(pp)，因?yàn)?, 是完全集，所以 , 是完全集。任取由 生成的僅出現(xiàn)命題變?cè)猵 的公式 a，令真值賦值v = (p/0)，則 v(a) = 0，而v(p) = 1，因此 不能定義。所以 不是完全集。 不是完全集。所以 ,是極小完全集。(3) pp1p(pp)，因?yàn)?, 是完全集，所以 , 是完全集。任取由, 生成的僅出現(xiàn)命題變?cè)猵 的公式 a，令真值賦值 v = (p/0)，則 v

26、(a) = 0，而v(p) = 1，因此 , 不能定義。所以 , 不是完全集。任取由 , 生成的僅出現(xiàn)命題變?cè)?p 的公式 a，令真值賦值v = (p/1)，則 v(a) = 1，而 v(p) = 0，因此 , 不能定義。所以 , 不是完全集。 , 不是完全集。所以, 是極小完全集。(4) pp1p(pp)，因?yàn)?, 是完全集，所以 , 是完全集。任取由, 生成的僅出現(xiàn)命題變?cè)猵 的公式 a，令真值賦值 v = (p/0)，則 v(a) = 0，而v(p) = 1，因此 , 不能定義。所以 , 不是完全集。任取由 , 生成的僅出現(xiàn)命題變?cè)?p 的公式 a，令真值賦值v = (p/1)，則 v(

27、a) = 1，而 v(p) = 0，因此 , 不能定義。所以 , 不是完全集。 , 不是完全集。所以, 是極小完全集。21. 證明以下聯(lián)結(jié)詞集合不是完全集。(1),(2),證明 (1)任取由 , 生成的僅出現(xiàn)命題變?cè)猵 的公式 a，令真值賦值 v( p/ 1) ，則 v( a)1 ，而v(p)0 ，因此 , 不能定義。所以 , 不是完全集。(2)任取由 ,生成的僅出現(xiàn)命題變?cè)猵 的公式 a，令真值賦值 v( p / 0) ，則v( a)0 ，而v(p)1 ，因此 ,不能定義。所以 ,不是完全集。22. 二元聯(lián)結(jié)詞（稱為“與非” ）和（稱為“或非” ）的真值表如下。p0011q0101pqpq1

28、1101000證明：(1) 是完全集。(2) 是完全集。(3) 若是二元聯(lián)結(jié)詞且 是完全集，則是或。證明(1)ppp,pq(pq)(pq)(pq)(pq)，因?yàn)?, 是完全集，所以 是完全集。(2)ppp ,pq(pq)(pq)(pq)(pq) ， 因?yàn)?, 是完全集，所以 是完全集。(3)若 00 = 0 或 11 = 1，則不能由 定義。因此， 00 = 1 且 11 = 0。若 0110，則的真值表的最后一列有偶數(shù)個(gè)1，真值表最后一列有奇數(shù)個(gè)1 的不能由 定義。所以， 01 = 10。若 01 = 10 = 1，則是。若01 = 10 = 0，則是。23. 三元聯(lián)結(jié)詞的真值表如下。pqr

29、( p,q, r )00010011010001101000101011011110證明 是極小完全集。證明pqpqq ，因?yàn)?是完全集，所以 是極小完全集。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 的主析取范式， p

30、qr 是關(guān)于 p, q, r 的主合取范式。26. 是否有這樣的公式，它既是主合取范式，又是主析取范式？如果有，舉出一例。解有。 p 既是關(guān)于 p 的主析取范式，又是關(guān)于p 的主合取范式。27. 求下列公式的主范式，進(jìn)而判斷其是否永真式、永假式、可滿足式。(1) pqr(2) ( pq)r(3) pq( pq)(4) p( pq (qr )(5) ( pqr )(pqr )(6) pq(pq)解(1)pqr(pq)rpqrpq足式。r 的主合取范式是 pqr ，包含一個(gè)極大項(xiàng)，因此它是非永真的可滿(2) ( pq)r(pq)r(pq)r( pr )(qr )( p(qq)r )( pp)qr

31、)( pqr )( pqr )(pqr )( pq)r 的主合取范式是 ( pqr )( pqr )(pqr ) ，包含了三個(gè)極大項(xiàng)，因此它是非永真的可滿足式。(3) pq( pq)(pq)(pq)( pq )(pq)( pq)( pq)pqpqpq( pq) 的主合取范式為pq，包含了一個(gè)極大項(xiàng)，因此它是非永真的可滿足式。(4) p( pq(qr )p(pq(qr )1p( pq(qr ) 的主合取范式為1，不包含任何極大項(xiàng)， 因此它是永真式。(5) ( pqr )(pqr )(p(qr )(p(qr )(pp)(pqr )( qrp) (qrqr )(pqr )( pqr )( pqr )

32、(pqr ) 的主析取范式為 (pqr )( pqr ) ，包含了兩個(gè)極小項(xiàng)，因此它是非永真的可滿足式。(6) pq(pq)( p(qq)( pp) q)(pq)( pq)( pq) (pq) (pq)pq(pq) 的主合取范式為( pq)( pq)(pq)(pq) ，包含了所有的四個(gè)極大項(xiàng)，因此它是永假式。28. 用主范式證明下列等值式。(1) ( pq)pq(pp) (rp)(2) ( pq) ( pr )p qr解 (1)( pq)pq(pq)( pq)( pq)( pq)( pq(rr )( pq(rr )( pqr )( pqr )( pqr )( pqr )(pp)(rp)(pp)

33、(rp)p( pr )pp(qq)(rr )( pqr )( pqr )( pqr )( pqr )( pq)pq 和 (pp)(rp) 等值于同一個(gè)關(guān)于p , q , r 的主析取范式( pqr )( pq r )( pqr )( pqr ) ，因此，( pq)pq(pp)(rp) 。(2)( pq)( pr )(pq)(pr )(pq( rr )(p( qq) r )(pqr )(pqr )(pqr )(pqr )(pqr )(pqr )(pqr )(pq(rpr )(qpr(qpq)( qr )r )(pq)(pr )(pqr )(pqr )(pqr )(pqr )(pqr )(pqr

34、)(pqr )( pq)( pr ) 和 pqr 的主合取范式相同，所以，( pq)( pr )pqr 。29. 判斷以下關(guān)系是否成立，并說(shuō)明理由。(1)pq ,p |q(2)pq , ,q |p(3) (3)p1q1 ,p 2q2 , p1p 2 |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 ，所以pq, pq , q |/ p 。(3) 若真值賦值 v 使得v( p1q1 )v( p2q 2 )v( p1p 2 )1 ，則 v( p1)v( p 2 )1 ，因而 v( q1)v(q 2 )1 ， v(q1q 2 )1。所以p1q1 ,p 2q2 , p1p2 |q1q 2 。(4) 真 值 賦 值 v( p / 0 , q / 0)使 得 v( pq)v(qp) 1 ， 但v( pq) 0。 所 以p q , qp | / pq 。(5) 真 值 賦 值 v( p/ 0 , q /