龔志偉

(中南林業(yè)科技大學理學院,湖南 長沙 410004)

部分多值邏輯的準完備集中同源關系的研究*

龔志偉

(中南林業(yè)科技大學理學院,湖南 長沙 410004)

通過研究準完備集之間存在的內在聯(lián)系，首次提出了兩個m項關系同源的概念，然后分析并證明了保同源關系的準完備集之間的性質，最后闡述了此性質在準完備集之最小覆蓋的證明過程中所發(fā)揮的作用。

多值邏輯；準完備集；最小覆蓋；同源關系

1 引言

多值邏輯是指一切邏輯值的取值數(shù)大于2的邏輯，它是由二值邏輯擴展而來的。經(jīng)典的二值邏輯只有兩個狀態(tài)，即“真”和“假”，任何命題“非真即假”，二者必居其一，即排中律成立。然而，客觀世界的事物是十分復雜的，有些事物在某些情況下不是二值邏輯所能完全描述的。于是，便產(chǎn)生了多值邏輯。目前領域中主要使用的是二值邏輯，但三值、四值以及更高值的邏輯也已逐漸得到應用，并且正越來越多地滲透到計算機領域的許多分支中，顯示著強大的生命力。

多值邏輯的思想是19世紀蘇格蘭學者MacColl首先提出的，但作為正式邏輯系統(tǒng)，則是由波蘭邏輯學家Lukasiewicz J和美國數(shù)學家Post E L

分別于1920年和1921年各自提出的。在我國,多值邏輯的研究已有較長的歷史，王湘浩院士一直致力于多值邏輯函數(shù)結構理論的研究。其中函數(shù)系完備性之判定問題是一個基本而重要的問題，同時也是自動機理論、多值邏輯網(wǎng)絡中必須解決的問題，此問題的解決依賴于定出多值邏輯函數(shù)集中的所有準完備集。

2 基本概念

3 主要結論

3.1 同源關系

定義8若在m項關系Gm中，存在一個元素〈a1,…,am〉，對于Gm中的任意元素〈b1,…,bm〉，都存在變換σ，σ∈Sm(Sm是m次對稱群)，使得σ(〈a1,…,am〉)=〈b1,…,bm〉，則稱此關系Gm為元素〈a1,…,am〉的生成關系，稱元素〈a1,…,am〉是Gm的生成元。

3.2 保同源關系的準完備集之間的性質

□

3.3 同源關系的作用舉例

為了證明關系G2={〈0,0〉,〈1,1〉,〈2,2〉,〈3,3〉,〈0,1〉}所確定的準完備集是最小覆蓋成員，我們構造函數(shù)f(x,y,z)，令：

再證f(x,y,z)不屬于其它270個準完備集。

在這270個集合中，有：

H1={e,(12)(34)}

H2={e,(13)(24)}

H3={e,(14)(23)}

H4={e,(12)(34),(13)(24),(14)(23)}

H5={e,(12),(34),(12)(34)}

H6={e,(13),(24),(13)(24)}

H7={e,(14),(23),(14)(23)}

H8={e,(12),(34),(12)(34),(13)(24),(14)(23),(1324),(1423)}

H9={e,(13),(24),(12)(34),(13)(24),(14)(23),(1234),(1432)}

H10={e,(14),(32),(12)(34),(13)(24),(14)(23),(1243),(1342)}

H11={e,(123),(124),(132),(134),(142),(143),(234),(243),(12)(34),(13)(24),(14)(23)}

H12=S4

a當R1={1,2},R2={3,4}時，G4=G4(R1，R2)的對稱群有10個，分別為：

H1={(1)}

H2={(1),(12)}

H3={(1),(34)}

H4={(1),(12)(34)}

H5={(1),(13)(24)}

H6={(1),(14)(23)}

H7={(1),(12)(34),(13)(24),(14)(23)}

H8={(1),(1324),(1423),(12)(34)}

H9={(1),(12),(34),(12)(34)}

H10={(1),(12),(34),(12)(34),(13)(24),(14)(23),(1324),(1423)}

b當R1={1,2，3,4}時,G4={〈i,i,i,i〉|i=0,1,2,3.},它的對稱群有12個:

H1={e,(12)(34)}

H2={e,(13)(24)}

H3={e,(14)(23)}

H4={e,(12)(34),(13)(24),(14)(23)}

H5={e,(1234),(1423),(13)(24)}

H6={e,(1243),(1342),(14)(23)}

H7={e,(1324),(1423),(12)(34)}

H8={e,(12),(34),(12)(34),(13)(24),(14)(23),(1324),(1423)}

H9={e,(13),(24),(12)(34),(13)(24),(14)(23),(1234),(1432)}

H10={e,(14),(32),(12)(34),(13)(24),(14)(23),(1243),(1342)}

H11={e,(123),(124),(132),(134),(142),(143),(234),(243),(12)(34),(13)(24),(14)(23)}

H12=S4

下面證明f不屬于這些T(G4)：

