一類3值邏輯2元Sheffer函數(shù)

杜 國 平

一類3值邏輯2元Sheffer函數(shù)

杜 國 平

【摘要】3值邏輯Sheffer函數(shù)研究是多值邏輯重要的基礎(chǔ)理論之一。通過給出嚴(yán)格的相互可定義性，54個3值2元S型函數(shù)可分為相互定義的10個組，并且可分為3種類型：117型、135型和333型。其中，117型6個，135型36個，333型12個。通過嚴(yán)格的定義可以證明：只有333型中的6個不是Sheffer函數(shù)，其余48個均為Sheffer函數(shù)。在此基礎(chǔ)上，可以進(jìn)一步發(fā)現(xiàn)并證明大量的其他類Ci型和類Di 型Sheffer函數(shù)。

【關(guān)鍵詞】3值邏輯Sheffer函數(shù)S型函數(shù)類Ci型Sheffer函數(shù)

一、3值2元Sheffe函數(shù)的類型

3值邏輯Sheffer函數(shù)研究是多值邏輯重要的基礎(chǔ)理論之一。*Lou Goble. The Blackwell Guide to Philosophical Logic, Wiley-Blackwell, 2001.本文不討論一般的多值邏輯函數(shù)集中的準(zhǔn)完備集問題，而是通過給出嚴(yán)格的相互可定義性來分析某些特殊函數(shù)之間的關(guān)系，并證明相關(guān)結(jié)果。n值m元邏輯函數(shù)共有nnm個，3值2元邏輯函數(shù)共計有332，即19 683個，將近兩萬個。如果對所有這些函數(shù)一個一個地討論其是否是Sheffer函數(shù)，那將是一項艱苦而繁瑣的工作。因此我們將選擇其中的一類特殊函數(shù)對其進(jìn)行分析、歸類。

取E3={0, 1, 2}，一個3值2元邏輯函數(shù)G(x,y)的真值表是如下的一個九宮格：

一個3值2元Sheffer函數(shù)的真值表其V1位置上不可能是0。因為如果這個位置是0，意味著G(0,0)=0，因此G(x,y)就不可能定義出3值一元函數(shù)～x：

同樣，一個3值2元Sheffer函數(shù)的真值表其V5位置上不可能是1，V9位置上也不可能是2。一個3值2元邏輯函數(shù)G(x,y)如果是Sheffer函數(shù)，那么其真值表可能是如下情形之一。

一個3值2元Sheffer函數(shù)要能定義出所有的3值邏輯函數(shù)，當(dāng)然包括諸如max(x,y)、min(x,y)這樣的邏輯函數(shù)，考慮到max(x,y)和min(x,y)的真值表其中的變元具有對稱性(即在真值表中，V2和V4、V3和V7、V6和V8位置上的值相同)，因此下面我們研究這類真值表中的變元具有對稱性的3值2元函數(shù)。*杜國平：《單獨函數(shù)完全的算子》，載《哲學(xué)研究》2000年第6期。這樣的函數(shù)共有54個(我們稱之為3值2元S型函數(shù))，其真值表如下。

……

……

已經(jīng)證明，其中的D4，D5，D7，D23，D25，D26，C10，C13，C15，C19，C21，C24等12個是3值2元Sheffer函數(shù)。*杜國平：《三值邏輯Sheffer函數(shù)》，載《哲學(xué)動態(tài)(邏輯學(xué)研究專輯)》2005年。

那么，由上述結(jié)果可得：

容易證明：

[1]D14pq=C1C1pqC1pq

[2]D1pq=C1C1ppC1qq

[3]C1pq=D1D1pqD1pq

[4]C1pq=D1D1ppD1qq

[5]C1pq=D14D14pqD14pq

[6]C14pq=D14D14ppD14qq

[7]D1pq=C14C14pqC14pq

[8]D27pq=C14C14ppC14qq

[9]C14pq=D27D27pqD27pq

[10]C27pq=D27D27ppD27qq

[11]D27pq=C27C27ppC27qq

[12]D1pq=C27C27pqC27pq

