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

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

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

3、rue），用“T”或“1”表示；否則稱該命題假（False），用“F”或“0”表示。要點(diǎn)：確定的對象 作出判斷 陳述句,通常把不含有邏輯聯(lián)結(jié)詞的命題稱為原子命題或原子（atoms）（自然語言中的單句）,把由原子命題和邏輯聯(lián)結(jié)詞共同組成的命題稱為復(fù)合命題（compositive propositions or compound statements）（自然語

4、言中的復(fù)句）。,命題的符號(hào)化（標(biāo)示符）： 可以用以下兩種形式將命題符號(hào)化： ?.用（帶下標(biāo)的）大寫字母； 例如：P：今天下雨。 ?.用數(shù)字。 例如：[12]：今天下雨。 上例中的“P”和“[12]”稱為命題標(biāo)示符。,,命題常元（proposition constants） 我們把表示具體命題及表示常命題的p，q，r，s等與f，t統(tǒng)稱為命題常元。,命題變元（proposition varia

5、ble） 是以“真、假”或“1，0”為取值范圍的變元，它未指出符號(hào)所表示的具體命題，可以代表任意命題 。,指派 當(dāng)命題變元用一個(gè)特定命題取代時(shí)，該命題變元才能有確定的真值，從而成為一個(gè)命題。稱對命題變元進(jìn)行指派,對任意給定的命題變元p1,…,pn的一種取值狀況，稱為指派或賦值（assignments） ，用字母?，?等表示,當(dāng)A對取值狀況 ? 為真時(shí)，稱指派?弄真A或?是A的成真賦值，記為?(A) = 1；

6、反之稱指派?弄假A或?是A的成假賦值，記為? (A) = 0。,3-2 聯(lián)結(jié)詞,否定詞“并非”,合取詞“并且”,析取詞“或”,條件詞“如果……，那么……”,雙條件詞“當(dāng)且僅當(dāng)”,(1)否定（negation ） 定義3-2.1 設(shè)P為一命題，P的否定是一個(gè)新命題，記作“┐P”。若P為T， ┐P為F；若P為F， ┐P為T。聯(lián)結(jié)詞“ ┐ ”表示自然語言中的“并非”（not ）。,表3-2.1 否定詞“┐”的意

7、義,“見假為真，見真為假”┐p讀作“并非p”或“非p”。,（2）合?。?conjunction ） 定義3-2.2 兩個(gè)命題P和Q的合取是一個(gè)復(fù)合命題，記作P∧Q。當(dāng)且僅當(dāng)P、Q同時(shí)為T時(shí)， P∧Q 為T，其他情況下， P∧Q的真值都是F。合取聯(lián)結(jié)詞 “∧”表示自然語言中的 “并且”（and ）。,3-2.2 合取詞“∧”的意義,p∧q讀作“p并且q”或“p且q”,見假為假，全真為真。,（3）析取詞（disj

8、unction） 定義3-2.3 兩個(gè)命題P和Q的析取是一個(gè)復(fù)合命題，記作P ∨ Q。當(dāng)且僅當(dāng)P、Q同時(shí)為F時(shí)， P ∨ Q 為F，其他情況下， P ∨ Q的真值都是T。析取聯(lián)結(jié)詞 “∨ ”表示自然語言中的 “ 或”（or ）。,表 1-2.3 析取詞“∨”的意義,見真為真，全假為假。,p∨q讀作“p或者q”、“p或q”。,（4）條件詞（implication) 定義3-2.4 給定兩個(gè)命題

9、P和Q，其條件命題是一個(gè)復(fù)合命題，記作P → Q。當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時(shí)， P → Q 的真值為F，其他情況下， P → Q的真值都是T。條件聯(lián)結(jié)詞 “→ ”表示自然語言中的 “如果…，那么…” （if…then…）。,表3-2.4 條件詞“ → ”的意義,p→q中的p稱為條件前件，q稱為條件后件,前真后假為假，其他為真。,（5）雙條件(two-way-implication) 定義3-2.5 給定兩個(gè)

10、命題P和Q，其復(fù)合命題P ? Q稱作雙條件命題。當(dāng)P和Q的真值相同時(shí)， P ? Q 的真值為T，否則， P ? Q的真值都是F。雙條件聯(lián)結(jié)詞 “? ”表示自然語言中的“當(dāng)且僅當(dāng)”（if and only if）。,,3-2.5 雙向條件詞“ ? ”的意義,p?q讀作“p與q互為條件”，“p當(dāng)且僅當(dāng)q”。,相同為真，相異為假。,定義3-3.1 以下四條款規(guī)定了命題公式（proposition formula） 的意義：,（1）單

