第3章_命題邏輯

1、123項目： 1. ?？蒲许椖?，直覺模糊滿意度模型與應(yīng)用 (編號：12SKY009)已結(jié)題。 2. ?？蒲许椖?，基于直覺模糊聚類分析的電子作業(yè)抄襲檢測研究(編號：13SKY009)已結(jié)題。 3. 校教改項目，地方院校離散數(shù)學(xué)課計算機基礎(chǔ)性及應(yīng)用性研究(編號：14SJYX013)，在研。 教學(xué)：主要承擔(dān)C語言、計算機基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)等課程教學(xué)。4章節(jié)章節(jié)主要內(nèi)容主要內(nèi)容各教學(xué)環(huán)節(jié)學(xué)時分配各教學(xué)環(huán)節(jié)學(xué)時分配備注備注講授講授實驗實驗討論討論習(xí)題習(xí)題課外課外其它其它小計小計1命題邏輯命題邏輯6282一階邏輯一階邏輯6283集合的基本概念和運算集合的基本概念和運算4264二元關(guān)系和函數(shù)二元關(guān)系和

2、函數(shù)6285圖的基本概念圖的基本概念606合計合計28836l離散數(shù)學(xué)離散數(shù)學(xué)(又稱計算機數(shù)學(xué)計算機數(shù)學(xué))是現(xiàn)代數(shù)學(xué)的重要分支，是計算機專業(yè)核心基礎(chǔ)課程之一。l離散數(shù)學(xué)是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫原理、數(shù)字邏輯、編譯原理、人工智能、信息安全等課程的前續(xù)課程，同時以計算機導(dǎo)論和程序設(shè)計基礎(chǔ)作為離散數(shù)學(xué)的先導(dǎo)課程。5l離散數(shù)學(xué)是計算機應(yīng)用的必不可少的工具。例如數(shù)理邏輯在數(shù)據(jù)模型、計算機語義、人工智能等方面的應(yīng)用，集合論在數(shù)據(jù)庫技術(shù)中的應(yīng)用，代數(shù)系統(tǒng)在信息安全中的密碼學(xué)方面的應(yīng)用，圖論在信息檢索、網(wǎng)絡(luò)布線、指令系統(tǒng)優(yōu)化等方面的應(yīng)用。67定義、定理多。 本課內(nèi)容定義定義定理定理例題例題為了學(xué)好這門課，要求： (

3、1) 弄懂定義、定理，弄懂例題，加深對定義、定理的理解； (2) 在課后復(fù)習(xí)基礎(chǔ)上，做好作業(yè)。同學(xué)之間可以討論，但要弄懂弄通。 (3)做好課堂筆記。8離散數(shù)學(xué)離散數(shù)學(xué)授課教師：魚先鋒命題符號化及聯(lián)結(jié)詞命題符號化及聯(lián)結(jié)詞命題公式及分類命題公式及分類等值演算等值演算聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集對偶與范式對偶與范式推理理論推理理論10邏輯學(xué)：邏輯學(xué)： 研究推理的一門學(xué)科研究推理的一門學(xué)科數(shù)理邏輯：數(shù)理邏輯： 用數(shù)學(xué)方法研究推理的一門數(shù)學(xué)學(xué)科用數(shù)學(xué)方法研究推理的一門數(shù)學(xué)學(xué)科一套符號體系一套符號體系+一組規(guī)則一組規(guī)則11數(shù)理邏輯的內(nèi)容：數(shù)理邏輯的內(nèi)容： 古典數(shù)理邏輯：古典數(shù)理邏輯： 命題邏輯、謂詞邏輯命

4、題邏輯、謂詞邏輯 現(xiàn)代數(shù)理邏輯：現(xiàn)代數(shù)理邏輯： 邏輯演算、公理化集合論、遞邏輯演算、公理化集合論、遞歸論、模型論、證明論歸論、模型論、證明論12命題命題(Proposition)： 一個有確定真或假意義的陳述句。一個有確定真或假意義的陳述句。命題符號化及聯(lián)結(jié)詞命題符號化及聯(lián)結(jié)詞13EXAMPLE 1 下列句子都是命題：下列句子都是命題： 1. 華盛頓是美國的首都。華盛頓是美國的首都。 2. 多倫多是加拿大的首都。多倫多是加拿大的首都。 3. 1+1=2。 4. 2+2=3。 命題命題1和和3是真命題，是真命題，2和和4是假命題。是假命題。14EXAMPLE 2 考慮如下句子：考慮如下句子： 1

