數(shù)理邏輯與集合論：2-3 命題邏輯的等值和推理演算

1、第2章 命題邏輯的等值和推理演算 2.1 等值定理2.2 等值公式2.3 命題公式與真值表的關(guān)系2.4 聯(lián)結(jié)詞的完備集2.5 對偶式2.6 范式2.7 推理形式2.8 基本的推理公式2.9 推理演算2.10 歸結(jié)推理法討論討論等值演算等值演算討論討論推理演算推理演算主析取范式的用途如如 PQ = P Q = m0 x mx1 = m00 m01 m01 m11 = m0 m1 m3 = (0,1,3) P (P Q) = m0 x m11 = m00 m01 m11 = m0 m1 m3 = (0,1,3)所以所以 PQ = P (P Q)定理定理 任何命題公式都存任何命題公式都存在與之等值的

2、主析取范在與之等值的主析取范式式, , 并且是惟一的并且是惟一的. .(1)(1)求公式的成真賦值和成假賦值求公式的成真賦值和成假賦值(2)(2)判斷公式的類型判斷公式的類型(3)(3)判斷判斷兩個公式是否等值兩個公式是否等值主析取范式的應(yīng)用(4)舉例例：甲、乙、丙、丁四人參例：甲、乙、丙、丁四人參加考試，有人問他們，誰加考試，有人問他們，誰的成績最好，的成績最好， 甲說：甲說：“不是我不是我” 乙說：乙說：“是丁是丁” 丙說：丙說：“是乙是乙” 丁說：丁說：“不是我不是我” 四人的回答只有一人符合四人的回答只有一人符合實際，實際，問是誰的成績最好，問是誰的成績最好，若只有一人成績最好，他若只

3、有一人成績最好，他是誰？是誰？解此類問題的步驟為：解此類問題的步驟為： 將簡單命題符號化將簡單命題符號化 寫出各復(fù)合命題寫出各復(fù)合命題 寫出由中復(fù)合命題組寫出由中復(fù)合命題組成的合取式成的合取式 求中所得公式的主析求中所得公式的主析取范式取范式主析取范式的應(yīng)用舉例解解 設(shè)設(shè)A：甲的成績最好：甲的成績最好 B：乙的成績最好，：乙的成績最好， C：丙的成績最好：丙的成績最好 D：丁的成績最好，：丁的成績最好， (1) ( A D B D) (2) ( A D B D) (3) ( A D B D) (4) ( A D B D)例：甲、乙、丙、丁四人參例：甲、乙、丙、丁四人參加考試，有人問他們，誰加考

4、試，有人問他們，誰的成績最好，的成績最好， 甲說：甲說：“不是我不是我” 乙說：乙說：“是丁是丁” 丙說：丙說：“是乙是乙” 丁說：丁說：“不是我不是我” 四人的回答只有一人符合四人的回答只有一人符合實際實際，問是誰的成績最好，問是誰的成績最好，若只有一人成績最好，他若只有一人成績最好，他是誰？是誰？主析取范式的應(yīng)用舉例 (1) ( A D B D) (2) ( A D B D) (3) ( A D B D) (4) ( A D B D) (1) (4)構(gòu)成的析取式為構(gòu)成的析取式為 ( A D B D) (A D B D) ( A D B D) (A D B D)主析取范式的應(yīng)用舉例 求求中所

5、得公式的主析取范式中所得公式的主析取范式 ( A D B D) (A D B D) ( A D B D) (A D B D)= (A D B D) (A D B D) = (A B D) (A B D)= m10 x1 m10 x0= m1001 m1011 m1000 m1010 所以，只有一人成所以，只有一人成績最好的是績最好的是甲。甲。甲、丁并列甲、丁并列成績最好成績最好甲、丙、丁并列甲、丙、丁并列成績最好成績最好甲、丙并列甲、丙并列成績最好成績最好極大項n 定義 n n個命題變項的個命題變項的簡單析取式簡單析取式，其中每個命題變項與其否，其中每個命題變項與其否定不同時出現(xiàn)，而二者之一必