11、個(gè)命題常元或命題變元是命題公式，也稱為原子公式或原子。 （2）如果A是命題公式，那么┐A也是命題公式。 （3）如果A，B是命題公式，那么（A∧B），（A∨B），（A→B），（A?B）也是命題公式。 （4）只有有限步引用條款（1）、（2）、（3）所組成的符號(hào)串是命題公式。 命題公式又稱為合式公式Wff（Well formed formula ） Wff的正例

12、和反例見其他書上表述。,3-3 命題公式與翻譯,聯(lián)結(jié)詞的優(yōu)先級(jí) 命題公式外層的括號(hào)可以省略；聯(lián)結(jié)詞的優(yōu)先級(jí)：┐、∧、∨、→、?。 利用加括號(hào)的方法可以提高優(yōu)先級(jí)。范例：如下的Wff ： P∧Q→R等價(jià)于Wff ： （（P∧Q）→R ）等價(jià)于Wff ： （P∧Q）→R不等價(jià)于Wff ： P∧（Q→R）,自然語言的語句用Wff 形式化主要是以下幾個(gè)方面：,① 要準(zhǔn)確確定

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

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

15、 E1 ┐┐A?A 雙重否定律 E2 A∨A?A 冪等律 E3 A∧A?A 冪等律 E4 A∨B?B∨A

16、 交換律 E5 A∧B?B∧A 交換律 E6 (A∨B)∨C?A∨(B∨C) 結(jié)合律 E7 (A∧B)∧C?A∧(B∧C) 結(jié)合律 E8 A∧(B∨C) ? (A∧B)∨(A∧C) 分配律 E9 A∨(B∧C) ? (A∨B)∧(

17、A∨C) 分配律 E10 ┐(A∨B) ?┐A∧┐B 德摩根律 E11 ┐(A∧B) ?┐A∨┐B 德摩根律 E12 A∨(A∧B) ?A 吸收律 E13 A∧(A∨B) ?A 吸收律,E14 A→B?┐A∨B

18、 E15 A? B? (A→B)∧(B→A)E16 A∨t?tE17 A∧t?AE18 A∨f?AE19 A∧f?fE20 A∨┐A?t 排中律E21 A∧┐A?f 矛盾律E22 ┐t?f, ┐f?t 否定律 E23 A∧B→C?A→(B

19、→C) E24 A→B? ┐B→┐A 逆否律E25 (A→B)∧(A→┐B) ?┐A,,1律,0律,,定義3-4.3 如果X是Wff A的一部分，且X本身也是一個(gè)Wff，則稱X為公式A的子公式。 定理3-4.1 （替換原理Rule of Replacement ，簡記為RR）如果X是Wff A的子公式，若X ? Y，如果將A中的X用Y來置換，所得到的新公式B與公

20、式A等價(jià)，即A ? B。等價(jià)證明方法2：證明思路： “討論指派法”等價(jià)證明方法3： “等價(jià)代換法”。,定義3-5.1 對命題公式A，如果對A中命題變元的一切指派均弄真A，則A稱為重言式（tautology），又稱永真式.,如果至少有一個(gè)指派弄真A，則A稱為可滿足式（satisfactable formula or contingency）。,定義3-5.2如果對A中命題變元的一切指派均弄假A，則稱A為不可滿足式或矛

21、盾式（contradiction or absurdity）或永假式 。,3-5 重言式與蘊(yùn)涵式,,定理3-5.1 任何兩個(gè)重言式的合取或析取，仍然是一個(gè)重言式。證明思路：“討論指派法”A為T，B為T， A與B析取（或合?。┤詾門，  定理3-5.2 一個(gè)重言式，對同一分量都用任何Wff置換，其結(jié)果仍為一重言式。證明思路：“討論指派法” 真值與分量的指派無關(guān)，置換后與仍為T。 定理3-5.3

22、 設(shè)A、B是兩個(gè)Wff，一個(gè)重言式， A?B當(dāng)且僅當(dāng)A ?B為一重言式。關(guān)于“當(dāng)且僅當(dāng)”的證明思路：雙向證明法，從“A?B”出發(fā)推出“A ?B為一重言式”；再從“A ?B為一重言式”出發(fā)推出“A?B” 。,定義3-4.2‘ （ 等價(jià)公式的另一種定義）當(dāng)命題公式A?B為重言式時(shí)，稱A邏輯等價(jià)于B，記為A ? B，它又稱為邏輯等價(jià)式（logically equivalent or equivalent）。,定義3-5.3

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

