關于數理邏輯的公理化理論第一頁，共二十頁，2022年，8月28日第十二章數理邏輯的公理化理論推理部分:系統中的公理,基本規則以及給出的系統中證明與定理的概念公理：按學科要求給出推理中最基本的事實基本規則：一種動態推理公式,分原始規則與導出規則證明:是一種由公理及推理規則按一定語法規則所進行的動態過程,并產生一個公式串.定理:由公理及推理規則按證明過程所得的結果第二頁，共二十頁，2022年，8月28日12.1公理化理論的基本思想1)系統的不矛盾性系統的不矛盾性是對公理系統的最基本要求2)系統的完備性相對完備性:一個為某學科建立的公理系統,該學科中的所有定理和規則均能由系統推出絕對完備性:一個公理系統中如果將任一個非定理的公式作為公理加入系統后,所得到的系統均為矛盾的系統一個系統最好是完備的或相對完備的,但允許不完備3)系統的獨立性系統中的每條公理均不能由其他公理推出一個系統可以是不獨立的第三頁，共二十頁，2022年，8月28日12.2.1命題邏輯的公理化理論命題邏輯永真公式的公理系統1.系統的組成部分

1)基本符號命題:P,Q,R,…;聯結詞:?,∧,∨,→,?括號:(,) 2)公式命題是公式如P,Q是公式,則(P∧Q),(P∨Q),(P→Q),(P?Q)是公式公式由且僅由有限次使用(1)(2)而得第四頁，共二十頁，2022年，8月28日12.2.1命題邏輯的公理化理論2.系統的推理部分1)公理 如P,Q,R為公式,則有下述的公理: (1)P→P (2)(P→(Q→R))→(Q→(P→R)) (3)(P→Q)→((Q→R)→(P→R)) (4)(P→(P→Q))→(P→Q) (5)(P?Q)→(P→Q) (6)(P?Q)→(Q→P) (7)(P→Q)→((Q→P)→(P?Q))第五頁，共二十頁，2022年，8月28日12.2.1命題邏輯的公理化理論 (8)P∧Q→Q (9)P∧Q→P (10)P→(Q→P∧Q) (11)P→P∨Q (12)Q→P∨Q (13)(Q→P)→((R→P)→(Q∨R→P)) (14)(P→?Q)→(Q→?P) (15)??P→P第六頁，共二十頁，2022年，8月28日12.2.1命題邏輯的公理化理論2)推理過程 分離規則:P→Q,P├Q3)證明與定理 證明給出了公理系統中定理生成的過程,它是一個公式序列:P1,P2,…,Pn,其中每個Pi(i=1,2,…,n)必須滿足下列的條件之一. (1)Pi是公理

(2)Pi是由Pk,Pr(k,r<i)施行分離規則而得 最后Pn=Q即為定理.

此公理系統是不矛盾,完備的(相對完備與絕對完備),但它不是獨立.第七頁，共二十頁，2022年，8月28日12.2.1命題邏輯的公理化理論例12.1試證P∨Q→Q∨P證明: (1)Q→Q∨P 公(12) (2)P→Q∨P 公(11) (3)(P→Q∨P)→((Q→Q∨P)→(P∨Q→Q∨P))

公(13) (4)((Q→Q∨P)→(P∨Q→Q∨P)) 分(3),(2) (5)P∨Q→Q∨P 分(4),(1)

證明的每一步后面都附有說明叫證明根據.第八頁，共二十頁，2022年，8月28日12.2.1命題邏輯的公理化理論只要公理系統中有蘊含式為公理,則可必可同時得到一個推理規則,由這種方法所推得的規則叫導出規則.利用導出規則可以從前面15條公理得到15條導出規則:

規則1 P├P

規則2 P→(Q→R)├Q→(P→R)

規則3 P→Q,Q→R├P→R

規則4 P→(P→Q)├P→Q

規則5 P?Q├P→Q

規則6 P?Q├Q→P第九頁，共二十頁，2022年，8月28日12.2.1命題邏輯的公理化理論

規則7 P→Q,Q→P├P?Q

規則8 P∧Q├Q

規則9 P∧Q├P

規則10 P,Q├P∧Q

規則11 P├P∨Q

規則12 Q├P∨Q

規則13 Q→P,R→P├Q∨R→P

規則14 P→?Q├Q→?P

