命題邏輯的公理系統(tǒng)-進(jìn)一步的討論1

1、僅供個人參考不得用于商業(yè)用途關(guān)于形式化的討論第2、3章證明了每一命題形式都可以通過等值變換成各種范式用真 值表方法和范式，回答了命題邏輯中很多有重要意義的問題，如：判定任 一給定的命題形式是不是重言式 （常真的）、矛盾式（常假的）；一命題形式 是不是另一些命題形式的邏輯后承；兩個任給的命題形式是否等值以及如 何判定一個推理形式是否正確，等等。但是，真值表方法有它的局限性， 它沒有把所有的重言式作為一個整體來研究，而邏輯中其它更復(fù)雜的部分 也不能用真值表方法來處理。公理方法是研究命題邏輯的另外一種方法， 通公理方法建立命題邏輯的形式系統(tǒng)一一命題演算。公理系統(tǒng)從一些公理出發(fā)，應(yīng)用邏輯規(guī)則，推導(dǎo)一系

2、列定理，這樣形成的演繹 體系稱為公理系統(tǒng)。歐氏幾何就是一個著名的古典公理系統(tǒng)。公理系統(tǒng)首先包括一組特別挑選出來的命題稱為公理，也叫作初始命 題。公理是不加證明而接受作為系統(tǒng)的出發(fā)點的。系統(tǒng)中其余的命題都從 公理出發(fā)經(jīng)證明推導(dǎo)出來，稱為定理。公理的選擇必須滿足某些一般的條 件，如公理必須明確地規(guī)定所包含的概念的意義，并且容易理解；一組公 理要能充分地刻劃所研究對象的恃征；是協(xié)調(diào)的（不會導(dǎo)致矛盾的），等等,在現(xiàn)代公理系統(tǒng)中，選作公理的命題其真實性不一定是最明顯的。公理系統(tǒng)包括一組不加定義的概念，稱為基本概念或初始概念。其余 的概念由基本概念定義，稱為派生概念?；靖拍畹囊饬x由公理明確地陳 述和規(guī)定

3、。現(xiàn)代公理系統(tǒng)和古典公理系統(tǒng)的一個重大差別是， 對于現(xiàn)代公理系統(tǒng)， 可以有多種不同的概念都使得公理為真， 或者說可以對系統(tǒng)作不同的解釋。 例如，等價關(guān)系理論就是現(xiàn)代公理系統(tǒng)的一個例子。僅供個人參考不得用于商業(yè)用途例 等價關(guān)系理論建立在下面三個公理的基礎(chǔ)上( xRy 讀作“ x 等價 于 y ”或“ x 與 y 等價”)。(E1) 對所有 x， xRx；(E2) 對所有x和y，如果xRy,則yRx;(E3) 對所有x, y和z,如果xRy并且yRz,則xRz。令A(yù)是一非空集合，R是A中的一個二元關(guān)系。二元組v A, R稱為 一個結(jié)構(gòu)。我們稱 R是A中的一個等價關(guān)系，v A, R是一個等價結(jié)構(gòu)如

4、果公理 (E1)-(E3) 被滿足的話。 (E1)-(E3) 不是關(guān)于某一個特定的等價結(jié)構(gòu) 的公理，其中的R可以作不同的解釋。例如，以 S表示命題形式的集合， 把R解釋為命題形式之間的等值關(guān)系“=”以自然數(shù)集合N為論域，把R 解釋為自然數(shù)的相等關(guān)系“=”以整數(shù)集合Z為論域，把a(bǔ)Rb解釋為a-b 能被5整除(記為“ R5)，那么v S, =,v N,=,v Z, R5都是等 價結(jié)構(gòu)。 形式系統(tǒng) 形式系統(tǒng)是完全形式化的公理系統(tǒng)。對公理系統(tǒng)的研究,可以采取兩 種不同的觀點：一種是把公理、定理等等看作是語句,另種足把公理理 解為由語句所表達(dá)的意義。前者是對公理系統(tǒng)的語法研究；后者是對公理 系統(tǒng)的語義研

5、究。形式系統(tǒng)是公理系統(tǒng)的語法部分,使用人工語言,用專 門的符號表示概念,把公理和定理都變換成一些符號公式,對這些具體對 象進(jìn)行研究。形式系統(tǒng)和通常的公理系統(tǒng)的另一個不同之點是,普通公理 系統(tǒng)不把從公理推導(dǎo)定理 (證明定理 )所用的邏輯規(guī)律 (推理規(guī)則 )包括系 統(tǒng)在本身之中,對于哪些證明方法是可以使用的沒有明確的規(guī)定。而在形 式系統(tǒng)中對此有明確的規(guī)定。一個形式系統(tǒng)包括三個組成部分。 第一部分是語言 (形式語言),通常 僅供個人參考不得用于商業(yè)用途是一種人工語言。語言的選擇應(yīng)當(dāng)盡可能使得語句的結(jié)構(gòu)能反映它們的意 義。建立一個語言首先是確定它的符號 （初始符號）。初始符號相當(dāng)于普通 拼音文字中的字

