格值直覺模糊有限自動機(jī)的直積與覆蓋

楊 莉, 莫智文

(四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院, 四川 成都 610066)

1965年,L. A. Zadeh[1]提出模糊集理論.隨后,在1967年W. G. Wee[2]引入了模糊自動機(jī)理論.J. N. Mordeson[3]等對模糊自動機(jī)的代數(shù)性質(zhì)做了詳細(xì)的研究.隨著模糊集理論的發(fā)展，1983年K. T. Atanassov[4]提出了直覺模糊集，它是一種高層次的模糊集，比一般的模糊集合多了一個(gè)非隸屬度，這就使得它在處理不確定信息時(shí)比傳統(tǒng)的模糊集有更強(qiáng)的靈活性和準(zhǔn)確性,K. T. Atanassov等[5]又在1984年提出了格值直覺模糊集，格值直覺模糊集理論是直覺模糊集理論的推廣.Y. B. Jun[6]于2005年提出了直覺模糊有限自動機(jī)的概念,不久Y. B. Jun[7-8]和X. W. Zhang等[9]對直覺模糊有限自動機(jī)的代數(shù)性質(zhì)做了詳細(xì)研究.在此基礎(chǔ)上，提出了格值直覺模糊有限自動機(jī)的定義，當(dāng)L=[0,1]時(shí)，格值直覺模糊有限自動機(jī)就為直覺模糊有限自動機(jī)，因此格值直覺模糊有限自動機(jī)是直覺模糊有限自動機(jī)的推廣.自動機(jī)的乘積在分解和覆蓋定理中起著很重要的作用，因此對自動機(jī)乘積的研究是必要的.文獻(xiàn)[10-15]建立了自動機(jī)的乘積理論.基于此，本文建立了格值直覺模糊有限自動機(jī)的直積理論，并得到了一些重要性質(zhì).

1 預(yù)備知識

特別地，完備格L一定有一最小元和最大元，即infL和supL，分別記為0和1.

定理1.1[17]在任意格L中，下述2個(gè)分配恒等式等價(jià)：

(D1)a∧(b∨c)=(a∧b)∨(a∧c),?a,b,c∈L;

(D2)a∨(b∧c)=(a∨b)∧(a∨c),?a,b,c∈L.

滿足分配恒等式D1(或D2)的格L叫做一個(gè)分配格.

定理1.2[17]在任意格(L,≤)中，對?a,b,c∈L有

(L1)a∧a=a,a∨a=a;(冪等律)

(L2)a∧b≤b∧a,a∨b≤b∨a;(交換律)

(L3)a∧(b∧c)≤(a∧b)∧c,a∨(b∨c)≤(a∨b)∨c;(結(jié)合律)

(L4)a∧(a∨b)=a=a∨(a∧b).(吸收律)

定理1.3[17]在任意格L中,交、并運(yùn)算是保序的，即對?a,b,c∈L，若a≤b，則a∧c≤b∧c,a∨c≤b∨c.

定義1.2[18]′:L→L是格L上的逆序?qū)蠈?yīng)，即對任意的a,b∈L，a≤b時(shí)有a′≥b′且a″=a.

若0,1分別是完備格L的最小元與最大元，則0′=1,1′=0.

定理1.4[18]設(shè)L是具有逆序?qū)蠈?yīng)的完備格，則De Morgan對偶律成立,即對{ai|i∈I}?L有

定義1.3[5]設(shè)X是一個(gè)非空集合，L是具有逆序?qū)蠈?yīng)的完備格，X上的一個(gè)格值直覺模糊集A定義為

A={〈x,μA(x),νA(x)〉|x∈X},

其中μA:X→L,νA:X→L，分別表示X上的元素x屬于A的隸屬度和非隸屬度，′:L→L且對?x∈X，滿足

μA(x)≤(νA(x))′.

格值直覺模糊集A可以簡記為A=(μA,νA).

2 格值直覺模糊有限自動機(jī)

