第一篇數(shù)理邏輯

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

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

3、否則稱(chēng)該命題（False），用），用“F”或或“0”表示。表示。要點(diǎn)：要點(diǎn)：確定確定的對(duì)象的對(duì)象 作出判斷作出判斷 陳述句陳述句 （見(jiàn)（見(jiàn)P-2的句子）的句子） 通常把不含有邏輯聯(lián)結(jié)詞的命題通常把不含有邏輯聯(lián)結(jié)詞的命題稱(chēng)為稱(chēng)為或或（atoms）（自然語(yǔ)言中的單句自然語(yǔ)言中的單句,P-2的的(1)、(2)、(4)） 把由原子命題和邏輯聯(lián)結(jié)詞共同組成的把由原子命題和邏輯聯(lián)結(jié)詞共同組成的命題稱(chēng)為命題稱(chēng)為（compositive propositions or compound statements）（自然語(yǔ)言中的復(fù)句，自然語(yǔ)言中的復(fù)句， P-2的的(9)、(10)）。）。命題的符號(hào)化（標(biāo)示符）：命題

4、的符號(hào)化（標(biāo)示符）： 可以用以下兩種形式將命題符號(hào)化：可以用以下兩種形式將命題符號(hào)化： . .用（帶下標(biāo)的）大寫(xiě)字母；用（帶下標(biāo)的）大寫(xiě)字母； 例如：例如：P P：今天下雨。：今天下雨。 . .用數(shù)字。用數(shù)字。 例如：例如：1212：今天下雨。：今天下雨。 上例中的上例中的“P”P(pán)”和和“12”12”稱(chēng)為命題標(biāo)示稱(chēng)為命題標(biāo)示符。符。（proposition constants） 我們把表示具體命題及表示常命題的我們把表示具體命題及表示常命題的p，q，r，s等與等與f，t統(tǒng)稱(chēng)為統(tǒng)稱(chēng)為。（proposition variable） 是以是以“真、假真、假”或或“1，0”為取值范圍的變?yōu)槿≈捣秶淖?/p>

5、元，它未指出符號(hào)所表示的具體命題，可以代元，它未指出符號(hào)所表示的具體命題，可以代表任意命題表任意命題 。指派指派 當(dāng)命題變?cè)靡粋€(gè)特定命題取代時(shí)，該命當(dāng)命題變?cè)靡粋€(gè)特定命題取代時(shí)，該命題變?cè)拍苡写_定的真值，從而成為一個(gè)命題。題變?cè)拍苡写_定的真值，從而成為一個(gè)命題。稱(chēng)對(duì)命題變?cè)M(jìn)行稱(chēng)對(duì)命題變?cè)M(jìn)行指派指派 對(duì)任意給定的命題變?cè)獙?duì)任意給定的命題變?cè)猵1,pn的一種取值的一種取值狀況，稱(chēng)為狀況，稱(chēng)為或或（assignments） ，用字母用字母 ， 等表示等表示 當(dāng)當(dāng)A對(duì)取值狀況對(duì)取值狀況 為真時(shí)，稱(chēng)指派為真時(shí)，稱(chēng)指派 A或或 是是A的成真賦值，記為的成真賦值，記為 (A) = 1；反之稱(chēng)指派

6、反之稱(chēng)指派 A或或 是是A的成假賦值，記為的成假賦值，記為 (A) = 0。 1-2 1-2 聯(lián)結(jié)詞聯(lián)結(jié)詞否定詞否定詞“并非并非”合取詞合取詞“并且并且”析取詞析取詞“或或” 條件詞條件詞“如果如果，那么，那么” 雙條件詞雙條件詞“當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)”（negation ）“ ”表示自然表示自然語(yǔ)言中的語(yǔ)言中的“并非并非”（not ）。）。 p p F（0） T（1） T（1） F（0）表表1-2.1 否定詞否定詞“ ”的意義的意義 “見(jiàn)假為真，見(jiàn)真為假見(jiàn)假為真，見(jiàn)真為假”p讀作讀作“并非并非p”或或“非非p”。合取合取（ conjunction ）合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞 “”表示自然語(yǔ)言中的表示