3.4 相似與同源的比較

相似和同源是從兩個不同的角度來描述兩個m項關系之間的關聯(lián)。

4 結束語

[1]LuoZhu-kai.Thecompletenesstheoryofpartialmultiple-valuedlogic[J].MathematicsJournals, 1984,27(5):676-683.(inChinese)

[2]WangXiang-hao.Structuretheoryoftotalandpartialtunctionsdefinedinafiniteset[J].JournalofJilinUniversity(ScienceEdition), 1963(2):295-315.(inChinese)

[3]LiuRen-ren,ChenJian-er,ChenSong-qiao.ThedecisiononShefferfunctionsinpartialtwo-valuedlogic[J].ComputerEngineering, 2004,30(24):19-21.(inChinese)

[4]LiuRen-ren.Theminimalcoveringofpre-completesetsinpartialtree-valuedlogic[J].XiangtanUniversityNaturalScienceJournal,1991,13(2):158-164.(inChinese)

[5]LiuRen-ren.DecisionandconstructionoftheShefferfunctionsinpartialfour-valuedlogic[J].ComputerEngineering&Science, 2008,25(11):75-76.(inChinese)

[6]LuoZhu-kai,HuMou,ChenTing-huai.Multi-valuedlogictheoryandapplication[M].Beijing:SciencePress, 1992.(inChinese)

[7]LiuRen-ren,ChenSong-qiao,ChenJian-er,etal.SomeresultsontheminimalcoveringsofprecompleteclassesinpartialK-valuedlogicfunctions[C]∥Procof2003IEEEInternationalConferenceonSystems,Man&Cybernetics,2003:2645-2650.

[8]LiuRen-ren,WangTing,ChenJian-er,etal.SomeresultsonthesimplyseparablefunctionsetsinpartialK-valuedlogicfunctions[C]∥Procof2004IEEEInternationalConferenceonSystems,Man&Cybernetics,2004:1238-1242.

[9]GongZhi-wei.Thedecisionontheminimalcoveringoffunctionsetspreservingbinaryregularlyseparablerelationsinpartialfour-valuedlogic[D].Xiangtan:XiangtanUniversity, 2006.(inChinese)

[10] Gong Zhi-wei,Liu Ren-ren. Minimal covering for precomplete sets in partial four-valued logic[J]. Computer Engineering and Applications, 2012,48(23)：52-57.(in Chinese)

[11] Xu Fen. The decision on the minimal covering of simply separable function sets in partial four-valued logic[J]. Journal of Hainan Normal University, 2006,19(3):222-224.(in Chinese)

[12] Zhou Xiao-qiang, Liu Ren-ren. Decision on minimal covering of preserving quaternary regularly separable relations in partial four-valued logic[J]. Computer Science, 2009,46(9):176-177.(in Chinese)

附中文參考文獻：

[1] 羅鑄楷. 部分多值邏輯函數(shù)集的完備性理論[J].數(shù)學學報，1984,27(5)：676-683.

[2] 王湘浩. 有限集合上缺值及不缺值函數(shù)的結構理論[J].吉林大學自然科學學報, 1963(2):295-315.

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

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

[5] 劉任任. 部分四值邏輯中Sheffer函數(shù)的判定與構造[J].計算機工程與科學，2008,25(11)：75-76.

[6] 羅鑄楷，胡謀，陳廷槐. 多值邏輯的理論及應用[M]. 北京：科學出版社，1992.

[9] 龔志偉. 部分四值邏輯中保二元正則可離關系函數(shù)集最小覆蓋之判定 [D].湘潭：湘潭大學，2006.

[10] 龔志偉，劉任任. 部分四值邏輯中準完備集的最小覆蓋[J]. 計算機工程與應用，2012,48(23)：52-57.

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

GONGZhi-wei,born in 1980,MS,lecturer,CCF member(E200024067M),her research interest includes multiple-valued logic.

Studyonhomologousrelationshipintheprecompletesetsofpartialmultiple-valuedlogic

GONG Zhi-wei

(College of Science,Central South University of Forestry and Technology,Changsha 410004,China)

By studying the inner link amongst precomplete sets, a homologous concept between two m-ary relationship is proposed firstly. Secondly, the property of the homologous relationship among precomplete sets is analyzed and proved. Finally, the effect of this property in the proof of the minimal covering of precomplete sets is introduced.

multiple-valued logic；precomplete sets；minimal covering；homologous relationship

1007-130X(2014)08-1533-05

2012-08-27;

：2013-01-20

國家自然科學基金資助項目(60673193)

TP301.1

：A

10.3969/j.issn.1007-130X.2014.08.019

龔志偉(1980-),女,湖南益陽人，碩士，講師，CCF會員(E200024067M)，研究方向為多值邏輯。E-mail:419366729@qq.com

通信地址：410004 湖南省長沙市中南林業(yè)科技大學理學院

Address:College of Science,Central South University of Forestry and Technology,Changsha 410004,Hunan,P.R.China