第一章命題演算基礎(chǔ)

1、醉雪醉雪風隨心動風隨心動 數(shù)理邏輯數(shù)理邏輯第一章第一章 命題演算基礎(chǔ)命題演算基礎(chǔ)第二章第二章 命題演算的推理理論命題演算的推理理論第三章第三章 謂詞演算基礎(chǔ)謂詞演算基礎(chǔ)第四章第四章 謂詞演算的推理理論謂詞演算的推理理論第五章第五章 遞歸函數(shù)論遞歸函數(shù)論數(shù)理邏輯數(shù)理邏輯集集 合合 論論圖圖 論論代代 數(shù)數(shù)24學時學時17學時學時19學時學時12學時學時醉雪醉雪風隨心動風隨心動 邏輯學邏輯學研究推理的科學研究推理的科學早期創(chuàng)始人早期創(chuàng)始人 亞里士多德亞里士多德(公元前公元前384322) 柏拉圖柏拉圖(公元前公元前429348), 首先把邏輯學的思首先把邏輯學的思想方法引入幾何學想方法引入幾何學

2、蘇格拉底蘇格拉底（前（前470前前399年）年）醉雪醉雪風隨心動風隨心動 數(shù)理邏輯數(shù)理邏輯數(shù)學化的邏輯學數(shù)學化的邏輯學 德國德國G.W. Leibniz (1626-1716)把數(shù)學引入形式邏輯，把數(shù)學引入形式邏輯，明確提出用數(shù)學方法研究推理。明確提出用數(shù)學方法研究推理。 英國英國G. Boole (1815-1864)等創(chuàng)立了邏輯代數(shù)，等創(chuàng)立了邏輯代數(shù)，1847年年Boole實現(xiàn)了命題演算。實現(xiàn)了命題演算。 德國德國G. Frege (1848-1925)在在1879年建立了第一個謂詞年建立了第一個謂詞演算系統(tǒng)。演算系統(tǒng)。 英國英國B. Russell (1872-1970)等從邏輯學的基本

3、法則建等從邏輯學的基本法則建立了自然數(shù)理論、實數(shù)理論及解析幾何學等。立了自然數(shù)理論、實數(shù)理論及解析幾何學等。 奧地利奧地利K. Godel (1906-1978)在在1931年提出年提出Godel不完不完全性定理。全性定理。 英國英國Alan M. Turing (1912-1954)在在1936年提出一種抽年提出一種抽象計算模型（數(shù)學邏輯機），引入圖靈機象計算模型（數(shù)學邏輯機），引入圖靈機一種一種理想的計算機。理想的計算機。醉雪醉雪風隨心動風隨心動 在計算機科學中的邏輯在計算機科學中的邏輯創(chuàng)建一種語言創(chuàng)建一種語言,使人們能夠?qū)τ嬎銠C科學領(lǐng)域使人們能夠?qū)τ嬎銠C科學領(lǐng)域中所遇到的情境進行建模中所

4、遇到的情境進行建模, 并在這種方式下并在這種方式下, 對對情境進行形式化推理。情境進行形式化推理。對情境進行推理意味著構(gòu)造與其相關(guān)的論證，對情境進行推理意味著構(gòu)造與其相關(guān)的論證，人們希望這個過程形式化，使這些論證經(jīng)得起人們希望這個過程形式化，使這些論證經(jīng)得起嚴格的推敲，或者能夠在計算機上實現(xiàn)。嚴格的推敲，或者能夠在計算機上實現(xiàn)。醉雪醉雪風隨心動風隨心動 例例1 前提？前提？ 結(jié)論？結(jié)論？ 怎么推理怎么推理?如果火車晚點，而且車站沒有出租車，那么小如果火車晚點，而且車站沒有出租車，那么小王參加會議就會遲到。小王沒有遲到，火車的王參加會議就會遲到。小王沒有遲到，火車的確晚點了，因此，車站有出租車。

5、確晚點了，因此，車站有出租車。P：火車晚點：火車晚點Q：車站有出租車：車站有出租車R：小王參加會議會遲到：小王參加會議會遲到如果如果P且非且非Q,那么那么R。非。非R，P，因此，因此，Q。醉雪醉雪風隨心動風隨心動 例例2 前提？前提？ 結(jié)論？結(jié)論？ 怎么推理怎么推理?如果下雨，小李沒有帶傘，就會被淋濕。而小如果下雨，小李沒有帶傘，就會被淋濕。而小李沒有被淋濕，確實下雨了，因此，小李帶傘李沒有被淋濕，確實下雨了，因此，小李帶傘了。了。P：下雨：下雨Q：小李帶傘小李帶傘R：小李被淋濕小李被淋濕如果如果P且非且非Q,那么那么R。非。非R，P，因此，因此，Q。醉雪醉雪風隨心動風隨心動 數(shù)理邏輯的學習數(shù)

6、理邏輯的學習“我現(xiàn)在年紀大了，搞了這么多年的我現(xiàn)在年紀大了，搞了這么多年的軟件，錯誤不知犯了多少，現(xiàn)在覺悟軟件，錯誤不知犯了多少，現(xiàn)在覺悟了。我想，假如我早年在數(shù)理邏輯上了。我想，假如我早年在數(shù)理邏輯上好好下點工夫的話，我就不會犯這么好好下點工夫的話，我就不會犯這么多的錯誤。不少東西邏輯學家早就說多的錯誤。不少東西邏輯學家早就說過了，可是我不知道。要是我能年輕過了，可是我不知道。要是我能年輕二十歲的話，我就去學邏輯。二十歲的話，我就去學邏輯?！?Edsger. W. Dijkstra 1972年年Turing獎獲得者獎獲得者 (1930-2002)帶權(quán)圖的最短通路算法醉雪醉雪風隨心動風隨心動