7、自然語(yǔ)言中的 “并且并且”（and ）。）。 1-2.2 合取詞合取詞“”的意義的意義 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” 見(jiàn)假為假，見(jiàn)假為假，全真為真。全真為真。詞（詞（disjunction） 取聯(lián)結(jié)詞取聯(lián)結(jié)詞 “ ”表示自然語(yǔ)言中的表示自然語(yǔ)言中的 “ 或或”（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）

8、 T（1）見(jiàn)真為真，見(jiàn)真為真，全假為假。全假為假。pq讀作讀作“p或者或者q”、“p或或q”。詞（詞（implication) 聯(lián)結(jié)詞聯(lián)結(jié)詞 “ ”表示自然語(yǔ)言中的表示自然語(yǔ)言中的 “如果如果，那么那么” （ifthen）。）。 表表1-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稱(chēng)為稱(chēng)為，q稱(chēng)為稱(chēng)為 前真后假為假，前真后假為假，其他為真。其他為真。(two-way-implication) 聯(lián)結(jié)詞聯(lián)結(jié)詞 “ ”表示自然語(yǔ)言中的表示自然語(yǔ)言中的“當(dāng)且僅當(dāng)當(dāng)且僅

9、當(dāng)”（if and only if）。）。 1-2.5 雙向雙向詞詞“ ”的意義的意義 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”。 相同為真，相同為真，相異為假。相異為假。 定義定義1-3.1 以下四條款規(guī)定了以下四條款規(guī)定了（proposition formula） 的意義：的意義： 命題常元或命題變?cè)敲}公式，也稱(chēng)命題常元或命題變?cè)敲}公式，也稱(chēng)為原子公式或原子。為原子公式或原子。如果如果A是命題公式，那么是命題公式，那么A也是

10、命題公式。也是命題公式。如果如果A，B是命題公式，那么（是命題公式，那么（AB），），（AB），（），（AB），（），（AB）也是命題公式。）也是命題公式。只有有限步引用條款（只有有限步引用條款（1）、（）、（2）、）、所組成的符號(hào)串是命題公式。所組成的符號(hào)串是命題公式。1-3 1-3 命題公式與翻譯命題公式與翻譯n命題公式外層的括號(hào)可以省略；命題公式外層的括號(hào)可以省略；、。范例：如下的范例：如下的 ： PQR等價(jià)于等價(jià)于 ： （PQ）R ）等價(jià)于等價(jià)于 ： （PQ）R不等價(jià)于不等價(jià)于 ： P（QR）自然語(yǔ)言的語(yǔ)句用自然語(yǔ)言的語(yǔ)句用 形式化形式化主要是以下幾個(gè)方面：主要是以下幾個(gè)方面： 要準(zhǔn)確

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

12、言的語(yǔ)句用自然語(yǔ)言的語(yǔ)句用 形式化形式化1-4 1-4 真值表與等價(jià)公式真值表與等價(jià)公式 定義定義1-4.1（真值表）真值表） 在命題公式在命題公式 對(duì)于公式對(duì)于公式中分量一切可能的指派組合中分量一切可能的指派組合,公式公式A的取值可能用下表來(lái)的取值可能用下表來(lái)描述，這個(gè)表稱(chēng)為描述，這個(gè)表稱(chēng)為（truth table） 。 真值表真值表1-4.11-4.21-4.3和和1-4.4、1-4.51-4.6 定義定義1-4.2 （ 等價(jià)公式）等價(jià)公式） 給定兩個(gè)給定兩個(gè)命題公式命題公式A和和B，設(shè)設(shè)P1，P2， ， Pn為所有出現(xiàn)于為所有出現(xiàn)于A和和B中的原子變?cè)?，若中的原子變?cè)艚o給P1，P2，

