部分多值逻辑的准完备集中同源关系的研究*

龚志伟

(中南林业科技大学理学院,湖南 长沙 410004)

部分多值逻辑的准完备集中同源关系的研究*

龚志伟

(中南林业科技大学理学院,湖南 长沙 410004)

通过研究准完备集之间存在的内在联系，首次提出了两个m项关系同源的概念，然后分析并证明了保同源关系的准完备集之间的性质，最后阐述了此性质在准完备集之最小覆盖的证明过程中所发挥的作用。

多值逻辑；准完备集；最小覆盖；同源关系

1 引言

多值逻辑是指一切逻辑值的取值数大于2的逻辑，它是由二值逻辑扩展而来的。经典的二值逻辑只有两个状态，即“真”和“假”，任何命题“非真即假”，二者必居其一，即排中律成立。然而，客观世界的事物是十分复杂的，有些事物在某些情况下不是二值逻辑所能完全描述的。于是，便产生了多值逻辑。目前领域中主要使用的是二值逻辑，但三值、四值以及更高值的逻辑也已逐渐得到应用，并且正越来越多地渗透到计算机领域的许多分支中，显示着强大的生命力。

多值逻辑的思想是19世纪苏格兰学者MacColl首先提出的，但作为正式逻辑系统，则是由波兰逻辑学家Lukasiewicz J和美国数学家Post E L

分别于1920年和1921年各自提出的。在我国,多值逻辑的研究已有较长的历史，王湘浩院士一直致力于多值逻辑函数结构理论的研究。其中函数系完备性之判定问题是一个基本而重要的问题，同时也是自动机理论、多值逻辑网络中必须解决的问题，此问题的解决依赖于定出多值逻辑函数集中的所有准完备集。

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〉}所确定的准完备集是最小覆盖成员，我们构造函数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项关系之间的关联。

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] 罗铸楷. 部分多值逻辑函数集的完备性理论[J].数学学报，1984,27(5)：676-683.

[2] 王湘浩. 有限集合上缺值及不缺值函数的结构理论[J].吉林大学自然科学学报, 1963(2):295-315.

[3] 刘任任，陈建二，陈松乔.部分二值逻辑中Sheffer函数的判定[J].计算机工程，2004,30(24)：19-21.

[4] 刘任任．部分三值逻辑中准完备集之最小覆盖[J]．湘潭大学自然科学学报，1991，13(2)，158-164.

[5] 刘任任. 部分四值逻辑中Sheffer函数的判定与构造[J].计算机工程与科学，2008,25(11)：75-76.

[6] 罗铸楷，胡谋，陈廷槐. 多值逻辑的理论及应用[M]. 北京：科学出版社，1992.

[9] 龚志伟. 部分四值逻辑中保二元正则可离关系函数集最小覆盖之判定 [D].湘潭：湘潭大学，2006.

[10] 龚志伟，刘任任. 部分四值逻辑中准完备集的最小覆盖[J]. 计算机工程与应用，2012,48(23)：52-57.

[11] 许芬.部分四值逻辑单纯可离函数集最小覆盖之判定[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 湖南省长沙市中南林业科技大学理学院

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