6、出現(xiàn)且僅出現(xiàn)一次，這樣定不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，這樣的的簡單析取式簡單析取式稱為稱為極大項極大項。n如：兩個命題變元如：兩個命題變元P和和Q，其極大項為：，其極大項為： P Q， P Q ， P Q ， P Qn 說明nn個命題變項產(chǎn)生個命題變項產(chǎn)生2n個極大項，它們互不等值個極大項，它們互不等值,n用用Mi表示第表示第i個極大項，每個小項的個極大項，每個小項的n個變元排序相同。個變元排序相同。（按下標或字典順序），分別記為（按下標或字典順序），分別記為n其中其中: 正變元：正變元：1，變元的否定：，變元的否定：0 M11 M10 M01 M00 1210, nMMM 由P,

7、 Q, R三個命題變項形成的極小項與極大項 極小項極小項 極大項極大項 公式公式 名稱名稱 公式公式 名稱名稱 P Q R P Q R P Q R P Q R P Q RP Q RP Q RP Q Rm0m1m2m3m4m5m6m7 P Q R P Q R P Q R P Q R P Q R P Q R P Q RP Q R M0M1M2M3M4M5M6M7 主合取范式n主合取范式n由極大項構(gòu)成的合取范式由極大項構(gòu)成的合取范式n如如n=3, 命題變項為命題變項為P, Q, R時，主合取范式時，主合取范式: (P QR) ( P QR) = M6 M2 n定理定理n任何命題公式都存在與之等值的主

8、合取范式任何命題公式都存在與之等值的主合取范式, 并且是惟并且是惟一的一的. . n求主合取范式的方法求主合取范式的方法n等值演算法和真值表法（按等值演算法和真值表法（按F列出）列出）1. 求求A的合取范式的合取范式A ； 2. 若若A 的某簡單析取式的某簡單析取式B中不含某命題變項或其否定中不含某命題變項或其否定，則將，則將B展成如下形式：展成如下形式： B = B F = B (Pi Pi ) = (B Pi) (B Pi)3. 將重復(fù)出現(xiàn)的命題變項、重言式及重復(fù)出現(xiàn)的極大項將重復(fù)出現(xiàn)的命題變項、重言式及重復(fù)出現(xiàn)的極大項都都“消去消去”。 4. 將極大項按由小到大的順序排列，并用將極大項按

9、由小到大的順序排列，并用 表示之，表示之，如如 M1 M2 M6 用用 (1,2,6) 表示。表示。用等值演算法求主合取范式的步驟求公式(PQ)R 的主合取范式解解1: ： (PQ)R = ( P Q) R = (P Q) R = (P R) (Q R) （合取范式）（合取范式） P R = (P R) (Q Q ) = (P Q R) ( P Q R) = M111 M101 = M7 M5 Q R =(Q R) (P P ) = (P Q R) ( P Q R) = M111 M011 = M7 M3 , 代入并排序，得主合取范式：代入并排序，得主合取范式： (PQ)R = M3 M5 M

10、7 = (3,5,7)解解2: (PQ)R = (P R) (Q R) (合取合取范式范式) = M1x1 Mx11 = M101 M111 M011 M111 = M3 M5 M7 = (3,5,7)求公式(PQ)R 的主合取范式 （析取范式）（析取范式） (PQ)R= (P Q) R = (1,3,5,6,7)u 主析取范式主析取范式與與主合取范式主合取范式的轉(zhuǎn)換的轉(zhuǎn)換 (1,3,5,6,7) = (0,1,2,3,4,5,6,7) (1,3,5,6,7)補補 = (0,2,4)補補= (7- 0,7- 2,7- 4) = (7,5,3)用真值表法求公式(PQ)R 的主析取、主合取范式 P

11、 Q R PQ (PQ)R F F FF F TF T FF T TT F FT F TT T F T T T TTTTTTF FFTFTFTTT (PQ)R = m1 m3 m5 m6 m7= (1,3,5,6,7) (PQ)R = M3 M5 M7 = (3,5,7)2.7 推理形式n 推理引例: (1) 正項級數(shù)收斂當且僅當部分和有上界正項級數(shù)收斂當且僅當部分和有上界. (2) 若若A C B D，則，則A B且且C D.n 數(shù)理邏輯的主要任務(wù)是用邏輯的方法研究數(shù)學(xué)中的推理。n 推理從前提出發(fā)，應(yīng)用推理規(guī)則推出結(jié)論的從前提出發(fā)，應(yīng)用推理規(guī)則推出結(jié)論的思維過程思維過程n上面上面(1)是正確

