第六講命題演算系統(tǒng)

第六講命題演算系統(tǒng)第1頁，共24頁，2023年，2月20日，星期一命題演算形式系統(tǒng)Lp命題演算形式系統(tǒng)Lp；命題演算系統(tǒng)的可靠性；命題演算系統(tǒng)的完全性。第2頁，共24頁，2023年，2月20日，星期一命題演算系統(tǒng)Lp

命題演算系統(tǒng)通常記為：P，分為公理演算系統(tǒng)和自然演繹推理系統(tǒng)，它們都是用形式語言構(gòu)造出來的。所謂公理演算系統(tǒng)，指的是由一些基本命題（即公理）和推導規(guī)則以及由此推出的一些命題（即定理）而形成的演繹系統(tǒng)。所謂自然演繹系統(tǒng)，指的是沒有公理只依賴推導規(guī)則推出一些命題（即定理）而形成的演繹系統(tǒng)。第3頁，共24頁，2023年，2月20日，星期一命題演算系統(tǒng)Lp形式化的公理系統(tǒng)又稱為形式系統(tǒng)。一個形式系統(tǒng)主要由形式語言、初始公式、變形規(guī)則以及由它們得到的公式四部分組成。下面具體介紹命題演算系統(tǒng)。第4頁，共24頁，2023年，2月20日，星期一命題演算系統(tǒng)Lp初始符號1、命題變元：p，q，r，……；2、命題聯(lián)接詞：∧，∨，→，，﹁；3、輔助符號：（，）。形成規(guī)則1、任何命題變元是合式公式；2、如果A是合式公式，則（﹁A）是合式公式；3、如果A、B是合式公式，則（A∧B）、（A∨B）、（A→B）、（AB）是合式公式；4、只有按照1、2、3的規(guī)定形成的符號串才是合式公式。第5頁，共24頁，2023年，2月20日，星期一命題演算系統(tǒng)Lp下面給出初始公式（即公理演算系統(tǒng)的公理）和初始規(guī)則：初始公式AP1A→（B→A）AP2（A→（B→C））→（（A→B）→（A→C））AP3（﹁A→B）（（﹁A→﹁B）→A）初始規(guī)則（又叫變形規(guī)則）MP分離規(guī)則若├A→B且├A，則├B。SB代入規(guī)則若├A，則├A（p1/B1，p2/B2，…，pn/Bn）其中，A（p1/B1，p2/B2，…，pn/Bn）表示將A中的命題變元p1，p2，…，pn（如果有的話）處處分別換成B1，B2，…，Bn。這就是代入規(guī)則，運用代入規(guī)則時請注意，一定是處處代入。第6頁，共24頁，2023年，2月20日，星期一命題演算系統(tǒng)Lp一個使用形式語言的形式系統(tǒng)，通過初始公式和初始規(guī)則得到的公式就是這個系統(tǒng)的定理。一個形式系統(tǒng)的任務也就是證明這些定理的成立。下面給出系統(tǒng)中的一些定義。第7頁，共24頁，2023年，2月20日，星期一命題演算系統(tǒng)Lp定義3（證明的定義）