這樣，C1、C14、C27、D1、D14和D27構(gòu)成了可以相互定義的一個組。

容易證明：

[13]D15pq=C2C2pqC2pq

[14]D10pq=C2C2ppC2qq

[15]C2pq=D15D15pqD15pq

[16]C17pq=D15D15ppD15qq

[17]C9pq=D10D10pqD10pq

[18]C2pq=D10D10ppD10qq

[19]D21pq=C17C17pqC17pq

[20]D15pq=C17C17ppC17qq

[21]C17pq=D21D21pqD21pq

[22]C9pq=D21D21ppD21qq

[23]D10pq=C9C9pqC9pq

[24]D21pq=C9C9ppC9qq

這樣，C2、C9、C17、D10、D15和D21構(gòu)成了可以相互定義的一個組。

容易證明：

[25]D13pq=C3C3pqC3pq

[26]D19pq=C3C3ppC3qq

[27]C3pq=D13D13pqD13pq

[28]C11pq=D13D13ppD13qq

[29]C18pq=D19D19pqD19pq

[30]C3pq=D19D19ppD19qq

[31]D24pq=C11C11pqC11pq

[32]D13pq=C11C11ppC11qq

[33]C11pq=D24D24pqD24pq

[34]C18pq=D24D24ppD24qq

[35]D19pq=C18C18pqC18pq

[36]D24pq=C18C18ppC18qq

這樣，C3、C11、C18、D13、D19和D24構(gòu)成了可以相互定義的一個組。

容易證明：

[37]D17pq=C4C4pqC4pq

[38]D2pq=C4C4ppC4qq

[39]C25pq=D2D2pqD2pq

[40]C4pq=D2D2ppD2qq

[41]C4pq=D17D17pqD17pq

[42]C23pq=D17D17ppD17qq

[43]D9pq=C23C23pqC23pq

[44]D17pq=C23C23ppC23qq

[45]C23pq=D9D9pqD9pq

[46]C25pq=D9D9ppD9qq

[47]D2pq=C25C25pqC25pq

[48]D9pq=C25C25ppC25qq

這樣，C4、C23、C25、D2、D9和D17構(gòu)成了可以相互定義的一個組。

容易證明：

[49]D18pq=C5C5pqC5pq

[50]D11pq=C5C5ppC5qq

[51]C7pq=D11D11pqD11pq

[52]C5pq=D11D11ppD11qq

[53]C5pq=D18D18pqD18pq

[54]C26pq=D18D18ppD18qq

[55]D11pq=C7C7pqC7pq

[56]D3pq=C7C7ppC7qq

[57]C26pq=D3D3pqD3pq

[58]C7pq=D3D3ppD3qq

[59]D3pq=C26C26pqC26pq

[60]D18pq=C26C26ppC26qq

這樣，C5、C7、C26、D3、D11和D18構(gòu)成了可以相互定義的一個組。

容易證明：

[61]D16pq=C6C6pqC6pq

[62]D20pq=C6C6ppC6qq

[63]C6pq=D16D16pqD16pq

[64]C20pq=D16D16ppD16qq

[65]C16pq=D20D20pqD20pq

[66]C6pq=D20D20ppD20qq

[67]D20pq=C16C16pqC16pq

[68]D6pq=C16C16ppC16qq

[69]C20pq=D6D6pqD6pq

[70]C16pq=D6D6ppD6qq

[71]D6pq=C20C20pqC20pq

[72]D16pq=C20C20ppC20qq

這樣，C6、C16、C20、D6、D16和D20構(gòu)成了可以相互定義的一個組。

容易證明：

[73]D12pq=C8C8pqC8pq

[74]D12pq=C8C8ppC8qq

[75]C8pq=D12D12pqD12pq

[76]C8pq=D12D12ppD12qq

這樣，C8和D12構(gòu)成了可以相互定義的一個組。

容易證明：

[77]C12pq=D22D22pqD22pq

[78]C12pq=D22D22ppD22qq

[79]D22pq=C12C12pqC12pq

[80]D22pq=C12C12ppC12qq

這樣，C12和D22構(gòu)成了可以相互定義的一個組。

