Ｐ４中保四元正則可離關系非最小覆蓋的剔除

摘 要：為確定部分四值邏輯的最小覆蓋，根據部分K值邏輯的完備性理論、正則可離關系以及準完備集之間的相似關系理論， 對部分四值邏輯的最小覆蓋進行分析，證明了109個保四元正則可離關系函數集中的67個函數集必不屬于部分四值邏輯中最小覆蓋的成員。

關鍵詞：多值邏輯; 完備性; 正則可離關系; 最小覆蓋

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695(2009)06-2090-02

doi:10.3969/j.issn.1001-3695.2009.06.026

Elimination of not belonging to minimal covering of preserving quaternaryregularly separable relations in partial four-valued logic

ZHOU Xiao-qiang1，LIU Ren-ren2

(1.Dept. of Mathematics， Hunan Institute of Science Technology，Yueyang Hunan 414006， China;2.College of Information Engineering， Xiangtan University， Xiangtan Hunan 411105， China)

Abstract:To determine the minimal covering in partial four-valued logic， according to the completeness theory in partial K-valued logic， regularly separable relation and the similar relationship theory among precomplete sets，analyzed the minimal covering in partial four-valued logic， and proved 67 sets of 109 preserving quaternary regularly separable relations function sets not belong to the minimal covering members in partial four-valued logic．

Key words:multi-valued logic; completeness; regularly separable relations; minimal covering

多值邏輯是計算機科學中的一個重要分支，隨著計算機科學與技術的不斷進步，多值邏輯得到了前所未有的發展，其研究內容主要包括理論、電路與系統、應用三個方面。在多值邏輯函數結構理論中， Sheffer 函數的判定與構造是一個非常重要的研究課題，其判定問題與函數集完備性的判定密切相關。完備性的判定可歸結為定出其中的所有準完備集，而Sheffer函數的構造又可歸結為定出準完備集的最小覆蓋。對于完全多值邏輯函數已由Kudrjavcev^[1]和羅鑄楷等人^[2]完全解決。對于部分多值邏輯， 羅鑄楷教授根據保關系的思想定出了部分多值邏輯中所有的準完備集(共七類)，徹底解決了函數集的完備性問題，但Sheffer函數的判定與構造問題尚未徹底解決， 即未定出所有準完備集的最小覆蓋，只取得了部分結果^[2~9]。對于其中的正則可離函數集，根據相似關系理論， 若某準完備集能被已確定的最小覆蓋成員之并所覆蓋，則它們在最小覆蓋中必不出現，即可以剔除。本文根據已確定的最小覆蓋成員^[2~4]， 對P4中正則可離函數集SR，m的499個準完備集進行分析，證明了m＝4時的67個準完備集在部分四值邏輯的最小覆蓋中必不出現。 

1 基本定義

設Ek={0，1，…，K-1}，K≥2，Ek上的完全和非完全K值邏輯函數統稱為部分多值邏輯函數，所有部分K值邏輯函數形成的集合記為Pk。

函數f(x1，…，xn)(∈PK)是一個Sheffer函數，如果f能疊合出PK中的所有函數。

令Σ={Ai|Ai(PK)是準完備集，i=1，…，n}且Σ′Σ，定義SΣ′={f∈PK|存在A′j∈Σ′使得f∈A′j，1≤j≤n}，即SΣ′表示PK中所有屬于Σ′中某個準完備集的函數之集合，也即 SΣ′=∪nj=1A′j，A′j∈Σ′，|Σ′|=n，j=1，…，n。

集合Σ′（Σ）是集合Σ的覆蓋，如果滿足SΣ′=SΣ。覆蓋Σ′是最小的，如果Σ′的任何一個真子集都不是集合Σ的覆蓋。

定義1 設Gm=Gm(R1，…，Rm)∪Gm，H是Gm(R1，…，Rm)的對稱群，Gm=m∪σ1m∪…∪σn-1m。其中R1={1，…，r1}，R2={r1+1，…，r2}，…，Rn={rn-1+1，…，rn}。

Gm是正則可離的， 如果存在Ek的一組直接分劃Di:Ek=A(i)1+…+A(i)m（i=1，…，n），使得對任意〈a1，…，am〉∈m， 必有一個具有下列性質的直接分劃Dh(1≤h≤n):ai∈A(h)i（i=1，…，m），且對任意的Dj（1≤j≤h-1）有