LP中的證明是一個合式公式的有限序列：A1，A2，…An，且滿足以下條件：對每一個Ai（1in）要么是公理，要么是由前面的公式根據(jù)變形規(guī)則得到的。定義4（A證明的定義）如果一個證明A1，A2，…An中的An=A，我們就稱這個證明叫做關于A的證明，也就是A證明。定義5（定理的定義）如果有一個A證明，則稱A是這個系統(tǒng)的定理。記作：├LPA。第8頁，共24頁，2023年，2月20日，星期一定理1├A→A證明：（1）A→（B→A）AP1（2）A→（（A→A）→A）（1）SB（3）（A→（B→C））→（（A→B）→（A→C））AP2（4）A→（（A→A）→A）→（（A→（A→A））→（A→A））（3）SB（5）（A→（A→A））→（A→A）（2）（4）MP（6）A→（A→A）（1）SB（7）A→A(5)(6)MP第9頁，共24頁，2023年，2月20日，星期一命題演算系統(tǒng)Lp定義6（推演的定義）如果A1，A2，…An是一個滿足如下條件的公式序列，則稱它是以Γ為前提的推演。條件：任一Ai（1≤i≤n）是Γ中的元素，或者是公理，或者是由前面的公式根據(jù)變形規(guī)則得到的。定義7從Γ到A的推演：如果A1，A2，…An是Γ以為前提的推演，并且An=A，我們就稱它是從Γ到A的推演，或者說A是從Γ出發(fā)得到的推論，記作：Γ├A。如果Γ={B}，可以記作：B├A；如果Γ={B，C}，可以記作：B，C├A；如果Γ=?，就記作：├A。從?出發(fā)推出A，A就是一個定理。演繹定理的證明見教材。第10頁，共24頁，2023年，2月20日，星期一演繹定理：如果?！葅A}├B，則Γ├A→B。演繹定理的證明需要數(shù)學歸納法，數(shù)學歸納法是證明無窮個命題成立的方法，它由兩部分組成，分別是歸納基礎和歸納步驟。歸納法可以分為兩類：第一類歸納法：有一批編了號碼的命題（1）我們能證明第1號命題是正確的；（2）如果我們還能證明，在第n號命題正確的時候，第n+1號命題也正確，那么這一批命題就都是正確的。第11頁，共24頁，2023年，2月20日，星期一第二類歸納法：有一批編了號碼的命題（1）我們能證明第1號命題是正確的；（2）如果我們還能證明，在k﹤n時命題正確的時候，k=n時命題也正確，那么這一批命題都是正確的。第12頁，共24頁，2023年，2月20日，星期一證明：歸納基礎：令該演繹序列有一個公式B構(gòu)成，Γ為LP中任意合式公式的集合，如果如果{Γ，A}├B，則Γ├A→B。情況1：B是公理（1）B公理（2）B→（A→B）AP1SB（3）A→B（1）（2）MP即Γ├A→B得證。第13頁，共24頁，2023年，2月20日，星期一情況2：B是Γ中的公式，記作：B∈Γ（1）B前提（2）B→（A→B）AP1SB（3）A→B（1）（2）MP即├A→B得證。情況3：B就是A。此時要證├A→A，根據(jù)定理1得證。歸納基礎證畢。第14頁，共24頁，2023年，2月20日，星期一歸納步驟：假設當由Γ和A得出B的演繹的公式數(shù)目小于n時，演繹定義成立，現(xiàn)在證明當由Γ和A得出B的演繹的公式數(shù)目等于n時，演繹定理也成立。分四種情況：情況1：B是公理，同歸納基礎中情況1相同。情況2：B是中的公式，同上。情況3：B就是A，也同上。第15頁，共24頁，2023年，2月20日，星期一情況4：B是由出現(xiàn)在演繹序列中在前的兩個公式，通過分離規(guī)則得到的，此時前面必定有兩個這樣的公式：一個是C，一個是C→B。兩者中的任一必然在LP中由Γ和A為前提推出，把這些公式序列數(shù)目分別設為：k和m，k和m都小于n。根據(jù)歸納假設可得：第16頁，共24頁，2023年，2月20日，星期一Γ├（A→C）和Γ├（A→（C→B））以為Γ前提得出（A→B）的演繹如下：（1）…（k）（A→C）…（m）A→（C→B）（m+1）（A→（C→B））→（（A→C）→（A→B））AP2（m+2）（A→C）→（A→B）（m）（m+1）MP（m+3）A→B（m+2）（k）MP因此，在以上四種情況下，都有Γ├A→B。演繹定義證畢。第17頁，共24頁，2023年，2月20日，星期一命題演算系統(tǒng)的可靠性命題演算系統(tǒng)LP的可靠性古典的一致性系統(tǒng)S是一致的，當且僅當，不存在公式，和都是S-可證的。語法的一致性系統(tǒng)S是一致的，當且僅當，并非任一公式都是S-可證的。語義的一致性系統(tǒng)S是一致的，當且僅當，S的內(nèi)定理都是有效的。語義一致性就是可靠性，因此，通常情況下把系統(tǒng)的一致性和可靠性看作是相同的。第18頁，共24頁，2023年，2月20日，星期一定義8命題演算系統(tǒng)LP中的一個賦值是一個函數(shù)v，v的定義域是系統(tǒng)LP中的合式公式，值域是{1，0}（1表示真，0表示假），對LP中的任意公式A，B，滿足：定義9LP中的公式A是重言式，當且僅當，對每一個賦值v，都有v（A）=1。引理1（MP保真性定理）令A，B是LP中的任意公式，如果A是重言式且A→B是重言式，則B也是重言式。第19頁，共24頁，2023年，2月20日，星期一定理4（可靠性定理）：系統(tǒng)LP中的每一個定理都是重言式。證明：令A是LP中的一個定理，必然存在LP中對A的一個證明，假設該證明是由n個公式A1，A2，…An組成的序列，現(xiàn)在對n進行數(shù)學歸納即可證得可靠性定理。歸納基礎：當n=1時，即A在LP中的證明序列只有一個公式，很顯然，A一定是系統(tǒng)中的一個初始公式，即公理，公理都是重言式。（可用真值表法證明）第20頁，共24頁，2023年，2月20日，星期一歸納步驟：假設LP中的證明序列小于n的所有定理都是重言式，證明LP中的證明序列為n的定理也是重言式?，F(xiàn)在令A的證明序列為n，證明序列中的第n個公式就是A，有兩種情況：情況1：A是公理。情況2：A是由證明序列中在前的兩個公式通過分離規(guī)則得到的，此時必有兩個公式為：B和B→A。又因為它們都是在A前面的公式，因此證明序列必然小于n，根據(jù)歸納假設，B和B→A都是重言式。再根據(jù)引理1，得到A也是重言式?？煽啃远ɡ碜C畢。第21頁，共24頁，2023年，2月20日，星期一定義10

一個系統(tǒng)是一致的，當且僅當，對系統(tǒng)中的任意合式公式A，A和A不能都是該系統(tǒng)的定理。定理5（一致性定理）命題演算系統(tǒng)LP是一致的，即對LP中的任一公式，A和A不能都是命題演算系統(tǒng)LP的定理。定理6LP是一致的，當且僅當，LP中存在一個公式不是它的定理。第22頁，共24頁，2023年，2月20日，星期一命題演算系統(tǒng)的完全性古典的完全性系統(tǒng)S是古典完全的，當且僅當，對于任意A，或者A不可證，或者A不可證。語法的完全