第一篇數(shù)理邏輯

第一篇數(shù)理邏輯演示文稿當(dāng)前1頁(yè)，總共45頁(yè)。（優(yōu)選）第一篇數(shù)理邏輯當(dāng)前2頁(yè)，總共45頁(yè)。

第一章

命題邏輯當(dāng)前3頁(yè)，總共45頁(yè)。

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推理理論當(dāng)前4頁(yè)，總共45頁(yè)。第一章命題演算及其形式系統(tǒng)

1-1命題及其表示法

把對(duì)確定的對(duì)象作出判斷的陳述句稱作命題（propositionsorstatements）

當(dāng)判斷正確或符合客觀實(shí)際時(shí)，稱該命題真（True），用“T”或“1”表示；否則稱該命題假（False），用“F”或“0”表示。要點(diǎn)：確定的對(duì)象

作出判斷

陳述句（見P-2的句子）當(dāng)前5頁(yè)，總共45頁(yè)。

通常把不含有邏輯聯(lián)結(jié)詞的命題稱為原子命題或原子（atoms）（自然語(yǔ)言中的單句,P-2的(1)、(2)、(4)）

把由原子命題和邏輯聯(lián)結(jié)詞共同組成的命題稱為復(fù)合命題（compositivepropositionsorcompoundstatements）（自然語(yǔ)言中的復(fù)句，P-2的(9)、(10)）。當(dāng)前6頁(yè)，總共45頁(yè)。命題的符號(hào)化（標(biāo)示符）：可以用以下兩種形式將命題符號(hào)化：.用（帶下標(biāo)的）大寫字母；例如：P：今天下雨。.用數(shù)字。例如：[12]：今天下雨。上例中的“P”和“[12]”稱為命題標(biāo)示符。命題常元（propositionconstants）我們把表示具體命題及表示常命題的p，q，r，s等與f，t統(tǒng)稱為命題常元。當(dāng)前7頁(yè)，總共45頁(yè)。命題變?cè)╬ropositionvariable）是以“真、假”或“1，0”為取值范圍的變?cè)?，它未指出符?hào)所表示的具體命題，可以代表任意命題。指派

當(dāng)命題變?cè)靡粋€(gè)特定命題取代時(shí)，該命題變?cè)拍苡写_定的真值，從而成為一個(gè)命題。稱對(duì)命題變?cè)M(jìn)行指派當(dāng)前8頁(yè)，總共45頁(yè)。

對(duì)任意給定的命題變?cè)猵1,…,pn的一種取值狀況，稱為指派或賦值（assignments）

，用字母，等表示

當(dāng)A對(duì)取值狀況為真時(shí)，稱指派弄真A或是A的成真賦值，記為(A)=1；反之稱指派弄假A或是A的成假賦值，記為

(A)=0。當(dāng)前9頁(yè)，總共45頁(yè)。1-2聯(lián)結(jié)詞否定詞“并非”合取詞“并且”析取詞“或”條件詞“如果……，那么……”

雙條件詞“當(dāng)且僅當(dāng)”當(dāng)前10頁(yè)，總共45頁(yè)。(1)否定（negation）

定義1-2.1設(shè)P為一命題，P的否定是一個(gè)新命題，記作“┐P”。若P為T，┐P為F；若P為F，┐P為T。聯(lián)結(jié)詞“

┐”表示自然語(yǔ)言中的“并非”（not）。

p

┐p

F（0）

T（1）

T（1）

F（0）表1-2.1

否定詞“┐”的意義

“見假為真，見真為假”┐p讀作“并非p”或“非p”。當(dāng)前11頁(yè)，總共45頁(yè)。（2）合取（

conjunction）定義1-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é)詞

“∧”表示自然語(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）p∧q讀作“p并且q”或“p且q”

見假為假，全真為真。當(dāng)前12頁(yè)，總共45頁(yè)。（3）析取詞（disjunction）定義1-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é)詞

