（计算机软件与理论专业论文）非线性信念变化的研究.pdf

南京航夺航灭人学硕1 ：学位论文 摘要 本文对非线性信念修正的若干问题进行了讨论。取得的主要结果如下： ( 1 ) 建立了基于部分交构造的由非线性序选择机制决定的满足某种完备性条件的 一类收缩算子的表示定理。 ( 2 ) 以一个较弱的逻辑平台为起点，引入一种类似e e 序的非线性序一l e e 序，探 讨了l e e 序的性质和收缩算子公理假设之间的对应性。建立了基于l e e 序的 收缩函数的基本表示定理，然后在基本表示定理的基础上逐一建立了基于几类 特殊l e e 序的收缩算子的表示定理 ( 3 ) 提出r e e 序概念，系统讨论了r e e 序与l e e 序之间的关系。并以此为基础阐 述了非线性l e e 序的存在性。初步讨论了非线性l e e 序的分段线性表示问题 关键词：部分交收缩l e e 序收缩表示定理 a b s t r a c t 1 1 1 i s 也e s i sc o n c e r n sb e l i e f c h a n g ew i t h o u tl i n e a r i t y , m a i nc o n t r i b u t i o ni n c l u d e s ： ( 1 ) w ce s t a b l i s h e sar e p r e s e n t a t i o nt h e o r e mf o rap a r t i a lm e e tc o n t r a c t i o nw h i c hi s d e f i n e db yan o n l i n e a rr e l a t i o na n ds a t i s f i e sa c o m p l e t ec o n d i f i o n ( 2 ) b a s e do nl a t t i c et h e o r y , w ei n t r o d u c ear e l a t i o nc a l l e dl e e ( l a t t i c e - e p i s t e m i c e n t r e n c h m e n t ) ，e x p l o r et h ep r o p e r t i e so fc o n t r a c t i o nb a s e do nl e ea n dg e ta s e r i a lo fi n t e r e s t i n gr e p r e s e n t a t i o nt h e o r e m s ( 3 ) w ep r e s e n tar e l a t i o nc a l l e dr e e ，a n di n v e s t i g a t es y s t e m a t i c a l l yt h er e l a t i o n b e t w e e nl e ea n dr e e f u r t h e r m o r e w es h o wt h a tt h e r ee x i s t san o r d i n e a rl e e r e l a t i o n f i n a l l y , w ed i s c u s sh o wt or e p r e s e n tn o n l i n e a rl e eb yl i n e a rl e e s k e y w o r d s p a r t i a lm e e tc o n t r a c t i o nr e p r e s e n t a t i o nt h e o r e ml e er e l a t i o n 南京航中航天人学顺1 学位论文 第一章绪论 1 1 信念变化研究背景 人们在现实世界中不断地获得新信息，新信息经常和我们原有的知识不协调， 作为一个理智的人当然不能容忍这种不协调因此，有必要对原有的知识和新信息进 行处理，以消除这种不协调这种处理过程j 下是信念改变( b e l i e fc h a n g e ) 研究的直观背 景 人工智能作为研究和模拟智能行为的学科成为研究信念变化的主要学科之一， 其它诸如哲学和逻辑学领域亦有许多学者参与了信念变化的研究学术界通常将信 念变化理论描述成刻画知识进化规律的理论和模型。 为了研究和刻画知识的进化规 律，人们提出了如下三种知识进化模式。 第一种形式是扩充( e x p a n s i o n ) 当一个命题x 和一个理论世协调时，将 置+ x = c h ( k u 扛) ) 作为扩充的结果 第二种形式是收缩( c o n t r a c t i o n ) 从一个演绎封闭的理论k 当中抛弃一个命题x 该种形式的中心问题是：决定k 当中哪些命题应该和z 一起被抛弃，并且剩下的 世+ z 仍然是封闭的理论 第三种形式是修正( r e v i s i o n ) 当个命题x 和一个理论k 不协调时，将z 添加到 k 当中去，要求得到的新理论世o x 协调，修正过程可以通过如下l e v i 等式归约到收 缩 k 0 x = c n ( ( k 浦) u 忸) ) ( l e v i 等式) 事实上， 收缩操作也可以通过下列所谓h a r p e r 等式归约为修j 下操作。 k x = ( k 0 _ 1 z ) n k ( h a r p e r 等式) 在上述三种操作中扩充操作是平凡的。人们研究的主要兴趣集中在后两个操作 上，由于收缩操作较修f 操作更基本并且修f 操作可以通过l e v i 等式归约为收缩操 作，所以信念修正研究的许多工作是基于收缩算子展开的。由前面关于收缩操作的 描述可以知道，为达到收缩的目的可以有多种收缩方式，但并不是所有方式都是合 理的。为此，研究人员提出了信念收缩要遵循的一条重要原则“信息经济原 则”( p r i n c i p l eo fi n f o r m a t i o n a le c o n o m y ) ， 其主要思想是：在收缩的过程中，信息的损 失要尽可能少显然这条原则带有相当的含混性，这种含混性是计算机科学和数理 逻辑学者不能接受的。所以，人们用数学和逻辑学的形式语言形式化该原则，可 以说信念变化的研究在很大程度上就是在追求该原则的形式化刻画。 1 f 线性信念变化的研究 一个显然的事实是信息经济原则带有浓厚的哲学色彩，这使得信念变化的研究 和通常哲学问题的研究一样呈现出百花齐放，日家争鸣的态势，备种不同理论和模 型被提出。然而在一定标准下，这些理论和模型可以分为两个学派其一称为一致 主义行( c o h e r e n t i s t ) 另一派称为基础主义者( f o u n d a t i o n a l i s t ) 在一致主义者的系统中， 所有的信念被看成是同样基本的因此不存在基本信念和推论信念之问的茬别但 是，基础主义者强调在更新信念时，保持基本信念和推论信念之问分离的重要性 f u h r m a n n ，h a n s s o n ，n e b e l 研究了当信念集k 添加新信息时，相应的信念基b 应该怎 样改变在他们的系统中，为了决定新信念集，先要决定新信念基本文侧重于前者 的研究，下面我们简要介绍一致主义学派中最具代表性的理论一a g m 理论。 1 2a g m 理论 a g m 理论是由a l c h o u r r 6 n ，g a r d e n f o r s 和m a k i n s o n 共同提出的一种信念变化理论， 它在信念变化研究中具有里程碑的地位。其重要性在于，a g m 理论并不研究具体 的信念变化过程，而是通过提出一组公理假设来刻画合理的信念变化算子，虽然学 术界对他们提出的公理假设尚存在争议，但他们开创的用公理化的方法研究信念变 化已为绝大多数人所接受和采纳。a g m 理论提出如下关于收缩算子的公理假设，其 中k 是命题语言3 的理论( 即k = c n ( k ) ) ，是理论k 上的收缩函数，x ，y 是3 的任意命题： ( 1 )c n ( k 工) = k x ( 2 ) k x k ( 3 )x 隹k 暑k 工= k ( 4 )x k x = x c 门( ) ( 5 ) k c n ( ( k x ) u x ) ) ( 6 ) c n ( x ) ) = c 玎( _ y ) = k x = k y 上述假设称为收缩基本假设，其中( 二1 ) 的含义是从一个理论中收缩一个信念后 得到的仍然是理论( 二2 ) 的含义是当我们收缩一个信念，我们不可能因此相信原有知 识之外的任何新信念( + 3 ) 的含义是：收缩一个我们不相信的信念对于我们的信念集 南京航守航天人学蟛! i 学位论史 没有影响( 4 ) 的含义是：非永真命题总能被成功收缩掉( 5 ) 的含义是：收缩后的 信念集应该包含足够多的信息，以致于当我们把被收缩的信息重新加入收缩后的信 念集后能够恢复收缩过程中损失的所有信息， 一些学者认为该假设是信息经济原 则的集中体现：( + 6 ) 的含义是：如果两个命题的内容相同，那么从同一个信念集收缩 这两个命题，所得的结果相同，换言之收缩结果不依赖语形 除了上述基本假设外，a g m 理论的收缩算子还有两条附加假设 ( 7 )k x n k y k x 入y ( 8 )x 芒k - - x _ y jk z a y k x a g m 不但提出了上述假设，还为符合这些假设的收缩算子提出了构造方法。下 面我们简要介绍与本文工作相关的两种构造方法的基本思想，其形式化定义在后续 章节中介绍； ( 1 ) 部分交收缩( p a r t i a lm e e tc o n t r a c t i o n ) 的基本思想【1 】： 为了从一个理论足中 收缩一个命题z ，部分交构造在k 的所有不包食工的极大子理论集上引入一种选择 机制，将部分交收缩算子定义成选择机制挑选出的集合的广义交。 ( 2 ) 基于e e ( e p i s t e m i ce n t r e n c h m e n t ) 序构造的基本思想【7 】： e e 序是定义在命 题之间的一种满足若干性质的二元关系， 直观上它提供了信念集合中不同信念的相 对置信度，由置信度的高低来决定收缩时信念的取舍，据此构造收缩算子。值得 指出的一点是，e e 序的引入为信息经济原则提供了新的理解方式，即信息经济原 则不是信息量的经济原则，而是信息置信度的经济原则，换言之，在信念收缩过 程中应当尽量保留高置信度的信息。 已有的工作表明上述两种构造算子的方法与a g m 假设有很好的对应：每个部分 交收缩函数满足假设卜1 ) 一( + 6 ) ，而每个满足假设卜1 ) 一( + 6 ) 的函数是部分交收缩函 数【1 】若将选择机制定义成一种所谓传递序结构，我们还有更加优美的理论结果：每 个传递序决定的部分交收缩函数满足假设( 1 ) 一一8 ) ，而每个满足假设( 1 ) 一( 二8 ) 的 部分交收缩函数是传递序决定的部分交收缩函数【l 】对基于e e 序的构造，文献【7 】 证明了：每个e e 序决定的收缩函数都满足假设( 1 ) 一( 8 ) ，而每个满足假设 ( 1 ) 一一8 ) 的收缩函数都是一个e e 序决定的收缩函数 文献中一般把类似于上面的结果称为表示定理，为不同的假设系统构造合适的算 子或为所构造的算子寻找公理刻画建立相应的表示定理是信念修正理论研究的核心 仆线性竹念变化的研究 所在。 a g m 关于信念修证算子也做了类似的研究，提出了修正算子的基本假i 殳如f ( 0 1 ) o n ( k o x ) = k o x ( 0 2 ) x e k 国x ( 0 3 ) k o x c n ( k u 工 ) ( 0 4 ) ，x e k = ，c n ( k u 工 ) k o z ( 0 5 ) o ( x ) = 白( _ y ) ) j k o x = k o y ( 0 6 ) k o x = 3 当且仅当叫c h ( 妒) ( e 1 ) 的含义是：对理论进行信念修正的结果仍然是理论( 0 2 ) 的含义是：信念 修正的结果总能包含新信息( 0 3 ) 的含义是：信念扩充是信念修正的上界( 0 4 ) 的 含义是：当新信息与原有信念集协调时，信念修正就是信念扩充( 0 5 ) 的含义是： 如果两条信息的内容相同，同一信念集关于这两条信息修正，得到相同的信念集 ( 0 6 ) 的含义是：修正后的信念集不协调当且仅当加入的新信息是一个永假公式类 似于收缩假设，修正算子还有两条附加假设： ( 0 7 ) k o ( x y ) c n ( ( k o x ) u 姐) ( 0 8 ) 叫茌k o x j c n ( ( k 0 x ) u y ) ) k o ( x a y ) 上述修f 算子的假设与收缩算子假设有着密切的联系，具体而言，如果一个收缩 函数满足假设( 1 ) 一( 上6 ) ，那么通过l e v i 定义决定的修正函数。满足假设 ( 0 1 ) 一( e 6 ) 如果一个收缩函数+ 满足假设一1 ) 一卜8 ) ，那么通过l e v i 定义决定的 修砥函数满足假设( 0 1 ) 一( 0 8 ) 在信念变化的多年研究中，除了上述理论和构造方法外还涌现出其它理论和构造 方法，例如，f u h r m a n n 等人致力于把a g m 理论扩充到能处理新信念是一般语句集合 的研究，文献中一般把相应的信念改变操作称为多扩充、多修j 下和多收缩 1 0 ，1 1 ， 1 2 - ：最近，b o c h m a n n 提出一种新的非单调后承一收缩后承 3 ，其语义结构为迭代 修正提供了合适的研究平台，而后者是信念变化研究尚未解决的问题，另外收缩后承 与信念收缩算子有密切联系，它提供了证明信念收缩表示定理的一种可行途径。 j k 京航守航天人学碳i 。学位沦丈 1 3 本文研究背景和全文安排 虽然信念变化的研究取得了丰富的研究成果，但依然存在许多未解决的问题，如 何用公理假设刻画非线性序所决定的收缩算子就是其一。下面我们对此加以晚明。 从上面我们简要介绍的两种算予构造的基本思想不难看出，它们一个共同的特点 是都含有选择机制，这也是信念变化算子构造中的特性。事实上，这种选择机制是不 可或缺的，信念算予不可能作用在纯粹的集合之上，而应作用在带有选择机制的结构 上，这种选择机制抽象刻画了诸如信念置信度，信念重要性程度等信息，证是选择机 制在收缩算子的构造中提供了信念取舍的信息。如果在a g m 理论提出当初人们对此 还没有充分的认识的话，时至今同这点已成为学术界的共识。 选择机制的数学刻画一般可以采用选择函数和基于序结构，在信念变化研究中有 一种流行的观点“合理的选择是基于序结构的选择” 2 】，所以信念变化的研究许多 是基于序结构进行的。序结构的性质很大程度上决定了基于其所构造的算子的性质， 从而不同性质的序结构所对应的算子往往有着不同的公理刻画及不同的表示定理。信 念修正研究中获得的基于序结构构造的收缩算子表示定理有着一个有趣的现象，它们 所依赖的序或者是线性的或者通过某种变化成为线性的或者可以嵌入线性序中。 近年来，人们一直在寻找非线性序结构所作为选择机制所决定的收缩算子的公理 刻画。这种刻画是否存在依赖于描述公理假设语言的表达能力的强弱。最近，j o h n c a n t w e l l 获得的结果表明【8 】，在一种表达能力相当强的模态语言下这种公理刻画不 存在。在非单调逻辑后承的研究中也存在类似的问题。文献 1 3 1 证明，如果要求公理 假设在语言归约后的模型中保持成立，一般语言下的单射占先模型类不存在公理刻 画，而非单调逻辑中的单射占先模型类对应着信念变化的非线性序结构所决定的算 子。由此可见寻找非线性序结构所作为选择机制所决定的收缩算子的公理刻画是非常 困难的问题。本文将在该方向开展一些研究。 全文安排如下：第二章证明了附加其它条件的非线性序结构部分交收缩的一个 表示定理；第三章定义了有界格上的l e e 序并建立了l e e 序收缩的表示定理：第四 章说明第三章定义的l e e 序不满足线性条件并且初步讨论了非线性l e e 序的分段 线性表示最后全文总结。 1 r 线f - r 信念变化的 f 究 第二章部分交收缩的一个表示定理 本章我们将基于部分交构造建立一个由非线性序选择机制决定的收缩算子的表 示定理，这类选择机制虽然是非线性序的但必需满足某种完备性条件。 2 1 基本概念 本章在经典命题演算的基础上讨论本章中用3 表示命题演算中所有合式公式 的集合c h 是经典命题逻辑后承算子对于任何公式集b ，c n ( b ) = xb 卜x 如果a = c n ( a ) ，那么a 称为理论 首先我们回顾【1 】中的有关定义和结论令口上x = m b lx 壁c n ( m ) 并且对 于任何满足条件m c n b 的满足条件：x c n c n ) 如果b 是一个理论，那么 b 上工的元素都是理论如果一是一个理论，定义哇上= 4 上x lx 爿一0 2 ( 庐) ) ， u 。= u ( a 上) 易知u 。就是a 的所有极大真子理论的集合下面罗列出与本文相关的 一些结果，证明细节见文献【l 】，【2 】， 3 】中的有关部分 引理l ( 2 ) 若a 是一个理论，u 。是4 的所有极大真子理论的集合，圮= r r l 形是 极大协调集并且a 垡矽) 定义函数，：- + 如下：对于任何w ， f ( w ) = 矿n a 那么f ：寸u 。是双射函数 引理2 ( 2 ) 如果a 是理论，工a c n ( 妒) 那么对于任何m u 。x e m 当且仅当 m a 上x 引理3 ( 2 ) ：如果4 是理论，并且x ，y a 一凸( 矿) ，那么a 上x y = a 上x u a 上y 沿用【2 】的定义，函数：3 呻p ( 3 ) 称为理论a 上的收缩函数，( x ) 也记作a + x 下面是关于收缩函数的一些假设+ 是理论a 上的收缩函数，对于任何z ，y 3 6 商京航卒航天人学颅1 ：学位论义 ( 1 ) c n ( a x ) = a x ( 2 ) a x a ( 3 )工任a = a x = a ( 4 )x a x ：= x c h ( 庐) ( 5 ) agc n ( ( a x ) u x ) ) ( 6 )c n ( x ) = c 玎( y ) = = a x = a y l 7 )a x n a y a x y ( + 8 r ) a x a y c n ( a z u a + y ) ( 8 c )y a x a y j a x a y a x 其中，( 1 ) 一一7 ) 引自文献【1 】，( 8 ，) 和( + 8 c ) 最先出现于文献【2 】 令是理论a 上满足所有上述假设的收缩函数定义s 上的二元关系s 如下 口s 当且仅当a _ a ( 口a ) 引理4 ( 3 1 ) ( 1 ) 是3 上的自反和传递关系 ( 2 ) 如果a 玉卢并且a 0 ，那么口卢 口 定义1 ( 3 】) “是一个理论，口是一个公式“称为关于口的j 下规理论当且仅当：口e d 并且如果a s 卢并且诺“，那么对于任何p 3 ，a 口“ 引理j ( 3 ) 如果是极大协调集那么是关于d 的诈规理论当且仅当 一口w 并且a 口w 引理6 ( 3 ) 如果口s ，“是关于口的正规理论，1 1 那么u 是关于卢的币规理 论 引理7 ( 3 1 ) 若口p 并且0 “是关于口的正规理论并且口玑那么0 “ 1 h 线忡f j 念变化的究 如果a 是一个理论满足条仆：对于任何c a 上，y ( c ) ( 的函数 y ：a _ l - - * 舻( 驴( 爿) ) 称为ae 的选择函数y 的补y 。定义为：对于任何x a c h ( ) ，( 爿上x ) = m a 上x i n ，( 一上x ) 冬m 如果y = y ，称，是完备的【2 】 引理8 ( 【2 ) 如果y 是理论a 上的选择函数那么y 是完备的当且仅当对任何 x a c n ( ) 及m u 。满足如下条件：如果n r ( a 上x ) e m ，那么m r ( a 上x ) 定义2 ( 2 1 ) 函数：3 斗p ( s ) 称为理论爿上的选择函数y 决定的理论彳上的部分交收 缩函数当且仅当对于任何x a c ( 庐) ，a x = n r ( a 上工) ；并且对于任何x 仨a 或者 z e c h ( 痧) ，a x = a 理论a 上的选择函数，决定的部分交收缩函数记作n ( ，a ) ，下文中由于我们固定 在一个理论上讨论所以将该记号缩记为l - ( y ) 。后续章节中类似情形均如此处理不再 声明。 令b 是一个集合，r 是b 上的二元关系，s 是b 的子集我们用m a x 。( s ) 表示集 合抄s i v x s ( ( y ，x ) 芒r ) ) 如果存在一个【，。上的二元关系r 满足条件：对于任何 x a c n ( o ) ，r ( a 上x ) = m a x 8 ( 彳上x ) ，则我们称选择函数y 是由二元关系r 决定 的，汜作，= o ( r ) 引理9 ( 1 】) ：如果+ 是理论a 上满足卜1 ) 一卜6 ) 的收缩函数，那么+ 是理论a 上的完备 选择函数y 决定的理论a 上的部分交收缩函数，其中，对任何x a o ( ) ，( 以上z ) = a 上x i a x b t 在本章的下文中，出现的每个y 都指引理9 中定义的完备选择函数，并且决定 y 的收缩函数除了满足假设( 1 ) 一( 6 ) 还满足假设( 7 ) ，( + 8 r ) 和( + 8 c ) 南隶航守航人人学坝i ：学位论文 2 2 预备引理 本节证明的一系列引理为下一节建立表示定理作准备 引理l o 对于任何a ，a c ”( ) 如果a ，u r ( a 上口) ，仨邢么 i g r ( a 上卢) 证明：根据引理l ，存在极大协调集满足“= w n a ，- 1 ae w ，a 口w 根据 引理5 ，w 是关于口的f 规理论因为声e “，所以萑w 根据引理6 ，w 是关于 的正规理论所以_ 1 w 并且4 w 所以爿卢, 4 因为，是完备的 所以“r ( a 上) 口 引理1 1 对于任何口，晟0 a c h ( ) 如果口p ，卢s 0 ，1 , 1 y ( a 上口) 且 口“，贝u 0 “ 证明：由引理l ，存在极大协调集彤满足“= w n a ，- 1 口w ，a 口三w 由引理 5 ，w 是关于d 的正规理论根据引理7 ，因为w ，所以0 w 。故，0 u 口 令t = “，a ) i“y ( a 上口) 并且a 爿一曲( 驴) 定义丁上的二元关系 如下 “，口) ( v ，卢) 当且仅当s 盯并且口v 引理1 2 ，那么a 1 1 n r ( a 上o r ) ，所以gg “导致矛盾所以 是7 上的反自反关系 假设( 虬，a ) - 4 如，) ，( “2 ，户) _ ，那么p s 口，0 卢，卢u 3 根据引理4 ， 0 a 根据弓i 理1 1 ，口“3 所以 r l 口匹”) 记做k 0 l f 线性f 二念坐化的研究 i j l 理1 3 如粜( “，) t 那么( “，p ) m a x ( k 当且仅当口e “并且口 证明：( 仁) 因为口芒“，所以( “，卢) k l 假设( “，西正m a x ( k l ) 那么存在( v ，口) 满足：( “，卢) ( u 口) 并且( p ，口) k 卜i 行l 2 1 a 芒v ，v ，0 s 因为卢a ，根据 引理i i ，口v 导致矛盾所以( “，卢) m a x l ( k l ) ( j ) 假设卢口不成立那么一a 诺a 口a 所以a 口a p u 卢a 一口) 协调 所以存在极大协调集w 满足4 口 卢w ， j a 一口w 所以卢，口e w 所以 a 正w 根据引理1 ，令v = w 1 7 a 那么a 口 v 因为，是完备的所以 v ) ，( a i 口 卢) 所以( v ，a ) t 因为口仨v ，所以( v ，口 卢) k 【r 因为卢v 并 r a ，、卢s 卢，0 t 口2 ( u ，卢) m a x 。( k r ) 所以卢蔓a 口 引理1 4 对于任何口a - c ”( 妒) ，任何m k 【r ，如果m 硭m a x ( k 1 ) ，那么存在 使得n m a x 。( k 1 ) 并且m n 证明：令肘= ( “，卢) 因为( “，) k l ，所以口g “根据引理1 3 ，a 不成立同 引理1 3 的证明，存在理论v 满足条件：( v ，口、卢) k 【r 并且( “，卢) _ ( v ，口a 卢) 因为 a 口，根据引理1 3 ，( v ，口a ) m a x ( k 【r ) 令= ( v ，a a 卢) ，那么m m a n ( k l ) 所以卢曼口并且 a 甚“所以( “口) ，所以“r ( a 上d ) 1 l ( d o m ( m a x ( k l ) ) r ( a 上口) 口 令s = d o r a ( t ) = “i 3 a ( ( u ，口) 丁) ) 定= 3 l s 上的二元关系 - k ，( v ，卢 ) ) 引理1 6 + 是s 上的严格偏序 证明：假设“s 并且“叫那么存在口，卢满足条件：( “，a ) ( “，) 所以口萑“ 矛盾于口“所以( 是反自反的因为 是传递的，所以 t 并且( “，卢) t ，则 诺t ， 则集合u a + 口 l ( “，卢) t ) u - 1 口) u 0 l 满足条件： v ，f ) m a x l ( k l ) 并且( “，妒) ( v ，f ) 所以f 伊，妒v ，f 口，口芒v 所以 f 口 妒a a f l , 0 - 所以” m a x 。( k l ) 所以 p s a 并且d 壁“所以引! k k 假设w 匹m a x ( k l ) ，那么存在v 满足条件：。_ ( + ， 并且v k l 所以存在口满足条件：( “，卢) 盛t ，根据引理1 9 ，存在v e s 满足条件：“ t 因为“s 并且h a 上口，根据引理1 9 ，存在v e s 使得 “ + v 并且( v ，口) t 因为口s 口，所以( v ，口) m a x ( k l ) 所以v m a x ( k l ) 口 2 3 表示定理 定理1 如果理论爿上的收缩函数满足一1 ) 一( - 7 ) ，( + 8 r ) ，( + 8 c ) 那么 = n ( o ( r ) ) 这里尺= u 厶肛s 是玑上的二元关系 是一个有界格，l 是的最大元f 是工的滤子当且仅当，e 三满足 下列条件： 1 1 f 2 z f 并且y f j x a y f 3 x f 并且z y = ，y f ， 如果f 是有界格三的滤子并且0 仨f ，称f 是有界格的真滤子 如果f 是有界格l 的滤子，那么f 是三的真滤子当且仅当f l 定义2l 是有界格，司l 。l 。是厶上的二元关系如果司满足条件 1 v x l o ( 工司工) 2 v x ，y ，：l o ( x y ，y q z j 工q ：) 3 v x ，y ，：l ( x y qz j x 司z 或者y 司z ) 那么口称为l o 上l e e 序设k 是有界格工的滤子如果司还满足如下条件4 ，那 南京航守航天人+ 颅i ：学位论立： 么司称为l 。上关于k 的l e e ，弘 4 v x ，y l ( x k ，y 岳k j x 硇y ) 进一步，司被称为关于k 的满足最小元条件的l e e 序当且仅当其满足如下条件 5 v x ，y l o ( x 岳k ；x q y ) ( 关于k 的最小元条件) 因为q l o l 。并且k l 。互上所以司因此q 也是l 上的二元关系 因为司互l 。厶，所以上述条件2 等价于： 27 v x ，y ，z l ( x y ，y 司z j z 司= ) 显然条件4 等价于4 v x ，y l ( x e k ，x q y j y k ) 引理1 如果z ，y l o 并r x y ，那么x 司y 证明：因为x s y 并且j ，司y ，所以x 司y 口 如果司是厶上关于k 的l e e 序定义k 上的收缩运算如下： v x l ，k x = k 一 y iy q x 这个函数称为司诱导的k 上的收缩函数当需要指 明序时，记作( q ) 显然，k 1 = k 一 j ，1y 司1 ) = k 一= k 定理l 若k 是有界格l 的滤子，司是厶上关于茁的l e e 序，+ 是q 诱导的k 上的收 缩函数那么对于任何x l k x 满足条件： 1 世j 是上的滤子 2 j l ( x 互k 3 x 甚k j k x = k 4 x 1 ；x 芒k x 证明：1 如果y ，z k x 那么y k ，y ，自x 并且：k ，= 盎x 所以y = k 假设 y a 2 司x ，根据l e e 序的条件3 ，y 司x 或者：习x 矛盾所以y ：相x 所以 y a z k x 如果y k + x 并且y 茎：那么y k ，y 稿x 所以z k 假设：司工，那么 x ，y ，= e 厶根据l e e 序的条件2 ，y 司x 矛盾所以z 神x 所以：e x 因为1g 厶，所以1 芒沙l j ，司 所以】c - k t 3 如果x 硅k 那么l c n y iy q x = 所以k z = k 4 如果x 1 根据l e e 序的条件1 ，xqz 所以x y iy 司x 所以j g k x 口 引理2k 是有界格l 的真滤子如梁q 是关于k 的满足最小元条件的l e e 序那么 k = ( y iy 曲0 证明：如果y k 假设y q 0 ，根据条件4 ，0 k 矛盾于k 是l 的真滤子所以 y 曲0 所以y y l iy 袖o ) ，所以k y 三 y 柏o 如果_ y y l i y 曲0 那么_ y 柏0 假设j ，萑k ，那么y 1 所以y 厶因为 o 三0 ，根据条件5 ，y 司o 导致矛盾所以y k 所以 _ y l i _ y 曲0 k 口 定理2k 是有界格工的滤予q 是关于k 的满足最小元条件的l e e 序，是司诱导的 k 上的收缩函数那么对于任何x ，) ，上并且x l o oy q 工 = 司口 定理3k 是有界格l 的滤子如果是k 上的收缩函数，并且满足下列条件：对于任 何x l 1 足工是的滤子 南京航夺航天人学坝i + 学他论文 王k 工k 3 x 芒k j k x = k 4 r lx ，y l o 并助仨k 上 证明：( i ) 因为x l o ，所以x 1 根掘满足的条件4 ，x g k z 所以x 司x ( i i ) 因为y 司：，所以y 芒k ：假设x k z ，因为工s y ，根据满足的条件1 y k ：矛盾所以x 诺k z 所以x 司2 ( i i i ) 因为x y q ：，所以x a y 芒k z 并且z 1 所以工芒k + z 或者y 匹k ：不妨 设x 甓k ：那么x 1 所以x