12、的推理，而是正確的推理，而(2)是錯誤的推理是錯誤的推理. n 推理的組成n前提前提推理所根據(jù)的已知命題推理所根據(jù)的已知命題n結(jié)論結(jié)論從前提出發(fā)通過推理而得到的新命題從前提出發(fā)通過推理而得到的新命題n 證明 描述推理正確或錯誤的過程描述推理正確或錯誤的過程. . 推理形式n 例：如果我有時間，我就去上街；如果我有時間，我就去上街； 如果我上街，我就去書店買書；如果我上街，我就去書店買書； 但我沒有去書店買書，但我沒有去書店買書， 所以我沒有時間。所以我沒有時間。n 解：令 P：我有時間。 Q：我去上街。 R：我去書店買書。 根據(jù)題意，前提為：PQ，QR，R 結(jié)論為：P 推理的形式為： (PQ)

13、(QR)R P 反映了一類推理關(guān)系反映了一類推理關(guān)系重言蘊涵n 定義定義n 若若 (A1 A2 Ak ) B為為重言式重言式， 則稱則稱由由 A1, A2, , Ak推出結(jié)論推出結(jié)論B的的推理正確（有推理正確（有效結(jié)論）效結(jié)論） , 否則否則推理不正確（錯誤）推理不正確（錯誤）.n “A1, A2, , Ak 推出B” 的推理正確 當且僅當 A1 A2 AkB為重言式.n 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): A1 A2 AkB 或或 前提：前提： A1, A2, , Ak 結(jié)論：結(jié)論： B n 若推理正確，則記作：若推理正確，則記作：A1 A2 Ak B例：判斷下面推理是否正確?（1）若天氣涼快，

14、小王就不去游泳。天氣涼快，所以小王沒去游泳。解題方法將命題符號化將命題符號化寫出前提、結(jié)論和推理的形式結(jié)構(gòu)寫出前提、結(jié)論和推理的形式結(jié)構(gòu)進行判斷進行判斷解： 設(shè) P：天氣涼快，Q：小王去游泳. 前提： P Q，P 結(jié)論： Q 推理的形式結(jié)構(gòu)為： (PQ) P) Q 判斷上式是否為重言式 。例：判斷下面推理是否正確（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒去游泳。判斷 (PQ) P) Q 是否為重言式 方法1：真值表法PQP Q(P Q) P(P Q) P) QFFTFTFTTFTTFTTTTTFFT( (PQ)P) ) Q例：判斷下面推理是否正確（1）若天氣涼快，小王就不去游泳。天

15、氣涼快，所以小王沒去游泳。判斷 (PQ) P) Q 是否為重言式 方法2：等值演算法 (PQ) P) Q = ( PQ) P)Q = = (P Q) P Q = = (P Q) (P Q) = = T( (PQ)P) ) Q例：判斷下面推理是否正確（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒去游泳。判斷 (PQ) P) Q是否為重言式 方法3：主析取范式法 (PQ) P) Q = ( PQ) P)Q = (P Q) P Q = m11 m0 x mx0 = m11 m00 m01 m00 m10 = (0,1,2,3) = T例：判斷下面推理是否正確?（2）若我上街，我一定去書店。我

16、沒上街，所以我沒去書店。解： 設(shè) P：我上街，Q：我去書店。 前提： PQ， P 結(jié)論： Q 推理的形式結(jié)構(gòu)為： (PQ)P) Q 判斷上式是否為重言式 (PQ) P) Q = ( P Q) P) Q = (P Q) P Q = m10 m1x mx0 = m10 m10 m11 m00 m10 = (0,2,3)不是重言式！不是重言式！所以推理不正確所以推理不正確重言蘊涵的幾個結(jié)果n如果如果A B，A為重言式，則為重言式，則B也是重言式也是重言式n如果如果A B， B A同時成立，必有同時成立，必有A=Bn反之反之，如果，如果A=B，必有，必有A B，B An如果如果A B， B C，則，則

