（基础数学专业论文）格值自动机的代数性质与极小化算法.pdf

格值自动机的代数性质与极小化算法 韩召伟 摘要取值于格半群的自动机比其它形式的模糊自动机能接受更为广泛的 形式语言与模糊语言，将基于词的计算模型建立在更广泛的理论之上因此，对 取值于格半群的自动机代数性质的研究和极小化问题的研究是格值自动机理论的 两个重要课题 既然格值自动机具有如此强大的计算能力，有必要对其从代数角度出发较 详细地，较深入地研究此类自动机的变换半群，乘积和覆盖关系，揭示此类自动 机的代数性质和格半群间的紧密联系对于一个给定的自动机，它的状态中有一 些根本没有被访问过，有一些尽管被访问过，但是本身是不可达的，有一些状态 尽管是可达的，但是在功能上却与另一些状态等价，这样的自动机在设计和应用 中显然很累赘。可以将一些无用的状态删掉，将另外一些等价状态进行整合和约 简，使之状态数达到极小如果一个格值自动机本身可极小化，能否找到一个可 在有限步实现的行之有效的算法? 本文主要是在文献( 3 ，5 ，8 ，1 3 1 4 ，2 9 3 0 ，3 9 1 基础上研究格值自动机的代数 性质及极小化算法 首先，提出了格值自动机和变换半群的定义，研究了其具有的代数性质，并 给出了任意格值自动机可转化为格值变换半群的充分必要条件然后，给出了格 值自动机和变换半群的覆盖以及格值同态的定义，揭示了其具有的代数性质若 格半群中的乘法是格值变换半群可诱导的，在格值强同态下证明了格值可诱导变 换半群和一般有效变换半群是等价的最终，给出四类构造格值自动机乘积和两 类构造变换半群乘积的方法。研究了其具有的代数性质，并研究了几类格值自动 机和变换半群乘积之间具有的覆盖关系 其次。在更一般的框架一格半群意义下，提出具有输入和输出字符的自动 机一一格值m e a l y 自动机的概念，从代数角度出发较详细地研究了此类自动机具 有的性质，同时研究了此类自动机的同余和同态，揭示了此类自动机的代数性质 和格半群的紧密联系，最终研究了格值m e a l y 自动机的极小化问题，并给出了在 有限步可实现此极小化的算法 最后，作为应用主要研究了第二类格值自动机，并在正则同余关系下给出了 可在有限步实现具有模糊初始状态和模糊终状态的自动机l a 极小化的算法 关键词：格半群；格值自动机；格值变换半群；乘积；覆盖；格值同态；覆 盖关系；同余；正则同余；极小化 1 a l g e b r a i cp r o p e r t i e sa n d o fl a t t i c e - v a l u e df u z z y m i n i m i z a t i o na l g o r i t h m f i n i t es t a t ea u t o m a t a z h a o w e ih a n a b s t r a c t ：a u t o m a t aw i t ht r u t h - v a l u e si nl a t t i c e - o r d e r e dm o n o i da r em o r e p o w e r f u lt h a no t h e rk i n do ff u z z ya u t o m a t a ，w h i c hc o n s t r u c tan e wm o d e lo fc o i n - p u t i n gw i t hw o r d s t h e r e f o r e ，t h es t u d yo ft h et h ea l g e b r a i cp r o p e r t i e so fa u t o m a t a w i t ht r u t h - v a l u e si nl a t t i c e - o r d e r e dm o n o i da n dt h es t u d yo ft h em i n i m i z a t i o na l g o - r i t h mf o r mt w oc r u c i a ls u b j e c t si nf u z z ya u t o m a t at h e o r y n o w 6 a t h el - v a l u e df u z z ys t a t ea u t o m a t ah a ss u c hp o w e r f u lc o m p u t a t i o n c a p a c i t y i ti sn e c e s s a r yt ot r a v e r s et h ea l g e b r a i cp r o p e r t i e ss u c ha st r a n s f o r m a t i o n s e m i g r o u p s ，p r o d u c t sa n dc o v e r i n gr e l a t i o n si nl - v a l u e df u z z ya u t o m a t ai no r d e r t os h o wt h ec l o s ec o r r e s p o n d e n c eb e t w e e nt h ea l g e b r a i cp r o p e r t i e sa n dt h el a t t i c e - o r d e r e dm o n o i d a sf o rag i v e na u t o m a t a t h e r ee x i s t st h r e ec a s e s ：f o rs o m es t a t ew h i c h d i dn o tb e i n gv i s i t e d ，f o rs o m es t a t ei t s e l fi n d e e db e i n gn o tr e a c h a b l ea l t h o u l g h i th a sb e e nv i s i t e d ，f o rs o m es t a t ei t i se q u i v a l e n tt oo t h e rs t a t e st h o u g hi tc a n b er e a c h e dt o ，i nt h e s et h r e ec a s e si t i so b v i o u s l yr e d u n d a n tt oc o n s t r u c tt h e s e a u t o m a t a ，a n dt h eo n l yw a yf o ru si st od e l e t e ，i n t e g r a t ea n dr e d u c tt h e s eu s e l e s s s t a t e si no r d e rt om i n i m i z et h en u m b e ro fs t a t e s i fag i v e na u t o m a t aw h i c hc a nb e m i n i m i z a t e d ，w h e t h e rc a nw ef i n da l le f f e c t i v ea l g o r i t h mt om i n i m i z et h e m ? i t h i st h e s i s w em a i n l ys t u d yt h ea l g e b r a i cp r o p e r t i e sa n dm i n i m i z a t i o na p g o r i t h mo fl - v a l u e df u z z yf i n i t es t a t ea u t o m a t aw h i c ha r eb a s e do nt h er e f e r e n c e s 【3 ，5 ，8 ，1 3 一1 4 ，2 9 3 0 ，3 9 】 f i r s t l y , w ei n t r o d u c et h ec o n c e p t so fl a t t i c e - v a l u e d ( a b b r e v i a t e da sl - v a l u e d ) f u z z yf i n i t es t a t ea u t o m a t aa n dl - v a l u e df u z z yt r a n s f o r m a t i o ns e m i g r o u p s ，t r a v e r s e t h ea l g e b r a i cp r o p e r t i e so ft h e m u n l i k et h ec a s eo fo r d i n a r ya n dc l a s s i c a lf u z z ya n - t o m a t at h e o r y , w eg i v es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n sf o rag i v e nl - v a l u e df u z z y f i n i t es t a t ea u t o m a t at of o r maf u z z yt r a n s f o r m a t i o ns e m i g r o u p f u r t h e r m o r ew ei n - t r o d u c et h ec o n c e p t so fc o v e r i n g sa n dl a t t i c e - v a l u e dh o m o m o r p h i s m s ，w ep r o v et h a t t h el - v a l u e df u z z yt r a n s f o r m a t i o ns e m i g r o u p si nw h i c ht h em u l t i p l i c a t i o ni sf u z z y t r a n s f o r m a t i o ns e m i g r o u pi n d u c i b l ei se q u i v e l e n tt ou s u a lf a i t h f u lt r a n s f o r m a t i o n s e m i g r o u p si nt h es e n c eo fl a t t i c e - v a l u e ds t r o n gh o m o m o r p h i s m ，i nt h ee n d , w eg i v e f o u rw a y st oc o n s t r u c t i n gp r o d u c t so fl - v a l u e df u z z yf i n i t es t a t ea u t o m a t aa n dt w o 2 w a y st oc o n s t r u c t i n gp r o d u c t so fl - v a l u e df u z z yt r a n s f o r m a t i o n m i g r o u p sa n d a l g e b r a i cp r o p e r t i e sa n dc o v e r i n gr e l a t i o no ft h e s ep r o d u c t sa r ea l s os t u d i e d s e c o n d l y , i nam o r eg e n e r a l i z e df r a m e s t r u c t r u e - - l a t t i c e - o r d e r e dm o n o i d s ，t h e n o t i o no fl a t t i c e - v a l u e dm e a l y - t y p ea u t o m a t ai si n t r o d u c e d ，w et r a v e r s es o m ea l - g e b r a i cp r o p e r t i e so ft h i sa u t o m a t aa n di n v e s t i g a t et h ec o n g r u e n c e sa n dh o m o m o r - p h i s m so ft h i st y p ea u t o m a t a o u rm a i nr e s u l t si n d i c a t et h a tt h ea l g e b r a i cp r o p e r t i e s o fl a t t i c e - v a l u e dm e a l y - t y p ea u t o m a t ah a v ec l o s el i n k st ot h ea l g e b r a i cp r o p e r t i e s o fl a t t i c e - o r d e r e dm o n o i d sw h i c ha u t o m a t at a k ev a l u e si n f u t h e r m o r ew es t u d yt h e m i n i m i z a t i o no fl a t t i c e - v a l u e dm e a l y - t y p ea u t o m a t aa n dp r o v i d ea na l g o r i t h mt o a c h i e v et h em i n i m a ll a t t i c e - v a l u e dm e a l y - t y p ea u t o m a t aw i t h i nf i n i t es t e p s f i n a l l y , a sa na p p l i c a t i o n ，w es t u d yt h es e c o n dt y p eo fl - v a l u e df u z z yf i n i t e s t a t ea u t o m a t aw h i c hh a sf u z z yi n i t i a ls t a t ea n df u z z yf i n a ls t a t e ，a n dp r o v i d ea n a l g o r i t h mt oa c h i e v et h em i n i m a ll - v a l u e df u z z yf i n i t es t a t ea u t o m a t aw i t h i nf i n i t e s t e p si nt h er e g u l a rc o n g r u e n c er e l a t i o n s k e y w o r d s ：l a t t i c e - o r d e r e dm o n o i d ；l - v a l u e df u z z yf i n i t es t a t ea u t o m a t o n ； 厶v a l u e d 蠹冽t r a n s f o r m a t i o ns e m i g r o u p ；p r o d u c t ；c o v e r i n g ；h o m o m o r p h i s m ；c o y - e r i n gr e l a t i o n ；c o n g r u e n c e ；r e g u l a rc o n g r u e n c er a l a t i o n ；m i n i m i z a t i o n 3 学位论文独创性声明 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果尽我所知，除文中已经注明引用的内容外，论文中不 包含其他个人已经发表或撰写过的研究成果，也不包含为获得陕西师范 大学或其它教育机构的学位或证书而使用过的材料对本文的研究做出 重要贡献的个人和集体，均已在文中作了踞确说明并表示谢意 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西 师范大学本人保证毕业离校后发表本论文或使用本论文成果时署名 单位仍为陕西师范大学学校有权保留学位论文并向国家主管部门或其 它指定机构送交论文的电子版和纸质版；有权将学位论文用于非赢利目 的的少量复制并允许论文进入学校图书馆，院系资料室被查阅；有权将 学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘 要汇编出版 前言 1 9 6 5 年l a z a d e h 5 1 1 教授在其发表的论文h l z z ys e t s 中首次提出用“隶 属函数”的概念来定量地描述事物模糊性的模糊集合理论，奠定了模糊数学的理 论基础 模糊数学是用数学的方法来描述客观世界的模糊现象，揭示其本质和规律 模糊数学在经典数学和充满模糊性的现实世界之间架起了一座桥梁在短短的4 0 年时间里，模糊数学取得了长足的发展，不管是在理论还是应用方面都取得了令 人瞩目的成果模糊数学的应用领域涉及自动控制、图象和文字识别、人工智能、 地质地震、医疗诊断、气象分析、航天航空、火车汽车驾驶、交通管理、决策评 价、企业管理和经济等诸多方面f 9 ，2 5 ，4 2 4 4 ，5 2 5 3 1 有穷自动机作为计算理论中最简单的数学模型，它不仅是计算机科学的理 论基础，为现代计算理论提供可靠的形式理论，而且与神经网络、数学模型等领 域密切相关，在汇编语言，编译语言和算法设计等方面有重要的应用【7 ，1 0 - 1 2 ，5 4 】 自从模糊集合理论产生以后，1 9 6 9 年，w g w e e 利用模糊集的方法研究自动机 理论 4 5 - 4 7 1 ，并提出了模糊自动机的理论，模糊自动机为计算理论提供了一种研 究和处理包含模糊性自然语言的有力工具，关于模糊自动机和模糊语言的讨论已 有很多【1 ，3 - 5 ，1 3 - 1 6 ，2 6 - 3 0 ，3 2 - 3 3 ，3 7 - 3 9 ，4 5 - 4 8 1 在文7 6 - 3 2 1 中d s m a l i k ，j n m o r d e s o n 开始了模糊自动机的代数研究，随 后p r j a s v e l d 和y h k i m 等人 1 , 3 ，1 3 - 1 4 ，3 8 - 3 9 】较详细地研究了模糊自动机的 代数性质极小化问题对于模糊自动机的实现具有重要的意义，因此许多人都致 力于各种类型自动机极小化的研究中，如对于有输入和输出的自动机的极小化在 文【5 l 中有较详细的讨论，此方面最新研究见f 3 9 ；对于具有分明状态转移函数的 模糊自动机的极小化研究见【17 】；对于没有输出且具有分明终状态的模糊自动机 的极小化研究见【3 l ；更多关于这方面的研究见【3 0 ，3 4 - 3 2 最近应明生【4 9 - 5 0 】提 出了基于量子逻辑的自动机理论，邱道文【6 ，4 0 4 1 】提出了基于完备剩余格值逻辑 的自动机理论，从而提供了多值逻辑意义下研究自动机理论的方法正如文【2 1 1 所说，以往的模糊自动机理论只是对经典问题较初步的模糊化，因而缺乏层次结 构我们知道自动机主要是识别形式语言的数学模型，以往的模糊自动机在这方 面只是对经典自动机的简单推广比如，它识别的语言从层次结构上与经典自动 机等价( 经典的自动机可看成取值于 o ，1 ) 集合的模糊自动机，而 o ，1 ) 上的运 算v ，a 分别为数的取大。取小运算，这时， o ，1 ) 就是完备的分配格) 完备剩余 格值逻辑对应的自动机也有类似的问题在文【1 8 - 2 4 】中李永明等提出了格值自 动机的理论，从而在更一般的框架下，即在格半群意义下研究自动机理论。把基 于词的计算模型建立在更广泛的格值自动机理论之上所得结果表明格值自动机 和通常的自动机及经典模糊自动机相比较有更强的计算能力，这也是格值自动机 理论本身的特色 格值自动机按照经典的分类方法可以分成两类t 第一类是具有输出字符而没 有初始状态的格值自动机，第二类是具有初始状态和终状态而没有输出字符的格 值自动机既然格值自动机具有如此强大的计算能力。我们有必要对其从代效角 度出发较详细，较深入地研究此类自动机的变换半群，乘积和覆盖关系，揭示此 类自动机的代数性质和取值格半群的紧密联系另外我们知道，对于一个给定的 自动机，它的状态中一些根本没有被访冈过，一些尽管被访问过，但是本身是不 可达的，有一些状态尽管是可达的，但是在功能上却与另一些状态等价，对于这 样的自动机在设计和应用中显然很累赘，可以将一些无用的状态删掉，将另外一 些状态进行整合和约简，使之状态数达到极小化因此在新的框架下对格值自动 机其自身状态能否进行极小化的研究是很重要的研究课题，如果一个格值自动机 本身可约简，。我们能否找到一个可在有限步实现的行之有效的算法? 这些都构成 了本文的研究内容，下面分别加以叙述 本文共分为四章：第一章主要介绍了模糊集合的基本性质及基本定理，格半 群的定义及其性质。格半群意义下模糊集及映射的模糊扩张 第二章首先提出了格值自动机和变换半群定义及其代数性质，给出了任意格 值自动机可转化为格值变换半群的充分必要条件，然后给出格值自动机和变换半 群的覆盖。格值同态定义，揭示了其具有的代数性质。同时给出和构造了四类格 值自动机和两类变换半群的乘积的方法，研究了其代数性质，最后研究了几类格 值自动机和交换半群乘积之间具有的覆盖关系。 第三章在更广的框架下格半群意义下，提出具有输入和输出字符的自动 机一一格值m e a l y 自动机的概念，从代数角度出发较详细地研究了此类自动机的 性质，同时研究了此类自动机的同余和同态，揭示了此类自动机的代数性质和取 值格半群的紧密联系，最终研究了格值m e a l y 自动机的极小化，并给出了在有限 步可实现此极小化的算法 第四章作为应用我们主要研究了第二类格值自动机，并在正则同余关系下 给出了可在有限步实现具有模糊初始状态和模糊终状态的自动机l a 援小化的算 法 2 第一章预备知识 本章给出本文要用到的一些基本概念，以及这些概念的基本性质 1 1 模糊集的基本性质及基本定理 定义1 1 1 设x 是经典集合，称映射a ：x 一【0 ，1 】为x 上的模糊集 比x ，称a ( z ) 为对a 的隶属度，函数a ( z ) 也称为模糊集以的隶属函数 注1 1 1x 上的模糊集的全体记为f ( x ) ，当a 的值域( 以后称为真值集) ，退 化为 o ，1 时，4 就是经典集合 定义1 1 2 设a ，b f 伍) ， a ：t qc ，( x ) ，其中丁为指标集， ( 1 ) 令u t a t ：x + 0 ，1 1 ，v z x ，( u t r a d ( z ) = v t r a t ( x ) ，贝0u t r a t f ( x ) ，称u t t a t 为 a ：t t 的并特别的，称a ub 为a 与日的并，其隶 属函数为u 口) ( z ) = m a x ( a ( x ) ，b ( z ) ) ( 2 ) 令n t t a t ：x _ 【0 ，1 1 ，v x x ，( n t t a t ) ( z ) = a t t a ( z ) ，则广k r a t f ( x ) ，称n t r a 为 a t ：t n 的交特别地，称a nb 为a 与b 的交，其隶 属函数为nb ) ( 。) = m i n ( a ( z ) ，b ( z ) ) ( 3 ) 令a 。：x 一【0 ，1 】，x ，a 。( z ) = 1 一a ( z ) 则a 。f 何) 称为a 的补 当我们定义了f ( x ) 上的代数运算u ，n ，c 后，显然，( f ) ，u ，n ，c ) 构成一 个代数系统 定义1 1 3 设a ，b f ( x ) ， 。 ( 1 ) 若妇x ，有a ( x ) b ( z ) ，则称a 含于b 或b 包含a 记为以b ( 2 ) 若比x ，有a ( z ) = b ( z ) ，则称a 与b 相等记为a = b 由定义1 1 3 容易证明下面的定理 定理1 1 1 代数系统( f ( x ) ，u ，n ，c ) 有以下性质： ( ) 幂等律，a u a = a ，a n a = a ( 2 ) 交换律；a u b = b u a ，a n b = b n a ( 3 ) 结合律：( a u b ) u c = a u ( b u g ) ，( a n b ) n c = a n ( b n c ) ( 4 ) 分配律；a n ( b u c ) = ( a n b ) u ( a n c ) ，a u ( b n c ) = ( a u b ) n n c ) 3 ( 5 ) 吸收律：a n ( a u b ) = a ，a u ( a n b ) = a ( 6 ) 两极律；a n x = a ，a u x = x ，a n 0 = 0 ，a u0 = a ( 7 ) 复原律t ( a 。) 。= a 。 、 ( 8 ) 摩根律t似u b ) 。= a 。n b 。，( a n b ) 。= a 。ub c 定义1 1 4 设a f 伍) ，a 【0 ，1 】，定义a 与a 的积a a ：x 一【0 ，1 j v z x ，a a 扛) = a a a ( z ) ，则a a f ( j r ) 定义1 1 5v a f ( x ) 模糊集a 的截集厶定义为， a = z ：a ( x ) a ，z x ) 定理1 1 2 ( 模糊集的分解定理) 设a ，) ，有a = o x e o ，1 a a 证明只需证娩x ，a ( z ) = ( u l o ，1 1 a 如) ( 。) ，由于 凡( 互) ： 1 ，蚝厶 1 0 ，o t h e r w i s e 即 酬= k 竺三 敖有 ( u x l x a x ) ( z ) = v a a x ( x ) ：a l ) = v a a a ( z ) ：a l ) = v a ：a ( x ) = a ( z ) 上述证明中用到了格f o ，1 】的完备性 定义1 1 6 设有两个经典集合x 和y ，定义x 和y 的直积为t x y = f ( z ，v ) l z x ，y y ) 直积亦称笛卡尔积，也称积集 定义1 1 7 直积x x y 上的模糊关系是x y 的一个模糊子集兄，r ：x x y 一 【0 ，1 】r 的隶属函数r ( z ，y ) 表示了x 中元素z 与y 中元素y 具有这种关系的程 度x 到x 的模糊关系称为x 上的模糊关系x y 上的全体模糊关系记为 f ( x y 1 4 定义1 1 8 若冗是x 上的经典二元关系。定义t ( i7 若括x 扫，习r ，则称冠是自反的； ( 2 ) 若( z ，y ) r ，则( 雪，z ) r ，则称r 是对称的； ( 3 ) 若( z ，y ) 兄，( 口，z ) 冗，则( z ，z ) r ，则称兄是传递的； ( 4 ) 若只是x 上的一个自反的、对称的且传递的二元关系，则称冗是一个 等价关系 定义1 1 9 若r 是x 上的一个等价关系，比x ，称子集r = 0 xi ( x ，y ) 脚为以z 为代表元的模月等价类，简称等价类称由等价关系r 唯一 决定的x 上的分划，x r = r hz x ) 为x 的模r 商集 1 2 格半群的定义及其性质 设( p ，s ) 是偏序集，其中s 表示集合p 上的偏序关系，若v a ，b p ，则 口b ，或者b d ，则称p 为一个全序集设a 和v 分别表示p 上的下确界运算 和上确界运算， c a ，b p ，若a ab 和a vb 都存在，则称p 为一个格设n p 如果忱p ，都有z 。 则称a 为p 的最大元；如果坛p ，都有z a ，则称 。为p 的最小元，分别记为1 和0 设g 为一个非空集合，为g 上的二元运算，e g 为g 的单位元，若满 足( i ) v a ，b ，c g ，b ( b ec ) = ( g b ) c ；( i i ) v a g ，a e = e o = 8 ，则称g 为 幺半群 定义1 2 1 设l 为格，a 和v 分别表示p 上的下确界运算和上确界运算， 0 ，1 分别为l 的最小元和最大元，为l 上的二元运算( 也称乘法运算) 且 ( l ，e ) 为有单位元e l 的半群，若满足t 一 ( 1 ) v a l ，a 0 = 0 a = 0 ( 2 ) v a ，b ，c l ，asb 辛a csb c 且c a c b ，则称工为序半群若满足 ( 3 ) v a ，b ，c l ，a ( b v c ) = ( a b ) v ( a c ) ，且( b v c ) 口= ( b n ) v ( c n ) ，则 称为格半群进而若l 为完备格，且满足 ( 4 ) v a l ， b t t e r l ，口( v t b t ) = v t ( a o6 t ) ，且v a l ， 巩) t r l ，( v b t ) a = v 。( 6 t o ) ，其中t 为指标集，则称l 为q u a n t a l e 若条件( 4 ) 只对? 取可数集 成立，称己为可数格半群 5 注1 2 1 对于一个格半群厶我们最关心二元运算( 乘法) 和有限上确界运 算v ，并将格半群记侮( 厶，v ) 当我们提及到格半群( l ，v ) 的子代数l 1 时。 我们是说l 1 是l 的非空子集，并且l 1 关于乘法运算和有限上确界运算v 封 闭，而并不关心对于l 1 下确界运算a 是否封闭，因此l l 不必是格 注1 2 2 以下除非特别声明都假定三为带有单位元e 的序半群( 厶，e ) 若 存在a ，b l 且口 0 ，b 0 使得a “= 0 ，则称( l ，e ) 含有零因子例如当 l = 【o ，1 j 且= 似+ b 一1 ) v o ，v a ，b l ，即取l u k a s i e w i c zt 模时，容易验证此 时l 满足定义1 1 的条件即( 1 0 ，1 】，v ) 为格半群，且易知该格半群含有零因子， 如取a = 0 2 ，b 一0 3 ，此时a ，b 0 而o b = 0 注1 2 3 对于取值于格半群( l ，v ) 的矩阵a = ( k 。和b = ( b o ) 。l 定义矩阵的乘积运算为s u p 一复合，即a b = ( k f ，其中q = 0 ( b k j ) ，因为乘法运算满足结合律，容易验证矩阵乘积满足结合律，即对于任意 4 。，且：蝻c ；。d ，( a b ) c = a ( b c ) 注1 2 4 若在序半群( l ，e ) 上，v a ，b l ，都有口b = b a 成立，则称序 半群( l ， 8 ) 可换 铆1 2 1 ( 1 ) 设( 厶 ，v ) 为分配格，取= a ，则三成为格半群，单位元为1 ( 2 ) 设( l ，v ) 为格半群，以l ( n ) 表示取值于l 的n n 维矩阵全体，其上的 乘法运算( 记为o ) 规定为矩阵的s 婶一合成，而a v b = d = ( 如) ，奶= v b , j 则( l ( n ) ，o ，v ) 为格半群，单位元为e = 击叼( 岛，e ) ，即主对角线上的元素为e 的对角矩阵l ( n ) 上的乘法运算一般不可换，即使l 上的乘法运算是可换的 ( 3 ) 若为单位区闻( 0 ，1 i 上的任一一致模，若0 1 = 0 ，则( i o ，1 】，v ) 为可 换格半群，特别的当为单位区间【0 ，1 】上的任一t 模，则( i o ，1 】，v ) 为可换格 半群，单位元为1 ( 4 ) 若t o ，1 j 表示单位区间，比1 ，耽，y l ，驰f 0 ，l j ，定义为( z 1 ，y 1 ) ( y 2 ) = ( x 1 2 7 2 ，y t y 2 ) ，善e 中( z l ，分1 ) a ( 3 ：2 ，暑2 ) = = ( 茁1aj 吃，y la 分2 ) ，( x l ，剪1 ) v ( z 2 ，y 2 ) = ( z 1v z 2 ，y lv 沈) ，则( f o ，1 】f 0 ，l 】，v ) 为格半群 ( 5 ) 令二= f 0 ，+ o o ) ，v 为实数的取大运算， 为实数的乘法运算，即 口b a b ，a ，b o o 0 口一0o rb = 0 。0 ，d 0 ，b ；0 0o rn = o 。，6 0 6 则称( l ，v ) 为可换的q u a n t a l e ，单位元为1 ，最大元为0 0 ( 6 ) 完备剩余格是一类较特殊的q u a n t a l e ，其乘法运算是可换的，单位元是其 最大元 ( 7 ) 取l = ( o ，叼，1 ，v ，a ，0 ，1 ) ，其中0 1 ，0 l ，7 ( ，1 ) 2 ) ，( 厶，k ) ，( 9 1 ，啦) ) ) = v ( 1 0 1 ， ( 如) ，7 1 1 ) # 乜渤，b l ，r t 2 ) ) ( 舻1 ( r l l ，2 ( r 1 2 ) ，r 2 1 ) l r _ i ，r + 2 ) q 1 x ( b p 2 ( r 1 2 ，进，r 2 2 ) ) ) ( p 1 ( 扣一1 ) 1 ，厶( 扣一1 ) 2 ，k ) ，口1 ) 。r e ( r ( 。一1 ) 2 ，k ，眈) ) ) = ( v ( 弛l 白1 ， ( 驰) ，r 1 i ) 户i f n i ，厶( r 1 2 ) ，匏1 ) 芦l ( 加一l ，l ，厶( 7 b i ) 2 ) ，g i ) ) ) 7 1 1 t v l ( v ( ( p 2 渤，b a ，r 1 2 ) 他( r a z ，幻，r 2 2 ) 。脚( ( n 一1 ) 2 k ，幽) r n e v z = v ( 店l ， p 2 ) ，2 ( r 1 ) 厶( r ，1 ) ，口1 ) 脚溉，h ，r 1 ) p 2 ( r l ，b 2 ，r 2 ) t 出 。助( h 一1 ，k ，口2 ) ) ( i i ) 必要性 。 对于任意口，b l ，假设结论( 1 ) 和( 2 ) 成立，构造两个格值自动机l m 巩= ( q 1 ，1 ，肛1 ) 和 如；( q 2 ，2 ，弘2 ) ，其中q 1 = 妇l ，q l ，r 1 ，e 1 = 仃1 ) ，p 1 0 1 ，叮l ，r 1 ) = e ，m ( r l ，口1 ，口1 ) = 口，p l 慨1 ：3 1 ，口) = 0 ，其它，q 2 = p 2 ，班，r 2 ) ，e 2 = 0 r 2 ，脚( p 2 ，眈，r 2 ) = 6 ，比( r 2 ，观，9 2 ) = e ，p 2 ，以，g ) = 0 ，其它。e 为格半群中的单位元 同时v p q 2 定义u ：q 2 1 一e 1 为u 扫，叻) = j 1