1、第2章 命題邏輯的等值和推理演算,2.1 等值定理 2.2 等值公式 2.3 命題公式與真值表的關(guān)系 2.4 聯(lián)結(jié)詞的完備集 2.5 對(duì)偶式 2.6 范式 2.7 推理形式 2.8 基本的推理公式 2.9 推理演算 2.10 歸結(jié)推理法,討論等值演算,討論推理演算,極大項(xiàng),定義 n個(gè)命題變項(xiàng)的簡(jiǎn)單析取式，其中每個(gè)命題變項(xiàng)與其否定不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，這樣的簡(jiǎn)單析取式稱為極大項(xiàng)。 如：兩個(gè)命題變?cè)狿和Q，其極大項(xiàng)為： P Q， P Q ， P Q ， P Q 說明 n個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極大項(xiàng)，它們互不等值 用Mi表示第i個(gè)極大項(xiàng)，每個(gè)小項(xiàng)的n個(gè)變?cè)判蛳嗤＃ò聪聵?biāo)或字典順

2、序），分別記為 其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示的補(bǔ). （正變項(xiàng)：0，變?cè)姆穸ǎ?）,M11 M10 M01 M00,由P, Q, R三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng),主合取范式,主合取范式 由極大項(xiàng)構(gòu)成的合取范式 如n=3, 命題變項(xiàng)為P, Q, R時(shí)，主合取范式: (PQR)(PQR) = M6M2 定理 任何命題公式都存在與之等值的主合取范式, 并且是惟一的. 求主合取范式的方法 等值演算法和真值表法,1. 求A的合取范式A ； 2. 若A 的某簡(jiǎn)單析取式B中不含某命題變項(xiàng)或其否定，則將B展成如下形式： B = B 0 = B (Pi Pi ) = (B Pi) (B Pi) 3.

3、 將重復(fù)出現(xiàn)的命題變項(xiàng)、重言式及重復(fù)出現(xiàn)的極大項(xiàng)都“消去”。 4. 將極大項(xiàng)按由小到大的順序排列，并用 表示之，如 M1 M2 M6 用 (1,2,6) 表示。,用等價(jià)演算法求主合取范式的步驟,求公式(PQ)R 的主合取范式,解1: ： (PQ)R = ( P Q) R = (PQ) R = (PQ) (QR) PR = (PR) (Q Q ) =(PRQ) ( P Q R) =M111 M101 QR =(QR) (P P ) =(PQ R) ( P Q R) =M111 M011 , 代入并排序，得主合取范式： =M3 M5 M7 = (3,5,7),解2: (PQ)R = ( P Q)

4、R = (PQ) R = (PR)(QR) (合取范式) = M1x1 Mx11 = M101 M111 M011 M111 = M3 M5 M7 = (3,5,7),求公式(PQ)R 的主合取范式,= (PQ)R （析取范式） = m11x mxx1 = (m110 m111)( m001 m011 m101 m111) = (1,3,5,6,7),主析取范式與主合取范式的轉(zhuǎn)換 (1,3,5,6,7) = (07)-(1,3,5,6,7)補(bǔ) = (0,2,4)補(bǔ) = (3,5,7),2.7 推理形式,推理引例: (1) 正項(xiàng)級(jí)數(shù)收斂當(dāng)且僅當(dāng)部分和有上界. (2) 若ACBD，則AB且CD.

5、數(shù)理邏輯的主要任務(wù)是用邏輯的方法研究數(shù)學(xué)中的推理。 推理從前提出發(fā)，應(yīng)用推理規(guī)則推出結(jié)論的思維過程 上面(1)是正確的推理，而(2)是錯(cuò)誤的推理. 推理的組成 前提推理所根據(jù)的已知命題 結(jié)論從前提出發(fā)通過推理而得到的新命題 證明 描述推理正確或錯(cuò)誤的過程.,推理形式,例：如果我有時(shí)間，那么我就去上街； 如果我上街，那么我就去書店買書； 但我沒有去書店買書， 所以我沒有時(shí)間。 解：令 P：我有時(shí)間。 Q：我去上街。 R： 我去書店買書。 根據(jù)題意，前提為：PQ，QR，R 結(jié)論為：P 推理的形式為： (PQ)(QR)R P,反映了一類推理關(guān)系,重言蘊(yùn)涵,定義 若（A1A2 Ak）B為重言式，則稱

