許格妮, 李永明, 張 云

(1.陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 西安 710062; 2.西安財經(jīng)學(xué)院 統(tǒng)計學(xué)院, 西安 710100)

半環(huán)誘導(dǎo)賦值代數(shù)的輪廓解

許格妮1,2, 李永明1, 張 云2

(1.陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 西安 710062; 2.西安財經(jīng)學(xué)院 統(tǒng)計學(xué)院, 西安 710100)

先對全序半環(huán)誘導(dǎo)的賦值代數(shù)的輪廓解性質(zhì)進行研究, 再在全序半環(huán)誘導(dǎo)的賦值代數(shù)中引入保輪廓解的概念, 并借助輪廓解的性質(zhì), 對轉(zhuǎn)移函數(shù)f保全序半環(huán)誘導(dǎo)的賦值代數(shù)的輪廓解問題進行研究.結(jié)果表明, 若轉(zhuǎn)移函數(shù)f是一個半環(huán)同態(tài), 則f是保輪廓解的.

賦值代數(shù); 半環(huán); 輪廓解; 轉(zhuǎn)移函數(shù)

0 引 言

賦值代數(shù)是從人工智能領(lǐng)域中包括約束系統(tǒng)、信任函數(shù)系統(tǒng)、數(shù)據(jù)庫理論等抽象出來的用于描述信息處理方式的一種特殊代數(shù)結(jié)構(gòu)模型, Kohlas[1]對其進行了明確、完整的表達(dá).在一個賦值代數(shù)系統(tǒng)中, 系統(tǒng)通過對變量的賦值表達(dá)知識和信息, 并通過聯(lián)合運算對信息進行合成, 通過投影運算得到在指定變量集上的相關(guān)信息, 從而完成信息的提取.賦值代數(shù)是非確定情形下知識表示和推理的重要工具.

局部計算是賦值代數(shù)的一個核心內(nèi)容, 目前已有很多研究結(jié)果[2-6].在半環(huán)所誘導(dǎo)的賦值代數(shù)中, 投影運算可轉(zhuǎn)化為求和運算.特別地, 在全序半環(huán)誘導(dǎo)的賦值代數(shù)中, 求和運算即為求最大值運算.因此, 對于全序半環(huán)賦值φ∈Φ, 當(dāng)投影到空集時, 滿足等式φ(x)=φ↓?(◇)的x即為使得φ取最大值的輪廓,φ↓?(◇)即為該賦值的最大值.基于此, 文獻(xiàn)[3]在全序半環(huán)所誘導(dǎo)的賦值代數(shù)中提出了輪廓解的概念, 并給出了尋求輪廓解的一種算法; 文獻(xiàn)[7-8]對輪廓解的性質(zhì)進行了初步探討.本文在此基礎(chǔ)上對輪廓解的一些性質(zhì)及其與擴展解之間的關(guān)系進行進一步研究, 并對輪廓解的求法提出一種新思想： 當(dāng)直接尋求一個賦值的輪廓解存在困難時, 可以將其轉(zhuǎn)移到新系統(tǒng)的一個賦值上, 通過求解新賦值的輪廓解獲得原問題的信息, 從而給出了在全序半環(huán)誘導(dǎo)的賦值代數(shù)中轉(zhuǎn)移函數(shù)保輪廓解的判別方法.

1 預(yù)備知識

一般可通過對變量賦值傳達(dá)知識或信息, 本文將該賦值用φ,ψ…表示, 用Φ,Ψ…表示由這些賦值構(gòu)成的集合.

定義1[1]設(shè)(Φ,D)是一個具有如下3種運算的二元組, 其中(D,∨,∧)是一個格：

1) 論域運算：Φ→D;φ→d(φ);

2) 聯(lián)合運算：Φ×Φ→Φ; (φ,ψ)→φ?ψ;

3) 投影運算：Φ×D→Φ; (φ,T)→φ↓T.

若系統(tǒng)(Φ,D)滿足如下公理, 則稱其為一個帶標(biāo)記的賦值代數(shù)：

1) 半群律：Φ關(guān)于聯(lián)合運算滿足交換律與結(jié)合律, 且有單位元;

2) 論域律： 若?φ,ψ∈Φ, 則有d(φ?ψ)=d(φ)∨d(ψ);

3) 邊緣化律： ?φ∈Φ,T∈D, 若T≤d(φ), 則有d(φ↓T)=T;

4) 傳遞律： 若?φ∈Φ,T≤S≤d(φ), 則(φ↓S)↓T=φ↓T;

5) 聯(lián)合律： ?φ,ψ∈Φ, 若d(φ)=S,d(ψ)=T, 則有(φ?ψ)↓S=φ?ψ↓S∧T;

6) 單位元律： ?S,T∈D, 有eS?eT=eS∨T.

