龔志偉

(中南林業(yè)科技大學(xué)理學(xué)院,湖南 長(zhǎng)沙 410004)

部分多值邏輯的準(zhǔn)完備集中同源關(guān)系的研究*

龔志偉

(中南林業(yè)科技大學(xué)理學(xué)院,湖南 長(zhǎng)沙 410004)

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

多值邏輯；準(zhǔn)完備集；最小覆蓋；同源關(guān)系

1 引言

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

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

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

2 基本概念

3 主要結(jié)論

3.1 同源關(guān)系

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

3.2 保同源關(guān)系的準(zhǔn)完備集之間的性質(zhì)

□

3.3 同源關(guān)系的作用舉例

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

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

在這270個(gè)集合中，有：

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當(dāng)R1={1,2},R2={3,4}時(shí)，G4=G4(R1，R2)的對(duì)稱群有10個(gè)，分別為：

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當(dāng)R1={1,2，3,4}時(shí),G4={〈i,i,i,i〉|i=0,1,2,3.},它的對(duì)稱群有12個(gè):

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 相似與同源的比較

相似和同源是從兩個(gè)不同的角度來(lái)描述兩個(gè)m項(xiàng)關(guān)系之間的關(guān)聯(lián)。

4 結(jié)束語(yǔ)

[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)

附中文參考文獻(xiàn)：

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

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

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

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

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

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

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

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

[11] 許芬.部分四值邏輯單純可離函數(shù)集最小覆蓋之判定[J].海南師范學(xué)院學(xué)報(bào),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

國(guó)家自然科學(xué)基金資助項(xiàng)目(60673193)

TP301.1

：A

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

龔志偉(1980-),女,湖南益陽(yáng)人，碩士，講師，CCF會(huì)員(E200024067M)，研究方向?yàn)槎嘀颠壿?。E-mail:419366729@qq.com

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

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