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

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é)推理法討論討論等值演算等值演算討論討論推理演算推理演算主析取范式的用途如如 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)判斷判斷兩個(gè)公式是否等值兩個(gè)公式是否等值主析取范式的應(yīng)用(4)舉例例：甲、乙、丙、丁四人參例：甲、乙、丙、丁四人參加考試，有人問(wèn)他們，誰(shuí)加考試，有人問(wèn)他們，誰(shuí)的成績(jī)最好，的成績(jī)最好， 甲說(shuō)：甲說(shuō)：“不是我不是我” 乙說(shuō)：乙說(shuō)：“是丁是丁” 丙說(shuō)：丙說(shuō)：“是乙是乙” 丁說(shuō)：丁說(shuō)：“不是我不是我” 四人的回答只有一人符合四人的回答只有一人符合實(shí)際，實(shí)際，問(wèn)是誰(shuí)的成績(jī)最好，問(wèn)是誰(shuí)的成績(jī)最好，若只有一人成績(jī)最好，他若只

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

4、試，有人問(wèn)他們，誰(shuí)的成績(jī)最好，的成績(jī)最好， 甲說(shuō)：甲說(shuō)：“不是我不是我” 乙說(shuō)：乙說(shuō)：“是丁是丁” 丙說(shuō)：丙說(shuō)：“是乙是乙” 丁說(shuō)：丁說(shuō)：“不是我不是我” 四人的回答只有一人符合四人的回答只有一人符合實(shí)際實(shí)際，問(wèn)是誰(shuí)的成績(jī)最好，問(wèn)是誰(shuí)的成績(jī)最好，若只有一人成績(jī)最好，他若只有一人成績(jī)最好，他是誰(shuí)？是誰(shuí)？主析取范式的應(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 所以，只有一人成所以，只有一人成績(jī)最好的是績(jī)最好的是甲。甲。甲、丁并列甲、丁并列成績(jī)最好成績(jī)最好甲、丙、丁并列甲、丙、丁并列成績(jī)最好成績(jī)最好甲、丙并列甲、丙并列成績(jī)最好成績(jī)最好極大項(xiàng)n 定義 n n個(gè)命題變項(xiàng)的個(gè)命題變項(xiàng)的簡(jiǎn)單析取式簡(jiǎn)單析取式，其中每個(gè)命題變項(xiàng)與其否，其中每個(gè)命題變項(xiàng)與其否定不同時(shí)出現(xiàn)，而二者之一必

6、出現(xiàn)且僅出現(xiàn)一次，這樣定不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，這樣的的簡(jiǎn)單析取式簡(jiǎn)單析取式稱為稱為極大項(xiàng)極大項(xiàng)。n如：兩個(gè)命題變?cè)纾簝蓚€(gè)命題變?cè)狿和和Q，其極大項(xiàng)為：，其極大項(xiàng)為： P Q， P Q ， P Q ， P Qn 說(shuō)明nn個(gè)命題變項(xiàng)產(chǎn)生個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極大項(xiàng)，它們互不等值個(gè)極大項(xiàng)，它們互不等值,n用用Mi表示第表示第i個(gè)極大項(xiàng)，每個(gè)小項(xiàng)的個(gè)極大項(xiàng)，每個(gè)小項(xiàng)的n個(gè)變?cè)判蛳嗤?。個(gè)變?cè)判蛳嗤＃ò聪聵?biāo)或字典順序），分別記為（按下標(biāo)或字典順序），分別記為n其中其中: 正變?cè)赫冊(cè)?，變?cè)姆穸ǎ?，變?cè)姆穸ǎ? M11 M10 M01 M00 1210, nMMM 由P,

7、 Q, R三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng) 極小項(xiàng)極小項(xiàng) 極大項(xiàng)極大項(xiàng) 公式公式 名稱名稱 公式公式 名稱名稱 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由極大項(xiàng)構(gòu)成的合取范式由極大項(xiàng)構(gòu)成的合取范式n如如n=3, 命題變項(xiàng)為命題變項(xiàng)為P, Q, R時(shí)，主合取范式時(shí)，主合取范式: (P QR) ( P QR) = M6 M2 n定理定理n任何命題公式都存在與之等值的主

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

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)補(bǔ)補(bǔ) = (0,2,4)補(bǔ)補(bǔ)= (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) 正項(xiàng)級(jí)數(shù)收斂當(dāng)且僅當(dāng)部分和有上界正項(xiàng)級(jí)數(shù)收斂當(dāng)且僅當(dāng)部分和有上界. (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é)論的思維過(guò)程思維過(guò)程n上面上面(1)是正確

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