例1設(shè)A是一組屬性集, 對任意一個屬性α∈A, 用非空集Uα表示α可能的取值.設(shè)x∈A, 若?α∈x, 有f(α)∈Uα, 則稱定義域為x的函數(shù)f是一個x元組.符號Ex表示所有x元組構(gòu)成的集合.若R?Ex, 則稱R為x上的一個關(guān)系,x稱為這個關(guān)系的域, 記d(R)=x.

1) 對于x,y上的兩個關(guān)系R,S, 它們的聯(lián)合定義域是x∪y上的關(guān)系, 滿足：

R??S={f:f∈Ex∪y,f[x]∈R,f[y]∈S},

其中f[x]表示x元組f在x上的投影.

2) 對于x上的一個關(guān)系R, 若y?x, 則定義關(guān)系R在y上的投影為πy(R)={f[y]:f∈R}.

給定一個屬性集A, 記R為由該屬性集子集上所有關(guān)系構(gòu)成的集合, 則由文獻(xiàn)[1]知, 系統(tǒng)(R,A)在上述定義的標(biāo)記運算、聯(lián)合運算及投影運算下構(gòu)成一個賦值代數(shù).

定義2[2]設(shè)非空集合L上有兩個二元運算+,×, 且元素0,1∈L, 若下列條件成立, 則稱(L,+,×,0,1)是一個半環(huán):

1) 加法和乘法均滿足交換律和結(jié)合律；

2) 乘法在加法上滿足分配律；

3) ?a∈L, 有a+0=a,a×0=0, 0稱為L的零元；

4) ?a∈L, 有a×1=a, 1稱為單位元.

在半環(huán)L上定義關(guān)系：a≤b?a+b=b, 由文獻(xiàn)[2]知, 若在L上定義的該序關(guān)系是全序, 則?a,a′,b,b′∈L, 有:

1)a+b=max{a,b};

2) 若a≤b,a′≤b′, 則a+a′≤b+b′,a×a′≤b×b′.

令D=P(r), 在(Φ,D)上定義如下運算：

1) 聯(lián)合運算： ?φ∈ΦS,ψ∈ΦT及x∈ΩS∪T, 定義φ?ψ(x)=φ(x↓S)ψ(x↓T);

文獻(xiàn)[2]已證明： 該系統(tǒng)在上述運算下構(gòu)成一個賦值代數(shù), 稱其為由半環(huán)L誘導(dǎo)的賦值代數(shù).

2 半環(huán)誘導(dǎo)賦值代數(shù)輪廓解的性質(zhì)

在全序半環(huán)所誘導(dǎo)的賦值代數(shù)中,φ↓?(◇)=max{φ(x):x∈Ωd(φ)}, 則滿足φ(x)=φ↓?(◇)的x即為φ取最大值的輪廓, 而對應(yīng)的φ(x)即為φ的最大值.為考察一個賦值φ對應(yīng)的這樣解的情況, 文獻(xiàn)[3]在全序半環(huán)所誘導(dǎo)的賦值代數(shù)中引入了輪廓解與擴展解的概念, 并對其性質(zhì)進行了研究.本文在這些工作的基礎(chǔ)上對全序半環(huán)所誘導(dǎo)賦值代數(shù)輪廓解的性質(zhì)及其與擴展解的關(guān)系進行進一步研究.

定義3[3]設(shè)(Φ,D)是由全序半環(huán)所誘導(dǎo)的賦值代數(shù), 對于φ∈ΦS, 如果x∈ΩS滿足φ↓?(◇)=φ(x), 則稱x為φ的一個輪廓解,φ的全體輪廓解之集記為Cφ.

例2設(shè)L=({0,1,a,b},∨,∧,0,1)是四元鏈格, 其中0

φ:ΩS→L, (0,0)→1, (0,1)→1, (1,0)→a, (1,1)→b,

則Cφ={(0,0),(0,1)}.

注1特別地, 若S∩T=?時, 則有(x1,x2)∈Cφ?ψ.

定理1的逆命題未必成立, 如：

推論1設(shè)(Φ,D)是由全序半環(huán)所誘導(dǎo)的賦值代數(shù), 取φ∈Φ且φ=φ1?φ2?…?φn, 其中d(φi)=Si,i=1,2,…,n, 且當(dāng)i≠j時,Si∩Sj=?.如果xi∈Cφi, 則(x1,x2,…,xn)∈Cφ.

注2上述結(jié)論表明： 若φ=φ1?φ2?…?φn, 通過尋求賦值φi的輪廓解并不能完全得到φ的輪廓解, 但提供了尋求賦值輪廓解的一種方法.

即c∈Cφ↓S-T.

定理2的逆命題未必成立, 如：

