“不可得兼”型命題邏輯自然推演系統(tǒng)

杜國平

作為文化傳承載體的自然語言——漢語有著豐富的邏輯聯(lián)結(jié)詞，其中表達“兩者不可并立”關(guān)系的二元聯(lián)結(jié)詞就有“若A，則非B”“并非A且B”“AB 兩者不可得兼”等[1]。如《孟子·告子上》：“魚，我所欲也，熊掌，亦我所欲也，二者不可得兼，舍魚而取熊掌者也。生，亦我所欲也，義，亦我所欲也，二者不可得兼，舍生而取義者也?！?/p>

本文擬基于括號表示法[2-5]，以二元聯(lián)結(jié)詞“不可得兼”作為唯一初始聯(lián)結(jié)詞，建立一個命題邏輯自然推演系統(tǒng)，并分析、探討其與常用命題邏輯系統(tǒng)之間的關(guān)系。

一、形式語言

定義1.01 形式語言￡DP包括如下兩類符號：

（1）命題符號：p1，p2，…，pn，pn+1，…；

（2）聯(lián)結(jié)詞符號：（，）。

其中初始聯(lián)結(jié)詞只有一對左右圓括號“（）”。

定義1.02 形式語言￡DP中的公式當且僅當有限次使用如下規(guī)則而得：

（1）單獨的一個命題符號是公式；

（2）若符號串D、E 是公式，則（DE）是公式。

通常以大寫字母A、B、C等表示任意的公式?！闐P中所有公式的集合記為Form（￡DP）。

“不可得兼”型聯(lián)結(jié)詞（AB）的語義可用真值表直觀表示如下：

命題1.01 聯(lián)結(jié)詞（AB）對于二值真值函數(shù)其表達能力是完備的。

證明：

基始。對于任一一元二值真值函數(shù)，存在如下4 種可能：

不難驗證：

?1[A]=（（AA）A）

?2[A]=（（AA）（AA））

?3[A]=（AA）

?4[A]=（（（AA）A）（（AA）A））①等式左邊的方括號為通常的括號用法，等式右兩邊的圓括號為初始二元真值聯(lián)結(jié)詞。

歸納步驟。假設(shè)對于任一n 元真值函數(shù)均可由初始聯(lián)結(jié)詞“不可得兼”定義，則對于任一n+1元二值真值函數(shù)H[p1，p2，…，pn，pn+1]，有：

H[p1，p2，…，pn，pn+1]=（（pn+1H[p1，p2，…，pn，1]）（（pn+1pn+1）H[p1，p2，…，pn，0]））

不難驗證：

若pn+1=1，則上式

若pn+1=0，則上式

不論在哪種情況下，均有左邊=右邊。

因此，定理得證。

由此可見，在表達能力上，括號“（AB）”與舍弗函數(shù)之一的析舍“A|B”[6]以及二元聯(lián)結(jié)詞“”等價，從真值表也可以看出這一點。但是，括號“（AB）”不再像析舍及二元聯(lián)結(jié)詞那樣對于復(fù)雜的公式需要外加另外的符號如括號等來標志結(jié)合的先后順序和層次等，其轄域是非常清楚的，因此比舍弗函數(shù)及聯(lián)結(jié)詞集{￢，∨}等表達更加簡練。

二、自然推理規(guī)則

基于形式語言￡DP的一個“不可得兼”型命題邏輯自然推演系統(tǒng)NP1包括如下5 條推理規(guī)則：

規(guī)則SR1 A ├A。簡記為Ref。

規(guī)則SR2 如果Σ├A，那么Σ，Σ′├A。簡記為+。

規(guī)則SR3 如果Σ，A，B ├C，且Σ，A，B ├（CC），那么Σ ├（AB）。簡記為（）+。

規(guī)則SR4 如果Σ ├（（AA）B），并且Σ ├B，那么Σ ├A 。簡記為（）r–。

規(guī)則SR5 如果Σ ├（AB），并且Σ ├A，那么那那么Σ ├（BB）。簡記為（）l-。

