第一篇數理邏輯第1頁，共47頁，2023年，2月20日，星期一邏輯學（logic

）

是一門研究思維形式及思維規律的科學。數理邏輯（mathematicallogic)

是用數學的方法來研究人類推理過程的一門數學學科。數理邏輯又稱符號邏輯、現代邏輯。

其顯著特征是符號化和形式化，即把邏輯所涉及的“概念、判斷、推理”用符號來表示，用公理體系來刻劃,并基于符號串形式的演算來描述推理過程的一般規律。

第2頁，共47頁，2023年，2月20日，星期一

第一章

命題邏輯第3頁，共47頁，2023年，2月20日，星期一

1-1命題及其表示法1-2聯結詞1-3命題公式與翻譯1-4真值表與等價公式第一章

命題邏輯1-5重言式與蘊涵式1-6其他聯結詞1-7對偶與范式1-8推理理論第4頁，共47頁，2023年，2月20日，星期一第一章命題演算及其形式系統

1-1命題及其表示法

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

當判斷正確或符合客觀實際時，稱該命題真（True），用“T”或“1”表示；否則稱該命題假（False），用“F”或“0”表示。要點：確定的對象

作出判斷

陳述句（見P-2的句子）第5頁，共47頁，2023年，2月20日，星期一

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

把由原子命題和邏輯聯結詞共同組成的命題稱為復合命題（compositivepropositionsorcompoundstatements）（自然語言中的復句，P-2的(9)、(10)）。第6頁，共47頁，2023年，2月20日，星期一命題的符號化（標示符）：可以用以下兩種形式將命題符號化：.用（帶下標的）大寫字母；例如：P：今天下雨。.用數字。例如：[12]：今天下雨。上例中的“P”和“[12]”稱為命題標示符。命題常元（propositionconstants）我們把表示具體命題及表示常命題的p，q，r，s等與f，t統稱為命題常元。第7頁，共47頁，2023年，2月20日，星期一命題變元（propositionvariable）是以“真、假”或“1，0”為取值范圍的變元，它未指出符號所表示的具體命題，可以代表任意命題。指派

當命題變元用一個特定命題取代時，該命題變元才能有確定的真值，從而成為一個命題。稱對命題變元進行指派第8頁，共47頁，2023年，2月20日，星期一

對任意給定的命題變元p1,…,pn的一種取值狀況，稱為指派或賦值（assignments）

，用字母，等表示

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

(A)=0。第9頁，共47頁，2023年，2月20日，星期一1-2聯結詞否定詞“并非”合取詞“并且”析取詞“或”條件詞“如果……，那么……”

雙條件詞“當且僅當”第10頁，共47頁，2023年，2月20日，星期一(1)否定（negation）

定義1-2.1設P為一命題，P的否定是一個新命題，記作“┐P”。若P為T，┐P為F；若P為F，┐P為T。聯結詞“

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

p

┐p

F（0）

T（1）

T（1）

F（0）表1-2.1

否定詞“┐”的意義

“見假為真，見真為假”┐p讀作“并非p”或“非p”。第11頁，共47頁，2023年，2月20日，星期一（2）合取（

conjunction）定義1-2.2兩個命題P和Q的合取是一個復合命題，記作P∧Q。當且僅當P、Q同時為T時，P∧Q為T，其他情況下，P∧Q的真值都是F。合取聯結詞

“∧”表示自然語言中的“并且”（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”

見假為假，全真為真。第12頁，共47頁，2023年，2月20日，星期一（3）析取詞（disjunction）定義1-2.3兩個命題P和Q的析取是一個復合命題，記作P∨

Q。當且僅當P、Q同時為F時，P∨

Q為F，其他情況下，P∨

Q的真值都是T。析取聯結詞

“∨”表示自然語言中的“

或”（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”。第13頁，共47頁，2023年，2月20日，星期一（4）條件詞（implication)

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

Q。當且僅當P的真值為T，Q的真值為F時，P→

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

Q的真值都是T。條件聯結詞

“→”表示自然語言中的

“如果…，那么…”（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稱為條件后件

前真后假為假，其他為真。第14頁，共47頁，2023年，2月20日，星期一（5）雙條件(two-way-implication)

