第十二章 數(shù)理邏輯的公理化理論

第十二章數(shù)理邏輯的公理化理論第1頁(yè)，共19頁(yè)，2023年，2月20日，星期三第十二章數(shù)理邏輯的公理化理論推理部分:系統(tǒng)中的公理,基本規(guī)則以及給出的系統(tǒng)中證明與定理的概念公理：按學(xué)科要求給出推理中最基本的事實(shí)基本規(guī)則：一種動(dòng)態(tài)推理公式,分原始規(guī)則與導(dǎo)出規(guī)則證明:是一種由公理及推理規(guī)則按一定語(yǔ)法規(guī)則所進(jìn)行的動(dòng)態(tài)過(guò)程,并產(chǎn)生一個(gè)公式串.定理:由公理及推理規(guī)則按證明過(guò)程所得的結(jié)果第2頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.1公理化理論的基本思想1)系統(tǒng)的不矛盾性系統(tǒng)的不矛盾性是對(duì)公理系統(tǒng)的最基本要求2)系統(tǒng)的完備性相對(duì)完備性:一個(gè)為某學(xué)科建立的公理系統(tǒng),該學(xué)科中的所有定理和規(guī)則均能由系統(tǒng)推出絕對(duì)完備性:一個(gè)公理系統(tǒng)中如果將任一個(gè)非定理的公式作為公理加入系統(tǒng)后,所得到的系統(tǒng)均為矛盾的系統(tǒng)一個(gè)系統(tǒng)最好是完備的或相對(duì)完備的,但允許不完備3)系統(tǒng)的獨(dú)立性系統(tǒng)中的每條公理均不能由其他公理推出一個(gè)系統(tǒng)可以是不獨(dú)立的第3頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.2.1命題邏輯的公理化理論命題邏輯永真公式的公理系統(tǒng)1.系統(tǒng)的組成部分 1)基本符號(hào)命題:P,Q,R,…;聯(lián)結(jié)詞:?,∧,∨,→,?括號(hào):(,) 2)公式命題是公式如P,Q是公式,則(P∧Q),(P∨Q),(P→Q),(P?Q)是公式公式由且僅由有限次使用(1)(2)而得第4頁(yè)，共19頁(yè)，2023年，2月20日，星期三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頁(yè)，共19頁(yè)，2023年，2月20日，星期三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頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.2.1命題邏輯的公理化理論2)推理過(guò)程 分離規(guī)則:P→Q,P├Q3)證明與定理 證明給出了公理系統(tǒng)中定理生成的過(guò)程,它是一個(gè)公式序列:P1,P2,…,Pn,其中每個(gè)Pi(i=1,2,…,n)必須滿足下列的條件之一. (1)Pi是公理 (2)Pi是由Pk,Pr(k,r<i)施行分離規(guī)則而得 最后Pn=Q即為定理. 此公理系統(tǒng)是不矛盾,完備的(相對(duì)完備與絕對(duì)完備),但它不是獨(dú)立.第7頁(yè)，共19頁(yè)，2023年，2月20日，星期三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) 證明的每一步后面都附有說(shuō)明叫證明根據(jù).第8頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.2.1命題邏輯的公理化理論只要公理系統(tǒng)中有蘊(yùn)含式為公理,則可必可同時(shí)得到一個(gè)推理規(guī)則,由這種方法所推得的規(guī)則叫導(dǎo)出規(guī)則.利用導(dǎo)出規(guī)則可以從前面15條公理得到15條導(dǎo)出規(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頁(yè)，共19頁(yè)，2023年，2月20日，星期三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頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.2.1命題邏輯的公理化理論定理12.1推理定理 設(shè)有A1,A2,…,An├B,則必有 A1,A2,…,An-1├An→B推論 設(shè)有A1,A2,…,An├B,則必有 ├A1→(A2→(…(An→B))…)此定理說(shuō)明,為證明一個(gè)帶蘊(yùn)含的公式,只要證明它的最后一個(gè)后件即成,而其所有前件(稱為假設(shè)前提)均可作為已知條件(作為定理)使用,這種方法叫做假設(shè)推理方法.第11頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.2.1命題邏輯的公理化理論假設(shè)推理方法的證明過(guò)程: 證明過(guò)程是一個(gè)公式序列:P1,P2,…,Pn,其中每個(gè)Pi(i=1,2,…,n)必須滿足下列的條件之一. (1)Pi是假設(shè)前提 (2)Pi是公理 (3)Pi是由Pk,Pr(k,r<i)施行分離規(guī)則而得 最后Pn=Q即為定理.第12頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.2.1命題邏輯的公理化理論例12.5:試證(P→Q)→((P→R)→(P→Q∧R))證明: 即證:P→Q,P→R,P├Q∧R (1)P→Q 假設(shè)前提 (2)P→R 假設(shè)前提 (3)P 假設(shè)前提 (4)Q 分(1)(3) (5)R 分(2)(3) (6)Q∧R 規(guī)則10第13頁(yè)，共19頁(yè)，2023年，2月20日，星期三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頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.2.2謂詞邏輯的公理化理論3)證明與定理 證明是一個(gè)公式序列:P1,P2,…,Pn,其中每個(gè)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頁(yè)，共19頁(yè)，2023年，2月20日，星期三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謂詞邏輯推理定理 設(shè)有R1,R2,…,Rn├Q,且在推理過(guò)程中對(duì)Ri(i=1,2,…,n)不作代入,各Ri至少被使用一次且在施行全稱規(guī)則、存在規(guī)則時(shí)絕不對(duì)各Ri中的自由變?cè)M(jìn)行,則必有 R1,R2,…,Rn-1├Rn→Q第16頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.2.2謂詞邏輯的公理化理論推論 設(shè)有R1,R2,…,Rn├Q,且在推理過(guò)程中對(duì)Ri(i=1,2,…,n)不作代入,各Ri至少被使用一次且在施行全稱規(guī)則、存在規(guī)則時(shí)絕不對(duì)各Ri中的自由變?cè)M(jìn)行,則必有 ├R1→(R2→(…(Rn→Q))…)規(guī)則18

?xP(x)├P(e)(存在指定規(guī)則:ES)此規(guī)則中e叫額外變?cè)?它是一種額外假設(shè)的自由變?cè)?它的變化范圍是使對(duì)?xP(x)成立的x.第17頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.2.2謂詞邏輯的公理化理論可充分應(yīng)用UG,US,EG,ES四條規(guī)則,通過(guò)US,ES將公式中的量詞全部除去,從而得到一個(gè)命題邏輯公式，然后用命題邏輯方法推理,在最后得到結(jié)論前利用UG,EG重新加入量詞，恢復(fù)成謂詞邏輯公式.使用UG時(shí)需遵守:1)對(duì)假設(shè)前提中所出現(xiàn)的自由變?cè)荒苁褂么艘?guī)則2)對(duì)額外變?cè)荒苁褂么艘?guī)則3)一公式中含有額外變?cè)獎(jiǎng)t對(duì)此公式中的自由變?cè)嗖荒苁褂么艘?guī)則.使用ES需遵守:不同額外變?cè)栌貌煌?hào)表示,而且不能互相代入.第18頁(yè)，共19頁(yè)，2023年，2月20日，星期三12.2.2謂詞邏輯的公理化理論例12.7:試證?x(P(x)→Q(x)