1、電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程離離 散散 數(shù)數(shù) 學(xué)學(xué)2022年6月1日星期三電子科技大學(xué)計算機科學(xué)與工程學(xué)院電子科技大學(xué)計算機科學(xué)與工程學(xué)院電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-22022-6-1第第5 5章章 推理與證明技術(shù)推理與證明技術(shù) 數(shù)學(xué)歸納法的使用數(shù)學(xué)歸納法的使用 3CPCP規(guī)則相關(guān)證明規(guī)則相關(guān)證明4命題邏輯的推理理論命題邏輯的推理理論 1謂詞邏輯的推理理論謂詞邏輯的推理理論 2電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家

2、級精品課程國家級精品課程 雙語示范課程雙語示范課程105-32022-6-11.1 1.1 本章學(xué)習(xí)要求本章學(xué)習(xí)要求1掌握各種不同掌握各種不同類型的規(guī)則和類型的規(guī)則和公理，特別是公理，特別是命題邏輯和謂命題邏輯和謂詞邏輯的推理詞邏輯的推理規(guī)則和公理規(guī)則和公理3理解謂詞邏輯理解謂詞邏輯的精髓，將其的精髓，將其思想貫穿于所思想貫穿于所有的證明之中有的證明之中 2熟練掌握不熟練掌握不同證明方法同證明方法的證明原理、的證明原理、不同的應(yīng)用不同的應(yīng)用場景場景 重點掌握重點掌握一般掌握一般掌握了解了解電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程

3、105-42022-6-15.2 命題邏輯的推理理論命題邏輯的推理理論 概念概念描述問題描述問題的句子的句子Add Your TexT判斷判斷對概念的肯對概念的肯定定與否定的與否定的判斷判斷推理推理從一個或多從一個或多個前提推出個前提推出結(jié)論的結(jié)論的思維思維過程過程認(rèn)識世界的漸進過程認(rèn)識世界的漸進過程電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-52022-6-1推理的有效性和結(jié)論的真實性推理的有效性和結(jié)論的真實性有效的推理不一定產(chǎn)生真實的結(jié)論有效的推理不一定產(chǎn)生真實的結(jié)論；而；而產(chǎn)生真實結(jié)產(chǎn)生真實結(jié)論的推理過程未必是有效的論

4、的推理過程未必是有效的。有效的推理有效的推理中可能包中可能包含為含為“假假”的前提的前提，而，而無效的推理無效的推理卻可能得到為卻可能得到為“真真”的結(jié)論的結(jié)論 。所謂所謂推理有效推理有效，指的是，指的是它的結(jié)論是它前提的合乎邏它的結(jié)論是它前提的合乎邏輯的結(jié)果輯的結(jié)果。也即，如果它的。也即，如果它的前提都為真，那么所得前提都為真，那么所得的結(jié)論也必然為真的結(jié)論也必然為真，而并不是要求前提或結(jié)論一定，而并不是要求前提或結(jié)論一定為真或為假，如果推理是有效的話，那么不可能它為真或為假，如果推理是有效的話，那么不可能它的前提都為真時，而它的結(jié)論為假。的前提都為真時，而它的結(jié)論為假。電子科技大學(xué)離散數(shù)學(xué)

5、課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-62022-6-15.2.1 5.2.1 推理的基本概念和推理形式推理的基本概念和推理形式 定義定義5.2.0 5.2.0 設(shè)設(shè)G,HG,H是公式，對任意解釋是公式，對任意解釋I I，如果，如果I I滿滿足足G G，那么，那么I I滿足滿足H H，則稱，則稱H H是是G G的邏輯結(jié)果的邏輯結(jié)果( (或稱或稱G G蘊蘊涵涵H),H),記為記為G G，此時稱，此時稱G G為前提為前提，H H為為結(jié)論結(jié)論。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示

6、范課程105-72022-6-1判定定理判定定理定理定理5.2.0 5.2.0 設(shè)設(shè)G,HG,H是公式，是公式，H H是是G G的邏輯結(jié)果當(dāng)且的邏輯結(jié)果當(dāng)且僅當(dāng)僅當(dāng)GG為永真公式。為永真公式。 證明：證明：“”若若G G，但，但GHGH不是永真公式。不是永真公式。于是，必存在一個解釋于是，必存在一個解釋I I，使得，使得GHGH為假，即在為假，即在解釋解釋I I下，下，G G為真，而為真，而H H為假，這與為假，這與G G矛盾，故矛盾，故GHGH是永真公式。是永真公式?！啊比羧鬐HGH是永真式，但是永真式，但G G不成立，故存不成立，故存在在G,HG,H的一個解釋的一個解釋I I，使得，使得G

7、 G為真，而為真，而H H為假，從而為假，從而在解釋在解釋I I下，下，GHGH為假，這與為假，這與GHGH是永真公式矛是永真公式矛盾，所以盾，所以G G。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-82022-6-1推廣推廣 定義定義5.2.1 5.2.1 設(shè)設(shè)G G1 1,G,G2 2, ,G,Gn n,H,H是公式，稱是公式，稱H H是是G G1 1,G,G2 2, , , G Gn n的邏輯結(jié)果的邏輯結(jié)果(G(G1 1,G,G2 2, ,G,Gn n共同蘊涵共同蘊涵H),H),當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)H H是是G G1 1G