A(j)j1，…，A(j)jn(1≤j1，…，jn≤m)使a1，…，ar1∈A(j)j1，…，arn-1+1，…，arn∈A(j)jn。若Gm正則可離，則稱T(Gm)為保正則可離函數集， 并記為SR，m。

在上面定義中所提到的m都僅含m元不同的序列。子群H={e，σ1，…，σh-1}

Sm(或S4)。

定義2 關系Gm與G′m是相似的，如果|Gm|=|G′m|且存在一個雙射φ：Ek→Ek使得G′m={〈φ（a1），…，φ（am）〉|〈a1，…，am〉∈Gm}。

顯然，相似關系是一個等價關系，本文用Gm~G′m來表示Gm與G′m在雙射φ下相似。

2 主要結果及其證明

定理 部分四值邏輯中保四元正則可離關系G4的109個準完備集T（G4）中有67個必不屬于最小覆蓋的成員，按相似關系分為29類。其中，G4=G4(R)∪G4。根據R的取值分為三種情況：

a）當R={1，2}時，G4(R)=G4({1，2})={〈0，0，0，0〉，〈1，1，1，12，2，2，2〉，〈3，3，3，3〉，〈0，0，0，1〉，〈0，0，0，2〉，為如下5類：

其中：H1={e}，H2={e，(12)}，H3={e，(34)}，H4={e，(12)(34)}， H5={e，(12)，(34)，(12)(34)}是G4({1，2})的對稱子群。

b）當R={1，2，3}時，G4(R)={〈0，0，0，0〉，〈1，1，1，1〉，〈2，2，2，2〉，〈3，3，3，3〉，〈，0，0，0，1〉，〈0，0，0，2〉， 32)}是G4({1，2，3})的對稱子群。

c）當R={1，2，3，4}時，G4(R)={〈0，0，0，0〉，〈1，1，1，1〉，〈2，2，2，2〉，〈3，3，3，3〉}，18個G4分為18類：

{〈0，1，2，3〉}Hi；i=1，…，18

其中：H1={e}，H2={e，(12)}，H3={e，(13)}， H4={e，(14)}，H5={e，(23)}，H6={e，(24)}，H7={e，(34)}，H8={e，(123)，(132)}，H9={e，(124)，(142)}，H10={e，(134)，(143)}，H11={e，(234)，(243)}，H12={e，(12)，(13)，(123)，(132)}，H13={e，(12)，(14)，(124)，(142)}，H14={e，(13)，(14)，(134)，(143)}，H15={e，(23)，(24)，(234)，(243)}，H16={e，(12)，(34)，(12)(34) }，H17={e，(13)，(24)，(13)(24)}，H18={e，(14)，(23)，(14)(23) }是G4({1，2，3，4})的對稱子群。

證明 根據相似關系理論， 任何兩個相似的準完備集要么同屬于最小覆蓋， 要么同不屬于最小覆蓋，而相似關系又是一個等價關系。因此，只需從以上29類中各取其中一個（以下均取第一個）G4來證明保此關系的準完備集不屬于最小覆蓋即可。由于當R相同時，證明方法類似，下面只對R={1，2}，R={1，2，3}和R={1，2，3，4}分別取一類進行證明。

1)R={1，2}時的第一類 H1={e}， 即G4={〈0，1，2，3〉}。

設f∈T(G4)，G4=G4({1，2})∪G4，則f∈T(G2)。其中G2=G2({1，2})∪{〈0，1〉}。

反證法。設fT(G2)，則存在保G2的1、2使得〈f(α1)，f(α2)〉=〈a，b〉G2。顯然a≠b，而且i=(i1，…，in)中必有〈α1j，α2j〉=〈0，1〉（i=1，2）。令3=（2，…，2），4=（3，…，3），于是顯然有1、2、3、4保G4，但

f α11…α1j…α1n

α21…α2j…α2n

2…2…2

3…3…3=abik

容易驗證〈a，b，i，k〉G4（i，k=0，1，2，3）。這與f∈T(G4)矛盾，故f∈T(G2)。

由于G2=G2（{1，2}）∪{〈0，1〉}已證明是P4中的最小覆蓋成員^[3]，故可剔除。

2)R={1，2，3}時的第一類 H1={e}，即G4={〈0，1，2，3〉}。

