第2篇數(shù)理邏輯ch3命題邏輯

1、 第第 二二 篇篇 數(shù)數(shù) 理理 邏邏 輯輯logic（mathematical logic) 是用數(shù)學(xué)的方法來研究人類推理過程的一門是用數(shù)學(xué)的方法來研究人類推理過程的一門數(shù)學(xué)學(xué)科。數(shù)學(xué)學(xué)科。又稱又稱符號邏輯、現(xiàn)代邏輯符號邏輯、現(xiàn)代邏輯。 其顯著特征是符號化和形式化，即把邏輯其顯著特征是符號化和形式化，即把邏輯所涉及的所涉及的“概念、判斷、推理概念、判斷、推理”用符號來表用符號來表示，用公理體系來刻劃示，用公理體系來刻劃, 并基于符號串形式的并基于符號串形式的演算來描述推理過程的一般規(guī)律。演算來描述推理過程的一般規(guī)律。 第第 3 3 章章 命題邏輯命題邏輯 3-1 命題及其表示法命題及其表示法3

2、-2 聯(lián)結(jié)詞聯(lián)結(jié)詞3-3 命題公式與翻譯命題公式與翻譯3-4 真值表與等價公式真值表與等價公式第第3 3章章 命題邏輯命題邏輯3-5 重言式與蘊(yùn)涵式重言式與蘊(yùn)涵式3-6 其他聯(lián)結(jié)詞其他聯(lián)結(jié)詞3-7 對偶與范式對偶與范式3-8 推理理論推理理論第第3 3章章 命題演算及其形式系統(tǒng)命題演算及其形式系統(tǒng) 3-1 3-1 命題及其表示法命題及其表示法 我們把對我們把對確定確定的對象的對象作出判斷作出判斷的的陳述句陳述句稱作稱作（propositions or statements） 當(dāng)判斷正確或符合客觀實際時，當(dāng)判斷正確或符合客觀實際時，稱該命題稱該命題（True），用），用“T”或或“1”表示；表示

3、；否則稱該命題否則稱該命題（False），用），用“F”或或“0”表示。表示。要點(diǎn)：要點(diǎn)：確定確定的對象的對象 作出判斷作出判斷 陳述句陳述句 通常把不含有邏輯聯(lián)結(jié)詞的命題通常把不含有邏輯聯(lián)結(jié)詞的命題稱為稱為或或（atoms）（自然語言中的單句自然語言中的單句） 把由原子命題和邏輯聯(lián)結(jié)詞共同組成的把由原子命題和邏輯聯(lián)結(jié)詞共同組成的命題稱為命題稱為（compositive propositions or compound statements）（自然語言中的復(fù)句自然語言中的復(fù)句）。）。命題的符號化（標(biāo)示符）：命題的符號化（標(biāo)示符）： 可以用以下兩種形式將命題符號化：可以用以下兩種形式將命題符號化

4、： . .用（帶下標(biāo)的）大寫字母；用（帶下標(biāo)的）大寫字母； 例如：例如：P P：今天下雨。：今天下雨。 . .用數(shù)字。用數(shù)字。 例如：例如：1212：今天下雨。：今天下雨。 上例中的上例中的“P”P”和和“12”12”稱為命題標(biāo)示稱為命題標(biāo)示符。符。（proposition constants） 我們把表示具體命題及表示常命題的我們把表示具體命題及表示常命題的p，q，r，s等與等與f，t統(tǒng)稱為統(tǒng)稱為。（proposition variable） 是以是以“真、假真、假”或或“1，0”為取值范圍的變?yōu)槿≈捣秶淖冊?，它未指出符號所表示的具體命題，可以代元，它未指出符號所表示的具體命題，可以代表任