24、出條件“P?Q且Q?P ” ， 說明條件是必要的。 先證必要性：XXXXXX 再證充分性：XXXXXX ,關(guān)于等價(jià)式和蘊(yùn)涵式的性質(zhì)： （1）A?B當(dāng)且僅當(dāng) ?A?B （2）A?B當(dāng)且僅當(dāng) ?A→B （3）若A?B，則B?A 等價(jià)對稱性 （4）若A?B，

25、B?C，則A?C 等價(jià)傳遞性 （5）若A?B，則┐B?┐A 蘊(yùn)涵逆否性 （6）若A?B，B?C，則A?C 蘊(yùn)涵傳遞性 （7）若A?B，A?A‘，B?B’，則A‘?B’ 蘊(yùn)涵等價(jià)代換 （8）若A?B，C?B，則A∨C?B （9）若A?B，A?C，則A?B∧C,設(shè)A為永真式，p為A中命題變元，A(B/p) 表示將A中p的所有出現(xiàn)全

26、部代換為公式B后所得的命題公式（稱為A的一個(gè)代入實(shí)例），那么 A(B/p)亦為永真式。,◆代入原理（Rule of Substitution），簡記為RS,3-6 其它聯(lián)結(jié)詞,3-6.1 異或詞“∨”的意義,p ∨ q讀作“p異或q”,相同為假，相異為真。,,（1）不可兼析?。ó惢颍?定義3-6.1 兩個(gè)命題公式P和Q的不可兼析取是一個(gè)新命題公式，記作P ∨ Q。當(dāng)且僅當(dāng)P、Q真值不同時(shí)， P ∨ Q 為T，其他

27、情況下的真值都是F。,,,,,異或聯(lián)結(jié)詞的性質(zhì)： （1） P∨Q?P∨Q 交換律（2）（P∨Q）∨R ?P∨（Q∨R） 結(jié)合律（3）P∧（Q∨R）?（P∧Q）∨（P∧R）分配律（4）（ P∨Q ）?（P∧ ┐ Q）∨（ ┐P∧Q）（5）（ P∨Q ）? ┐（P?Q）（6）（ P∨P ）?F，F(xiàn)∨P ? P，T ∨P ?

28、┐P 定理3-6.1 設(shè)P、Q和R為命題公式，如果 P∨Q?R，則P∨R?Q ，Q∨R?P， 且P∨Q∨R為一矛盾式。 證明思路利用性質(zhì)（6）。,,,,,,,,,,,,,,,,,,,表3-6.2 異或詞“?”的意義,p ? q讀作“p和q的條件否定”,前真后假為真其余為假。,（2）條件否定 定義3-6.2 設(shè)P和Q是兩個(gè)命題公式， P和Q的條件否定是一個(gè)新命題公式，記作P ?

29、Q。當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時(shí)， P ? Q 為T，其他情況下的真值都是F。 根據(jù)此定義，可知 P ? Q ? ┐（P → Q）,（3）與非 定義3-6.3 設(shè)P和Q是兩個(gè)命題公式， P和Q的與非是一個(gè)新命題公式，記作P ? Q。當(dāng)且僅當(dāng)P和Q的真值都為 T時(shí)， P ? Q 為F ，其他情況下P ? Q的真值都是T 。 根據(jù)此定義，可知 P ? Q ? ┐（P∧Q）P ? Q的3個(gè) 性質(zhì)見P-26頁

30、。,全真為假見假為真。,表3-6.3 與非詞“?”的意義,（4）或非 定義3-6.4 設(shè)P和Q是兩個(gè)命題公式， P和Q的或非是一個(gè)新命題公式，記作P ? Q。當(dāng)且僅當(dāng)P和Q的真值都為 F 時(shí)， P ? Q 為T ，其他情況下P ? Q的真值都是F 。 根據(jù)此定義，可知 P ? Q ? ┐（P ∨ Q）P ? Q的 性質(zhì)與聯(lián)結(jié)詞性質(zhì)留給大家自己推算。,表3-6.4 或非詞“?”的意義,全假為真見真為假。,