6、母，也稱為字母表。當(dāng)對符號加以解釋時，其中某些符號 就是公理系統(tǒng)的初始概念。符號的數(shù)目一般是無窮的，可以由有窮個初始 符號進(jìn)行構(gòu)造。符號的有窮序列 （有窮長的符號串 ） 稱為表達(dá)式。某一表達(dá)式中符號的 數(shù)目（包括重復(fù)數(shù)）稱為該表達(dá)式的長度。一個表達(dá)式 （ 不算單個符號自身 ） 也可能在另一表達(dá)式中出現(xiàn)。例如，“好讀書”和“好讀書不好讀書”是漢語中的兩個表達(dá)式，前一表達(dá)式在 后一表達(dá)式中出現(xiàn)兩次。表達(dá)式中有一部分被專門區(qū)別開來。在有的形式 語言中，這樣被區(qū)分開來的表達(dá)式包括兩類，一類稱為項，一類稱為合式 公式。一個語言的符號和公式確定時，語言得到確定。建立一個語言就是確 定它的符號和形成規(guī)則。語

7、言是純語法的對象。形式系統(tǒng)的第二個組成部分是它的公理。公理是從系統(tǒng)公式中挑選出 來作為推導(dǎo)系統(tǒng)中其余定理的出發(fā)點的部分公式。形式系統(tǒng)的第三個組成部分是推理規(guī)則，也稱變形規(guī)則。推理規(guī)則用 于從公理得出定理。每一條推理規(guī)則都規(guī)定：在一定條件下，從若干稱為 前提的公式能推出一個稱為結(jié)論的公式。當(dāng)一個推理的前提是公理或者是 已經(jīng)應(yīng)用推理規(guī)則從公理得出的結(jié)論，那么應(yīng)用一個推理規(guī)則得出的結(jié)論 稱為定理。一個形式系統(tǒng)的定理可以定義為：（1）一個形式系統(tǒng)的公理是它的定理；（2）如果所有的前提都是定理，那么應(yīng)用它的一個推理規(guī)則得出的結(jié)僅供個人參考不得用于商業(yè)用途論是它的定理。并且只有根據(jù)（1）和（2）這兩條能確

8、定它是定理的公式才是 系統(tǒng)的定理。對于一個形式系統(tǒng)的定理可以更清晰地描述如下：設(shè)So是系統(tǒng)的公理的集合，根據(jù)（1） So是能夠確定為定理的公式集合。設(shè)Si是只以So中的公式作前提應(yīng)用推理規(guī)則得出的結(jié)論集合，根據(jù)（2）S i是能夠確定為定理的公式集合。設(shè)S2是只以Si中的公式作前提應(yīng)用推理規(guī)則得出的結(jié)論集合，根據(jù)（2）S 2是能夠確定為定理的公式集合。用同樣的方法構(gòu)造集合S3 ,S4,.令S:是以So, S, S2 中的公式作前提應(yīng)用推理規(guī)則得出的結(jié)論 集合，根據(jù)（2）S ：是定理集合。用同樣的方法繼續(xù)構(gòu)造下去，直到根據(jù)（2）再也不能得到新的定理為止。這樣得到了一個形式系統(tǒng)的全部定理.上述方式的

9、定義稱為廣義歸納定義。一個歸納定義通過給出一組規(guī)則 （法則），由這些規(guī)則確定某一類對象組成的一個集合。這些規(guī)則中的第一 條規(guī)定某些對象屬于該集合，其余各條都規(guī)定如果某些對象屬于該集合， 那么另外的一個怎樣的對象屬于該集合。形式語言的（合式）公式的形成規(guī)則是一個關(guān)于合式公式的歸納定義。歸納定義具有這樣的特點：要證明歸納定義所確定的某一類對象中的 每一個都有某個性質(zhì)，只需證明滿足定義中陳述的規(guī)則的對象都有該性質(zhì)。 例如，要證明一個形式系統(tǒng)的每一定理都有性質(zhì)P,只需要證明滿足對定理的定義規(guī)則的公式都有性質(zhì)P。即只需要證明：（1）形式系統(tǒng)的每一公理都有性質(zhì)P;（2）如果一個推理規(guī)則的所有前提都有性質(zhì)P