設f∈T(G4)，G4=G4({1，2，3})∪G4，則f∈T{0}

∪T{1}∪T{2}∪T{3}∪T{G3}。其中G3={〈0，0，0〉，〈1，1，1〉，〈2，2，2〉，〈3，3，3〉，〈0，1，2〉}。這是因為：

a)若f(0~)=0或*，則f∈T{0}。

b)若f(0~)=1，則f(1~)=1或*，于是f∈T{1}。

c)若f(0~)=2，則f(1~)=f(2~)=2或*，于是f∈T{2}。

d)若f(0~)=3，則f(1~)=f(2~)=3，則f(3~)=0，1，2，3或*。若f(3~)=3或*，則f∈T{3}；若f(3~)=0，1或2，下證f∈T(G3)。其中G3=G3（{1，2，3}）∪{〈0，1，2〉}。

反證法。設fT(G3)，則存在保G3的1、2、3使得〈f(1)，f(2)，f(3)〉=〈a，b，c〉G3。顯然a≠b≠c，而且

i=(i1，…，in)中必有

〈α1j，α2j，α3j〉=〈0，1，2〉(i=1，2，3；1≤j≤n）。

令4=（3，…，3），于是顯然有1、2、3、4保G4，但

f α11…α1j…α1n

α21…α2j…α2n

α31…α3j…α3n

3…3…3=abci

容易驗證〈a，b，c，i〉G4（i=0，1或2）。這與f∈T(G4)矛盾，故f∈T(G3)。

對G3=G3({1，2，3}）∪{〈0，1，2〉}，已證得是P4中最小覆蓋成員^[3]，故此類準完備集也可以剔除。

3)R={1，2，3，4}時的第一類 H1={e}，即G4={〈0，1，2，3〉}。

設f∈T(G4)，G4=G4({1，2，3，4})∪G4，則f∈T{0}∪T{1}∪T{2}∪T{3}∈TE。這是因為：

a)若f(0~)=0或*，則f∈T{0}。

b)若f(0~)=1，則f（1~）=1或*，于是f∈T{1}。

c)若f(0~)=2，則f（1~）=2，從而f（2~）=2或*，于是f∈T{2}。

d)若f(0~)=3，則f（1~）=f（2~）=3，從而f(3~)=3或*，于是f∈T{3}。

T{0}∪T{1}∪T{2}∪T{3}∈TE已證得是P4中最小覆蓋成員^[2]，故此類準完備集也可以剔除。

3 結束語

至此，本文證明了m=4時正則可離關系函數集SR，4=T(G4)中的29類共67個準完備集能被若干最小覆蓋成員之并所覆蓋， 即它們都不屬于最小覆蓋成員，故它們都可以從最小覆蓋中剔除。此工作為解決部分四值邏輯的最小覆蓋奠定了良好的基礎，并為以后研究部分k(>4)值邏輯準完備集的最小覆蓋提供了很好的思路。

參考文獻：

［1］KUDRJAVCEV V B.The coverings of precomplete classes of K-valued logic[J].DiskretnyiAnaliz，1970，17(1):32-44.

[2]羅鑄楷.多值邏輯的理論及應用研究[M].長沙：國防科學技術大學出版社，2003.

[3]劉任任.部分三值邏輯中準完備集的最小覆蓋[J].湘潭大學自然科學學報，1991，13(2):158-164.

[4]許芬.部分四值邏輯單純可離函數集最小覆蓋之判定[J].海南師范學院學報，2006，19(3):222-224.

[5] LIU Ren-ren.Some results on the minimal coverings of precomplete classes in partial K-valued logic functions[J].Journal of Computer Science and Technology，2004，19(6):981-985.

[6]LIU Ren-ren.On the categorizing of simply separable relations in partial four-valuedlogic[C]//Proc of Advances in Natural Computation.[S.l.]:Springer-Verlag，2005:1251-1256.

[7]LIU Ren-ren.On the categorizing of fully symmetric relations in partial four-valued logic[C]//Proc of Advances in Natural Computation.[S.l.]:Springer-Verlag，2006:286-289.

[8]劉任任，陳建二，陳松喬.部分二值邏輯中Sheffer函數的判定[J].計算機工程，2004，30(24):19-21.

[9]劉玉珍，劉任任.部分K值邏輯中最小覆蓋之判定的一些結果[J].計算機工程與應用，2007，43(23):38-39.