31、3-7 對偶與范式,定義3-7.1 設(shè)給定的命題公式A僅含聯(lián)結(jié)詞 ┐，∧，∨，A*為將A中符號(hào)∧，∨，t，f分別改換為∨，∧，f，t后所得的公式，那么稱A*為A的對偶式（dual）。 顯然， A 也為A*的對偶式。,定理3-7.1 設(shè)公式A和A*中僅含命題變元p1,…,pn，及聯(lián)結(jié)詞┐，∧，∨；則 ┐A(p1， p2 …, pn) ?A*(┐p1， ┐p2 …, ┐pn) A(┐p1， ┐p2 …

32、, ┐pn)? ┐ A*(p1， p2 …, pn)  證明思路：利用德摩根定律 P∨Q ? ┐（┐P∧┐Q） A ? ┐ A* 推廣到p1， p2 …, pn ,,,定理3-7.2 設(shè)公式A和B中僅含命題變元p1,…,pn，如果A?B，則A*?B*。,文字(letters)：指命題常元、變元及它們的否定，前者又稱正文字，后者則稱負(fù)文字。,析取子句(disjunctive c

33、lauses)：指文字或若干文字的析取。,合取子句(conjunctive clauses)：指文字或若干文字的合取。,互補(bǔ)文字對(complemental pairs of letters) ：指形如L，┐L（L為文字）的一對字符。,定義3-7.2 命題公式A‘稱為公式A的合取范式（conjunctive normal form）如果 （1）A' ? A （2）A‘為一析取子句或若干析取子句的合取。

34、 A‘形如：A1∧A2∧…∧An (n?1),定義3-7.3命題公式A‘稱為公式A的析取范式（disjunctive normal form），如果 （1）A' ? A （2）A‘為一合取子句或若干合取子句的析取。 A‘形如：A1∨A2∨…∨An (n?1),求一個(gè)命題公式的合取范式或析取范式的步驟： ?. 將公式中的聯(lián)結(jié)詞化歸成僅含∨ 、∧、┐；

35、 ?. 利用德 . 摩根定律將否定符號(hào)┐直接內(nèi)移到各個(gè)命題變元之前； ?. 利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。定義3-7.4 n個(gè)命題變元的合取式，稱作布爾合取或小項(xiàng)，其中每個(gè)變元與它的否定不能同時(shí)出現(xiàn)，但兩者必須出現(xiàn)且僅出現(xiàn)一次。 一般來說，n個(gè)命題變元共有2n個(gè)小項(xiàng)。,根據(jù)定義可知，沒有兩個(gè)小項(xiàng)是等價(jià)的，且每個(gè)小項(xiàng)都只對應(yīng)P和Q的一組真值指派，使得該小項(xiàng)的真值為T。

36、 以上結(jié)論可推廣到三個(gè)以上的變元情況，并且由此可以作出一種編碼，使n個(gè)變元的小項(xiàng)可以很快地寫出來。 小項(xiàng)有如下性質(zhì)： ?. 每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為T，在其余2n -1種真值指派情況下均為F。 ?. 任意兩個(gè)不同小項(xiàng)的合取式永假。 ?. 全體小項(xiàng)的析取式永為真。 2n -1 ? mi =m0∨m1

37、 ∨ …∨m 2n -1 ?T i=0,定義3-7.5 對于給定的命題公式A，如果有一個(gè)等價(jià)公式A’，它僅由小項(xiàng)的析取所組成，則稱A’為A的主析取范式（major disjunctive normal form）。 一個(gè)公式主析取范式可以構(gòu)成真值表的方法寫出。 定理3-7.3 在真值表中，一個(gè)公式的真值為T的指派所對應(yīng)的小項(xiàng)的析取，即為次公式的主析取范式。 利用等價(jià)公式推演主析取范

38、式的步驟： ?. 化歸為析取范式。 ?. 除去析取范式中所有永假的析取式。 ?. 將析取式中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變元合并。 ? . 對合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變元，即添加（P ∨ ┐ P）式，然后，應(yīng)用分配律展開公式，再經(jīng)過整理。,定義3-7.6 n個(gè)命題變元的析取式，稱作布爾析取或大項(xiàng)，其中每個(gè)變元與它的否定不能同時(shí)出現(xiàn)，但兩者必須出現(xiàn)且僅出現(xiàn)一次。 一般來

39、說，n個(gè)命題變元共有2n個(gè)大項(xiàng)。 大項(xiàng)有如下性質(zhì)： ?. 每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為F，在其余2n -1種真值指派情況下均為T。 ?. 任意兩個(gè)不同大項(xiàng)的析取式永真。 ?. 全體大項(xiàng)的合取式永為假。 2n -1 ? Mi =M0∧M1 ∧ …∧M 2n -1 ?F

