離散數(shù)學(左孝凌)課后習題解答(詳細)

1、離散數(shù)學習題1. 以下句子中，哪些是命題？哪些不是命題？如果是命題，指出它的真值。 中國有四大創(chuàng)造。 計算機有空嗎? 不存在最大素數(shù)。 21+35。 老王是山東人或河北人。 2 與 3 都是偶數(shù)。 小李在宿舍里。 這朵玫瑰花多美麗呀! 請勿隨地吐痰! 圓的面積等于半徑的平方乘以。 只有 6 是偶數(shù)，3 才能是 2 的倍數(shù)。 雪是黑色的當且僅當太陽從東方升起。如果天下大雨，他就乘班車上班。解：是命題，其中是真命題，是假命題，的真值目前無法確定；不是命題。2. 將以下復合命題分成假設干原子命題。 李辛與李末是兄弟。 因為天氣冷，所以我穿了羽絨服。 天正在下雨或濕度很高。 劉英與李進上山。 王強與劉

2、威都學過法語。 如果你不看電影，那么我也不看電影。我既不看電視也不外出，我在睡覺。 除非天下大雨，否那么他不乘班車上班。解：本命題為原子命題；p：天氣冷；q：我穿羽絨服；p：天在下雨；q：濕度很高；p：劉英上山；q：李進上山；p：王強學過法語；q：劉威學過法語；p：你看電影；q：我看電影；p：我看電視；q：我外出；r：我睡覺；p：天下大雨；q：他乘班車上班。3. 將以下命題符號化。 他一面吃飯，一面聽音樂。 3 是素數(shù)或 2 是素數(shù)。 假設地球上沒有樹木，那么人類不能生存。 8 是偶數(shù)的充分必要條件是 8 能被 3整除。 停機的原因在于語法錯誤或程序錯誤。 四邊形 ABCD 是平行四邊形當且僅

3、當它的對邊平行。 如果 a 和 b 是偶數(shù)，那么 a+b 是偶數(shù)。解：p：他吃飯；q：他聽音樂；原命題符號化為：pqp：3 是素數(shù)；q：2 是素數(shù)；原命題符號化為：pqp：地球上有樹木；q：人類能生存；原命題符號化為：pqp：8 是偶數(shù)；q：8 能被 3 整除；原命題符號化為：pqp：停機；q：語法錯誤；r：程序錯誤；原命題符號化為：qrpp：四邊形 ABCD 是平行四邊形；q：四邊形 ABCD 的對邊平行；原命題符號化為：pq。p：a 是偶數(shù)；q：b 是偶數(shù)；r：a+b 是偶數(shù)；原命題符號化為：pqr4. 將以下命題符號化，并指出各復合命題的真值。如果 3+3=6，那么雪是白的。 如果 3+

4、36，那么雪是白的。 如果 3+3=6，那么雪不是白的。 如果 3+36，那么雪不是白的。是無理數(shù)當且僅當加拿大位于亞洲。3 2+3=5 的充要條件是是無理數(shù)。(假定是 10 進制)3 假設兩圓 O1，O2的面積相等，那么它們的半徑相等，反之亦然。 當王小紅心情愉快時，她就唱歌，反之，當她唱歌時，一定心情愉快。解：設 p：336。q：雪是白的。原命題符號化為：pq；該命題是真命題。原命題符號化為：pq；該命題是真命題。原命題符號化為：pq；該命題是假命題。原命題符號化為：pq；該命題是真命題。p：是無理數(shù)；q：加拿大位于亞洲；原命題符號化為：pq；該命題是假命3題。p：2+35；q：是無理數(shù)；