7、第一章第一章 命題演算基礎(chǔ)命題演算基礎(chǔ)1.11.1 命題和聯(lián)結(jié)詞命題和聯(lián)結(jié)詞 1.1.1 命題命題 1.1.2 聯(lián)結(jié)詞聯(lián)結(jié)詞 1.1.3 合式公式合式公式1.2 1.2 真假性真假性1.3 1.3 范式及其應(yīng)用范式及其應(yīng)用醉雪醉雪風隨心動風隨心動 (一一) 命題定義命題定義定義定義1： 凡是可以凡是可以判斷真假判斷真假的的陳述句陳述句稱為命題。稱為命題。命題的值命題的值 真真, 用用T(或或1)表示表示假假, 用用F(或或0)表示表示醉雪醉雪風隨心動風隨心動 例：下列句子都是命題嗎？ 雪是白的。雪是白的。 雪是黑的。雪是黑的。 好大的雪?。『么蟮难┌。?8大于大于12。 1+101=110。

8、醉雪醉雪風隨心動風隨心動 例：下列句子都是命題嗎？上海世博會開幕時天晴上海世博會開幕時天晴 21世紀末，人類將住在月球世紀末，人類將住在月球 大于大于2的偶數(shù)可表示成兩個素數(shù)之和的偶數(shù)可表示成兩個素數(shù)之和X0， 則則 x20。例例3 a=0當且僅當當且僅當 |a|=0。醉雪醉雪風隨心動風隨心動 真值函項的定義以真假為以真假為定義域定義域并以真假為并以真假為值域值域的函數(shù)的函數(shù)T, F(T, T), (T,F),(F,T), (F,F)T, F一元真值函項一元真值函項二元真值函項二元真值函項醉雪醉雪風隨心動風隨心動 一元聯(lián)結(jié)詞的真值表一個命題變項一個命題變項P，可取，可取“T”和和“F”兩種值。

9、兩種值。可定義四個一元真值函項可定義四個一元真值函項 f0，f1，f2，f3。P f0(P) f1(P) f2(P) f3(P)T T T F FF T F T F永永真真恒恒等等否否定定 P永永假假醉雪醉雪風隨心動風隨心動 二元聯(lián)結(jié)詞 P Q f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15T T T F T T T F F F T T T T F F F FT F T T F T T F T T F F T F T F F FF T T T T F T T F T F T F F F T F FF F T T T T F T T F

10、 T F F F F F T Ff4為析取f2為蘊含f8為等價f11為合取醉雪醉雪風隨心動風隨心動 三元聯(lián)結(jié)詞共有多少個？f0f1f2f?(0,0,0)0101(0,0,1)0011(0,1,0)0001(0,1,1)0001(1,0,0)0001(1,0,1)0001(1,1,0)0001(1,1,1)000128醉雪醉雪風隨心動風隨心動 第一章第一章 命題演算基礎(chǔ)命題演算基礎(chǔ)1.11.1 命題和聯(lián)結(jié)詞命題和聯(lián)結(jié)詞 1.1.1 命題命題 1.1.2 聯(lián)結(jié)詞聯(lián)結(jié)詞 1.1.3 合式公式合式公式 1.2 1.2 真假性真假性1.3 1.3 范式及其應(yīng)用范式及其應(yīng)用醉雪醉雪風隨心動風隨心動 合式公

11、式(Well formed formulae) 合式公式為如下定義的式子，簡稱為公式：合式公式為如下定義的式子，簡稱為公式： 任何命題變元均是公式；任何命題變元均是公式； 如果如果P為公式，則為公式，則 P為公式；為公式； 如果如果P，Q為公式，則為公式，則 P Q, P Q, PQ, PQ 為公式；為公式；當且僅當經(jīng)過有限次使用當且僅當經(jīng)過有限次使用、所組成的所組成的符號串才是公式，否則不為公式符號串才是公式，否則不為公式 。醉雪醉雪風隨心動風隨心動 n 元公式 若公式若公式 中有中有n n個不同的命題變元，個不同的命題變元，就說就說 為為n n 元公式。元公式。3元公式的例子：元公式的例子

12、： （P Q） R）（ P Q）（P Q R）（ P Q）醉雪醉雪風隨心動風隨心動 優(yōu)先級約定 非非 比其它聯(lián)結(jié)詞比其它聯(lián)結(jié)詞有更高的優(yōu)先級有更高的優(yōu)先級 括號括號（）（）內(nèi)的運算優(yōu)先內(nèi)的運算優(yōu)先本書未約定本書未約定 和比有更高的優(yōu)先級 是右結(jié)合的醉雪醉雪風隨心動風隨心動 命題符號化步驟：步驟：分析出簡單命題，符號化分析出簡單命題，符號化用聯(lián)結(jié)詞聯(lián)結(jié)簡單命題用聯(lián)結(jié)詞聯(lián)結(jié)簡單命題提示：根據(jù)命題的實際含義，不拘泥于原句形式地確提示：根據(jù)命題的實際含義，不拘泥于原句形式地確定原子命題和選用聯(lián)結(jié)詞。定原子命題和選用聯(lián)結(jié)詞。醉雪醉雪風隨心動風隨心動 例4(p5)已知三個命題：已知三個命題： P：今晚我在

13、家上網(wǎng)；：今晚我在家上網(wǎng)；Q：今晚我去球場看足球比賽；：今晚我去球場看足球比賽；R：今晚我在家上網(wǎng)或去球場看足球比賽。：今晚我在家上網(wǎng)或去球場看足球比賽。試問試問P Q和和R是否表達同一命題？是否表達同一命題？請用真值表說明之。請用真值表說明之。 R=( P Q) (PQ)P Q PQ R T T T F T F T T F T T T F F F F不可兼 或或 醉雪醉雪風隨心動風隨心動 例 將下述命題符號化，并指出真值: （1）豆沙包是由面粉和紅小豆做成的。 （2）2是質(zhì)數(shù)或合數(shù)。 （3）吃一塹，長一智。 （4）n是偶數(shù)當且僅當它能被3整除。 （n為一固定的自然數(shù)）醉雪醉雪風隨心動風隨心動

14、 例 令 p：北京比天津人口多。 q：2+24。 r：烏鴉是白色的。 求下列公式的真值： (1) (qr)(pr) (2) (pr) (pr) 醉雪醉雪風隨心動風隨心動 第一章第一章 命題演算基礎(chǔ)命題演算基礎(chǔ)1.11.1 命題和聯(lián)結(jié)詞命題和聯(lián)結(jié)詞 1.2 1.2 真假性真假性 1.2.1 1.2.1 解釋解釋 1.2.2 1.2.2 等價公式等價公式 1.2.3 1.2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 1.2.4 1.2.4 對偶式和內(nèi)否式對偶式和內(nèi)否式1.3 1.3 范式及其應(yīng)用范式及其應(yīng)用醉雪醉雪風隨心動風隨心動 完全解釋、部分解釋完全解釋、部分解釋定義：設(shè)定義：設(shè)n元公式元公式 中所有

15、的不同的命題變元為中所有的不同的命題變元為 P1, ,Pn 如果對每個命題變元均給予一個確定的值，如果對每個命題變元均給予一個確定的值，則稱對公式則稱對公式 給了一個給了一個完全解釋完全解釋； 如果僅對部分變元給予確定的值，如果僅對部分變元給予確定的值， 則稱對公式則稱對公式 給了一個給了一個部分解釋部分解釋。n元公式元公式 有有2n個完全解釋。個完全解釋。醉雪醉雪風隨心動風隨心動 例 考察公式考察公式 =（P Q） R PQR TTTTTTFFTT*不能確定F*T醉雪醉雪風隨心動風隨心動 成真解釋與成假解釋定義：對于任何公式定義：對于任何公式 ，凡使得，凡使得 取真值的解釋，不管取真值的解釋

16、，不管是完全解釋還是部分解釋，均稱為是完全解釋還是部分解釋，均稱為 的成真解釋。的成真解釋。定義：對于任何公式定義：對于任何公式 ，凡使得，凡使得 取假值的解釋，不管取假值的解釋，不管是完全解釋還是部分解釋，均稱為是完全解釋還是部分解釋，均稱為 的成假解釋。的成假解釋。醉雪醉雪風隨心動風隨心動 例 考察公式考察公式 =（P Q） R PQR TTTT1個成真解釋TTFF1個成假解釋TT*不能確定1個成真解釋1個成假解釋F*T4個成真解釋醉雪醉雪風隨心動風隨心動 永真公式與永假公式永真公式與永假公式定義：如果一個公式的所有完全解釋均為成真定義：如果一個公式的所有完全解釋均為成真解釋，則稱該公式為

17、解釋，則稱該公式為永真公式永真公式或稱為重或稱為重言式。言式。定義定義: 如果一個公式的所有完全解釋均為成假如果一個公式的所有完全解釋均為成假解釋，則稱該公式為解釋，則稱該公式為永假公式永假公式或稱為予或稱為予盾式。盾式。例例 P P 永假公式永假公式 P P 永真公式永真公式 P P 永真公式永真公式醉雪醉雪風隨心動風隨心動 可滿足公式與非永真公式可滿足公式與非永真公式定義：如果一個公式存在成真解釋，定義：如果一個公式存在成真解釋， 則稱該公式為則稱該公式為可滿足公式可滿足公式； 如果一個公式存在成假解釋，如果一個公式存在成假解釋， 則稱該公式為則稱該公式為非永真公式非永真公式。例例 P Q

18、 可滿足公式，非永真公式可滿足公式，非永真公式 P Q 可滿足公式，非永真公式可滿足公式，非永真公式醉雪醉雪風隨心動風隨心動 第一章第一章 命題演算基礎(chǔ)命題演算基礎(chǔ)1.11.1 命題和聯(lián)結(jié)詞命題和聯(lián)結(jié)詞 1.2 1.2 真假性真假性 1.2.1 1.2.1 解釋解釋 1.2.2 1.2.2 等價公式等價公式 1.2.3 1.2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 1.2.4 1.2.4 對偶式和內(nèi)否式對偶式和內(nèi)否式1.3 1.3 范式及其應(yīng)用范式及其應(yīng)用醉雪醉雪風隨心動風隨心動 邏輯等價邏輯等價定義：給定兩個公式定義：給定兩個公式 和和 ， 設(shè)設(shè)P1，P2，Pn為為 和和 的所有命題變元，的所有

19、命題變元， 那么那么 和和 有有2n個解釋。個解釋。 如果對每個解釋，如果對每個解釋， 和和 永取相同的真假值，永取相同的真假值， 則稱則稱 和和 是是邏輯等價邏輯等價的，記為的，記為 = 。 醉雪醉雪風隨心動風隨心動 例例 問：問： P P = P?從真值表，可以看出：從真值表，可以看出： P P = PP P P P TFTF=FFTFT=T考察真值表如下考察真值表如下醉雪醉雪風隨心動風隨心動 八組重要的等價公式 雙重否定律雙重否定律 P=P結(jié)合律結(jié)合律 （P Q） R = P （Q R） （P Q） R = P （Q R）分配律分配律 P （Q R）=（P Q ） （P R） P （Q

20、R）=（P Q ） （P R）醉雪醉雪風隨心動風隨心動 八組重要的等價公式交換律交換律 P Q= Q P P Q= Q P等冪律等冪律 P P = P P P = P P P = T P P = T醉雪醉雪風隨心動風隨心動 八組重要的等價公式等值公式等值公式 P Q = P Q P Q =（PQ） （Q P） =（ P Q） （P Q） =（P Q） （ P Q） （P Q）= PQ （P Q）= PQ醉雪醉雪風隨心動風隨心動 八組重要的等價公式 部份解釋部份解釋 P T = P P F = F P T = T P F = P T P = P F P = T P T = T P F = P T

21、 P = P F P = P?醉雪醉雪風隨心動風隨心動 八組重要的等價公式吸收律吸收律 P （P Q）= P P （P Q）= P醉雪醉雪風隨心動風隨心動 例 判斷下列公式的類型 q ( pq) p)解解: 考察真值表考察真值表 所以，它是永真的所以，它是永真的。 pqA= pqB=ApC= BqCTTTTFTTFFFTTFTTFTTFFTFTT醉雪醉雪風隨心動風隨心動 例 判斷下列公式的類型 q ( pq) p)解解: q ( pq) p) =q( ( pq) ) p =(q p )( ( pq) ) =T 所以，它是永真的所以，它是永真的。 醉雪醉雪風隨心動風隨心動 例 判斷下列公式的類型

22、判斷下列公式的類型 (pq) p解解: 考察真值表考察真值表 所以，它是可滿足的所以，它是可滿足的。 pqA=pqB= pABTTTFFTFFFFFTTTTFFTTT醉雪醉雪風隨心動風隨心動 例 判斷下列公式的類型判斷下列公式的類型 (pq) p解解: (pq) p =( pq) p = p 所以，它是可滿足的。所以，它是可滿足的。醉雪醉雪風隨心動風隨心動 例 判斷下列公式的類型 (p p) (q q) r)解解: (p p) (q q) r) = T (q q) r) = (q q) r =Fr =F 所以，它是永假的。所以，它是永假的。醉雪醉雪風隨心動風隨心動 成真解釋和成假解釋的求解方法

23、 （1）否定深入：即把否定詞一直深入至命題變）否定深入：即把否定詞一直深入至命題變元上；元上；（2）部分解釋：選定某個出現(xiàn)次數(shù)最多的變元）部分解釋：選定某個出現(xiàn)次數(shù)最多的變元對它作真或假的兩種解釋從而對它作真或假的兩種解釋從而得公式；得公式；（3）化簡；）化簡；（4）依次類推，直至產(chǎn)生公式的所有解釋。）依次類推，直至產(chǎn)生公式的所有解釋。醉雪醉雪風隨心動風隨心動 例(p7) 試判定公式 (P Q)( QP)R) 的永真性和可滿足性。的永真性和可滿足性。解解1：否定深入：否定深入 原式原式 = ( P Q)( QP)R) 對對 P=T 進行解釋并化簡，進行解釋并化簡， 結(jié)果見教材。結(jié)果見教材。醉雪

24、醉雪風隨心動風隨心動 解解2：否定深入：否定深入 原式原式 = ( P Q)( QP)R) 對對P=F進行解釋并化簡。進行解釋并化簡。 原式原式=（ FQ）（ QF）R） = （ QF）R = Q R Q=T 時，時， 原式原式 =TR = R， 于是于是 R=T 時，原式時，原式=F R=F 時，原式時，原式=T 因此因此,公式存在成真解釋公式存在成真解釋 (P，Q，R)=(F，T，F(xiàn)) ； 公式存在成假解釋公式存在成假解釋(P，Q，R)=(F，T，T)。 故公式可滿足但非永真。故公式可滿足但非永真。醉雪醉雪風隨心動風隨心動 解解3：考察：考察 (P Q)( QP)R)所以，公式存在成真解釋

25、：所以，公式存在成真解釋： (T,T,*), (T,F,F), (F,T,F), (F,F,T); 公式存在成假解釋：公式存在成假解釋： (T,F,T), (F,T,T), (F,F,F)。故公式可滿足但非永真。故公式可滿足但非永真。(P,Q,R)A=(PQ)B=QPC=BRAC(T,T,T)FTFT(T,T,F)FFFT(T,F,T)TTFF(T,F,F)TTTT(F,T,T)TTFF(F,T,F)TTTT(F,F,T)TFTT(F,F,F)TFFF醉雪醉雪風隨心動風隨心動 例例 試求下列公式的成真解釋和成假解釋試求下列公式的成真解釋和成假解釋 （PQ） （Q （ R P）解解:當當P=T時

