（基础数学专业论文）基于量子逻辑的自动机理论研究.pdfVIP

、 基于量子逻辑的自动机理论研究 基础数学专业 研究生郭秀红指导教师莫智文 本文主要讨论了由，一值自动机( 或称为基于量子逻辑的自动机) 构造的 格的一些性质，研究了初始格，与由，一值自动机构造的格之间的关系，并且进 一步讨论了基于量子逻辑的自动机理论的一些拓扑性质。 首先，给出了由，一值自动机构造的格上同态，子格，理想和嵌入映射的 定义，并且研究了同态，子格，理想的性质，同时讨论了子格，理想与同态之 间的关系，得出了由i 一值自动机构造的格的一些性质。 其次，给出了由| 一值自动机构造的格上同构的定义，建立了原始格，的 同构和由，一值自动机构造的格同构的等价性。同时由格同构来作格的一种分 类，进一步得出了原始格，的分类和由，一值自动机构造的格的分类的等价性。 最后，给出了z 一值s u c c e s s o r 算子和s o u r c e 算子的另一种定义，讨论了 ，一值s u c c e s s o r 算子，s o u r c e 算子和z 一值子自动机之间的关系，得到了，一值 s u c c e s s o r 算子，s o u r c e 算子和，一值子自动机的某种等价性。进一步研究了 由，一值s u c c e s s o r 算子，s o u r c e 算子和，一值子自动机构造拓扑。 关键词：量子逻辑；量子自动机；量子自动机的格；格的同态；格的同构； 分类；，一值s u c c e s s o r 算子；，一值s o u r c e 算子；子自动机；拓扑。 i i s t u d yo na u t o m a t at h e o r y b a s e do nq u a n t u m l o g i c m a j o r b a s i cm a t h e m a t i c s p o s t g r a d u a t e g u ox i u h o n g s u p e r v i s o r m oz h i w e n i nt h i sp a p e r , w em a i n l ys t u d yt h el a t t i c ef o r m e db yz v a l u e da u t o m a t a ( a l s o c a l l e da u t o m a t at h e o r yb a s e do nq u a n t u ml o g i c ) t h er e l a t i o n sb e t w e e no r i g i n a l l a t t i c e ，a n dl a t t i c ef o r m e db y ，一v a l u e da u t o m a t aa r ed i s c u s s e d a 1 s o ，w e d i s c u s ss o m eo ft h et o p o l o g i c a lp r o p e r t i e so fa u t o m a t at h e o r yb a s e do nq u a n t u m l o g i c f i r s t l y , t h ec o n c e p t i o n so fh o m o m o r p h i s m ，s u b l a t t i c e ，i d e a la n de m b e d d i n g i n l a t t i c e sf o r m e db v z - v a l u e da u t o m a t aa l ed e f i n e da n ds o m eo ft h ep r o p e r t i e so f h o m o m o r p h i s m ，s u b l a t t i c ea n di d e a la r ed i s c u s s e d r e l a t i o n sb e t w e e ns u b l a t t i c e ， i d e a la n dh o m o m o r p h i s ma r es t u d i e da n ds o m ep r o p e r t i e so fl a t t i c e sf o r m e db y ，- v a l u e da u t o m a t aa r eo b t a i n e d s e c o n d l y , i s o m o r p h i s m i nl a t t i c e sf o r m e db y ，一v a l u e da u t o m a t ai s d e f i n e d i ti ss h o w nt h a tt h ei s o m o r p h i s mo fo r i g i n a ll a t t i c e ，i se q u i v a l e n tt ot h a t o fl a t t i c ef o r m e db y | 一v a l u e da u t o m a t a i nt h em e a n t i m e ，l a t t i c e sc a l lb e c l a s s i f i e db yi s o m o r p h i s ma n dw ep r o v et h a tt h ec l a s s i f i c a t i o no fo r i g i n a ll a t t i c e si s e q u i v a l e n tt ot h a to fl a t t i c e sf o r m e db y ，一v a l u e da u t o m a t a a tl a s t z v a l u e ds u c c e s s o ra n ds o u r c eo p e r a t o r sa r er e d e f m e da n dt h e e q u i v a l e n c e so f ，- v a l u e ds u c c e s s o ro p e r a t o r s ，s o u r c eo p e r a t o r sa n dz - v a l u e d s u b a u t o m a t aa r ed e m o n s t r a t e d a f t e r w a r d s ，w ed e s c r i b e s o m e t o p o l o g i c a l c h a r a c t e r i z a t i o n si nt e r m so ft h ez - v a l u e ds u c c e s s o ra n ds o u r c eo p e r a t o r sa n d l - v a l u e ds u b a u t o m a t a f i n f l l y ，w es h o wt h a tt h el - v a l u e dt o p o l o g i e si nt e r m so f l v a l u e ds u c c e s s o ra n ds o u r c eo p e r a t o r sa n dl v a l u e ds u b a u t o m a t aa r e e q u i v a l e n t k e yw o r d s ： q u a n t u ml o g i c ；q u a n t u ma u t o m a t a ；l a t t i c e s o fq u a n t u m a u t o m a t a ；h o m o m o r p h i s mo fl a t t i c e s ；i s o m o r p h i s mo fl a t t i c e s ；c l a s s i f i c a t i o n ； l - v a l u e ds u c c e s s o ro p e r a t o r s ；l v a l u e ds o u r c eo p e r a t o r s ；s u b a u t o m a t a ；t o p o l o g y i i i i _ j 一 刖舌 计算机科学是关于计算知识的有系统的整体，其始源可回溯到欧几里得关 于一些算法的设计和巴比伦人关于渐近复杂性和归约性的使用。计算机科学有 两个主要部分：第一，构成计算基础的一些基本概念和模型；第二，设计计算 系统( 软件和硬件) 的工程技术，尤其是设计理论的应用。自动机理论是作为 计算机的理论模型和离散自动装置建立起来的。 1 9 3 6 年，t u r i n g t 3 3 1 定义了一类简单的机器- t u r i n g 机，它能够计算任 何可以定义的实数。t u r i n g 机是现代计算机最早的数学模型。t u r i n g 把计算 机的理论大大推进，给予自动机以现在具有的技术含义。对这种机器施加不同 的限制就产生了不同能力的自动机，如有限自动机、下推自动机、线性有界自 动机等。对这些机器进行研究的理论叫做自动机理论，它是计算机科学的一个 分支。例如一个有限状态自动机是一个由五元组m = ( q ，a ，仍f ，丁) 所表示的系 统，其中q 是一个有限状态集；彳是一个有限的输入符号集或字母表；f 是初 始状态；丁是终止状态集；9 ：q a 专q 是状态转移函数( 缈可以自然扩张为 缈：q a 专q ) 。我们说有限状态自动机m 识别( 或接受) 一个字彩a 如 果f 国t 。我们把m 所识别字的全体称为有限状态自动机m 所识别的语言， 记作三) 。换一种方式用矩阵和向量的观点来看待一个有限状态自动机。一 个有限状态自动机是一个由四元组m = ( q ，万， f ( 盯) l 盯么) ，矿) 所表示的系 统，其中q = q l q ：，q 。) 是一个有限状态集；a 是一个有限的输入符号集或 字母表；f 是初始状态；万= ( 。，万啦，) 是一个n 维行向量，其中。= l 如 果q 女= f ；万“= 0 如果q i f 丁是终止状态集；矿= ( ，刁，刁“) 是一个挖维 列向量j 其中，7 靠= 1 如果q t t ；7 7 乳= 0 如果q i 正t f ( 盯) 是一个以疗阶状态 转移矩阵：如果输入字母盯a ，存在从状态k 到状态，的状态转移，那么 旷p ) 】蔚= 1 ；否则，旷( 盯) 】盯= 0 。我们说有限状态自动机m 识别( 或接受) 一个字国a + 如果石f ( o ) x7 7 r = 1 。我们把m 所识别字的全体称为有限状态 自动机m 所识别的语言，记作三( m ) 。 随着微电子技术和信息科学的发展，自动机理论不断向信息技术的各个应 用领域渗透，为它们提供理论模型、设计技术和运行算法。掌握自动机的基本 理论及其应用技术，有助于工程技术人员在实际工程的系统分析、结构综合、 工程实现和模拟检测方面提高其设计技巧和理论分析能力。 传统计算机最终失效问题的一个可能解决的办法是采用不同的计算模式 ( 有效算法解决问题需要的时间，是问题规模的多项式；相反，非有效算法需 要超多项式时间) 。量子计算理论就是这类模式中的一种，量子计算是基于量 子力学而非经典物理学的思想进行计算的。虽然经典计算机可以模拟量子计算 机，但不可能以一种有效的方式去模拟，量子计算机在速度上相对于经典计算 机有本质的超越。 2 0 世纪8 0 年代初，b e n i o f f 1 】和f e y n m a n 2 , 3 1 首先提出了量子计算机的思 想。f e y n m a n 指出在经典计算机上模拟量子力学系统存在本质困难，并建议在 量子力学原理的基础上构造计算机以克服那些困难。1 9 8 5 年d e u t s c h 4 , 5 1 试图 定义一种能够有效模拟任意物理系统的计算装置，由于量子力学是物理学的最 终规律，他很自然地考虑在量子力学原理下的计算装置。仿照4 9 年前t u r i n g 定义的机器，d e u t s c h 给出了量子t u r i n g 机的概念，他举出了一个简单的例 子来说明量子计算机确实可能从计算能力上超过那些经典计算机。1 9 9 4 年 s h o r l 6 1 发现了量子计算机上计算离散对数和大数因子分解的多项式时间算法。 g r o v e r 7 】于1 9 9 6 年为模式识别和数据挖掘提出了一个快速的量子算法。s h o r 的量子因子分解算法和g r o v e r 的量子搜索算法展示了量子计算机从根本上超 越经典计算机的计算能力和在信息处理方面的巨大潜力。此后量子计算的研究 日益活跃。自动机是计算机的简单数学模型，m o o r e ，c r u t c h f i e l d 嘲和 g u d d e r 9 m 从不同的角度引入了作为量子计算机的数学模型的量子自动机，推 广了经典的自动机理论。此后，不少学者在相关方面作了大量工作 1 1 - 1 6 , 2 弘3 1 , 3 4 , 3 5 。 量子力学是用物理理论发展的一个数学框架，它提供了研究物理系统所服+ 从的定律的数学和概念。量子力学的基本假设是经过长期的尝试与失败后推导 出来的，经过了发明者的大量猜测和摸索。假设1 ，任一孤立物理系统都有一 个称为系统状态空间的复内积向量空间( 即h i l b e r t 空间) 与之相联系，系统 完全由状态向量所描述，这个向量是系统状态空间的一个单位向量；假设2 ， 一个封闭量子系统的演化可以由一个酉变换来刻画。即系统在时刻的状态 2 j 和系统在时 l j t ：的状态i 沙 ，可以通过一个仅依赖于时间r 。和f 2 的酉算子 u 相联系：f ) = u f 沙) ；假设3 ，量子测量由一组测量算子 坂) 描述，这些 算子作用在被测系统状态空间上，指标m 表示实验中可能的测量结果。若在 测量前量子系统的最新状态是f 少 ，则结果m 发生的可能性由 p ( m ) = 给出，且测量后系统的状态为 吮j ( 沙i 坂 l - 坂j c ， 测量算子满足完备性方程 肘：心= i ： 假设4 ，复合物理系统的状态空间是分物理系统状态空间的张量积，若将分物 理系统编号为1 到刀，系统f 的状态被置为i ，则整个系统的总状态为 i 沙i o l 沙2 圆圆i 。一个量子有限状态自动机q 是一个由以下五部分所表 示的系统：o ) 一个h i l b e r t 空间h ；( 打) 一个有限的输入字母表a ；( i i i ) 一个 初始状态向量h 并且恢= 1 ；( 柳日的一个子空间f 为终止状态，并且 有一个投影到f 上的投影算子p ；o ) 任意的a a ，都对应有一个酉的转移矩 阵虬。称被q 识别的语言f e ：a 幸j 【0 ，1 】，即v o = o ) 1 0 d 2 月彳木，顾) = i p u 。u 蜘s o l l 2 为量子语言。 而“数学是根据某些假设，用逻辑的推理得到结论”，因此我们有必要研 究量子自动机的逻辑基础。早在1 9 3 6 年，b i r k h o f f 和y o nn e u m a n n1 1 7 】提出了 量子逻辑。此后，不少学者对量子逻辑作了研究1 8 l - 2 1 1 。量子逻辑源于量子力 学的形式化，由于量子力学系统可以用h i l b e r t 空间的闭子空间描述，而 h i l b e r t 空间的所有闭子空间构成正交模格。正如b o o l e a n 代数是经典逻辑的代 数形式一样，文献 2 2 ，2 3 将量子逻辑定义为完备的正交模格值逻辑，提出了 基于量子逻辑的自动机理论即，一值自动机( 或称为量子自动机，但不同于文 献 8 ，9 中定义的量子自动机) ，并且研究了，一值自动机的一些性质。文献 2 4 建立了基于量子逻辑的文法理论的基本框架，证明了任意z 一值量子正规文法 生成的语言等价于某种j 一值量子自动机识别的语言，反之，任意，一值量子自 动机识别的语言等价于某，一值量子正规文法生成的语言。文 2 5 给出了基于 量子逻辑且含动作e 的自动机的定义，推广了文 2 2 中，一值自动机的定义， 并且建立了基于量子逻辑的自动机和文法理论的基本框架，讨论了，一值自动 机识别的语言与，一值正规文法生成的语言的等价性。文 2 6 定义和研究了三 种，一值自动机，四种，一值自动机的运算，得出了不确定的，一值自动机不一定 有等价的确定一值自动机，并且由一值自动机构造了半格和格，进一步讨论 了初始格| 与由，一值自动机构造的格之间的紧密关系。在经典自动机理论中 s u c c e s s o r 算子，s o u r c e 算子和子自动机是研究的一些基本工具，能由它们讨 论自动机的拓扑性质。文 2 7 建立了在，一值自动机理论中的s u c c e s s o r 算子， s o u r c e 算子和，一值子自动机的定义，讨论了它们的性质。文 3 2 给出了基 于量子逻辑的算法理论的综述。 完备的正交模格是一个七元组j = 但，s ，v ，上o ，】 。其中( 厶s ，v ，0 1 是完 备格；1 与0 分别是最大元与最小元；是三上的偏序；任意m l ，人朋和v m 分别表示m 的最大下界和最小上界；一元运算上是三上的正交补，并且满足： 任意口，b 厶a 人口上= 0 ；a va 上= 1 ；口上上= 口；a 6 蕴含b 上a 上：a b 蕴含 a 人血上v 6 ) = b 量子逻辑是一个完备的正交模格值逻辑，定义蕴含算子 a 专5 = a 上v 6 ) ，定义双蕴含算子a 付5 = 0 6 ) ( 6 专口) ，定义 a & 6 = v 6 上) 5 。，值逻辑的语法类似于经典的一阶逻辑，- i ， ，专是三 个原始连接词，v 是原始量词v ，h 和j 由- i ，人，专和v 来定义。在语义方面， 我们将- i ，人，j 分别解释为 ，和j ；v 解释为三中的最大下界。集合论公 式x a 的真值是lx al = 么( x ) ；公式驴是有效的，当且仅当i 矽l 等于l 。 量子计算与量子信息给信息处理和通信带来许多新的令人鼓舞的动力，计 算机科学家和信息论专家有了一个值得探索的新的内容丰富的模型。也许有一 天会导致发明远超过当今计算和通信能力的信息处理装置。量子计算和量子信 息对人类社会最具影响也最为惊人的发现之一是量子计算机能够迅速破解广 泛采用的r s a 密码系统。 本文共分为三章。第一章讨论了由，一值自动机构造的格上同态，子格和 理想之间的关系。第二章进一步研究了初始格，与由，一值自动机构造的格之间 的关系，提出了由z 一值自动机构造的格的一种分类。第三章讨论了基于量子 逻辑的自动机理论的一些拓扑性质。 4 第一章量子自动机的格同态 文献 z 6 研究了，一值自动机，得出在一定程度上，一值自动机其自身也构 成格。本章给出了由，一值自动机构造的格上同态，子格，理想和嵌入映射的 定义，并且研究了它们的性质，同时讨论了它们之间的关系，得出了由，一值 自动机构造的格的一些性质。 1 预备知识 定义俨6 1 设，；( l ，- 0 ，1 ) 是一个格，是有限的输入字母表，o 是状态空 间，称月= ( 凸，l ) 是定义在( ，o ) 上的z 一值自动机，其中q o 表示有限 状态集合，1 q 表示初始状态集合，t q 表示终结状态集合，是定义在 q q 上的f 值谓词集合，即v q 。，q 2 g x ，占( 口1 ，z ，9 2 ) 是，中的一个 元，在中仅8 ( q l ，x ，9 2 ) 0 ( ，的最小元) 被列出，j ( 9 1 ，z ，9 2 ) 称为当输入为x 状态9 1 转移到q ：时x 的接受度。 定义2 【”1 墨= ( 9 l ，i j ，互，a 。) ，r ：= ( q 2 ，厶，疋，2 ) 是两个定义在( ，o ) 上 的，一值自动机，定义r 。，、r ：= ( 奶，1 3 ，正，色) 其中幺= 幺nq 2 ，厶= 1 1 n 厶， 五= 五n 瓦，3 = 巧( g ，x , q 。) f g ，q 幺，茗，j ( g ，x ，q ) = j 马( g ，x , q ) a 万马( g ，_ x ， g ) 0 ，易知r 。 胄：也是定义在( ， ) 上的，一值自动机。 定义3 叫1 r 1 = ( q i ，i l ，正，a 1 ) ，r 2 = ( q 2 ，l ，疋，a 2 ) 是两个定义在口，o ) 上 的l 一值自动机，定义r v r ：= ( 马，l ，五，：) 其中q 3 = 鸟u 幺，1 3 = i i u 厶， 正= 正u 五，a 3 = 占( 易葛g 。) j 吼q 。珐，z 是巧0 ，x , q ) = 氏0 ，x , q ) v 氏0 ，五 g ) 0 ) ，易知r 1v r ，也是定义在“， ) 上的，一值自动机。 定理1 2 6 1 定义在( ，o ) 上的，一值自动机构成格，记为；a c ( t ， ) 。 2 主要结果 定义1 设上。= l a t ( 1 ，o ) ，m q = l a t ( 1 ，o ) 是卜值自动机构造的格， 映射p ：上。j m 。若满足( 1 ) v r l ，r 2 l q , r lc r 2 n o ( x ，) o ( r 2 ) 称口为一个序 同态。如果0 是一个双射并且满足( 1 ) 与( 2 ) v r l ，r 2 l q ，o ( r ，) o ( e 2 ) 则 r 1c r ：称口为一个序同构a 若满足( f ) v r ，r ：l q , o ( r 。 月：) = o ( r ，) 0 ( r ：) 则称0 为一个交同态。若满足何) 。，r ：l q ，o ( r 。vr ：) = o ( e ，) vo ( r ：) 则称 秒为一个并同态。当口同时满足和时，则称秒为一个格同态。设汐是格 同态，如果乡是单射，则称汐为单同态；如果汐是满射，则称秒为满同态，这 时也说格厶与格鸠同态；如果秒是双射，则称口为格同构，也说格厶同构于 格m q o 定理1 设l q = l a t ( 1 ，o ) ，鸠= l a t ( f , ，o ) ，如果，与，同态，则三g 与鸠 同态。 证明设秒：j 专j 是满同态，缈：r = ( q l l ) 专r = ( q l l 臼( 厶) ) 其中矽( ) = a ( q ，x , q 。) ig ，q q 工x , 8 ( q ，x ，q ) = 口( 蟊白，x , q ) ) 0 ) ，则伊是 三，到鸠的满同态。 推论1 设l q = l a t ( 1 ，o ) ，鸩= l a t ( f , ，o ) ，如果，同构于，则厶同 桷干m q t 定理2 设三，鸠是任意，一值自动机构造的格，对于映射臼：l q 专m 叮， 下列条件是等价的： ( d0 是格同构； ( 哟0 是并同构； ( i i i ) p 是交同构； ) 0 是序同构。 证明) 哼( 豇) 是显然的。 ( 功专( 柳犯，月2 三g ，月l 垦，则局vr 2 = r 2 ，从o ( r 2 ) = o ( r lvr 2 ) = e ( r 1 ) v e ( r 2 ) 于是e ( r 。) o ( r 2 ) 。反之，若o ( r 1 ) o ( r 2 ) ，则 o ( r 2 ) = o ( e 1 ) vo ( r 2 ) = e ( r lvr 2 ) ，因为p 是双射，则r 2 = r l vr 2 。因此 足r ：，故秒为序同构。 ( i v ) 哼( i i i ) v r l ，r 2 厶，因为口是双射，存在r ，厶，使得 秒( r 3 ) = 秒( 墨) 人口( r 2 ) 。，显然 秒( r 3 ) 护( 置) ，秒( r 3 ) g 秒( 恐) ，于是 玛r i ，玛r 2 则r 3 r lar 2 , 口( r 3 ) 臼( 垦 r 2 ) 因为曰是序同构，则 o ( r lar 2 ) o ( r 1 ) 人口( r 2 ) = 秒( r 3 ) ，因此o ( r 1 人r 2 ) = o ( r 1 ) o ( r 2 ) ，故口是交 同构。 ( f i f ) 寸( f ) 由对偶原则可得若曰是交同构，则秒是序同构，从而秒是并同构， 6 故汐是格同构。 定义 2 设x 是格三。的一个子集，如果 v r l ，r 2 z 墨人r 2 x ，r lv r 2 x ，则称z 为格z 4 的一个子格。 定理3l 。= l a t ( 1 ，o ) ，设， 分别是j ，o 的子集， x = l q a ( i , ，o ) 是定义在( ，o ) 上的l r 一值自动机的集合，则彳是三。的 子格当且仅当，是，的子格。 证明”j ”v a ，b ，存在r l ，r 2 x ，使得屯( g ，x , q ) = 口，吒( g ，x ，q ) = b 。 因为z 是厶的子格，r 1 人r 2 x ，r l vr 2 x ，则 6 毫( g ，x , q 。) 人巧之( g ，x ，q 。) = 口a b ，。， 万蠢( g ，x ，q 。) v 万岛( g ，x ，q 。) = av b z ， 故，是，的子格。 ”仁”因为，。，o 分别是，o 的子集，在中仅列出了非0 元故x 是格 厶的一个子集。，r ：x ，因为z 是，的子格，氏( g ，x ，g 。) a 氏( g ，x ，9 ) ， 氏( g ，x , q 。) v 氏( 吼x , q ) ，则r 1 人r 2 z 墨vr 2 x ，故x 是厶的子格。 定理4 如果三。是分配格( 模格) ，则l 的子格也是分配格( 模格) 。 证明设z 是厶的子格，v r l ，马，马x ，因为厶是分配格， r la ( 尺2vr 3 ) = ( r i r 2 ) v ( r lar 3 ) 。而r la ( r 2vr 3 ) x ，( r lar 2 ) v ( r 1 人 飓) z ，故z 也是分配格。 同理可证，如果三。是模格，则x 也是模格。 定理5 设三。= l a t ( 1 ，o ) ，鸠= l a t ( 1 ，o ) 是任意，一值自动机构造的 格，0 ：l 。- - - - m 。是满同态，则下列结论成立： ( f ) 如果g 是三。的子格，贝j j o ( g ) 是心的子格； ( f f ) 如果日是心的子格，则p - 1 ( 日) 是三口的子格； ( f f f ) 如果z 是模格( 分配格) ，则，也是模格( 分配格) 。 证明( f ) ：，r ：秒( g ) ，存在r 。，r 2 g 使得o ( r 1 ) = r ：，o ( r 2 ) = r ：。因为 g 是三。的子格，则r lar 2 g ，r lvr 2 g 于是： 秒( r 1 ) 人o ( r 2 ) = o ( r 1 人r 2 ) 秒( g ) ，o ( r 】) v 伊( r 2 ) = o ( r lvr 2 ) 秒( g ) 。 即r ：八r ：口( g ) ，r ：vr ：臼( g ) 从而臼( g ) 是心的子格。 g 力l ，足：汐。1 ( 日) ，则o ( r 1 ) ，o ( r 2 ) h ，因为日是的子格，于 7 是： o ( r 1 ) 人口( r 2 ) = o ( r lar 2 ) h ，o ( r 1 ) vo ( r 2 ) = o ( r lvr 2 ) h 。 a g f f r lar 2 o - i ( 日) ，r lvr 2 矽- 1 ( 日) 。故口- 1 ( 忉是乞的子格。 ( i i i ) 叫，月：，鸭，存在局，r 2 ，r ，l q 使得口( 量) = 硝，臼( r 2 ) = 砭， o ( r ，) = r ；。，是模格，则三g 是模格，于是 硝v ( r ：a ( r ：v 欠；) ) = o ( r 。) v ( 口( 坞) 人( 口( r ，) v 0 ( r 3 ) ) ) = 秒( r lv ( r 2a v 马) ) ) = 口( ( r lv r 2 ) 人( 足lv r 3 ) ) = ( 口( r 1 ) v o ( r 2 ) ) a ( 秒( 置) v 秒( r 3 ” = ( 垦vr ：) a ( 置v 坞) 。 从而m o 是模格，故，也是模格。 同理可证，如果，是分配格，则| 也是分配格。 定义3 设j 是格三。的一个子集，如果满足 ( 1 ) v r l ，r 2 j ，r lvr 2 j ( 2 ) v r l j ，r 厶，如果rgr l 则r j ， 则称j 为三。的一个理想。 显然，格厶的所有理想都是厶的子格。 定理6l 。= l a t ( 1 ，o ) ，设z ，。，o 分别是z ，o 的子集，则 x = l q a ( f , 。，o ) 是三。的理想当且仅当z 是，的理想。 证明”因为x 是三。的理想，于是z 是三。的子格，则是的子格。 v a z ，b ，b a ，存在r l x ，r l g 使得氏( g ，x ，g ) = 口，昧( g ，x ，g ) = b 。因 为r lar r l ，r 1 人r 五则氏( g ，x ，q ) 人蟊( g ，x ，g ) = a a b = b ，故z 。是， 的理想。 ”仁因为z 是，的理想，于是，是，的子格，则x 是三。的子格。 v r l x ，r 三口，r r l ，则r r l = r ，因此 万尼( g ，x ，q 。) a 万r ( g ，x ，g 。) = 以( g ，x ，q ) 因为是，的理想，& 国，x ，q ) j ，则r x ，故x 是厶的理想。 定义4 设是格厶的任意子集，则l 。中所有包含的理想的交集是三g 中 包含的最小理想，称由生成的理想，记作( 】。特别地，由单元集 r ) 生 8 成的理想( 捌叫做厶的主理想，( r 】- r 。ir g qr 埘。 我们记三。表示由三。的所有理想组成的集合。 定理7 三。关于集合的包含关系成为完备格。 证明( 乞，) 是偏序集，设厶= 厶j 口d ，则 念以= q 以，以= ( y 以】 而l q 的任意多个理想的交集仍是l q 的理想，故( 厶，g ) 是完备格。 定理8 如果三。是模格( 分配格) ，则三。也是模格( 分配格) 。 证明 设以，以，厶是厶的理想，以( 集合的包含关系) 。 v r ( v 以) a 以，因为以a 以= 以n 以= 似ar ir 以，r 以) ， v 以= ( - 1 1u 以】- 俅ir l 4 ，3 r l 以，r 以，3r r lvr 2 ) ， 则存在r l 以，r 2 以，马以，使得r v 兄) 马。显然r l 正，= r vr 3 以。 于是r ( r l v r 2 ) ar 3 ( r lvr 2 ) a = r lv ( r 2 趟) ，则 r d lv ( 以a 以) ，因而( a l lv 以) 人以以v ( 以人也) 。再由模不等式知 ( 以v 以) 以2 v ( 以 以) 。故( 以v 以) 以= 以v ( 以人以) ，即三g 也是模 格。 同理可证，如果上。是分配格，则三。也是分配格。 定义5 秒：三口专心是单同态，易见口( 厶) = i m 0 是鸠的子格，并且三叮同 构于臼( 厶) ，这时称口为格的嵌入映射，也说厶可以同构嵌入到鸠之中。 定理9 三。是任意，一值自动机构造的格，秒：尺岭( r 】是上g 到三g 的单同态， 从而l 。可同构嵌入到厶之中。 证明。，r ：厶，( r l 】= ( r 2 】当且仅当r 。= r ：，因此口为单射。 ( 墨】八( r ：】= ( r 1 人r ：】，( r l 】v ( r 2 】_ ( r ，vr ：】知臼为单同态。故上。可同构嵌入 到厶之中。 推论2 厶是任意，一值自动机构造的格，则三。可以嵌入到一个完备格之 中。 推论3 三。是模格( 分配格) 当且仅当三。可以嵌入到一个完备的模格( 分 配格) 之中。 3 总结 9 本章在，一值自动机构造的格上定义了同态，子格，理想和同构嵌入。从 初始格j 与由，一值自动机构造的格厶的关系出发研究了由，一值自动机构造的 格上同态，子格，理想的性质。同时讨论了由，一值自动机构造的格上子格， 理想与同态之间的关系，如在同态意义下子格的象和逆象都仍是子格，并且得 出了任意j 一值自动机构造的格可以嵌入到一个完备格之中。这样的研究丰富 了，一值自动机的理论。 1 0 第二章量子自动机的格的一种分类 本章进一步研究了由，一值自动机构造的格，首先给出了由，一值自动机构 造的格上同构的定义。然后讨论了原始格j 的同构与，一值自动机构造的格同 构之间的关系( 定理l 和定理3 ) 。最后由格同构来作格的一种分类，得出了 原始格的分类与，一值自动机构造的格的分类之间的关系( 定理5 ) 。 1 主要结果 定义1 设厶= l a t ( 1 ，o ) ，鸩= l a t ( 1 ， ) 是任意由，一值自动机构造的 格，映射乡：l q 专g q 如果满足 ( i ) v r = ( g l ，9 2 ，q 。) ， g ，q ，q ) ， g ，q 如，q ) ，a ) l g ， p ( r ) = ( g i ，q 2 ，g ：) ， g ：，g ：，g ；i ， g 二，9 2 ，g 五) ，1 ) ，f i = f f o dv r l ，r 2 厶，o ( r 1a r 2 ) = p ( 蜀) a o ( r 2 ) ( f 哟v r l ，r 2 l q ，o ( r lv r 2 ) = o ( r t ) v o ( r 2 ) 则称臼为一个格同态。设口是格同态，如果秒是单射，则称9 为单同态；如果口 是满射，则称汐为满同态，这时也说格厶与格必同态；如果汐是双射，则称 0 为格同构，也说格l 同构于格肘。 定理1 设厶= l a t ( 1 ，邑o ) ，鸠= l a t ( f , ，o ) ，如果j 同构于，。，贝l j l q 同 构于m g 。 证明设缈：，- - f 是格同构，口：r = ( 9 ，丁，) 一r = 汜，厶丁，伊( ) ) 其中伊( ) = 万( g ，x ，q ) lg ，q q ，x ，艿( g ，x , q ) = 9 ( 蟊( g ，z ，q ) ) 0 ，贝i j 易知臼 是三g 到鸠的格同构，故格l q 同构于格m q 。 定理2 设r ，= ( g l ，q 2 ) ， 9 1 ) ， g ：) ，p ( g l ，x ，q 2 ) 啪，秒是三。到m 。的格同 构，则 o ( r ，) = ( ( g ：，勃，瓯 ， ) ， 万( g - ，盯，9 2 ) z ) ) ，i 2 ，五，j z 1 ，2 ，o - 。 证明v a ，b ，r 。= ( g l ，q 2 ) ， g l ， 9 2 ) - ， 万国l ，x , q 2 ) = 口 ) ， r b = ( g l ，q 2 ， 9 1 ) ， 9 2 ) ， ，娩( g 二，叽g 二) z ) ) ， 故结论成立。 推论1 设秒是三g 到鸩的格同构，弓= ( 幻：，g ：) ，幻i ) ， 无) ，p ( 无，以吐) ， ) ，贝口1 ( r ，) = ( g l ，q ：) ， 9 1 ) ， 9 2 ) ， 万( g l ，x ，q 2 ) d ) 。 定理3 设厶= l a t ( 1 ，o ) ，鸠= l a t ( 1 , ， ) ，如果三g 同构于m g ，则，同 构于。 证明设乡：厶哼m 。是格同构， v a z ，r 。= ( g l ，q 2 ) ， g l ， 9 2 ) ， 万( 9 1 ，x ，q 2 ) = 口) ) ， 存在g ：，g ：o ，盯，之，五，左 1 ，2 ) 使得 o ( r 。) = ( g i ，g ： ，慨 ， g ：2 ) ，俄( g 二，盯，9 2 ) ，。) ) 。 令伊( 口) = 以( g j ，仃，g z ) z ，易知伊是，到，的双射。 v a , b ，疋= ( g l ，q 2 ， g l ， 9 2 ) ， 万( g l ，x , q 2 ) = 口) ) ， 口( 疋) = ( g ：，g ： ， g i ) ， g ；2 ) ， 皖( g 二，仃，9 2 ) ) ) ， 伊( 口) = 皖( g i ，仃，g 羔) ， r b = ( g l ，q 2 ) ， 9 1 ) ， 9 2 ) ， 万( g l ，x ，9 2 ) = 6 ) ) ， o ( r 。) = ( g ：，g ：) ，瓯 ， u q 是格同构，n o - 1 是肘。到z 口的格同构，因此对称 律满足； ( i i i ) 设孝：厶专鸠，r i ：鸩专只是格同构，则7 7 孝是三，到的格 同构，因此推移律满足，故量子自动机的格同构是一个等价关系。 由格同构来作格的一种分类有如下的关系： 定理5 若三。= l a t ( 1 ，o ) 与坂= l a t ( f , ，o ) 在同一个类，则，与，也在同 一个类，反之，与，在同一个类，则厶与鸠也在同一个类；若三。与必。不在 同一个类，则，与，也不在同j 个类，反之j 与，不在同一个类，则厶与必也 不在同一个类。 证明若l q 与鸠在同一个类，则厶与鸠同构，从而j 与j 同构，于是j 与 ，也在同一个类，反之若z 与，在同一个类，则z 与，同构，从而三。与m 。同构， 于是三口与m 口也在同一个类；若三。与m g 不在同一个类，设，与z 在同一个类 则三。与m 。在同一个类，产生矛盾，从而，与，也不在同一个类，反之若，与， 不在同一个类，设三。与m 。在同一个类则z 与i 在同一个类，产生矛盾，从而三。 与m 。也不在同一个类，故结论成立。 2 总结 本章进一步讨论了由，一值自动机构造的格的一些性质。首先，给出了由 z 一值自动机构造的格上同构的定义。其次，建立了原始格，的同构和由，一值 自动机构造的格同构的等价性。最后，由格同构来作格的一种分类，进一步 得出了原始格珀勺分类和由，一值自动机构造的格的分类的等价性。 第三章基于量子逻辑的自动机理论的拓扑性质 文( 2 7 1 建立了在，一值自动机理论中的s u c c e s s o r 算子，s o u r c e 算子和，一 值子自动机的定义，讨论了s u c c e s s o r 算子，s o u r c e 算子和，一值子自动机的 性质。得到了在人关于v 分配时s u c c e s s o r 算子，s o u r c e 算子和，一值子自动 机的等价性以及s u c c e s s o r 算子和s o u r c e 算子关于并封闭，在关于v 分配 时，一值子自动机关于交封闭，证明了s u c c e s s o r 算子和s o u r c e 算子关于交封 闭，一值子自动机关于并封闭。因此得到了在人关于v 分配时s u c c e s s o r 算子 和s o u r c e 算子可构造，一值自动机的拓扑。而在完备的正交模格中正交模律 ( 即v a ，b l ，口人( 口上v ( 口人6 ) ) b ) 可以看成分配律较弱的形式。由此，本 章给出了s u c c e s s o r 算子和s o u r c e 算子的另一种定义，得出了s u c c e s s o r 算 子，s o u r c e 算子和，一值子自动机之间的某种等价关系( 定理2 2 ) ，研究了由 它们构造拓扑，证明了s u c c e s s o r 算子和s o u r c e 算子关于交封闭( 定理3 1 ) ， 得到了在关于v 分配时s u c c e s s o r 算子和s o u r