5、. 現(xiàn)在幾點了？現(xiàn)在幾點了？ 2. 認真閱讀一下。認真閱讀一下。 3. x+1=2. 4. x+y=z. 句子句子1和和2不是命題，因為它們都不是陳述句。不是命題，因為它們都不是陳述句。句子句子3和和4不是命題，由于不是命題，由于x，y和和z的值不確定，的值不確定，使得它們的真值都不唯一。使得它們的真值都不唯一。15命題的語句形式：命題的語句形式： 陳述句陳述句非命題語句：非命題語句： 疑問句、命令句、感嘆句、疑問句、命令句、感嘆句、 非命題陳述句：悖論語句（真值不唯一）非命題陳述句：悖論語句（真值不唯一）莊子莊子天下篇天下篇中提到：中提到：“一尺之棰，日取其半，一尺之棰，日取其半，萬世不竭。

6、萬世不竭?！?6命題的符號表示：命題的符號表示： 大小寫英文字母：大小寫英文字母：P、Q、R、 p 、q 、r命題真值命題真值(Truth Values)的表示：的表示： 真：真：T、1 假：假：F、017命題語句真值確定的幾點說明：命題語句真值確定的幾點說明： 1、時間性、時間性 2、區(qū)域性、區(qū)域性 3、標準性、標準性命題真值間的關(guān)系表示：命題真值間的關(guān)系表示： 真值表真值表(Truth Table) 18DEFINITION 1. 設(shè)設(shè)p為任一命題，復(fù)合命題為任一命題，復(fù)合命題“非非p”（或（或“p的否定的否定”）稱為）稱為p的的否定式否定式。記作。記作 p 。 為為否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞。

7、真值表見。真值表見Table 1。(Let p be a proposition. The statement “It is not the case that p.” is another proposition, called the negation of p. The negation of p is denoted by p. The proposition p is read “not p.”)p的否定的否定19Table 1 20EXAMPLE 3 設(shè)設(shè)p表示表示“離散數(shù)學(xué)好學(xué)離散數(shù)學(xué)好學(xué)”，則則 p表示表示“離散數(shù)學(xué)難學(xué)離散數(shù)學(xué)難學(xué)”。顯然，當顯然，當p的真值為的真值為0時，時

8、， p的的真值為真值為1。21設(shè)設(shè)p，q為兩命題，復(fù)合命題為兩命題，復(fù)合命題“p并且并且q”（或（或“p和和q”）稱作）稱作p與與q的的合取式合取式。記作。記作pq。 為為合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞。真值表見。真值表見Table 2。(Let p and q be propositions. The proposition p and q, denoted by pq, is the proposition that is true when both p and q are true and is false otherwise. The proposition pq is called the

9、conjunction of p and q. )p和和q的合取的合取DEFINITION 2. 22Table 2 23EXAMPLE 4 用用p表示命題表示命題“今天是星期五今天是星期五”，q表示命題表示命題“今天下雨今天下雨”， 則命題則命題p與與q的合取式是什么？的合取式是什么？解答：解答： p與與q的合取式的合取式 pq是是“今天是星期五，而今天是星期五，而且今天下雨。且今天下雨。”如果是星期五，又下雨，則該如果是星期五，又下雨，則該命題為真；如果是除星期五外的任意一天，或命題為真；如果是除星期五外的任意一天，或者雖是星期五但沒下雨，則該命題為假。者雖是星期五但沒下雨，則該命題為假。

10、24設(shè)設(shè)p，q為兩命題，復(fù)合命題為兩命題，復(fù)合命題“p或或q” 稱作稱作p與與q的的析取式析取式。記作。記作pq。為為析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞。真值表見真值表見Table 3。 (Let p and q be propositions.The proposition p or q, denoted by pq,is the proposition that is false when p and q are both false and true otherwise. The proposition pq is called the disjunction of p and q.)p和和q的析取的