5、原命題符號化為：pq；該命題是真命題。3p：兩圓 O1,O2的面積相等；q：兩圓 O1,O2的半徑相等；原命題符號化為：pq；該命題是真命題。p：王小紅心情愉快；q：王小紅唱歌；原命題符號化為：pq；該命題是真命題。習題1.判斷以下公式哪些是合式公式，哪些不是合式公式。 (pqr) (p(qr) (pq)(rs) (pqrs) (p(qr)(qp)qr)。解：是合式公式；不是合式公式。2.設 p：天下雪。q：我將進城。r：我有時間。將以下命題符號化。 天沒有下雪，我也沒有進城。 如果我有時間，我將進城。 如果天不下雪而我又有時間的話，我將進城。解： pq rq prq p、q、r 所表示的命題

6、與上題相同，試把以下公式譯成自然語言。 rq (rq) q (r p) (qr)(rq) 解： 我有時間并且我將進城。 我沒有時間并且我也沒有進城。 我進城，當且僅當我有時間并且天不下雪。 如果我有時間，那么我將進城，反之亦然。4. 試把原子命題表示為 p、q、r 等，將以下命題符號化。 或者你沒有給我寫信，或者它在途中喪失了。 如果張三和李四都不去，他就去。 我們不能既劃船又跑步。 如果你來了，那末他唱不唱歌將看你是否伴奏而定。解： p：你給我寫信；q：信在途中喪失；原命題符號化為：(p q)(pq)。p：張三去；q：李四去；r：他去；原命題符號化為：pqr。p：我們劃船；q：我們跑步；原命

7、題符號化為：pq 。p：你來了；q：他唱歌；r：你伴奏；原命題符號化為：pqr 。5. 用符號形式寫出以下命題。假設上午不下雨，我去看電影，否那么就在家里讀書或看報。我今天進城，除非下雨。僅當你走，我將留下。解：p：上午下雨；q：我去看電影；r：我在家讀書；s：我在家看報；原命題符號化為：pqprs 。p：我今天進城；q：天下雨；原命題符號化為：qp。p：你走；q：我留下；原命題符號化為：qp。習題1.設 A、B、C 是任意命題公式，證明：AA假設 AB，那么 BA假設 AB，BC，那么 AC證明：由雙條件的定義可知 AA 是一個永真式，由等價式的定義可知 AA 成立。因為 AB，由等價的定義

8、可知 AB 是一個永真式，再由雙條件的定義可知BA 也是一個永真式，所以，BA 成立。對 A、B、C 的任一賦值，因為 AB，那么 AB 是永真式， 即 A 與 B 具有相同的真值，又因為 BC，那么 BC 是永真式， 即 B 與 C 也具有相同的真值，所以 A 與C 也具有相同的真值；即 AC 成立。2.設 A、B、C 是任意命題公式，假設 ACBC, AB 一定成立嗎？假設 ACBC, AB 一定成立嗎？假設AB，AB 一定成立嗎？解：不一定有 AB。假設 A 為真，B 為假，C 為真，那么 ACBC 成立，但AB 不成立。不一定有 AB。假設 A 為真，B 為假，C 為假，那么 ACBC

9、 成立，但AB 不成立。一定有 AB。3.構造以下命題公式的真值表，并求成真賦值和成假賦值。 q(pq)p p(qr) (pq)(qp) (pq)(rq)r (p(pq)r)(qr)解：q(pq)p 的真值表如表所示。表pqpqq(pq)q(pq)p00101011101000111111使得公式 q(pq)p 成真的賦值是：00，10，11，使得公式 q(pq)p 成假的賦值是：01。p(qr) 的真值表如表所示。表pqrqrp(qr)0000100111010110111110000101111101111111 使得公式 p(qr)成真的賦值是：000，001，010，011，101，1

10、10，111，使得公式p(qr)成假的賦值是：100。(pq)(qp) 的真值表如表所示。表pqpqqp(pq)(qp)00001011111011111111所有的賦值均使得公式(pq)(qp)成真，即(pq)(qp)是一個永真式。(pq)(rq)r 的真值表如表所示。表pqrqpqrq(pq)(rq)(pq)(rq)r0001000100110001010000010110011110011010101110111100000111100111使得公式(pq)(rq)r 成真的賦值是：000，001，010，011，101，110，111，使得公式(pq)(rq)r 成假的賦值是：100。

11、(p(pq)r)(qr) 的真值表如表所示。使得公式(p(pq)r)(qr)成真的賦值是：000，001，010，011，101，110，111，使得公式(p(pq)r)(qr)成假的賦值是：100。 證明以下等價式：(pq)pq證明：證明(pq)pq 的真值表如表所示。表pqpq(pq) qpq001010011000100111111000由上表可見：(pq)和 pq 的真值表完全相同，所以(pq)pq。pqqp 證明：證明 pqqp 的真值表如表所示。表 1.30表pqrpq p(pq)(p(pq)rqr(p(pq)r)(qr)000001010010010101000111011001

12、0110011000101111011100101111101101pqpqpqqp001111011101100010111001由上表可見：pq 和qp 的真值表完全相同，所以 pqqp。(pq)pq證明：證明(pq)和 pq 的真值表如表所示。表pqpq(pq) qpq001010010101100111111000由上表可見：(pq)和 pq 的真值表完全相同，所以(pq)pq。p(qr)(pq)r證明：證明 p(qr)和(pq)r 的真值表如表所示。表pqrqrp(qr)pq(pq)r00011010011101010010101111011001101101110111000101

13、111111由上表可見：p(qr)和(pq)r 的真值表完全相同，所以 p(qr)(pq)r。p(qp)p(pq)證明：證明 p(qp)和p(pq)的真值表如表所示。表pqqpp(qp)pq pq p(pq)00111111010110111011011111110001由上表可見：p(qp)和p(pq)的真值表完全相同，且都是永真式，所以p(qp)p(pq)。(pq)(pq)(pq)證明：證明(pq)和(pq)(pq)的真值表如表所示。表pqpq(pq)pqpq (pq) (pq)(pq)00100010010110111001101111101100由上表可見：(pq)和(pq)(pq)的

14、真值表完全相同，所以(pq)(pq)(pq)(pq)(pq)(pq) 證明：證明(pq)和(pq)(pq)的真值表如表所示。表pqpq(pq) pq pq(pq)(pq)0010000010101110011011110000由上表可見：(pq)和(pq)(pq)的真值表完全相同，所以(pq)(pq)(pq)。p(qr)(pq)r證明：證明 p(qr)和(pq)r 的真值表如表所示。表pqrqrp(qr)qpq (pq)r0000110100111101010110010111100110000110101111111101100111111001由上表可見：p(qr)和(pq)r 的真值表完

15、全相同，所以 p(qr)(pq)r。5. 用等價演算證明習題 4 中的等價式。(pq)(pq)(條件等價式)pq(德摩根律)qpqp(條件等價式)qp(雙重否認律)pq(交換律) pq(條件等價式)(pq)(pq)(qp)(雙條件等價式)(pq)(qp)(條件等價式)(pq)(qp)(德摩根律)(pq)q)(pq)p)(分配律)(pq)(qp)(分配律)(pq)(qp)(交換律)(pq)(qp)(條件等價式)pq(雙條件等價式)p(qr)p(qr)(條件等價式)(pq)r(結(jié)合律)(pq)r(德摩根律)(pq)r(條件等價式)p(qp)p(qp)(條件等價式)Tp(pq)p(pq)(條件等價式

16、)T所以 p(qp)p(pq)(pq)(pq)(pq)(例 1.17)(pq)(pq)(德摩根律)(pq)(pq)(德摩根律)所以(pq)(pq)(pq)(pq)(pq)(qp)(雙條件等價式)(pq)(qp)(條件等價式)(pq)(pq)(德摩根律)p(qr)p(qr)(條件等價式)(pq)r(結(jié)合律)(pq)r(德摩根律)(pq)r(條件等價式)6.試用真值表證明以下命題定律。結(jié)合律：(pq)rp(qr)，(pq)rp(qr)證明：證明結(jié)合律的真值表如表和表所示。表pqrpq(pq)rqrp(qr)0000000001011101011110111111100110110111111101

