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

1、第十二章 數(shù)理邏輯的公理化理論 12.1 公理化理論的基本思想 公理: 學(xué)科領(lǐng)域中最基本的原理與規(guī)則 公理系統(tǒng): 以公理為基礎(chǔ)所建立的基于一定語(yǔ)法規(guī)范的形式系統(tǒng) 公理系統(tǒng)一般由兩部分內(nèi)容組成: 組成部分: 基本符號(hào)：按學(xué)科要求建立 公式：由基本符號(hào)按一定語(yǔ)法規(guī)則組成第十二章 數(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)過程, 并產(chǎn)生一個(gè)公式串. 定理: 由公理及推理規(guī)則按證明過程所得的結(jié)果12.1 公

2、理化理論的基本思想 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ú)立的12.2.1 命題邏輯的公理化理論 命題邏輯永真公式的公理系統(tǒng)1. 系統(tǒng)的組成部分1) 基本符號(hào) 命題: P,Q,R,; 聯(lián)結(jié)詞: , 括號(hào): (,)2) 公式 命題是公式 如P,Q

3、是公式, 則(PQ), (PQ), (PQ), (PQ)是公式 公式由且僅由有限次使用(1)(2)而得12.2.1 命題邏輯的公理化理論2. 系統(tǒng)的推理部分1) 公理如P,Q,R為公式, 則有下述的公理:(1) P P(2) (P(QR) (Q(PR) (3) (PQ) (QR)(PR)(4) (P(PQ) (PQ)(5) (PQ) (PQ)(6) (PQ) (QP)(7) (PQ) (QP)(PQ)12.2.1 命題邏輯的公理化理論(8) PQ Q(9) PQ P(10) P (QPQ)(11) P PQ(12) Q PQ(13) (QP) (RP)(QRP)(14) (PQ) (QP)(1

4、5) P P12.2.1 命題邏輯的公理化理論2) 推理過程分離規(guī)則: PQ, PQ3) 證明與定理證明給出了公理系統(tǒng)中定理生成的過程, 它是一個(gè)公式序列: P1,P2,Pn, 其中每個(gè)Pi(i=1,2,n)必須滿足下列的條件之一.(1) Pi是公理(2) Pi是由Pk, Pr (k,ri)施行分離規(guī)則而得最后Pn=Q即為定理.此公理系統(tǒng)是不矛盾, 完備的(相對(duì)完備與絕對(duì)完備),但它不是獨(dú)立.12.2.1 命題邏輯的公理化理論 例12.1 試證PQ QP 證明: (1) Q QP 公(12)(2) P QP 公(11)(3) (PQP) (QQP)(PQQP)公(13)(4) (QQP)(PQ

5、QP)分(3),(2)(5) PQ QP 分(4),(1)證明的每一步后面都附有說明叫證明根據(jù).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(QR) Q(PR) 規(guī)則3 PQ, QR PR規(guī)則4 P(PQ) PQ規(guī)則5 PQ PQ規(guī)則6PQ QP12.2.1 命題邏輯的公理化理論規(guī)則7 PQ, QP PQ規(guī)則8 PQ Q規(guī)則9 PQ P規(guī)則10 P, Q PQ規(guī)則11 P PQ規(guī)則12 Q PQ規(guī)則13 QP, RP QRP規(guī)則

6、14 PQ QP規(guī)則15 P P12.2.1 命題邏輯的公理化理論 定理12.1 推理定理設(shè)有A1,A2,An B, 則必有 A1,A2,An-1 An B 推論設(shè)有A1,A2,An B, 則必有 A1(A2(AnB) 此定理說明, 為證明一個(gè)帶蘊(yùn)含的公式, 只要證明它的最后一個(gè)后件即成, 而其所有前件(稱為假設(shè)前提)均可作為已知條件(作為定理)使用, 這種方法叫做假設(shè)推理方法.12.2.1 命題邏輯的公理化理論 假設(shè)推理方法的證明過程:證明過程是一個(gè)公式序列: P1,P2,Pn, 其中每個(gè)Pi(i=1,2,n)必須滿足下列的條件之一.(1) Pi是假設(shè)前提(2) Pi是公理(3) Pi是由P

7、k, Pr (k,ri)施行分離規(guī)則而得最后Pn=Q即為定理.12.2.1 命題邏輯的公理化理論 例12.5: 試證 (PQ)(PR)(PQR) 證明:即證: PQ, PR, P QR(1) PQ假設(shè)前提(2) PR 假設(shè)前提(3) P假設(shè)前提(4) Q分(1)(3)(5) R分(2)(3)(6) QR規(guī)則1012.2.2 謂詞邏輯的公理化理論 謂詞邏輯永真公式的公理系統(tǒng) 推理部分 1) 公理(16) xP(x) P(x)(17) P(x) P(x) 2) 推理規(guī)則(1) 分離規(guī)則: PQ, P Q(2) 全稱規(guī)則: QP(x) QxP(x)(3) 存在規(guī)則: P(x)Q xP(x)Q 12.

8、2.2 謂詞邏輯的公理化理論 3) 證明與定理證明是一個(gè)公式序列: P1,P2,Pn, 其中每個(gè)Pi(i=1,2,n)必須滿足下列的條件之一.(1) Pi是公理(2) Pi是由Pk, Pr (k,ri)施行分離規(guī)則而得(3) Pi是由Pk (ki)施行全稱規(guī)則而得(4) Pi是由Pk (ki)施行全稱規(guī)則而得最后Pn=Q即為定理.12.2.2 謂詞邏輯的公理化理論 4) 全稱規(guī)則另外的形式P(x) xP(x) (全稱推廣規(guī)則: UG)規(guī)則16 xP(x) P(x) (全稱指定規(guī)則: US)規(guī)則17 P(x) P(x) (存在推廣規(guī)則: EG) 定理12.2 謂詞邏輯推理定理設(shè)有R1,R2,Rn

9、 Q, 且在推理過程中對(duì)Ri(i=1,2,n)不作代入, 各Ri至少被使用一次且在施行全稱規(guī)則、存在規(guī)則時(shí)絕不對(duì)各Ri中的自由變?cè)M(jìn)行, 則必有 R1,R2,Rn-1 Rn Q12.2.2 謂詞邏輯的公理化理論 推論設(shè)有R1, R2,Rn Q,且在推理過程中對(duì)Ri(i=1,2,n)不作代入, 各Ri至少被使用一次且在施行全稱規(guī)則、存在規(guī)則時(shí)絕不對(duì)各Ri中的自由變?cè)M(jìn)行, 則必有 R1(R2(RnQ) 規(guī)則18 xP(x) P(e) (存在指定規(guī)則:ES) 此規(guī)則中e叫額外變?cè)? 它是一種額外假設(shè)的自由變?cè)? 它的變化范圍是使對(duì)xP(x)成立的x. 12.2.2 謂詞邏輯的公理化理論 可充分應(yīng)用UG, US, EG, ES四條規(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)表示, 而且不能互相代入.12.2.2 謂詞邏輯的公理化理論