容易證明：

[81]C22pq=D8D8pqD8pq

[82]C22pq=D8D8ppD8qq

[83]D8pq=C22C22pqC22pq

[84]D8pq=C22C22ppC22qq

這樣，C22和D8構(gòu)成了可以相互定義的一個組。

通過上述研究，可以看出54個3值2元邏輯函數(shù)可以分為內(nèi)部可以相互定義的10組：

我們可以按其首元分別將其稱之為C1組、C2組等等。按照真值表中3個值的個數(shù)不同，又可以將54個3值2元邏輯函數(shù)分為3種類型：117型(即真值表中3個值的數(shù)目分別為1個、1個和7個)、135型和333型。其中117型只有C1組；333型包括C6組、C8組、C12組和C22組；其余5組均為135型。

二、3值2元邏輯函數(shù)的表達(dá)能力

上述54個3值2元邏輯函數(shù)共分成了10種類型，這10種類型之中的函數(shù)是相互可定義的，那么它們的表達(dá)能力是相同的。下面我們來研究這10種類型之間的可表達(dá)性。當(dāng)然，首先我們已經(jīng)知道下述12個Sheffer函數(shù)其表達(dá)能力是最強的：

下面討論其他類型之間的可表達(dá)性。

[1]E1pq=C2D10pqD15pq

[2]C5pq=C2E1pqE1pq

[3]E2pq=C2D10pqD21pq

[4]C26pq=C2E2pqE2pq

[5]E3pq=C2D15pqD21pq

[6]C23pq=C2E3pqE3pq

[7]E4pq=C9D10pqD15pq

[8]C4pq=C9E4pqE4pq

[9]E5pq=C9D10pqD21pq

[10]C7pq=C9E5pqE5pq

[11]E1pq=C9D15pqD21pq

[12]C5pq=C9E1pqE1pq

[13]E5pq=C17D10pqD15pq

[14]C7pq=C17E5pqE5pq

[15]E6pq=C17D10pqD21pq

[16]C25pq=C17E6pqE6pq

[17]E2pq=C17D15pqD21pq

[18]C26pq=C17E2pqE2pq

下面進(jìn)一步使用已經(jīng)獲得定義的邏輯函數(shù)來考察C2組的表達(dá)能力：

[19]C11pq=C2E1pqE2pq

[20]C14pq=C2E1pqE3pq

[21]C4pq=C2E1pqE4pq

[22]C1pq=C2E1pqE5pq

[23]C10pq=C2E1pqE6pq

[24]C20pq=C2E2pqE3pq

[25]C10pq=C2E2pqE4pq

[26]C16pq=C2E2pqE5pq

[27]C25pq=C2E2pqE6pq

[28]C13pq=C2E3pqE4pq

[29]C10pq=C2E3pqE5pq

[30]C19pq=C2E3pqE6pq

[31]C1pq=C2E4pqE5pq

[32]C10pq=C2E4pqE6pq

[33]C16pq=C2E5pqE6pq

更為關(guān)鍵的是，由[23][25][29][30]和[32]可以看出C2組可以定義出Sheffer函數(shù)C10和C19，因此可以得出C2、C9、C17、D10、D15和D21都是Sheffer函數(shù)。

[34]F1pq=C3D13pqD19pq

[35]C6pq=C3F1pqF1pq

[36]F2pq=C3D13pqD24pq

[37]C2pq=C3F2pqF2pq

[38]F3pq=C3D19pqD24pq

[39]C14pq=C3F3pqF3pq

更為關(guān)鍵的是，由[37]可以看出C3組可以定義出Sheffer函數(shù)C2，因此可以得出C3、C11、C18、D13、D19和D24都是Sheffer函數(shù)。

[40]G1pq=C4D2pqD9pq

[41]C26pq=C4G1pqG1pq

[42]G2pq=C4D2pqD17pq

[43]C16pq=C4G2pqG2pq

[44]G3pq=C4D9pqD17pq

[45]C14pq=C4G3pqG3pq

下面進(jìn)一步使用已經(jīng)獲得定義的邏輯函數(shù)來考察C4組的表達(dá)能力：