17、1111111111表pqrpq(pq)rqrp(qr)00000000010000010000001100101000000101000011010001111111由真值表可知結(jié)合律成立。分配律：p(qr)(pq)(pr)，p(qr)(pq)(pr)證明：證明合取對析取的分配律的真值表如表所示，析取對合取的的分配律的真值表如表所示。表pqrqrp(qr)pqpr(pq)(pr)0000000000110000010100000111000010000000101110111101110111111111表pqrqrp(qr)pqpr(pq)(pr)000000000010001001000

18、1000111111110001111101011111100111111111111由真值表可知分配律成立。假言易位式：pqqp證明：證明假言易位式的真值表如表所示。表pqpqqpqp001111011011100100111001由真值表可知假言易位律成立。雙條件否認等價式：pqpq證明：證明雙條件否認的真值表如表所示。表pqpqpqpq001111010100100010111001由真值表可知雙條件否認等價式成立。習題 1.4 1.用真值表或等價演算判斷以下命題公式的類型。(pq)q(pq)q條件等價式(pq)q德摩根律q 可滿足式吸收律(pq)q(pq)q條件等價式(pq)q德摩根律

19、F永假式結(jié)合律、矛盾律(pq)pq(pq)pq條件等價式(pp)(qp)q分配律(qp)q同一律、矛盾律(qp)q條件等價式(qp)q德摩根律T(永真式)零律、排中律(pq)q(pq)q條件等價式q可滿足式吸收律(pq)(qp)(pq)(pq)假言易位式T(永真式)(pq)(qr)(pr)(pq)(qr)(pr)條件等價式(pq)(qr)(pr)德摩根律(pq)(pqr)(prr)分配律(pq)(pqr)同一律、排中律、零律(pqrp)(pqrq)分配律T(永真式)p(pq) p(pq)條件等價式T(永真式)p(pqr)p(pqr)條件等價式T(永真式)2.用真值表證明以下命題公式是重言式。(

20、p(pq)q(p(pq)q 的真值表如表所示。由表可以看出(p(pq)q 是重言式。表pqpqp(pq) (p(pq)q00101011011000111111(q(pq)p(q(pq)p 的真值表如表所示。由表可以看出(q(pq)p 是重言式。表pqpqqq(pq) p (q(pq)p0011111011001110010011110001(p(pq)q(p(pq)q 的真值表如表所示。由表可以看出(p(pq)q 是重言式。表pqpq p p(pq)(p(pq)q000101011111101001111001(pq)(qr)(pr)(pq)(qr)(pr)的真值表如表所示。由表可以看出(p

21、q)(qr)(pr)是重言式。表pqrpqqr(pq)(qr)pr(pq)(qr)(pr)0001111100111111010100110111111110001001101010111101000111111111(pq)(pr)(qr)r(pq)(pr)(qr)r 的真值表如表所示。由表可以看出(pq)(pr)(qr)r 是重言式。表pqrpqprqr(pq)(pr)(qr) (pq)(pr)(qr)r0000110100101101010110010111111110010101101111111101000111111111(pq)(rs)(pr)(qs)(pq)(rs)(pr)(q

22、s)的真值表如表所示。由表可以看出(pq)(rs)(pr)(qs)是重言式。表pqrspqrs(pq)(rs)prqs(pr)(qs)原公式00001110011000111100110010100001100111110011010011100110101111011101101000011011111101111000010001110010100011101000010011011010100111001110011110111101111110100100111111111111(pq)(qr)(pr)(pq)(qr)(pr)的真值表如表所示。由表可以看出(pq)(qr)(pr)是重言

23、式。表pqrpqqr(pq)(qr)pr(pq)(qr)(pr)00011111001100010100001101101001100010011010001111010001111111113. 用等價演算證明題 2 中的命題公式是重言式。(p(pq)q(p(pq)q(p(pq)q(pp)(pq)q(pq)qT(q(pq)p(q(pq)p(q(pq)p(q(pq)p(pq)(pq)(pq)(pq)T(p(pq)q(pq)q(pq)qpqqT(pq)(qr)(pr)(pq)(qr)(pr)(pq)(qr)(pr)(pq)(pqr)(prr)(pq)(pqr)(pqrp)(pqrq)T(pq)(

24、pr)(qr)r(pq)(pr)(qr)r(pq)(pq)r)r(pq)r)r(pq)r)r(pq)rrT(pq)(rs)(pr)(qs)(pq)(rs)(pr)(qs)(pq)(rs)(pr)(qs)(pq)(rs)(prq)(prs)(pq)(rs)(prq)(pq)(rs)(prs)(rs)(prqp)(prqq)(rs)(prsp)(prsq)(rs)T)(rs)(pqrs)(rs)(pqrs)(pqrsr)(pqrss)T(pq)(qr)(pr)(pq)(qp)(qr)(rq)(pr)(pq)(qp)(qr)(rq)(pr)(pr)(pq)(pr)(rq)(qr)(qp)(pr)(p

25、(qr)(qr)(rq)(qp)(pr)(qr)(qr)(p(qr)(rq)(qp)(pr)(T(p(qr)(rq)(qp)(pr)p(qr)(rq)(qp)(pr)p(qr)(qp)(pr)(rq)p(qr)(p(qr)(qr)p(qr)p(qr)T4.證明以下等價式：(pr)(qr)(pr)(qr)(pq)r(pq)r(pq)r(pq)(pq)(pq)(pq)p(qq)pFpp(pq)p(pq)(pp)(pq)F(pq)pq習題 1.5 1.求以下命題公式的析取范式。(pq)r(pq)rpqr(pq)r(pq)r(pq)rpqrp(pq) p(pq)(pp)(pq) pq(pq)(qr)(

26、pq)(qr) q(pr)(pq)(rt)(pq)(rt)(pqr)(pqt)2. 求以下命題公式的合取范式。(pq)(pq)pqq(pqr)(qp)(qq)(qr)(qp)(qr)(pq)(pq)(pq)p)(pq)q)(pp)(qp)(pq)(qq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)r(pq)r(pq)rpqr3.求以下命題公式的主析取范式，并求命題公式的成真賦值。(pq)(pr)作(pq)(pr)的真值表，如表所示。表pqrpqpr(pq)(pr)000000001000010000011000100000101011110101111111由真值表可知，原

27、式(pqr)(pqr)(pqr)(主析取范式)5,6,7使得命題公式(pq)(pr)成真的賦值是：101，110，111。(pq)(pr)(pq)(pr)(pq)(pr)(pqp)(pqr)pqr(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)1,2,3,4,5,6,7使得命題公式(pq)(pr)成真的賦值是：001，010、011，100，101，110，111。(pq)(pq)作(pq)(pq)的真值表，如表所示。表pqp qpqpq(pq)(pq)0011100011011110011111100001由真值表可知:原式(pq)(pq)(pq) (主析

28、取范式)1,2,3使得命題公式(pq)(pq)成真的賦值是：01，10，11。(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pqp)(pqq)pq(pq)(pq)(pq)(主析取范式)0,2,3使得命題公式(pq)(pq)成真的賦值是：00,10,11。(p(qr)(p(qr)(p(qr)(p(qr)(pq)(pr)(pq)(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)使得命題公式(p(qr)(p(qr)成真的賦值是：000,111。4.

29、求以下命題公式的主合取范式，并求命題公式的成假賦值。(pq)r(pq)r(pqr)(pqr)(pr)(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)0,2,4,5,6使得命題公式(pq)r 成假的賦值是：000,010,100,101,110。(pq)(pq)作(pq)(pq)的真值表，如表所示。表pqpq(pq)qpq(pq)(pq)0010110011001010011111110001由真值表可知:原式(pq)(pq)0,1使得命題公式(pq)(pq)成假的賦值是：00,01。(pq)(pr)(pq)(pr)(pq)(

30、pr)(pqp)(pqr)pqr0使得命題公式(pq)(pr)成假的賦值是：000。(pq)p(pq)ppqpF0,1,2,3使得命題公式(pq)p 成假的賦值是：00,01,10,11。(p(qr)rpqrrpqr4使得命題公式(p(qr)r 成假的賦值是：100。5. 求以下命題公式的主析取范式，再用主析取范式求出主合取范式。(pq)(qr)(pq)(qr)(pq)q)(pq)r)(pq)(pr)(qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)0,1,3,72,4,5,6(pqr)(pqr)(pqr)(pqr)(主合

31、取范式)(pq)r(pq)r(pqr)(pqr)(pr)(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)1,3,5,6,70,2,4(pqr)(pqr)(pqr)(主合取范式)6. 求以下命題公式的主合取范式，再用主合取范式求出主析取范式。(pq)r(pq)(qp)r(pq)(qp)r(pqr)(pqr)(qpr)(qpr)(pr)(pr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主合取范式)0,2,3,4,5,

32、61,7(pqr)(pqr)(主析取范式)(pq)q(pq)qpqqT(無主合取范式)0,1,2,3(pq)(pq)(pq)(pq)7.用主析取范式判斷以下命題公式是否等價。p(qr)和 q(pr)p(qr)p(qr)pqr(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)0,1,2,3,4,5,7q(pr)q(pr)pqr(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)0,1,2,3,4,5,7因為 p(qr)與 q(pr)的主析取范式相同，所以 p(qr)q(pr)。(pq)(pr)和 p(qp)(pq)(pr)(pq)

33、(pr)p(qr)(pq)(pq)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(主析取范式)0,1,2,3,7p(qp)p(qp)(pq)(pp)pq(pq)(pq)(pq)(pq)(pq)(pq)(pq) (主析取范式)0,1,3因為(pq)(pr)與 p(qp)的主析取范式不相同，所以(pq)(pr)與p(qp)不等價。8. 用主合取范式判斷以下命題公式是否等價。(pq)r 和 p(qr)(pq)r(pq)r(pq)r(pr)(qr)(pqr)(pqr)(pqr)0,2,6p(qr)p(qr)pqr6因為

34、(pq)r 與 p(qr)的主合取范式不相同，所以(pq)r 與 p(qr)不等價。(pq)(pq)和(pq)(pq)(pq)(pq)1,20,3(pq)(pq)(pq)(pq)(pq)(pq)0,3因為(pq)(pq)和(pq)(pq)的主合取范式相同，所以(pq)(pq) (pq)(pq)。習題，的等價式表示。(pq)r(pq)(qp)r(pq)(pq)r(p(q(qr)(p(qqr)(q(qr)p(qr)(q(qr)p(qr)qpqrp(pq)p(pq)(p(pq)(p(pq)(pq)ppq(pq)r(pq)(pq)r(pq)(pq)r)(pq)(pq)r)(pqr)(pqr)(pq)(

35、pq)r)(pqr)(pqr)(pq)(pq)r)(pq)(rt)(pq)(qp)(rt)(pq)(qp)(rt)(pq)(qp)(rt)(pq)(qp)(rt)(pq)(qp)(rt)2. 將以下命題公式用只含，的等價式表示。(pq)p(pq)p)pq(pq)(qp)(pq)(qp)(pq)r(pq)r(pq)r)pq(pq)(pq)(qp) (pq)(pq)(pq)r(pq)(qp)r(pq)(qp)r)3. 將以下命題公式用只含，的等價式表示。pq(rp)pq(rp)(pqrp)(pq)(pr)(pq)(pr)(pr)(pq)(pr)(pr)(pq)(pq)(pq)(pq)pq(pq)(

36、pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq) (p(qr)(pr)(pqr)(pr)T4.以下結(jié)論是否成立？假設成立，請證明。假設不成立，舉反例說明。pqqp成立。pq(pq)(qp)qppqqp成立。pq(pq)(qp)qpp(qr)(pq)r不成立。p(qr)p(qr)(p(qr)p(qr)(pqr)(pqr)(pqr)4,5,6而(pq)r(pq)r(pq)r)(pq)r(pqr)(pqr)(pqr)1,3,5顯然上式不成立p(qr)(pq)r不成立。p(qr)p(qr)(p(qr)p(qr)(pqr)(pqr)(pqr)1,2,3而(pq)r(pq)r

37、(pq)r)(pq)r(pqr)(pqr)(pqr)2,4,6顯然上式不成立。5.證明以下等價式。(pq)pq證明：(pq)(pq)(pq)pqpq (pq) pq所以：(pq)pq(pq)pq證明：(pq)(pq)pqpq (pq)pq所以：(pq)pq6.將以下命題公式僅用“表示。ppppq(pq)(pq)(pq)pq(pq) pq (pp)(qq)7.將以下命題公式僅用“表示。p(pp)pppq(pq)pq(pp)(qq)pq(pq)(pq)(pq)(pq)習題 1. 寫出以下命題公式的對偶式。(pq)r 的對偶式是：(pq)r(pq)(rp)對偶式是(pq)(rp) pq(pq)(pq

38、)(qp)(pq)(qp)(pq)(qp)所以 pq 的對偶式是(pq)(qp)而(pq)(qp)(pq)(qp)pqpq(pq)(pq)所以 pq 的對偶式是(pq)(pq)r(pq)rpqr所以(pq)r 的對偶式是pqr(pq)r 的對偶式是(pq)r(pq)r(pq)r所以(pq)r 的對偶式是(pq)rp(qr)(pq)p(qr)(pq)(pq)(pqr)所以 p(qr)(pq)的對偶式是(pq)(pqr)(pq)r(pq)r(pq)(qp)r(pq)(qp)r(pq)(pq)r所以(pq)r 的對偶式是(pq)(pq)r2. 設 pq 為公式，那么 qp 稱為該公式的逆換式，pq

39、稱為反換式，qp稱為逆反式。證明：公式與它的逆反式等價，即 pqqp 證明：pqpq而qpqppq所以 pqqp公式的逆換式與公式的反換式等價，即 qppq證明：qpqp而pqpqpqqp所以 qppq3.用真值表或等價演算證明以下蘊含式。pqpq證明：(pq)(pq)(pq)(pq)pqpqT所以，pqpqpqp(pq)證明：作(pq)(p(pq)的真值表，如表所示。表pqpqpqp(pq)(pq)(p(pq)001011011011100001111111由以上真值表可知：(pq)(p(pq)是一個永真式，所以 pqp(pq)ppq證明：p(pq)ppqppqT所以，ppqp(qr)(pq

40、)(pr)證明：(p(qr)(pq)(pr)(pqr)(pq)(pr)(pqr)(pq)pr(pqr)r)(pq)p)(pr)(qr)(rr)(pp)(pq)(pr)(qr)pq(prp)(qrp)qqrpq1所以，p(qr)(pq)(pr)p(pq)q證明：作(p(pq)q 的真值表，如表所示。表pqpqp(pq)(p(pq)q00101011011000111111由以上真值表可知：(p(pq)q 是一個永真式，所以 p(pq)qq(pq)p證明：作(p(pq)q 的真值表，如表所示。表pqqpqq(pq) (q(pq)p001111010101101001110101由以上真值表可知：(

41、q(pq)p 是一個永真式，所以q(pq)p“假設前件為真，推證后件也為真或假設后件為假，推證前件也為假“的方法證明以下蘊含式。pqpq證明：假設前件 pq 為真，證明后件 pq 也為真。因為 pq 為真，所以 p 為真并且 q 也為真，根據(jù)條件的定義可知 pq 也為真。所以，pqpqpqp(pq)證明:假設后件 p(pq)為假,證明前件 pq 必為假；因為 p(pq)為假，那么 p 為真,q 為假；根據(jù)條件的定義可知 pq 也為假。即：pqp(pq)ppq證明:假設前件 p 為真,那么p 為假, 根據(jù)條件的定義可知pq 必為真。所以，原蘊含式成立。p(qr)(pq)(pr)證明:假設后件(p

42、q)(pr)為假, 證明前件 p(qr)必為假。因為(pq)(pr)為假，所以，pq 為真，pr 為假；因為 pr 為假，所以 p 為真，r 為假；所以，q 必為真；因為 q 為真，r 為假，所以 qr 必為假；因為 p 為真，所以，p(qr)必為假。所以，原蘊含式成立。p(pq)q證明：假設前件 p(pq)為真，證明后件 q 也為真。因為 p(pq)為真，所以 p 為真，pq 也為真，根據(jù)條件的定義 q 必為真。所以，原蘊含式成立。q(pq)p證明：假設前件q(pq)為真，證明后件p 也為真。因為q(pq)為真，所以，q 為真，q 為假，又因為 pq 為真，根據(jù)條件的定義p 為假，所以p 必

43、為真。所以，原蘊含式成立。5.設 A 是任意的命題公式，證明 AA證明：由條件的定義可知：AA 是一個永真式；根據(jù)蘊含式的定義可知 AA。習題習題證明以下各題的有效結(jié)論。(p(qr)，pqr(p(qr)(pq)r 的全真值表如表所示。表pqrqrp(qr)pq(p(qr)(pq)(p(qr)(pq)r0001100100111001010010010111100110011001101110011100010111111111由真值表可知，(p(qr)(pq)r 是永真式，所以(p(qr)，pqr。pq,(qr),rp(pq)(qr)r)p 的全真值表如表所示。表pqrpq r(qr)(pq)

44、(qr)r(pq)(qr)r)p0001111100110101010110010111010110001101101001011101100111110101由真值表可知：(pq)(qr)r)p 是永真式，所以pq，(qr)，rp。pq,rqpr(pq)(rq)(pr)的真值表如表所示。表pqrpqrq pr (pq)(rq) (pq)(rq)(pr)0001111100111111010111110111010110001101101010011101111111110001由真值表可知：(pq)(rq)(pr)是永真式，所以pq,rqpr。pq，qrpr(pq)(qr)(pr)的真值表如

45、表所示。表pqrpqqrpr(pq)(qr)(pq)(qr)(pr)0001111100111111010101010111111110001001101011011101000111111111由真值表可知：(pq)(qr)(pr)是永真式，所以 pq，qrpr。pp,pq,pqq(pp)(pq)(pq)q 的真值表如表所示。表pqrpp pq pq (pp)(pq)(pq) (pp)(pq)(pq)q0001100100111001010111110111111110010101101101011101111111111111由真值表可知：(pp)(pq)(pq)q 是永真式，所以pp,p

46、q,pqq。pq，qrpr(pq)(qr)(pr)的真值表如表所示。表pqrpqqrpr(pq)(qr)(pq)(qr)(pr)0001111100110001010001010110100110001001101001011101000111111111由真值表可知：(pq)(qr)(pr)是永真式，所以 pq，qrpr。2.用等價演算法，主析取范式法或蘊含演算法證明上題中的各有效結(jié)論。(p(qr),pqr(p(qr)(pq)r(p(qr)(pq)r(pqr)(pq)r(pqr)(pq)r(pqr)(pqr)1所以(p(qr),pqrpq,(qr),rp(pq)(qr)r)p(pq)(qr)

47、r)p(pq)(qr)r)p(pq)(qr)rp(pq)p)(qr)r)(pq)(qr)1所以pq,(qr),rppq,rqpr(pq)(rq)(pr)(pq)(rq)(pr)(pq)(rq)(pr)(pq)(rq)(pr)(pq)p)(rq)r)(pq)(qr)1所以pq,rqprpq，qrpr(pq)(qr)(pr)(pq)(qr)(pr)(pq)(qr)(pr)(pq)(rq)pr(pq)p)(rq)r)(pq)(qr)1所以 pq，qrprpp,pq,pqq(pp)(pq)(pq)q(1(pq)(pq)q(pq)(pq)q(pq)(pq)qqq1所以 pp,pq,pqqpq，qrpr(

48、pq)(qr)(pr)(pq)(qp)(qr)(rq)(pr)(pq)(qp)(qr)(rq)(pr)(pr)(pq)(pr)(rq)(qr)(qp)(pr)(p(qr)(qr)(rq)(qp)(pr)(qr)(qr)(p(qr)(rq)(qp)(pr)(T(p(qr)(rq)(qp)(pr)p(qr)(rq)(qp)(pr)p(qr)(qp)(pr)(rq)p(qr)(p(qr)(qr)p(qr)p(qr)T所以 pq，qrpr3.推理證明以下各題的有效結(jié)論。p(qr)，(ts)p，(ts)qr證明：tsP(ts)pPpT假言推理p(qr)PqrT假言推理pq，(pq)(ts)(ts)證明:

49、 pqPpT化簡律qT化簡律pqT例 1.30(2)qpT例 1.30(2) (pq)(qp)T合取引入pqT雙條件等價式(pq)(ts)PtsT假言推理(pq)(rs)，(qp)r,rpq證明:rP(qp)rPqpT析取三段論rsT附加律(pq)(rs)PpqT拒取式(pq)(qp)T合取引入pqT雙條件等價式pqr，rs，spq證明:sPrsPrT析取三段論pqrP(pq)T拒取式pqT德摩根律pp,pq,pqq證明:qP(附加前提)pqPpT拒取式pqPqT假言推理qq(矛盾)T合取引入ps，pq，rspr證明:(pr)P(附加前提)prT條件等價式pT化簡律rT化簡律rsPsT假言推理

50、psPpT析取三段論pp(矛盾)T合取引入4.用 CP 規(guī)那么推證以下各題的有效結(jié)論。pq,rqpr證明:pP(附加前提)pqPqT析取三段論rqPrT拒取式prCP 規(guī)那么pqrs，stupu證明:pP(附加前提)pqT附加律pqrsPrsT假言推理sT化簡律stT附加律stuPuT假言推理puCP 規(guī)那么p(qr)，qs，(tu)s，q(pt)qt證明:qP(附加前提)qsPsT析取三段論(tu)sP(tu)T拒取式( tu)T條件等價式tuT德摩根律tT化簡律qtCP 規(guī)那么pq，pr，qssr證明:因為 srsr，原題可改寫為：pq，pr，qssr。sP(附加前提)qsPqT拒取式pq

51、PpT析取三段論prPrT假言推理srCP 規(guī)那么pqr，rs，pspq證明:pP(附加前提)psPsT假言推理rsPrT析取三段論pqrP(pq)T拒取式pqT德摩根律qT析取三段論pqCP 規(guī)那么prq，sp，rsq證明:sP(附加前提)spPpT析取三段論prqPrqT假言推理qT化簡律sqCP 規(guī)那么5.用歸謬法推證以下各題的有效結(jié)論。pq，(pq)(ts)ts證明:(ts)P(附加前提)(pq)(ts)P(pq)T拒取式(pq)(pq)T例(pq) (pq)T德摩根律(pq)T化簡律pqP(pq)(pq)(矛盾)T合取引入rq，rs，sq，pqp證明:pP(附加前提)pT雙重否認律p

52、qPqT假言推理rqPrT拒取式rsPsT析取三段論sqPqT假言推理qq矛盾T合取引入pq，(qr)r，(ps)s證明:sP(附加前提)sT雙重否認律(ps)Pps T德摩根律pT析取三段論pqPqT假言推理(qr)rPqrT化簡律rT化簡律rT析取三段論rr(矛盾)T合取引入(pq)(rs)，(qt)(su)，(tu)，prp證明:pP(附加前提)pT雙重否認律prPrT假言推理(pq)(rs)PpqT化簡律rsT化簡律qT假言推理sT假言推理(qt)(su)PqtT化簡律suT化簡律tT假言推理uT假言推理tuT合取引入(tu)P(tu)(tu)(矛盾)T合取引入p(qr)，(ts)p，

53、(ts)qr證明：(qr)P(附加前提)p(qr)PpT拒取式(ts)pP(ts)T拒取式(ts)P(ts)(ts)(矛盾)T合取引入pq，rq，rp證明：pP(附加前提)pT雙重否認律pqPqT假言推理rqPrT拒取式rPrr矛盾T合取引入6. 證明下面各命題推得的結(jié)論是有效的：如果今天是星期三，那么我有一次離散數(shù)學或數(shù)字邏輯測驗。如果離散數(shù)學課老師有事，那么沒有離散數(shù)學測驗。今天是星期三且離散數(shù)學老師有事。所以，我有一次數(shù)字邏輯測驗。證明：設 p：今天是星期三。q：我有一次離散數(shù)學測驗。r：我有一次數(shù)字邏輯測驗。s：離散數(shù)學課老師有事。該推理就是要證明：p(qr)，sq，psrpsPpT化

54、簡律sT化簡律sqPqT假言推理p(qr)PqrT假言推理rT析取三段論1將以下命題符號化。(1) 4 不是奇數(shù)。解：設 A(x)：x 是奇數(shù)。a：4?！? 不是奇數(shù)。符號化為：A(a)(2) 2 是偶數(shù)且是質(zhì)數(shù)。解：設 A(x)：x 是偶數(shù)。B(x)：x 是質(zhì)數(shù)。a：2?！? 是偶數(shù)且是質(zhì)數(shù)。符號化為：A(a)B(a)(3) 老王是山東人或河北人。解：設 A(x)：x 是山東人。B(x)：x 是河北人。a：老王。“老王是山東人或河北人。符號化為：A(a)B(a)(4) 2 與 3 都是偶數(shù)。解：設 A(x)：x 是偶數(shù)。a：2，b：3?！? 與 3 都是偶數(shù)。符號化為：A(a)A(b)(5)

55、 5 大于 3。解：設 G(x,y)：x 大于 y。a：5。b：3?！? 大于 3。符號化為：G(a,b)(6) 假設 m 是奇數(shù)，那么 2m 不是奇數(shù)。解：設 A(x)：x 是奇數(shù)。a：m。b：2m?！凹僭O m 是奇數(shù)，那么 2m 不是奇數(shù)。符號化為：A(a)A(b)(7) 直線 A 平行于直線 B 當且僅當直線 A 不相交于直線 B。解：設 C(x,y)：直線 x 平行于直線 y。設 D(x,y)：直線 x 相交于直線 y。a：直線A。b：直線 B?！爸本€ A 平行于直線 B 當且僅當直線 A 不相交于直線 B。符號化為：C(a,b)D(x,y) (8) 小王既聰明又用功，但身體不好。解：

56、設 A(x)：x 聰明。B(x)：x 用功。C(x)：x 身體好。a：小王?！靶⊥跫嚷斆饔钟霉?，但身體不好。符號化為：A(a)B(a)C(a)(9) 秦嶺隔開了渭水和漢水。解：設 A(x,y,z)：x 隔開了 y 和 z。a：秦嶺。b：渭水。c：漢水?！扒貛X隔開了渭水和漢水。符號化為：A(a,b,c)(10) 除非小李是東北人，否那么她一定怕冷。解：設 A(x)：x 是東北人。B(x)：x 怕冷。a：小李?！俺切±钍菛|北人，否那么她一定怕冷。符號化為：B(a)A(a)2將以下命題符號化。并討論它們的真值。(1) 有些實數(shù)是有理數(shù)。解：設 R(x)：x 是實數(shù)。Q(x)：x 是有理數(shù)。“有些實

57、數(shù)是有理數(shù)。符號化為：(x)(R(x)Q(x)它的真值為：真。(2) 但凡人都要休息。解：設 R(x)：x 是人。S(x)：x 要休息?！暗踩硕家菹?。符號化為：(x)(R(x)S(x)它的真值為：真。(3) 每個自然數(shù)都有比它大的自然數(shù)。解：設 N(x)：x 是自然數(shù)。G(x,y)：x 比 y 大?！懊總€自然數(shù)都有比它大的自然數(shù)。符號化為：(x)(N(x)(y)(N(y)G(y,x)它的真值為：真。(4) 烏鴉都是黑的。解：設 A(x)：x 是烏鴉。B(x)：是黑的?！盀貘f都是黑的。符號化為：(x)(A(x)B(x)它的真值為：真。(5) 不存在比所有火車都快的汽車。解：設 A(x)：x

58、是汽車。B(x)：是火車。K(x,y)：x 比 y 快。“不存在比所有火車都快的汽車。符號化為：(x)(A(x)(y)(B(y)K(x,y)它的真值為：真。(6) 有些大學生不佩服運發(fā)動。解：設 S(x)：x 是大學生。L(x)：是運發(fā)動。B(x,y)：x 佩服 y。“有些大學生不佩服運發(fā)動。符號化為：(x)(S(x)L(y)B(x,y)它的真值為：真。(7) 有些女同志既是教練員又是運發(fā)動。解：設 W(x)：x 是女同志。J(x)：x 是教練員。L(x)：x 是運發(fā)動?！坝行┡炯仁墙叹殕T又是運發(fā)動。符號化為：(x)(W(x)J(x)L(x)它的真值為：真。(8) 除 2 以外的所有質(zhì)數(shù)都

59、是奇數(shù)。解：設 A(x)：x 是質(zhì)數(shù)。B(x)：x 是奇數(shù)。C(x,y)：x 不等于 y?！俺?2 以外的所有質(zhì)數(shù)都是奇數(shù)。符號化為：(x)(A(x)C(x,2)B(x)它的真值為：真。3指出一個個體域，使以下被量化謂詞的真值為真，該個體域是整數(shù)集合的最大子集。在以下各題中，A(x)表示：x0，B(x)表示：x=5，C(x,y) 表示：xy=0(1) (x)A(x)解：正整數(shù)集合 Z+。(2) (x)A(x)解：整數(shù)集合 Z。(3) (x)B(x) 解：集合5 。(4) (x)B(x)解：整數(shù)集合 Z。(5) (x)(y)C(x,y)解：整數(shù)集合 Z。4分別在全總個體域和實數(shù)個體域中，將以下命

60、題符號化。(1) 對所有的實數(shù) x，都存著實數(shù) y，使得 xy=0解：設 R(x)：x 是實數(shù)。B(x,y)：xy=0。在實數(shù)個體域符號化為：(x)(y)B(x,y)在全總個體域符號化為：(x)(R(x)(y)(R(y)B(x,y)(2) 存在著實數(shù) x，對所有的實數(shù) y，都有 xy=0 解：設 R(x)：x 是實數(shù)。B(x,y)：xy=0。在實數(shù)個體域符號化為：(x)(y)B(x,y)在全總個體域符號化為：(x)(R(x)(y)(R(y)B(x,y)(3) 對所有的實數(shù) x 和所有的實數(shù) y，都有 xy=yx解：設 R(x)：x 是實數(shù)。B(x,y)：x=y。在實數(shù)個體域符號化為：(x)(y