8、G2 2GGn n的邏輯結(jié)果的邏輯結(jié)果(logic conclusion)(logic conclusion)。記。記為為G G1 1,G,G2 2, ,G,Gn n，此時稱，此時稱G G1 1,G,G2 2, ,G,Gn n為為有效有效的的(efficacious),(efficacious),否則稱為否則稱為無效的無效的(inefficacious)(inefficacious)。G G1 1,G,G2 2, ,G,Gn n稱為一組前提稱為一組前提(Premise),(Premise),有時用集合有時用集合來 表 示 ， 記來 表 示 ， 記 = G = G1 1, G, G2 2, ,

9、, G, Gn n 。 H H 稱 為稱 為 結(jié) 論結(jié) 論(conclusion)(conclusion)。又稱。又稱H H是是前提集合前提集合的邏輯結(jié)果。記的邏輯結(jié)果。記為為H H。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-92022-6-1判定定理判定定理定理定理5.2.15.2.1 公式公式H H是前提集合是前提集合=G=G1 1,G,G2 2, ,G,Gn n 的邏輯結(jié)果當(dāng)且僅當(dāng)?shù)倪壿嫿Y(jié)果當(dāng)且僅當(dāng)G G1 1GG2 2GGn n為永真為永真公式。公式。 證明：證明：略。略。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離

10、散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-102022-6-1“”與與“”的不同的不同1.1.“”“”僅是一般的僅是一般的蘊涵聯(lián)結(jié)詞蘊涵聯(lián)結(jié)詞，GHGH的結(jié)果仍是的結(jié)果仍是一個公式，而一個公式，而“”卻描述了兩個公式卻描述了兩個公式G G，H H之間的之間的一種邏輯蘊涵關(guān)系，一種邏輯蘊涵關(guān)系，G G H H的的“結(jié)果結(jié)果”，是非命題，是非命題公式；公式；2.2. 用計算機來判斷用計算機來判斷G G H H是辦不到的。然而計算是辦不到的。然而計算機卻可機卻可“計算計算”公式公式GHGH是否為永真公式。是否為永真公式。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)

11、課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-112022-6-15.2.2 5.2.2 判斷有效結(jié)論的常用方法判斷有效結(jié)論的常用方法 =G G1 1, G, G2 2, , ,G,Gn n H HG G1 1GG2 2GGn n為永真公式為永真公式真值表技術(shù)、演繹法和真值表技術(shù)、演繹法和間接證明方法間接證明方法電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-122022-6-11 1、真值表技術(shù)、真值表技術(shù) 設(shè)設(shè)P P1 1,P,P2 2,P,Pn n是出現(xiàn)在前提是出現(xiàn)在前提G G1 1,G,G2 2,G

12、,Gn n和結(jié)和結(jié)論論H H中的一切命題變元，如果將中的一切命題變元，如果將P P1 1,P,P2 2,P,Pn n中所有中所有可能的解釋及可能的解釋及G G1 1,G,G2 2,G,Gn n，H H的對應(yīng)真值結(jié)果都列的對應(yīng)真值結(jié)果都列在一個表中，在一個表中，根據(jù)根據(jù)“”的定義，的定義，則有判斷方法則有判斷方法如下：如下： 對所有對所有G G1 1,G,G2 2, ,G,Gn n都具有真值都具有真值T T的行的行( (表示前提為真的表示前提為真的行行),),如果在每一個這樣的行中，如果在每一個這樣的行中，H H也具有真值也具有真值T T，則則H H是是G G1 1,G,G2 2, ,G,Gn

13、n的邏輯結(jié)果。的邏輯結(jié)果。 對所有對所有H H具有真值為具有真值為F F的行的行( (表示結(jié)論為假的行表示結(jié)論為假的行),),如果在如果在每一個這樣的行中，每一個這樣的行中，G G1 1,G,G2 2, ,G,Gn n中至少有一個公式的中至少有一個公式的真值為真值為F(F(前提也為假前提也為假),),則則H H是是G G1 1,G,G2 2, ,G,Gn n的邏輯結(jié)果的邏輯結(jié)果。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-132022-6-1例例5.2.1 5.2.1 判斷下列判斷下列H H是否是前提是否是前提G G1 1,

14、G,G2 2的邏輯結(jié)果的邏輯結(jié)果(1)(1)H H：Q Q；G G1 1：P P；G G2 2：PQPQ；(2)(2)H H：P P； G G1 1：PQPQ；G G2 2：Q Q；(3)(3)H H：Q Q；G G1 1：P P；G G2 2：PQPQ。解解P Q G1G2H0 0 01 00 1 01 11 0 10 01 1 11 1(1)P Q G1G2H0 01110 11011 00101 1100(2)P Q G1G2H0 0 11 00 1 11 11 0 00 01 1 01 1(3)是是是是否否電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程

15、 雙語示范課程雙語示范課程105-142022-6-12 2 推理定律推理定律設(shè)設(shè)G G，H H，I I，J J是任意的命題公式，則有：是任意的命題公式，則有： I I1 1：GHGHG G( (簡化規(guī)則簡化規(guī)則) )I I2 2：GHGHH H I I3 3：G GGHGH( (添加規(guī)則添加規(guī)則) )I I4 4：H HGHGH I I5 5：G GGHGHI I6 6：H HGHGH I I7 7：(GH)(GH)G GI I8 8：(GH)(GH)HH I I9 9：G G，H HGHGH電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示

16、范課程105-152022-6-12 2 推理定律推理定律( (續(xù)續(xù)) ) I I1010：G G，GHGHH H( (選言三段論選言三段論) )I I1111：G G，G HG HH H I I1212：G G，GHGHH H( (分離規(guī)則分離規(guī)則) ) I I1313：H H，GHGHGG( (否定后件式否定后件式) ) I I1414：GHGH，HIHIGIGI( (假言三段論假言三段論) ) I I1515：GHGH，GIGI，HIHII I( (二難推論二難推論) )電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-16

17、2022-6-1例子例子1)1)、前提：、前提：1.1.如果明天天晴，我們準(zhǔn)備外出旅游。如果明天天晴，我們準(zhǔn)備外出旅游。PQPQ2 2明天的確天晴。明天的確天晴。P P結(jié)論：我們外出旅游。結(jié)論：我們外出旅游。 Q Q可描述為：可描述為：PQPQ，P PQ Q( (分離規(guī)則分離規(guī)則) )2)2)、前提：、前提：1.1.如果一個人是單身漢，則他不幸福。如果一個人是單身漢，則他不幸福。PQPQ2.2.如果一個人不幸福，則他死得早。如果一個人不幸福，則他死得早。QRQR結(jié)論：單身漢死得早。結(jié)論：單身漢死得早。 PRPR可描述為：可描述為：PQPQ，QRQRPRPR( (假言三段論假言三段論) )電子科

18、技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-172022-6-1例子例子( (續(xù)續(xù)1)1)3)3)、某女子在某日晚歸家途中被殺害，據(jù)多方調(diào)查、某女子在某日晚歸家途中被殺害，據(jù)多方調(diào)查確證，兇手必為王某或陳某，但后又查證，作案之確證，兇手必為王某或陳某，但后又查證，作案之晚王某在工廠值夜班，沒有外出，根據(jù)上述案情可晚王某在工廠值夜班，沒有外出，根據(jù)上述案情可得前提：得前提：1.1.兇手為王某或陳某兇手為王某或陳某。PQPQ2.2.如果王某是兇手，則他在作案當(dāng)晚必外出如果王某是兇手，則他在作案當(dāng)晚必外出PRPR3.3.王某案發(fā)之晚并未

19、外出。王某案發(fā)之晚并未外出。 RR結(jié)論：陳某是兇手。結(jié)論：陳某是兇手。Q Q則則可描述為：可描述為：PRPR，RRPP( (否定后件式否定后件式) ) PQPQ，PPQ Q( (選言三段論選言三段論) )電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-182022-6-1例子例子( (續(xù)續(xù)2)2)4)4)、前提：、前提：1.1.如果某同學(xué)為省二級以上運動員，則他將如果某同學(xué)為省二級以上運動員，則他將被大學(xué)錄取。被大學(xué)錄取。PRPR2.2.如果某同學(xué)高考總分在如果某同學(xué)高考總分在560560分以上，則將被分以上，則將被大學(xué)錄取。大

20、學(xué)錄取。QRQR3.3.某同學(xué)高考總分在某同學(xué)高考總分在560560分以上或者是省二級分以上或者是省二級運動員。運動員。PQPQ結(jié)論：該同學(xué)被大學(xué)錄取。結(jié)論：該同學(xué)被大學(xué)錄取。R R則上述例子可描述為：則上述例子可描述為： PQPQ，PRPR，QRQRR R( (二難推論二難推論) )電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-192022-6-13 3 演繹法演繹法 演繹法演繹法是從前提是從前提(假設(shè)假設(shè))出發(fā)，依據(jù)公認(rèn)的推理出發(fā)，依據(jù)公認(rèn)的推理規(guī)則和推理定律，推導(dǎo)出一個結(jié)論來。規(guī)則和推理定律，推導(dǎo)出一個結(jié)論來。 Y YN

21、 N觸發(fā)規(guī)則觸發(fā)規(guī)則新事實新事實事實事實= =結(jié)結(jié)論？論？事實庫事實庫規(guī)則匹配規(guī)則匹配公理庫公理庫將事實加入到事實庫中將事實加入到事實庫中結(jié)束結(jié)束引入事實引入事實電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-202022-6-1演繹的定義演繹的定義定義定義5.2.25.2.2 從前提集合從前提集合推出結(jié)論推出結(jié)論H H的一個演繹是構(gòu)造命題的一個演繹是構(gòu)造命題公式的一個有限序列：公式的一個有限序列： H H1 1，H H2 2，H Hn n其中，其中，H Hi i或者是或者是中的某個前提，或者是前面的某中的某個前提，或者是前面的

