（逻辑学专业论文）一个条件化的知信逻辑.pdf

论文原创性声明： 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：币。 日期：。严f 月1 1 日 学位论文使用授权声明： 本人完全了解中山大学有关保留、使用学位论文的规定， 即：学校有权保留学位论文并向国家主管部门或其指定机构 送交论文的电子版和纸质版，有权将学位论文用于非赢利目 的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以 采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：代池 日期：o 夕年f 月 、1 日 导师签名：苍力电 日期：d 年厂月 ，日 l 一个条件化的知信逻辑 专业：逻辑学 硕士生：龙进 指导教师：李小五教授 摘要 首先，构造条件化的知信系统d c ，给出一些证明论结果。 其次，引入命题型的择类语义，给出d c 的特征公理的框架 条件，证明d c 是框架可靠的。最后，证明d c 是框架完全 的。 关键词：条件化的知信系统；命题型的择类语义；框架 可靠性；框架完全性 a l o g i cf o rc o n d i t i o n i z a t i o n a lk n o w l e d g ea n d c o n d i t i o n i z a t i o n a lbe l i e f m a jo r ：l o g i c n a m e ：l o n gj i n s u p e r v i s o r ：l ix i a o w u a b s t r a c t f i r s t l y , w ec o n s t r u c tt h es y s t e md cf o rc o n d i t i o n i z a t i o n a l k n o w l e d g ea n dc o n d i t i o n i z a t i o n a lb e l i e f , g i v es o m er e s u l t so fi t s p r o o ft h e o r y s e c o n d l y , w ei n t r o d u c eap r o p o s i t i o n a lc l a s s s e l e c t i o n s e m a n t i c s ，g i v et h ef l a m ec o n d i t i o n so ft h ec h a r a c t e ra x i o m so fd c ， a n dt h u sp r o v et h ef r a m es o u n d n e s so fd c f i n a l l y , w ep r o v et h e 一 一j 1 t r a m ec o m p l e t e n e s so td c k e vw o r d s ： s y s t e mf o rc o n d i t i o n i z a t i o n a lk n o w l e d g ea n d c o n d i t i o n i z a t i o n a lb e l i e f ；p r o p o s i t i o n a lc l a s s s e l e c t i o ns e m a n t i c s ； f l a m es o u n d n e s s ；f l a m ec o m p l e t e n e s s 4 目录 第一章形式系统及其证明论1 第二章命题型的择类语义和可靠性定理1 1 第三章完全性定理1 6 结束语：2 6 参考文献：2 8 后记：2 9 5 本文的主要工作是要建立一个条件化的知信逻辑，研究单主体的条件化知 道与条件化相信这两个模态概念，进而研究关于这两个概念的规律和推理模式。 本文提到但未定义的概念和记号，请参见李小五的 1 。 第一章形式系统及其证明论 先来定义经典句子语言与公理化系统： 定义1 1 ( 1 ) 定义l o 是经典句子语言的字母表： 句符：p l ，p n ，。； 句子联结符：1 ，a ； 括号：( ，) 。 ( 2 ) 经典句子语言f o r m o 递归定义如下： p l p n f o r m o ： 若a ，b f o r m o ，则1 a ，a a b f o r m o 。 ( 3 ) 经典句子系统p c o 由以下公理( 模式) 和推演规则构成：对所有a ，b ， c e f o r m o ， 公理( 模式) ： ( t a l )a c a ， ( t a 2 ) ( a b c ) 一( a 专b ) 专a c ， ( 1 a 3 ) ( 1 a c ) 一( 一1 a 寸1 c ) 一a 。 推理规则： ( m p ) a ，a c c 。一 l 下面再来定义双条件句算子的语言与公理化系统： 定义1 2 ( 1 ) 定义l 是双条件句算子的语言的字母表： 句符：p l ，p n ，； 句子联结符：1 ，八； 条件句算子：， ； 括号：( ，) 。 ( 2 ) 递归定义双条件句算子的语言f o r m 如下： p 1 ，p n ，f o r m ； 若a ，c f o r m ，则1 a ，a a c ，a c ，a c f o r m 。- 说明： ( 1 ) 本文若不特别说明，以后总用a ，b ，c ，d ( 带或不带下标) 表示f o r m 中的公式。 ( 2 ) 缩写符号v ，一和h 如通常定义。 ( 3 ) 为了叙述方便，规定联结符的结合力从左到右依次减弱： - 1 ，a ，v ， ，专，h 。 同时还规定同类联结符右向结合，因此 a ( b 专c ) 寸a b _ a c 就是 ( a ( b j c ) ) 一( ( a b ) 一( a c ) ) 。 ( 4 ) 下面常用符号表示“当且仅当”，用表示“若，则。 ( 5 ) 条件句a c 直观表示某个主体“在a 的条件知道c ”，所以直观 表示条件化的知道概念；而条件句a c 表示主体“在a 的条件相信c ”，所 以 直观表示条件化的相信概念。所以a c 也可以解释为相对a 来说c 是该 2 a c 解释为相对a 来说c 是该主体的信念。我的创新就在于把 上的认知概念相对化，或者说，条件化。 上面的条件a 可以做各种解释。我比较喜爱的一个解释是把条件a 解释为 一个场景或脉络。因为在我看来，至少是在通常情况下，主体是相对某个场景 或脉络a 才知道c 和相信c 的。 定义1 3 定义l 的基本系统d c 如下： 公理( 模式) ： ( t a l )a - - c - - 9 a ， ( t a 2 ) ( a b 专c ) 一( a b ) 寸a j c ， ( t a 3 ) ( 1 a 专c ) j ( a 一1 c ) 一a ， ( c k l )a ( b c ) 一a b a c ， ( c k 2 )a ( b c ) 专a b j a c ， ( i d l ) a a ，( 相对的自知公理) ( c m p l ) a 7 c - - - a c ，( 知信关联公理) ( c m p 2 )a c a 专c ，( 相对的知识公理) ( s d a l )a v b 7 c - - ( a c ) 人( b c ) ， ( s d a 2 )a v b c - - ( a c ) 八( b c ) ， ( c 4 1 )a c a a c ，( 相对的条件化正反思公理) ( c 4 2 ) a ： c - - - a a c ，( 相对 的条件化正反思公理) ( c 5 1 )1 ( a c ) 专a - 1 ( a c ) ，( 相对的条件化负反思公理) ( c 5 2 ) - 1 ( a c ) 一a ( a c ) 。 ( 相对 的条件化负反思公理) 推理规则： ( m p )a ，a c c ， ( r c n l ) c a c ， 3 ( r c e a l ) a l h a 2 a 1 c h a 2 c ， ( r c e a 2 ) a l h a 2 a l c 4 - a 2 c 。- i 说明： ( 1 ) i d l - - c 5 2 称为d c 的特征公理，垢我们会看到这样的称谓是正当的。 ( 2 ) c m p l 表示相对a 来说，如果c 是当下主体的知识，则c 也是他的 信念。理性的主体总是相信自己获得的知识，即使这是条件化的知识。这是符 合主流逻辑的想法。 ( 3 ) c m p 2 的 对应公式是 a c j a 寸c ， 但它的直观解释似乎不合理。例如，我相信在张三来的条件李四会来，现在张 三来了，不见得李四一定来。 ( 4 ) 我们总是想刻画具有较高智能的主体，所以这里我们添加了刻画认知 算子的条件化正反思公理和条件化负反思公理。 定义1 4 ( 1 ) i - a 表示a 是d c 的内定理：a 在d c 中有一个形式证明，即存在一 个公式序列a l ，a n 使得对每一个l i n ，a i 是d c 的某个公理的实例，或 者a i 是通过d c 的规则从它前面的公式得到。 ( 2 ) d c 的全体内定理的集合记为t h ( d c ) 。 ( 3 ) 我们也用铲a 表示a 盛t h ( d c ) 。 ( 4 ) 称a 1 a n c 是d c 的导出规则，当且仅当，在d c 中有一个从 a l ，a n 到c 的形式推演a l ，a n 卜c 。- 引理1 5 下面是d c 的内定理和导出规则： ( 1 ) a a 。( = i d 2 ) 4 ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) c a c 。( = r c n 2 ) b c a b ja c 。( = r c m l ) b c a b 专a c 。( - - r c m 2 ) ( a c ) ( a d ) a c d 。( = c c t ) ( a c ) ( a d ) 争a c 八d 。( = c c 2 ) c l a 人c n c ( a c 1 ) 八a ( a c n ) _ a c 。( = r c k l ) 这里约定当n - - 0 时，r c k l 是r c n l 。 c i a c n j c ( a c 1 ) 八a ( a c n ) 一a c 。( = r c k 2 ) 这里约定当n = 0 时，r c k 2 是r c n 2 。 a c a a c 。 ( 1 0 ) a o ( a c h a a c ) 。 证明： 只给出证明的主要步骤和主要根据。 ( 1 ) 据c m p l 和i d x 。 ( 2 ) 据r c n l 和c m p l 。 ( 3 ) a ( b c ) a ( b 争c ) j a b 争a c ( 萤 a b a c ( 4 ) 证明类似( 3 ) 。 ( 5 ) c 专d c d a c a ( d 争c 八d ) a ( d c d ) j a d a c 八d ( da c a d 专a c d 5 假设，r c n l c k i ，m p 。 t a l 一3 ，m p ，r c m l c k l ，三段论。 ( 6 ) 证明类似( 5 ) 。 ( 7 ) 证明施归纳于n 。 当n = 0 时，据约定，r c k l 就是r c n l 。 设n = k 时要证结果成立。则 c l a a c k l a c k a c k + l c假设 ( a c 1 ) a 八( a c k 1 ) a ( a ( c k a c k + 1 ) ) 一a c ，归纳假设 ( a c 1 ) a ( a c k 1 ) 八( a c k ) 八( a c k + 1 ) a c ，c c l ，致论。 ( 8 ) 证明类似( 7 ) 。 ( 9 ) 据c 4 l 和c m p i 。 ( 1 0 ) a a a c a c a j a c a a c c m p 2 c 4 l ，t a l - - 3 ，m p 。- 定理1 6 基本置换定理 若卜b h c ，则卜a + - a ( c b ) ，其中a ( c b ) 表示用b 替换a 中c 的若干出现 得到的公式。 证明： 施归纳于公式a 的结构，详细证明如通常。- 1 说明： 据上面的定理，易见d c 满足组合原则。 下面，研究d c 与p c o 的关系。要证明前者是后者的协调概括，或者说前 者可以协调地退化为后者。 定义1 7 6 ( 1 ) 定义从f o r m 到f o r m o 的翻译映射t 如下： t ( p ) - - p ，对所有句符p ； t ( 1 a ) = 1 t ( a ) ： t ( a 八b ) = t ( a ) 八t ( b ) ； t ( a c ) = t ( a ) 寸t ( c ) ； t ( a c ) = t ( a ) t ( c ) 。 ( 2 ) 对每一公式a f o r m ，称t ( a ) 是a 的t 诩译。_ 说明： 据上面的定义，易证 t ( a v b ) - - t ( a ) v t ( b ) ， t ( a 争b ) = t ( a ) t ( b ) ， t ( a h b ) = t ( a ) h t ( b ) 。 定义1 8 令s 和t 是任意两个公理化系统。 称s 能t 退化为t ，当且仅当s 的所有内定理都能t 翻译为t 的内定理。 定理1 9 d c 能t 退化为p c o ， 证明： 易见公理t a l 3 和m p 的t 翻译仍是t a l 3 和m p ，而且它们只涉及f o r m o 中的公式。 c k l 的t 翻译是 t ( a ( b c ) 一a b a c ) = ( t ( a ) 寸t ( b ) 一t ( c ) ) 一( t ( a ) 一t ( b ) ) 一t ( a ) 一t ( c ) 。 因此c k l 的t 翻译形如 7 ( 0 c j p 专d 一( c c p ) 寸仪一丫，其中仅，p ，7 e f o r m o 。 同理c k 2 的t 翻译也形如 ( 仅斗p 专丫) 一( 仪j p ) 专仅叫。 i d l 的t 翻译形如 q 一仅o c m p l 和c m p 2 的t 翻译都形如 ( 0 【专p ) 一仅j p 。 s d a l 和s d a 2 的t 。翻译都形如 ( a v l 3 _ 川一( 0 c 切 ( p 吖) 。 c 4 l 和c 4 2 的t 翻译都形如 ( 仪一p ) 一q 专a p a c 5 l 和c 5 2 的t 一翻译都形如 _ 1 ( 0 c p ) 一a 一 ( 0 【_ p ) 。 r c n l 的t 翻译形如 丫仅叶。 r c e a l 和r c e a 2 的t 翻译都形如 o c l h 啦仅l y h 啦专丫。 据上面的结果，易见 ( 1 ) 若a 是d c 的公理，则a 的t 翻译是p c o 的内定理； ( 2 ) 若r 是d c 的规则，则r 的t 翻译是p c o 的导出规则。 由此证明： ( 3 ) 若a 是d c 的内定理，则a 的t 翻译是p c o 的内定理。- 说明： 因为d c 有d l ，否则把定义1 7 中的关键两步修改为 t 似c ) = t ( c ) ，t ( a c ) - - t ( c ) 。 相对系统d c d 1 ( 从d c 删去i d l 得到的系统) ，上一定理仍成立，而且证明 r 定义1 1 0 称公理化系统s 是协调系统，当且仅当不存在a 使得a 和_ 1 a 都是s 的内 定理。- 1 定理1 1 l d c 是协调的。 证明： 假设d c 不协调，则存在a 使得a 和a 都是d c 的内定理，则据上面的 定理，t ( a ) 和 t ( a ) 都是p c o 的内定理，矛盾于p c o 的协调性。_ 本节最后，研究d c 的缩写退化系统。 缩写定义1 1 2 令t 表示某个固定的常真式。 ( 1 ) k a = d f t a ， ( 2 ) b a = d f t a 。 说明： k a 可称为主体( 绝对的) 知道a ，b a 可称为主体( 绝对的) 相信a 。换 句话说，k a 和b a 表示主体的绝对知识和绝对信念。 令d c 涉及的条件句a b 和a c 都为t b 和t c ，则d c 可以用上一缩写 定义如下退化为一种( 绝对的) 知信系统： 齐一使用缩写定义于一个系统也能得到一种退化 易见公理t a ! 一3 和规则m p 的缩写仍是t a ! 一3 和m p 。 r c n l 的缩写形如 ( r n k ) 伐k 仅。 r c e a l 和r c e a 2 的缩写分别退化为p c 的平凡规则 t h 可k q k 仪， t 七专t b c ) 【 o t 。 令s d a i 和s d a 2 中a 和b 分别是t ，则它们的缩写分别形如 k e , - - ) k ( ：z a k 0 c ，b a - - - - ) b o r , a b 仅。 c 4 1 和c 4 2 的缩写分别形如 ( 4 k ) k w - ) k k o 【| ，和 ( 4 b ) b o h b b o t 。 c 5 l 和c 5 2 的缩写分别形如 ( 5 k ) 1 k 仪一h k 0 【，和 ( 5 b ) _ 1 8 0 【专b b 仅。 从如上结果易见，d c 的缩写退化系统d c a 可以表示为： p c + r n k + 脉+ k b + k b + t k + 4 k + 4 b + 5 k + 5 b 。 o 注意：用缩写定义得到的公式仍是同一语言中的公式。 1 0 易见d c a 本质上是通常的知道模态系统s 5 k 和相信模态系统i ( 4 5 b 的扩充 ( 即在这两个系统中增加知信关联公理k b ) 。由此可见，d c 是大多数逻辑学 家都能接受的( 绝对的、即经典的) 知信系统的一个自然扩充。所以经典知信 系统能表述的规律在d c 中被全部保留下来，而且我们的系统能更丰富地表达 前者不能表达的规律，即关于条件化或相对化的知识和信念的规律。 实际上，在d c 中引入缩写定义1 1 2 ，易见d c a 的下列公理和规则都是 d c 的内定理和导出规则： r n ，k k ，k b ，t k ，4 k ，4 b ，5 k ，5 b 。 第二章命题型的择类语义和可靠性定理 择类语义有两类：命题型的择类语义和句子型的择类语义。 本文只选择命题型的择类语义来匹配d c 。 定义2 1 ( 1 ) 称三元组f = ( w ，cg ) 是双算子的命题型择类框架，徘f 是p 2 - 框架， 当且仅当 w 是非空的可能世界集。 f 和g 都是从p ( w ) w 到p ( w ) 中的映射，舟p ( w ) 表示w 的幂集。 ( 2 ) 称四元组m - - ( w , eg ，【】) 是双算子的命题型择类模型，简称m 是p 2 一 模型，当且仅当( w ，eg ) 是p 2 一框架且 】是从全体句符到p ( w ) 的指派映射。 ( 3 ) 所有p 2 一框架组成的框架类记为f r a m e ( p 2 ) 。_ 1 说明： 可能世界也可以看作是状态。 】也称为框架( w f g ) 上的指派映射。 定义2 2 令m - - ( w , eg ， 】) 是p 2 - 模型。 对每一复合公式a ，定义a 相对m 的真值集【a 如下：对任意w e w ， ( 1 ) w 1 a 】w 萑 a 】， ( 2 ) w e a a b w e a 且w e b ， ( 3 ) w e a c 】营f ( a ，w ) c c 】， ( 4 ) w e a c g ( a 】，w ) c c 。- 说明： 基于框架定义的模型和定义复合公式的真值集，两者合在一起称为语义， 因为由此可以在任何一个模型的任意可能世界中对任何一个公式赋予一个意义 ( 真值) 。 上面给出的语义可以称为命题型的择类语义。 例2 3 c m p l 的逆a c - - + a 7 b 相对f r a m e ( p 2 ) 不是有效式( 有效性定义请见定义 2 5 ) 。 证明： 令m - - ( w , eg ， 】) 是p 2 一模型使得： w = w = 埘p ，w ) ，g ( p 】，w ) = p = a 。 则 g ( 【p 】，、7 i d 【p ，f ( n ) ，) 霎【p 】， 所以 w 萑 a c a b 。- i 1 2 简称f 是k b 框架，当且仅 ( s d a 2 )g ( x ，w ) w g ( yw ) c _ g ( x u y , w ) ， ( c 4 1 )u e f ( x ，w ) f ( x ，u ) _ c f ( x ，、) ， ( c 4 2 )u e g ( x ，w ) = g ( x ，u ) _ c g ( x ，w ) ， ( c 5 1 )u ，w f ( x ，w ) v e f ( x ，u ) ， ( c 5 2 )u ，v e g ( x ，w ) jv e g ( x ，u ) 。 ( 2 ) 所有k b 框架组成的框架类记为f r a m e ( k b ) 。- i 定义2 5 有效性定义 令f = ( w ，f ，疹是p 2 框架，m = ( w ，eg ，【 是p 2 模型。 ( 1 ) 称a 在m 中有效，记为m a ，当且仅当 a = w ；否则称a 在m 中 不有效，记为m 忙a 。 ( 2 ) 称a 在f 中有效，记为f a ，当且仅当，对f 上的任意指派映射 】， 有 a - - w ；否则称a 在f 中不有效，记为f 乒a 。 ( 3 ) 称规则a l a n c 相对m 保持有效性，当且仅当，若【a 1 】= = 【a n 】 - - w ，则 c 】= w 。- i 引理2 6 令m = ( w ，eg ， 】) 是上述任意模型。则 ( 1 ) 1 a - - w - - a ， a x b - - - a n b ， a v b - a u b ， 【上】= o ， t 】= w ，其中上和t 分别表示某个固定的常假式和常真式。 ( 2 ) a n a - - - b c b 。 ( 3 ) a b 】= w a b 】。 ( 4 ) a c ，且 i f a ，w ) c 【b 】。 任给u e f ( a ，w ) 。据，有u e b - - - c ，再据，有u c 】。据u 的任意性，有 i f a ，w ) c c 】， 1 4 2 4 的( i d o ，对任意a ，有i f a ，w ) c a ，所以 w 【a c 】。则f ( a 】，w ) c 【c 】。据2 4 的( c m p l ) ，有 g ( a 】，w ) s c 】， 所以w a c 】。 验证公理c m p 2 ：任给w e a 7 c c t a 。有 f ( a 】，w ) c ，且 w a 】。 据和定义2 4 的( c m p 2 ) ，w f ( a ，w ) 。再据，有w e c 。 验证公理s d a l ：任给w e a v b c 。有 f ( a v b ，w ) c c ， 据引理2 6 ( 1 ) ，有埘a u b ，w ) c c 】，再据定义2 4 的( s d a o ，有 f ( 【a 】，w ) u f ( 【b ，w ) 互【c 】。 所以 f ( a 】，w ) 【c 】 且 坟 b ，w ) s 【c 】。 因此w e ( a c ) 八( b c ) 】。 同理可验证公理s d a 2 0 验证公理c 4 1 ：任给w a c 】。要证w a a c 】，为此只须证 f i a 】，w ) a c 】。 任给u e f ( a ，w ) ，要证u e a t c ，为此只须证 ( 参 坟 a 】，u ) c 。 据u e f ( a ，w ) 和( c 4 0 ，有 ( 9 f ( 【a 】，u ) 冬f ( a ，w ) 。 据w a c 】，有i f a ，w ) c 【c 】。再据，有。 l s 验证公理c 4 2 ：类似公理c 4 l 的验证。 验证公理c 5 l ：任给w 【 ( a c ) 】。要证w a _ 1 ( a c ) 】，为 ( d坟 a 】，w ) 1 ( a c ) 】。 任给u e f ( a ，w ) ，要证u 【1 ( a c ) 】，为此要证u 正【a c 】，最后只 f i ( a 】，u ) 垂 c 】。 据w e ( a c ) 】，有w 萑 a c ，因此觚a 】，w ) 霎 c 】，所以存在 v e f ( a ，w ) ，且 v 萑【c 】。 据，u e f ( a ，w ) 和( c s o ，有v e f ( a ，u ) 。再据，有。 验证公理c 5 2 ：类似公理c 5 1 的验证。 验证规则r c n l ：设 c 】= w 。任给w e w ，有f ( a 】，w ) c c 】，故w a c 】。 据w 的任意性，有 a 7 c - - w 。 验证规则r c e a l ：设 a l h a 2 = w 。据引理2 6 ( 4 ) ，有 【a d = a 2 】。 任给w e w ，有 f i a l 】，w ) c 】 c w ) 。- i 令w 是极大一致集。则 ( 1 ) a c e w 任给极大一致集u ，若w l ( a ) c - u ，则c e u 。 ( 2 ) a c e w 任给极大一致集u ，若w e ( a ) _ c u ，则c e u 。 证明： ( 1 ) “”：设a c e w 。任给极大一致集u 使得w l ( a ) g 。易见c e u 。 “乍 ：设 任给极大一致集u ，若w k a ) _ c u ，则c u 。 这意味c 属于每一以w l ( a ) 为子集的极大一致集。据引理3 3 ( 1 ) ，裢c l c n e w l ( a ) 使得 ( 爹卜c l a c n c 。 据引理1 5 ( 7 ) 的r c k l ，有 ( 爹卜( a c 1 ) 八a ( a c n ) 一a c 。 因为c l ，c n e w l ( a ) ，所以a c l ，a c n e w ，所以据和引理3 3 ( 2 ) ，有 a cq e w 。 同理可证( 2 ) 。- i 定义3 8 ( 1 ) 定义d c 的典范框架f - - 如下： w = w ：w 是极大一致集 ； li f a ，w ) _ c l c i a c e w ，对所有w e w 和公式a ，c ； 2g ( i a i ，w ) c _ l c i a c w ，对所有w e w 和公式a ，c 。 ( 2 ) 定义i ) c 的典范模型m - - 如下： 是d c 的典范 框架，且 p l - - l p ，对每一句符p 。- i 说明： 1 9 ( 1 ) d c 的( 命题型的) 典范框架相对系统d c 不是 且不存在a 使得i a i - - x 时，还没有规定f ( x ，w ) 和g ( x ，w ( 2 ) 据定理3 2 ，d c 是一致的，所以w 是非空的。 ( 3 ) 这里还要证明上述择类映射f ( i a i ，w ) 和g ( i a i ，w ) 是良定义的。设 l a l i = i a 2 1 ，i c l l = 1 c 2 1 。 据引理3 5 ( 4 ) ，有 卜a i h a 2 ，卜c l e c 2 。 据卜a l h a 2 ，r c e a l 和r c e a 2 ，易得 卜a l c l h a 2 c l ，卜a 1 c 1 h a 2 c l 。 再据i - c l h c 2 ，引理1 5 的r c m l 和r c m 2 ，易得 卜a l c l h a 2 c 2 ，卜a l c l h a 2 c 2 。 所以据引理3 3 ( 2 ) ，对所有w e w ，易证 a l c l e w a 2 c 2 e w ，且 a l c le wc ，a 2 c 2 e w 。 再据上面的1 和2 ，有 f ( i a d ，w ) c _ l c l i f ( i a 2 1 ，w ) l c 2 1 ，且 g ( i a ll ，w ) c _ l c li 甙j a 2 i ，w ) c _ l c ：l 。 定理3 9 典范模型基本定理 令 是d c 的典范模型。 ( 1 ) b e w w e b ，对每一w e w 和公式b 。 ( 2 ) j b i = b 】， 对每一公式b 。 证明： ( 2 ) 从( 1 ) 易得。所以只须证( 1 ) 。 施归纳于b 的结构。 句符的情况据定义3 8 的。 布尔联结词- 1 和八的情况如通常所证。 令b = a c 。则 w e b 】w a c 】 f ( a 】，w ) c c 】据真值集定义2 2 的( 3 ) f ( i a i ，w ) c _ l c l 据归纳假设 a 7 c e w 据上一定义的l b e w 。 令b - - a c 。则据上一定义的2 同理可证。- 定理3 1 0 令m - - 是d c 的典范模型。则对每一公式a ，有 m a c ，i - a 。 证明： 卜a i a i = w据引理3 3 ( 3 ) 一( 4 ) a - - w据上一定理 mi = a据有效性定义2 5 。 定义3 1 l 定义i ) c 的适当结构( p r o p e rs t r u c t u r e ) m 木= 如下。 ( 1 ) w = w ：w 是极大一致集) 。 ( 2 1 ) f 是从p ( w ) w 到p ( w ) 中的映射：对任意x c w 和w w ， 厂 u ：w l ( a ) 剑 ， 存在a 使得= x ； f 【x ，w ) = l _ x ，否则。 ( 2 2 ) g 是从p ( w ) w 到p ( w ) 中的映射：对任意x c w 和w e w ， 厂 u ：w 2 ( a ) u ) ， 存在a 使得1 a l = x ； g ( x ，w ) = 7 c e w ， 对所有w w 和公式a ，c ； 2g ( i a i ，w ) c _ l c l a c w ，对所有w e w 和公式a c 。 证明l ：据上一定义的( 2 1 ) 和( 2 2 ) ，有 ( a 1 ) f ( i a i ，w ) = u ：w l ( a ) c u ) ， 对所有w e w 和公式a ； ( a 2 ) g ( i a i ，w ) = u ：w 2 ( a ) c u ) ， 对所有w e w 和公式a 。 因此任给公式c ，有 a 7 c e w v u w ( w l ( a ) c _ ujc e u )据引理3 7 ( 1 ) v u e w ( u f ( i a i ，w ) u l c i )据( a 1 ) 铮f 0 a i ，w ) 互j c l 。 据引理3 7 ( 2 ) 和( a 2 ) ，同理可证2 。- 定理3 1 3 框架完全性定理 d c 相对框架类f r a m e ( k b ) 是完全的。 证明： 据定理3 1 0 ，为了证明d c 相对f r a m e ( k b ) 完全，只须证明上面的f 宰属于 f r a m e ( k b ) 。 据上一引理，只须证f 宰满足定义2 4 的框架条件：任给w e w 和x c w 。 验 j e ( i d l ) ：任给u e f ( x ，w ) 。要证u e x 。 情况1 存在a 使得i a i = x 。则u f ( i a i ，w ) 。据3 1 2 的证明中的( a 1 ) ，有 ( # ) w l ( a ) c u 。 另一方面，据引理3 3 ( 3 ) ，公理i d l 在w 中，所以 a a w ， 所以据( # ) ，a e u ，所以u l a i ，所以u e x 。 情况2 不存在a 使得i a i - - x 。据定义3 1 1 的( 2 1 ) ，我们有f ( x ，w ) = x 。 因为u e f ( x ，w ) ，所以w e x 。 验i i e ( c m p l ) ：任给u e g ( x ，w ) 。要证u e f ( x ，w ) 。 情况1 存在a 使得i a i - - x 。则u e g ( i a i ，w ) 。据3 1 2 的证明中的( a 2 ) ， ( ) w 2 ( a ) a i 。 另一方面，据引理3 3 ( 3 ) ，公理c m p l 在w 中，所以 a c 专a c t e w ， 所以据引理3 3 ( 2 ) ，易证 a c e w a c e w 。 因此对任意u e w 和公式c ，有 ( a c e w c e u ) j ( a c e wjc e u ) 。 所以据定义3 6 ， w 2 ( a ) _ c ujw l ( a ) g 。 因此据( ) ，有w 1 ( a ) c u 。再据3 1 2 的证明中的( a 1 ) ，有u f ( i a i ，w ) ，即 u e f ( x ，w ) 。 情况2 不存在a 使得i a i - x 。据3 “的( 2 1 ) 和( 2 2 ) ， f ( x ，w ) = x = 甙x ，w ) 。 因为u e g ( x ，w ) ，所以u e f ( x ，w ) 。 验证( c i n p 2 ) ：任给w e x 。要证w e f ( x ，w ) 。 情况1 存在a 使得i a i - x 。则w l a i ，因此a e w 。据引理3 3 ( 3 ) ，公 理c m p 2 在w 中，所以对任意c ，有 a c 专a c w ， 所以据a e w 和引理3 3 ( 2 ) ，易证 2 3 a c e w c e w 。 所以据c 的任意性，w l ( a ) c w ，据3 1 2 的证明中的( a 1 ) ，w e f ( i a i ，w ) ，即 w e f ( x ，w ) 。 情况2 不存在a 使得i a i = x 。据3 1 1 的( 2 2 ) ，f ( x ，w ) - x 。因为w e x ， 所以w e f ( x ，w ) 。 验i 正( s d a o ： 情况1 存在a 和b 使得i a = xi ；i i b i - - y 。任给u e w ，要证 u f ( i a i ，w ) u f ( 1 b i ，w ) u e f ( 1 a i u i b i ，w ) 。 据引理3 3 ( 3 ) ，公理s d a l 在w 中，所以据引理3 3 ，有 a v b ；， c e w a c e w 且b7 c e w 。 所以 ( a 7 c e w c e u ) 或( b 7 c e wjc e u ) j ( a v b 一c e w c e u ) 。 因此 w 1 ( a ) _ c u 或w l ( b ) 剑w l ( a v b ) c u 。 据3 1 2 的证明中的( a 1 ) ，有 u e f ( i a i ，w ) 或u e f ( i b i ，w ) ju e f ( i a v b i ，w ) ， 据引理3 5 ( 1 ) ，有 情况2 不存在a 和b 使得i a i = x 且| b i = y 。据3 11 的( 2 1 ) ， f ( x ，w ) = x ，f ( yu ) = y ，f ( x u y ，w ) = x w y 。 所以总有 f ( x ，w ) u f ( y , w ) c f ( x u y , w ) 。 情况3 不存在a 使得i a i = x ，但存在b 使得i b i = y 。据3 1 l 的( 2 1 ) ， f ( x ，w ) = x ， f ( i s l ，w ) = u ：w l ( b ) _ c u f ( x u i b i ，w ) = x b i 。 要证 4 f ( x ，w ) u f ( i b i ，w ) s f ( x w l b i ，w ) 。 须证 x u f ( i b i ，w ) _ c x u l b i 。 据刚刚验证成立的( i d o ，有f ( 1 b ，w ) 至i b i ，因此有。 情况4 存在a 使得i a i = x ，但不存在b 使得i b i = y 。本情况的验证如情 况3 的验证。 验i e ( s d a 2 ) ：据( c m p l ) 和( i d l ) ，有g ( x ，w ) c _ x 。其余证明类似( s d a l ) t 拘验证。 验证( c 4 0 ：设u e f ( x ，w ) 。要证 f ( x ，u ) c f ( x ，w ) 。 情况1 存在a 使得i a = x 。则u f ( i a i ，w ) ，据3 1 2 的证明中的( a 1 ) ，有 w l ( a ) c u 。 要证： f ( 1 a i ，u ) c _ f ( i a i ，w ) 。 任给v e f ( i a i ，u ) ，有 u l ( a ) c v 。 要证v e f ( i a ，w ) ，只须证w i ( a ) c - - v ，最终只须证： a ；，c e w c e v ，对任意c 。 任给c 使得a 7 c e w 。据引理3 - 3 ( 3 ) ，狸c 4 l 在w 中，所以据3 3 ( 2 ) ，有 a c e w a a c e w 。 因此据给定，a a c w 。据，有a 7 c e u ，据，有c e v 。因此证明了 。 情况2 不存在a 使得i a i = x 。据3 1 1 的( 2 2 ) ， f ( x ，w ) - - f ( x ，u ) = x 。 显然有。 验证( c 4 2 ) ：类似( c 4 0 的验证。 验证( c 5 1 ) ：设u ，v e f ( x ，w ) 。要证 2 s v e f