6、由A1,A2, Ak推出結(jié)論B的推理正確（有效結(jié)論） 否則推理不正確（錯(cuò)誤）. “A1, A2, , Ak 推出B” 的推理正確 當(dāng)且僅當(dāng) A1A2AkB為重言式. 推理的形式結(jié)構(gòu) A1A2AkB 或 前提： A1, A2, , Ak 結(jié)論： B 若推理正確，則記作：A1A2Ak B,例：判斷下面推理是否正確,（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒去游泳。 解題方法 將命題符號(hào)化 寫出前提、結(jié)論和推理的形式結(jié)構(gòu) 進(jìn)行判斷 解： 設(shè) P：天氣涼快，Q：小王去游泳. 前提： PQ，P 結(jié)論： Q 推理的形式結(jié)構(gòu)為： (PQ)P) Q 判斷上式是否為重言式,例：判斷下面推理是否正確,

7、（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒去游泳。 判斷 (PQ)P) Q 是否為重言式 方法1：真值表法,(PQ)P) Q,例：判斷下面推理是否正確,（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒去游泳。 判斷 (PQ)P) Q 是否為重言式 方法2：等值演算法 (PQ)P) Q = (PQ)P)Q = (PQ) P Q = (PQ) (PQ) = T,(PQ)P) Q,例：判斷下面推理是否正確,（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒去游泳。 判斷 (PQ)P) Q是否為重言式 方法3：主析取范式法 (PQ)P) Q = (PQ)P)Q = (PQ) P

8、Q = m11m0 xmx0 = m11m00m01m00m10 = (0,1,2,3) = T,(PQ)P) Q,例：判斷下面推理是否正確,（2）若我上街，我一定去新華書店。我沒上街，所以我沒去新華書店。 解： 設(shè) P：我上街，Q：我去新華書店. 前提： PQ，P 結(jié)論： Q 推理的形式結(jié)構(gòu)為： (PQ)P) Q 判斷上式是否為重言式 (PQ) P) Q = (P Q) P) Q = (P Q) P Q = m10m1xmx0 = m10m10m11m00m10 = (0,2,3),不是重言式！ 所以推理不正確,重言蘊(yùn)涵的幾個(gè)結(jié)果,如果A B，A為重言式，則B也是重言式 如果A B， B A

9、同時(shí)成立，必有A=B 反之，如果A=B，必有A B，B A 如果A B， B C，則A C 如果A B， A C，則A BC 如果A C， B C，則AB C,2.8 基本的推理公式,判斷推理是否正確的方法 真值表法、等值演算法、主析取范式法 推理演算法一個(gè)描述推理過程的命題公式序列 其中的每個(gè)命題公式是已知的前提、或是由某些前提依據(jù)等值公式或蘊(yùn)涵關(guān)系式、應(yīng)用推理規(guī)則得到的結(jié)論 說明： 當(dāng)命題變項(xiàng)比較少時(shí)，用前3個(gè)方法比較方便, 此時(shí)采用形式結(jié)構(gòu)“ A1A2AkB” . 而在推理演算時(shí)，采用下面形式： 前提: A1, A2, , Ak, 結(jié)論: B,基本的推理公式,PQ P 化簡(jiǎn)律 (PQ)

10、P (PQ) Q P PQ 附加律 P PQ Q PQ P (P Q) Q 析取三段論 P (PQ) Q 假言推理 Q (PQ) P 拒取式,基本的推理公式,10. (PQ)(QR) PR 假言三段論 11.(PQ)(QR) P R 等價(jià)三段論 12. (PR)(QR) (PQ) R 13. (PQ)(RS)(PR) QS 構(gòu)造性二難 14. (PQ)(RS)( QS) (PR) 破壞性二難 15. (QR) (PQ) (PR) 16. (QR) (PQ) (PR),證明推理公式的方法,定理2.8.1 AB成立的充分必要條件是 AB 是重言式。 定理2.8.2 AB成立的充分必要條件是 A B

