數(shù)理邏輯的公理化理論

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

1)基本符號命題:P,Q,R,…;聯(lián)結(jié)詞:?,∧,∨,→,?括號:(,) 2)公式命題是公式如P,Q是公式,則(P∧Q),(P∨Q),(P→Q),(P?Q)是公式公式由且僅由有限次使用(1)(2)而得第4頁,共20頁，2024年2月25日，星期天12.2.1命題邏輯的公理化理論2.系統(tǒng)的推理部分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))第5頁,共20頁，2024年2月25日，星期天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第6頁,共20頁，2024年2月25日，星期天12.2.1命題邏輯的公理化理論2)推理過程 分離規(guī)則:P→Q,P├Q3)證明與定理 證明給出了公理系統(tǒng)中定理生成的過程,它是一個公式序列:P1,P2,…,Pn,其中每個Pi(i=1,2,…,n)必須滿足下列的條件之一. (1)Pi是公理

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

此公理系統(tǒng)是不矛盾,完備的(相對完備與絕對完備),但它不是獨立.第7頁,共20頁，2024年2月25日，星期天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)

證明的每一步后面都附有說明叫證明根據(jù).第8頁,共20頁，2024年2月25日，星期天12.2.1命題邏輯的公理化理論只要公理系統(tǒng)中有蘊含式為公理,則可必可同時得到一個推理規(guī)則,由這種方法所推得的規(guī)則叫導出規(guī)則.利用導出規(guī)則可以從前面15條公理得到15條導出規(guī)則:

規(guī)則1 P├P

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

規(guī)則3 P→Q,Q→R├P→R

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

規(guī)則5 P?Q├P→Q

規(guī)則6 P?Q├Q→P第9頁,共20頁，2024年2月25日，星期天12.2.1命題邏輯的公理化理論

規(guī)則7 P→Q,Q→P├P?Q

規(guī)則8 P∧Q├Q

規(guī)則9 P∧Q├P

規(guī)則10 P,Q├P∧Q

規(guī)則11 P├P∨Q

規(guī)則12 Q├P∨Q

規(guī)則13 Q→P,R→P├Q∨R→P

規(guī)則14 P→?Q├Q→?P

規(guī)則15 ??P├P第10頁,共20頁，2024年2月25日，星期天12.2.1命題邏輯的公理化理論定理12.1推理定理 設有A1,A2,…,An├B,則必有

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

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

(2)Pi是公理

(3)Pi是由Pk,Pr(k,r<i)施行分離規(guī)則而得 最后Pn=Q即為定理.第12頁,共20頁，2024年2月25日，星期天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 規(guī)則10第13頁,共20頁，2024年2月25日，星期天12.2.2謂詞邏輯的公理化理論謂詞邏輯永真公式的公理系統(tǒng)推理部分1)公理

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

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

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

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

(4) Pi是由Pk(k<i)施行全稱規(guī)則而得 最后Pn=Q即為定理.第15頁,共20頁，2024年2月25日，星期天12.2.2謂詞邏輯的公理化理論4)全稱規(guī)則另外的形式

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

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

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

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

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

只要證明?x(P(x)→Q