26、時, 原式原式= (TQ) (Q ( R T) = Q (Q ( R)= QR 當當P=F時時, 原式原式= (FQ) (Q ( R F) = T (Q F)=Q由上可知由上可知: 公式不是永真公式公式不是永真公式,是可滿足的是可滿足的. 成真解釋為成真解釋為(P,Q,R)=(T,F,F),(F,T,*), 成假解釋為成假解釋為(P,Q,R)=(T,T,T),(T,F,T),(T,T,F),(F,F*).醉雪醉雪風隨心動風隨心動 第一章第一章 命題演算基礎(chǔ)命題演算基礎(chǔ)1.11.1 命題和聯(lián)結(jié)詞命題和聯(lián)結(jié)詞 1.2 1.2 真假性真假性 1.2.1 1.2.1 解釋解釋 1.2.2 1.2.2

27、等價公式等價公式 1.2.3 1.2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 1.2.4 1.2.4 對偶式和內(nèi)否式對偶式和內(nèi)否式1.3 1.3 范式及其應(yīng)用范式及其應(yīng)用醉雪醉雪風隨心動風隨心動 聯(lián)結(jié)詞的完備集 定義定義 設(shè)設(shè)S是聯(lián)結(jié)詞的集合，如果是聯(lián)結(jié)詞的集合，如果 對任何命題演算公式均可以由對任何命題演算公式均可以由S中的聯(lián)中的聯(lián)結(jié)詞表示出來的公式與之等價結(jié)詞表示出來的公式與之等價， 則說則說S是聯(lián)結(jié)詞的完備集。是聯(lián)結(jié)詞的完備集。由聯(lián)結(jié)詞的定義知，聯(lián)結(jié)詞集合由聯(lián)結(jié)詞的定義知，聯(lián)結(jié)詞集合 ， ， ，是完備的。是完備的。 醉雪醉雪風隨心動風隨心動 定理1 聯(lián)結(jié)詞的集合聯(lián)結(jié)詞的集合 ， ， 是完備的。

28、是完備的。思路思路: 去蘊含詞與等價詞去蘊含詞與等價詞 PQ = P Q PQ =（ P Q） （P Q） 醉雪醉雪風隨心動風隨心動 定理定理 聯(lián)結(jié)詞的集合聯(lián)結(jié)詞的集合 ， 是完備的。是完備的。思路思路: 在去蘊含詞與等價詞的基礎(chǔ)上在去蘊含詞與等價詞的基礎(chǔ)上, PQ = P Q PQ =（ P Q） （P Q） 去析取詞：去析取詞： P Q = （ P Q） 醉雪醉雪風隨心動風隨心動 定理定理 聯(lián)結(jié)詞的集合聯(lián)結(jié)詞的集合 ， 是完備的。是完備的。思路思路: 在去蘊含詞與等價詞的基礎(chǔ)上在去蘊含詞與等價詞的基礎(chǔ)上, PQ = P Q PQ =（ P Q） （P Q） 去合取詞去合取詞 P Q = （

29、 P Q）醉雪醉雪風隨心動風隨心動 定理定理 聯(lián)結(jié)詞的集合聯(lián)結(jié)詞的集合 ， 是完備的。是完備的。思路思路: 去等價詞、析取詞、合取詞：去等價詞、析取詞、合取詞： PQ =（ PQ ） （ PQ ） P Q= PQ PQ = （ P Q）= （P Q） 醉雪醉雪風隨心動風隨心動 與非與非: P Q = （P Q） P Q P Q T T FT F TF T TF F T定理定理2(p8) 聯(lián)結(jié)詞的集合聯(lián)結(jié)詞的集合是完備的。是完備的。 思路：思路： 去否定詞與合取詞：去否定詞與合取詞： P = P P P Q= （P Q）醉雪醉雪風隨心動風隨心動 或非：或非： PQ= (PQ) 定理：定理： 聯(lián)結(jié)

30、詞的集合聯(lián)結(jié)詞的集合是完備的。是完備的。 P Q PQ T T FT F FF T FF F T思路：思路： 去否定詞與析取詞：去否定詞與析取詞： P = P P P Q= （P Q）醉雪醉雪風隨心動風隨心動 例例(p8) 試證明聯(lián)結(jié)詞集合試證明聯(lián)結(jié)詞集合不完備。不完備。證明：證明： 對于任意公式對于任意公式P， P也是公式也是公式 。 假設(shè)假設(shè)是完備的。根據(jù)完備性的定義知，是完備的。根據(jù)完備性的定義知， P = Q1 Q2 Q3 Qn 當當P，Q1, Q2, Q3, , Qn全取為真時，全取為真時，公式左邊公式左邊=F，公式右邊，公式右邊=T。 顯然矛盾。顯然矛盾。 故聯(lián)結(jié)詞集合故聯(lián)結(jié)詞集合

31、不完備。不完備。 醉雪醉雪風隨心動風隨心動 例例 試證明聯(lián)結(jié)詞集合試證明聯(lián)結(jié)詞集合不完備。不完備。證明：證明： 對于任意公式對于任意公式P， P也是公式也是公式 。 假設(shè)假設(shè)是完備的。根據(jù)完備性的定義知，是完備的。根據(jù)完備性的定義知， P = Q1 Q2 Q3 Qn 當當P，Q1, Q2, Q3, , Qn全取為假時，全取為假時，公式左邊公式左邊=T，公式右邊，公式右邊=F。 顯然矛盾。顯然矛盾。 故聯(lián)結(jié)詞集合故聯(lián)結(jié)詞集合不完備。不完備。 醉雪醉雪風隨心動風隨心動 第一章第一章 命題演算基礎(chǔ)命題演算基礎(chǔ)1.11.1 命題和聯(lián)結(jié)詞命題和聯(lián)結(jié)詞 1.2 1.2 真假性真假性 1.2.1 1.2.1

32、 解釋解釋 1.2.2 1.2.2 等價公式等價公式 1.2.3 1.2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 1.2.4 1.2.4 對偶式和內(nèi)否式對偶式和內(nèi)否式 1.3 1.3 范式及其應(yīng)用范式及其應(yīng)用醉雪醉雪風隨心動風隨心動 對偶式對偶式的定義 定義：將任何一個定義：將任何一個不含不含蘊含詞和等價詞的命題蘊含詞和等價詞的命題演算公式演算公式 中的中的 換為換為 ， 換為換為 后所得的公式稱為后所得的公式稱為 的的對偶式對偶式， 記為記為 *。 醉雪醉雪風隨心動風隨心動 例例 已知公式已知公式 = P （QR）, 求對偶式求對偶式 *、 （ *）* 。解：解： = P （QR） *= P （Q

33、R） ( *)*= P （QR）醉雪醉雪風隨心動風隨心動 內(nèi)否式的定義定義：將任何命題演算公式定義：將任何命題演算公式 中的所有中的所有 肯定形式換為否定形式、肯定形式換為否定形式、 否定形式換為肯定形式否定形式換為肯定形式 后所得的公式稱為后所得的公式稱為 的的內(nèi)否式內(nèi)否式， 記為記為 。醉雪醉雪風隨心動風隨心動 例例 已知公式已知公式 = P （QR）, 求內(nèi)否式求內(nèi)否式 、 （ ） 。解：解： = P （QR） = P （ Q R）（ ） = P （Q R）醉雪醉雪風隨心動風隨心動 對偶式和內(nèi)否式的性質(zhì)對偶式和內(nèi)否式的性質(zhì) 性質(zhì)性質(zhì)1 （ *）* = （ ） = 醉雪醉雪風隨心動風隨心動

34、 對偶式和內(nèi)否式的否定對偶式和內(nèi)否式的否定定理定理1(p9) （A*）=（ A）* （A）=（ A）醉雪醉雪風隨心動風隨心動 定理定理2(p9) A =A*證明：證明：思路是對公式思路是對公式A中出現(xiàn)的聯(lián)結(jié)詞的個數(shù)中出現(xiàn)的聯(lián)結(jié)詞的個數(shù)n進行歸納證明進行歸納證明。 當當n=0時，時， A中無聯(lián)結(jié)詞，便有中無聯(lián)結(jié)詞，便有 A=P， 從而有從而有 A= P， A*=P ， 所以所以 A* = P= A， 即定理成立。即定理成立。 醉雪醉雪風隨心動風隨心動 證明證明(續(xù)續(xù)): 歸納假設(shè)：設(shè)歸納假設(shè)：設(shè)n k時定理成立。時定理成立。 考察考察n=k+1 1，A中至少有一個聯(lián)結(jié)詞，中至少有一個聯(lián)結(jié)詞， 可

35、分為下面三種情形：可分為下面三種情形： A= A1， A=A1 A2， A=A1 A2 其中其中A1，A2中的聯(lián)結(jié)詞個數(shù)中的聯(lián)結(jié)詞個數(shù) k 。 依歸納假設(shè)依歸納假設(shè) A1= A1* ， A2= A2* 。 對于上述三種情形，可以分別證明結(jié)論成立：對于上述三種情形，可以分別證明結(jié)論成立： A =A*。 由數(shù)學歸納法知，定理得證。由數(shù)學歸納法知，定理得證。醉雪醉雪風隨心動風隨心動 第一章第一章 命題演算基礎(chǔ)命題演算基礎(chǔ)1.11.1 命題和聯(lián)結(jié)詞命題和聯(lián)結(jié)詞 1.2 1.2 真假性真假性 1.3 1.3 范式及其應(yīng)用范式及其應(yīng)用 1.3.1 1.3.1 范式范式 1.3.2 1.3.2 主范式主范式

36、 1.3.3 1.3.3 范式的應(yīng)用范式的應(yīng)用醉雪醉雪風隨心動風隨心動 合取式、析取式合取式、析取式定義定義1 命題變元、或者命題變元的否定、或由它們命題變元、或者命題變元的否定、或由它們利用合取詞組成的合式公式稱為利用合取詞組成的合式公式稱為合取式合取式。定義定義2 命題變元、或者命題變元的否定、或由它們命題變元、或者命題變元的否定、或由它們利用析取詞組成的合式公式稱為利用析取詞組成的合式公式稱為析取式析取式。例例 顯然，顯然， P， P，P Q， P QR 均為合取式；均為合取式； P， P，P Q， P QR 均為析取式。均為析取式。醉雪醉雪風隨心動風隨心動 (一一) 解釋與合取式、析取

37、式之間的關(guān)系解釋與合取式、析取式之間的關(guān)系 定理定理1 任給一個成真解釋有且僅有一個合取式任給一個成真解釋有且僅有一個合取式與之對應(yīng)；與之對應(yīng)； 任給一個成假解釋有且僅有任給一個成假解釋有且僅有一個析取式與之對應(yīng)。一個析取式與之對應(yīng)。 反之亦然。反之亦然。例例 成真解釋成真解釋(P，Q，R)= (T,F,T) 成假解釋成假解釋(P，Q，R)= (F,F,T)合取式合取式PQ R析取式析取式P QR醉雪醉雪風隨心動風隨心動 析取范式、合取范式析取范式、合取范式定義定義3 形如形如A1 A2 An的公式稱為的公式稱為析取范式析取范式， 其中其中Ai(i=1,2,n)為合取式。為合取式。定義定義4

38、形如形如A1 A2 An的公式稱為的公式稱為合取范式合取范式， 其中其中Ai(i=1,2,n)為析取式。為析取式。例例 P， P，P Q，P Q ，( P Q) (SR) 均為析取范式。均為析取范式。 P， P，P Q，P Q ， ( P Q) (SR)均為合取范式。均為合取范式。醉雪醉雪風隨心動風隨心動 例例: 考察公式考察公式 =PQ的的析取范式析取范式有兩個成真解釋：有兩個成真解釋： (T, T), (F, F), 分別對應(yīng)于兩個合取式為分別對應(yīng)于兩個合取式為 PQ, P Q于是，有于是，有 = (PQ) ( P Q)P Q P QT T TT F FF T FF F T醉雪醉雪風隨心動

39、風隨心動 例例: 考察公式考察公式 =PQ的的合取范式合取范式成假解釋成假解釋 (T, F), (F, T), 對應(yīng)析取式為對應(yīng)析取式為 PQ, P Q于是，有：于是，有： = ( PQ) (P Q)P Q P QT T TT F FF T FF F T醉雪醉雪風隨心動風隨心動 定理定理2 任何命題演算公式均可以化為合任何命題演算公式均可以化為合取范式，也可以化為析取范式。取范式，也可以化為析取范式。證明：證明： (1)設(shè)公式設(shè)公式 為永真公式為永真公式 =PP (2)設(shè)公式設(shè)公式 為永假公式為永假公式 =P P醉雪醉雪風隨心動風隨心動 證明證明(3)： 設(shè)公式設(shè)公式 既非永真又非永假。既非永

40、真又非永假。設(shè)公式設(shè)公式 的成真解釋為的成真解釋為 1， 2， n， 成假解釋為成假解釋為 1， 2， t。根據(jù)解釋和范式的關(guān)系知：根據(jù)解釋和范式的關(guān)系知：對應(yīng)于成真解釋對應(yīng)于成真解釋 1， 2， n的合取式為的合取式為 1， 2， n對應(yīng)于成假解釋對應(yīng)于成假解釋 1， 2， t的析取式為的析取式為 1， 2， t而公式而公式 12 n的成真解釋為的成真解釋為 1， 2， n；公式公式 12 t的成假解釋為的成假解釋為 1， 2， t。根據(jù)根據(jù)兩個公式邏輯等價的定義兩個公式邏輯等價的定義知知 = 12 n = 12 t故公式故公式 既可表示為析取范式又可表示為合取范式。既可表示為析取范式又可表

41、示為合取范式。醉雪醉雪風隨心動風隨心動 (二二) 析取范式和合取范式的求解方法析取范式和合取范式的求解方法 等價變換法等價變換法解釋法解釋法醉雪醉雪風隨心動風隨心動 等價變換法等價變換法(1)去蘊含詞與等價詞：去蘊含詞與等價詞： PQ = P Q PQ =（ P Q） （P Q）(2)否定深入：否定深入： (P Q)= PQ (P Q)= PQ， P = P(3)重復(fù)使用分配律：重復(fù)使用分配律： P (Q R)=(P Q ) (P R) P (Q R)=(P Q ) (P R)醉雪醉雪風隨心動風隨心動 解釋法解釋法(1) 求所有成真解釋、成假解釋；求所有成真解釋、成假解釋；(2) 寫出成真解釋

42、對應(yīng)的合取式、寫出成真解釋對應(yīng)的合取式、 成假解釋對應(yīng)的析取式；成假解釋對應(yīng)的析取式；(3) 把所有的合取式用析取詞聯(lián)結(jié)起來就構(gòu)成析把所有的合取式用析取詞聯(lián)結(jié)起來就構(gòu)成析取范式，把所有的析取式用合取詞聯(lián)結(jié)起取范式，把所有的析取式用合取詞聯(lián)結(jié)起來就構(gòu)成合取范式。來就構(gòu)成合取范式。醉雪醉雪風隨心動風隨心動 例例 求公式的范式求公式的范式 (PQ)(RQ)P)解解：原式原式= ( P Q)( ( RQ)P) =(PQ) ( RQ) P) =(PQ) (PR) (PQ) =(PQ) (PR) 析取范式析取范式 = P ( QR) 合取范式合取范式醉雪醉雪風隨心動風隨心動 解：解：P=T時時, 原式原式

43、= (TQ) (RQ)T) = Q R P=F時時, 原式原式= (FQ) (RQ)F) =F 所以有所以有: 成真解釋為：成真解釋為：(P,Q,R)=(T,F,T), (T,F,F), (T,T,F) 成假解釋為：成假解釋為：(P,Q,R)=(T,T,T), (F, , )例例 求公式的范式求公式的范式 (PQ)(RQ)P)于是析取范式為于是析取范式為: (PQ R) (P Q R) (P Q R) 合取范式為：合取范式為： ( P QR) P醉雪醉雪風隨心動風隨心動 范式不唯一性范式不唯一性例例 求公式的范式求公式的范式 (PQ)(RQ)P)解解1： 原式原式=(PQ) (PR) 析取范式