5、意命題表任意命題 。指派指派 當(dāng)命題變元用一個特定命題取代時，該命當(dāng)命題變元用一個特定命題取代時，該命題變元才能有確定的真值，從而成為一個命題。題變元才能有確定的真值，從而成為一個命題。稱對命題變元進(jìn)行稱對命題變元進(jìn)行指派指派 對任意給定的命題變元對任意給定的命題變元p1,pn的一種取值的一種取值狀況，稱為狀況，稱為或或（assignments） ，用字母用字母 ， 等表示等表示 當(dāng)當(dāng)A對取值狀況對取值狀況 為真時，稱指派為真時，稱指派 A或或 是是A的成真賦值，記為的成真賦值，記為 (A) = 1；反之稱指派反之稱指派 A或或 是是A的成假賦值，記為的成假賦值，記為 (A) = 0。 3-2

6、 3-2 聯(lián)結(jié)詞聯(lián)結(jié)詞否定詞否定詞“并非并非”合取詞合取詞“并且并且”析取詞析取詞“或或” 條件詞條件詞“如果如果，那么，那么” 雙條件詞雙條件詞“當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)”（negation ）“ ”表示自然表示自然語言中的語言中的“并非并非”（not ）。）。 p p F（0） T（1） T（1） F（0）表表3-2.1 否定詞否定詞“ ”的意義的意義 “見假為真，見真為假見假為真，見真為假”p讀作讀作“并非并非p”或或“非非p”。合取合?。?conjunction ）合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞 “”表示自然語言中的表示自然語言中的 “并且并且”（and ）。）。 3-2.2 合取詞合取詞“”的意義的意

7、義 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） F（0） F（0） F（0） T（1）pq讀作讀作“p并且并且q”或或“p且且q” 見假為假，見假為假，全真為真。全真為真。詞（詞（disjunction） 取聯(lián)結(jié)詞取聯(lián)結(jié)詞 “ ”表示自然語言中的表示自然語言中的 “ 或或”（or ）。）。 表表 1-2.3 析取詞析取詞“”的意義的意義 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） F（0） T（1） T（1） T（1）見真為真，見真為真，全假為假。全假為假。pq讀作讀作“p或者或者q”、“p

8、或或q”。詞（詞（implication) 聯(lián)結(jié)詞聯(lián)結(jié)詞 “ ”表示自然語言中的表示自然語言中的 “如果如果，那么那么” （ifthen）。）。 表表3-2.4 詞詞“ ”的意義的意義 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） T（1） T（1） F（0） T（1）pq中的中的p稱為稱為，q稱為稱為 前真后假為假，前真后假為假，其他為真。其他為真。(two-way-implication) 聯(lián)結(jié)詞聯(lián)結(jié)詞 “ ”表示自然語言中的表示自然語言中的“當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)”（if and only if）。）。 3-2.5 雙向雙向詞詞“ ”的意義的意

9、義 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） T（1） F（0） F（0） T（1）pq讀讀作作“p與與q互為條件互為條件”，“p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q”。 相同為真，相同為真，相異為假。相異為假。 定義定義3-3.1 以下四條款規(guī)定了以下四條款規(guī)定了（proposition formula） 的意義：的意義： 命題常元或命題變元是命題公式，也稱命題常元或命題變元是命題公式，也稱為原子公式或原子。為原子公式或原子。如果如果A是命題公式，那么是命題公式，那么A也是命題公式。也是命題公式。如果如果A，B是命題公式，那么（是命題公式，那么（AB），）

10、，（AB），（），（AB），（），（AB）也是命題公式。）也是命題公式。只有有限步引用條款（只有有限步引用條款（1）、（）、（2）、）、所組成的符號串是命題公式。所組成的符號串是命題公式。3-3 3-3 命題公式與翻譯命題公式與翻譯 命題公式外層的括號可以省略；命題公式外層的括號可以省略；、。范例：如下的范例：如下的 ： PQR等價于等價于 ： （PQ）R ）等價于等價于 ： （PQ）R不等價于不等價于 ： P（QR）自然語言的語句用自然語言的語句用 形式化形式化主要是以下幾個方面：主要是以下幾個方面： 要準(zhǔn)確確定原子命題，并將其形式化。要準(zhǔn)確確定原子命題，并將其形式化。 要選用恰當(dāng)?shù)穆?lián)結(jié)詞，

