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

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

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

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

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

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

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

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)用醉雪醉雪風(fēng)隨心動風(fēng)隨心動 (一一) 命題定義命題定義定義定義1： 凡是可以凡是可以判斷真假判斷真假的的陳述句陳述句稱為命題。稱為命題。命題的值命題的值 真真, 用用T(或或1)表示表示假假, 用用F(或或0)表示表示醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例：下列句子都是命題嗎？ 雪是白的。雪是白的。 雪是黑的。雪是黑的。 好大的雪啊！好大的雪??！ 8大于大于12。 1+101=110。

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

9、兩種值?？啥x四個(gè)一元真值函項(xiàng)可定義四個(gè)一元真值函項(xiàng) f0，f1，f2，f3。P f0(P) f1(P) f2(P) f3(P)T T T F FF T F T F永永真真恒恒等等否否定定 P永永假假醉雪醉雪風(fēng)隨心動風(fēng)隨心動 二元聯(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為蘊(yùn)含f8為等價(jià)f11為合取醉雪醉雪風(fēng)隨心動風(fēng)隨心動 三元聯(lián)結(jié)詞共有多少個(gè)？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醉雪醉雪風(fēng)隨心動風(fēng)隨心動 第一章第一章 命題演算基礎(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)用醉雪醉雪風(fēng)隨心動風(fēng)隨心動 合式公

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

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

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

14、 例 令 p：北京比天津人口多。 q：2+24。 r：烏鴉是白色的。 求下列公式的真值： (1) (qr)(pr) (2) (pr) (pr) 醉雪醉雪風(fēng)隨心動風(fēng)隨心動 第一章第一章 命題演算基礎(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 等價(jià)公式等價(jià)公式 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)用醉雪醉雪風(fēng)隨心動風(fēng)隨心動 完全解釋、部分解釋完全解釋、部分解釋定義：設(shè)定義：設(shè)n元公式元公式 中所有

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

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

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

18、 可滿足公式，非永真公式可滿足公式，非永真公式 P Q 可滿足公式，非永真公式可滿足公式，非永真公式醉雪醉雪風(fēng)隨心動風(fēng)隨心動 第一章第一章 命題演算基礎(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 等價(jià)公式等價(jià)公式 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)用醉雪醉雪風(fēng)隨心動風(fēng)隨心動 邏輯等價(jià)邏輯等價(jià)定義：給定兩個(gè)公式定義：給定兩個(gè)公式 和和 ， 設(shè)設(shè)P1，P2，Pn為為 和和 的所有命題變元，的所有

19、命題變元， 那么那么 和和 有有2n個(gè)解釋。個(gè)解釋。 如果對每個(gè)解釋，如果對每個(gè)解釋， 和和 永取相同的真假值，永取相同的真假值， 則稱則稱 和和 是是邏輯等價(jià)邏輯等價(jià)的，記為的，記為 = 。 醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例例 問：問： P P = P?從真值表，可以看出：從真值表，可以看出： P P = PP P P P TFTF=FFTFT=T考察真值表如下考察真值表如下醉雪醉雪風(fēng)隨心動風(fēng)隨心動 八組重要的等價(jià)公式 雙重否定律雙重否定律 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）醉雪醉雪風(fēng)隨心動風(fēng)隨心動 八組重要的等價(jià)公式交換律交換律 P Q= Q P P Q= Q P等冪律等冪律 P P = P P P = P P P = T P P = T醉雪醉雪風(fēng)隨心動風(fēng)隨心動 八組重要的等價(jià)公式等值公式等值公式 P Q = P Q P Q =（PQ） （Q P） =（ P Q） （P Q） =（P Q） （ P Q） （P Q）= PQ （P Q）= PQ醉雪醉雪風(fēng)隨心動風(fēng)隨心動 八組重要的等價(jià)公式 部份解釋部份解釋 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?醉雪醉雪風(fēng)隨心動風(fēng)隨心動 八組重要的等價(jià)公式吸收律吸收律 P （P Q）= P P （P Q）= P醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例 判斷下列公式的類型 q ( pq) p)解解: 考察真值表考察真值表 所以，它是永真的所以，它是永真的。 pqA= pqB=ApC= BqCTTTTFTTFFFTTFTTFTTFFTFTT醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例 判斷下列公式的類型 q ( pq) p)解解: q ( pq) p) =q( ( pq) ) p =(q p )( ( pq) ) =T 所以，它是永真的所以，它是永真的。 醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例 判斷下列公式的類型

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

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