定義1-2.5給定兩個命題P和Q，其復合命題P

Q稱作雙條件命題。當P和Q的真值相同時，P

Q的真值為T，否則，P

Q的真值都是F。雙條件聯結詞

“”表示自然語言中的“當且僅當”（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當且僅當q”。

相同為真，相異為假。第15頁，共47頁，2023年，2月20日，星期一定義1-3.1

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

（1）單個命題常元或命題變元是命題公式，也稱為原子公式或原子。（2）如果A是命題公式，那么┐A也是命題公式。（3）如果A，B是命題公式，那么（A∧B），（A∨B），（A→B），（AB）也是命題公式。

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

Wff的正例和反例見P-10頁。1-3命題公式與翻譯第16頁，共47頁，2023年，2月20日，星期一聯結詞的優先級

命題公式外層的括號可以省略；聯結詞的優先級：┐、∧、∨、→、。

利用加括號的方法可以提高優先級。范例：如下的Wff

：

P∧Q→R等價于Wff

：（（P∧Q）→R）等價于Wff

：（P∧Q）→R不等價于Wff

：P∧（Q→R）第17頁，共47頁，2023年，2月20日，星期一自然語言的語句用Wff

形式化主要是以下幾個方面：

①

要準確確定原子命題，并將其形式化。

②

要選用恰當的聯結詞，尤其要善于識別自然語言中的聯結詞（有時它們被省略），否定詞的位置要放準確。

③

必要時可以進行改述，即改變原來的敘述方式，但要保證表達意思一致。④

需要的括號不能省略，而可以省略的括號，在需要提高公式可讀性時亦可不省略。

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

形式化的例子見P-10頁。第18頁，共47頁，2023年，2月20日，星期一1-4真值表與等價公式定義1-4.1（真值表）在命題公式Wff中，對于公式中分量一切可能的指派組合,公式A的取值可能用下表來描述，這個表稱為真指表（truthtable）。真值表的例子見P-13頁表1-4.1

、表1-4.2

、表1-4.3和P-14頁表1-4.4、表1-4.5

、表1-4.6

。定義1-4.2（

等價公式）給定兩個命題公式A和B，設P1，P2，…，Pn為所有出現于A和B中的原子變元，若給P1，P2，…，Pn任一組真值指派，A和B的真值都相同，則稱A和B是等價的或邏輯相等。記作AB

等價證明方法1：可以用真值表驗證兩個Wff是否等價，見P-13的例題5“真值表法”。第19頁，共47頁，2023年，2月20日，星期一

常用的等價等值式

E1

┐┐AA雙重否定律

E2A∨AA冪等律

E3A∧AA冪等律

E4A∨BB∨A交換律

E5A∧BB∧A交換律

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

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

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吸收律第20頁，共47頁，2023年，2月20日，星期一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驗證吸收率1律0律第21頁，共47頁，2023年，2月20日，星期一

定義1-4.3

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

定理1-4.1（替換原理RuleofReplacement，簡記為RR）如果X是WffA的子公式，若XY，如果將A中的X用Y來置換，所得到的新公式B與公式A等價，即AB。等價證明方法2：證明思路：“討論指派法”等價證明方法3：見P-16的例題7“等價代換法”。第22頁，共47頁，2023年，2月20日，星期一定義1-5.1對命題公式A，如果對A中命題變元的一切指派均弄真A，則A稱為重言式（tautology），又稱永真式.

如果至少有一個指派弄真A，則A稱為可滿足式（satisfactableformulaorcontingency）。定義1-5.2如果對A中命題變元的一切指派均弄假A，則稱A為不可滿足式或矛盾式（contradictionorabsurdity）或永假式。1-5重言式與蘊涵式第23頁，共47頁，2023年，2月20日，星期一

定理1-5.1

任何兩個重言式的合取或析取，仍然是一個重言式。證明思路：“討論指派法”A為T，B為T，A與B析取（或合取）仍為T，定理1-5.2

一個重言式，對同一分量都用任何Wff置換，其結果仍為一重言式。證明思路：“討論指派法”真值與分量的指派無關，置換后與仍為T。見P-20的例題1

定理1-5.3