11、尤其要善于識別自然語要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識別自然語言中的聯(lián)結(jié)詞（有時它們被省略），否定詞的位置要言中的聯(lián)結(jié)詞（有時它們被省略），否定詞的位置要放準(zhǔn)確。放準(zhǔn)確。 必要必要時可以進(jìn)行改述，即改變原來的敘述方式，時可以進(jìn)行改述，即改變原來的敘述方式，但要保證表達(dá)意思一致但要保證表達(dá)意思一致。 需要的括號不能省略，而可以省略的括號，需要的括號不能省略，而可以省略的括號，在需要提高公式可讀性時亦可不省略。在需要提高公式可讀性時亦可不省略。 要注意語句的形式化未必是唯一的。要注意語句的形式化未必是唯一的。 自然語言的語句用自然語言的語句用 形式化形式化3-4 3-4 真值表與等價公式真值表與等價

12、公式 定義定義3-4.1（真值表）真值表） 在命題公式在命題公式 對于公式對于公式中分量一切可能的指派組合中分量一切可能的指派組合,公式公式A的取值可能用下表來的取值可能用下表來描述，這個表稱為描述，這個表稱為（truth table） 。 定義定義3-4.2 （ 等價公式）等價公式） 給定兩個給定兩個命題公式命題公式A和和B，設(shè)設(shè)P1，P2， ， Pn為所有出現(xiàn)于為所有出現(xiàn)于A和和B中的原子變元，若中的原子變元，若給給P1，P2， ， Pn任一組真值指派，任一組真值指派，A和和B的真值都相同，的真值都相同，則稱則稱A和和B是等價的或邏輯相等。記作是等價的或邏輯相等。記作AB 等價證明方法等價

13、證明方法1：可以用真值表驗證兩個可以用真值表驗證兩個是否等價。是否等價。 常用的等價等值式常用的等價等值式 E1 AA 雙重否定律雙重否定律 E2 AAA 冪等律冪等律 E3 AAA 冪等律冪等律 E4 ABBA 交換律交換律 E5 ABBA 交換律交換律 E6 (AB)CA(BC) 結(jié)合律結(jié)合律 E7 (AB)CA(BC) 結(jié)合律結(jié)合律 E8 A(BC) (AB)(AC) 分配律分配律 E9 A(BC) (AB)(AC) 分配律分配律 E10 (AB) AB 德摩根律德摩根律 E11 (AB) AB 德摩根律德摩根律 E12 A(AB) A 吸收律吸收律 E13 A(AB) A 吸收律吸收律

14、E14 ABAB E15 A B (AB)(BA)E16 AttE17 AtAE18 AfAE19 AffE20 AAt 排中律排中律E21 AAf 矛盾律矛盾律E22 tf, ft 否定律否定律 E23 ABCA(BC) E24 AB BA 逆否律逆否律E25 (AB)(AB) A1律律0律律 定義定義3-4.3 如果如果X X是是 A的一部分，且的一部分，且X本本身也是一個身也是一個，則稱，則稱X為公式為公式A的子公式。的子公式。 定理定理3-4.1 （Rule of Replacement ，簡記為簡記為RR）如果如果X X是是 A的子公式，若的子公式，若X Y，如果將如果將A中的中的X

15、用用Y來置換，所得到的新公式來置換，所得到的新公式B與與公式公式A等價，即等價，即A B。 等價證明方法等價證明方法2：證明思路：證明思路： “討論指派討論指派法法” 等價證明方法等價證明方法3： “等價代換法等價代換法”。 定義定義3-5.1 對命題公式對命題公式A，如果對，如果對A中命題變元的一中命題變元的一切指派均弄真切指派均弄真A，則，則A稱為稱為（tautology），），又稱又稱. 如果至少有一個指派弄真如果至少有一個指派弄真A，則，則A稱為稱為（satisfactable formula or contingency）。）。 定義定義3-5.2如果對如果對A中命題變元的一切指派均