定義2.1一個(gè)格值直覺模糊有限自動機(jī)(簡寫為LIFFSM)是三元組M=(Q,X,A)，其中

1)Q表示非空有限狀態(tài)集合;

2)X表示非空有限輸入符號集合;

3)A=(μA,νA)表示一個(gè)Q×X×Q上的格值直覺模糊集，即μA:X→L,νA:X→L,′:L→L且對?x∈X，滿足μA(x)≤(νA(x))′,A叫做格值直覺模糊轉(zhuǎn)移函數(shù).

當(dāng)L=[0,1]時(shí)，格值直覺模糊有限自動機(jī)M就為直覺模糊有限自動機(jī)，因此格值直覺模糊有限自動機(jī)是直覺模糊有限自動機(jī)的推廣.

令X*表示X上所有有窮長度的串的集合，令Λ表示X*上的空串，對于任意的x∈X*,|x|表示x的長度.

定義2.2若M=(Q,X,A)是格值直覺模糊有限自動機(jī)，定義一個(gè)Q×X*×Q上的格值直覺模糊集A*=(μA*,νA*)為：對?q,p∈Q，x∈X*,a∈X,

定理2.1設(shè)M=(Q,X,A)為格值直覺模糊有限自動機(jī)，則

μA=μA*|Q×X×Q,νA=νA*|Q×X×Q.

定理2.2下列條件相互等價(jià)：

1) (L,∨,∧)是分配格，即滿足分配恒等式D1(或D2)；

2) 設(shè)M=(Q,X,A)為任意格值直覺模糊有限自動機(jī)，?q,p∈Q，x,y∈X*有

3) 設(shè)M=(Q,X,A)為任意格值直覺模糊有限自動機(jī)，則?q,p∈Q,x=x1x2…xn∈X*,xi∈X,i=1,2,…,n,有

μA(r1,x2,r2)∧…∧μA(rn-1,xn,p)],

νA(r1,x2,r2)∨…∨νA(rn-1,xn,p)].

證明1)?2) 根據(jù)y的長度，用數(shù)學(xué)歸納法證明.

2)?1) 取M=(Q,X,A)如下：Q={q0,q1,q2,q3,q4},X={x1,x2,x3},μA(q0,x1,q1)=a,μA(q1,x2,q2)=μA(q1,x2,q3)=1,μA(q2,x3,q4)=b,μA(q3,x3,q4)=c,其余情況取μA(qi,xj,qk)=0.νA(q0,x1,q1)=d,νA(q1,x2,q2)=νA(q1,x2,q3)=0,νA(q2,x3,q4)=e,νA(q3,x3,q4)=f,其余情況取νA(qi,xj,qk)=1.滿足a≤d′,b≤e′,c≤f′.

令x=x1,y=x2x3,則有

μA*(q0,xy,q4)=μA*(q0,x1x2x3,q4)=

μA(q0,x1,q1)∧μA*(q1,x2x3,q4),

μA*(q1,x2x3,q4)=

(1∧b)∨(1∧c)=b∨c,

又μA(q0,x1,q1)=a，從而有

μA*(q0,xy,q4)=a∧(b∨c).

又因?yàn)?/p>

μA*(q0,xy,q4)=μA*(q0,x1x2x3,q4)=

[μA*(q0,x1x2,q2)∧μA(q2,x3,q4)]∨

[μA*(q0,x1x2,q3)∧μA(q3,x3,q4)]=

[μA*(q0,x1x2,q2)∧b]∨

[μA*(q0,x1x2,q3)∧c],

μA*(q0,x1x2,q2)=

μA(q0,x1,q1)∧μA*(q0,x1x2,q3)=

μA(q0,x1,q1)∧μA(q1,x2,q3)=a∧1=a,

從而有

μA*(q0,xy,q4)=(a∧b)∨(a∧c),

則

a∧(b∨c)=(a∧b)∨(a∧c).

即滿足分配恒等式D1，則(L,∨,∧)是分配格.

同理可以證明1)?3)和3)?1).