“∨”表示自然語(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）見真為真，全假為假。p∨q讀作“p或者q”、“p或q”。當(dāng)前13頁(yè)，總共45頁(yè)。（4）條件詞（implication)

定義1-2.4給定兩個(gè)命題P和Q，其條件命題是一個(gè)復(fù)合命題，記作P→

Q。當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時(shí)，P→

Q的真值為F，其他情況下，P→

Q的真值都是T。條件聯(lián)結(jié)詞

“→”表示自然語(yǔ)言中的

“如果…，那么…”（if…then…）。

表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）p→q中的p稱為條件前件，q稱為條件后件

前真后假為假，其他為真。當(dāng)前14頁(yè)，總共45頁(yè)。（5）雙條件(two-way-implication)

定義1-2.5給定兩個(gè)命題P和Q，其復(fù)合命題P

Q稱作雙條件命題。當(dāng)P和Q的真值相同時(shí)，P

Q的真值為T，否則，P

Q的真值都是F。雙條件聯(lián)結(jié)詞

“”表示自然語(yǔ)言中的“當(dāng)且僅當(dāng)”（ifandonlyif）。

1-2.5雙向條件詞“”的意義

p

q

pq

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”。

相同為真，相異為假。當(dāng)前15頁(yè)，總共45頁(yè)。定義1-3.1

以下四條款規(guī)定了命題公式（propositionformula）的意義：

（1）單個(gè)命題常元或命題變?cè)敲}公式，也稱為原子公式或原子。（2）如果A是命題公式，那么┐A也是命題公式。（3）如果A，B是命題公式，那么（A∧B），（A∨B），（A→B），（AB）也是命題公式。

（4）只有有限步引用條款（1）、（2）、（3）所組成的符號(hào)串是命題公式。命題公式又稱為合式公式Wff（Wellformedformula）

Wff的正例和反例見P-10頁(yè)。1-3命題公式與翻譯當(dāng)前16頁(yè)，總共45頁(yè)。聯(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）當(dāng)前17頁(yè)，總共45頁(yè)。自然語(yǔ)言的語(yǔ)句用Wff

形式化主要是以下幾個(gè)方面：

①

要準(zhǔn)確確定原子命題，并將其形式化。

②

要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識(shí)別自然語(yǔ)言中的聯(lián)結(jié)詞（有時(shí)它們被省略），否定詞的位置要放準(zhǔn)確。

③

必要時(shí)可以進(jìn)行改述，即改變?cè)瓉淼臄⑹龇绞?，但要保證表達(dá)意思一致。④

需要的括號(hào)不能省略，而可以省略的括號(hào)，在需要提高公式可讀性時(shí)亦可不省略。

⑤要注意語(yǔ)句的形式化未必是唯一的。自然語(yǔ)言的語(yǔ)句用Wff

形式化的例子見P-10頁(yè)。當(dāng)前18頁(yè)，總共45頁(yè)。1-4真值表與等價(jià)公式定義1-4.1（真值表）在命題公式Wff中，對(duì)于公式中分量一切可能的指派組合,公式A的取值可能用下表來描述，這個(gè)表稱為真指表（truthtable）。真值表的例子見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è)艚oP1，P2，…，Pn任一組真值指派，A和B的真值都相同，則稱A和B是等價(jià)的或邏輯相等。記作AB

等價(jià)證明方法1：可以用真值表驗(yàn)證兩個(gè)Wff是否等價(jià)，見P-13的例題5“真值表法”。當(dāng)前19頁(yè)，總共45頁(yè)。

常用的等價(jià)等值式

E1

┐┐AA雙重否定律

E2A∨AA冪等律

E3A∧AA冪等律

E4A∨BB∨A交換律

E5A∧BB∧A交換律

E6(A∨B)∨CA∨(B∨C)結(jié)合律

E7(A∧B)∧CA∧(B∧C)結(jié)合律

E8A∧(B∨C)

(A∧B)∨(A∧C)分配律

E9A∨(B∧C)

(A∨B)∧(A∨C)分配律

E10