13、(QR)R P 反映了一類推理關(guān)系反映了一類推理關(guān)系重言蘊(yùn)涵n 定義定義n 若若 (A1 A2 Ak ) B為為重言式重言式， 則稱則稱由由 A1, A2, , Ak推出結(jié)論推出結(jié)論B的的推理正確（有推理正確（有效結(jié)論）效結(jié)論） , 否則否則推理不正確（錯(cuò)誤）推理不正確（錯(cuò)誤）.n “A1, A2, , Ak 推出B” 的推理正確 當(dāng)且僅當(dāng) 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、小王就不去游泳。天氣涼快，所以小王沒(méi)去游泳。解題方法將命題符號(hào)化將命題符號(hào)化寫出前提、結(jié)論和推理的形式結(jié)構(gòu)寫出前提、結(jié)論和推理的形式結(jié)構(gòu)進(jìn)行判斷進(jìn)行判斷解： 設(shè) P：天氣涼快，Q：小王去游泳. 前提： P Q，P 結(jié)論： Q 推理的形式結(jié)構(gòu)為： (PQ) P) Q 判斷上式是否為重言式 。例：判斷下面推理是否正確（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒(méi)去游泳。判斷 (PQ) P) Q 是否為重言式 方法1：真值表法PQP Q(P Q) P(P Q) P) QFFTFTFTTFTTFTTTTTFFT( (PQ)P) ) Q例：判斷下面推理是否正確（1）若天氣涼快，小王就不去游泳。天

15、氣涼快，所以小王沒(méi)去游泳。判斷 (PQ) P) Q 是否為重言式 方法2：等值演算法 (PQ) P) Q = ( PQ) P)Q = = (P Q) P Q = = (P Q) (P Q) = = T( (PQ)P) ) Q例：判斷下面推理是否正確（1）若天氣涼快，小王就不去游泳。天氣涼快，所以小王沒(méi)去游泳。判斷 (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、沒(méi)上街，所以我沒(méi)去書店。解： 設(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)不是重言式！不是重言式！所以推理不正確所以推理不正確重言蘊(yùn)涵的幾個(gè)結(jié)果n如果如果A B，A為重言式，則為重言式，則B也是重言式也是重言式n如果如果A B， B A同時(shí)成立，必有同時(shí)成立，必有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推理演算法推理演算法一個(gè)描述推理過(guò)程的命題公式一個(gè)描述推理過(guò)程的命題公式序列序列n其中的每個(gè)命題公式是已知的其中的每個(gè)命題公式是已知的前提前提、或是由某些前、或是由某些前提依據(jù)提依據(jù)等值公式等值公式或或蘊(yùn)涵關(guān)系式蘊(yùn)涵關(guān)系式、應(yīng)用、應(yīng)用推理規(guī)則推理規(guī)則得到得到的結(jié)論的結(jié)論 n說(shuō)明：說(shuō)明：n當(dāng)命題變項(xiàng)比較少時(shí)，用上面當(dāng)命題變項(xiàng)比較少時(shí)，用上面3 3種方法比較方便種方法比較方便, , 此時(shí)此

18、時(shí)采用采用形式結(jié)構(gòu)形式結(jié)構(gòu)“A1 A2 AkB” . n而在推理演算時(shí)，而在推理演算時(shí)，采用下面形式：采用下面形式： 前提前提: A1, A2, , Ak 結(jié)論結(jié)論: B基本的推理公式1. P Q P 化簡(jiǎn)律化簡(jiǎn)律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 等價(jià)三段論等價(jià)三段論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說(shuō)明：n可用可用AB是重言式是重言式或或A B 是矛盾式是矛盾式來(lái)來(lái)證明推理公式證明推理公式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) 化簡(jiǎn)規(guī)則化簡(jiǎn)規(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)造性二難 在大城市球賽中，在大城市球賽