13、 ， Pn任一組真值指派，任一組真值指派，A和和B的真值都相同，的真值都相同，則稱(chēng)則稱(chēng)A和和B是等價(jià)的或邏輯相等。記作是等價(jià)的或邏輯相等。記作AB 等價(jià)證明方法等價(jià)證明方法1：可以用真值表驗(yàn)證兩個(gè)可以用真值表驗(yàn)證兩個(gè)是否等價(jià)，是否等價(jià)，見(jiàn)見(jiàn)P-13的例題的例題5 “真值表法真值表法”。 常用的等價(jià)等值式常用的等價(jià)等值式 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) 分配律分

14、配律 E9 A(BC) (AB)(AC) 分配律分配律 E10 (AB) AB 德摩根律德摩根律 E11 (AB) AB 德摩根律德摩根律 E12 A(AB) A 吸收律吸收律 E13 A(AB) A 吸收律吸收律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) AP-16 例題例題6 驗(yàn)證吸收率驗(yàn)證吸收率1律律0律律 定義定義1-4.3 如果如果X X是是 A的一

15、部分，且的一部分，且X本本身也是一個(gè)身也是一個(gè)，則稱(chēng)，則稱(chēng)X為公式為公式A的子公式。的子公式。 定理定理1-4.1 （Rule of Replacement ，簡(jiǎn)記為簡(jiǎn)記為RR）如果如果X X是是 A的子公式，若的子公式，若X Y，如果將如果將A中的中的X用用Y來(lái)置換，所得到的新公式來(lái)置換，所得到的新公式B與與公式公式A等價(jià)，即等價(jià)，即A B。 等價(jià)證明方法等價(jià)證明方法2：證明思路：證明思路： “討論指派討論指派法法” 等價(jià)證明方法等價(jià)證明方法3：見(jiàn)見(jiàn)P-16的例題的例題7“等價(jià)代換法等價(jià)代換法”。 定義定義1-5.1 對(duì)命題公式對(duì)命題公式A，如果對(duì)，如果對(duì)A中命題變?cè)囊恢忻}變?cè)囊磺兄概?/p>

16、均弄真切指派均弄真A，則，則A稱(chēng)為稱(chēng)為（tautology），），又稱(chēng)又稱(chēng). 如果至少有一個(gè)指派弄真如果至少有一個(gè)指派弄真A，則，則A稱(chēng)為稱(chēng)為（satisfactable formula or contingency）。）。 定義定義1-5.2如果對(duì)如果對(duì)A中命題變?cè)囊磺兄概删僦忻}變?cè)囊磺兄概删貯，則稱(chēng)則稱(chēng)A為為或或（contradiction or absurdity）或或 。1-5 1-5 重言式與蘊(yùn)涵式重言式與蘊(yùn)涵式 定理定理1-5.1 任何兩個(gè)重言式的合取或析取，仍然任何兩個(gè)重言式的合取或析取，仍然是一個(gè)重言式。是一個(gè)重言式。 證明思路：證明思路：“討論指派法討論指派法”

17、A為為T(mén)，B為為T(mén)， A與與B析析取（或合?。┤詾槿。ɑ蚝先。┤詾門(mén)， 定理定理1-5.2 一個(gè)重言式，對(duì)同一分量都用任何一個(gè)重言式，對(duì)同一分量都用任何Wff置換，其結(jié)果仍為一重言式。置換，其結(jié)果仍為一重言式。 證明思路：證明思路：“討論指派法討論指派法” 真值與分量的指派無(wú)關(guān)，真值與分量的指派無(wú)關(guān)，置換后與仍為置換后與仍為T(mén)。 見(jiàn)見(jiàn)P-20的例題的例題1 定理定理1-5.3 設(shè)設(shè)A、B是兩個(gè)是兩個(gè)Wff，一個(gè)重言式，一個(gè)重言式， 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