┐(A∨B)

┐A∧┐B德摩根律

E11

┐(A∧B)

┐A∨┐B德摩根律

E12A∨(A∧B)

A吸收律

E13A∧(A∨B)

A吸收律當(dāng)前20頁(yè)，總共45頁(yè)。E14A→B┐A∨BE15AB(A→B)∧(B→A)E16A∨ttE17A∧tAE18A∨fAE19A∧ffE20A∨┐At排中律E21A∧┐Af矛盾律E22

┐tf,┐ft否定律E23A∧B→CA→(B→C)E24A→B┐B→┐A逆否律E25(A→B)∧(A→┐B)

┐AP-16例題6驗(yàn)證吸收率1律0律當(dāng)前21頁(yè)，總共45頁(yè)。

定義1-4.3

如果X是WffA的一部分，且X本身也是一個(gè)Wff，則稱X為公式A的子公式。

定理1-4.1（替換原理RuleofReplacement，簡(jiǎn)記為RR）如果X是WffA的子公式，若XY，如果將A中的X用Y來置換，所得到的新公式B與公式A等價(jià)，即AB。等價(jià)證明方法2：證明思路：“討論指派法”等價(jià)證明方法3：見P-16的例題7“等價(jià)代換法”。當(dāng)前22頁(yè)，總共45頁(yè)。定義1-5.1對(duì)命題公式A，如果對(duì)A中命題變?cè)囊磺兄概删鍭，則A稱為重言式（tautology），又稱永真式.

如果至少有一個(gè)指派弄真A，則A稱為可滿足式（satisfactableformulaorcontingency）。定義1-5.2如果對(duì)A中命題變?cè)囊磺兄概删貯，則稱A為不可滿足式或矛盾式（contradictionorabsurdity）或永假式。1-5重言式與蘊(yùn)涵式當(dāng)前23頁(yè)，總共45頁(yè)。

定理1-5.1

任何兩個(gè)重言式的合取或析取，仍然是一個(gè)重言式。證明思路：“討論指派法”A為T，B為T，A與B析?。ɑ蚝先。┤詾門，定理1-5.2

一個(gè)重言式，對(duì)同一分量都用任何Wff置換，其結(jié)果仍為一重言式。證明思路：“討論指派法”真值與分量的指派無(wú)關(guān)，置換后與仍為T。見P-20的例題1

定理1-5.3

設(shè)A、B是兩個(gè)Wff，一個(gè)重言式，AB當(dāng)且僅當(dāng)AB為一重言式。關(guān)于“當(dāng)且僅當(dāng)”的證明思路：雙向證明法，從“AB”出發(fā)推出“AB為一重言式”；再?gòu)摹癆B為一重言式”出發(fā)推出“AB”。當(dāng)前24頁(yè)，總共45頁(yè)。定義1-4.2‘（

等價(jià)公式的另一種定義）當(dāng)命題公式AB為重言式時(shí)，稱A邏輯等價(jià)于B，記為AB，它又稱為邏輯等價(jià)式（logicallyequivalentorequivalent）。定義1-5.3當(dāng)命題公式A→B為重言式時(shí)，稱A邏輯蘊(yùn)涵B，記為AB，它又稱為邏輯蘊(yùn)涵式(logically

implication)。

常用的邏輯蘊(yùn)涵式見p-21頁(yè)表1-5.2當(dāng)前25頁(yè)，總共45頁(yè)。定理1-5.4設(shè)P、Q為任意兩個(gè)命題公式，PQ的充分必要條件是PQ且QP

。證明思路：本定理的結(jié)論是“PQ”

本定理的條件是“PQ且QP

”

如果能從條件“PQ且QP

”推出結(jié)論“PQ”，說明條件是充分的；如果能從結(jié)論“PQ”推出條件“PQ且QP

”，說明條件是必要的。先證必要性：XXXXXX

再證充分性：XXXXXX當(dāng)前26頁(yè)，總共45頁(yè)。關(guān)于等價(jià)式和蘊(yùn)涵式的性質(zhì)：