22、某些些H Hj j（jijx。 推導(dǎo)推導(dǎo)1： （1）( x)( y)G(x, y)P （2）( y)G(y, y) US,(1) 分析分析：推導(dǎo)：推導(dǎo)1是錯誤的。是錯誤的。正確的推導(dǎo)如下：正確的推導(dǎo)如下： （1）( x)( y)G(x, y) P （2）( y)G(z, y)US,(1)注意：注意：使用使用US規(guī)則規(guī)則來來消去消去量詞時，若選用量詞時，若選用變元變元y取代取代x，則要求，則要求在在原公式中原公式中x x不能出現(xiàn)不能出現(xiàn)在量詞在量詞( ( y)y)或或( ( y)y)的轄域之內(nèi)的轄域之內(nèi)。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課

23、程雙語示范課程105-482022-6-1推理規(guī)則的正確使用（推理規(guī)則的正確使用（2 2）推導(dǎo)推導(dǎo)2： （1）( x)( y)G(x, y) P （2）( y)G(z, y) US,(1) （3）G(z, c) ES,(2) 分析分析：推導(dǎo)：推導(dǎo)2是錯誤的。是錯誤的。正確的推導(dǎo)如下：正確的推導(dǎo)如下： （1）( x) ( y)G(x, y) P （2）( y)G(z, y) US,(1) （3）G(z, f(z) ES,(2) 注意：注意：使用使用ESES規(guī)則規(guī)則來來消去消去量詞時，量詞時， 若還若還有其它有其它自由變自由變元元時，則必須用關(guān)于自由時，則必須用關(guān)于自由變元的變元的函數(shù)符號函數(shù)符號

24、來取代常量符號來取代常量符號. .電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-492022-6-1推理規(guī)則的正確使用（推理規(guī)則的正確使用（3 3）推導(dǎo)推導(dǎo)3： （1）( y)G(z, y) P （2）( y)( y)G(y, y) UG,(1)分析分析：推導(dǎo)：推導(dǎo)3是錯誤的。是錯誤的。正確的推導(dǎo)如下：正確的推導(dǎo)如下： （1）( y)G(z, y) P （2）( z)( y)G(z, y) UG,(1)注意：注意：使用使用UG規(guī)則規(guī)則來來添加添加量詞時，若選量詞時，若選用變元用變元x取代取代y，則要求，則要求在在原公式中原公式

25、中y不不能出現(xiàn)在量詞能出現(xiàn)在量詞( x)或或( x)的轄域之內(nèi)的轄域之內(nèi)。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-502022-6-1推理規(guī)則的正確使用（推理規(guī)則的正確使用（4 4）推導(dǎo)推導(dǎo)4： （1）G(x, c) P （2）( x)G(x, x) EG,(2)分析分析：推導(dǎo)：推導(dǎo)4是錯誤的。是錯誤的。正確的推導(dǎo)如下：正確的推導(dǎo)如下： （1）G(x, c) P （2）( y)G(x, y) EG,(2)注意：注意：使用使用EG規(guī)則規(guī)則來來添加添加量詞時，若選用量詞時，若選用變元變元x取代取代c，則要求，則要求在在原公式

26、中原公式中c不能出現(xiàn)不能出現(xiàn)在量詞在量詞( x)或或( x)的轄域之內(nèi)的轄域之內(nèi)且且原公式中原公式中中中無自由變量無自由變量x x。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-512022-6-1判斷判斷（1）( x)( y)G(x, y)P （2）( y)G(z, y)US,(1)（3）G(z, c)ES,(2)（4）( x)G(x, c) UG,(3)（5）( y) ( x)G(x, y) EG,(4)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-522

27、022-6-15.3.2 5.3.2 謂詞演算的綜合推理方法謂詞演算的綜合推理方法 推導(dǎo)過程中可以引用命題演算中的推導(dǎo)過程中可以引用命題演算中的規(guī)則規(guī)則P 和規(guī)和規(guī)則則T 。 如果如果結(jié)論結(jié)論是以蘊涵形式是以蘊涵形式(或或析取形式析取形式)給出，我們給出，我們還可以還可以使用規(guī)則使用規(guī)則CP。 若需若需消去量詞消去量詞，可以，可以引用規(guī)則引用規(guī)則US和規(guī)則和規(guī)則ES。 當(dāng)所要求的結(jié)論可能被當(dāng)所要求的結(jié)論可能被定量定量時，此時可時，此時可引用規(guī)引用規(guī)則則UG和規(guī)則和規(guī)則EG將其量詞加入將其量詞加入。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語

28、示范課程105-532022-6-1謂詞演算的綜合推理方法（續(xù)謂詞演算的綜合推理方法（續(xù)1 1） 證明時可采用如證明時可采用如命題演算命題演算中的中的直接證明方法和直接證明方法和間接證明方法間接證明方法。 在推導(dǎo)過程中，在推導(dǎo)過程中，對消去量詞的公式或公式中不對消去量詞的公式或公式中不含量詞的子公式含量詞的子公式，完全可以，完全可以引用命題演算中的引用命題演算中的基本等價公式和基本蘊涵公式基本等價公式和基本蘊涵公式。 在推導(dǎo)過程中，對在推導(dǎo)過程中，對含有量詞的公式含有量詞的公式可以可以引用謂引用謂詞中的基本等價公式和基本蘊涵公式詞中的基本等價公式和基本蘊涵公式。電子科技大學(xué)離散數(shù)學(xué)課程組電子科

29、技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-542022-6-1例例5.3.1 解：設(shè)解：設(shè)H(x)：x是人；是人；M(x)：x是要死的；是要死的； s：蘇格拉底。：蘇格拉底。 則符號化為：則符號化為： ( x)(H(x)M(x)，H(s) M(s)證明證明蘇格拉底三段論蘇格拉底三段論：“所有的人都是要死的；蘇所有的人都是要死的；蘇格拉底是人。所以蘇格拉底是要死的。格拉底是人。所以蘇格拉底是要死的。”證明：證明： (1) ( x)(H(x)M(x)P (2) H(x)M(x)US,(1) (3) H(s)P (4) M(s)T,(2),(3),I證明：證明

30、：(1)( x)(H(x)M(x)P (2)H(s)M(s)US,(1) (3)H(s)P (4)M(s)T,(2),(3),I(4)錯了！錯了！電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-552022-6-1例例5.3.2 5.3.2 證明：證明：( ( x)(P(x)x)(P(x)Q(x)Q(x)，( ( x)x)P(x)P(x)( ( x)x)Q(x)Q(x)有下面的推導(dǎo)有下面的推導(dǎo)： (1) (1) ( ( x)(P(x)x)(P(x)Q(x)Q(x) P P (2) P(x) (2) P(x)Q(x)Q(x) US

31、,(1) US,(1) (3) (3) ( ( x)x)P(x)P(x) P P (4) (4) P(c)P(c)ES,(3)ES,(3) (5) Q(c) (5) Q(c)T,(2),(4),IT,(2),(4),I (6) (6) ( ( x)x)Q(x)Q(x) EG,(5) EG,(5)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-562022-6-1例例5.3.25.3.2（) )推導(dǎo)可修改為推導(dǎo)可修改為：(1) (1) ( ( x)(P(x)x)(P(x)Q(x)Q(x)P P(2) P(c)(2) P(c)Q(c

32、)Q(c)US,(1)US,(1)(3) (3) ( ( x)x)P(x)P(x)P P(4) (4) P(c)P(c)ES,(3)ES,(3)(5) Q(c)(5) Q(c)T,(2),(4),IT,(2),(4),I(6) (6) ( ( x)x)Q(x)Q(x)EG,(5)EG,(5)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-572022-6-1例例5.3.25.3.2( () )請看推導(dǎo)請看推導(dǎo)：(1)(1) ( ( x)x)P(x)P(x)P P(2) (2) P(c)P(c)ES,(1)ES,(1)(3) (3

33、) ( ( x)(P(x)x)(P(x)Q(x)Q(x)P P(4) P(c)(4) P(c)Q(c)Q(c)US,(3)US,(3)(5) Q(c)(5) Q(c)T,(2),(4),IT,(2),(4),I(6) (6) ( ( x)x)Q(x)Q(x)EG,(5)EG,(5)正確！正確！電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-582022-6-1例例5.3.3 5.3.3 證明證明：1) (1) ( x x) )(P(x)(P(x)Q(x)Q(x)P P 2) P(c) 2) P(c)Q(c)Q(c) ES,1)

34、ES,1) 3) P(c) 3) P(c)T,2),IT,2),I 4) Q(c) 4) Q(c)T,2),IT,2),I 5) 5) ( ( x x) )P(x)P(x)EG,3)EG,3) 6) 6) ( ( x x) )Q(x)Q(x)EG,4)EG,4) 7) 7) ( ( x x) )P(x)P(x)( x x) )Q(x)Q(x)T,5),6),I T,5),6),I 證明：證明：( ( x x) )(P(x)(P(x)Q(x)Q(x)( ( x)x)P(x)P(x)( ( x)x)Q(x)Q(x)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙

35、語示范課程雙語示范課程105-592022-6-1例例5.3.3(5.3.3(續(xù)續(xù)1)1)1) (1) ( x x) )P(x)P(x)( x x) )Q(x)Q(x)P P2) 2) ( ( x x) )P(x)P(x)T,1),IT,1),I3) P(c)3) P(c)ES,2)ES,2)4) 4) ( ( x x) )Q(x)Q(x)T,1),IT,1),I5) Q(c)5) Q(c)ES,4)ES,4)6) P(c)6) P(c)Q(c)Q(c)T,3),4),IT,3),4),I7) 7) ( ( x x) )(P(x)(P(x)Q(x)Q(x)EG,6) EG,6) 請看上述推論的