定理3[4]設(shè)(Φ,D)是由全序半環(huán)所誘導(dǎo)的賦值代數(shù), 若d(φ)=S,d(ψ)=T, 且S∩T?U?S∪T, 則有(φ?ψ)↓U=φ↓S∩U?ψ↓T∩U.

φ(x↓U∩S,c1)×ψ(x↓U∩T,c2)=φ↓U∩S(x↓U∩S)×ψ↓U∩T(x↓U∩S),

因此有

3 半環(huán)誘導(dǎo)賦值代數(shù)的保輪廓解

定義5設(shè)f:L→L′是兩個全序半環(huán)間的一個映射, (Φ,D)與(Ψ,D)分別為半環(huán)L,L′誘導(dǎo)所得的賦值代數(shù), 對于Φ中的任一賦值φ:Ωs→L, 有復(fù)合映射fφ:Ωs→L′, 顯然fφ∈Ψ.因此, 稱映射f為Φ的轉(zhuǎn)移映射.

定義6設(shè)f:L→L′是兩個全序半環(huán)間的一個映射, (Φ,D)是由半環(huán)L誘導(dǎo)的賦值代數(shù), 如果f滿足?φ∈Φ, 有Cφ?Cfφ, 則稱f是保輪廓解的.

定義7[5]設(shè)f是兩個半環(huán)(L,+,×,0,1)與(L′,+,×,0,1)間的一個映射, 若f滿足:

1)f(0)=0,f(1)=1;

2)f(a+b)=f(a)+f(b);

3)f(a×b)=f(a)×f(b).

則稱f是一個半環(huán)同態(tài).

引理1設(shè)(Φ,D)是由全序半環(huán)L所誘導(dǎo)的賦值代數(shù),f是兩個全序半環(huán)L,L′間的一個映射, 即f:L→L′, 且有f(0)=0,f(1)=1, 若對任意的正整數(shù)m,n, 有

則f是一個半環(huán)同態(tài), 其中?uij,vij∈L,i=1,2,…,n;j=1,2,…,m.

證明: 若式(1)成立, 則f是單調(diào)的.事實上, 在式(1)中, 令m=n=1即可得.

下證?a,b∈L, 有f(a)+f(b)=f(a+b).由f單調(diào)可得,f(a)+f(b)≤f(a+b).假設(shè)f(a)+f(b)

再證f(ab)=f(a)(b).假設(shè)f(ab)≠f(a)f(b), 則有f(a)f(b)

綜上可知,f是一個半環(huán)同態(tài).

定理5設(shè)(Φ,D)是由全序半環(huán)L所誘導(dǎo)的賦值代數(shù),f是兩個全序半環(huán)L,L′間的一個映射, 且有f(0)=0,f(1)=1, 若式(1)成立, 則f是保輪廓解的.

由引理1知,f是一個半環(huán)同態(tài), 因此有

因此有

定理5給出了轉(zhuǎn)移函數(shù)f保輪廓解的一個判別條件, 但有時驗證式(1)是否成立較麻煩, 下面給出定理5的另一種表示形式.

引理2設(shè)(Φ,D)是由全序半環(huán)L所誘導(dǎo)的賦值代數(shù),f是兩個全序半環(huán)S,S′間的一個映射, 即f:L→L′, 且有f(0)=0,f(1)=1, 則f是一個半環(huán)同態(tài)當(dāng)且僅當(dāng)式(1)成立.

證明: 由引理1知, 僅證必要性即可.若f是一個半環(huán)同態(tài), 則f是單調(diào)的.事實上, ?a,b∈S, 若a≤b, 則有f(a)+f(b)=f(a+b)=f(b), 因此f(a)≤f(b).

由f是一個半環(huán)同態(tài)可得

因此, 式(1)成立.

綜上, 可得：

定理6設(shè)(Φ,D)是由全序半環(huán)L所誘導(dǎo)的賦值代數(shù),f是兩個全序半環(huán)L,L′間的一個映射, 且有f(0)=0,f(1)=1, 若f是一個半環(huán)同態(tài), 則f保輪廓解.

當(dāng)直接尋求某個賦值φ的輪廓解存在困難時, 可借助定理6, 通過一個半環(huán)同態(tài)映射f將其轉(zhuǎn)移到一個結(jié)構(gòu)較簡單的、新的賦值代數(shù)系統(tǒng)中, 通過給出fφ的輪廓解解決原問題.

例5近期某類動物有一種疾病, 醫(yī)務(wù)專家對此不能確診, 但憑借多年醫(yī)學(xué)經(jīng)驗一致認(rèn)為服用三唑核苷、氧氟沙星、阿奇霉素或胸腺素這4種藥有助于該疾病的好轉(zhuǎn).多名醫(yī)務(wù)專家對該類動物按不同組合服用這幾種藥物給出評價, 結(jié)果列于表1, 其中:x1,x2,x3,x4依次表示上述4種藥物, 若服用藥物xi, 則取xi=1, 否則取xi=0(i=1,2,3,4);φ表示是否服用各藥物與醫(yī)務(wù)專家給出分值之間的對應(yīng)關(guān)系.求最佳服用方案.