10、,結(jié)論也有性質(zhì)P（推理規(guī)則保持性質(zhì)P）。用這個方法所作的證明稱為對于定理的歸納證明。（1）稱為基始，（2僅供個人參考不得用于商業(yè)用途）稱為歸納步驟。（2）中的假設(shè)：推理規(guī)則的所有前提都有性質(zhì)P,稱為歸 納假設(shè)。類似地，要證明每一個合式公式都有某個性質(zhì)，只需對合式公式 作歸納證明。歸納證明是一個很重要應(yīng)用很廣的證明方法。一個形式系統(tǒng)由語言 （ 包括初始符號和形成規(guī)則 ） 、公理和推理規(guī)則這 樣三部分組成。系統(tǒng)中的其它對象：合式公式 （ 或者還有項 ） 和定理都是在 系統(tǒng)內(nèi)逐步生成的。公式由符號和形成規(guī)則生成，定理由公理和推理規(guī)則 生成。每一公式和定理都有一個生成序列，一個公式的生成序列是由有窮

11、個公式組成的，其中每一個或者是由公式形成規(guī)則直接確定為公式的，或 者從前面的公式根據(jù)形成規(guī)則形成的，最后一個是由這序列生成的公式。 公式是有窮長的符號序列，所以總能在有窮步內(nèi)生成，生成序列的長度是 有窮的。定理是由公理和推理規(guī)則生成，每一推理規(guī)則的前提的數(shù)目是有 窮的。定理的生成序列稱為證明，其長度也是有窮的。一個證明是一有窮長的公式序列，其中每一個公式或者是一個公理， 或者是以序列中在前的公式作前提的一個推理規(guī)則的結(jié)論。如果一個公式 A 是一個證明 P 的最后的公式，就說 P 是 A 的一個證明，并說 A 是一個定 理。一形式系統(tǒng)的一個公式是系統(tǒng)中的定理當(dāng)且僅當(dāng)存在它的一個證明。 每一定理都

12、有一個證明：對定理作歸納證明，一個公理自身是它的一個證 明，所以每一公理是有證明的。如果一個定理是以某些定理作前提的推理 規(guī)則的結(jié)論，根據(jù)歸納假設(shè)，這些作前提的定理都是有證明的。這樣把這 些證明放在一起構(gòu)成一個公式序列，把那個公式（ 定理 ） 放在這序列的最后，就得到這個公式 （ 定理 ） 的一個證明。反過來，如果一個公式是有證明 的，它是一個證明的最后的公式，根據(jù)定理和證明的定義，它就是個定 理。在一個形式系統(tǒng)中，對于下列各點：僅供個人參考不得用于商業(yè)用途（1）任一符號是不是一初始符號；(2) 任一有窮長的符號序列是不是合式的；(3) 任一公式是不是一個公理；(4) 任一公式是不是以給定的公

13、式作前提的某個推理規(guī)則的結(jié)論；(5) 任一有窮長的公式序列是不是一個證明，也就是說，序列中的每 一公式是不是一個公理，或者是不是以序列中在前的公式作前提的推理規(guī) 則的一個結(jié)論。都要求有一個機(jī)械的方法，能在有窮步內(nèi)進(jìn)行判定。在形式系統(tǒng)中， 上述各點都是能夠判定的。一般不能機(jī)械地判定任一公式是不是一個定理。要求判定一個公式是 不是定理，需要給出它的一個證明，確定它是定理，或者證明它不是定理 即它是沒有證明的，所有的證明都不是它的證明。存在機(jī)械的方法判定一 個公式是不是定理的系統(tǒng) ( 理論 ) ，稱為是可判定的。內(nèi)容豐富的系統(tǒng)一般 是不可判定的。 語法和語義 形式系統(tǒng)是把普通公理系統(tǒng)形式化的結(jié)果。普

14、通的公理系統(tǒng)都是有解 釋的理論，其中的公理、定理等等都是有意義的。一個形式系統(tǒng)是一個公理系統(tǒng)的語法部分。在把一個公理系統(tǒng)形式化 時，用特定的符號表示公理系統(tǒng)中的概念，用符號公式表示公理系統(tǒng)中的 命題， 而把公理系統(tǒng)的內(nèi)容抽象。 在形式系統(tǒng)中， 處理的只是符號、 公式、 公式的符號組合的變換等等，完全不涉及內(nèi)容和意義。推理實際上就是對 公式(符號組合 )所作的變形或符號變換。從給定的前提能不能得出某個結(jié) 論，實際上就是根據(jù)變形 (推理) 規(guī)則，從給定的公式經(jīng)過符號變換能不能 僅供個人參考不得用于商業(yè)用途得出(變成) 某個公式。這種語法研究的優(yōu)點是，符號、公式等等都是具體 的對象， 是完全確定的，