18、為一重言式為一重言式”；再?gòu)模辉購(gòu)摹癆 B為一重言式為一重言式”出發(fā)推出出發(fā)推出“AB” 。 定義定義1-4.2 （ 等價(jià)公式的另一種定義）等價(jià)公式的另一種定義）當(dāng)命題當(dāng)命題公式公式AB為重言式時(shí)，稱(chēng)為重言式時(shí)，稱(chēng)A邏輯等價(jià)于邏輯等價(jià)于B，記為，記為A B，它又稱(chēng)為，它又稱(chēng)為（logically equivalent or equivalent）。 定義定義1-5.3 當(dāng)命題公式當(dāng)命題公式AB為重言式時(shí)，稱(chēng)為重言式時(shí)，稱(chēng)A邏邏輯蘊(yùn)涵輯蘊(yùn)涵B，記為，記為A B，它又稱(chēng)為，它又稱(chēng)為(logically implication)。 常用的常用的 定理定理1-5.4 設(shè)設(shè)P、Q為任意兩個(gè)命題公式，為任

19、意兩個(gè)命題公式，PQ的的充分必要條件是充分必要條件是PQ Q且且Q QP P。 證明思路：證明思路： 本定理的結(jié)論是本定理的結(jié)論是“PQ” 本定理的條件是本定理的條件是“PQ Q且且Q QP P ” 如果能從條件如果能從條件“PQ Q且且Q QP P ”推出結(jié)論推出結(jié)論“PQ”，說(shuō)，說(shuō)明條件是充分的；明條件是充分的； 如果能從結(jié)論如果能從結(jié)論“PQ”推出條件推出條件“PQ Q且且Q QP P ” ， 說(shuō)明條件是必要的。說(shuō)明條件是必要的。 先證必要性：先證必要性：XXXXXX 再證充分性：再證充分性：XXXXXX 關(guān)于等價(jià)式和蘊(yùn)涵式的性質(zhì)：關(guān)于等價(jià)式和蘊(yùn)涵式的性質(zhì)： （1）AB B當(dāng)且僅當(dāng)當(dāng)且僅

20、當(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 等價(jià)對(duì)稱(chēng)性等價(jià)對(duì)稱(chēng)性 （4 4）若）若A AB B，B BC C，則，則A AC C 等價(jià)傳遞性等價(jià)傳遞性 （5 5）若）若A AB B，則，則BBA A 蘊(yùn)涵逆否性蘊(yùn)涵逆否性 （6 6）若）若A AB 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)涵等價(jià)蘊(yùn)涵等價(jià)代換代換 （8 8）若）若A AB B，C CB B，則，則ACACB B （9 9）若）若A AB B，A AC C，則，

21、則A ABCBC 設(shè)設(shè)A為永真式，為永真式，p為為A中命題變?cè)?，中命題變?cè)?，A(B/p) 表表示將示將A中中p的的出現(xiàn)出現(xiàn)代換為公式代換為公式B后所得后所得的命題公式（稱(chēng)為的命題公式（稱(chēng)為A的一個(gè)代入實(shí)例），那么的一個(gè)代入實(shí)例），那么 A(B/p)亦為永真式。亦為永真式。（Rule of Substitution），簡(jiǎn)記為），簡(jiǎn)記為RS1-6 1-6 其它聯(lián)結(jié)詞其它聯(lián)結(jié)詞 1-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” 相同為假，相同為

22、假，相異為真。相異為真。異或）異或） 異或聯(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為一矛盾式。為一矛盾式。 表表1-6.2 異或異或詞詞“ ”的意義的意義 F（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（

23、0） F（0） T（1） F（0） T（1） F（0） F（0） T（1） T（1） p q q p全真為假全真為假見(jiàn)假為真。見(jiàn)假為真。 表表1-6.3 與非與非詞詞“ ”的意義的意義 （P ） 表表1-6.4 或非或非詞詞“ ”的意義的意義 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全假為真全假為真見(jiàn)真為假。見(jiàn)真為假。1-7 1-7 對(duì)偶與范式對(duì)偶與范式 定義定義1-7.1 設(shè)給定的命題公式設(shè)給定的命題公式A僅含聯(lián)結(jié)詞僅含聯(lián)結(jié)詞 ，A*為將為將A中符號(hào)中符號(hào)，t，f分別改換為分別改換為，f，t后所得的

24、公式，那么稱(chēng)后所得的公式，那么稱(chēng)A* *為為A的的（dual）。）。A為為A*的的 定理定理1-7.1 設(shè)公式設(shè)公式A A和和A A* *中僅含命題變?cè)袃H含命題變?cè)猵 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， pp2 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* * 推廣到推