3 格值直覺模糊有限自動機(jī)的直積

定義3.1設(shè)Mi=(Qi,Xi,Ai)是格值直覺模糊有限自動機(jī)，i=1,2.稱M1×M2=(Q1×Q2,X1×X2,A1×A2)為M1與M2的全直積.其中μA1×A2:(Q1×Q2)×(X1×X2)×(Q1×Q2)→L,νA1×A2:(Q1×Q2)×(X1×X2)×(Q1×Q2)→L,?(q1,q2),(p1,p2)∈Q1×Q2,?(x1,x2)∈X1×X2，有

μA1×A2((q1,q2),(x1,x2),(p1,p2))=

μA1(q1,x1,p1)∧μA2(q2,x2,p2),

νA1×A2((q1,q2),(x1,x2),(p1,p2))=

νA1(q1,x1,p1)∨νA2(q2,x2,p2).

由定義3.1當(dāng)X1=X2=X時(shí)，可以定義格值直覺模糊有限自動機(jī)的限制直積，其定義如下：

定義3.2設(shè)Mi=(Qi,X,Ai)是格值直覺模糊有限自動機(jī)，i=1,2.稱M1∧M2=(Q1×Q2,X,A1∧A2)為M1與M2的限制直積,其中μA1∧A2:(Q1×Q2)×X×(Q1×Q2)→L,νA1∧A2:(Q1×Q2)×X×(Q1×Q2)→L,?(q1,q2),(p1,p2)∈Q1×Q2,a∈X，有

μA1∧A2((q1,q2),a,(p1,p2))=

μA1(q1,a,p1)∧μA2(q2,a,p2),

νA1∧A2((q1,q2),a,(p1,p2))=

νA1(q1,a,p1)∨νA2(q2,a,p2).

定理3.1設(shè)Mi=(Qi,Xi,Ai)是格值直覺模糊有限自動機(jī)，i=1,2,則有

1)M1×M2是格值直覺模糊有限自動機(jī);

2)M1∧M2是格值直覺模糊有限自動機(jī),其中X1=X2=X.

證明1) 要證全直積M1×M2為格值直覺模糊有限自動機(jī)，只需證A1×A2為格值直覺模糊集.?(q1,q2),(p1,p2)∈Q1×Q2,?(x1,x2)∈X1×X2有

μA1×A2((q1,q2),(x1,x2),(p1,p2))=

μA1(q1,x1,p1)∧μA2(q2,x2,p2),

νA1×A2((q1,q2),(x1,x2),(p1,p2))=

νA1(q1,x1,p1)∨νA2(q2,x2,p2),

則

(νA1×A2((q1,q2),(x1,x2),(p1,p2)))′=

(νA1(q1,x1,p1)∨νA2(q2,x2,p2))′=

(νA1(q1,x1,p1))′∧(νA2(q2,x2,p2))′.

因?yàn)锳1,A2為格值直覺模糊集，所以

μA1(q1,x1,p1)≤(νA1(q1,x1,p1))′,

μA2(q2,x2,p2)≤(νA2(q2,x2,p2))′.

根據(jù)任意格L中,交、并運(yùn)算是保序的，則

μA1(q1,x1,p1)∧μA2(q2,x2,p2)≤

(νA1(q1,x1,p1))′∧(νA2(q2,x2,p2))′,

即

μA1×A2((q1,q2),(x1,x2),(p1,p2))≤

(νA1×A2((q1,q2),(x1,x2),(p1,p2)))′.

所以A1×A2為格值直覺模糊集，則M1與M2的格值直覺直積M1×M2為格值直覺模糊有限自動機(jī).

類似地可證明2).

性質(zhì)3.1若L為分配格，Mi=(Qi,Xi,Ai)是格值直覺模糊有限自動機(jī)，i=1,2.M1×M2為M1與M2的全直積,則對?(q1,q2),(p1,p2)∈Q1×Q2,?(x,y)∈(X1×X2)*有

μ(A1×A2)*((q1,q2),(x,y),(p1,p2))=

ν(A1×A2)*((q1,q2),(x,y),(p1,p2))=

證明1) 當(dāng)|x|=|y|=0時(shí)，即x=y=Λ時(shí)，

μ(A1×A2)*((q1,q2),(Λ,Λ),(p1,p2))=

μ(A1×A2)*((q1,q2),(Λ,Λ),(p1,p2))=

綜上|x|=|y|=0時(shí)有

μ(A1×A2)*((q1,q2),(Λ,Λ),(p1,p2))=

同理可證

ν(A1×A2)*((q1,q2),(Λ,Λ),(p1,p2))=

因此，|x|=|y|=0時(shí)，結(jié)論成立.

2) 若|x|=|y|=n-1(n>0)時(shí)，結(jié)論成立.

3) ?(a,b)∈X1×X2,則(xa,yb)∈(X1×X2)*，且|xa|=|yb|=n，則

μ(A1×A2)*((q1,q2),(xa,yb),(p1,p2))=

μ(A1×A2)*((q1,q2),(x,y)(a,b),(p1,p2))=

即|x|=|y|=n時(shí)，

μ(A1×A2)*((q1,q2),(x,y),(p1,p2))=

同理可證

ν(A1×A2)*((q1,q2),(x,y),(p1,p2))=

綜上所述，結(jié)論成立.

性質(zhì)3.2若L為分配格，Mi=(Qi,X,Ai)是格值直覺模糊有限自動機(jī)，i=1,2.M1∧M2為M1與M2的限制直積,則?(q1,q2),(p1,p2)∈Q1×Q2,?x∈X*有

μ(A1∧A2)*((q1,q2),x,(p1,p2))=

ν(A1∧A2)*((q1,q2),x,(p1,p2))=

證明利用|x|的長度用數(shù)學(xué)歸納法證明,方法類似于性質(zhì)3.1的證明.

4 格值直覺模糊有限自動機(jī)的直積之間的覆蓋關(guān)系

定義4.1設(shè)Mi=(Qi,Xi,Ai)是格值直覺模糊有限自動機(jī)，i=1,2.如果η:Q2→Q1是一滿的部分函數(shù)，ξ:X1→X2是一函數(shù)，則稱序?qū)?η,ξ)是M2對M1的覆蓋，記作M1≤M2，如果滿足對?x1∈X1,p,q∈domain(η)有

μA1(η(p),x1,η(q))≤μA2(p,ξ(x1),q),

νA1(η(p),x1,η(q))≥νA2(p,ξ(x1),q).

證明根據(jù)x的長度，用數(shù)學(xué)歸納法證明.

1) 當(dāng)|x|=1時(shí)結(jié)論顯然成立;

2) 假設(shè)|x|=n-1時(shí)結(jié)論成立;

3) 若|x|=n,x=x1x2…xn-1xn,?xi∈X1則

μA1(r1,xn,η(q))]=

μA1(η(p2),xn,η(q))|η(p2)=r1}≤

μA1(p2,ξ(xn),q)]=

定理4.1設(shè)Mi=(Qi,Xi,Ai)是格值直覺模糊有限自動機(jī)，i=1,2,3.若M1≤M2,M2≤M3,則M1≤M3.

證明因?yàn)镸1≤M2,所以存在滿的部分函數(shù)η1:Q2→Q1,函數(shù)ξ1:X1→X2,對?x1∈X1,p2,q2∈domain(η1)有

μA1(η1(p2),x1,η1(q2))≤μA2(p2,ξ1(x1),q2),

νA1(η1(p2),x1,η1(q2))≥νA2(p2,ξ1(x1),q2).

又因?yàn)镸2≤M3,所以存在滿的部分函數(shù)η2:Q3→Q2,函數(shù)ξ2:X2→X3,對?x2∈X2,p3,q3∈domain(η2)有

μA2(η2(p3),x2,η2(q3))≤μA3(p3,ξ(x2),q3),

νA2(η2(p3),x2,η2(q3))≥νA3(p3,ξ(x2),q3).

令η=η1°η2:Q3→Q1,ξ=ξ2°ξ1:X1→X3.顯然η是一滿的部分函數(shù),ξ是一函數(shù),并且對對?x1∈X1,p,q∈domain(η)?domain(η2)有

μA1(η(p),x1,η(q))=

μA1(η1°η2(p),x1,η1°η2(q))=

μA1(η1(η2(p)),x1,η1(η2(q)))≤

μA2(η2(p),ξ1(x1),η2(q))≤

μA3(p,ξ2°ξ1(x1),q)=μA3(p,ξ(x1),q).

同理可證νA1(η(p),x1,η(q))≥μA3(p,ξ(x1),q).因此(η,ξ)是M3對M1的覆蓋，即M1≤M3.

定理4.2設(shè)Mi=(Qi,X,Ai)是格值直覺模糊有限自動機(jī),i=1,2.則M1∧M2≤M1×M2.

證明定義η:Q1×Q2→Q1×Q2是Q1×Q2上的恒等映射,顯然滿足η是滿的部分函數(shù).定義ξ:X→X×X為，對?a∈X,有ξ(a)=(a,a)，ξ為一函數(shù),并有

μA1∧A2(η((p1,p2)),a,η((q1,q2)))=

μA1∧A2((p1,p2),a,(q1,q2))=

μA1(p1,a,q1)∧μA2(p2,a,q2)=

μA1×A2((p1,p2),(a,a),(q1,q2))=

μA1×A2((p1,p2),ξ(a),(q1,q2)).

同理可得

νA1∧A2(η((p1,p2)),a,η((q1,q2)))=

νA1×A2((p1,p2),ξ(a),(q1,q2)).

則(η,ξ)是M2對M1的覆蓋，即M1∧M2≤M1×M2.

定理4.3設(shè)Mi=(Qi,Xi,Ai)是格值直覺模糊有限自動機(jī)，i=1,2,3.若M1≤M2，則

1)M1×M3≤M2×M3,M3×M1≤M3×M2;

2)M1∧M3≤M2∧M3,M3∧M1≤M3∧M2,其中X1=X2=X3=X.

證明因?yàn)镸1≤M2,所以存在滿的部分函數(shù)η1:Q2→Q1,函數(shù)ξ1:X1→X2,對?x1∈X1,p2,q2∈domain(η1)有

μA1(η1(p2),x1,η1(q2))≤μA2(p2,ξ1(x1),q2),

νA1(η1(p2),x1,η1(q2))≥νA2(p2,ξ1(x1),q2).

定義η2:Q2×Q3→Q1×Q3為對?p2∈Q2,p3∈Q3有η2((p2,p3))=(η2(p2),p3),易知滿足η2是滿的部分函數(shù).定義ξ2:X1×X3→X2×X3為，對?x1∈X1,x3∈X3有ξ2((x1,x3))=(ξ1(x1),x3)，顯然ξ為一函數(shù).由任意格L中交、并運(yùn)算是保序的,定義3.1和定義4.1,易知(η2,ξ2)是M2×M3對M1×M3的覆蓋,即M1×M3≤M2×M3.同理可證M3×M1≤M3×M2,進(jìn)而可證M1∧M3≤M2∧M3,M3∧M1≤M3∧M2.

推論4.1設(shè)Mi=(Qi,Xi,Ai)是格值直覺模糊有限自動機(jī)，i=1,2,3.若M1≤M2，則

1)M1∧M3≤M2×M3,其中X1=X3=X;

2)M3∧M1≤M3×M2,其中X1=X3=X.

證明利用定理4.1，定理4.2和定理4.3即可得證.

推論4.2設(shè)Mi=(Qi,Xi,Ai)是格值直覺模糊有限自動機(jī)，i=1,2,3,4.若M1≤M2，M3≤M4,則

1)M1×M3≤M2×M4;

2)M1∧M3≤M2∧M4,其中X1=X2=X3=X4=X;