15、 不會引起不同理解， 不會造成歧義并且容易掌握， 能更精確地處理。而意義是抽象的，往往比較難于理解和掌握，不同的人 在理解上很容易不一致。語法研究包括可證明性、協(xié)調(diào)性等重要概念和問 題。在把一個有內(nèi)容的理論形式化，建立一個形式系統(tǒng)時，在選擇形式系 統(tǒng)的語言時，應(yīng)盡可能使得系統(tǒng)的語句(公式)的結(jié)構(gòu)能反映它們的意義。 經(jīng)解釋后某些符號就成為概念，公式成為有意義的句子。對形式系統(tǒng)的解 釋，關(guān)于表達(dá)式的意義、表達(dá)式與它們所反映的對象之間的關(guān)系的研究， 屬于語義的研究。語義研究包括真假、可滿足性、意義等等概念和問題。 由語義研究建立的理論成為語義理論或者語義學(xué).關(guān)于公理系統(tǒng)P合式公式的定義是一個歸納定義

16、。因此，要證明所有的公式都有某個 性質(zhì)，可以對公式作歸納證明。這個證明方法稱為施歸納于公式的結(jié)構(gòu)， 具體地說，要證明所有公式有某個性質(zhì)，只要證明以下三點：(1)所有原子公式都有這個性質(zhì)；(2)對任何A,如果A有這個性質(zhì)，則 - A有這個性質(zhì)；(3)對任何A和B,如果A和B有這個性質(zhì)，則(A、B)有這性質(zhì)。P的公理和推理規(guī)則P的公理凡是有下列形式的 P的公式都是P的公理：(A1)卜 A (B A)(A2)卜(A (B C) (A B) (A C)(A3)卜(- B) ( B) A)僅供個人參考不得用于商業(yè)用途(A2)稱為蘊涵詞分配律，即蘊涵詞對蘊涵詞自身是可分配的.(A3)稱為反證律，它反映通常

17、的反證法，相當(dāng)于：假設(shè) A是假的(即 假設(shè)-A)，就引出一個矛盾，即得出 B并且非B(-A蘊涵B, - A蘊涵-B),那么就可以肯定A。P的定理我們也可以用另一種方式，即用歸納定義來定義P的定理：(1)P的每一公理是P的定理；(2)如果分離規(guī)則的前提 A1, A2是定理，B是應(yīng)用分離規(guī)則從 A1和 A2得出的結(jié)論，則B是定理。要證明P的所有定理有性質(zhì)P，需要證明：(1)每一公理有性質(zhì)P;(2)如果A1, A2有性質(zhì)P，B是應(yīng)用分離規(guī)則從 A1, A2得出的結(jié)論， 則B有性質(zhì)P.定理P中有1卜A，A (同一律)2卜(BT C)T (AT B)T (AT C)3卜(AT B)T (BT C)T (

18、AT C)(蘊涵詞傳遞律)4卜(AT (BT C)T (BT (AT C)證明僅供個人參考不得用于商業(yè)用途導(dǎo)出規(guī)則下面引進(jìn)若干規(guī)則，稱為導(dǎo)出的推理規(guī)則，簡稱導(dǎo)出規(guī)則。這些規(guī)則 從P中的公理、定理和分離規(guī)則導(dǎo)出。導(dǎo)出規(guī)則具有與分離規(guī)則同樣的性 質(zhì)：如果一個規(guī)則的前提是定理，那么應(yīng)用規(guī)則得出的結(jié)論也是定理。應(yīng) 用導(dǎo)出規(guī)則可以簡化證明。導(dǎo)出規(guī)則1從卜A,可推出卜B A導(dǎo)出規(guī)則2從卜A (BT C)，可推出卜(AT B)T (AT C)導(dǎo)出規(guī)則3從卜-M- B和卜-A B,可推出卜A導(dǎo)出規(guī)則4從卜A B和卜B C可推出卜AC導(dǎo)出規(guī)則5從卜A （BT C），可推出卜B （AT C）定理P中有5卜心（AT B）T B）6卜-AA （ 雙重否定律）7卜A - - A8卜（-A B廠（BA）9卜（一A，B）（一B A）10卜（AB），（-B- A）11卜（A B），（BA）12卜（ATB）T （AT B）TA）（歸謬律）證明演繹定理我們將證明一個重要的語法定理一演繹定理。