36、逆推導(dǎo)請看上述推論的逆推導(dǎo)：電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-602022-6-1例例5.3.3(5.3.3(續(xù)續(xù)2)2)正確地推導(dǎo)正確地推導(dǎo)：1) (1) ( x x) )P(x)P(x)( x x) )Q(x)Q(x)P P2) 2) ( ( x x) )P(x)P(x)T,1),IT,1),I3) P(c)3) P(c)ES,2)ES,2)4) 4) ( ( x x) )Q(x)Q(x)T,1),IT,1),I5) Q(b)5) Q(b)ES,4)ES,4)6) P(c)6) P(c)Q(b)Q(b)T,3)

37、,4),IT,3),4),I7) 7) ( ( y y) )(P(c)(P(c)Q(y)Q(y)EG,6)EG,6)8) 8) ( ( x x)()( y y) )(P(x)(P(x)Q(y)Q(y)EG,7) EG,7) 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-612022-6-1例例5.3.4 5.3.4 證明證明( (采用反證法，采用反證法，CPCP規(guī)則的方法由學(xué)生完成規(guī)則的方法由學(xué)生完成) )：1 1) ) ( ( ( x)P(x)x)P(x)( ( x)x)Q(x)Q(x)P(P(附加附加) )2 2) ) (

38、 ( x)P(x)x)P(x) ( ( x)x)Q(x)Q(x)T,1),ET,1),E3) 3) ( ( x)P(x)x)P(x)T,2),IT,2),I4) 4) ( ( x)x)Q(x)Q(x)T,2),IT,2),I5) 5) ( ( x)x) P(x)P(x)T,3),ET,3),E6) 6) P(c)P(c) ES,5) ES,5)證明證明( ( x)(P(x)x)(P(x)Q(x) Q(x) ( ( x)P(x)x)P(x)( ( x)x)Q(x)Q(x)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-622022

39、-6-1例例5.3.4 5.3.4 7) (7) ( x)x) Q(x)Q(x) T,4),ET,4),E8) 8) Q(c)Q(c) US,7)US,7)9) 9) P(c)P(c) Q(c)Q(c) T,6),8),I T,6),8),I10) 10) (P(c)(P(c)Q(c)Q(c) T,9),E T,9),E11) (11) ( x)(P(x)x)(P(x)Q(x)Q(x) P P12) (P(c)12) (P(c)Q(c)Q(c) US,11) US,11)13) 13) (P(c)(P(c)Q(c)Q(c)(P(c)(P(c)Q(c) Q(c) T,10),12)T,10),1

40、2)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-632022-6-15.3.3 5.3.3 謂詞邏輯推理的難點謂詞邏輯推理的難點 在推導(dǎo)過程中，如在推導(dǎo)過程中，如既要使用規(guī)則既要使用規(guī)則USUS又要使用規(guī)則又要使用規(guī)則ESES消去公式中的量詞，而且選用的個體是同一個消去公式中的量詞，而且選用的個體是同一個符號，則必須符號，則必須先先使用規(guī)則先先使用規(guī)則ESES，再使用規(guī)則，再使用規(guī)則USUS。然后再使用命題演算中的推理規(guī)則，最后使用規(guī)然后再使用命題演算中的推理規(guī)則，最后使用規(guī)則則UGUG或規(guī)則或規(guī)則EGEG引入量詞，得到所要

41、的結(jié)論。引入量詞，得到所要的結(jié)論。 如一個變量是用如一個變量是用規(guī)則規(guī)則ESES消去量詞消去量詞，對該變量在添，對該變量在添加量詞時，則加量詞時，則只能使用規(guī)則只能使用規(guī)則EGEG，而不能使用規(guī)則，而不能使用規(guī)則UGUG；如使用；如使用規(guī)則規(guī)則USUS消去量詞消去量詞，對該變量在添加量，對該變量在添加量詞時，則詞時，則可使用規(guī)則可使用規(guī)則EGEG和規(guī)則和規(guī)則UGUG。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-642022-6-1謂詞邏輯推理的難點（續(xù)）謂詞邏輯推理的難點（續(xù)） 如有如有兩個含有存在量詞的公式兩個含有存在量詞

42、的公式，當(dāng)用，當(dāng)用規(guī)則規(guī)則ESES消去消去量詞量詞時，時，不能選用同樣的一個常量符號不能選用同樣的一個常量符號來取代兩來取代兩個公式中的變元，而應(yīng)用不同的常量符號來取代個公式中的變元，而應(yīng)用不同的常量符號來取代它們。它們。 在用在用規(guī)則規(guī)則US和和規(guī)則規(guī)則ES消去量詞消去量詞、用、用規(guī)則規(guī)則UG和和規(guī)規(guī)則則EG添加量詞添加量詞時，此量詞必須位于時，此量詞必須位于整個公式的整個公式的最前端，并且它的轄域為其后的整個公式最前端，并且它的轄域為其后的整個公式。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-652022-6-1謂詞邏輯

43、推理的難點（續(xù)）謂詞邏輯推理的難點（續(xù)） 在在添加量詞添加量詞( x)、( x)時，所選用的時，所選用的x不能在公不能在公式式G(y)或或G(c)中中自由出現(xiàn)自由出現(xiàn)且且G(y)或或G(c)對對x是是自自由由的。的。 在使用在使用規(guī)則規(guī)則EG引入存在量詞引入存在量詞( x)時，時，此此x不得不得僅為僅為G(c)或或G(y)中的函數(shù)變元中的函數(shù)變元。在使用。在使用規(guī)則規(guī)則UG引入全稱量詞引入全稱量詞( x)時，時，此此x不得為不得為G(y)中的函數(shù)中的函數(shù)變元變元(因該函數(shù)變元不得作為自由變元因該函數(shù)變元不得作為自由變元)。 在使用在使用規(guī)則規(guī)則UG引入全稱量詞引入全稱量詞( x)時，時，G(y

44、)中不中不得出現(xiàn)在使用得出現(xiàn)在使用規(guī)則規(guī)則US引入引入y之后由之后由規(guī)則規(guī)則ES引入引入的常量或函數(shù)。的常量或函數(shù)。電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-662022-6-15.3.4 5.3.4 謂詞邏輯推理的應(yīng)用謂詞邏輯推理的應(yīng)用例例5.3.5 每個喜歡步行的人都不喜歡坐汽車；每個每個喜歡步行的人都不喜歡坐汽車；每個人或者喜歡坐汽車或者喜歡騎自行車；有的人不喜人或者喜歡坐汽車或者喜歡騎自行車；有的人不喜歡騎自行車。因而有的人不喜歡步行。歡騎自行車。因而有的人不喜歡步行。 設(shè)：設(shè)：H(x)：x是人；是人； P(x)：

45、x喜歡坐汽車；喜歡坐汽車； Q(x)：x喜歡騎自行車；喜歡騎自行車； R(x)：x喜歡步行喜歡步行。則上述語句可符號化為：則上述語句可符號化為： ( x)(H(x)R(x) P(x)， ( x)(H(x)P(x)Q(x)， ( x)(H(x) Q(x) ( x)(H(x) R(x) 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-672022-6-1例例5.3.55.3.5證明證明 ( x)(H(x) Q(x)P H(c) Q(c)ES,(1) H(c)T,(2 ),I Q(c)T,(2 ),I ( x)( H(x)P(x)Q(

46、x)P H(c)P(c)Q(c)US,(5) P(c)Q(c)T,(3),(6),I P(c)T,(4),(7),I電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-682022-6-1例例5.3.55.3.5（續(xù)）（續(xù)） ( x)(H(x)R(x) P(x)P H(c)R(c) P(c)US,(9) (H(c)R(c)T,(8),(10),I H(c) R(c)T,(11),E R(c)T,(3),(12),I H(c) R(c)T,(3),(13),I ( x)(H(x) R(x)EG,(14) 電子科技大學(xué)離散數(shù)學(xué)課程組電子

47、科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-692022-6-1例例5.3.55.3.5每個喜歡步行的人都不喜歡坐汽車；每個人或者喜每個喜歡步行的人都不喜歡坐汽車；每個人或者喜歡坐汽車或者喜歡騎自行車；有的人不喜歡騎自行歡坐汽車或者喜歡騎自行車；有的人不喜歡騎自行車。因而有的人不喜歡步行。車。因而有的人不喜歡步行。 設(shè)：設(shè)：個體域個體域D人人； P(x)：人：人x喜歡坐汽車；喜歡坐汽車；Q(x)：人：人x喜歡騎自行車；喜歡騎自行車；R(x)：人：人x喜歡步行喜歡步行。則上述語句可符號化為：則上述語句可符號化為： ( x)(R(x) P(x)， ( x)(

48、P(x)Q(x)， ( x)( Q(x) ( x)( R(x) 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-702022-6-1證明證明(1) ( x)( Q(x)P(2) Q(c)ES,(1)(3) ( x)(P(x)Q(x)P(4) P(c)Q(c)US,(3)(5) P(c)T,(2),(4),I(6) ( x)(R(x) P(x)P(7) R(c) P(c)US,(6)(8) R(c)T,(5),(7),I(9) ( x) R(x)EG,(8) 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級

49、精品課程 雙語示范課程雙語示范課程105-712022-6-1例例5.3.6 5.3.6 ：證明下述論斷的正確性：證明下述論斷的正確性：所有的哺乳動物都是脊椎動物；并非所有的哺乳動所有的哺乳動物都是脊椎動物；并非所有的哺乳動物都是胎生動物；故有些脊椎動物不是胎生的。物都是胎生動物；故有些脊椎動物不是胎生的。解解：設(shè)謂詞如下：設(shè)謂詞如下：P(x)：x是哺乳動物；是哺乳動物；Q(x)：x是脊椎動物；是脊椎動物；R(x)：x是胎生動物。是胎生動物。則有則有： ( x)(P(x)Q(x)， ( x)(Q(x) R(x) ( x)(P(x)R(x)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家

50、級精品課程國家級精品課程 雙語示范課程雙語示范課程105-722022-6-1請看下面推導(dǎo)：請看下面推導(dǎo)：1) ( x)(P(x)R(x)P2) (P(x)R(x)US,1)3) ( P(x)R(x)T,2),E4) (P(x) R(x)T,3),E5) P(x)T,4),I 6) R(x)T,4),I7) ( x)(P(x)Q(x)P8) P(x)Q(x)US,7)9) Q(x)T,(5),(8),I 10) Q(x) R(x)T,6),9),I11) ( x)(Q(x) R(x)EG,10)12) ( x)(Q(x) R(x)UG,10)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組

51、國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-732022-6-1證明：證明：1) ( x)(P(x)R(x)P2) ( x) ( P(x)R(x)T,1),E3) ( P(c)R(c)ES,2)4) (P(c) R(c)T,3),E5) P(c)T,4),I 6) R(c)T,4),I7) ( x)(P(x)Q(x)P8) P(c)Q(c)US,7)9) Q(c)T,5),8),I 10) Q(c) R(c)T,6),9),I11) ( x)(Q(x) R(x)EG,10)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課

