第一部分命題邏輯教學(xué)課件

1、第一部分命題邏輯教學(xué)課件第一部分命題邏輯教學(xué)課件 1-1 命題及其表示法1-2 聯(lián)結(jié)詞1-3 命題公式與翻譯1-4 真值表與等價(jià)公式第一章 命題邏輯1-5 重言式與蘊(yùn)涵式1-6 其他聯(lián)結(jié)詞1-7 對(duì)偶與范式1-8 推理理論 1-1 命題及其表示法1-2 聯(lián)結(jié)詞1-3 命題公式第一章 命題邏輯 1-1 命題及其表示法 把對(duì)確定的對(duì)象作出判斷的陳述句稱(chēng)作命題 當(dāng)判斷正確或符合客觀實(shí)際時(shí)，稱(chēng)該命題真（True），用“T”或“1”表示；否則稱(chēng)該命題假（False），用“F”或“0”表示。要點(diǎn)：確定的對(duì)象 作出判斷 陳述句 （見(jiàn)P-2的句子）第一章 命題邏輯 1-1 命題及其表示法 通常把不含有邏輯聯(lián)結(jié)

2、詞的命題稱(chēng)為原子命題或原子（atoms）（自然語(yǔ)言中的單句,P-2的(1)、(2)、(4)） 把由原子命題和邏輯聯(lián)結(jié)詞共同組成的命題稱(chēng)為復(fù)合命題（compositive propositions or compound statements）（自然語(yǔ)言中的復(fù)句， P-2的(9)、(10)）。 通常把不含有邏輯聯(lián)結(jié)詞的命題把由原子命題和命題的符號(hào)化（標(biāo)示符）： 可以用以下兩種形式將命題符號(hào)化： .用（帶下標(biāo)的）大寫(xiě)字母； 例如：P：今天下雨。 .用數(shù)字。 例如：12：今天下雨。 上例中的“P”和“12”稱(chēng)為命題標(biāo)示符。命題常元（proposition constants） 我們把表示具體命題及表

3、示常命題的p，q，r，s等與f，t統(tǒng)稱(chēng)為命題常元。命題的符號(hào)化（標(biāo)示符）：命題常元（proposition c命題變?cè)╬roposition variable） 是以“真、假”或“1，0”為取值范圍的變?cè)?，它未指出符?hào)所表示的具體命題，可以代表任意命題 。指派 當(dāng)命題變?cè)靡粋€(gè)特定命題取代時(shí)，該命題變?cè)拍苡写_定的真值，從而成為一個(gè)命題。稱(chēng)對(duì)命題變?cè)M(jìn)行指派命題變?cè)╬roposition variable）指派 對(duì)任意給定的命題變?cè)猵1,pn的一種取值狀況，稱(chēng)為指派或賦值（assignments） ，用字母，等表示 當(dāng)A對(duì)取值狀況 為真時(shí)，稱(chēng)指派弄真A或是A的成真賦值，記為(A) = 1；

4、反之稱(chēng)指派弄假A或是A的成假賦值，記為 (A) = 0。 對(duì)任意給定的命題變?cè)猵1,pn的一種取1-2 聯(lián)結(jié)詞否定詞“并非”合取詞“并且”析取詞“或” 條件詞“如果，那么” 雙條件詞“當(dāng)且僅當(dāng)”1-2 聯(lián)結(jié)詞否定詞“并非”合取詞“并且”析取詞“或” 條(1)否定（negation ） 定義1-2.1 設(shè)P為一命題，P的否定是一個(gè)新命題，記作“P”。若P為T(mén)， P為F；若P為F， P為T(mén)。聯(lián)結(jié)詞“ ”表示自然語(yǔ)言中的“并非”（not ）。 p p F（0） T（1） T（1） F（0）表1-2.1 否定詞“”的意義 “見(jiàn)假為真，見(jiàn)真為假”p讀作“并非p”或“非p”。(1)否定（negation

5、） p （2）合?。?conjunction ） 定義1-2.2 兩個(gè)命題P和Q的合取是一個(gè)復(fù)合命題，記作PQ。當(dāng)且僅當(dāng)P、Q同時(shí)為T(mén)時(shí)， PQ 為T(mén)，其他情況下， PQ的真值都是F。合取聯(lián)結(jié)詞 “”表示自然語(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)假為假，全真為真。（2）合?。?conjunction ） 1-2.2 合（3）析取詞（disjunction） 定義1-2.3 兩個(gè)命題P和Q的析取是一個(gè)復(fù)

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

7、為F，其他情況下， P Q的真值都是T。條件聯(lián)結(jié)詞 “ ”表示自然語(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)為條件前件，q稱(chēng)為條件后件 前真后假為假，其他為真。（4）條件詞（implication)表1-2.4 條件（5）雙條件(two-way-implication) 定義1-2.5 給定兩個(gè)命題P和Q，其復(fù)合命題P Q稱(chēng)作雙條件命題。當(dāng)P和Q的真值相同時(shí)， P Q 的真值為T(mén)，否則， P Q的真值都是F。雙條