11、 是矛盾式。 (AB)=( AB)= A B 說明： 可用AB 是重言式或A B 是矛盾式來證明推理公式AB,2.9 推理演算推理規(guī)則,推理規(guī)則(續(xù)),使用推理規(guī)則的推理演算舉例,例1：證明： 前提：P Q, Q R, P 結(jié)論：R 證： (1) P 前提引入 (2) P Q 前提引入 (3) Q (1)(2)分離（假言推理） (4) Q R 前提引入 (5) R (3)(4)分離（假言推理）,推理演算直接證明法,例2 證明： 前提： P Q， P R, Q S 結(jié)論：S R 證明：(1) P Q 前提引入 (2) P Q (1)置換 (3) Q S 前提引入 (4) P S (2)(3)假言

12、三段論 (5) S P (4)置換 (6) P R 前提引入 (7) S R (5)(6)假言三段論 (8) S R (7)置換,(PQ)(RS)(PR) QS 構(gòu)造性二難,在大城市球賽中，如果北京隊(duì)第三，那么如果上海隊(duì)第二，則天津隊(duì)第四；沈陽隊(duì)不是第一或北京隊(duì)第三，上海隊(duì)第二。從而知：如果沈陽隊(duì)第一，那么天津隊(duì)第四。 解：設(shè) P：北京隊(duì)第三 Q：上海隊(duì)第二 R：天津隊(duì)第四 S：沈陽隊(duì)第一 前提： P(QR)，SP, Q 結(jié)論： S R,寫出對(duì)應(yīng)下面推理的證明,(1) P (Q R) 前提 (2) Q (P R) (1)置換 (3) Q 前提 (4) P R (2)(3)假言推理 (5) SP

13、 前提 (6) S P (5)置換 (7) S R (6)(4) 析取三段論,推理演算附加前提證明法,欲證明 前提：A1, A2, , Ak 結(jié)論：CB 等價(jià)地證明 前提：A1, A2, , Ak, C 結(jié)論：B 理由： (A1A2Ak)(CB) = ( A1A2Ak)(CB) = ( A1A2Ak)C) B = ( A1A2AkC)B = (A1A2AkC)B,例如：證明下列推理。 前提： P(QR)，SP, Q 結(jié)論： S R 證明：(1) S P 前提 (2) S 附加前提引入 (3) P (1)(2) 析取三段論 (4) P (Q R) 前提 (5) Q R (3)(4) 假言推理 (

14、6) Q 前提 (7) R (5)(6) 假言推理,附加前提證明法 舉例,2.10 歸結(jié)推理法（反證法）,欲證明 前提：A1, A2, , Ak 結(jié)論：B 將B加入前提，若推出矛盾，則得證推理正確. 理由: A1A2AkB = (A1A2Ak)B = (A1A2Ak) (B) = (A1A2AkB) 括號(hào)內(nèi)部為矛盾式當(dāng)且僅當(dāng) (A1A2AkB )為 重言式,證明AB是重言式的歸結(jié)證明過程,建立子句集S 將AB化成合取范式，如 P (PR) (PQ) (PR) 的形式，進(jìn)而將所有句子構(gòu)成子句集合： S=P，(PR)，(PR)， (PR) 對(duì)S作歸結(jié) 對(duì)S的子句消去互補(bǔ)對(duì)： 子句：PR，PQ 作歸結(jié)，得 歸結(jié)式：RQ 并將此歸結(jié)式仍放入S中，重復(fù)此過程 直至歸結(jié)出矛盾式，證明結(jié)束,歸結(jié)推理法 舉例,例 構(gòu)造下面推理的證明 前提：(PQ)R, RS, S, P 結(jié)論：Q 證明： Q 結(jié)論否定引入 RS 前提引入 RS 置換 S 前提引入 R 歸結(jié) (PQ)R 前提引入 (PQ) 歸結(jié) PQ 置換 P 歸結(jié) P 前提引入