44、析取范式 = P ( QR) 合取范式合取范式解解2: 析取范式為析取范式為: (PQ R) (P Q R) (P Q R) 合取范式為：合取范式為： ( P QR) P醉雪醉雪風隨心動風隨心動 第一章第一章 命題演算基礎(chǔ)命題演算基礎(chǔ)1.11.1 命題和聯(lián)結(jié)詞命題和聯(lián)結(jié)詞 1.2 1.2 真假性真假性 1.3 1.3 范式及其應(yīng)用范式及其應(yīng)用 1.3.1 1.3.1 范式范式 1.3.2 1.3.2 主范式主范式 1.3.3 1.3.3 范式的應(yīng)用范式的應(yīng)用醉雪醉雪風隨心動風隨心動 (一一) 主析取范式主析取范式定義定義1 對于對于n個命題變元個命題變元P1，P2，Pn，公式，公式 Q1 Q2

45、 Qn 稱為稱為極小項極小項，其中，其中Qi=Pi或或 Pi(i=1，n)。例例 由兩個命題變元由兩個命題變元P，Q組成的極小項有四個，它們組成的極小項有四個，它們分別為：分別為： PQ P QPQ P Q醉雪醉雪風隨心動風隨心動 三個命題變元三個命題變元P、Q和和R可構(gòu)造可構(gòu)造8個極小項個極小項把命題變元的否定形式看成把命題變元的否定形式看成0，肯定形式看成，肯定形式看成1，則每，則每個極小項對應(yīng)一個二進制數(shù)，也對應(yīng)一個十進制數(shù)。個極小項對應(yīng)一個二進制數(shù)，也對應(yīng)一個十進制數(shù)。它們對應(yīng)如下：它們對應(yīng)如下： PQR 與與000 或或0對應(yīng)，簡記為對應(yīng)，簡記為 m0 PQ R 與與001 或或1對

46、應(yīng)，簡記為對應(yīng)，簡記為 m1 P QR 與與010 或或2對應(yīng)，簡記為對應(yīng)，簡記為 m2 P Q R 與與011 或或3對應(yīng)，簡記為對應(yīng)，簡記為 m3 PQR 與與100 或或4對應(yīng)，簡記為對應(yīng)，簡記為 m4 PQ R 與與101 或或5對應(yīng)，簡記為對應(yīng)，簡記為 m5 P QR 與與110 或或6對應(yīng)，簡記為對應(yīng)，簡記為 m6 P Q R 與與111 或或7對應(yīng)，簡記為對應(yīng)，簡記為 m7醉雪醉雪風隨心動風隨心動 n個命題變元組成的極小項有個命題變元組成的極小項有2n個個 公式的每一個完全成真解釋對應(yīng)一個極小項公式的每一個完全成真解釋對應(yīng)一個極小項 公式的所有完全成真解釋對應(yīng)極小項的析取公式的所

47、有完全成真解釋對應(yīng)極小項的析取醉雪醉雪風隨心動風隨心動 主析取范式主析取范式 定義定義2 僅有極小項構(gòu)成的析取范式稱為僅有極小項構(gòu)成的析取范式稱為主析取范式主析取范式。定理定理1 任何一個合式公式，均有惟一的一個主析取范式任何一個合式公式，均有惟一的一個主析取范式與該合式公式等價。與該合式公式等價。主析取范式就是主析取范式就是公式的所有完全成真解釋對應(yīng)極小項的析取。公式的所有完全成真解釋對應(yīng)極小項的析取。 醉雪醉雪風隨心動風隨心動 求主析取范式的兩種方法(1)解釋法解釋法: 根據(jù)公式的所有完全成真解釋，求出與這些根據(jù)公式的所有完全成真解釋，求出與這些成真解釋對應(yīng)的合取式，所有合取式的析取就為成

48、真解釋對應(yīng)的合取式，所有合取式的析取就為公式的主析取范式。公式的主析取范式。(2)等價變換法等價變換法: 將析取范式中的每一個合取式用將析取范式中的每一個合取式用AA填填滿命題變元，然后用等價公式進行變換，消去相滿命題變元，然后用等價公式進行變換，消去相同部分，即得公式的主析取范式。同部分，即得公式的主析取范式。醉雪醉雪風隨心動風隨心動 例例 求公式的求公式的主析取范式 (PQ)(RQ)P)解解：原式原式= ( P Q)( ( RQ)P) =(PQ) ( RQ) P) =(PQ) (PR) (PQ) =(PQ) (PR) 析取范式析取范式 =(PQ (R R) (P (QQ)R) = (PQ

49、R) (PQ R) (P QR) =101 100 110=4 5 6醉雪醉雪風隨心動風隨心動 解：解：P=T時時, 原式原式= (TQ) (RQ)T) = Q R P=F時時, 原式原式= (FQ) (RQ)F) =F 所以有所以有: 成真解釋為：成真解釋為：(P,Q,R)=(T,F,T), (T,F,F), (T,T,F) 例例 求公式的求公式的主析取范式 (PQ)(RQ)P)于是主析取范式為于是主析取范式為: (PQ R) (P Q R) (P Q R) =101 100 110=4 5 6醉雪醉雪風隨心動風隨心動 (二二) 主合取范式主合取范式定義定義3 對于對于n個命變元個命變元P1

50、，P2，Pn，公式，公式 Q1 Q2 Qn 稱為稱為極大項極大項，其中，其中Qi=Pi或或 Pi(i=1，n)。例例 由兩個命題變元由兩個命題變元P，Q組成的極大項有四個，它們組成的極大項有四個，它們分別為：分別為： PQ P Q PQ P Q醉雪醉雪風隨心動風隨心動 三個命題變元三個命題變元P、Q和和R可構(gòu)造可構(gòu)造8個極大項個極大項 把命題變元的否定形式看成把命題變元的否定形式看成1，肯定形式看成，肯定形式看成0，則每個，則每個極大項對應(yīng)一個二進制數(shù)，也對應(yīng)一個十進制數(shù)。它們極大項對應(yīng)一個二進制數(shù)，也對應(yīng)一個十進制數(shù)。它們對應(yīng)如下：對應(yīng)如下： P Q R 與與000 或或0對應(yīng)，簡記為對應(yīng)，

51、簡記為 M0 P QR 與與001 或或1對應(yīng)，簡記為對應(yīng)，簡記為 M1 PQ R 與與010 或或2對應(yīng)，簡記為對應(yīng)，簡記為 M2 PQR 與與011 或或3對應(yīng)，簡記為對應(yīng)，簡記為 M3 P Q R 與與100 或或4對應(yīng)，簡記為對應(yīng)，簡記為 M4 P QR 與與101 或或5對應(yīng)，簡記為對應(yīng)，簡記為 M5 PQ R 與與110 或或6對應(yīng)，簡記為對應(yīng)，簡記為 M6 PQR與與111 或或7對應(yīng)，簡記為對應(yīng)，簡記為 M7醉雪醉雪風隨心動風隨心動 n個命題變元組成的極大項有個命題變元組成的極大項有2n個個 公式的每一個完全成假解釋對應(yīng)一個極大項公式的每一個完全成假解釋對應(yīng)一個極大項 公式的所

52、有完全成假解釋對應(yīng)極大項的合取公式的所有完全成假解釋對應(yīng)極大項的合取醉雪醉雪風隨心動風隨心動 主合取范式主合取范式定義定義4 僅有極大項構(gòu)成的合取范式稱為僅有極大項構(gòu)成的合取范式稱為主合取范式主合取范式。 定理定理2 任何一個合式公式，均有惟一的一個主合取范式與任何一個合式公式，均有惟一的一個主合取范式與該合式公式等價。該合式公式等價。主合取范式就是主合取范式就是公式的所有完全成假解釋對應(yīng)的極大項的合取。公式的所有完全成假解釋對應(yīng)的極大項的合取。醉雪醉雪風隨心動風隨心動 求主合取范式的兩種方法求主合取范式的兩種方法(1)解釋法解釋法 根據(jù)公式的所有完全成假解釋，求出與這些根據(jù)公式的所有完全成假

53、解釋，求出與這些成假解釋對應(yīng)的析取式，所有析取式的合取就為成假解釋對應(yīng)的析取式，所有析取式的合取就為公式的主合取范式。公式的主合取范式。(2)等價變換法等價變換法 將合取范式中的每一個析取式用將合取范式中的每一個析取式用AA填滿命題變元，然后用等價公式進行變換，消去填滿命題變元，然后用等價公式進行變換，消去相同部份，即得公式的主合取范式。相同部份，即得公式的主合取范式。醉雪醉雪風隨心動風隨心動 例例 求公式的主合取范式求公式的主合取范式 (PQ)(RQ)P)解解：原式原式= ( P Q)( ( RQ)P) =(PQ) ( RQ) P) =(PQ) (PR) (PQ) =(PQ) (PR) 析取

54、范式析取范式 = P ( QR) 合取范式合取范式 =(P (QQ) (RR) ( QR) (PP) =(P Q R) (P QR) (PQ R) (PQR) ( PQR) =000 001 010 011 111=0 1 2 3 7醉雪醉雪風隨心動風隨心動 解：解：P=T時時, 原式原式= (TQ) (RQ)T) = Q R P=F時時, 原式原式= (FQ) (RQ)F) =F 所以有所以有: 成假解釋為：成假解釋為：(P,Q,R)=(T,T,T), (F, , )例例 求公式的主合取范式求公式的主合取范式 (PQ)(RQ)P)于是于是主合取范式主合取范式= ( PQR) (PQR) (P

55、Q R) (P QR) (P Q R) =111 011 010 001 000=0 1 2 3 7(F,TT),(F,T,F),(F,F,T),(F,F,F)醉雪醉雪風隨心動風隨心動 例例 試求試求 =(PR)( P ( Q R) 的主析取范式和主合取范式的主析取范式和主合取范式解解: =( PR) ( P( QR)(P( ( QR)（去蘊涵詞、等價詞）（去蘊涵詞、等價詞） =( PR) ( P QR) (PQ) (P R)（化簡）（化簡） =(P R) ( P QR) (PQ) (P R)（去蘊涵詞）（去蘊涵詞） = (P R) ( P QR)(PQ) =(110 100) 001 (111 110)=(1,4,6,7)醉雪醉雪風隨心動風隨心動 解解(續(xù)續(xù)): 已經(jīng)得到已經(jīng)得到主析取范式如下主析取范式如下: = ( P QR)(PQ)(P R)=( PP)( PQ)( QP) ( QQ)(PR)(QR)(P R) =( PQ)( QP)(PR)(QR)