17、A Cn如果如果A B， A C，則，則A B Cn如果如果A C， B C，則，則A B C2.8 基本的推理公式n判斷推理是否正確的方法n真值表法、等值演算法、主析取范式法真值表法、等值演算法、主析取范式法n推理演算法推理演算法一個描述推理過程的命題公式一個描述推理過程的命題公式序列序列n其中的每個命題公式是已知的其中的每個命題公式是已知的前提前提、或是由某些前、或是由某些前提依據(jù)提依據(jù)等值公式等值公式或或蘊涵關(guān)系式蘊涵關(guān)系式、應(yīng)用、應(yīng)用推理規(guī)則推理規(guī)則得到得到的結(jié)論的結(jié)論 n說明：說明：n當命題變項比較少時，用上面當命題變項比較少時，用上面3 3種方法比較方便種方法比較方便, , 此時此

18、時采用采用形式結(jié)構(gòu)形式結(jié)構(gòu)“A1 A2 AkB” . n而在推理演算時，而在推理演算時，采用下面形式：采用下面形式： 前提前提: A1, A2, , Ak 結(jié)論結(jié)論: B基本的推理公式1. P Q P 化簡律化簡律2. 2. (PQ) P3. 3. (PQ) Q4. P P Q 附加律附加律 5. 5. P PQ6. Q PQ7. P (P Q) Q 析取三段論析取三段論8. P (P Q) Q 假言推理假言推理9. 9. Q (PQ) P 拒取式拒取式10.(PQ) (QR) PR 假言三段論假言三段論基本的推理公式11.(PQ) (QR) P R 等價三段論等價三段論12. (PR) (Q

19、R) ( (P Q) R 13. 13. (PQ) (RS) (P R) Q S 構(gòu)造性二難構(gòu)造性二難14. (PQ) (RS) ( QS) ( PR) 破壞性二難破壞性二難15. (QR) (P Q) (P R) 16. (QR) (PQ) (PR) 證明推理公式的方法n定理2.8.1 AB成立的充分必要條件是成立的充分必要條件是 AB 是重言式。是重言式。n定理2.8.2 AB成立的充分必要條件是成立的充分必要條件是 A B 是矛盾式是矛盾式。n(AB)=( ( A B)= A B n說明：n可用可用AB是重言式是重言式或或A B 是矛盾式是矛盾式來來證明推理公式證明推理公式AB2.9 推

20、理演算推理規(guī)則 (1) 前提引入規(guī)則前提引入規(guī)則(2) 結(jié)論引入規(guī)則結(jié)論引入規(guī)則(3) 代入規(guī)則代入規(guī)則(4) 置換規(guī)則置換規(guī)則(5)假言推理假言推理(分離規(guī)則分離規(guī)則) PQ P Q(6) 附加規(guī)則附加規(guī)則 P P Q (7) 化簡規(guī)則化簡規(guī)則 P Q P (8) 拒取式規(guī)則拒取式規(guī)則 PQ Q P(9) 假言三段論規(guī)則假言三段論規(guī)則 PQ QR PR 推理規(guī)則(續(xù)) (12) 破壞性二難推理規(guī)則破壞性二難推理規(guī)則 PQ RS QS PR(13) 合取引入規(guī)則合取引入規(guī)則 P Q P Q (10) 析取三段論規(guī)則析取三段論規(guī)則 P Q Q P (11)構(gòu)造性二難推理規(guī)則構(gòu)造性二難推理規(guī)則 P

21、Q RS P R Q S使用推理規(guī)則的推理演算舉例例1：證明：前提：前提：P Q, Q R, P 結(jié)論：結(jié)論：R 證： P 前提引入前提引入 P Q 前提引入前提引入 Q 分離（假言推理）分離（假言推理） Q R 前提引入前提引入 R 分離（假言推理）分離（假言推理） 推理演算直接證明法例2 證明：前提：前提： P Q， P R, Q S 結(jié)論：結(jié)論：S R證明：證明： P Q 前提引入前提引入 P Q 置換置換 Q S 前提引入前提引入 P S 假言三段論假言三段論 S P 置換置換 P R 前提引入前提引入 S R 假言三段論假言三段論 S R 置換置換( (PQ)()(RS)()(P R) ) Q S 構(gòu)造性二難構(gòu)造性二難 在大城市球賽中，在大城市球賽