8、件聯(lián)結(jié)詞 “ ”表示自然語(yǔ)言中的“當(dāng)且僅當(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)q”。 相同為真，相異為假。（5）雙條件(two-way-implication)1-2 定義1-3.1 以下四條款規(guī)定了命題公式（proposition formula） 的意義： （1）單個(gè)命題常元或命題變?cè)敲}公式，也稱(chēng)為原子公式或原子。 （2）如果A是命題公式，那么A也是命題公式。 （3）如果A，B

9、是命題公式，那么（AB），（AB），（AB），（AB）也是命題公式。 （4）只有有限步引用條款（1）、（2）、（3）所組成的符號(hào)串是命題公式。 命題公式又稱(chēng)為合式公式Wff（Well formed formula ） Wff的正例和反例見(jiàn)P-10頁(yè)。1-3 命題公式與翻譯 定義1-3.1 以下四條款規(guī)定了命題公式聯(lián)結(jié)詞的優(yōu)先級(jí) 命題公式外層的括號(hào)可以省略；聯(lián)結(jié)詞的優(yōu)先級(jí)：、。 利用加括號(hào)的方法可以提高優(yōu)先級(jí)。范例：如下的Wff ： PQR等價(jià)于Wff ： （PQ）R ）等價(jià)于Wff ： （PQ）R不等價(jià)于Wff ： P（QR）聯(lián)結(jié)詞的優(yōu)先級(jí) 自然語(yǔ)言的語(yǔ)句用Wff 形式化主要是以下幾個(gè)方面：

10、要準(zhǔn)確確定原子命題，并將其形式化。 要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識(shí)別自然語(yǔ)言中的聯(lián)結(jié)詞（有時(shí)它們被省略），否定詞的位置要放準(zhǔn)確。 必要時(shí)可以進(jìn)行改述，即改變?cè)瓉?lái)的敘述方式，但要保證表達(dá)意思一致。 需要的括號(hào)不能省略，而可以省略的括號(hào)，在需要提高公式可讀性時(shí)亦可不省略。 要注意語(yǔ)句的形式化未必是唯一的。 自然語(yǔ)言的語(yǔ)句用Wff 形式化的例子見(jiàn)P-10頁(yè)。自然語(yǔ)言的語(yǔ)句用Wff 形式化 要準(zhǔn)確確定原子命題，并1-4 真值表與等價(jià)公式 定義1-4.1（真值表） 在命題公式Wff中， 對(duì)于公式中分量一切可能的指派組合,公式A的取值可能用下表來(lái)描述，這個(gè)表稱(chēng)為真指表（truth table） 。 真值

11、表的例子見(jiàn)P-13頁(yè)表1-4.1 、表1-4.2 、表1-4.3和P-14頁(yè)表1-4.4、表1-4.5 、表1-4.6 。 定義1-4.2 （ 等價(jià)公式） 給定兩個(gè)命題公式A和B，設(shè)P1，P2， ， Pn為所有出現(xiàn)于A和B中的原子變?cè)?，若給P1，P2， ， Pn任一組真值指派，A和B的真值都相同，則稱(chēng)A和B是等價(jià)的或邏輯相等。記作AB 等價(jià)證明方法1：可以用真值表驗(yàn)證兩個(gè)Wff是否等價(jià)，見(jiàn)P-13的例題5 “真值表法”。1-4 真值表與等價(jià)公式 定義1-4.1（真值表 常用的等價(jià)等值式 E1 AA 雙重否定律 E2 AAA 冪等律 E3 AAA 冪等律 E4 ABBA 交換律 E5 ABBA

12、交換律 E6 (AB)CA(BC) 結(jié)合律 E7 (AB)CA(BC) 結(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 吸收律 常用的等價(jià)等值式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)證吸

13、收率1律0律E14 ABAB 1律0律 定義1-4.3 如果X是Wff A的一部分，且X本身也是一個(gè)Wff，則稱(chēng)X為公式A的子公式。 定理1-4.1 （替換原理Rule of Replacement ，簡(jiǎn)記為RR）如果X是Wff A的子公式，若X Y，如果將A中的X用Y來(lái)置換，所得到的新公式B與公式A等價(jià)，即A B。等價(jià)證明方法2：證明思路： “討論指派法”等價(jià)證明方法3：見(jiàn)P-16的例題7“等價(jià)代換法”。 定義1-4.3 如果X是Wff A的一部分，且 定義1-5.1 對(duì)命題公式A，如果對(duì)A中命題變?cè)囊磺兄概删鍭，則A稱(chēng)為重言式（tautology），又稱(chēng)永真式. 如果至少有一個(gè)指派弄