規(guī)則SR1、規(guī)則SR2 是通常的命題邏輯自然推理規(guī)則。規(guī)則SR3、規(guī)則SR4 和規(guī)則SR5 這3條規(guī)則是關(guān)于唯一聯(lián)結(jié)詞括號“（）”的特征推理規(guī)則，其中規(guī)則SR3 是括號引入規(guī)則，規(guī)則SR4、規(guī)則SR5 是括號消去規(guī)則，規(guī)則SR4 是括號右消去規(guī)則，規(guī)則SR5 是括號左消去規(guī)則。

規(guī)則SR3 的直觀意思是，若由前提 A、B 推出矛盾，則 A、B 不可得兼；規(guī)則SR4 的直觀意思是，若B 與A 的否定不可得兼（即有B 則 A），且B 成立，則A 亦成立；規(guī)則SR5 的直觀意思是，若A 與B 不可得兼，且A 成立，則B 不成立。

三、定理的推演

定義3.01 公式A 在系統(tǒng)NP1中由公式集Σ形式可推演，記為Σ├A，當且僅當Σ├A 能由有限次使用規(guī)則SR1-規(guī)則SR5 而生成。

引理3.01 若 A ∈Σ，則Σ├A。

該引理簡記為∈。

引理3.02 若Σ├Σ′，且Σ′├C，則Σ├C。

（一）關(guān)于“否定”聯(lián)結(jié)詞

定理3.11 B├（（BB）（BB））。

證明：

這是雙否引入律。

定理3.12

（1）Σ├（（BB）B）

（2）Σ├（B（BB））

證明：

（1）

（2）類似可證。

這是排中律。

定理3.13 若Σ，（BB）├C，且Σ，（BB）├（CC），則Σ├B。

證明：

這是反證律。

定理3.14 若Σ├（（BB）（BB）），則Σ├B。證明：

這是雙否消去律。

定理3.15 若Σ，B├C，且Σ，B├（CC），則Σ├（BB）。

證明：

這是歸謬律。

定理3.16 若Σ├B，且Σ├（BB），則Σ├C。

這是司各脫法則。

（二）關(guān)于“蘊涵”聯(lián)結(jié)詞

定理3.21 若Σ，A├B，則Σ├（A（BB））

證明：

這是演繹定理。

定理3.22 若Σ├（A（BB）），且Σ├A，則Σ├B。

證明：

這是與規(guī)則SR5 相應(yīng)的另一種形式的左消去規(guī)則。

定理3.23 若Σ├（A（BB）），且Σ├（B（CC）），則Σ├（A（CC））。

證明：

這是蘊涵的傳遞律。

定理3.24 Σ├（A（（B（AA））（B（AA））））。

證明：

定理3.25 若Σ├（A（（B（CC））（B（CC）））），且Σ├（A（BB）），則Σ├（A（CC））。

證明：

定理3.26 Σ├（（A（（B（CC））（B（CC））））（（（A（BB））（（A（CC））（A（CC））））（（（A（BB））（（A（CC））（A（CC））））））

證明：

定理3.27 若Σ├（AB），并且Σ├B，那么Σ├（AA）。

證明：

這是與規(guī)則SR4 相應(yīng)的另一種形式的右消去規(guī)則。

定理3.28

（1）若Σ，（AA）├B，則Σ，（BB）├A；

（2）若Σ，A├（BB），則Σ，B├（AA）；

（3）若Σ，（AA）├（BB），則Σ，B├A；

（4）若Σ，A├B，則Σ，（BB）├（AA）。

證明：

（1）

（2）（3）（4）類似可證。

這是假言易位律。

定理3.29 Σ├（（（AA）（BB））（（（（AA）B）（AA））（（（AA）B）（AA））））。

證明：

（三）關(guān)于“析取”聯(lián)結(jié)詞

定理3.31 若Σ├（AB），且Σ├（A（BB）），則Σ├（AA）。

證明：

定理3.32 若Σ├（AB），且Σ├（（AA）B），則Σ├（BB）。

證明：

定理3.33

（1）若Σ├（AA），則Σ├（AB）；