24、醉雪風(fēng)隨心動風(fēng)隨心動 解解2：否定深入：否定深入 原式原式 = ( P Q)( QP)R) 對對P=F進(jìn)行解釋并化簡。進(jìn)行解釋并化簡。 原式原式=（ FQ）（ QF）R） = （ QF）R = Q R Q=T 時(shí)，時(shí)， 原式原式 =TR = R， 于是于是 R=T 時(shí)，原式時(shí)，原式=F R=F 時(shí)，原式時(shí)，原式=T 因此因此,公式存在成真解釋公式存在成真解釋 (P，Q，R)=(F，T，F(xiàn)) ； 公式存在成假解釋公式存在成假解釋(P，Q，R)=(F，T，T)。 故公式可滿足但非永真。故公式可滿足但非永真。醉雪醉雪風(fēng)隨心動風(fēng)隨心動 解解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醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例例 試求下列公式的成真解釋和成假解釋試求下列公式的成真解釋和成假解釋 （PQ） （Q （ R P）解解:當(dāng)當(dāng)P=T時(shí)

26、時(shí), 原式原式= (TQ) (Q ( R T) = Q (Q ( R)= QR 當(dāng)當(dāng)P=F時(shí)時(shí), 原式原式= (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*).醉雪醉雪風(fēng)隨心動風(fēng)隨心動 第一章第一章 命題演算基礎(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、等價(jià)公式等價(jià)公式 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)用醉雪醉雪風(fēng)隨心動風(fēng)隨心動 聯(lián)結(jié)詞的完備集 定義定義 設(shè)設(shè)S是聯(lián)結(jié)詞的集合，如果是聯(lián)結(jié)詞的集合，如果 對任何命題演算公式均可以由對任何命題演算公式均可以由S中的聯(lián)中的聯(lián)結(jié)詞表示出來的公式與之等價(jià)結(jié)詞表示出來的公式與之等價(jià)， 則說則說S是聯(lián)結(jié)詞的完備集。是聯(lián)結(jié)詞的完備集。由聯(lián)結(jié)詞的定義知，聯(lián)結(jié)詞集合由聯(lián)結(jié)詞的定義知，聯(lián)結(jié)詞集合 ， ， ，是完備的。是完備的。 醉雪醉雪風(fēng)隨心動風(fēng)隨心動 定理1 聯(lián)結(jié)詞的集合聯(lián)結(jié)詞的集合 ， ， 是完備的。

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

29、 P Q）醉雪醉雪風(fēng)隨心動風(fēng)隨心動 定理定理 聯(lián)結(jié)詞的集合聯(lián)結(jié)詞的集合 ， 是完備的。是完備的。思路思路: 去等價(jià)詞、析取詞、合取詞：去等價(jià)詞、析取詞、合取詞： PQ =（ PQ ） （ PQ ） P Q= PQ PQ = （ P Q）= （P Q） 醉雪醉雪風(fēng)隨心動風(fēng)隨心動 與非與非: 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）醉雪醉雪風(fēng)隨心動風(fēng)隨心動 或非：或非： 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）醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例例(p8) 試證明聯(lián)結(jié)詞集合試證明聯(lián)結(jié)詞集合不完備。不完備。證明：證明： 對于任意公式對于任意公式P， P也是公式也是公式 。 假設(shè)假設(shè)是完備的。根據(jù)完備性的定義知，是完備的。根據(jù)完備性的定義知， P = Q1 Q2 Q3 Qn 當(dāng)當(dāng)P，Q1, Q2, Q3, , Qn全取為真時(shí)，全取為真時(shí)，公式左邊公式左邊=F，公式右邊，公式右邊=T。 顯然矛盾。顯然矛盾。 故聯(lián)結(jié)詞集合故聯(lián)結(jié)詞集合

31、不完備。不完備。 醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例例 試證明聯(lián)結(jié)詞集合試證明聯(lián)結(jié)詞集合不完備。不完備。證明：證明： 對于任意公式對于任意公式P， P也是公式也是公式 。 假設(shè)假設(shè)是完備的。根據(jù)完備性的定義知，是完備的。根據(jù)完備性的定義知， P = Q1 Q2 Q3 Qn 當(dāng)當(dāng)P，Q1, Q2, Q3, , Qn全取為假時(shí)，全取為假時(shí)，公式左邊公式左邊=T，公式右邊，公式右邊=F。 顯然矛盾。顯然矛盾。 故聯(lián)結(jié)詞集合故聯(lián)結(jié)詞集合不完備。不完備。 醉雪醉雪風(fēng)隨心動風(fēng)隨心動 第一章第一章 命題演算基礎(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 等價(jià)公式等價(jià)公式 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)用醉雪醉雪風(fēng)隨心動風(fēng)隨心動 對偶式對偶式的定義 定義：將任何一個(gè)定義：將任何一個(gè)不含不含蘊(yùn)含詞和等價(jià)詞的命題蘊(yùn)含詞和等價(jià)詞的命題演算公式演算公式 中的中的 換為換為 ， 換為換為 后所得的公式稱為后所得的公式稱為 的的對偶式對偶式， 記為記為 *。 醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例例 已知公式已知公式 = P （QR）, 求對偶式求對偶式 *、 （ *）* 。解：解： = P （QR） *= P （Q

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

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

35、分為下面三種情形：可分為下面三種情形： A= A1， A=A1 A2， A=A1 A2 其中其中A1，A2中的聯(lián)結(jié)詞個(gè)數(shù)中的聯(lián)結(jié)詞個(gè)數(shù) k 。 依歸納假設(shè)依歸納假設(shè) A1= A1* ， A2= A2* 。 對于上述三種情形，可以分別證明結(jié)論成立：對于上述三種情形，可以分別證明結(jié)論成立： A =A*。 由數(shù)學(xué)歸納法知，定理得證。由數(shù)學(xué)歸納法知，定理得證。醉雪醉雪風(fēng)隨心動風(fēng)隨心動 第一章第一章 命題演算基礎(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)用醉雪醉雪風(fēng)隨心動風(fēng)隨心動 合取式、析取式合取式、析取式定義定義1 命題變元、或者命題變元的否定、或由它們命題變元、或者命題變元的否定、或由它們利用合取詞組成的合式公式稱為利用合取詞組成的合式公式稱為合取式合取式。定義定義2 命題變元、或者命題變元的否定、或由它們命題變元、或者命題變元的否定、或由它們利用析取詞組成的合式公式稱為利用析取詞組成的合式公式稱為析取式析取式。例例 顯然，顯然， P， P，P Q， P QR 均為合取式；均為合取式； P， P，P Q， P QR 均為析取式。均為析取式。醉雪醉雪風(fēng)隨心動風(fēng)隨心動 (一一) 解釋與合取式、析取

37、式之間的關(guān)系解釋與合取式、析取式之間的關(guān)系 定理定理1 任給一個(gè)成真解釋有且僅有一個(gè)合取式任給一個(gè)成真解釋有且僅有一個(gè)合取式與之對應(yīng)；與之對應(yīng)； 任給一個(gè)成假解釋有且僅有任給一個(gè)成假解釋有且僅有一個(gè)析取式與之對應(yīng)。一個(gè)析取式與之對應(yīng)。 反之亦然。反之亦然。例例 成真解釋成真解釋(P，Q，R)= (T,F,T) 成假解釋成假解釋(P，Q，R)= (F,F,T)合取式合取式PQ R析取式析取式P QR醉雪醉雪風(fēng)隨心動風(fēng)隨心動 析取范式、合取范式析取范式、合取范式定義定義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)均為合取范式。均為合取范式。醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例例: 考察公式考察公式 =PQ的的析取范式析取范式有兩個(gè)成真解釋：有兩個(gè)成真解釋： (T, T), (F, F), 分別對應(yīng)于兩個(gè)合取式為分別對應(yīng)于兩個(gè)合取式為 PQ, P Q于是，有于是，有 = (PQ) ( P Q)P Q P QT T TT F FF T FF F T醉雪醉雪風(fēng)隨心動

39、風(fēng)隨心動 例例: 考察公式考察公式 =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醉雪醉雪風(fēng)隨心動風(fēng)隨心動 定理定理2 任何命題演算公式均可以化為合任何命題演算公式均可以化為合取范式，也可以化為析取范式。取范式，也可以化為析取范式。證明：證明： (1)設(shè)公式設(shè)公式 為永真公式為永真公式 =PP (2)設(shè)公式設(shè)公式 為永假公式為永假公式 =P P醉雪醉雪風(fēng)隨心動風(fēng)隨心動 證明證明(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ù)兩個(gè)公式邏輯等價(jià)的定義兩個(gè)公式邏輯等價(jià)的定義知知 = 12 n = 12 t故公式故公式 既可表示為析取范式又可表示為合取范式。既可表示為析取范式又可表

41、示為合取范式。醉雪醉雪風(fēng)隨心動風(fēng)隨心動 (二二) 析取范式和合取范式的求解方法析取范式和合取范式的求解方法 等價(jià)變換法等價(jià)變換法解釋法解釋法醉雪醉雪風(fēng)隨心動風(fēng)隨心動 等價(jià)變換法等價(jià)變換法(1)去蘊(yùn)含詞與等價(jià)詞：去蘊(yùn)含詞與等價(jià)詞： 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)醉雪醉雪風(fēng)隨心動風(fēng)隨心動 解釋法解釋法(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)成合取范式。醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例例 求公式的范式求公式的范式 (PQ)(RQ)P)解解：原式原式= ( P Q)( ( RQ)P) =(PQ) ( RQ) P) =(PQ) (PR) (PQ) =(PQ) (PR) 析取范式析取范式 = P ( QR) 合取范式合取范式醉雪醉雪風(fēng)隨心動風(fēng)隨心動 解：解：P=T時(shí)時(shí), 原式原式

