一個命題邏輯的排斥演算系統(tǒng)

杜國平

?

一個命題邏輯的排斥演算系統(tǒng)

杜國平

摘要：在日常推理中，一般的非有效式比邏輯矛盾具有更大的隱蔽性，通過對盧卡西維茨的工作進行改造，可以建立一個排斥所有非有效式的演算系統(tǒng)，并對其可靠性和完全性給出嚴格的證明。在此基礎(chǔ)上，證明了排斥系統(tǒng)和證明系統(tǒng)的不同性質(zhì)，這有利于人們進一步認識謬誤的本質(zhì)。

關(guān)鍵詞：非有效式；排斥演算；等謬

邏輯矛盾是我們在一個正確推理或者論證中首先必須加以拒斥的*參見杜國平、趙曼《一階謂詞邏輯反駁演算自然推理系統(tǒng)》(《重慶理工大學學報》2013年第9期，第1~6頁)，杜國平《一個命題邏輯的反駁演算系統(tǒng)》(《哲學研究》2014年第2期，第118~125頁)。，另外，對于一些并非是邏輯矛盾但也不是有效推理形式的推理或者論證我們也必須加以排斥。而且，這些不是邏輯矛盾的非有效推理形式其謬誤往往具有更大的隱蔽性，在日常的論證中也常常被不知不覺地廣泛使用，這尤其需要引起邏輯研究者的注意。

盧卡西維茨曾經(jīng)天才地指出了一個排斥所有非有效式的公理系統(tǒng)的框架*盧卡西維茨：《亞里士多德的三段論》，李真、李先琨譯，北京：商務(wù)印書館，1981年，第118~150頁。，本文將在盧卡西維茨工作的基礎(chǔ)上，對其公理系統(tǒng)進行適當?shù)母脑?，?gòu)建一個排斥所有非有效式的演算系統(tǒng)，并對其中的演算過程進行比較充分的展開和討論；隨后，在給出嚴格語義的基礎(chǔ)上，進一步證明該系統(tǒng)的可靠性和完全性。本文擬通過上述工作進而來探究如下若干問題：各種謬誤的邏輯起點在哪里？如果有邏輯起點，那么為什么是它(或它們)？各種謬誤之間的邏輯結(jié)構(gòu)是什么？各種謬誤如何公理化？如何證明排斥系統(tǒng)的可靠性和完全性？排斥系統(tǒng)和證明系統(tǒng)有什么本質(zhì)區(qū)別？

一、排斥演算的公理系統(tǒng)

命題邏輯排斥演算的形式語言包括如下三類符號：

(1)命題符號：p1,p2, …,pn, …