25、廣到p p1 1， p p2 2 , p , pn n 定理定理1-7.2 設(shè)公式設(shè)公式A A和和B B中僅含命題變?cè)袃H含命題變?cè)猵 p1 1,p,pn n，如果如果A AB B，則，則A A* *B B* *。 (letters)：指命題常元、變?cè)八鼈兊姆穸ǎ褐该}常元、變?cè)八鼈兊姆穸?，前者又稱(chēng)前者又稱(chēng)，后者則稱(chēng)，后者則稱(chēng)。(disjunctive clauses)：指文字或若干：指文字或若干文字的析取。文字的析取。 (conjunctive clauses)：指文字或若干：指文字或若干文字的合取。文字的合取。(complemental pairs of letters) ：指形如指

26、形如L，L（L為文字）的一對(duì)字符。為文字）的一對(duì)字符。 定義定義1-7.2 命題公式命題公式A稱(chēng)為公式稱(chēng)為公式A的的（conjunctive normal form）如果如果 A A A為一析取子句或若干析取子句的合取。為一析取子句或若干析取子句的合取。 A形如：形如：A1AA2 2AAn n (n(n 1)1) 定義定義1-7.3命題公式命題公式A稱(chēng)為公式稱(chēng)為公式A的的（disjunctive normal form），如果，如果 A A A為一合取子句或若干合取子句的析取為一合取子句或若干合取子句的析取。 A形如：形如：A1AA2 2AAn n (n (n 1)1)求一個(gè)命題公式的合取范式

27、或析取范式的步驟：求一個(gè)命題公式的合取范式或析取范式的步驟： . 將公式中的聯(lián)結(jié)詞化歸成僅含將公式中的聯(lián)結(jié)詞化歸成僅含 、； . 利用德利用德 . 摩根定律將否定符號(hào)摩根定律將否定符號(hào)直接內(nèi)移到各直接內(nèi)移到各個(gè)命題變?cè)埃粋€(gè)命題變?cè)埃?. 利用分配律、結(jié)合律將公式歸約為合取范式利用分配律、結(jié)合律將公式歸約為合取范式或析取范式?；蛭鋈》妒?。 見(jiàn)見(jiàn)P-32頁(yè)例題頁(yè)例題5 定義定義1-7.4 n1-7.4 n個(gè)命題變?cè)暮先∈剑Q(chēng)作個(gè)命題變?cè)暮先∈?，稱(chēng)作布爾布爾合取合取或或小項(xiàng)小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，但兩者必須出現(xiàn)且僅出現(xiàn)一次。但兩者必須

28、出現(xiàn)且僅出現(xiàn)一次。 一般來(lái)說(shuō)，一般來(lái)說(shuō)，n n個(gè)命題變?cè)灿袀€(gè)命題變?cè)灿? 2n n個(gè)小項(xiàng)。個(gè)小項(xiàng)。 P-32P-32頁(yè)表頁(yè)表7-7.17-7.1 根據(jù)定義可知，沒(méi)有兩個(gè)小項(xiàng)是等價(jià)的，且每個(gè)根據(jù)定義可知，沒(méi)有兩個(gè)小項(xiàng)是等價(jià)的，且每個(gè)小項(xiàng)都只對(duì)應(yīng)小項(xiàng)都只對(duì)應(yīng)P和和Q的一組真值指派，使得該小項(xiàng)的的一組真值指派，使得該小項(xiàng)的真值為真值為T(mén)。 以上結(jié)論可推廣到三個(gè)以上的變?cè)闆r，并且由以上結(jié)論可推廣到三個(gè)以上的變?cè)闆r，并且由此可以作出一種編碼，使此可以作出一種編碼，使n個(gè)變?cè)男№?xiàng)可以很快地個(gè)變?cè)男№?xiàng)可以很快地寫(xiě)出來(lái)。見(jiàn)寫(xiě)出來(lái)。見(jiàn)P=33頁(yè)表頁(yè)表1-7.3。 小項(xiàng)有如下性質(zhì)：小項(xiàng)有如下性質(zhì)： .