（1）AB當(dāng)且僅當(dāng)AB

（2）AB當(dāng)且僅當(dāng)A→B

（3）若AB，則BA等價(jià)對(duì)稱性（4）若AB，BC，則AC等價(jià)傳遞性（5）若AB，則┐B┐A蘊(yùn)涵逆否性（6）若AB，BC，則AC蘊(yùn)涵傳遞性（7）若AB，AA‘，BB’，則A‘B’

蘊(yùn)涵等價(jià)代換

（8）若AB，CB，則A∨CB

（9）若AB，AC，則AB∧C當(dāng)前27頁(yè)，總共45頁(yè)。

設(shè)A為永真式，p為A中命題變?cè)珹(B/p)表示將A中p的所有出現(xiàn)全部代換為公式B后所得的命題公式（稱為A的一個(gè)代入實(shí)例），那么A(B/p)亦為永真式?！舸朐恚≧uleofSubstitution），簡(jiǎn)記為RS當(dāng)前28頁(yè)，總共45頁(yè)。1-6其它聯(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”

相同為假，相異為真。（1）不可兼析?。ó惢颍┒x1-6.1兩個(gè)命題公式P和Q的不可兼析取是一個(gè)新命題公式，記作P∨

Q。當(dāng)且僅當(dāng)P、Q真值不同時(shí)，P∨

Q為T，其他情況下的真值都是F。

當(dāng)前29頁(yè)，總共45頁(yè)。異或聯(lián)結(jié)詞的性質(zhì)：

（1）P∨QP∨Q交換律（2）（P∨Q）∨RP∨（Q∨R）結(jié)合律（3）P∧（Q∨R）（P∧Q）∨（P∧R）分配律（4）（P∨Q

）（P∧┐

Q）∨（┐P∧Q）（5）（P∨Q

）┐（PQ）（6）（P∨P

）F，F(xiàn)∨PP，T∨P

┐P

定理1-6.1設(shè)P、Q和R為命題公式，如果

P∨QR，則P∨RQ

，Q∨RP，且P∨Q∨R為一矛盾式。證明思路利用性質(zhì)（6）。當(dāng)前30頁(yè)，總共45頁(yè)。表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è)命題公式，P和Q的條件否定是一個(gè)新命題公式，記作P

Q。當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時(shí)，P

Q為T，其他情況下的真值都是F。根據(jù)此定義，可知

P

Q┐（P→

Q）當(dāng)前31頁(yè)，總共45頁(yè)。（3）與非定義1-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頁(yè)。

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全真為假見假為真。表1-6.3與非詞“”的意義當(dāng)前32頁(yè)，總共45頁(yè)。（4）或非定義1-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的3個(gè)性質(zhì)見P-26頁(yè)。聯(lián)結(jié)詞小結(jié)見P-27頁(yè)。表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全假為真見真為假。當(dāng)前33頁(yè)，總共45頁(yè)。1-7對(duì)偶與范式定義1-7.1設(shè)給定的命題公式A僅含聯(lián)結(jié)詞

┐，∧，∨，A*為將A中符號(hào)∧，∨，t，f分別改換為∨，∧，f，t后所得的公式，那么稱A*為A的對(duì)偶式（dual）。顯然，A

也為A*的對(duì)偶式。見P-29頁(yè)例題1

定理1-7.1設(shè)公式A和A*中僅含命題變?cè)猵1,…,pn，及聯(lián)結(jié)詞┐，∧，∨；則┐A(p1，

p2

…,pn)

A*(┐p1，

┐p2

…,┐pn)A(┐p1，

┐p2

…,┐pn)┐

A*(p1，

p2

…,pn)

證明思路：利用德摩根定律

P∨Q┐（┐P∧┐Q）

A

┐A*

推廣到p1，

p2

…,pn

當(dāng)前34頁(yè)，總共45頁(yè)。定理1-7.2設(shè)公式A和B中僅含命題變?cè)猵1,…,pn，如果AB，則A*B*。當(dāng)前35頁(yè)，總共45頁(yè)。