(3)技術(shù)性符號：), (

定義1.1命題邏輯排斥演算中的公式指的是當且僅當由使用下列規(guī)則生成的有限長的符號串：

(1)單獨一個命題符號是公式；

(2)如果A是公式，那么(A)也是公式；

(3)如果A、B是公式，那么(AB)也是公式。

由單獨一個命題符號構(gòu)成的公式稱之為原子公式，我們以小寫字母p、q、r等表示任一原子公式，以大寫字母A、B、C等(或加下標)表示任意一個公式，以符號、、等表示任意的公式集。下面引入3個定義連接詞符號：

ABdef(AB)

ABdef((AB))

ABdef((AB)(BA))

在不引起歧義的情況下，括號可以省略。

定義1.2如果以公式A1、A2、A3、…替換公式B中各處出現(xiàn)的命題變元p、q、r、…，得到公式A，則稱公式A是B的代入，記為AB(p/A1, q/A2, r/A3,)。

命題邏輯排斥演算系統(tǒng)E包括如下兩組公理模式和推理規(guī)則：

第一組：

證明公理：

證明規(guī)則：

第二組：

排斥公理：p

排斥規(guī)則：

(2)如果A是B的一個代入，并且A被排斥，則排斥B。簡記為E2。

(1)Ak是證明公理；

(2)Ak；

公式序列A1, A2, …,An1,An稱之為公式A的一個證明。

如果公式A由公式集形式可證明，則稱可證明出A，符號記為├EA，也簡記為：├A。

定義1.4如果公式A由形式可證明，則稱公式A是可證明的。由到A形式可證明的一個公式序列稱為公式A的一個證明。如果公式A是可證明的，則稱公式A為排斥演算系統(tǒng)E的定理，符號記為：├EA，也簡記為：├A。

定義1.5公式A形式可排斥，當且僅當存在公式序列A1,A2, …,An1, An，使得AnA且An是通過排斥公理或者排斥規(guī)則得到，并且對于每一個Ak(1kn)，Ak滿足下列條件之一：

(1)Ak是證明公理；

(2)Ak是排斥公理；

(3)有i，jk，使得AiAjAk；

(4)Ak由在它前面的公式通過使用排斥規(guī)則E1或者E2而得到。

公式序列A1,A2, …,An1, An稱之為公式A的一個排斥。

定義1.6如果公式A形式可排斥，則稱公式A為排斥演算系統(tǒng)E的謬論，符號簡記為：★A。

在一個證明或者排斥中，我們將直接使用已經(jīng)證明或者排斥的定理或者謬論。

關(guān)于一個定理的證明，在一般的現(xiàn)代邏輯教科書中都有比較詳細的表述*參見Elliott Mendelson, Introduction to Mathematical Logic, Florida：CRC Press, 2010.，本文不再重復，以下只是列出在后面的排斥中將要用到的一些主要定理。

定理1.1

(2)├((qq)p)p

(3) ├(pp)p

(6)├(pq)(pq)

(7)├pqp

(8)├AAB

(9)├A(AB)

(10)├A(BB)A

(11)├A(BB)A

(12)如果A├B，則├AB

(13)如果├ABC，則├CAB

排斥

定理1.1(1)

(2)★p

排斥公理

(1)(2)E1

(3)E2(p/pq)

這表明任一原子公式的否定都是謬論，都可以被排斥演算系統(tǒng)E所排斥。

謬論1.2★pq(其中p、q是不同的原子公式)

排斥

(1)((qq)r)r

定理1.1(2)

(2)★r

排斥公理

(3)★(qq)r

(1)(2)E1

(4)★pq(其中p、q是不同的原子公式)

(3)E2(p/qq,q/r)

這表明任一前后件是不同原子公式的蘊涵式都是謬論，都可以被排斥演算系統(tǒng)E所排斥。

謬論1.3★pq

排斥

(1)(pp)p

定理1.1(3)

謬論1.1

(3)★pp

(1)(2)E1

(4)★pq

(3)E2(p/p,q/p)

這表明以任一原子公式作為前件、以任一原子公式的否定作為后件而構(gòu)成的蘊涵式都是謬論，都可以被排斥演算系統(tǒng)E所排斥。

排斥

定理1.1(4)

(2)★q

排斥公理

(1)(2)E1

(3)E2(p/q,q/q)

這表明以任一原子公式的否定作為前件、以任一原子公式作為后件而構(gòu)成的蘊涵式都是謬論，都可以被排斥演算系統(tǒng)E所排斥。

排斥

定理1.1(5)

(2)★pq

謬論1.2

(1)(2)E1

(3)E2(p/pq,q/p)

這表明以任意不同原子公式的否定作為前后件而構(gòu)成的蘊涵式都是謬論，都可以被排斥演算系統(tǒng)E所排斥。

謬論1.6★pq

排斥

(1)(pq)(pq)

定理1.1(6)

謬論1.4

(3)★pq

(1)(2)E1

這表明任意兩個原子公式的析取式都是謬論，都可以被排斥演算系統(tǒng)E所排斥。

類似可以排斥以下3個謬誤：

謬論1.8★pq(其中p、q是不同的原子公式)

對于合取式，也有類似的謬誤可以被排斥：

謬論1.10★pq

排斥

(1)pqp

定理1.1(7)

(2)★p

排斥公理

(3)★pq

(1)(2)E1

這表明任意兩個原子公式的合取式都是謬論，都可以被排斥演算系統(tǒng)E所排斥。

類似可以排斥以下3個謬誤：

謬論1.12★pq

作為一個非常特殊的謬誤——邏輯矛盾式AA，在排斥演算系統(tǒng)E中也可以被排斥：

謬論1.14★AA

(1)AAp

定理1.1(8)

(2)★p

排斥公理

(3)★AA

(1)(2)E1

根據(jù)命題邏輯的可靠性定理可知，所有命題邏輯系統(tǒng)的定理A都是永真式，因而其否定A都是矛盾式。以下定理表明，所有矛盾式在排斥演算系統(tǒng)E中都可以被排斥：

定理1.2如果├A，則★A。

證明

(1)A

前提

(2)A(Ap)

定理1.1(9)

(1)(2)MP

(4)★p

排斥公理

(1)(2)E1

下面我們來排斥一個更一般的謬論：

謬論1.15★A1A2…An1An(其中每一Ak(1kn)是任一原子公式或者原子公式的否定，并且所涉及的原子公式各不相同)

排斥

施歸納于其中所涉及的原子公式的數(shù)目k。

當k1時，A1或者是p或者是p，根據(jù)排斥公理和謬論1.1，命題成立。

假設(shè)當kn1時命題成立，下面來證明當kn時命題也成立。

可分如下兩種情況排斥A1A2…An1An：

情況一：An是原子公式p

(1) (A1A2…An1(AnAn))(A1A2…An1)

定理1.1(10)

(2)★A1A2…An1

歸納假設(shè)

(3)★A1A2…An1(AnAn)

(1)(2)E1

(4)★A1A2…An1p

(3)E2(p/AnAn)

情況二：An是原子公式的否定p

(1) (A1A2…An1(AnAn))(A1A2…An1)

定理1.1(11)

(2)★A1A2…An1

歸納假設(shè)

(3)★A1A2…An1(AnAn)

(1)(2)E1

(4)★A1A2…An1p

(3)E2(p/(AnAn))

二、排斥演算的語義

定義2.1一個真值賦值v是以所有公式的集為定義域、以{0,1}為值域的一個函數(shù)，并滿足下列條件：

(1)v(A)1，當且僅當v(A)0；

(2)v(AB)1，當且僅當v(A)0或者v(B)1。

定義2.2對于任一公式A，如果對于任一賦值v，均有v(A)1，則稱公式A是永真式，記為：╞A；對于任一公式A，如果存在賦值v，使得v(A)0，則稱公式A是非永真式，記為：☆A(yù)。

根據(jù)定義，顯然可得：

定理2.1☆p。

即排斥公理是非永真式。

定理2.2如果╞AB，并且☆B，則☆A(yù)。

證明：假設(shè)☆B，根據(jù)定義2.2，則存在賦值v，使得v(B)0。因為╞AB，所以有v(AB)1，根據(jù)語義定義2.1，可得v(A)0，因此有☆A(yù)。

該定理表明，排斥規(guī)則E1是保持非永真性的。

定理2.3如果A是B的一個代入，并且☆A(yù)，則☆B。

證明：假設(shè)AB(p/A1,q/A2,r/A3,)，如果☆A(yù)，根據(jù)定義2.2，則存在賦值v，使得v(A)0?，F(xiàn)構(gòu)造一個賦值v′，令v′(p)v(A1),v′(q)v(A2),v′(r)v(A3),，則有v′(B)v(A)0，因而有☆B。

該定理表明，排斥規(guī)則E2是保持非永真性的。

三、排斥演算的可靠性和完全性

根據(jù)上述定理2.1、定理2.2和定理1.2.3，可以得出關(guān)于命題邏輯排斥演算系統(tǒng)E的一個重要元定理：

定理3.1(可靠性定理)設(shè)A為任一公式，如果★A，則☆A(yù)。

定理3.2設(shè)A為任一公式，A1,A2, …,An1,An是其中出現(xiàn)的所有不同的原子公式。對于任一給定的賦值v，如果v(Ak)1(1kn)，則令A(yù)k′Ak；如果v(Ak)0(1kn)，則令A(yù)k′Ak。在該賦值v下，如果v(A)1，則令A(yù)′A；如果v(A)0，則令A(yù)′A。則有：A1′,A2′, …,An1′,An′├A′。

證明：施歸納于公式A中連接詞和的數(shù)目n。

當n0，即A中沒有連接詞和，則A即為原子命題p。因此在賦值v下，如果v(p)1，則v(A)1，所需證明的即為p├p；如果v(p)0，則v(A)0，所需證明的即為p├p。無論在哪種情況下，原命題都顯然成立。

假設(shè)原命題在A中連接詞和的數(shù)目小于n時都成立，則當A中連接詞和的數(shù)目為n時，可有如下兩種情況：

情況一：AB。在賦值v下，如果v(B)1，則有v(A)0，A′A，由v(B)1根據(jù)歸納假設(shè)有A1′,A2′, …,An1′,An′├B，因而有A1′,A2′, …,An1′,An′├B，即有A1′,A2′, …,An1′,An′├A，因而所需得證；如果v(B)0，則有v(A)1，A′A，由v(B)0根據(jù)歸納假設(shè)有A1′,A2′, …,An1′,An′├B，因而有A1′,A2′, …,An1′,An′├A，因而所需得證。

情況二：ABC。

情況二(1)，在賦值v下，v(B)1并且v(C)1，則有v(A)1，A′A。由v(B)1并且v(C)1根據(jù)歸納假設(shè)有A1′,A2′, …,An1′,An′├B，A1′,A2′, …,An1′,An′├C，因而有A1′,A2′, …,An1′,An′├BC，即有A1′,A2′, …,An1′,An′├A，因而所需得證。

情況二(2)，在賦值v下，v(B)1并且v(C)0，則有v(A)0，A′A。由v(B)1并且v(C)0根據(jù)歸納假設(shè)有A1′,A2′, …,An1′,An′├B，A1′,A2′, …,An1′,An′├C，因而有A1′,A2′, …,An1′,An′├(BC)，即有A1′,A2′, …,An1′,An′├A，因而所需得證。

情況二(3)，在賦值v下，v(B)0并且v(C)1，則有v(A)1，A′A。由v(B)0并且v(C)1根據(jù)歸納假設(shè)有A1′,A2′, …,An1′,An′├B，A1′,A2′, …,An1′,An′├C，因而有A1′,A2′, …,An1′,An′├BC，即有A1′,A2′, …,An1′,An′├A，因而所需得證。

情況二(4)，在賦值v下，v(B)0并且v(C)0，則有v(A)1，A′A。由v(B)0并且v(C)0根據(jù)歸納假設(shè)有A1′,A2′, …,An1′,An′├B，A1′,A2′, …,An1′,An′├C，因而有A1′,A2′, …,An1′,An′├BC，即有A1′,A2′, …,An1′,An′├A，因而所需得證。*該定理的證明主要參考了Elliott Mendelson的思想,見Elliott Mendelson, Introduction to Mathematical Logic, pp.32-33.

定理3.3(完全性定理)設(shè)A為任一公式，如果☆A(yù)，則★A。

證明：假設(shè)A1,A2, …,An1,An是A中出現(xiàn)的所有不同的原子公式，如果☆A(yù)，則存在一賦值v，使得v(A)0。根據(jù)定理3.2可得：A1′,A2′, …,An1′,An′├A，由此可得如下排斥序列：

(1)A1′,A2′, …,An1′,An′├A

已知

(2)A1′A2′…An1′An′A

定理1.1(12)

(3)AA1′A2′…An1′An′

定理1.1(13)

(5)★A

(3)(4)E1

四、排斥演算的特殊結(jié)果

在經(jīng)典命題邏輯的證明系統(tǒng)中，p和pq不是邏輯等值的，因而在下列兩個陳述中只有一個是成立的。

(1)p├pq

(2)pq├p

即只有(1)成立，(2)不成立。

但是在排斥系統(tǒng)中，有下列定理：

定理4.1

(1)如果★p，則★pq

(2)如果★pq，則★p

證明1

(1)★p

前提

(2)p(AA)p

定理1.1(10)

(3)★p(AA)

(1)(2)E1

(4)★pq

(3)E2(q/AA)

證明2

(1)★pq

前提

(2)★p

(2)E2(p/pq)

定義3.1設(shè)A、B為任意公式，如果★A當且僅當★B，則稱A和B等謬，簡記為：★A★B。

定理4.2★pq★pq

證明

(1)★pq

前提

(2)pqpq經(jīng)典命題邏輯證明系統(tǒng)定理

(3)★pq

(1)(2)E1

(4)★pq

前提

(5)(pq)(AA)pq

經(jīng)典命題邏輯證明系統(tǒng)定理

(6)★(pq)(AA)

(4)(5)E1

(7)★pq

(6)E2(p/pq,q/AA)

定理4.1和定理4.2表明，pq和pq都可以代替排斥公理p來作為命題邏輯排斥系統(tǒng)的唯一一條公理。

責任編校：余沉

作者簡介：杜國平，中國社會科學院哲學研究所研究員，哲學博士、工學博士(北京100732)。

基金項目：國家社科基金重大招標項目(14ZDBO14)

中圖分類號：B812.5

文獻標識碼：A

文章編號：1001-5019(2015)01-0042-05

DOI：10.13796/j.cnki.1001-5019.2015.01.005