16、弄假中命題變元的一切指派均弄假A，則稱則稱A為為或或（contradiction or absurdity）或或 。3-5 3-5 重言式與蘊(yùn)涵式重言式與蘊(yùn)涵式 定理定理3-5.1 任何兩個重言式的合取或析取，仍然任何兩個重言式的合取或析取，仍然是一個重言式。是一個重言式。 證明思路：證明思路：“討論指派法討論指派法”A為為T，B為為T， A與與B析析?。ɑ蚝先。┤詾槿。ɑ蚝先。┤詾門， 定理定理3-5.2 一個重言式，對同一分量都用任何一個重言式，對同一分量都用任何Wff置換，其結(jié)果仍為一重言式。置換，其結(jié)果仍為一重言式。 證明思路：證明思路：“討論指派法討論指派法” 真值與分量的指派無關(guān)，

17、真值與分量的指派無關(guān)，置換后與仍為置換后與仍為T。 定理定理3-5.3 設(shè)設(shè)A、B是兩個是兩個Wff，一個重言式，一個重言式， AB當(dāng)當(dāng)且僅當(dāng)且僅當(dāng)A B為一重言式。為一重言式。 關(guān)于關(guān)于“當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)”的證明思路：雙向證明法，從的證明思路：雙向證明法，從“AB”出發(fā)推出出發(fā)推出“A B為一重言式為一重言式”；再從；再從“A B為一重言式為一重言式”出發(fā)推出出發(fā)推出“AB” 。 定義定義3-4.2 （ 等價公式的另一種定義）等價公式的另一種定義）當(dāng)命題當(dāng)命題公式公式AB為重言式時，稱為重言式時，稱A邏輯等價于邏輯等價于B，記為，記為A B，它又稱為，它又稱為（logically equiv

18、alent or equivalent）。 定義定義3-5.3 當(dāng)命題公式當(dāng)命題公式AB為重言式時，稱為重言式時，稱A邏邏輯蘊(yùn)涵輯蘊(yùn)涵B，記為，記為A B，它又稱為，它又稱為(logically implication)。 定理定理3-5.4 設(shè)設(shè)P、Q為任意兩個命題公式，為任意兩個命題公式，PQ的的充分必要條件是充分必要條件是PQ Q且且Q QP P。 證明思路：證明思路： 本定理的結(jié)論是本定理的結(jié)論是“PQ” 本定理的條件是本定理的條件是“PQ Q且且Q QP P ” 如果能從條件如果能從條件“PQ Q且且Q QP P ”推出結(jié)論推出結(jié)論“PQ”，說，說明條件是充分的；明條件是充分的； 如

19、果能從結(jié)論如果能從結(jié)論“PQ”推出條件推出條件“PQ Q且且Q QP P ” ， 說明條件是必要的。說明條件是必要的。 先證必要性：先證必要性：XXXXXX 再證充分性：再證充分性：XXXXXX 關(guān)于等價式和蘊(yùn)涵式的性質(zhì)：關(guān)于等價式和蘊(yùn)涵式的性質(zhì)： （1）AB B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A AB B （2 2）A AB B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) ABAB （3 3）若）若A AB B，則，則B BA A 等價對稱性等價對稱性 （4 4）若）若A AB B，B BC C，則，則A AC C 等價傳遞性等價傳遞性 （5 5）若）若A AB B，則，則BBA A 蘊(yùn)涵逆否性蘊(yùn)涵逆否性 （6 6）若）若A AB

20、B，B BC C，則，則A AC C 蘊(yùn)涵傳遞性蘊(yùn)涵傳遞性 （7 7）若）若A AB B，A AA A，B BB B，則，則A AB B 蘊(yùn)涵等價蘊(yùn)涵等價代換代換 （8 8）若）若A AB B，C CB B，則，則ACACB B （9 9）若）若A AB B，A AC C，則，則A ABCBC 設(shè)設(shè)A為永真式，為永真式，p為為A中命題變元，中命題變元，A(B/p) 表表示將示將A中中p的的出現(xiàn)出現(xiàn)代換為公式代換為公式B后所得后所得的命題公式（稱為的命題公式（稱為A的一個代入實例），那么的一個代入實例），那么 A(B/p)亦為永真式。亦為永真式。（Rule of Substitution），簡記