11、析取DEFINITION 3. 25Table 3 26還是以還是以Example 4 為例，命題為例，命題p與與q的析取式是什么？的析取式是什么？解答：解答： p與與q的析取式的析取式 pq是是“今天是星期五或今天今天是星期五或今天下雨。下雨?！敝挥薪裉旒炔皇切瞧谖?，又沒有下雨，只有今天既不是星期五，又沒有下雨，則該命題為假；如果今天是星期五或者今天下雨則該命題為假；如果今天是星期五或者今天下雨了（包括下雨的星期五），則該命題就為真。了（包括下雨的星期五），則該命題就為真。EXAMPLE 5 27設(shè)設(shè)p，q為兩命題，復(fù)合命題為兩命題，復(fù)合命題“如果如果p，則，則q”稱作稱作p與與q的的蘊含式

12、蘊含式。 記作記作 pq。稱。稱p為蘊為蘊含式的含式的前件前件(hypothesis)，q為蘊含式的為蘊含式的后后件件(conclusion)。稱作稱作蘊含聯(lián)結(jié)詞蘊含聯(lián)結(jié)詞。真值。真值表見表見Table 4。(Let p and q be propositions.The implication pq is the proposition that is false when p is true and q is false and true otherwise. )如果如果p，則，則q單條件，單條件， 蘊涵蘊涵p：前提：前提 q：結(jié)論：結(jié)論DEFINITION 4. 28Table 4 29

13、 用用p表示命題表示命題“天下雨天下雨”，用，用q表示命題表示命題“我騎自行車上班我騎自行車上班”，將下列命題符號化：，將下列命題符號化： （1）只要不下雨，我就騎自行車上班。）只要不下雨，我就騎自行車上班。 （2）只有不下雨，我才騎自行車上班。）只有不下雨，我才騎自行車上班。解答：解答： （1）中，）中， p是是q的充分條件，因而符號化為的充分條件，因而符號化為 pq；（2）中，）中， p是是q的必要條件，因而符號化為的必要條件，因而符號化為q p。EXAMPLE 6 30設(shè)設(shè)p，q為兩命題，復(fù)合命題為兩命題，復(fù)合命題“p當且僅當當且僅當q”稱稱作作p與與q的的等價式等價式。記作。記作pq，

14、稱作稱作等價聯(lián)結(jié)等價聯(lián)結(jié)詞詞。真值表見。真值表見Table 5。(Let p and q be propositions, The biconditional pq is the proposition that is true when p and q have the same truth values and is false otherwise.)p當且僅當當且僅當q雙條件，等價雙條件，等價DEFINITION 5. 31Table 5 32將下一命題符號化：將下一命題符號化： “只有（僅當）只有（僅當）你是計算機科學(xué)系的學(xué)你是計算機科學(xué)系的學(xué)生或者你不是新生，你才可以通過校園網(wǎng)生或者

15、你不是新生，你才可以通過校園網(wǎng)上上Internet?！苯獯穑航獯穑?a (cf )EXAMPLE 7 cfa33 將下一命題符號化：將下一命題符號化：“如果你身高如果你身高小于小于4英尺英尺，你就不，你就不能乘能乘坐過山車坐過山車，除非你，除非你超過了超過了16歲歲?！苯獯穑航獯穑?1) (r s) q.(2) s(r q).EXAMPLE 8 rqs如果你身高小于如果你身高小于4英尺，而英尺，而且你不超過且你不超過16歲，那么你就歲，那么你就不能乘坐過山車。不能乘坐過山車。如果你不超過如果你不超過16歲，那么歲，那么當你身高小于當你身高小于4英尺時，你英尺時，你就不能乘坐過山車。就不能乘坐過