（2）若Σ├（BB），則Σ├（AB）。

證明：

（2）類似可證。

定理3.34 若Σ├（AB），則Σ├（BA）。

證明：

定理3.35 若Σ，（AA）├C，且Σ，（BB）├C，則Σ，（AB）├C。

證明：

（四）關(guān)于“合取”聯(lián)結(jié)詞

定理3.41

（1）若Σ├（（AB）（AB）），則Σ├A；

（2）若Σ├（（AB）（AB）），則Σ├B。

證明：

（1）

（2）類似可證。

定理3.42 若Σ├A，且Σ├B，則Σ├（（AB）（AB））。

證明：

（五）關(guān)于“等值”聯(lián)結(jié)詞

定理3.51

（1）Σ，A，（（AB）（（AA）（BB）））├B；

（2）Σ，B，（（AB）（（AA）（BB）））├A。

證明：

（1）

（2）類似可證。

定理3.52

（1）Σ，A，B├（（AB）（（AA）（BB）））；

（2）Σ，（AA），（BB）├（（AB）（（AA）（BB）））。

證明：

（1）

（2）類似可證。

四、系統(tǒng)NP1 和常見系統(tǒng)之間的關(guān)系

為了使表達更加簡潔，下面引入若干定義符號。

定義4.11

根據(jù)上述定義，前述相關(guān)定理可簡記為（相應(yīng)的定理使用原序號加“′”表示）：

定理3.11′ B├<>。

定理3.12′

定理3.13′ 若Σ，├C，且Σ，├，則Σ├B。

定理3.14′ 若Σ├<>，則Σ├B。

若把看作B 的否定，則定理3.11′—定理3.14′分別清晰地表述了雙否引入律、排中律、反證律和雙否消去律。

特別地，有：

定理3.24′ Σ├「A 「B「A」」」。

定理3.26′ Σ├「「A 「BC」」「「AB」「AC」」」

定理3.29′ Σ├「「B」「「」A」」。

定理3.22′ 若Σ├「AB」，且Σ├A，則Σ├B。

如所知，下列公理和推理規(guī)則構(gòu)成了一個常見的只含聯(lián)結(jié)詞否定和蘊涵的命題邏輯公理系統(tǒng)：

公理1：A →（B →A）

公理2：（A →（B →C）→（（A →B）→（A →C））

公理3：（￢A →B）→（（￢A →￢B）→A）

推理規(guī)則：若A →B，且A，則B。

將定理3.24′、定理3.26′、定理3.29′和定理3.22′與上述公理及推理規(guī)則相比，不難發(fā)現(xiàn)其中除了聯(lián)結(jié)詞的符號差異之外，兩者在推理功能方面并無二致。

如所知，下列推理規(guī)則構(gòu)成了一個常見的只含聯(lián)結(jié)詞否定和蘊涵的命題自然推理系統(tǒng)：

規(guī)則1 A├A。

規(guī)則2 若Σ├A，則Σ，Σ′├A。

規(guī)則3 若Σ，A├B，則Σ├A→B。

規(guī)則4 若Σ├A→B，且Σ├A，則Σ├B。

規(guī)則5 若Σ，￢A├B，且Σ，￢A├￢B，則Σ├A。

將規(guī)則SR1、規(guī)則SR2、定理3.21、定理3.22和定理3.13 與上述推理規(guī)則相比，不難發(fā)現(xiàn)其中除了聯(lián)結(jié)詞的符號差異之外，兩者在推理功能方面并無差別。

由此可知，系統(tǒng)NP1和常見的命題邏輯推理系統(tǒng)是等價的。因此，系統(tǒng)NP1相對于經(jīng)典的二值語義具有可靠性和完全性。

由此可見，僅僅使用一對括號就可以建立基于“不可得兼”型聯(lián)結(jié)詞的邏輯推理系統(tǒng)，括號表示法極大地簡化了構(gòu)建邏輯系統(tǒng)所需的初始聯(lián)結(jié)詞，括號表示法也可以比較直觀地、有效率地（不需要使用其他輔助的句法符號）表達各種邏輯推理規(guī)律。