21、為），簡記為RS3-6 3-6 其它聯(lián)結(jié)詞其它聯(lián)結(jié)詞 3-6.1 異或異或詞詞“”的意義的意義 F（0） T（1） T（1） F（0） F（0） T（1） F（0） T（1） F（0） F（0） T（1） T（1） p q q pp q讀作讀作“p異或異或q” 相同為假，相同為假，相異為真。相異為真。異或）異或） 異或聯(lián)結(jié)詞的性質(zhì)：異或聯(lián)結(jié)詞的性質(zhì)： （1） （2）（）（ （3） （ （ ）分配律分配律（4）（）（ （P ） Q（5）（）（ （P ）（6）（）（ P F，F(xiàn)P P，T P R，R ， R ， 且且 R為一矛盾式。為一矛盾式。 表表3-6.2 異或異或詞詞“ ”的意義的意義 F（

22、0） F（0） T（1） F（0） F（0） T（1） F（0） T（1） F（0） F（0） T（1） T（1） p q q pp q讀作讀作“p和和q的條件否定的條件否定” 前真后假為真前真后假為真其余為假。其余為假。 （P ） （P ） T（1） T（1） T（1） F（0） F（0） T（1） F（0） T（1） F（0） F（0） T（1） T（1） p q q p全真為假全真為假見假為真。見假為真。 表表3-6.3 與非與非詞詞“ ”的意義的意義 （P ） 表表3-6.4 或非或非詞詞“ ”的意義的意義 T（1） T（1） T（1） F（0） F（0） T（1） F（0） T（1）

23、 F（0） F（0） T（1） T（1） p q q p全假為真全假為真見真為假。見真為假。3-7 3-7 對偶與范式對偶與范式 定義定義3-7.1 設(shè)給定的命題公式設(shè)給定的命題公式A僅含聯(lián)結(jié)詞僅含聯(lián)結(jié)詞 ，A*為將為將A中符號中符號，t，f分別改換為分別改換為，f，t后所得的公式，那么稱后所得的公式，那么稱A* *為為A的的（dual）。）。A為為A*的的 定理定理3-7.1 設(shè)公式設(shè)公式A A和和A A* *中僅含命題變元中僅含命題變元p p1 1,p,pn n，及，及聯(lián)結(jié)詞聯(lián)結(jié)詞，；則；則 A(pA(p1 1， p p2 2 , p , pn n) ) A A* *(p(p1 1， pp

24、2 2 , p , pn n) ) A(p A(p1 1， pp2 2 , p , pn n) ) A A* *(p(p1 1， p p2 2 , p , pn n) ) 證明思路：利用德摩根定律證明思路：利用德摩根定律 PQ PQ （PQPQ） A A A A* * 推廣到推廣到p p1 1， p p2 2 , p , pn n 定理定理3-7.2 設(shè)公式設(shè)公式A A和和B B中僅含命題變元中僅含命題變元p p1 1,p,pn n，如果如果A AB B，則，則A A* *B B* *。 (letters)：指命題常元、變元及它們的否定，：指命題常元、變元及它們的否定，前者又稱前者又稱，后者則

25、稱，后者則稱。(disjunctive clauses)：指文字或若干：指文字或若干文字的析取。文字的析取。 (conjunctive clauses)：指文字或若干：指文字或若干文字的合取。文字的合取。(complemental pairs of letters) ：指形如指形如L，L（L為文字）的一對字符。為文字）的一對字符。 定義定義3-7.2 命題公式命題公式A稱為公式稱為公式A的的（conjunctive normal form）如果如果 A A A為一析取子句或若干析取子句的合取。為一析取子句或若干析取子句的合取。 A形如：形如：A1AA2 2AAn n (n(n 1)1) 定義定