29、 每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為真值為T(mén)，在其余，在其余2 2n n -1種真值指派情況下均為種真值指派情況下均為F。 . 任意兩個(gè)不同小項(xiàng)的合取式永假。任意兩個(gè)不同小項(xiàng)的合取式永假。 . 全體小項(xiàng)的析取式永為真。全體小項(xiàng)的析取式永為真。 2 2n n -1 mi =m0mm1 1 mm 2 2n n -1 T i=0 定義定義1-7.5 對(duì)于給定的對(duì)于給定的命題公式命題公式A，如果有一個(gè)等，如果有一個(gè)等價(jià)公式價(jià)公式A，它僅由小項(xiàng)的析取所組成，則稱(chēng)它僅由小項(xiàng)的析取所組成，則稱(chēng)A為為A的的（major disjunctive normal fo

30、rm）。）。 一個(gè)公式一個(gè)公式 定理定理1-7.31-7.3 在真值表中，一個(gè)公式的真值為在真值表中，一個(gè)公式的真值為T(mén) T的指的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為次公式的主析取范式。派所對(duì)應(yīng)的小項(xiàng)的析取，即為次公式的主析取范式。 利用等價(jià)公式推演主析取范式的步驟：利用等價(jià)公式推演主析取范式的步驟： . 化歸為析取范式?；瘹w為析取范式。 . 除去析取范式中所有永假的析取式。除去析取范式中所有永假的析取式。 . 將析取式中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變?cè)蠈⑽鋈∈街兄貜?fù)出現(xiàn)的合取項(xiàng)和相同的變?cè)喜?。并?. 對(duì)合取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)刺砑訉?duì)合取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?，即添加（P P）式，然后，應(yīng)

31、用分配律展開(kāi)公式，再經(jīng)）式，然后，應(yīng)用分配律展開(kāi)公式，再經(jīng)過(guò)整理。過(guò)整理。 定義定義1-7.6 n1-7.6 n個(gè)命題變?cè)奈鋈∈?，稱(chēng)作個(gè)命題變?cè)奈鋈∈剑Q(chēng)作布爾析布爾析取取或或大項(xiàng)大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，但兩者必須出現(xiàn)且僅出現(xiàn)一次。但兩者必須出現(xiàn)且僅出現(xiàn)一次。 一般來(lái)說(shuō)，一般來(lái)說(shuō)，n n個(gè)命題變?cè)灿袀€(gè)命題變?cè)灿? 2n n個(gè)大項(xiàng)。個(gè)大項(xiàng)。 P-36P-36頁(yè)大項(xiàng)的例子。頁(yè)大項(xiàng)的例子。 大項(xiàng)有如下性質(zhì)：大項(xiàng)有如下性質(zhì)： . 每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為真值為F，在其余，在其余2 2

32、n n -1種真值指派情況下均為種真值指派情況下均為T(mén)。 . 任意兩個(gè)不同大項(xiàng)的析取式永真。任意兩個(gè)不同大項(xiàng)的析取式永真。 . 全體大項(xiàng)的合取式永為假。全體大項(xiàng)的合取式永為假。 2 2n n -1 Mi =M0M M1 1 M M 2 2n n -1 F i=0 定義定義1-7.7 對(duì)于給定的對(duì)于給定的命題公式命題公式A，如果有一個(gè)等，如果有一個(gè)等價(jià)公式價(jià)公式A，它僅由大項(xiàng)的合取所組成，則稱(chēng)它僅由大項(xiàng)的合取所組成，則稱(chēng)A為為A的的（major conjunctive normal form）。）。 一個(gè)公式一個(gè)公式 定理定理1-7.41-7.4 在真值表中，一個(gè)公式的真值為在真值表中，一個(gè)公式