規則15 ??P├P第十頁，共二十頁，2022年，8月28日12.2.1命題邏輯的公理化理論定理12.1推理定理 設有A1,A2,…,An├B,則必有

A1,A2,…,An-1├An→B推論 設有A1,A2,…,An├B,則必有 ├A1→(A2→(…(An→B))…)此定理說明,為證明一個帶蘊含的公式,只要證明它的最后一個后件即成,而其所有前件(稱為假設前提)均可作為已知條件(作為定理)使用,這種方法叫做假設推理方法.第十一頁，共二十頁，2022年，8月28日12.2.1命題邏輯的公理化理論假設推理方法的證明過程:

證明過程是一個公式序列:P1,P2,…,Pn,其中每個Pi(i=1,2,…,n)必須滿足下列的條件之一. (1)Pi是假設前提

(2)Pi是公理

(3)Pi是由Pk,Pr(k,r<i)施行分離規則而得 最后Pn=Q即為定理.第十二頁，共二十頁，2022年，8月28日12.2.1命題邏輯的公理化理論例12.5:試證(P→Q)→((P→R)→(P→Q∧R))證明:

即證:P→Q,P→R,P├Q∧R (1)P→Q 假設前提

(2)P→R 假設前提

(3)P 假設前提

(4)Q 分(1)(3) (5)R 分(2)(3) (6)Q∧R 規則10第十三頁，共二十頁，2022年，8月28日12.2.2謂詞邏輯的公理化理論謂詞邏輯永真公式的公理系統推理部分1)公理

(16)?xP(x)→P(x) (17)P(x)→?P(x)2)推理規則

(1)分離規則:P→Q,P├Q (2)全稱規則:Q→P(x)├Q→?xP(x) (3)存在規則:P(x)→Q├?xP(x)→Q第十四頁，共二十頁，2022年，8月28日12.2.2謂詞邏輯的公理化理論3)證明與定理 證明是一個公式序列:P1,P2,…,Pn,其中每個Pi(i=1,2,…,n)必須滿足下列的條件之一. (1) Pi是公理

(2) Pi是由Pk,Pr(k,r<i)施行分離規則而得

(3) Pi是由Pk(k<i)施行全稱規則而得

(4) Pi是由Pk(k<i)施行全稱規則而得 最后Pn=Q即為定理.第十五頁，共二十頁，2022年，8月28日12.2.2謂詞邏輯的公理化理論4)全稱規則另外的形式

P(x)├?xP(x) (全稱推廣規則:UG)

規則16?xP(x)├P(x) (全稱指定規則:US)

規則17P(x)├?P(x) (存在推廣規則:EG)定理12.2謂詞邏輯推理定理 設有R1,R2,…,Rn├Q,且在推理過程中對Ri(i=1,2,…,n)不作代入,各Ri至少被使用一次且在施行全稱規則、存在規則時絕不對各Ri中的自由變元進行,則必有

R1,R2,…,Rn-1├Rn→Q第十六頁，共二十頁，2022年，8月28日12.2.2謂詞邏輯的公理化理論推論 設有R1,R2,…,Rn├Q,且在推理過程中對Ri(i=1,2,…,n)不作代入,各Ri至少被使用一次且在施行全稱規則、存在規則時絕不對各Ri中的自由變元進行,則必有 ├R1→(R2→(…(Rn→Q))…)規則18

?xP(x)├P(e)(存在指定規則:ES)此規則中e叫額外變元,它是一種額外假設的自由變元,它的變化范圍是使對?xP(x)成立的x.第十七頁，共二十頁，2022年，8月28日12.2.2謂詞邏輯的公理化理論可充分應用UG,US,EG,ES四條規則,通過US,ES將公式中的量詞全部除去,從而得到一個命題邏輯公式，然后用命題邏輯方法推理,在最后得到結論前利用UG,EG重新加入量詞，恢復成謂詞邏輯公式.使用UG時需遵守:1)對假設前提中所出現的自由變元不能使用此規則2)對額外變元不能使用此規則3)一公式中含有額外變元則對此公式中的自由變元亦不能使用此規則.使用ES需遵守:不同額外變元需用不同符號表示,而且不能互相代入.第十八頁，共二十頁，2022年，8月28日12.2.2謂詞邏輯的公理化理論例12.7:試證?x(P(x)→Q(x))→(?xP(x)→?xQ(x))證明: