（基础数学专业论文）命题集的相容性、根及发散性.pdf

命题集的相容性、根及发散性 任燕 x6 1 0 0 9 4 摘要本文涉及三个命题逻辑系统：二值经典逻辑系统，l u k a s i e w i c z 逻辑系 统和逻辑系统，主要内容是在不同的逻辑系统中有重点的讨论命题集的相容 性、命题集的根以及命题集的发散性与相容性之间的关系 在任何逻辑系统中，命题集的相容性都是一个十分重要的问题命题集是相 容的或是不相容的是我们对命题集的好坏最简单也是最直接的分类我们主要关 心的当然是相容的命题集，所以有必要讨论命题集的相容性，从而把不相容的命 题集分离出来本文的第一章主要在c + 系统中讨论了命题集的相容性，详细研 究了两种特殊的命题集一极大命题集和完备命题集，并给出了具体的例子加以说 明，中间穿插说明与二值逻辑系统中相应性质的差异 在逻辑学中，人们把各种具体的命题抽象化为符号，如a ，b ，c 等并可利用 逻辑连接词对这些代表命题的符号( 公式) 进行运算以得更多的公式一个自然的 问题是给定了一组公式r ，从1 1 出发可以“推出”哪些公式? 即，若以d ( r ) 表示全 部r 推论之集，那么d ( r ) 这个集合是怎样的? 王国俊教授在文献【l 】中首次提 出在命题集f ( s ) 中引入伪度量p ，通过p 可以计算d ( r ) 的直径，从而了解d ( r ) 的大体情况同时，王教授也在文献【1 】中首次提出了关于命题集r 的根的概念 从根的意义上看，只要知道了r 的最小推论( 即根) ，把比它大的公式拿来就得出 了r 的全部推论但文【1 】只证明了二值命题逻辑系统中公式集f ( s ) 的每个有限 子集都有根，对于p 系统，命题集r 的根的存在往及性质并未涉及在本文的 第二章中，主要讨论并回答了这个问题此部分中首先给出独立命题集的概念， 并在独立命题集中得到：任一有限的独立命题集的根都存在，给出了根的一般表 达式；任一无限的独立命题集的根都不存在而后又定义了命题集的约简，利用 约简的定义把根的存在性的问题推广到一般的命题集上，对根的概念及其应用作 了较深入细致的分析及推广 既然命题集的相容性是任何逻辑系统所关心的。那么一个自然的问题是：命 题集的相容性是否有程度之分? 命题集的发散度的引进为解决这一问题提出了 一种有利的工具发散度的值在f 0 ，l 】中变化，称发散度为1 的公式为全发散的， 那么显然不相容的命题集是全发散的反过来，全发散的命题集是否必为不相容 的? 这是一个尚不清楚的问题本文的第三章中，在我们所涉及的三个系统中均 回答了这一问题关于命题集的相容度是否有程度之分。以及关于命题集的相容 度的计算问题，文【4 q 针对l u k s i e w i c z 逻辑系统中的有限命题集提出了相容度函 数，用来刻画有限命题集的相容度，对于无限命题集文( 4 0 】并没有给出相容度函 数第三章的最后一节受文【4 0 】的启发，讨论了二值经典逻辑系统命题集的相容度 的计算问题，给出了任意命题集相容度函数，同时也把文【4 0 】所给的函数推广到 一般命题集上同时也可以看出，这种推广在满足紧致性的系统中具有一般性 关键词：二值经典逻辑系统l u k a s i e w i c z 逻辑系统c + 逻辑系统( 不) 相容 命题集极大命题集完备命题集独立命题集根约简真度发散度相容度 i i c o n s i s t e n c y ，r o o t sa n dd i v e r g e n c yd e g r e e s o fs e t so f p r o p o s i t i o n s 1 y a nr 启n a b s t r a c ti nt h i sa r t i c l e ，t h r e ep r o p o s i o n a ll o g i c a ls y s t e m s t h ec l a s s i c a l ，l u k a s i e w i c za n d c + p r o p o s i o n a ll o g i c a ls 珀t e m s - a r ei n c l u d e d w es t u d yc o n s i s t e n c y , r o o t sa n dd i v e r g e n c y d e g r e e so fs e t so fp r o p o s i t i o n si nt h e s es y s t e m s w e d i v i d et h i sa r t i c l ei n t ot h r e ec h a p t e r s t h e q u e s t i o nw h e t h e rat h e o r y ( ap r o p o s i o n a ls e t ) w ea r ed e a l i n gw i t h i sc o n s i s t e n t i so n eo ft h ec r u c i a lq u e s t i o ni na n yl o g i c a ls y s t e m s ri ss a i dt ob ec o n s i s t e n ti fd ( r ) ， o re l s ei ti si n c o n s i s t e n t w ea l w a y sp a ya t t e n t i o nt ot h ec o n s i s t e n tp r o p o s i o n a ls e t s s o ，i ti s n e c e s s a r yf o r1 1 8t os t u d y t h e c o n s i s t e n c yo f p r o p o s i o n a l s e t st oa p a r tf r o mt h ei n c o n s i s t e n c y p r o p o s i o n a l s e t s i nt h ef i r s tc h a p t e ro ft h i sa r t i c l e ，w ed i s c u s st h ec o n s i s t e n c yo f p r o p o s i o n a l s e t si nc + s y s t e m sa n dm a i n l ys t u d yt w os p e c i a la n di m p o r t a n tp r o p o s i o n a ls e t s - m a x i m a l p r o p o s i o r m l s e t sa n d c o m p l e t ep r o p o s i o n a ls e t s s o m ee x a m p l e s a r eg i v e nt of u r t h e re x p l a i n t h e s et w os e t s a tt h es a l n et i m e w ed i s t i n g n i s ht h ec + s y s t e m sf r o mt h ec l a s s i c a ll o g i c a l s y s t e mo n t h ea b o v ea s p e c t a si sw e l lk n o w nh u m a n r e a s o n i n g i sa p p r o x i m a t er a t h e rt h a n p r e c i s e i nn a t u r e t h e r e i san a t u r a lq u e s t i o ni na n yl o g i c a ls y s t e m ：s u p p o s et h a ta t h e o r yf i s g i v e n ，t h e nw h i c h f o r m u 】a sc a nb ed e d u c e df r o mr b yu s i n g d e d u c t i o nr u l e s ? p r o f e s s e rw a n gh a sp r o p o s e dt h e c o n c e p to fr o o t so fp r o p o s i o n a ls e t sf i r s t l yi n 【4 f r o mt h es e n s eo fr o o t s ，w es e et h a ta l lo f f - - c o n s e q u e n c e sc a nb eo b t a i n e d a 8l o n ga 暑t h el e a s tf - c o n s e q u e n c e ( r o o t 、i sk n o w n n o t i c e t h a t 【1 o n l yp r o v e dt h a te v e r yf n i t ep r o p o s i o n a l s e th a sr o o ti nc l a s s i c a ll o g i c a ls y s t e m s w e s t i l ld o n tk n o wt h ee x i s t e n c eo fr o o t sa n di t sc h a r a c t e r i s t i c si nc 4s y s t e m i nt h es e c o n d c h a p t e ro ft h i sa r t i c l e ，w es t u d ya n da n s w e rt h i sq u e s t i o n a tf i r s t ，w eg i v et h ed e f i n a t i o no f t h ed e p e n d e n tp r o p o s i o n a ls e t s ，a n dg e tt h i sc o n c l u s i o no nt h ed e p e n d e n ts e t s ：a n yf i n i t e d e p e n d e n ts e t h a sr o o t s ，o t h e r w i s ea n yi n f i n i t ed e p e n d e n ts e th a sn or o o t s s e c o n d l y , w e d e f i n et h er e d u c to ft h ep r o p o s i o n a ls e t s w i t ht h eh e l po ft h i s c o n c e p t ，w ee x t e n dt h e a b o v ec o n c l u s i o nt oa n yp r o p o s i o n a ls e t m o r e o v e r ，t h eq u e s t i o no ft ow h a te x t e n taf u z z yt h e o r yi sc o n s i s t e n to ri n c o n s i s t e n ti s a l s oo n eo ft h ec r u c i a lq u e s t i o ni na n y f u z z yl o g i c a ls y s t e m 【qf o r t u n a t e l y , t h ei d e ab a s e do n t h ec o n c e p to f d i v e r g e n c ed e g r e e so ft h e o r i e sc a nb eu s e dt os o l v et h i sp r o b l e m d i v e r g e n c e d e g r e e so ft h e o r yrc h a n g ef r o m0t o1 , pi ss a i dt ob ef u l l yd i v e r g e n ti fi t sd i v e r g e n c e d e g r e ei s1 o b v i o u s l y , e v e r yi n c o n s i s t e n tt h e o r yi sf u l l yd i v e r g e n c e h o w e v e r ，i sf u l l yd i v e r g e n c et h e o r i e st ob ei n c o n s i s t e n t ? t h i si sau n c l e a rp r o b l e m i nt h et l f i r dc h a p t e ro ft h i s i i i a r t i c l e t h i sp r o b l e ma r et ob es o l v e di nt h et h r e es y s t e m s k e y w o r d s ：t h e c l a s s i c a ll o g i c a ls y s t e m ，l u k a s i e w i c zl o g i c a ls y s t e m ，c + l o g i c a l s y s t e m ，( i n ) c o n s i s t e n t ，t h em a x i m a lp r o p o s i o n a ls e t s ，t h ec o m p l e t ep r o p o s i o n a ls e t ，t h ed e - p e n d e n ts e t s ，r o o t s ，r e d u c t ，t h et r u t hd e g r e e ，t h ed i v e r g e n c ed e g r e e ，t h ec o n s i s t e n td e g r e e i v 前言 通常把近代数理逻辑的思想溯源到l e i b n i z ( 1 6 4 6 1 7 1 6 ，德国) 的“一般文字”， 他力图建立一种精确的，普遍适用的科学语言，并且寻求一种推理演算，以便能 够用计算来解决辩论和意见不一致的问题如今，数理逻辑的理论研究已经空前 繁荣，并且在应用上也取得了辉煌的成绩【4 2 ，4 3 逻辑推理属于确定性推理这种 推理以其严谨性与形式化为特点正因为如此，它可以编制一定的程序而实现， 即，可以通过计算机的运行而完成比如，基于归结方法的逻辑推理就是定理机 器证明的基础【2 6j 另一方面，近似推理属于不确定推理，由于它允许一定程度的 误差存在，所以有更多的灵活性和更广泛的应用领域【2 4 即使在经典的二值逻 辑学中近似推理都是重要的研究课题【2 7 】，至于在多值逻辑与模糊逻辑中，近似推 理更有直接的应用，比如，作为近似推理的一种特殊形式，模糊推理已经成为模 糊控制的理论基础 模糊推理是模糊控制的基础，而各种各样的蕴涵算子则是模糊推理的数学工 具，因而继z a d e h 关于模糊推理的开创性文章 3 9 】问世后有众多学者从不同的应 用背景出发提出了不同的蕴涵算子，王国俊教授在文献模糊命题演算的一种形 式演绎系统中引入了一种形式系统c ，针对这种系统修正了k l e e n e 的蕴涵算 子，引入了新的蕴涵算子风不同的蕴涵算子确定不同的逻辑系统，有着不同的 公式集和赋值空间，由于赋值域中含有多个不同的元素，公式的真度也有不同的 类型，关于区分公式可靠程度的思想早在1 9 5 2 年就由r o s s e r 和t u r q u e t t e 提出 4 l 】， 而后许多学者从不同的角度提出了公式的程度化真确度的方法文献【4 ，2 1 】就连 续值域的情形。利用积分方法建立了公式的积分真度理论，如果积分真度越大， 相应公式的可靠程度也越大而文【37 】中基于测度理论引入了适合多种系统的逻 辑公式的真度的概念，并通过通用逻辑度量空间概念在全体公式集上引入了伪距 离，为逻辑空间的度量化奠定了基础，也为近似推理提供了一种可能的框架 多值逻辑的产生与发展给近似推理的研究提供了更广阔的空间，近似推理的 方法很多，针对不同的应用背景人们提出了各种不同的近似推理的理论 z a d e h 于1 9 7 3 年在文献 3 9 1 中首次提出了基于模糊集思想的近似推理理论，但是，近似 推理并不一定要与模糊集理论相联系，比如，王国俊教授在其专著g 非经典数理 逻辑与近似推理的积分语义学一章所提出的近似推理的主体部分就不依赖于模 糊集理论不过，无论哪种近似推理( 也包括确定性推理) ，都有一组作为出发点的 假设集r ，如果从r 出发能推出每个结论来，特别是从r 出发能推出矛盾式来，则 这种r 自然是没价值的，这时称r 是不相容的，否则称r 是相容的确切地说， 若以d ( r ) 表示全部r 一推论之集，以，表示全体逻辑公式之集，则r 叫相容的当 且仅当dc p ) ，那么，由f 出发究竟可以推出哪些逻辑公式，即d ( r ) 这个集合 是怎样的7 相容的命题集( 公式集) 在不同的系统中有什么样不同的性质? 命题 集的相容性可否有程度之分? 这些都是值得回答的问题，尤其是后者，v n o v a k 在作了若干探索而未能得出有价值的结论后指出：这是一个不容易的工作但本 文则较细致地讨论并回答了以上各问题 本文主要涉及二值经典逻辑系统，l u k a s i e w i c z 逻辑系统以及p 逻辑系统， 对文献【4 】中所涉及的概念比如：真度、伪距离、发散度、根、相容度等在以上三 个系统中作有针对性的讨论正文对三个系统中的基本知识不作赘述 文章的第一部分主要是系统命题集的相容性，重点讨论了两种相容的命 题集极大命题集与完备命题集，给出他们的重要性质及其典型的例子，并且说 明了c 系统与二值系统命题集相容性之间的差异而后讨论了由相容命题集确 定的一类凰一代数及其滤子，指出了极大滤子和素滤子与极大命题集和完备命题 集之间的对应关系 第二部分研究口系统命题集的根先定义了独立命题集，并在独立命题集 的基础上讨论了根的存在性及其性质，继而通过命题集约简的概念把根推广到一 般的命题集上从而对根的概念及其性质作了较深入的分析及推广并且说明了 在：值逻辑系统中根的情况 本文的第三部分详细讨论了l u k a s i e w i c z 系统和系统命题集的发散性与相 容性之间的关系通过具体的例子指出存在全发散而且相容的命题集并讨论了 两种系统间发散度和公式的真度的概念之间的差异最后，讨论了二值逻辑系统 命题集的相容度 这样全文从不同的角度讨论了命题集的性质 2 第一章系统命题集的相容性 命题集是相容的或是不相容的，是我们对命题集的好坏最简单也是最直接的 分类如果从一组假设集f 出发能推出个每结论，特别的从r 能推出矛盾式，则 这种f 自然是没有价值的，这时称r 是不相容的，否则称r 是相容的而我们主 要的兴趣当然是在相容的命题集上本章的研究主要集中在系统上，中间穿 插指出在系统与经典逻辑系统有关相容性的不同性质 1 1 相容命题集与不相容命题集 我们首先对这两种命题集作具体的讨论 定义1 1 _ 1 设c 是f ( s ) 中任一矛盾式，若r 卜e ，则称r 是不相容的，否则称 r 是相容的 例1 1 2 设r = 且，一a ) ，对任意矛盾式c ，有卜a _ ( 一且_ + g ) ，所以r 卜g ，故 r 是不相容的 例1 1 3 ( 1 ) 若r = 佃) p 为任一原子公式，则r 是相容的 假设r - 是不相容的，那么对任一矛盾式c ，有p 卜c 。由广义演绎定理 3 1 知卜p 2 _ + g 即卜叩2 ，由完备性可知 1 p 2 ，即 p - - 41 p ，而当v ) = ；时， p 叩) = 1 ，所以矿一p 2 故( p ) 是相容的 ( 2 ) 命题集f = 切- ，p 2 ，鲰， ( 即r 是由全体原子公式组成的命题集) ，足相 容的 ( 3 ) 圣是相容的 而由定义1 1 1 可知，若f 是不相容的命题集，c 为任一矛盾式，因为i - c 叶a 所以r 卜a 成立于是我们有以下的结论： 定理l 。1 4 设f f ( s ) ，则以下结论等价 ( 1 ) r 呢不相容的 ( 2 ) c a f ( s ) ，r 卜一4 ；即r 卜a n y t h i n g ( 3 ) d ( r ) = f ( s ) ( 4 ) 3 a f ( s ) ，f 卜a 且r 卜、a ( 5 ) v a ，b p ( s ) ，f 卜- a 兰b 这里r 卜a 兰b 是r 卜a - - + b 且r 卜b - a 的缩写 上面五条的等价性显然，证明省略 3 定理l 1 5 设r f ( s ) ，则以下结论等价 ( 1 ) r 是相容的 ( 2 ) 设c 为任一矛盾式，则r 矿c ( 3 ) d ( r ) f ( s ) ( 4 ) v a f ( s ) ，r 卜a 与r 卜，a 不能同时成立 ( 5 ) d ( r ) 也是相容的 设n 为全体赋值之集，v v q ，v ( a ) = l 与v ( a ) l 不可能同时成立，所以对 于不相容的命题集r ，砂q ，v a r 使得”( a ) = 1 ，但对于相容的命题集，有下面 的结论 定理1 1 6 ( 满足性定理) 设r 是f ( s ) 中的相容的命题集，则存在赋值u 使得 v a f ，v ( a ) = 1 定理1 1 7 ( 紧致性定理) 1 1 是f ( s ) 中相容的命题集当且仅当1 1 的每个有限子 集都是相容的 证明：必要性显然，只需证明充分性假设r 是不相容的，由定理l _ 1 4 可 知，3 a f ( s ) 使得i 、卜a 且r 卜，a 那么存在r 的有限子集r 1 ，r 2 ，使得r l 卜a 且r 2 卜，a ，所以存在r 的有限子集r o = r 1u r 2 ，使得f o 卜a 且r o 卜一a 由定理 1 1 4 可知是工1 0 是不相容的这与r 的每个有限子集是相容的矛盾所以r 是相 容的 推论1 1 8 设f f ( s ) ，r 是不相容的当且仅当存在r 的有限子集r o ，使得r o 是不相容的 定理1 1 9 设1 1 f ( s ) ，r 是不相容的当且仅当存在公式a 1 ，a 2 ，a 。，使得 钟。川o o a ：为矛盾式 证明；由推论1 1 8 可知，r 是不相容的当且仅当存在r 的有限子集r o ，使 得i 、o 是不相容的不妨设r o = az ，a z ，a 。) ，又r o 是不相容的当且仅当1 1 0 - g ( 这里c 为任一矛盾式) 即 a l ，a 2 ，a 。) 卜g 当且仅当卜钟。坞o o 镌_ + g ， 当且仅当田o a ；o o 以为矛盾式 当r = a t ，a f ( s ) 时，由定理1 1 9 可知r 是不相容的当且仅当4 2 为矛盾 式对于公式a ，有下面的结论 定理1 1 1 0 系统中，a 2 为矛盾式当且仅当、a 为 一重言式 证明： a 2 为矛盾式当且仅当q ，v ( a 2 ) = 0 即v ( 似_ 一a ) ) = 0 即 v ( a ，a ) = 1 , v ( a ) sv ( 一 ) ，所以u ( a ) ；即v ( 一a ) 25 ，所以，a 是5 一重畜式 4 例1 1 1 1 ( 1 ) f = p a 邓) 是不相容的，因为一( p a l p ) 足5 一重言式 ( 2 ) r = p a 、( 印o ( 叩- + p ) ) ) 是不相容的 注1 1 1 2 在经典逻辑中。由单个公式组成的命题集 舢，只要a 不是矛盾式， 那么 a ) 就是相容的因为此时a 矿c ( c 是任一矛盾式) 但在系统中，由上面 的例子可知，单个公式组成的命题集 a ) ，在a 不是矛盾式是情况下，也可能是不 相容的 经典逻辑中经常用到下面的命题 命题1 1 1 3 设r f ( s ) 且a f ( s ) ，f u 舢是不相容的当且仅当r 卜一a 但在c 系统中，此命题不成立比如设r = g ) ，a = pa 砷，p 和q 是两个 不同的原子公式，那么r u 舢是不相容的，因为由例1 1 1 1 可知 a ) 是不相容 的，但是f 矿，a 因为假设r 卜一4 ，即当q 卜pv 叩时，由广义演绎定理及 系统的完备性可知 q 2 _ + pv 、p 但当取v n ，使得p ( 口) = 1 ，”( p ) = ；时，有 l ，( 叮2 - + p v 巾) = 1 一；= 1 ，所以q 矿p v 1 p 即f 矿，a 与命题1 1 1 3 相对应，在系统中有下面的结论： 定理1 1 1 4 设r f ( s ) 且a f ( s ) ，f u 舢是不相容的当且仅当1 1 卜，a 2 证明； r u ” 是不相容的当且仅当r u 舢卜a n y t h i n g ，特别的，对于任一 矛盾式g ，r u 似) 卜c 由广义演绎定理可知r u a ) 卜c ，等价于r 卜a 2 一c ，即 r 卜- 1 2 1 2 极大命题集与完备命题集 本节讨论两种特殊的命题集：极大命题集与完备命题集它们的定义分别是： 定义1 2 1 命题集r 是极大的( m a x i m a l ) ，如果1 1 是相容的而且v eef ( s ) ，若 1 1 ，那么是不相容的或r = 定义1 2 2 命题集r 是完备的( c o m p l e t e ) ，当且仅当v a ，b f ( s ) ，i 、卜a _ b 或r 卜b - + a 由以上两个定义可知，如果命题集r 是极大的一定是相容的( 通常称r 极大 相容) ，但命题集r 是完备的，则未必是相容的，比如，f ( s ) 就是完备的 说明1 2 3 在文献【1 中的完备命题集的定义与我们这里定义1 2 2 不一样， 它等价于我们这里的极大命题集的定义，而我们这里的两个定义与文献【2 】和【3 】 的一致 定理1 2 4 设命题集f 是极大命题集，a f ( s ) 且a 掣r ，则f u 埘是不相 5 容的 证明；因为a 岳r ，所以r r u a ) 且r r u 舢，又因为r 是极大的，所 以r u 舢是不相容的 定理1 2 5 若命题集r 满足 ( 1 ) r = d ( r ) ( 2 ) v a f ( 司，f 卜a 与r 卜，a 有且仅有一个成立 那么命题集r 是极大的。 证明：假设命题集r 满足( 1 ) ，( 2 ) ，由( 2 ) 可知r 是相容的设f ( s ) 且r ， 当f 时，存在a e ，但a r ，由( 2 ) 可知一a r 所以、a e ，由定理1 1 2 知是不相容的，所以r 是极大的命题集 值得注意的是；在经典的逻辑中定理1 2 5 中的两个条件是极大命题集的充要 条件【l 】，但在系统中此命题的逆不成立比如； 例1 2 6 设f = ( p 1 + ，p 1 ) a ( ，p 1 p l ) ，( p z _ 1 2 ) a ( 叫2 - p 2 ) ，) ，0 ； 最t = 1 ，2 ，) 因为r 有且仅有一个模型p ：”眩) = ，( i = i ，2 ，) ，所以r 是相容 的，进而d ( f ) 也是相容的而且也有且仅有一个模型，设v a f ( s ) ，且且掣d ( f ) ， 那么v 不是它的模型，从而命题集d ( r ) u 埘没有模型，所以d ( r ) u 肿是不相 容的，由极大命题集的定义可知d ( r ) 是极大命题集但它不满足定理1 2 5 中的 条件( 2 ) ，比如对公式p l ，p l 与1 p 1 均不在d ( r ) 中 由上面的例子，可以得出另一个极大命题集的充分条件 定理1 2 7 若命题集r 满足 ( 1 ) f = d ( r ) ( 2 ) d ( r ) 有且仅有一个模型 那么r - 是极大命题集。 这个定理的条件与我们的直觉是一致的，我们知道相容的命题集一定有模 型，而随着命题集中公式个数的增加，其模型的个数在逐渐的减少，极大命题集 是相容的而且含有极大数日的公式，所以它的模型数应该是极小的是不是极大 命题集只能有一个模型? 也即，定理1 2 7 的逆命题是否成立，需进一步的研究 现知道的是在经典的情形下逆命题是成立的由上面的两个定理我们得出第三个 极大命题集的充分条件 推论1 2 8 若命题集r 满足 6 ( 1 ) f = d ( r ) ( 2 ) 对任一原子公式p , p dc r ) 与1 p ed ( f ) 有且仅有一个成立 那么1 1 是极大命题集 证明：由条件( 2 ) 可得到1 1 有且仅有一个模型，再由定理1 2 7 可知r 是极 大命题集 由文献【1 】知推论1 2 8 中的两个条件在经典的二值逻辑系统中是极大命题集 的充要条件，所以通过定理1 2 5 ，定理1 2 7 和推论1 2 8 我们得到了经典逻辑系统 中极大命题集的三个等价刻画，尤其由推论1 2 8 在二值逻辑系统中可得如下命 题： 命题1 2 9 在经典逻辑系统中，r 足极大命题集当且仅当i 、可以表示成 d ( q 1 ，q 2 ，) ) 的形式这里q i - p i 或q = 一p i , p i 为任意原子公式。 这样若用u 表示全体自然数所组成的集合n 的基数，那么在经典逻辑系统中 极大命题集的个数为2 “个 例1 2 t 0 设命题集r = p l ，p 2 ，p 一 ，即r 是由全体原予公式组成的集 合，那么由推论1 2 8 知是d ( f ) 极大命题集 定理1 2 1 1 命题集r 是完备的当且仅当v a ，b f ( s ) ，若1 1 卜a v b ，那么r 卜j 4 或r 卜b 证明： 先证充分性c 系统中，v a ，b f ( 5 ) ，均有卜- 4 b ) v ( b - + a ) 【4 】 又因为命题集f 满足y a ，b f ( s ) ，若r 卜a vb ，那么r 卜a 或r 卜b 所以 i 卜a _ + b ，或i 卜b - a 再由定义1 2 2 可知，命题集r 是完备的 再证必要性设r 是完备的，且r 卜a v b ，当r 卜a b 时，因r 卜b - b ， 所以r 卜a v b - + b ，由m p 规则得r 卜b 当r 卜b - a 时，由r 卜a + a ，所以 r 卜b v a _ + a ，再由m p 规则得r r a 定理l 2 。1 2 如果命题集f 有且仅有一个模型，那么i 、是完备相容的命题集 如例1 2 6 和例1 2 1 0 中的工1 都是相容完备的命题集从而也可以得出：如果 d ( r ) 是极大的命题集，那么r 就是完备命题集 定理1 2 1 3 设命题集r 是完备的，若有命题集，满足r ，则e 也是完备 的 证明： 因为工是完备的，所以v a ，b f ( s ) ，f 卜a b 或r 卜b - + a ，同时 又由于r e ，所以有卜a - + b 或e 卜b a 故e 也是完备的 定理1 2 1 4 如果r 是相容的命题集，则存在包含1 1 的极大命题集 7 证明：设 c = f ( s ) l r e ，且d ( e ) f ( s ) ) 因为r c ，所以c d 又( c ，) 是偏序集，设 e i h n 是c 中的任一链，且令 e = u i e i e i 显然e f ( s ) 且r 假设c 为任一矛盾式，且e 卜g ，知存在e 的有限子集o ，使得e o 卜g ，而o 必包含在某一e i 中，这与e 矿c 矛盾所以 矿a ，即c 由z o r n 引理可知，c 中有一极大元，比如e 4 ，则+ 即为所要求 的包含r 的极大命题集 定理1 2 1 5 设r f ( s ) ，且存在公式a f ( s ) ，p 矿a ，则存在一完备的命题集 1 1 ，使得r i 、，且r 矿a 证明：令 ，= f ( s ) l r 且矿a ) 因为1 1 ，所以，0 又( ，) 是偏序集，令 t i t ，) 是( ，) 中任一链，则 e = u 州e 为此链的上界 因为显然有r ，假若ei - a ，必存在e 的有限子集e o ，使得e o 卜a ，同时 e o 必包含在某个e t 中，所以存在t j ，t 卜a 这与 t i t n ，矛盾因此由 z o r n 引理，中存在极大元比如设为一，下证r ，是完备的 否则，假设存在b ，g f ( s ) ，使得r ，矿b - g ，且一矿c _ + b 令 r 1 = r u b g ) ，1 2 = r 。u g 日) 则r ，i 、l ，且r ，f 2 但工、l 与r 2 至少有一个在，中，即r l 矿a 与r 2 矿a 至少有 一个成立要不然，如果工1 l 卜a 且f 2 卜a ，则 i 山。，a j 。，a j 。一使得 山。，a j ：，a j 。，b - g ) 卜a | a i l ，a i 2 ，a i 。r ，使得 a 。，a i 。，一，a i 。，c _ b ) 卜a 由广义演绎定理可得 卜碍。o 镶o o a 五o ( b - g ) 2 a ；卜a 嚣o a 毳o a 乙o ( g b ) 2 - 且 所以卜( 穆， 缘o o ao ( b g ) 2 ) v ( a io 毛o - - o a 乙o ( g - b ) 2 ) a 又卜坞，o 椎o o 缘o a j0 4 乏o - - o a 乙o ( ( b 叶g ) 2 ) v ( c _ b ) 2 ) ( 坞。o 椎o 。_ 0 4 炙 ( b g ) 2 ) v ( a a 毛o o a 乙o ( g - b ) 2 ) 和卜g ) 2 v ( g - + b ) 2 成立 所以，卜坞。o 坞。o o 镶。鬈。o a 乞o o 镌_ + a 即t 山。，山。，如。，a 。，a 。，a i 。) 卜a 所以r 卜a 与r j 矿a 矛盾故r l 与f 2 8 至少有一个在，中，这与f ，是，中的极大元矛盾所以不存在公式b ，c ，使得 r ，矿b - + g ，且一矿g _ + b ，即v b ，g f c s ) ，r ，卜b - g f 。卜c _ b ，说明一是完 备的 定理1 2 1 6 如果命题集r 是极大的，那么r 是完备的 证明：r 是极大的因而是相容的命题集，所以必存在公式a f ( s ) ，使得 r y a ，由定理1 2 1 5 可知存在一个完备的命题集f ，使得r r ，且一矿a ，由此知 一是相容的命题集。又由f 是极大的得r = f ，所以r 也是完备的命题集 1 3 由相容命题集所确定的一类风代数及其滤子 文献【4 】以c * - l i n d e n b a u m 代数为背景，引入了丑。代数，而文献 1 1 中给出 了硒代数如下的特征定义： 定义1 3 1 月。代数的定义t 设m 为有界分配格、是m 上的一元运算v ，_ 是m 上的二元运算，则( m ，一，v ，_ + ) 是代数的充要条件是以下性质成立： ( t ) o - + b = 一b _ + 、a ( i i ) a 一( 6 + c ) = 6 - + ( o + c ) ( i i i ) 8 - - + b vc = ( a - 6 ) v ( o _ + c ) ( 如) a 6 铮+ b = 1 ( ) 似一b ) v ( ( 口_ 6 ) - + ，o vb ) = 1 定义1 3 2 设r 是p 系统中的命题集，v a f ( s ) ，记【a i r = b i f 卜a i b ) ， 即l a j r 是所有与公式ar 一等价的公式之集r 可证等价类的全体记为卸，即 研= r f ( s ) ) 这里r 卜a i b 是1 1 卜a _ b 且f 卜b - + a 的简写 显然，若工是不相容的命题集，由定理1 1 4 可知y a ，b f ( s ) ，r 卜a ；b 所 以i 目l = 1 ，也就是v a f ( s ) ，【a l r = f ( 观这样的i 、可证等价类是我们不想要 的，所以本节下文中我们约定：r 是给定的相容命题集 定理1 3 3 v a ，b f ( 习，在工r 上定义r _ 【b l r = 口_ b r a rv 【翻r = m v 捌r ， 一刎r = ，r ，则如是月。代数 特别的，当f = 日时，岛是c 一l i n d e n b a m n 代数【卅。简记为【a 】 为证明此定理，我们需要以下两个引理 弓l 理1 3 4 设1 1 卜- a ，捉9 v b f ( s ) ，r 卜b _ 且 证明：设r 卜a ，因为卜a - + 旧_ a ) 成立，由m p 规则立即可得r 卜b - a 9 引理1 3 5r 卜a 当且仅当【a l r = d ( r ) 证明：设r 卜a ，v b r ，由定义1 3 2 可得1 1 卜a e b ，由m p 规则立即可 得r 卜b 所以h r d ( r ) 另一方面，v b dc r ) ，即r 卜b ，由引理1 3 4 知 f 卜a _ + 日，又r 卜a ，所以再由引理1 3 4 知r 卜b _ a ，所以r 卜aeb ，即 b r ，所以d ( r ) = r 所以我们就有如果r 卜a ，那么就有r = d ( r ) 反之，若陋】r = d ( r ) ，因为a r ，所以a d ( r ) 即工、卜a 特别的，设t 为任一重言式，因为r 卜t 总成立，所以闭r = d ( r ) 下面我们证明定理1 3 3 证明：( 1 ) 证明幻是有界分配格 在所中定义序：【刎rs 吲r 当且仅当工1 卜a - + b ( a ，b f ( s ) ) 易证是卸 上的偏序当川r 陋】r 时，r fa - + b 同时r 卜b - + b ，所以得r 卜a v b 寸b 另一方面r 卜b + av b 总成立，所以r 卜a v b ；b ，即【av 矧r = 【引r 这说 明v 是关于序s 的如中的上确界由引理1 3 4 和引理1 3 5 知：v b f ( s ) ，若 a d ( r ) 均有r 卜b _ + a ，即【b 】r 【州r ，又【a l v = d ( r ) ，即d ( r ) 是( l r ，) 中的 上界。记为1 r ，相应的可得( l r ，) 中的下界o r = 【一棚r ( a d ( r ) ) l r 的分配性由 的分配性可得所以计是有界分配格 ( 2 ) 验证研满足定义1 3 1 中的五条性质 设r ， b 】r ，【q r l r ，( i ) ，( 毗( 倒) ，( ”) 由定义可直接验证，下面验证( 如) 刎r 【b 】r 当且仅当r 卜a - b 当且仅当陋_ + b r = 1 r 当且仅当r - + 旧】r = l r 由上面的证明可知研是凰代数，称此岛代数为由r 确定的r o 一代数它 是c - l i n d e n b a u m 代数的推广 推论1 3 6r 是完备的命题集当且仅当卸是线性的 证明： r 是完备的命题集当且仅当v a ，b f ( s ) ，ff - a _ + b 或f 卜b 一+ 4 当且仅当v a ，b f ( s ) ，【州r r 或【矧r r 当且仅当三r 是线性的 下面给出冗。一代数中的滤子的概念 定义1 3 7 ( 1 ) 设m 是r o - 代数f m ，若忱，y m ，有( t ) l f ，( t t ) z f 且z - y f ，则y f ，那么就称f 为m 上的一个滤子 ( 2 ) m 上的滤子f 是真的当且仅当0 岳f 1 0 ( 3 ) 场一代数m 的真滤子f 是素的当且仅当若v x ，f 蝎zv f ，则z f 或g f ( 4 ) 凰一代数m 的真滤子f 是极大的，若f x ，且x 为m 的一个滤子，则 f = x ，或x = m 此处给出的凰一代数的概念与文献【1 6 ，【l7 】， i s 】中的一代数的m p 滤子的 概念一致，与一般格论意义下的概念不一致，由文献【1 8 】可知，如果f 是m 的 m p 滤子