33、的真值為F F的指的指派所對(duì)應(yīng)的大項(xiàng)的合取，即為次公式的主合取范式。派所對(duì)應(yīng)的大項(xiàng)的合取，即為次公式的主合取范式。 利用等價(jià)公式推演主合取范式的步驟：利用等價(jià)公式推演主合取范式的步驟： . 化歸為合取范式?；瘹w為合取范式。 . 除去合取范式中所有永真的合取項(xiàng)。除去合取范式中所有永真的合取項(xiàng)。 . 將合取式中重復(fù)出現(xiàn)的析取項(xiàng)和相同的變?cè)蠈⒑先∈街兄貜?fù)出現(xiàn)的析取項(xiàng)和相同的變?cè)喜?。并?. 對(duì)析取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)刺砑樱▽?duì)析取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?，即添加（P P）式，然后，應(yīng)用分配律展開(kāi)公式，再經(jīng)過(guò)整理。）式，然后，應(yīng)用分配律展開(kāi)公式，再經(jīng)過(guò)整理。1-8 1-8 推理理論推理理論

34、定義定義1-8.1 設(shè)設(shè)A和和C是兩個(gè)命題公式，當(dāng)且僅當(dāng)是兩個(gè)命題公式，當(dāng)且僅當(dāng)AC為一重言式，即為一重言式，即A C，稱(chēng)，稱(chēng)C是是A的有效結(jié)論。或的有效結(jié)論?；駽可由可由A邏輯推出。邏輯推出。 序列序列H1, H2, , Hn和和C是命題公式，當(dāng)且僅當(dāng)是命題公式，當(dāng)且僅當(dāng) H1H2Hn C稱(chēng)稱(chēng)C是一組前提是一組前提H1, H2, , Hn的有效結(jié)論?；虻挠行ЫY(jié)論。或C可由可由H1, H2, , Hn邏輯推出。邏輯推出。 判別有效結(jié)論的過(guò)程就是論證過(guò)程，論證方法有判別有效結(jié)論的過(guò)程就是論證過(guò)程，論證方法有“真真值表法值表法”、“直接證明法直接證明法”和和“間接證明法間接證明法”。 （1）真值表

35、法）真值表法 （1 1）真值表法）真值表法 設(shè)設(shè)P1, P2, , Pn 是出現(xiàn)于前提是出現(xiàn)于前提H1, H2, , Hm和結(jié)論和結(jié)論C中的全部命題變?cè)?，假定?duì)中的全部命題變?cè)?，假定?duì)P1, P2, , Pn作了全部的真作了全部的真值指派，這樣就能對(duì)應(yīng)地確定值指派，這樣就能對(duì)應(yīng)地確定H1, H2, , Hm和和C的所有的所有真值，列出這個(gè)真值表，即可看出真值，列出這個(gè)真值表，即可看出 H1H2Hm C是否成立。是否成立。 因?yàn)槿魪恼嬷当砩险页鲆驗(yàn)槿魪恼嬷当砩险页鯤1, H2, , Hm真值均為真值均為T(mén)的行，的行，對(duì)于每一個(gè)這樣的行，若對(duì)于每一個(gè)這樣的行，若C也有真值也有真值T，則上述蘊(yùn)涵式成，則上述蘊(yùn)涵式成立；或者找出立；或者找出C的真值為的真值為F的行，對(duì)于每一個(gè)這樣的行，的行，對(duì)于每一個(gè)這樣的行，H1, H2, , Hm的真值中至少有一個(gè)為的真值中至少有一個(gè)為F F，則，則上述蘊(yùn)涵式上述蘊(yùn)涵式也成立。也成立。 P-41頁(yè)例題頁(yè)例題1、例題、例題2。 （2 2