26、義3-7.3命題公式命題公式A稱為公式稱為公式A的的（disjunctive normal form），如果，如果 A A A為一合取子句或若干合取子句的析取為一合取子句或若干合取子句的析取。 A形如：形如：A1AA2 2AAn n (n (n 1)1)求一個命題公式的合取范式或析取范式的步驟：求一個命題公式的合取范式或析取范式的步驟： . 將公式中的聯(lián)結(jié)詞化歸成僅含將公式中的聯(lián)結(jié)詞化歸成僅含 、； . 利用德利用德 . 摩根定律將否定符號摩根定律將否定符號直接內(nèi)移到各直接內(nèi)移到各個命題變元之前；個命題變元之前； . 利用分配律、結(jié)合律將公式歸約為合取范式利用分配律、結(jié)合律將公式歸約為合取范式

27、或析取范式?；蛭鋈》妒?。定義定義3-7.4 n3-7.4 n個命題變元的合取式，稱作個命題變元的合取式，稱作布爾合取布爾合取或或小項小項，其中每個變元與它的否定不能同時出現(xiàn)，但，其中每個變元與它的否定不能同時出現(xiàn)，但兩者必須出現(xiàn)且僅出現(xiàn)一次。兩者必須出現(xiàn)且僅出現(xiàn)一次。 一般來說，一般來說，n n個命題變元共有個命題變元共有2 2n n個小項。個小項。 根據(jù)定義可知，沒有兩個小項是等價的，且每個根據(jù)定義可知，沒有兩個小項是等價的，且每個小項都只對應(yīng)小項都只對應(yīng)P和和Q的一組真值指派，使得該小項的的一組真值指派，使得該小項的真值為真值為T。 以上結(jié)論可推廣到三個以上的變元情況，并且由以上結(jié)論可推廣

28、到三個以上的變元情況，并且由此可以作出一種編碼，使此可以作出一種編碼，使n個變元的小項可以很快地個變元的小項可以很快地寫出來。寫出來。 小項有如下性質(zhì)：小項有如下性質(zhì)： . 每一個小項當(dāng)其真值指派與編碼相同時，其每一個小項當(dāng)其真值指派與編碼相同時，其真值為真值為T，在其余，在其余2 2n n -1種真值指派情況下均為種真值指派情況下均為F。 . 任意兩個不同小項的合取式永假。任意兩個不同小項的合取式永假。 . 全體小項的析取式永為真。全體小項的析取式永為真。 2 2n n -1 mi =m0mm1 1 mm 2 2n n -1 T i=0 定義定義3-7.5 對于給定的對于給定的命題公式命題公

29、式A，如果有一個等，如果有一個等價公式價公式A，它僅由小項的析取所組成，則稱它僅由小項的析取所組成，則稱A為為A的的（major disjunctive normal form）。）。 一個公式一個公式 定理定理3-7.33-7.3 在真值表中，一個公式的真值為在真值表中，一個公式的真值為T T的指的指派所對應(yīng)的小項的析取，即為次公式的主析取范式。派所對應(yīng)的小項的析取，即為次公式的主析取范式。 利用等價公式推演主析取范式的步驟：利用等價公式推演主析取范式的步驟： . 化歸為析取范式。化歸為析取范式。 . 除去析取范式中所有永假的析取式。除去析取范式中所有永假的析取式。 . 將析取式中重復(fù)出現(xiàn)的

30、合取項和相同的變元合將析取式中重復(fù)出現(xiàn)的合取項和相同的變元合并。并。 . 對合取項補(bǔ)入沒有出現(xiàn)的命題變元，即添加對合取項補(bǔ)入沒有出現(xiàn)的命題變元，即添加（P P）式，然后，應(yīng)用分配律展開公式，再經(jīng)）式，然后，應(yīng)用分配律展開公式，再經(jīng)過整理。過整理。 定義定義3-7.6 n3-7.6 n個命題變元的析取式，稱作個命題變元的析取式，稱作布爾析布爾析取取或或大項大項，其中每個變元與它的否定不能同時出現(xiàn)，其中每個變元與它的否定不能同時出現(xiàn)，但兩者必須出現(xiàn)且僅出現(xiàn)一次。但兩者必須出現(xiàn)且僅出現(xiàn)一次。 一般來說，一般來說，n n個命題變元共有個命題變元共有2 2n n個大項。個大項。 大項有如下性質(zhì)：大項有如