文字(letters)：指命題常元、變?cè)八鼈兊姆穸ǎ罢哂址Q正文字，后者則稱負(fù)文字。析取子句(disjunctiveclauses)：指文字或若干文字的析取。

合取子句(conjunctiveclauses)：指文字或若干文字的合取?；パa(bǔ)文字對(duì)(complementalpairsofletters)：指形如L，┐L（L為文字）的一對(duì)字符。當(dāng)前36頁(yè)，總共45頁(yè)。定義1-7.2命題公式A‘稱為公式A的合取范式（conjunctivenormalform）如果

（1）A'

A

（2）A‘為一析取子句或若干析取子句的合取。

A‘形如：A1∧A2∧…∧An(n1)定義1-7.3命題公式A‘稱為公式A的析取范式（disjunctivenormalform），如果

（1）A'

A

（2）A‘為一合取子句或若干合取子句的析取。

A‘形如：A1∨A2∨…∨An(n1)當(dāng)前37頁(yè)，總共45頁(yè)。求一個(gè)命題公式的合取范式或析取范式的步驟：.將公式中的聯(lián)結(jié)詞化歸成僅含∨、∧、┐；.利用德.摩根定律將否定符號(hào)┐直接內(nèi)移到各個(gè)命題變?cè)埃?利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。見P-32頁(yè)例題5

定義1-7.4n個(gè)命題變?cè)暮先∈?，稱作布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，但兩者必須出現(xiàn)且僅出現(xiàn)一次。

一般來說，n個(gè)命題變?cè)灿?n個(gè)小項(xiàng)。

P-32頁(yè)表7-7.1當(dāng)前38頁(yè)，總共45頁(yè)。根據(jù)定義可知，沒有兩個(gè)小項(xiàng)是等價(jià)的，且每個(gè)小項(xiàng)都只對(duì)應(yīng)P和Q的一組真值指派，使得該小項(xiàng)的真值為T。以上結(jié)論可推廣到三個(gè)以上的變?cè)闆r，并且由此可以作出一種編碼，使n個(gè)變?cè)男№?xiàng)可以很快地寫出來。見P=33頁(yè)表1-7.3。小項(xiàng)有如下性質(zhì)：.每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為T，在其余2n-1種真值指派情況下均為F。.任意兩個(gè)不同小項(xiàng)的合取式永假。

.全體小項(xiàng)的析取式永為真。

2n-1mi=m0∨m1

∨…∨m

2n-1

T

i=0當(dāng)前39頁(yè)，總共45頁(yè)。

定義1-7.5

對(duì)于給定的命題公式A，如果有一個(gè)等價(jià)公式A’，它僅由小項(xiàng)的析取所組成，則稱A’為A的主析取范式（majordisjunctivenormalform）。

一個(gè)公式主析取范式可以構(gòu)成真值表的方法寫出。

定理1-7.3

在真值表中，一個(gè)公式的真值為T的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為次公式的主析取范式。利用等價(jià)公式推演主析取范式的步驟：.化歸為析取范式。.除去析取范式中所有永假的析取式。

.將析取式中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變?cè)喜ⅰ?對(duì)合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)刺砑樱≒∨┐P）式，然后，應(yīng)用分配律展開公式，再經(jīng)過整理。當(dāng)前40頁(yè)，總共45頁(yè)。定義1-7.6n個(gè)命題變?cè)奈鋈∈?，稱作布爾析取或大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，但兩者必須出現(xiàn)且僅出現(xiàn)一次。

一般來說，n個(gè)命題變?cè)灿?n個(gè)大項(xiàng)。

P-36頁(yè)大項(xiàng)的例子。

大項(xiàng)有如下性質(zhì)：.每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為F，在其余2n-1種真值指派情況下均為T。.任意兩個(gè)不同大項(xiàng)的析取式永真。

.全體大項(xiàng)的合取式永為假。

2n-1Mi