40、i=0,定義3-7.7 對于給定的命題公式A，如果有一個(gè)等價(jià)公式A’，它僅由大項(xiàng)的合取所組成，則稱A’為A的主合取范式（major conjunctive normal form）。 一個(gè)公式主合取范式可以構(gòu)成真值表的方法寫出。 定理3-7.4 在真值表中，一個(gè)公式的真值為F的指派所對應(yīng)的大項(xiàng)的合取，即為次公式的主合取范式。 利用等價(jià)公式推演主合取范式的步驟： ?. 化歸為合取范

41、式。 ?. 除去合取范式中所有永真的合取項(xiàng)。 ?. 將合取式中重復(fù)出現(xiàn)的析取項(xiàng)和相同的變元合并。 ? . 對析取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變元，即添加（P ∧┐ P）式，然后，應(yīng)用分配律展開公式，再經(jīng)過整理。,5-1 命題邏輯推理理論,定義5-1.1 設(shè)A和C是兩個(gè)命題公式，當(dāng)且僅當(dāng)A→C為一重言式，即A ? C，稱C是A的有效結(jié)論?；駽可由A邏輯推出。 序列H1, H2,

42、…, Hn和C是命題公式，當(dāng)且僅當(dāng) H1∧H2∧…∧Hn ? C稱C是一組前提H1, H2, …, Hn的有效結(jié)論?；駽可由H1, H2, …, Hn邏輯推出。 判別有效結(jié)論的過程就是論證過程，論證方法有“真值表法”、“直接證明法”和“間接證明法”。 （1）真值表法,（1）真值表法 設(shè)P1, P2, …, Pn 是出現(xiàn)于前提H1,

43、H2, …, Hm和結(jié)論C中的全部命題變元，假定對P1, P2, …, Pn作了全部的真值指派，這樣就能對應(yīng)地確定H1, H2, …, Hm和C的所有真值，列出這個(gè)真值表，即可看出 H1∧H2∧…∧Hm ? C是否成立。 因?yàn)槿魪恼嬷当砩险页鯤1, H2, …, Hm真值均為T的行，對于每一個(gè)這樣的行，若C也有真值T，則上述蘊(yùn)涵式成立；或者找出C的真值為F的行，對于每一個(gè)這樣的行，H1, H2,

44、…, Hm的真值中至少有一個(gè)為F，則上述蘊(yùn)涵式也成立。,（2）直接證明法 直接證明法就是由一組前提，利用一些公認(rèn)的推理規(guī)則，根據(jù)已知的等價(jià)或蘊(yùn)涵式，推演得到有效的結(jié)論。 P規(guī)則（前提引入）：前提在推導(dǎo)過程中的任何時(shí)候都可以引入。 T規(guī)則（結(jié)論引用）：在推導(dǎo)中，如果有一個(gè)或多個(gè)公式重言蘊(yùn)涵著公式S（結(jié)論），則公式S可以引入推導(dǎo)之中。 常用的蘊(yùn)涵式和等價(jià)式見書上所羅列。

45、 直接證明法例題1：,（3）間接證明法 定義5-1.2 設(shè)P1, P2, …, Pn 是出現(xiàn)于前提H1, H2, …, Hm中的全部命題變元，對于P1, P2, …, Pn的一些真值指派，如果能使H1∧H2∧…∧Hm 的真值為T，則稱公式H1, H2, …, Hm是相容的。如果對于P1, P2, …, Pn的每一組真值指派，使得H1∧H2∧…∧Hm 的真值均為F，則稱公式H1, H2, …, Hm是

46、不相容的。 不相容的概念用于命題公式的證明： 設(shè)有一組前提H1, H2, …, Hm，要推出結(jié)論C，即要證H1∧H2∧…∧Hm? C，記作S ? C，即┐C →┐S為永真，或 C∨ ┐S 為永真，故 ┐C∧S 為永假。因此要證H1∧H2∧…∧Hm? C，只要證H1, H2, …, Hm與┐C是不相容的。,間接證明法的另一種情況（CP規(guī)則） 若要證明H1∧H2∧…∧Hm?（R→C）

47、。 將H1∧H2∧…∧Hm記作S， 即要證 S ? （R→C） 或要證 S ? （ ┐R∨C） 故 S→（┐R∨C） 為永真式 因?yàn)?S→（┐R∨C） ? ┐S∨（┐R∨C） ?（┐S∨┐R ）∨C ?┐（S∧R ）∨