設A、B是兩個Wff，一個重言式，AB當且僅當AB為一重言式。關于“當且僅當”的證明思路：雙向證明法，從“AB”出發推出“AB為一重言式”；再從“AB為一重言式”出發推出“AB”。第24頁，共47頁，2023年，2月20日，星期一定義1-4.2‘（

等價公式的另一種定義）當命題公式AB為重言式時，稱A邏輯等價于B，記為AB，它又稱為邏輯等價式（logicallyequivalentorequivalent）。定義1-5.3當命題公式A→B為重言式時，稱A邏輯蘊涵B，記為AB，它又稱為邏輯蘊涵式(logically

implication)。

常用的邏輯蘊涵式見p-21頁表1-5.2第25頁，共47頁，2023年，2月20日，星期一定理1-5.4設P、Q為任意兩個命題公式，PQ的充分必要條件是PQ且QP

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

本定理的條件是“PQ且QP

”

如果能從條件“PQ且QP

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

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

再證充分性：XXXXXX第26頁，共47頁，2023年，2月20日，星期一關于等價式和蘊涵式的性質：

（1）AB當且僅當AB

（2）AB當且僅當A→B

（3）若AB，則BA等價對稱性（4）若AB，BC，則AC等價傳遞性（5）若AB，則┐B┐A蘊涵逆否性（6）若AB，BC，則AC蘊涵傳遞性（7）若AB，AA‘，BB’，則A‘B’

蘊涵等價代換

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

（9）若AB，AC，則AB∧C第27頁，共47頁，2023年，2月20日，星期一

設A為永真式，p為A中命題變元，A(B/p)表示將A中p的所有出現全部代換為公式B后所得的命題公式（稱為A的一個代入實例），那么A(B/p)亦為永真式。◆代入原理（RuleofSubstitution），簡記為RS第28頁，共47頁，2023年，2月20日，星期一1-6其它聯結詞

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）不可兼析取（異或）定義1-6.1兩個命題公式P和Q的不可兼析取是一個新命題公式，記作P∨

Q。當且僅當P、Q真值不同時，P∨

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

第29頁，共47頁，2023年，2月20日，星期一異或聯結詞的性質：

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

）（P∧┐

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

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

）F，F∨PP，T∨P

┐P

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

P∨QR，則P∨RQ

，Q∨RP，且P∨Q∨R為一矛盾式。證明思路利用性質（6）。第30頁，共47頁，2023年，2月20日，星期一表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設P和Q是兩個命題公式，P和Q的條件否定是一個新命題公式，記作P

Q。當且僅當P的真值為T，Q的真值為F時，P

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

P

Q┐（P→

Q）第31頁，共47頁，2023年，2月20日，星期一（3）與非定義1-6.3設P和Q是兩個命題公式，P和Q的與非是一個新命題公式，記作P

Q。當且僅當P和Q的真值都為T時，P

Q為F，其他情況下P

Q的真值都是T。根據此定義，可知

P

Q┐（P∧Q）P

Q的3個性質見P-26頁。

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與非詞“”的意義第32頁，共47頁，2023年，2月20日，星期一（4）或非定義1-6.4設P和Q是兩個命題公式，P和Q的或非是一個新命題公式，記作P

Q。當且僅當P和Q的真值都為F時，P

Q為T，其他情況下P

Q的真值都是F。根據此定義，可知

P

Q┐（P∨

Q）P

Q的3個性質見P-26頁。聯結詞小結見P-27頁。表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全假為真見真為假。第33頁，共47頁，2023年，2月20日，星期一1-7對偶與范式定義1-7.1設給定的命題公式A僅含聯結詞

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

也為A*的對偶式。見P-29頁例題1

定理1-7.1設公式A和A*中僅含命題變元p1,…,pn，及聯結詞┐，∧，∨；則┐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

第34頁，共47頁，2023年，2月20日，星期一定理1-7.2設公式A和B中僅含命題變元p1,…,pn，如果AB，則A*B*。第35頁，共47頁，2023年，2月20日，星期一

文字(letters)：指命題常元、變元及它們的否定，前者又稱正文字，后者則稱負文字。析取子句(disjunctiveclauses)：指文字或若干文字的析取。