16、山車。34“說離散數(shù)學(xué)是枯燥無味的或毫無價值說離散數(shù)學(xué)是枯燥無味的或毫無價值的，那是不對的。的，那是不對的?！眕：離散數(shù)學(xué)是有味道的；：離散數(shù)學(xué)是有味道的；q：離散數(shù)學(xué)是有價值的；：離散數(shù)學(xué)是有價值的；EXAMPLE 9 符號化為：符號化為：( p q)35命題公式及分類命題公式及分類P、Q、R 稱為稱為原子命題原子命題(Atomic Proposition)。原子命題或加上邏輯聯(lián)結(jié)詞組成的表達式成為原子命題或加上邏輯聯(lián)結(jié)詞組成的表達式成為復(fù)合命題復(fù)合命題(Compositional Proposition)。從從命題常量命題常量 到到 命題變量命題變量(Propositional Varia

17、ble)命題公式：命題公式：1. 原子命題是命題公式；原子命題是命題公式；2. 設(shè)設(shè)P是命題公式，則是命題公式，則 P也是命題公式；也是命題公式；3. 設(shè)設(shè)P、Q是命題公式，則是命題公式，則(PQ)、(PQ)、(PQ)、(P Q)也是命題公式；也是命題公式；4. 有限次地使用有限次地使用1、2、3所得到的也是命題公式。所得到的也是命題公式。Proposition Formulas, Well-Formed Formulas(wff)36命題公式的運算規(guī)則：命題公式的運算規(guī)則： 邏輯聯(lián)接詞的優(yōu)先級：邏輯聯(lián)接詞的優(yōu)先級： 、 、 、 、 命題公式的表達式的運算規(guī)律：命題公式的表達式的運算規(guī)律： 同