52、程105-742022-6-1例例5.3.7 5.3.7 證明下列論斷的正確性：證明下列論斷的正確性：有些學(xué)生相信所有的教師；任何一個學(xué)生都不相信有些學(xué)生相信所有的教師；任何一個學(xué)生都不相信騙子騙子；所以，教師都不是騙子。所以，教師都不是騙子。解解：設(shè)謂詞如下：設(shè)謂詞如下：S(x)：x是學(xué)生是學(xué)生T(x)：x是教師是教師P(x)：x是騙子是騙子L(x,y)：x相信相信y則可符號化為：則可符號化為：( x)(S(x)( y)(T(y)L(x,y),( x)( y)(S(x)P(y)L(x,y)( x)(T(x)P(x)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課

53、程 雙語示范課程雙語示范課程105-752022-6-1證明：證明：1) ( x)(S(x)( y)(T(y)L(x,y)P2) S(c)( y)(T(y)L(c,y)ES,1)3) S(c)T,2),I4) ( y)(T(y)L(c,y)T,2),I5) T(x)L(c,x)US,4)6) ( x)( y)(S(x)P(y)L(x,y)P7) ( y)(S(c)P(y)L(c,y)US,6)8) (S(c)P(x)L(c,x)US,7)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-762022-6-1證明：證明：9) S(c

54、)(P(x)L(c,x) T,8),E10) P(x)L(c,x)T,3),8),E11) L(c,x)P(x)T,10),E12) T(x)P(x)T,5),11),E13) ( x)(T(x)P(x) US,12)電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-772022-6-1例例5.3.85.3.8 現(xiàn)有一智力測驗題目現(xiàn)有一智力測驗題目(水容器問題水容器問題)：設(shè)有兩個：設(shè)有兩個分別能盛分別能盛7升與升與5升的水容器，開始時兩個容器均升的水容器，開始時兩個容器均空，允許對容器做三種操作：空，允許對容器做三種操作： （1

55、）容器倒?jié)M水，）容器倒?jié)M水， （2）將容器中的水倒光，）將容器中的水倒光， （3）從一個容器倒水至另一容器，使一個容）從一個容器倒水至另一容器，使一個容器倒光而另一容器倒?jié)M。器倒光而另一容器倒?jié)M。 最后要求能使大容器最后要求能使大容器(能盛能盛7升的容器升的容器)中有中有4升升水，并求其操作過程。水，并求其操作過程。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-782022-6-1大容器大容器注滿注滿小容器小容器倒空倒空解決方案解決方案S(0,0)S(0,0)S(7,0)S(7,0)S(2,5)S(2,5)S(2,0)S(2

56、,0)S(0,2)S(0,2)S(7,2)S(7,2)S(4,5)S(4,5)S(4,0)S(4,0)大容器大容器注滿注滿大容器大容器倒空倒空小容器小容器注滿注滿小容器小容器注滿注滿倒入倒入小容器小容器電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-792022-6-1證明證明（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

57、(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é)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-802022-6-1證明證明（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

58、）( 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é)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-812022-6-1證明（續(xù)）證明（續(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,

59、(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é)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-822022-6-1證明（續(xù)）證明（續(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

60、) 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é)課程組電子科技大學(xué)離散數(shù)學(xué)課程組國家級精品課程國家級精品課程 雙語示范課程雙語示范課程105-832022-6-15.4 5.4 數(shù)學(xué)歸納法數(shù)學(xué)歸納法 5.4.1 數(shù)學(xué)歸納法原理數(shù)學(xué)歸納法原理假設(shè)要證明的命題能寫成形式假設(shè)要證明的命題能寫成形式: nn0，有，有P(n) 其中其中n0是某個固定的整數(shù)，是某個固定的整數(shù)，即：希望證明對所有的整數(shù)即：希望證明對所有的整數(shù)nn0都有都有P(n)為真。為真。 電子科技大學(xué)離散數(shù)學(xué)課程組電子科技大學(xué)離