[46]C8pq=C4G1pqG2pq

[47]C2pq=C4G1pqG3pq

[48]C11pq=C4G2pqG3pq

[49]H1pq=C5D3pqD11pq

[50]C18pq=C5H1pqH1pq

[51]H2pq=C5D3pqD18pq

[52]C17pq=C5H2pqH2pq

[53]H3pq=C5D11pqD18pq

[54]C9pq=C5H3pqH3pq

由[50][52]和[54]可以看出C5組可以定義出Sheffer函數(shù)C9、C17和C18，因此可以得出C5、C7、C26、D3、D11和D18都是Sheffer函數(shù)。

[55]J1pq=C6D6pqD16pq

[56]C12pq=C6J1pqJ1pq

[57]J2pq=C6D6pqD22pq

[58]C21pq=C6J2pqJ2pq

由[58]可以看出C6組可以定義出Sheffer函數(shù)C21，因此可以得出C6、C16、C20、D6、D16和D20都是Sheffer函數(shù)。

[59]0=C1C1pqD14pq

[60]M1pq=C1p0

[61]M2pq=C10p

[62]M3pq=C1M1pqM2pq

[63]M4pq=D14D14pqD14pq

[64]M5pq=D14M3pqM3pq

[65]D2pq=C1M4pqM5pq

而前文已經(jīng)證明D2是Sheffer函數(shù)，因此可以得出C1、C14、C27、D1、D14和D27都是Sheffer函數(shù)。

三、幾個主要結(jié)論

定理1333型中的C8組、C12組和C22組，即C8、C12、C22、D8、D12和D22均不是Sheffer函數(shù)。

下面予以證明。

由C8的真值表不難驗證：

ΘΘC8pq=C8ΘΘpΘΘq

ΘΘC12pq=C12ΘΘpΘΘq

ΘΘC22pq=C22ΘΘpΘΘq*Θ的定義見杜國平：《三值邏輯Sheffer函數(shù)》，載《哲學(xué)動態(tài)(邏輯學(xué)研究專輯)》2005年。

由此可見，C8、C12和C22是自對偶函數(shù)。*朱梧槚、肖奚安：《數(shù)理邏輯引論》，第51—62頁，大連理工大學(xué)出版社2008年版。所以，C8、C12和C22不是Sheffer函數(shù)。

由此可得：D8、D12和D22也均不是Sheffer函數(shù)。

定理2上述54個3值2元邏輯函數(shù)均可以定義出3值1元邏輯函數(shù)Θ。

下面予以證明。

Θp=edfCiCippCipp(i=1,…,27)

Θp=edfDipp(i=1,…,27)

前述我們研究的54個函數(shù)都是其真值表中的變元具有可交換性的3值2元函數(shù)，那么是否存在其真值表中的變元不具有可交換性的3值2元Sheffer函數(shù)呢？答案是肯定的。

定理3除上述48個Sheffer函數(shù)外，還存在其他3值2元Sheffer函數(shù)。

下面予以證明。

可以定義出函數(shù)D11：

因為：

下面予以證明。

容易驗證：

類似地有：

下面予以證明。

容易驗證：

下面予以證明。

容易驗證：

下面予以證明。

容易驗證：

下面予以證明。

容易驗證：

下面予以證明。

容易驗證：

按照如上方法，我們還可以進(jìn)一步得出其他類Ci和類DiSheffer函數(shù)。

【責(zé)任編輯：趙小華】

【基金項目】國家社會科學(xué)基金重點項目“提高國民邏輯素質(zhì)的理論和實踐探索研究”(13AZX019);國家社會科學(xué)基金重大招標(biāo)項目“應(yīng)用邏輯與邏輯應(yīng)用研究”(14ZDB014)

【收稿日期】2015-10-29

【中圖分類號】B81-0

【文獻(xiàn)標(biāo)識碼】A

【文章編號】1000-5455(2016)01-0169-07

(作者簡介:杜國平，江蘇盱眙人，中國社會科學(xué)院哲學(xué)研究所教授、博士生導(dǎo)師。)