18、代數(shù)表達式同代數(shù)表達式命題公式的運算方法：命題公式的運算方法： 所有公式中的命題變量用指定命題（真值）代所有公式中的命題變量用指定命題（真值）代入（或指派），得到一個公式對應(yīng)的真值。入（或指派），得到一個公式對應(yīng)的真值。如果一個命題公式有如果一個命題公式有n個互異的命題變量，個互異的命題變量，則命題公式對應(yīng)的真值有則命題公式對應(yīng)的真值有2n種可能分布。種可能分布。37EXAMPLE 10 求下列命題公式的真值表：求下列命題公式的真值表：（1）p (q r ) .38EXAMPLE 10 求下列命題公式的真值表：求下列命題公式的真值表：（2）( p ( pq ) q .39EXAMPLE 10

19、求下列命題公式的真值表：求下列命題公式的真值表：（3） ( pq ) q .40永真式永真式(Tautology)：公式中的命題變量無論怎樣公式中的命題變量無論怎樣代入，公式對應(yīng)的真值恒為代入，公式對應(yīng)的真值恒為1。 永假式永假式(Contradiction)：公式中的命題變量無論公式中的命題變量無論怎樣代入，公式對應(yīng)的真值恒為怎樣代入，公式對應(yīng)的真值恒為0。 可滿足式可滿足式(Satisfaction)：公式中的命題變量無論公式中的命題變量無論怎樣代入，公式對應(yīng)的真值總有一種情況為怎樣代入，公式對應(yīng)的真值總有一種情況為1。41 （1）設(shè)）設(shè)P是永真命題公式，則是永真命題公式，則P的否定的否定

20、公式是永假命題公式；公式是永假命題公式； （2）設(shè)）設(shè)P是永假命題公式，則是永假命題公式，則P的否定的否定公式是永真命題公式；公式是永真命題公式； （3）設(shè)）設(shè)P、Q是永真命題公式，則是永真命題公式，則 (PQ)、(PQ)、(PQ)、(P Q)也是也是永真命題公式永真命題公式 。 42小小 結(jié)結(jié)1. 命題的概念：定義、邏輯值、命題的概念：定義、邏輯值、 符號化表示符號化表示2. 從簡單命題到復(fù)合命題：從簡單命題到復(fù)合命題： 邏輯聯(lián)接詞：運算方法、運算優(yōu)先級邏輯聯(lián)接詞：運算方法、運算優(yōu)先級3. 從命題常量到命題變量，從命題常量到命題變量， 從復(fù)合命題到命題公式：從復(fù)合命題到命題公式： 命題公式的

21、真值描述：真值表命題公式的真值描述：真值表4. 命題公式的分類：命題公式的分類： 永真公式、永假公式、可滿足公式永真公式、永假公式、可滿足公式 、一般公式、一般公式 43Propositional Equivalences設(shè)設(shè)A，B為兩命題公式，若等價式為兩命題公式，若等價式AB是重是重言式，則稱言式，則稱A與與B是是等值等值的。記作的。記作AB。(The propositions A and B are called logically equivalent if AB is a tautology. The notation AB denotes that A and B are logi

22、cally equivalent.)邏輯等值，或邏輯等價邏輯等值，或邏輯等價DEFINITION 6. 等值演算等值演算44證明證明( pq )與與pq 是等值的。是等值的。（這個等值關(guān)系是德（這個等值關(guān)系是德摩根摩根(De Morgan)定律之定律之一。德一。德摩根是十九世紀中葉的英國數(shù)學(xué)家。）摩根是十九世紀中葉的英國數(shù)學(xué)家。）解答：真值表見解答：真值表見Table 9。因為對于。因為對于p和和q 所所有可能的組合，有可能的組合， (pq)和和pq的真的真值都相同，所以這兩個命題是等值的。值都相同，所以這兩個命題是等值的。EXAMPLE 11 45Table 9 46證明證明pq與與pq是等

23、值的。是等值的。解答：真值表見解答：真值表見Table 10。因為對于。因為對于p和和q 所有可能的組合，所有可能的組合， pq 和和pq的真值的真值都相同，所以這兩個命題是等值的。都相同，所以這兩個命題是等值的。EXAMPLE 12 47Table 10 48證明證明p(qr)與與 (pq)(pr) 是等是等值的。值的。（分配律）（分配律）解答：真值表見解答：真值表見Table 11。因為對于。因為對于p、q和和r所有可能的組合，所有可能的組合， p(qr) 和和(pq)(pr) 的真值都相同，所以這兩個命題是等值的。的真值都相同，所以這兩個命題是等值的。EXAMPLE 13 49Table

24、 11 50 下面給出下面給出24個重要的等值式個重要的等值式（祥見（祥見P40）：）：雙重否定律、等冪律、交換律、結(jié)合律、分配律、雙重否定律、等冪律、交換律、結(jié)合律、分配律、德德摩根律、吸收律、零律、同一律、排中律、矛摩根律、吸收律、零律、同一律、排中律、矛盾式、蘊含等值式、等價等值式、假言易位、等盾式、蘊含等值式、等價等值式、假言易位、等價否定等值式、歸謬論。價否定等值式、歸謬論。根據(jù)已知的等值式，推演出另外一些等值式根據(jù)已知的等值式，推演出另外一些等值式的過程稱為的過程稱為等值演算等值演算。在進行等值演算時，往往。在進行等值演算時，往往用到用到置換規(guī)則置換規(guī)則。51證明證明(p(pq)與

25、與pq是等值的。是等值的。EXAMPLE 14 0052證明證明(pq) (pq)是重言式。是重言式。EXAMPLE 15 11153判斷命題公式邏輯等價的方法：判斷命題公式邏輯等價的方法： 1. 真值表真值表 2. 命題公式的演算命題公式的演算 基本等值定理；基本等值定理； 公式的代入不變性（置換規(guī)則）；公式的代入不變性（置換規(guī)則）； 等值關(guān)系的傳遞性。等值關(guān)系的傳遞性。54命題公式邏輯等價關(guān)系的應(yīng)用：命題公式邏輯等價關(guān)系的應(yīng)用： 1、判定是否邏輯等價（等值）；、判定是否邏輯等價（等值）； 2、判斷是否為永真公式或永假公式；、判斷是否為永真公式或永假公式； 3、命題公式的化簡。、命題公式的化

26、簡。55設(shè)設(shè)p,q為兩命題，復(fù)合命題為兩命題，復(fù)合命題“p,q之中恰有一個成立之中恰有一個成立”稱為稱為p與與q的的排斥或排斥或或或異或異或。記作。記作p q， 稱作稱作排斥排斥或或或或異或聯(lián)結(jié)詞異或聯(lián)結(jié)詞。真值表見真值表見Table 12。(Let p and q be propositions.The exclusive or of p and q, denoted by p q,is the proposition that is true when exactly one of p and q is true and is false otherwise.)p和和q的異或的異或DEFI

27、NITION 7. 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集56Table 12 p q (p q)(pq)57設(shè)設(shè)p,q為兩命題，復(fù)合命題為兩命題，復(fù)合命題“p與與q的否定的否定”稱為稱為p與與q的的與非式與非式。記作。記作p q， 稱作稱作與與非聯(lián)結(jié)詞非聯(lián)結(jié)詞。真值表見真值表見Table 13。(Let p and q be propositions.The and not of p and q, denoted by p q, is the proposition that is false when p and q are both true and true otherwise. )p和和q的與

28、非的與非DEFINITION 8. 58Table 13 p q ( pq )59設(shè)設(shè)p,q為兩命題，復(fù)合命題為兩命題，復(fù)合命題“p或或q的否定的否定”稱為稱為p與與q的的或非式或非式。記作。記作p q， 稱作稱作或或非聯(lián)結(jié)詞非聯(lián)結(jié)詞。真值表見真值表見Table 14。(Let p and q be propositions.The or not of p and q, denoted by p q, is the proposition that is true when p and q are both false and false otherwise. )p和和q的或非的或非DEFIN

29、ITION 9. 60Table 14 p q ( pq )61邏輯聯(lián)結(jié)詞集是邏輯聯(lián)結(jié)詞集是功能完備集功能完備集(Functionally Complete Set)： 任一個命題公式都能夠等價于僅包含這些任一個命題公式都能夠等價于僅包含這些邏輯聯(lián)結(jié)詞聯(lián)結(jié)起來的公式。邏輯聯(lián)結(jié)詞聯(lián)結(jié)起來的公式。邏輯聯(lián)結(jié)詞集是邏輯聯(lián)結(jié)詞集是極小功能完備集極小功能完備集： 是功能完備集并且沒有冗余聯(lián)結(jié)詞。是功能完備集并且沒有冗余聯(lián)結(jié)詞。62例例1： 、 、 、 、是功能完備的，但不是是功能完備的，但不是極小功能完備的極小功能完備的。例例2： 、 、 是是極小功能完備的極小功能完備的。例例3： 、 、 是是極小功能完

30、備的極小功能完備的。63DEFINITION 10. 命題公式命題公式P的的對偶公式對偶公式(Dual)：將：將P中的中的 析取聯(lián)結(jié)詞換成合取聯(lián)結(jié)詞，析取聯(lián)結(jié)詞換成合取聯(lián)結(jié)詞， 合取聯(lián)結(jié)詞換成析取聯(lián)結(jié)詞，合取聯(lián)結(jié)詞換成析取聯(lián)結(jié)詞， 1換成換成0，0換成換成1（如果存在的話）。（如果存在的話）。記為記為P*.對偶與范式對偶與范式64對偶原理對偶原理(Duality Principle)： 設(shè)設(shè)P，Q是兩命題公式，如果是兩命題公式，如果 P Q， 則則 P* Q*。例：例：A： (P Q) Q B： P Q這里，這里， A B，分，分析是否析是否A* B*。65命題公式的標準化命題公式的標準化范式

31、范式小項小項(small item)/合取式合取式(conjunctive form): 若干個原子命題或其否定的合取。若干個原子命題或其否定的合取。大項大項(large item)/析取式析取式(disjunctive form): 若干個原子命題或其否定的析取。若干個原子命題或其否定的析取。析取范式析取范式(disjunctive normal form)： 若干個小項的析取。若干個小項的析取。合取范式合取范式(conjunctive normal form)： 若干個大項的合取。若干個大項的合取。66定理的證明思路：定理的證明思路： 1、消去對、消去對 、 來說冗余的聯(lián)結(jié)詞；來說冗余的聯(lián)

32、結(jié)詞； 2、將否定聯(lián)結(jié)詞移到命題變量的前面；、將否定聯(lián)結(jié)詞移到命題變量的前面； 3、消除多余的否定聯(lián)結(jié)詞；、消除多余的否定聯(lián)結(jié)詞； 4、利用分配律化成合取范式和析取范式。、利用分配律化成合取范式和析取范式。定理定理1：任意一個命題公式都存在與之等價的：任意一個命題公式都存在與之等價的 合取范式和析取范式。合取范式和析取范式。范式存在定理范式存在定理例：求（）（）的析取范式： 68令令A(yù)(a1、a2、an)是包含有是包含有n個變量的公式，個變量的公式，極小項極小項(extremal ):小項中恰包含小項中恰包含n個變量或其否定。個變量或其否定。極大項極大項(extremal ):大項中恰包含大項

33、中恰包含n個變量或其否定。個變量或其否定。主析取范式主析取范式(Unique disjunctive normal form): 若干個若干個極小項極小項的析取。的析取。主合取范式主合取范式(Unique conjunctive normal form): 若干個若干個極大項極大項的合取。的合取。69 以三個命題變項以三個命題變項p,q,r為例，可形成為例，可形成23=8個個極小項極小項，每個每個極小項極小項對應(yīng)一個二進制數(shù)，也對應(yīng)一個十進制數(shù)，對應(yīng)一個二進制數(shù)，也對應(yīng)一個十進制數(shù)，二進制數(shù)是該極小項的二進制數(shù)是該極小項的成真賦值成真賦值，十進制數(shù)可做該極，十進制數(shù)可做該極小項抽象表示法的角碼

34、。對應(yīng)情況如下：小項抽象表示法的角碼。對應(yīng)情況如下： pqr 0000，記作，記作m0； pqr 0011，記作，記作m1； pqr 0102，記作，記作m2； pqr 0113，記作，記作m3； pqr 1004，記作，記作m4； pqr 1015，記作，記作m5； pqr 1106，記作，記作m6； pqr 1117，記作，記作m7。主析取范式主析取范式：如：如m1m2m5可用可用 ( 1,2,5 )表示。表示。70 以三個命題變項以三個命題變項p,q,r為例，可形成為例，可形成23=8個個極大項極大項，每個每個極大項極大項對應(yīng)一個二進制數(shù)，也對應(yīng)一個十進制數(shù)，對應(yīng)一個二進制數(shù)，也對應(yīng)一個

35、十進制數(shù)，二進制數(shù)是該極大項的二進制數(shù)是該極大項的成假賦值成假賦值，十進制數(shù)可做該極，十進制數(shù)可做該極大項抽象表示法的角碼。對應(yīng)情況如下：大項抽象表示法的角碼。對應(yīng)情況如下： pqr 0000，記作，記作M0； pqr 0011，記作，記作M1； pqr 0102，記作，記作M2； pqr 0113，記作，記作M3； pqr 1004，記作，記作M4； pqr 1015，記作，記作M5； pqr 1106，記作，記作M6； pqr 1117，記作，記作M7。主合取范式主合取范式：如：如M0 M3 M6可用可用( 0,3,6 )表示。表示。（1）只要命題公式不是永假式，則一定可以根據(jù)該命題公式的

36、真值表直接寫出其主析取范式，其方法是找出該公式為“”的行，對應(yīng)寫出極小項的析取式，且一定是唯一的。（2）若命題公式是含有n個變元的永真式，則它的主析取范式一定含有2n個極小項。（3）若二個命題公式對應(yīng)的主析取范式相同，則此二個命題公式一定是等價的。（4）命題公式的主析取范式中極小項的個數(shù)一定等于對應(yīng)真值表中真值為“”的個數(shù)。討論（5）與命題公式等價的主合范式中極大項的個數(shù)等于其真值表中真值為“”的個數(shù)。由真值表找極大項的方法為：將表中值為“”的對應(yīng)真值指派中，把變元寫成否定，把變元的否定寫成變元。（6）只要命題公式不是永真式，則一定可以寫出對應(yīng)與其等價的唯一的主合取范式。（7）若命題公式為含有

37、個變元的永假式，則主合取范式包含了2n個極大項的合取式。（8）可用主合取范式判定二個命題公式是否等價。（9）已知一個命題公式的主析取范式，則一定可以直接寫出與其等價的主合取范式來。反之也行。例： （ ）（）（） 主析取范式 （ ） 主合取范式74EXAMPLE 16 求求pqr的主析取范式和主合取范式：的主析取范式和主合取范式：解：解：( pq )r (p q) ( r r) (r (p p) (p q r) (p q r) (p r) ( p r) (p q r) (p qr) (p r) (qq) ( p r) (qq)(p q r) (p qr) (p q r) (pq r) ( p q

38、 r) ( pq r)(p q r) (p qr) (pq r) ( p q r) ( pq r)m7 m6 m5 m3 m1 ( 1,3,5,6,7 )（主析取范式）（主析取范式）M0 M2 M4 ( 0,2,4) （主合取范式）（主合取范式）75小小 結(jié)結(jié)1、命題公式的等價演算、命題公式的等價演算2、命題公式的標準化描述、命題公式的標準化描述 表達、分類、判定、應(yīng)用表達、分類、判定、應(yīng)用76數(shù)理邏輯的主要任務(wù)是借助于數(shù)學(xué)的數(shù)理邏輯的主要任務(wù)是借助于數(shù)學(xué)的方法來研究方法來研究推理推理的邏輯。的邏輯。推理推理是從前題推出結(jié)論的思維過程，是從前題推出結(jié)論的思維過程，前提前提是已知的命題公式，是已

39、知的命題公式，結(jié)論結(jié)論是從前題出是從前題出發(fā)應(yīng)用推理規(guī)則推出的命題公式。發(fā)應(yīng)用推理規(guī)則推出的命題公式。推理理論推理理論77DEFINITION 11. 若若A1A2AkB為重言式，則稱從為重言式，則稱從A1, A2, , Ak推出結(jié)論推出結(jié)論B的的推理正確推理正確，記作，記作A1A2AkB。B是是A1, A2, , Ak的的邏邏輯結(jié)論輯結(jié)論或或有效結(jié)論有效結(jié)論。稱稱A1A2AkB為推理的為推理的形式結(jié)構(gòu)形式結(jié)構(gòu)。78判斷推理是否正確的方法有以下幾種：判斷推理是否正確的方法有以下幾種： （1）真值表法；）真值表法； （2）等值演算法；）等值演算法； （3）主析取范式法。）主析取范式法。（即判斷（

40、即判斷A1A2AkB是否為重言式）是否為重言式）79EXAMPLE 17 判斷下列推理是否正確：判斷下列推理是否正確：如果天氣涼快，小王如果天氣涼快，小王就不去游泳，天氣涼快，所以小王沒去游泳。就不去游泳，天氣涼快，所以小王沒去游泳。 解這類推理問題，應(yīng)先將命題符號化，然后寫出解這類推理問題，應(yīng)先將命題符號化，然后寫出前提、結(jié)論和推理的形式結(jié)構(gòu)，最后進行判斷。前提、結(jié)論和推理的形式結(jié)構(gòu)，最后進行判斷。 在這里，設(shè)在這里，設(shè)p：天氣涼快；：天氣涼快；q：小王去游泳。：小王去游泳。前提：前提：pq, p。結(jié)論：。結(jié)論：q。推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)： (pq )p)q 。下面分別用三種方法來判

41、斷該蘊含式是否為重言式。下面分別用三種方法來判斷該蘊含式是否為重言式。80Table 15 （1）真值表法）真值表法 真值表的最后一列全為真值表的最后一列全為1，因而（，因而（*）是重言式，）是重言式，所以推理正確。所以推理正確。81（2）等值演算法）等值演算法 (pq)p)q(pq)p)q(p q)p)q(p q)pq(pq)(pq) 1該蘊含式是重言式，所以推理正確。該蘊含式是重言式，所以推理正確。82(pq)p)q (pq)p)q(pq)p)q(pq)pq(pq)(p(qq)(q(pp)(pq)(pq)(pq)(qp) (qp)(pq)(pq)(pq)(pq)m3m1m0m2 ( 0,1

42、,2,3 )（3）主析取范式法）主析取范式法 該蘊含式的主析取范式中含有該蘊含式的主析取范式中含有4個極小項，因而是重言式。個極小項，因而是重言式。83 為了更好地判斷推理的正確性，引入為了更好地判斷推理的正確性，引入構(gòu)造證構(gòu)造證明明的方法。的方法。 在數(shù)理邏輯中，在數(shù)理邏輯中，證明證明是一個描述推理過程的是一個描述推理過程的命題公式序列，其中的每個命題公式或者是已知命題公式序列，其中的每個命題公式或者是已知的前提，或者是由某些前提應(yīng)用的前提，或者是由某些前提應(yīng)用推理規(guī)則推理規(guī)則得到的得到的結(jié)論。其中有些規(guī)則建立在結(jié)論。其中有些規(guī)則建立在推理定律推理定律（重言蘊含（重言蘊含式）的基礎(chǔ)之上。式）的基礎(chǔ)之上。 重要的重要的8條條推理定律推理定律：附加、化簡、假言推理、附加、化簡、假言推理、拒取式、析取三段論、假言三段論、等價三段論、拒取式、析取三段論、假言三段論、等價三段論、構(gòu)造性二難。構(gòu)造性二難。 除