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

1、關(guān)于數(shù)理邏輯的公理化理論第一張，PPT共二十頁，創(chuàng)作于2022年6月第十二章 數(shù)理邏輯的公理化理論推理部分: 系統(tǒng)中的公理, 基本規(guī)則以及給出的系統(tǒng)中證明與定理的概念公理：按學(xué)科要求給出推理中最基本的事實(shí)基本規(guī)則：一種動(dòng)態(tài)推理公式, 分原始規(guī)則與導(dǎo)出規(guī)則證明: 是一種由公理及推理規(guī)則按一定語法規(guī)則所進(jìn)行的動(dòng)態(tài)過程, 并產(chǎn)生一個(gè)公式串.定理: 由公理及推理規(guī)則按證明過程所得的結(jié)果第二張，PPT共二十頁，創(chuàng)作于2022年6月12.1 公理化理論的基本思想1) 系統(tǒng)的不矛盾性系統(tǒng)的不矛盾性是對(duì)公理系統(tǒng)的最基本要求2) 系統(tǒng)的完備性相對(duì)完備性: 一個(gè)為某學(xué)科建立的公理系統(tǒng), 該學(xué)科中的所有定理和規(guī)則均

2、能由系統(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ú)立的第三張，PPT共二十頁，創(chuàng)作于2022年6月12.2.1 命題邏輯的公理化理論命題邏輯永真公式的公理系統(tǒng)1. 系統(tǒng)的組成部分1) 基本符號(hào)命題: P,Q,R,;聯(lián)結(jié)詞: ,括號(hào): (,)2) 公式命題是公式如P,Q是公式, 則(PQ), (PQ), (PQ), (PQ)是公式公式由且僅由有限次使用(1)(2)而得第四張，PPT共二十頁，創(chuàng)作于2022年6月12.

3、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)第五張，PPT共二十頁，創(chuàng)作于2022年6月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)(15) P P第六張，PPT共二十頁，創(chuàng)作于2022年6月12.2

4、.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ú)立.第七張，PPT共二十頁，創(chuàng)作于2022年6月12.2.1 命題邏輯的公理化理論例12.1 試證PQ QP證明: (1) Q QP 公(12)(2) P QP 公(11)(3) (PQP) (QQP)(PQQP)公(13)(4

5、) (QQP)(PQQP)分(3),(2)(5) PQ QP 分(4),(1)證明的每一步后面都附有說明叫證明根據(jù).第八張，PPT共二十頁，創(chuàng)作于2022年6月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 QP第九張，PPT共二十頁，創(chuàng)作于2022年6月12.2.1 命題邏輯的公理化理論規(guī)則7 PQ, QP PQ規(guī)則8 PQ Q規(guī)則9

6、 PQ P規(guī)則10 P, Q PQ規(guī)則11 P PQ規(guī)則12 Q PQ規(guī)則13 QP, RP QRP規(guī)則14 PQ QP規(guī)則15 P P第十張，PPT共二十頁，創(chuàng)作于2022年6月12.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è)推理方法.第十一張，PPT共二十頁，創(chuàng)作于2022年6月12.2.1 命題邏輯的公理化

7、理論假設(shè)推理方法的證明過程:證明過程是一個(gè)公式序列: P1,P2,Pn, 其中每個(gè)Pi(i=1,2,n)必須滿足下列的條件之一.(1) Pi是假設(shè)前提(2) Pi是公理(3) Pi是由Pk, Pr (k,ri)施行分離規(guī)則而得最后Pn=Q即為定理.第十二張，PPT共二十頁，創(chuàng)作于2022年6月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ī)則10第十三張，PPT共二十頁，創(chuàng)作于2022年6月12.2.2

8、謂詞邏輯的公理化理論謂詞邏輯永真公式的公理系統(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 第十四張，PPT共二十頁，創(chuàng)作于2022年6月12.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)

9、施行全稱規(guī)則而得最后Pn=Q即為定理.第十五張，PPT共二十頁，創(chuàng)作于2022年6月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 Q, 且在推理過程中對(duì)Ri(i=1,2,n)不作代入, 各Ri至少被使用一次且在施行全稱規(guī)則、存在規(guī)則時(shí)絕不對(duì)各Ri中的自由變?cè)M(jìn)行, 則必有 R1,R2,Rn-1 Rn Q第十六張，PPT共二十頁，創(chuàng)作于2022年6月12.2.2 謂詞邏輯的公理化

10、理論推論設(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. 第十七張，PPT共二十頁，創(chuàng)作于2022年6月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)表示, 而且不能互相代入.第十八張，PPT共二十頁，創(chuàng)作于2022年6月12.2.2 謂詞邏輯的公理化理論例12.7: 試證 x(P(x)Q(x)(xP(x)xQ(x)證明:只要證