43、= (TQ) (RQ)T) = Q R P=F時(shí)時(shí), 原式原式= (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醉雪醉雪風(fēng)隨心動風(fēng)隨心動 范式不唯一性范式不唯一性例例 求公式的范式求公式的范式 (PQ)(RQ)P)解解1： 原式原式=(PQ) (PR) 析取范式

44、析取范式 = P ( QR) 合取范式合取范式解解2: 析取范式為析取范式為: (PQ R) (P Q R) (P Q R) 合取范式為：合取范式為： ( P QR) P醉雪醉雪風(fēng)隨心動風(fēng)隨心動 第一章第一章 命題演算基礎(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)用醉雪醉雪風(fēng)隨心動風(fēng)隨心動 (一一) 主析取范式主析取范式定義定義1 對于對于n個(gè)命題變元個(gè)命題變元P1，P2，Pn，公式，公式 Q1 Q2

45、 Qn 稱為稱為極小項(xiàng)極小項(xiàng)，其中，其中Qi=Pi或或 Pi(i=1，n)。例例 由兩個(gè)命題變元由兩個(gè)命題變元P，Q組成的極小項(xiàng)有四個(gè)，它們組成的極小項(xiàng)有四個(gè)，它們分別為：分別為： PQ P QPQ P Q醉雪醉雪風(fēng)隨心動風(fēng)隨心動 三個(gè)命題變元三個(gè)命題變元P、Q和和R可構(gòu)造可構(gòu)造8個(gè)極小項(xiàng)個(gè)極小項(xiàng)把命題變元的否定形式看成把命題變元的否定形式看成0，肯定形式看成，肯定形式看成1，則每，則每個(gè)極小項(xiàng)對應(yīng)一個(gè)二進(jìn)制數(shù)，也對應(yīng)一個(gè)十進(jìn)制數(shù)。個(gè)極小項(xiàng)對應(yīng)一個(gè)二進(jìn)制數(shù)，也對應(yīng)一個(gè)十進(jìn)制數(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醉雪醉雪風(fēng)隨心動風(fēng)隨心動 n個(gè)命題變元組成的極小項(xiàng)有個(gè)命題變元組成的極小項(xiàng)有2n個(gè)個(gè) 公式的每一個(gè)完全成真解釋對應(yīng)一個(gè)極小項(xiàng)公式的每一個(gè)完全成真解釋對應(yīng)一個(gè)極小項(xiàng) 公式的所有完全成真解釋對應(yīng)極小項(xiàng)的析取公式的所

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

48、真解釋對應(yīng)的合取式，所有合取式的析取就為公式的主析取范式。公式的主析取范式。(2)等價(jià)變換法等價(jià)變換法: 將析取范式中的每一個(gè)合取式用將析取范式中的每一個(gè)合取式用AA填填滿命題變元，然后用等價(jià)公式進(jìn)行變換，消去相滿命題變元，然后用等價(jià)公式進(jìn)行變換，消去相同部分，即得公式的主析取范式。同部分，即得公式的主析取范式。醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例例 求公式的求公式的主析取范式 (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醉雪醉雪風(fēng)隨心動風(fēng)隨心動 解：解：P=T時(shí)時(shí), 原式原式= (TQ) (RQ)T) = Q R P=F時(shí)時(shí), 原式原式= (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醉雪醉雪風(fēng)隨心動風(fēng)隨心動 (二二) 主合取范式主合取范式定義定義3 對于對于n個(gè)命變元個(gè)命變元P1

50、，P2，Pn，公式，公式 Q1 Q2 Qn 稱為稱為極大項(xiàng)極大項(xiàng)，其中，其中Qi=Pi或或 Pi(i=1，n)。例例 由兩個(gè)命題變元由兩個(gè)命題變元P，Q組成的極大項(xiàng)有四個(gè)，它們組成的極大項(xiàng)有四個(gè)，它們分別為：分別為： PQ P Q PQ P Q醉雪醉雪風(fēng)隨心動風(fēng)隨心動 三個(gè)命題變元三個(gè)命題變元P、Q和和R可構(gòu)造可構(gòu)造8個(gè)極大項(xiàng)個(gè)極大項(xiàng) 把命題變元的否定形式看成把命題變元的否定形式看成1，肯定形式看成，肯定形式看成0，則每個(gè)，則每個(gè)極大項(xiàng)對應(yīng)一個(gè)二進(jìn)制數(shù)，也對應(yīng)一個(gè)十進(jìn)制數(shù)。它們極大項(xiàng)對應(yīng)一個(gè)二進(jìn)制數(shù)，也對應(yīng)一個(gè)十進(jìn)制數(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醉雪醉雪風(fēng)隨心動風(fēng)隨心動 n個(gè)命題變元組成的極大項(xiàng)有個(gè)命題變元組成的極大項(xiàng)有2n個(gè)個(gè) 公式的每一個(gè)完全成假解釋對應(yīng)一個(gè)極大項(xiàng)公式的每一個(gè)完全成假解釋對應(yīng)一個(gè)極大項(xiàng) 公式的所

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

53、解釋，求出與這些成假解釋對應(yīng)的析取式，所有析取式的合取就為成假解釋對應(yīng)的析取式，所有析取式的合取就為公式的主合取范式。公式的主合取范式。(2)等價(jià)變換法等價(jià)變換法 將合取范式中的每一個(gè)析取式用將合取范式中的每一個(gè)析取式用AA填滿命題變元，然后用等價(jià)公式進(jìn)行變換，消去填滿命題變元，然后用等價(jià)公式進(jìn)行變換，消去相同部份，即得公式的主合取范式。相同部份，即得公式的主合取范式。醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例例 求公式的主合取范式求公式的主合取范式 (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醉雪醉雪風(fēng)隨心動風(fēng)隨心動 解：解：P=T時(shí)時(shí), 原式原式= (TQ) (RQ)T) = Q R P=F時(shí)時(shí), 原式原式= (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)醉雪醉雪風(fēng)隨心動風(fēng)隨心動 例例 試求試求 =(PR)( P ( Q R) 的主析取范式和主合取范式的主析取范式和主合取范式解解: =( PR) ( P( QR)(P( ( QR)（去蘊(yùn)涵詞、等價(jià)詞）（去蘊(yùn)涵詞、等價(jià)詞） =( PR) ( P QR) (PQ) (P R)（化簡）（化簡） =(P R) ( P QR) (PQ) (P R)（去蘊(yùn)涵詞）（去蘊(yùn)涵詞） = (P R) ( P QR)(PQ) =(110 100) 001 (111 110)=(1,4,6,7)醉雪醉雪風(fēng)隨心動風(fēng)隨心動 解解(續(xù)續(xù)): 已經(jīng)得到已經(jīng)得到主析取范式如下主析取范式如下: = ( P QR)(PQ)(P R)=( PP)( PQ)( QP) ( QQ)(PR)(QR)(P R) =( PQ)( QP)(PR)(QR)