【正文】 P (4) P(c) ES,(3) (5) Q(c) T,(2),(4),I (6) (?x)Q(x) EG,(5)(4)中的 “ c” 未必能保證令 (2)為真， 推導(dǎo)錯(cuò)誤！電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程58例 （ ２ )推導(dǎo)可修改為（正確與否？） ：(1) (?x)(P(x)?Q(x)) P(2) (P(c)?Q(c)) US,(1)(3) (?x)P(x) P(4) P(c) ES,(3)(5) Q(c) T,(2),(4),I(6) (?x)Q(x) EG,(5)證明：(?x)(P(x)?Q(x))， (?x)P(x)?(?x)Q(x)(2)中的 “ c” 未必能保證令 (4)為真， 推導(dǎo)錯(cuò)誤！電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程59例 (３ )正確推導(dǎo) 如下：(1) (?x)P(x) P(2) P(c) ES，(1)(3) (?x)(P(x)?Q(x)) P(4) (P(c)?Q(c)) US,(3)(5) Q(c) T,(2),(4),I(6) (?x)Q(x) EG,(5)證明：(?x)(P(x)?Q(x))， (?x)P(x)?(?x)Q(x)電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程60例 證明 ： 1)(?x)(P(x)∧ Q(x)) P 2)(P(c)∧ Q(c)) ES,1) 3)P(c)T,2),I 4)Q(c)T,2),I 5)(?x)P(x) EG,3) 6)(?x)Q(x) EG,4) 7)(?x)P(x)∧ (?x)Q(x)T,5),6),I 證明：(?x)(P(x)∧ Q(x))?(?x)P(x)∧ (?x)Q(x)電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程61例 (續(xù) 1)1) (?x)P(x)∧ (?x)Q(x) P2) (?x)P(x) T,1),I3) P(c) ES,2)4) (?x)Q(x) T,1),I5) Q(c) ES,4)6) (P(c)∧ Q(c)) T,3),4),I7) (?x)(P(x)∧ Q(x)) EG,6) 請看上述推論的逆推導(dǎo) （正確與否？） ：證明：(?x)(P(x)∧ Q(x))?(?x)P(x)∧ (?x)Q(x)“ c” 未必能保證同時(shí)令(2)和 (4)為真， 推導(dǎo)錯(cuò)誤！電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程62例 (續(xù) 2)正確推導(dǎo) ：1)(?x)P(x)∧ (?x)Q(x) P2)(?x)P(x) T,1),I3)P(c) ES,2)4)(?x)Q(x) T,1),I5)Q(b) ES,4)6)(P(c)∧ Q(b)) T,3),4),I7)(?x)(?y)(P(x)∧ Q(y))EG,6) (?x)(P(x)∧ Q(x))?(?x)P(x)∧ (?x)Q(x)的逆推導(dǎo)：電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程63例 證明 (采用反證法， CP規(guī)則的方法自己完成 )：1) ?((?x)P(x)∨ (?x)Q(x)) P(附加前提 )2) ?(?x)P(x)∧ ?(?x)Q(x) T,1),E3) ?(?x)P(x) T,2),I4) ?(?x)Q(x) T,2),I5) (?x)?P(x) T,3),E6) ?P(c) ES,5)證明 (?x)(P(x)∨ Q(x)) ? (?x)P(x)∨ (?x)Q(x)電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程64例 證明（續(xù)） 6) ?P(c) ES,5)7) (?x)?Q(x) T,4),E8) ?Q(c) US,7)9) ?P(c)∧ ?Q(c) T,6),8),I10)?(P(c)∨ Q(c)) T,9),E11)(?x)(P(x)∨ Q(x)) P12)(P(c)∨ Q(c)) US,11)13) ?(P(c)∨ Q(c))∧ (P(c)∨ Q(c)) T,10),12)證明 (?x)(P(x)∨ Q(x)) ? (?x)P(x)∨ (?x)Q(x)電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程65 謂詞邏輯推理的難點(diǎn)（ 1） 在推導(dǎo)過程中，如 既要使用規(guī)則 US又要使用規(guī)則 ES消去公式中的量詞，而且選用的個(gè)體是同一個(gè)符號，則必須 先使用規(guī)則 ES，再使用規(guī)則US。（ 4） 在用規(guī)則 US和規(guī)則 ES消去量詞 時(shí)，此量詞必須位于 整個(gè)公式的最前端 。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程68 謂詞邏輯推理的應(yīng)用例 每個(gè)喜歡步行的人都不喜歡坐汽車；每個(gè)人或者喜歡坐汽車或者喜歡騎自行車；有的人不喜歡騎自行車。證明 設(shè) 謂詞如下 ：P(x)： x是哺乳動(dòng)物；Q(x)： x是脊椎動(dòng)物；R(x)： x是胎生動(dòng)物。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程78例 解決方案S(0,0) S(7,0) S(2,5) S(2,0) S(0,2)S(7,2)S(4,5)S(4,0)大容器注滿大容器注滿小容器倒空小容器注滿小容器倒空倒入小容器容器注滿小容器注滿電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程79例 證明（ 1） S(0, 0) P（ 2） (?x)(?y)(S(x, y)?S(7, y)) P（ 3） (?y)(S(0, y)?S(7, y)) US,(2)（ 4） S(0, 0)?S(7, 0) US ,(3)（ 5） S(7, 0) T,(1),(4).I（ 6） (?x)(?y)(?z)(S(x,y)?S(z,5)) P（ 7） (?y)(?z)(S(7,y)?S(z,5)) US，（ 6）（ 8） (?z)(S(7,0)?S(z,5)) US，（ 7）（ 9） S(7, 0)?S(2,5) ES，（ 8）電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程80例 證明（續(xù)）（ 10） S(2, 5) T,(5),(9),I（ 11） (?x)(?y)(S(x,y)?S(x,0)) P（ 12） (?y)(S(2, y)?S(2,0)) US，（ 11）（ 13） S(2, 5)?S(2,0) US，（ 12）（ 14） S(2, 0) T,(10),(13),I（ 15） (?x)(?y)(?z)(S(x, y)?S(0, z)) P（ 16） (?y)(?z)(S(2, y)?S(0,z)) US，（ 15）（ 17） (?z)(S(2, 0)?S(0,z)) US，（ 16）電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程81例 證明（續(xù)）（ 18） (S(2, 0)?S(0, 2)) ES，（ 17）（ 19） S(0, 2) T,(14),(18),I（ 20） (?x)(?y)(S(x,y)?S(7,y)) P（ 21） (?y)(S(0,y)?S(7,y)) US，（ 20）（ 22） (S(0,2)?S(7,2)) US，（ 21）（ 23） S(7,2) T,(19),(22),I（ 24） (?x)(?y)(?z)(S(x,y)?S(z,5)) P（ 25） (?y)(?z)(S(7,y)?S(z,5)) US，（ 24）（ 26） (?z)(S(7,2) ?S(z,5)) US，（ 25）電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程82例 證明（續(xù)）（ 27） S(7, 2)?S(4, 5) ES，（ 26）（ 28） S(4, 5) T,(23),(27),I（ 29） (?x)(?y)(S(x,y) ?S(x,0) ) P（ 30） (?y)(S(4,y)?S(4,0)) US，（ 29）（ 31） S(4, 5) ?S(4, 0) US，（ 30）（ 32） S(4, 0) T,(30),(33),I電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程83 數(shù)學(xué)歸納法 數(shù)學(xué)歸納法原理假設(shè)要證明的命題能寫成形式 :?n≥n0，有 P(n) 其中 n0是某個(gè)固定的整數(shù)，即：希望證明對所有的整數(shù) n≥n0都有P(n)為真 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程84數(shù)學(xué)歸納法原理假設(shè) 1）驗(yàn)證 n＝ n0，有 P(n0)為真； (歸納基礎(chǔ) )2）假設(shè)對于 n＝ k(k≥n0)，有 P(k)為真； (歸納假設(shè) )3）證明 n＝ k＋ 1，有 P(k+1)為真。謂詞表示： (?n0)(P(n0) ∧ P(n0+1) ∧ (?n)((n≤k)∧ P(n)→P(k+1)) ＝ 1 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程86例 用數(shù)學(xué)歸納法證明： 對所有 n≥1，有 1+2+3+…+n= 證明 歸納基礎(chǔ)驗(yàn)證 1= 顯然 P(1)真值為 1； 歸納假設(shè)假定 對于 n=k(k≥1)，有 P(k)為真，即有 1+2+3+…+k= ； 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程87例 歸納結(jié)論證明 對于 n＝ k＋ 1，有 P(k+1)為真 1+2+3+…+k+(k+1)= +(k+1) =由數(shù)學(xué)歸納法原理得到， P(n)對所有 n≥1為真。由數(shù)學(xué)歸納法原理得到， P(n)對所有 n≥1 為真。 根據(jù) 數(shù)學(xué)歸納法 知：對所有 n?0，有 P(n)為真。此處的鋪成是用直角三正方形正好覆蓋全圖的圖形，每個(gè)直角三正方形不能有重疊，也不許超出圖形之外。由歸納假設(shè)，此左上的 2k2k缺方板可由直角三正方形鋪成，把一個(gè)直角三正方形 T放在中間，則另外三個(gè)四分之一都是 2k2k的缺方板。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程98 按定義證明方法 在離散數(shù)學(xué)中，我們大量的定義描述都是用蘊(yùn)涵型 “P→Q” 的方式來描述的。由 CP規(guī)則知： A ?B。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程103作業(yè)1.（ 2）2.（ 1） （ 6）3.（ 3） （ 5）57. (8) (9)