表1 藥物服用情況分值結(jié)果Table 1 Score results about taking medicine

上述問題求最佳方案實際上是找φ的輪廓解, 為了找出φ的輪廓解, 需要在所有φ(x1,x2,x3,x4)中搜索出使φ取最大值的輪廓.當(dāng)φ取值較多時, 用逐一搜索法找出其輪廓解顯然較麻煩, 但借助定理6可縮小搜索范圍, 從而減少了運算量.

假設(shè)L1={[0,100],∨,∧,0,100}, 則上述φ可視為由全序半環(huán)L1所誘導(dǎo)的賦值代數(shù)(Φ,D)中的一個賦值, 其中Φ={f:ΩT→L1},T={x1,x2,x3,x4},D=P({x1,x2,x3,x4})是{x1,x2,x3,x4}的冪集.令L2={{0,a,b,1},∨,∧,0,1}, 其中0

表2 復(fù)合映射fφTable 2 Composite mapping fφ

由表2知Cα·φ={(0110),(1100),(0111)}, 則由定理6, 只需在Cα·φ中搜尋φ的輪廓解即可：φ(0110)=90,φ(1100)=90,φ(0111)=95, 因此Cφ={0111}, 即服用氧氟沙星、阿奇霉素和胸腺素為最佳方案.

[1]Kohlas J.Information Algebras: Generic Structures for Inference [M].London: Springer-Verlag, 2003.

[2]Kohlas J, Wilson N.Semiring Induced Valuation Algebras: Exact and Approximate Local Computation Algorithms [J].Artif Intell, 2008, 172(11): 1360-1399.

[3]Pouly M.A Generic Framework for Local Computation [D].Fribourg, Switzerland: University of Fribourg, 2008.

[4]韓邦合.賦值代數(shù)分裂算法與隱性半環(huán)賦值研究 [D].西安： 陜西師范大學(xué), 2011.(HAN Banghe.The Splitting Algorithm of Valuation Algebra and Implicit Valuation over a Semiring [D].Xi’an: Shaanxi Normal University, 2011.)

[5]LI Sanjiang, YING Mingsheng.Soft Constraint Abstraction Based on Semiring Homomorphism [J].Theoretical Computer Science, 2008, 403(2/3): 192-201.

[6]GUAN Xuechong, LI Yongming.On a Condition for Semirings to Induce Compact Information Algebras [J].Electronic Notes in Theoretical Computer Science, 2014, 301: 39-48.

[7]Kohlas J.Lecture Notes on the Algebraic Theory of Information [R/OL].2010-11-24.http://diuf.unifr.ch/drupal/tns/sites/diuf.unifr.ch.drupal.tns/files/file/kohlas/main.pdf.

[8]管雪沖.賦值代數(shù)中若干問題的研究 [D].西安: 陜西師范大學(xué), 2011.(GUAN Xuechong.The Study of Some Questions about Valuation Algebra [D].Xi’an: Shaanxi Normal University, 2011.)

SolutionConfigurationofSemiringValuationAlgebra

XU Geni1,2, LI Yongming1, ZHANG Yun2
(1.CollegeofMathematicsandInformationScience,ShaanxiNormalUniversity,Xi’an710062,China;
2.CollegeofStatistics,Xi’anUniversityofFinanceandEconomics,Xi’an710100,China)

The properties of the solution configuration of valuation algebra over a totally ordered semiring were discussed.Furthermore, the concept of preserving the solution configuration of valuation algebra over a totally ordered semiring was given.With the help of the properties of the solution configuration, the question of the transfer functionfpreserving solution configuration was studied.It is concluded that the transfer functionfpreserves solution configuration iffis a semiring homomorphism.

valuation algebra; semiring; solution configuration; transfer function

2014-03-12.

許格妮(1978—), 女, 漢族, 博士研究生, 講師, 從事計算智能、信息代數(shù)與不確定推理的研究, E-mail: geniwork@163.com.通信作者： 李永明(1966—), 男, 漢族, 博士, 教授, 博士生導(dǎo)師, 從事計算智能、量子邏輯和量子計算的研究, E-mail: liyongm@snnu.edu.cn.

國家自然科學(xué)基金(批準(zhǔn)號: 11271237; 61228305)和西安財經(jīng)學(xué)院科研基金(批準(zhǔn)號: 12JD04).

O141

A

1671-5489(2014)06-1119-06

10.13413/j.cnki.jdxblxb.2014.06.03

趙立芹)