合取子句(conjunctiveclauses)：指文字或若干文字的合取。互補文字對(complementalpairsofletters)：指形如L，┐L（L為文字）的一對字符。第36頁，共47頁，2023年，2月20日，星期一定義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)第37頁，共47頁，2023年，2月20日，星期一求一個命題公式的合取范式或析取范式的步驟：.將公式中的聯結詞化歸成僅含∨、∧、┐；.利用德.摩根定律將否定符號┐直接內移到各個命題變元之前；.利用分配律、結合律將公式歸約為合取范式或析取范式。見P-32頁例題5

定義1-7.4n個命題變元的合取式，稱作布爾合取或小項，其中每個變元與它的否定不能同時出現，但兩者必須出現且僅出現一次。

一般來說，n個命題變元共有2n個小項。

P-32頁表7-7.1第38頁，共47頁，2023年，2月20日，星期一根據定義可知，沒有兩個小項是等價的，且每個小項都只對應P和Q的一組真值指派，使得該小項的真值為T。以上結論可推廣到三個以上的變元情況，并且由此可以作出一種編碼，使n個變元的小項可以很快地寫出來。見P=33頁表1-7.3。小項有如下性質：.每一個小項當其真值指派與編碼相同時，其真值為T，在其余2n-1種真值指派情況下均為F。.任意兩個不同小項的合取式永假。

.全體小項的析取式永為真。

2n-1mi=m0∨m1

∨…∨m

2n-1

T

i=0第39頁，共47頁，2023年，2月20日，星期一

定義1-7.5

對于給定的命題公式A，如果有一個等價公式A’，它僅由小項的析取所組成，則稱A’為A的主析取范式（majordisjunctivenormalform）。

一個公式主析取范式可以構成真值表的方法寫出。

定理1-7.3

在真值表中，一個公式的真值為T的指派所對應的小項的析取，即為次公式的主析取范式。利用等價公式推演主析取范式的步驟：.化歸為析取范式。.除去析取范式中所有永假的析取式。

.將析取式中重復出現的合取項和相同的變元合并。.對合取項補入沒有出現的命題變元，即添加（P∨┐P）式，然后，應用分配律展開公式，再經過整理。第40頁，共47頁，2023年，2月20日，星期一定義1-7.6n個命題變元的析取式，稱作布爾析取或大項，其中每個變元與它的否定不能同時出現，但兩者必須出現且僅出現一次。

一般來說，n個命題變元共有2n個大項。

P-36頁大項的例子。

大項有如下性質：.每一個大項當其真值指派與編碼相同時，其真值為F，在其余2n-1種真值指派情況下均為T。.任意兩個不同大項的析取式永真。

.全體大項的合取式永為假。

2n-1Mi=M0∧M1

∧…∧M

2n-1

F

i=0第41頁，共47頁，2023年，2月20日，星期一定義1-7.7

對于給定的命題公式A，如果有一個等價公式A’，它僅由大項的合取所組成，則稱A’為A的主合取范式（majorconjunctivenormalform）。

一個公式主合取范式可以構成真值表的方法寫出。定理1-7.4

在真值表中，一個公式的真值為F的指派所對應的大項的合取，即為次公式的主合取范式。利用等價公式推演主合取范式的步驟：.化歸為合取范式。.除去合取范式中所有永真的合取項。

.將合取式中重復出現的析取項和相同的變元合并。.對析取項補入沒有出現的命題變元，即添加（P∧┐P）式，然后，應用分配律展開公式，再經過整理。第42頁，共47頁，2023年，2月20日，星期一1-8推理理論定義1-8.1

設A和C是兩個命題公式，當且僅當A→C為一重言式，即AC，稱C是A的有效結論。或C可由A邏輯推出。序列H1,H2,…,Hn和C是命題公式，當且僅當H1∧H2∧…∧Hn

C稱C是一組前提H1,H2,…,Hn的有效結論。或C可由H1,H2,…,Hn邏輯推出。判別有效結論的過程就是論證過程，論證方法有“真值表法”、“直接證明法”和“間接證明法”。（1）真值表法第43頁，共47頁，2023年，2月20日，星期一

（1）真值表法設P1,P2,…,Pn是出現于前提H1,H2,…,Hm和結論C中的全部命題變元，假定對P1,P2,…,P