（逻辑学专业论文）多值逻辑的联结词、系统和代数语义.pdf

摘要 多值逻辑的研究主要分为直观语义，系统构建和代数语义三个部分，本报告 大致也是围绕这三方面展开，内容共分三章；第一章介绍了多值逻辑的联结词和 多值逻辑系统，对历史上曾提出的多值逻辑给出了一个全面的列举，使读者可以 看到多值逻辑提出和发展的概貌。本章对这些逻辑的联结词和语义进行了介绍， 画出了逻辑联结词的真值表，便于不同逻辑之间进行比对。 第二章构建了一个n + l 值多值逻辑h i l b e r t 系统。构建逻辑系统可以采用多 种方法，如用m v - 代数，用r o s s e r _ t u e q u e u e 方法等等，也可h e n k i n 极大一致集 方法。但是极大一致集方法曾用来证明l u k a s i e w i c z 3 值逻辑的强完全性，而这 种证明没有推广到其他多值逻辑。在这一章，作者给出了一个可以推广到其他有 穷值逻辑的一个证明方法，并证明了系统的强完全性，这是本文的创新之处。 第三章对多值逻辑与其他逻辑的代数形态进行了介绍。逻辑代数是从代数语 义的角度开展对逻辑进行研究，呈现更抽象和更一般化的趋势，出现了抽象代数 逻辑的分支。从国外发表逻辑学论文看，逻辑代数的研究日渐成为现代逻辑研究 的主流。因此，这一章对国外的代数逻辑的研究状况给以较详细的介绍，对众多 的概念进行了厘清，介绍了一些主要成就，为以后的研究打下基础。 关键词：多值逻辑；逻辑联结词；逻辑代数；抽象代数逻辑。 a b s t r a c t 1 1 l es t u d yo fm a n y - v a l u e d l o g i cc o n s i s t sm a i n l yo fd i r e e t v i e w i n gs e m a n t i c s , c o n s t r u c t i n gl o g i cs y s t e m sa n da l g e b r a i cs e m a n t i c s s ot h i sr e p o r ti sc o m p o s e do f t h r e ec h a p t e r so nt h et h r e ea s p e c t s i nf i r s tc h a p t e rii n t r o d u c es e v e r a lm a n y v a l u e d l o g i c sa n dt h e i rc o n n e c t i v e s a n d 出a wu pt h et r u t h - v a l u et a b l e so f t h e s ec o m i c e t i v e s i nt h es e c o n dc h a p t e ric o n s t r u c t e ai 件1 一v a l u e dl o g i cs y s t e m t h e r ea r em a n y m e t h o d st oc o n t r u c tl o g i cs y s t e m s , s u c ha sm v - a l g e b r a ，r o s s e r o t u e q u e t t em e t h o d ， a n dh e n k i n sm a x i m a ls e te t c mm e t h o do f h e n k i n sm a x i m a ls e th a v eb e e n u s e dt o p r o v et h ec o m p l e t e n e s so f l u k a s i e w i e z s3 - v a l u e d1 0 9 i e b u tt h ec l a s s i c a lm o d e lh a v e b e e ng i v e nc a n n o th ee x t e n dt oo t h e rm a n yv a l u e dl o g i c s oig i v ea nc l a s s i c a lm o d e l t h a tc a nb ee x t e n dt oo t h e rf i n i t em a n y - v a l u e dl o g i c s 。a n do r o v et h ec o m p l e t e n e s so f t h en + 1 一v a l u e d1 0 9 i e i nt h et h i r dc h a p t e r , ii n t r o d u e ta l g e b r a i cc o u n t e r p a r to fm a n y - v a l u e dl o g i c sa n d o t h e rl o g i c s w i t ht h ed e v e l o p m e n to fl o g i cs c i e n c e 1 1 l es y s t e m a t i ci n v e s t i g a t i o no f b r o a dc l a s s e so fl o g i c si na l g e b r a i cc o n t e x ti sh e c o m i n gam a i nt r e n d ，a n da b s t r a e t a l g e b r a i cl o g i c ) h a sb e e nd e v e l o p e d t oi n t r o d u c tt h em a i nc o n c e p t sa n dr e s u r s i aat a s ko f t h i sc h a p t e r k e y w o r d s ：m a n y v a l u e dl o g i c ；c o n n e c t i v e ；l o g i ca l g e b r a ；a b s t r a c ta l g e b r a i cl o g i c h 第一章多值逻辑的联结词 1 2 多值逻辑的联结词和系统 本节介绍一些常见的多值逻辑，并通过真值表分析其联结词的特点。 一l u k a s i e w i c z 三值逻辑b ： 1 9 2 0 年提出，2 为特指值，以和j 为初始联结词。其他的析取、合取和等值等联结词 通过以下定义引进： c t v p = f ( 啼助；p a p = d e r ，( a v p ) c t 亭b = 酣( 惜印“睁 联结词的真值表是： j o12 o222 1122 2012 v012 o 012 1112 2222 o1 2 0000 101l 2012 012 0210 l121 2o12 该逻辑不是函数完备的。1 9 3 6 年j s l u p e c k i 为其增加了一个一元算子t ，t x = l ，使之成为 一个函数完备的逻辑，记为b 3 。在l 3 中增加一元算子- ，当x = l 和2 时w x = 2 ，当x = o 时 w x = o ，可以得到l 3 的弱系统l 3 ”。其联结词可以定义为： o m d e f w e t c t p = m f w 氆 w v p = d e f w a v w b n j b = m f w a - w p a 铮p = d c f w w p 真值表为 ：，012 0222 l022 2o22 v 01 2 0 o22 1222 2222 o12 oo00 1o22 2 02 2 012 o200 1022 2o22 把扩充到有穷或无穷值的情形会得到相应的逻辑系统。在1 9 2 2 年，l u k a s i e w i c z 推 广了他的三值逻辑并且定义了一族有穷值和无穷值的多值逻辑。一个l u k a s i e w i c zi 卜值矩阵 具有以下形式： m 。= ( k ，j ，v ，a ，；，( 1 ) ) 这里对自然数集合n 在k 上定义的晒数如下： ，( n 一2 ，n 一1 ) ，l ， 如果n 垃，n e n ； w 0 1 ，如果n = k o ： 2 如果n = k t 。 且 ， 并 酬 ) w 舾 啦 ， ( v l n 厂，、l = k ( i ) x = 1 - - x x j y = m i n l ，i x + y ( i i ) x v y = ( x - - j ”j y = m a x x , y ) x a y2 ( x v ”= m i n x , y x 斜= 旧y ) “y j 炉l i x - y k i 一个变种为v k l ，其值域为 一1 ，1 ，特指值为i ，联结词真值规则为： x j v 2 ， 如果x y ； 一x + y ， 否则 x v y = m a x x , y x a y = r a i n x , y x 营y = ( x j y ) “y jx ) 有穷值的v n 的真值：( 1 ) 当n 是奇数时为；一l 一( n 一1 ) 2 x 2 ( n 一1 ) ， 一3 x 2 ( n - 1 ) ，- 2 2 ( n - 1 ) ，- 1 2 ( n - 1 ) ，0 ，i x 2 ( n 1 ) ，2 x 2 ( n 一1 ) ，3 x 2 ( n - 1 ) ， ( n - 1 ) 2 x 2 ( n - 1 ) = 1 ( 2 ) 当n 是偶数时为：把( 1 ) 中的n 换为n + l ，并把0 删去所得到 的所有值。当特指值为1 时，v r l 的公理正是k 的公理。如果0 从值域中删去( 包括所有 偶值的v n ) ，和当特指值为所有大于0 的值的时候，系统的重言式正是经典命题逻辑的重言 式。 l 3 的扩充u 的真值：( 1 ) 当n 是奇数时为：( 包括) 一( n i ) 2 到( n 一1 ) 2 之间的所有 整数( 所有大于0 的为特指值) ( 2 ) 当n 是偶数时为：把( 1 ) 中的i i 换为n + l ，并把0 删 去所得到的所有值。真值规4 ： 一譬辛翼1 ； x v y = m a x x , y 。r a y = m i n x , y u n 的公理和经典命题逻辑的一样。 ， u k o 的真值取所有整数及 y o o ，一o o 。真值规则和公理与u n 一样。 u k l 的真值域为 1 ，+ 1 。真值规则与u 3 一样。公理和经典命题逻辑的一样。 u 亍的是通过把u n 的蕴涵换为 得到，3 的真值规则为：x = ) y = ) y = m a x 一) 【，y 。其 公理和经典命题逻辑的一样。 二p o s t 逻辑 p o s t 于1 9 2 0 ，1 9 2 1 年分析了一族有穷值的命题逻辑。他受怀特海( w h i t e h e a d ) 和罗 素的数学原理中的经典命题演算( e p c ) 的形式化、真值表方法，以及经典逻辑具有函 数完全特征的启示，构建了函数完备的有穷值逻辑系统。有穷值系统p n 的真值域为f l ，2 ， n ，初始联结词包括元的旋转 r o t a t i o n 或循环的否定( c y c l i cn e g a t i o n ) ，和二元 的析取v 。它们的定义如下： 厂 lx + l ，如果x n ； l - 1 x = y 。 x a y = m i n x , y x v y = m a x x ，y x ，= 如果x = 0 否则。 如果x = ” n x ，y ) ，否则。 无穷系统的真值域为 o ，1 】。 l 为特指值。真值规则和的一样。1 9 5 9 年d u n u n c t t 证明 其公理系统为直觉主义命题逻辑系统加上公理( 印v ( b _ 构成。 七标准后承( s t a n d a r ds e q u e n c e ) 系统s 有穷系统s l i ，真值为0 ，l ( n - o ，2 ( n - 1 ) ，( n - 2 ) ( n - i ) ，1 真值规则为： 1 x = 1 一x x , x y = m i n x ，y ) 8 x v y = m a x x ，y ) r i l ， 如果x y j 。y 2 、 lo ，否则。 l x h y ：( x 专” ( y _ x ) 如果x = y 否则。 州书? 5 x y 气x y ) “y _ x ) 2 如果x = y x ，y ) ，否则。 如果n 是偶数且所有大于l 店的值为特指值，该系统和经典命题逻辑的公理一样。 系统s 。的真值域为【o ，l 】，s i k l 的真值域为【o 1 1 - i 2 。真值规则和s ，的一样。当所有 大于i 2 的值为特指值时，s i 州和经典命题逻辑的公理一样。 系统s 。3 和8 【x 广的真值域分别与s w 和s 的相同真值规q 和s ，的相同。当只有l 9 1 0 rill _ 二 一 为特指值时没有重言式a 当所有大于1 2 的值为特指值时，8 畔广和经典命题逻辑的公理一样。 系统s k 和s t 州+ 的真值域也分别与s k 和s 的相同。真值规则和s l l 的相同。当所有大 于i 2 的值为特指值时，s l t q * 和经典命题逻辑的公理一样。 系统s k 的真值域为【o ，1 】，1 为特指值，公理和经典命题逻辑的一样 ，v 与s n 和s ，的一样，蕴涵和等值规定为： x v = 如果x l 或y = l ； 否则。 八h a l l d n ( 哈尔顿) 的三值演算 如果x = y 否则。 h a l l d 6 n 于1 9 4 9 年提出一个三值逻辑，他把中间值翻译为“无意义的”他以 0 ，1 ，2 为真值，以 1 ，2 为特指值，初始联结词为卜，和 。卜a 表示句子a 是有意义的， 和a 是否定和台取。联结词的真值表如下： x o2 l1 22 ol2 0010 l11l 2ol2 九& q v i s t ( 阿奎维斯特) 的三值演算 1 9 6 2 年，a q v i s t 以h a l | d 6 n 逻辑为起点提出一个本质上不同的三值逻辑，他考虑假 陈述，有意义陈述和无意义的陈述，以 0 ，1 ，2 为真值，以 2 为特指值，初始联结词为# ， 和v 。f a 表示# n ，意为“a 是假的”：l a 表示# a v f a ，意为“n 是有意义的”；m a 表示 h ，表示“句子。是无意义的”。# ，和v 的真值表如下： x o2 1l 20 0 vol2 ool2 1112 2222 y x l m 厂llj、，l = x斗 y y 专x = 吖 x 十s e g e r b e r g 的三值演算 1 9 6 5 年，和a q v i s t 一样s e g e r b e r g 按照h a l i d d n 的思想提出一个不同的三值逻辑， 他以 o ，l ，2 ) 为真值，以 l ，； 为特指值，初始联结词为，# ，卜， 这些联结词除了 具有上述的真值表，对卜，和a 的真值表还给出了如下的不同情况： 十一p i r 6 9 - r z e p e c l m 兰值演算 1 9 7 7 年， 并引进联结词一， ol2 0 010 1 111 n1 o12 o0oo 1011 2o 1 2 k p i r 6 9 - r z e p c c k a 提出以 2 为特指值，以 ， ，j 为初始联结词， v ，营。联结词的真值表如下： o12 oo1 2 1111 2212 ol2 oo1o 111l 2ol2 j ol2 0222 l222 2o02 营 ol2 o220 12 2 o 2 0 02 十二h e y t i n g 三值演算 根据直觉主义逻辑思想，a 。h e y t i n g 于1 9 3 2 年提出了一个三值逻辑，以2 为特指值， 以 ，j ，a ，v 为初始联结词。联结词真值表为： 0l2 0oo0 1o11 2012 jo12 o222 1022 2o12 vo12 0ol2 1112 2222 然而，这个三值逻辑并不能完全刻画直觉主义逻辑，因为直觉主义命题逻辑的所有定理都是 这个三值逻辑的定理，但是有该三值逻辑的定理不是直觉主义逻辑的定理，g o d e l 于1 9 3 2 年对此给出了证明。 十三r e i c h e n b a c h 三值演算 r e i c h e n b a c h 于1 9 4 6 年提出三值逻辑，试图解决在量子力学中遇到的哲学和逻辑问题。 逻辑的特指值是2 ，联结词为 ，v ， ，3 ，j ，寸，；， ，真值表如下： 1 2 012 o012 11l1 2222 ) o12 0222 1122 2o12 0l2 o 。oo0 1o11 2 o12 j ol2 o222 1222 2oo2 012 0210 1l2l 2012 4 o12 o111 1111 2o12 营 ol2 0200 102o 2002 三个否定，一和，分别称为循环，直径和全否定。该逻辑是函数完全的。 十四s l u p e c k i 三值演算 1 9 4 6 年s l u p e c k i 给出了一个函数完全的三值逻辑，以2 为特指值，联结词，一和j 。 的真值表如下： x o2 l2 20 j ol2 o222 l222 2o1 2 十五s o b o e i f i s k i 三值演算 1 9 3 6 年定义了一个三值矩阵 ，联结词的真值表为： 0 12 0002 1ol2 2222 j012 o212 1o22 2012 a o1 2 000o 1012 2 022 ol2 02oo 1o21 2012 十六j a k o w s k i 多值逻辑 1 9 3 6 年由j a k o w s k i 提出，真值为：1 ，2 ，3 ，n ，n + l 。真值规则： 令av ，和付为给定的n 值逻辑( 真值为1 ，2 ，3 ，n ) 的联结词，与 此对应n + l 值系统的联结词为 ，a ，y ，和，x 和y 为两个n + 1 值真值。用 y ( n + 1 ) n + l x ( n + 1 ) x n + l y n + 1 4 y ( n + 1 ) n + l 【( n + 1 ) n + 1 n + ln + 1n + 1 _ y ( n + 1 ) n + l 一 x ( n + 1 ) + l n + l1l 这样扩充得到的系统记为e n ( r ) ，其中p n 表示n 值系统。易见e n ( l 2 产k ，这里l 2 是 经典命题逻辑，是l u k a s i e w i c z 的1 卜值逻辑。 如果把蕴涵改为如下形式，会得到另一种多值逻辑： j1 y ( 1 ) 一 x ( n + 1 ) 1 ( x 斗( y 一妙计l n + l11 类似地，我们把得到的逻辑系统记为f n ( p 0 。易见f n ( l 2 产s ，。 给定一个n 值逻辑，令上是任意一元联结词，是任意二元联结词，要碍到的n + l 值逻 辑的对应的联结词和! 按如下方式定义： y ( n ) n + l ( ! m ) x 庐 l 十七j a k o w s k i 积系统 1 9 3 6 年由j a k o w s k i 提也，以考虑两个逻辑系统的乘积构成的系统。真值规定为：如果 x - 是命题p 在系统x 1 中的真值，x 2 是命题p 在系统x 2 中的真值，那么命题p 在系统x i x 2 中的真值为 。 真值规则为； 1 x = 1 x 1 ，1 x 产 x a y = x v y = ( x v y ) l ( x v y ) 矿 x y - - y - - ( x y ) 1 ，( 舯y ) p 十八b i a u 三值逻辑 1 9 7 8 年u 。b l a u 提出一个三值逻辑，用以处理模糊谓词，如“热水”。该逻辑有三个 初始联结词，两个否定和一个合取：一，和a 。 012 o000 1011 2012 该系统不是函数完全的，可以定义g o d e l 否定。但加上t 算子可以成为函数完全的。 1 2 几种非正规的多值逻辑 所谓非正规联结词是指其联结词的真值表不是正规的那些联结词。正规的真值表必须满 足两个条件：( 1 ) 它至少包括一个真真值2 和一个假真值0 ；( 2 ) 当只涉及两个真值2 和0 时，它与经典二值逻辑的一个联结词完全统一。一个多值逻辑可以称为正规的，如果它的 所有基本联结词的真值表都是正规的。一个多值逻辑可以称为非正规的，如果它不是正规 的。也就是说它的基本联结词至少有一个是非正规的。根据这种性质可以判定，p o s t ， s e g e r b e r g ，r e i c h e n b a e h ，s l u p e c k i 和s o b o c i m k i 的多值逻辑都可以是非正规的。而s l o 的 否定也是非正规的，因此s l o 也是非正规的多值逻辑。正规多值逻辑容易得到合理的语义 解释，而非正规多值逻辑难以得到合理的语义解释。非正规多值逻辑中除s l o ，s e g e r b e r g 和r e i c h e n b a c h 的三值逻辑等少数有解释外，其他非正规多值逻辑几乎没有合理的解释。 多值逻辑的基本联结词是多种多样的，非正规多值逻辑的基本联结词也是多种多样的。 我们可以把非正规多值逻辑的基本联结词划分为两种情况：所有基本联结词都是非正规的， 和基本联结词中有一部分是正规的。如果所有的基本联结词都是非正规的，这些联结词有可 能定义出正规的联结词，所以这种情况又可分为能定义出正规多值逻辑的情况和不能定义出 正规多值逻辑的情况。如p o s t 多值逻辑，它是函数完全的，因此可以定义出正规的联结词。 任何函数完全的多值逻辑都可以定义出正规的联结词。不能定义出正规联结词的基本联结 词，由于无法定义蕴涵词，往往也缺乏直观的语义解释，本书对此不予过多讨论。常见的的 非正规的多值逻辑其基本联结词都包含了正规的联结词，下面结合具体实力给以介绍。 上面已经介绍，p o s t 多值逻辑有两个基本联结词，一( 即一2 ) 和v ( 即v 1 ) 。p o s t 构 造多值逻辑只是从纯形式的考虑出发，其中否定词是非正规的，没有直观的语义解释。 h a l l d 6 n1 9 4 9 年提出了一个三值逻辑，他把第三个值l 解释为“无意义的”，真值0 ，2 分别解释为假，真。他的基本联结词是卜，一( 即一1 ) ，a ( 即a 1 ) 。卜的真值表为 以 l ，2 为特指值，建立了一个三值系统。他把命题区分为有意义和无意义的，本质上，他 1 6 的逻辑仍然是经典逻辑。 1 9 6 2 年l a q v i s t 年提出了一个不同于h a l l d n 的三值逻辑，他同样把命题区分为假的， 有意义的和无意义的。他的基本联结诃是# ，一( 即- 1 1 ) 和v ( u p v l ) 。0 ，l ，2 分别解释 为假，既不真也不假，真。他以2 为特指值建立了三值系统。 1 9 6 5 年，k s e g e r b e r g 也建立了三值命题逻辑，他根据h a l l d 6 n 和l a q v i s t 的思想，以 ，# ，一( 即_ 1 1 ) ，a ( 即a 1 ) 为基本联结词。但是，联结词卜的真值表有所不同，定 义为 用这些联结词，构建了三个逻辑系统s l ，既s 3 。其中s l 以 1 ，2 ) 为特指值，以为基本联结 词；s 2 以 l ，2 ) 为特指值，以卜， 为基本联结词；s 3 以2 为特指值，以一， 为基本联 结词。 以上三种非正规逻辑都把命题区分为有意义的和无意义的。除此之外，1 9 4 6 年r e i c h e n b a c h 为了解决量子力学中产生的哲学和逻辑问题，也提出了三值逻辑系统。他 以，一( 即- 1 1 ) ，一，v ( 即v 1 ) ，a ( 即a 1 ) ，3 ( 即一2 ) ，j ，_ ，= ，营为基本联结 词。这些联结词是函数完备的。r e i c h e n b a c h 以2 为特指值建立了三值逻辑系统。 s o b o c i f i s l ( i 1 9 3 6 年构建了一个多值逻辑系统，以，v ， ，j ，为基本联结词。 其中的否定是非正规的，其他都是正规的联结词。否定的真值表是 与p o s t 否定相同指值。他把他的逻辑推广到任意n 值的 情形，特指值为0 以外的任意值。这种逻辑也缺乏直观语义解释。 s l u p e c k i 于1 9 4 6 年也构建了函数完备的三值逻辑系统，他也用了非正规的否定词，这 种逻辑也是从纯形式的角度研究多值逻辑，并没有直观的语义。( 参看l e o n a r db o l c ，p i o t r b o r o w i k m a n y - v a l u e dl o g c s , jt h e o r e t i c a lf o u n d a t i o n s s p r i n g e r - v e r l a g b e r l i n h e i d e l b e r g , 1 9 9 2 p p 6 3 7 7 ) 研究非正规逻辑不仅要从纯形式出发，更重要和困难的是给出它的语义解释。鞠实几 教授在开放世界逻辑过程中给出一个三值逻辑的语义解释。本书的前面已经有论述。这种逻 辑的以，一( 即l u k a s i e w i c z 蕴涵屹) 为基本联结词，其中的真值表是 这里i ，2 ，3 分词集 ，一) 是函数完全的。在更抽象 的意义上，可以对该否定词进行了推广，其真度表规定：当a 取1 时a 取假m ，其余情况 1 7 a 都取真度2 。经过推广j 该否定和l u k a s i e w i e z 蕴涵一2 也可构成一个函数完备的联结词集。 对这种逻辑本j 愕将建立h i b e r t 型公理系统。 需要说明，开放世界的逻辑的语义解释从直观概念的角度看较为自然，一旦建立起逻辑 系统，它就变成纯数学的研究。这正如模糊集合概念易于为人所接受，而模糊逻辑不易为人 所理解一样。但是我们认为这种研究仍有重要价值。 8 第二章一个函数完备的n + 1 值命题逻辑公理系统的强完全性 有穷值逻辑的完全性可以通过多种方法证明。文献【5 】中用了m v n - 代数，文献【2 ，3 , 4 1 用 了h c n k i n 极大一致集方法对l u k a s i e w i c z 3 值逻辑的完全性进行了证明，文献【9 】用代数方法 证明了一些有穷值逻辑的系统完全性，其中就包括l u k a s i e w i c z 有穷值逻辑，p o s t 逻辑等等。 但是用h e n k i n 极大一致集方法来证明完全性还没有被推广到l u k a s i e w i c z 3 值逻辑以外的其 他逻辑，这是因为文献【2 ，3 ，4 跆出的典型模型无法推广到其他类型的多值逻辑。本文将构建 一个典型模型，它可以推广到任意有穷值逻辑乃至其他类型的逻辑。对该逻辑的完全性用 h e n k i n 方法给以证明。由于这个逻辑和p o s t 逻辑一样是函数完备的，它可以定义出p o s t 逻 辑，从而也证明了p o s t 逻辑的完全性。 我们以 o ，l n ，1 ) 为取值范围，以l 为特指值，把所建立的逻辑称为p ，它以一， 一为初始联结词，其中一是l u k a s i e w i c z 蕴涵。对联结词的真值运算规定为：当x = l 时，一x - - 0 ， 当x ：p l 时，一x = ( n - i 蜘；当x ，y 取任意真值时，r y = m i n 1 - x + y ，1 ) 。当1 1 = 2 时，0 表示 “假”，1 表示“真”，1 2 表示“真假不定”，这和鞠实儿建立的开放类逻辑s l o 的联结词 一样。即当命题p 假和真假不定时，p 真假不定；当p 真时，呻为假。联结词的真值表由 下图给出。 x 0l n2 n 1 y 0 lll 1 1 ，n ( n - 1 ) n 11 1 加 ( n - 2 ) n ( n q ) n1 i i l ll l 10 1 n 2 n 1 xq 0 ( n - 0 n l n ( n - 1 ) n 2 i n ( n - i i ) n f lo xn x 01 l n ( n - 1 ) n 2 1 1 ( n - 2 ) n f 1 0 x y 我们以可数无穷多的小写拉丁字母表示句子变元，如p ，q ，r ，p ，q 等等。肼的公式集是 句子变元加上所有形如a 和a b 的公式，其中a ，b 是公式。句子p 的长度f ( p ) 是1 ；否 定a 的长度m 以) 是“a ) + 1 ；条件句a b 的长度r ( a - - b ) 是“a 卜“b 卜l 。我们把公式“一 ( p p ) ”缩写为“f ”；形如( a f ) 的公式记为a ；形如( a 一，a ) 的公式记为a 。容易 看出“一”就是l u k a s i e w i c z 逻辑的否定。我们在不引起混淆的情况下省略括号。另外根据 文献【5 l o 】还定义出算子伽 0 ，l n ，l 。( a ) 的真值表是当a 取真值咖时， 其真值为l ，否则其真值为0 。 肼的公理是如下形式的公式： a j ：a 一( b a ) ， a 2 ：( a b ) 一( ( b c ) 一( a c ) ) ， t 9 a 3 ：( a + 一a ) 一a ， a 4 ：( 1 a 一b ) 一( b a ) ， a s ：( a ”一( b c ) ) - - ( ( a “一b ) 一( a n c ) ) a 6 ：，a f a n - 8 ) a 7 ：( a “一a + ) 一a a 8 ：a ，一a a 9 ：( j h ( a ”( ( ( a ) ) f ) ，两， a 1 0 ：( j i l n ( a ) ) + 一( ( j ( a ) ) 一( ( j i 呻l 缸a ) ) 一i a ) ) ) ) ，i l ，i 2 ，i n 互不相等。 a 1 1 ：j h ( b ) 一f ，i o n - l ，o ； a 1 2 ：j ( 舢l y n ( b ) 一“( b ) 一f ) ， a 1 3 ：j “b ) 一j 1 ( b ) ，i n - 1 ， 删的公式a 是从瑚的公式集s 可证的简记为s h 如果有一个以a 结束的一个公 式序列( 称为从s 对a 的证明) ，它的每一个公式或者是公理，或者是s 的成员，或者是序 列中前面的两个公式的推论。的公式a 是可证的简记为h 如果a 是从o 可证的。 公式集合s 是句法( 不) 一致的，如果在w 中没有( 有) a 使得s a 并且s a 。如果 s 不是句法一致的，则并非没有a 使得s a 并且sp a ，即有a 使得s a 并且s a ， 所以s 是句法不一致的。所以s 是句法不一致的当且仅当s 不是句法一致的。一个句法一 致的集合s 是极大一致的，如果对任何使s u a 是句法一致的公式a ，s a 。 肼的解释或真值指派是从础的所有句子变元到 0 ，l n ，1 ) 的函数。在这些真值 指派下否定句和条件句的真值由联结词的真值表给出。公式集合s 是语义一致的如果存在 一个解释使得按照这个解释每个s 中的公式都可以计算出取真值1 。s 语义蕴涵删的公式a 简记为s 队如果对任何满足v ( s ) = 1 ) 的解释v ，v ( a ) = l 。公式a 是有效的 简记为# a 如果对任何解释v 都有v ( a ) = 1 。 我们证明如下引理1 ( l 】) 中关于可证性和句法不一致性的辅助事实。l l ( a ) - ( d ) 根据定 义成立。 工j t 曲如果s f a 郡么j c 唾s 的任伺超集s ，s i - a 。 ( ”奶榘sf a ，彤么荐霍s 膨一个方旁察s 使得s a 。 c 、如果a 属于s 那么sf a 。 ( 回奶栗s i - a 孝直s 卜a b ，那么s b 。 ( e ) a a ( 0 奶榘s u a ) b 娜么s 弦一b 。 t 心如果s 是句法不一致的那么对公式集中的任翱公式ks ) - a 。 q 哑s 是句法不一致的当且仅当s 。 娜_ 如果s ut 吣是句法不一致的。那么s f a t 0 ) 奶榘s u a + 屠甸；游布蒙劈，那么s a 。 证明：( e ) 由a l ，a 4 有，卜a 一( i 一( a 卜a ) ， ( 一( a 卜一a ) 一( 1 a 一一( a ) ) 。由a 2 得， 卜1 a 一( - _ a 一一( a + ) ) 。由a 4 ，k _ a 一，( a + ) ) 一( a 一a ) ，由a 2 得卜1 a 一( a + 一a ) 。再由a ， a 2 得，卜l a a 。把该定理的a 替换为1 a 得，卜1 a 一_ a 。由a 4 有，k - a 一a ) 一( a 一1 a ) 。再根据a 2 得，卜a 一a 。由已证的p a a 和卜a 一a ，根据a 2 得，卜a a 。 ( 0 假定c l ，岛是从s u a ) 对b 的一个证明。通过对i 的归纳，我们证明s r c i ，ls i s p 。我们将区分下面的情形：情形i ：g 是s 的一个成员或公理，所以由l l ( a ) u gl i ( c ) 有sh g 。由a l 有sk 一( a g ) 。所以由l 1 ( d ) 有s 卜a c i 。再由a 1 有s ( a g ) 一( a 一( a g ) ) 。所以由l l ( d ) 有s 卜a 一( a c i ) 。再n - 2 次应用a i 和l 1 ( d ) 可得s a n c i 。情形2 ：c i 是a 。那么由( a 1 ) 有s 卜a 一( a c i ) 。再l 卜2 次应用a l 和l l ( d ) 可得s a n g 。情形3 ：c i 是c h 和q c i 的推论。由归纳假设有s - a n - - c h 和s 卜a “一( c h c i ) 。所以由a 5 和l l ( d ) 有sf a “一g 。 ( 曲假定对s 的某公式b 有s 卜b 和s 卜b 。由a 6 和l i ( d ) ，对s 的任何公式a 有sf a 。 ( h ) 由l i ( e ) 有s 卜a a 。所以，如果s 卜f ，那么s 是句法不一致的。所以由l l ( g ) 有l l ( h ) 。 ( j ) 假定s u a ) 是句法不一致的。那么由l l ( g ) 有s u a ) 卜a ，所以由l l ( d 有s f a n 一a ， 即s a “一a + ，再由a 7 和l l ( d ) 有s h + 。 ( j ) 由l l ( i ) ，a 8 和l i ( d ) 证明。 我们证明每个句法一致的集合s 也是语义一致的。我们首先回顾二值逻辑的情形：即， 我们假定s 是句法一致的，然后把s 扩充为熟知的超集。在我们设定的某真值指派下， 的成员也即s 的成员可以计算出取真值1 。的构造如f ：( a ) 取s o = s ，( b ) 假定睇的公 式是按顺序排列好的，对每个i ，a 是的第i 个公式，如果s i 1u a ) 是句法一致的s i = s i - l u a i ) ，否则s = s m ( c ) 令= u ”i ：0 s i 。 下面和二值逻辑的情形一样，容易证明： ( 1 ) 是句法一致的， 并且 ( 2 ) & 是极大致的。 要证明( 1 ) ，假定s 。是句法不一致的。那么由l i ( h ) 和l l ( b ) 至少有一个s 。的有穷子集s 是句法不一致的。但是s 一定是s o 的子集，或( 不是) s 的一个，或( 不是) s 2 的个， 等等，而s o s i ，s 2 等等的每一个是句法一致的，矛盾。因此( 1 ) 成立。要证明( 2 ) ，假定 并非s 。f a ，其中a 是l # 的第i 个公式。那么由l i ( c ) a 不属于s 曲，所以a 不属于s i ，因此 s i 1 u a 是句法不一致的，所以由l l ( h ) 和l l ( a ) ，& u a 也是不一致的。 文献【5 】从二值逻辑情形着手给出一个典型解释。它对肼的每个句子变元p 指派真值l 如果f p ( 由s 。的句法一致性，并非s 呻p 1 p ) ；对句子变元p 指派真值0 如果s 。r 1 p ( 由 s 呻的句法一致性，并非s 。扣) ；否则指派p 真值l 2 。通过这个真值指派归纳证明了对系统 的任何公式a ，如果卜a ，则a 在该解释下取真值1 ：如果 ，a ，则a 取值o ；如果即 不卜a 又不 堆，则a 取值1 2 。这个解释无法推广到任意有穷值逻辑的情形，为了用 极大一致集方法证明其他有穷值逻辑以及其他具有不同逻辑联结词的逻辑系统的完全性，本 文将把典型解释改为如下形式。这种解释不仅适应于三值逻辑，也适应于有穷其他多值，但 本文只构造三值情形。要构造的解释v 为： v ( p ) = i 饥如果s 。 j “( p ) 其中p 是句子变元。对任何公式a ，我们证明：如果卜j “a ) ，则v ( a ) = i n 。 公理a 9 保证了n + 1 个j h ( a ) 在& 中只能出现一个，否则由l l ( d ) 和l l ( h ) s 岫是句法不 一致的。公理a 1 0 保证了n + 1 个j “( a ) 在中至少出现一个。因为如果其中有n 个都不出 现，比如j o ( a ) ，j v n ( a ) ，j ( “a ) 都不在中出现，则由的构造过程和引理2 知& u j 0 ( a ) ，& u j v m ( a ) ，& u j ( + l 珈( a ) ) 都是句法不一致的，由l 1 ( i ) 有h j “a ) ) ， k j l “a 矿，s 。h j l “a ) ) ，由a i o 得卜j l ( a ) 。由此可见解释v 具有恰当性。下 面施归纳于a 的跃度f 证明如果f j v n ( a ) ，则“a ) - - i n 当乒l 时，a 是句子变元，由解释的定义可以证明。 当6 1 时，分为两个情形。 2 l 情形l ：a 是b 。( i ) 卜j i l ( a ) ，其中i ；e n - l 或0 ，这不可能，因为虫a l l 有s 。卜f ，矛盾。( i i ) 如果s 呻i - j 忡i y n ( a ) ，由a 1 2 不会出现卜j 1 ( b ) ，否则卜f 。因此只可能有s 。卜j ( b ) ，其中 i n 。由归纳假设可以得出“b ) 为1 之外的其他真值，所以“a ) = “b ) = ( i 卜l y n 。( i i i ) 如果 & - j o ( a ) ，由a 1 3 有，& 卜j 1 ( b ) ，由归纳假设有v ( b 产l ，v ( a ) - - - v ( 一b ) = 0 。 情形2 ：a 是b c 。假定卜j “( b - - c ) 。如果有& 咖( b ) 并且& 卜j 蜘( c ) ，由a 1 4 必有 卜j 。 ”k m l l ( b c ) 。若i m i n ( n - j + k ) ，i l ，l ，与解释v 的恰当性矛盾( 或者由a 9 有& 卜f ) ， 所以必有i = m i n ( n - j + k ) n , 1 ) 。由归纳假定，“b - j n , v ( b ) = k n ，所以v ( b c 产r a i n ( 时+ k ) l l 1 ) 。又根据解释v 的恰当性，总有这样的；和k 满足上面的假定。所以，v 确实是一个解释。 既然s 的每个成员都是& 的成员，由l 1 ( c ) 知也都是可以从& 证明出的，因此s 的每 个成员在解释v 下取值1 。于是有下面的引理： 2 如果s 是句法一致的那么s 是语义一致的。 现在可以证明完全性定理。假定s 队，那么s u a ) 不是语义一致的，所以由l 2 ，s u a t 是句法不一致的，所以，由l 1 0 ) 有s 卜a 。所以： 定理i ( 强完全性定理) 妇果s 队，那么s 卜a 。 当为空集时有： 定理2 ( 弱完全性定理) 奶暑队，期么卜a 。 通过对从s 对a 的证明的各种情况进行归纳证明，证明的每一步都能保证前提的真值 解释小于或等于结论的真值解释，因此定理l 的逆定理也成立。根据该定理，如果s 的每 一个有穷子集都是语义一致的，那么它也是