3)M1∧M3≤M2×M4,其中X1=X3=X.

證明1)和2)的證明利用定理4.1和定理4.3即可得證.3)的證明利用定理4.1和此推論中的1)得證.

5 結(jié)語

本文在格值直覺模糊集的框架下,給出了格值直覺模糊有限自動機(jī)的定義.格值直覺模糊有限自動機(jī)是直覺模糊有限自動機(jī)的推廣.因此對格值直覺模糊有限自動機(jī)進(jìn)行研究是有必要的.自動機(jī)的乘積是自動機(jī)研究的一個(gè)重要方面.本文系統(tǒng)的研究了格值直覺模糊有限自動機(jī)在全直積和限制直積下的轉(zhuǎn)移函數(shù)性質(zhì)、覆蓋關(guān)系和覆蓋關(guān)系的傳遞性質(zhì)，為進(jìn)一步研究格值直覺模糊有限自動機(jī)奠定了一定的理論基礎(chǔ).對格值直覺模糊有限自動的乘積研究還有很多工作可以做，比如，格值直覺模糊有限自動機(jī)的級聯(lián)積、圈積、同態(tài)和弱覆蓋等,這些將是今后工作的主要內(nèi)容.

[1] Zadeh L A. Fuzzy sets[J]. Information and Control,1965,8(3):338-353.

[2] Wee W G. On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification[D]. West Lafayette:Purdue University,1967.

[3] Mordeson J N, Malik D S. Fuzzy Automata and Languages: Theory and Applications[M]. Boca Raton,London:Chapman & Hall/CRC,2002.

[4] Atanassov K T. Intuitionistic Fuzzy Sets[J]. Fuzzy Sets and Systems,1986,20:87-96.

[5] Atanassov K T, Stoeva S. IntuitionisticL-fuzzy sets[C]// Trappl R. Cybernetics and Systems Research. Amsterdam:North-Holland,1984:539-540.

[6] Jun Y B. Intuitionistic fuzzy finite state machines[J]. J Appl Math Comput,2005,17(1/2):109-120.

[7] Jun Y B. Intuitionistic fuzzy finite switchboard state machines[J]. J Appl Math Comput,2006,20(1/2):315-325.

[8] Jun Y B. Intuitionistic fuzzy transformation semigroups[J]. Information Sciences,2007,177:4977-4986.

[9] Zhang X W, Li Y M. Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata[J]. Soft Comput,2009,13:611-616.

[10] 馮文俊,易忠,鄧培民. 狀態(tài)機(jī)和變換半群積的覆蓋關(guān)系[J]. 廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2007,25(1):26-29.

[11] 劉軍,莫智文. 格值有限自動機(jī)的乘積[J]. 高校應(yīng)用數(shù)學(xué)學(xué)報(bào),2009,24(1):121-126.

[12] 胡忠剛,鄧培民,易忠. 模糊樹自動機(jī)的積與覆蓋[J]. 廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2009,27(4):31-35.

[13] Liu J, Mo Z W, Qiu D, et al. Products of Mealy-type fuzzy finite state machines[J]. Fuzzy Sets and Systems,2009,160(16):2401-2415.

[14] 翁福利,舒蘭,王澤文. 直覺模糊有限自動機(jī)的乘積[J]. 模糊系統(tǒng)與數(shù)學(xué),2012,26(4):84-88.

[15] 柏明強(qiáng). Fuzzy樹自動機(jī)的等價(jià)性[J]. 四川師范大學(xué)學(xué)報(bào):自然科學(xué)版,2009,32(1):13-16.

[16] Birkhoff G. Lattice Theory[M]. 3rd Ed. Providence RI:AMS Colloquium Publications,1979.

[17] 胡長流,宋振明. 格論基礎(chǔ)[M]. 開封:河南大學(xué)出版社,1990.

[18] 王國俊. 映射與逆映射[J]. 商洛師范?？茖W(xué)校學(xué)報(bào),1999,10(4):1-7.