31、下性質(zhì)： . 每一個大項當(dāng)其真值指派與編碼相同時，其每一個大項當(dāng)其真值指派與編碼相同時，其真值為真值為F，在其余，在其余2 2n n -1種真值指派情況下均為種真值指派情況下均為T。 . 任意兩個不同大項的析取式永真。任意兩個不同大項的析取式永真。 . 全體大項的合取式永為假。全體大項的合取式永為假。 2 2n n -1 Mi =M0M M1 1 M M 2 2n n -1 F i=0 定義定義3-7.7 對于給定的對于給定的命題公式命題公式A，如果有一個等，如果有一個等價公式價公式A，它僅由大項的合取所組成，則稱它僅由大項的合取所組成，則稱A為為A的的（major conjunctive n

32、ormal form）。）。 一個公式一個公式 定理定理3-7.43-7.4 在真值表中，一個公式的真值為在真值表中，一個公式的真值為F F的指的指派所對應(yīng)的大項的合取，即為次公式的主合取范式。派所對應(yīng)的大項的合取，即為次公式的主合取范式。 利用等價公式推演主合取范式的步驟：利用等價公式推演主合取范式的步驟： . 化歸為合取范式。化歸為合取范式。 . 除去合取范式中所有永真的合取項。除去合取范式中所有永真的合取項。 . 將合取式中重復(fù)出現(xiàn)的析取項和相同的變元合將合取式中重復(fù)出現(xiàn)的析取項和相同的變元合并。并。 . 對析取項補(bǔ)入沒有出現(xiàn)的命題變元，即添加（對析取項補(bǔ)入沒有出現(xiàn)的命題變元，即添加（P

33、 P）式，然后，應(yīng)用分配律展開公式，再經(jīng)過整理。）式，然后，應(yīng)用分配律展開公式，再經(jīng)過整理。5-1 5-1 命題邏輯推理理論命題邏輯推理理論 定義定義5-1.1 設(shè)設(shè)A和和C是兩個命題公式，當(dāng)且僅當(dāng)是兩個命題公式，當(dāng)且僅當(dāng)AC為一重言式，即為一重言式，即A C，稱，稱C是是A的有效結(jié)論?；虻挠行ЫY(jié)論?；駽可由可由A邏輯推出。邏輯推出。 序列序列H1, H2, , Hn和和C是命題公式，當(dāng)且僅當(dāng)是命題公式，當(dāng)且僅當(dāng) H1H2Hn C稱稱C是一組前提是一組前提H1, H2, , Hn的有效結(jié)論?；虻挠行ЫY(jié)論?；駽可由可由H1, H2, , Hn邏輯推出。邏輯推出。 判別有效結(jié)論的過程就是論證過程，

34、論證方法有判別有效結(jié)論的過程就是論證過程，論證方法有“真真值表法值表法”、“直接證明法直接證明法”和和“間接證明法間接證明法”。 （1）真值表法）真值表法 （1 1）真值表法）真值表法 設(shè)設(shè)P1, P2, , Pn 是出現(xiàn)于前提是出現(xiàn)于前提H1, H2, , Hm和結(jié)論和結(jié)論C中的全部命題變元，假定對中的全部命題變元，假定對P1, P2, , Pn作了全部的真作了全部的真值指派，這樣就能對應(yīng)地確定值指派，這樣就能對應(yīng)地確定H1, H2, , Hm和和C的所有的所有真值，列出這個真值表，即可看出真值，列出這個真值表，即可看出 H1H2Hm C是否成立。是否成立。 因為若從真值表上找出因為若從真值表上找出H1, H2, , Hm真值均為真值均為T的行，的行，對于每一個這樣的行，若對于每一個這樣的行，若C也有真值也有真值T，則上述蘊(yùn)涵式成，則上述蘊(yùn)涵式成立；或者找出立；或者找出C的真值為的真值為F的行，對于每一個這樣的行，的行，對于每一個這樣的行，H1, H2, , Hm的真值中至少有一個為的真值中至少有一個為F F，則，則上述蘊(yùn)涵式上述蘊(yùn)涵式也成立。也成立。 （2 2）直接證明法）直接證明法 直接