14、真A，則A稱(chēng)為可滿足式（satisfactable formula or contingency）。 定義1-5.2如果對(duì)A中命題變?cè)囊磺兄概删貯，則稱(chēng)A為不可滿足式或矛盾式（contradiction or absurdity）或永假式 。1-5 重言式與蘊(yùn)涵式 定義1-5.1 對(duì)命題公式A，如果對(duì)A中命題 定理1-5.1 任何兩個(gè)重言式的合取或析取，仍然是一個(gè)重言式。證明思路：“討論指派法”A為T(mén)，B為T(mén)， A與B析取（或合?。┤詾門(mén)， 定理1-5.2 一個(gè)重言式，對(duì)同一分量都用任何Wff置換，其結(jié)果仍為一重言式。證明思路：“討論指派法” 真值與分量的指派無(wú)關(guān)，置換后與仍為T(mén)。 見(jiàn)P

15、-20的例題1 定理1-5.3 設(shè)A、B是兩個(gè)Wff，一個(gè)重言式， AB當(dāng)且僅當(dāng)A B為一重言式。關(guān)于“當(dāng)且僅當(dāng)”的證明思路：雙向證明法，從“AB”出發(fā)推出“A B為一重言式”；再?gòu)摹癆 B為一重言式”出發(fā)推出“AB” 。 定理1-5.1 任何兩個(gè)重 定義1-4.2 （ 等價(jià)公式的另一種定義）當(dāng)命題公式AB為重言式時(shí)，稱(chēng)A邏輯等價(jià)于B，記為A B，它又稱(chēng)為邏輯等價(jià)式（logically equivalent or equivalent）。 定義1-5.3 當(dāng)命題公式AB為重言式時(shí)，稱(chēng)A邏輯蘊(yùn)涵B，記為A B，它又稱(chēng)為邏輯蘊(yùn)涵式 (logically implication)。 常用的邏輯蘊(yùn)涵式

16、見(jiàn)p-21頁(yè)表1-5.2 定義1-4.2 （ 等價(jià)公式的另一種定義）當(dāng)命 定理1-5.4 設(shè)P、Q為任意兩個(gè)命題公式，PQ的充分必要條件是PQ且QP 。 證明思路： 本定理的結(jié)論是“PQ” 本定理的條件是“PQ且QP ” 如果能從條件“PQ且QP ”推出結(jié)論“PQ”，說(shuō)明條件是充分的； 如果能從結(jié)論“PQ”推出條件“PQ且QP ” ， 說(shuō)明條件是必要的。 先證必要性：XXXXXX 再證充分性：XXXXXX 定理1-5.4 設(shè)P、Q為任意兩個(gè)命題公式關(guān)于等價(jià)式和蘊(yùn)涵式的性質(zhì)： （1）AB當(dāng)且僅當(dāng) AB （2）AB當(dāng)且僅當(dāng) AB （3）若AB，則BA 等價(jià)對(duì)稱(chēng)性 （4）若AB，BC，則AC 等價(jià)傳

17、遞性 （5）若AB，則BA 蘊(yùn)涵逆否性 （6）若AB，BC，則AC 蘊(yùn)涵傳遞性 （7）若AB，AA，BB，則AB 蘊(yùn)涵等價(jià)代換 （8）若AB，CB，則ACB （9）若AB，AC，則ABC關(guān)于等價(jià)式和蘊(yùn)涵式的性質(zhì)： 設(shè)A為永真式，p為A中命題變?cè)?，A(B/p) 表示將A中p的所有出現(xiàn)全部代換為公式B后所得的命題公式（稱(chēng)為A的一個(gè)代入實(shí)例），那么 A(B/p)亦為永真式。代入原理（Rule of Substitution），簡(jiǎn)記為RS 設(shè)A為永真式，p為A中命題變?cè)珹(B/p)1-6 其它聯(lián)結(jié)詞 1-6.1 異或詞“”的意義 F（0） T（1） T（1） F（0） F（0） T（1） F（0）

18、T（1） F（0） F（0） T（1） T（1） p q q pp q讀作“p異或q” 相同為假，相異為真。（1）不可兼析?。ó惢颍?定義1-6.1 兩個(gè)命題公式P和Q的不可兼析取是一個(gè)新命題公式，記作P Q。當(dāng)且僅當(dāng)P、Q真值不同時(shí)， P Q 為T(mén)，其他情況下的真值都是F。 1-6 其它聯(lián)結(jié)詞 1-6.1 異或詞“”的意義 F（0異或聯(lián)結(jié)詞的性質(zhì)： （1） PQPQ 交換律（2）（PQ）R P（QR） 結(jié)合律（3）P（QR）（PQ）（PR）分配律（4）（ PQ ）（P Q）（ PQ）（5）（ PQ ） （PQ）（6）（ PP ）F，F(xiàn)P P，T P P 定理1-6.1 設(shè)P、Q和R為命題公式，如果 PQR，則PRQ ，QRP， 且PQR為一矛盾式。 證明思路利用性質(zhì)（6）。異或聯(lián)結(jié)詞的性質(zhì)： 表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的條件否定” 前真后假為真其余為假。（2）條件否定 定義1-6.2 設(shè)P和Q是兩個(gè)