（计算机软件与理论专业论文）用于不完全信息数据库的逻辑系统研究.pdf

南柬航空航犬人7 ：硕十学俺论文 摘要 不完全信息数据库是数据库领域的重要研究方向不仅具有重要的理论价值，而 且还具有重要的应用价值。中介逻辑命题演算系统m p 。和中介逻辑谓词演算系统m f l 是 一种适用于处理不完全信息的新的逻辑系统。本文建立了m p ”系统的范式理论，构造 了其表推演系统，并证明了其可靠性和完各性。该范式理论能够在三值环境下依1 日保 留等值完全范式与真值表一一对应的直观关系，同时，建立的表推演系统可作为不完 全信息的自动推演系统。此外通过引入判真、判中和判假三个算子给出了m f 。系统 与经典二值逻辑系统的关系，并以经典二值逻辑系统作为工具讨论了m p 系统的消解 理论，该消解理论能够完全利用经典二值逻辑系统的理论方便地解决m f 。的消解问题。 关键词：关系数据库、不完全信息、不完全信息数据库、表推演方法、中介逻辑系 统 型! 至至苎堕：垦垫塑堕墅篓塑至堑婴茎 a b s t r a c t i n c o m p l e t ei n f o r m a t i o nd a t a b a s ei sa nj m p o r t a n t f i e l di nd a t a b a s et h e o r y i th a s i m p o r t a n t t h e o r e t i c a la n dp r a c t i c a lv a l u e s t h em e d i u m l o g i cp r o p o s i t i o n a lc a l c u l u ss y s t e mm p m a n dt h em e d i u m l o g i cp r e d i c a t ec a l c u l u ss y s t e mm f ”a l en e wl o g i cs y s t e m s t h e ya r e n tf o rd e a l i n gw i t hi n c o m p l e t ei n t b r m a t i o n t h i sp a p e rd i s c u s s e st h es y s t e mm p ”a n d m f m c o n s t r n c t st h en o r m a lf o r mt h e o r i e so fm p ma n di t st a b l e a us y s t e m t h es o u n d n e s s a n d c o m p l e t e n e s st h e o r e m o f t h et a b l e a us y s t e ma r ea l s og i v e n t h en o r m a lf o r mt h e o r i e s c a nk e e pt h ei n t u i t i o nr e l a t i o n s h i pb e t w e e nt h ec o m p l e t en o r m a lf o r ma n dt h et r u t h t a b l e ，w h i c ho n l yk e e p si nc l a s s i c a l2 - v a l u e dl o g i cs y s t e m t h et a b l e a us y s t e mc a na c ta s t h ea u t o m a t e dr e a s o n i n gs y s t e mi ni n c o m p l e t ei n f o r m a t i o ne n v i r o n m e n t s i na d d i t i o n ，b y i n t r o d u c i n g t h r e e o p e r a t o r s ，j u d g i n gt r u e ，j u d g i n g m e d i u ma n dj u d g i n g f a l s e ，t h e r e l a t i o n s h i p b e t w e e nt h e s y s t e mm f ma n d t h ec l a s s i c a l2 - v a l u e d l o g i cs y s t e m i s d i s c u s s e d b a s e do nt h er e l a t i o n s h i p ，t h er e s o l u t i o np r i n c i p l e so fm f “1a r e g i v e nb y t a k i n gt h ec l a s s i c a l2 - v a l u e dl o g i cs y s t e ma sat 0 0 1 t h er e s o l u t i o np r i n c i p l e ss h o wt h a t t h er e s o l u t i o np r o b l e m sc a nb es o l v e db yu s i n gt h et h e o r i e so ft h ec l a s s i c a l2 - v a l u e d l o g i cs y s t e m k e yw o r d s ：r e l a t i o n a ld a t a b a s e ，i n c o m p l e t ei n f o r m a t i o n ，i n c o m p l e t e i n f o r m a t i o n d a t a b a s e ，t a b l e a um e t h o d ，m e d i u ml o g i cs y s t e m 向京航空航大人学硕 学位论文 第一章绪论 如今，关系数据库理论模型已经近乎完美，而且各种关系数据库系统几乎在各 个方面都非常成功。虽然如此，目前仍然存在着一些问题，这些问题束缚了关系数 据库系统的发展。数据库中的不完全信息问题是其中之一，本文将讨论该问题。 由于客观世界的复杂性，不完全信息、不确定信息以及模糊信息是普遍存在的。 数据库作为表达现实世界的手段，不可能回避不完全信息问题。因而，一个能够表 示和处理不完全信息的数据库系统具有现实意义和应用价值。 1 2 不完全信息数据库 传统的关系数据库理论是建立在信息完全的基础之上的，不允许缺失信息的存 在，这和早期数据库管理系统的处理能力是相适应的。由于客观世界的复杂性，不 完全信息、不确定信息以及模糊信息是普遍存在的。数据库系统作为表达现实世界 的一种手段，自然不能回避不完全信息问题。 在关系数据库领域，用空值( n u l l ) 代表不完全信息是目前广泛使用的方法。 由于不同的原因，导致需要各种不同的空值类型。a n s i1 9 7 5 共列出了1 4 种可能在 现实中出现的空值类型。对于这些空值的分类主要是基于应用和实现的角度来考虑 的。理论上说这些空值类型大致被分成3 种类型：不存在型或者属性不可用型，占 位型和值未知型。不存在型意味着在指定域中不存在有意义的值，无信息型表示没 有关于该属性值的任何信息。未知型是指存在这种类型的值但是目前不知道。下面 举例说明这几种类型的空值： 表1 1 空值类型示例 表1 1 表明了三种类型的空值，n u l l l 、n u l l 2 和n u l l 3 分别代表不存在型空值、 存在型空值和占位型空值，该例摘自文献 1 。 上表中的4 个元组，只有第一个元组是f 常的。对于第二个元组，由于许玉萍 hr 不完全信息数据庠的逻辑系统研究 未结婿，所以关于配偶姓名是不存在的。对于第三个元组而言，配偶姓名的信息显 然存舀那! 足不知道。而对于张立东，由于不知道他的婚姻状况，所以对于他的配偶 姓名足未知还是不存在都不知道，这种情况可称之为无信息，这种类型的空值属于 无信息类型。 传统的关系数掘库理论是以经典的二值逻辑( 2 v l ) 和精确的数学工具为基础 的，比较运算和逻辑运算的结果只有两种状态：真与假( 分别用逻辑值t 和f 表示) 。 但在空值环境下，二值逻辑难胜任不完全信息的处理，不能充分体现空值的语义， 更不能适应精确记录比较及逻辑运算结果的需要。 为了克服传统数据库模型不能很好地处理不完全信息这一缺陷，从7 0 年代到 8 0 年代出现了很多改进的数据库模型。最具有开创性的成就是由关系模型的奠基者 e ，f c o d d 做出的。他于1 9 7 9 年首次提出了用三值逻辑从不完全信息数据库中抽取 数据的思想。虽然他的处理空值的方法受到某些学者的批评。”1 ，但正如j - 8 i s k u p 所说，这种方法具有明显的优点，空值的处理可以统一在传统的关系数据库框架之 内，实质上没有增加基本算法的复杂陛。因此最重要的空值类型能以切实可行的方 式进行管理1 。另外，空值的系统化处理已成为全关系系统的基本准则。目前，关 系数据库标准语言s o l 2 和s q l 3 处理空值也是以三值逻辑为基础的。1 。r f r o s t “ ( 1 9 8 5 ) 提出了利用三值逻辑处理不完全关系结构数据库的方法，但没有形成理论 体系，仅是非形式的描述。1 9 9 1 年，k y u e “”提出了利用三值逻辑处理缺失信息的 更一般的模型，但没有给出形式系统。m n e g r i “4 等用三值逻辑讨论了s q l 查询的 形式语义，但仅是非形式的讨论，所用的三值逻辑系统的表达能力也较弱。 近年来，g a r c i a 和m o u s s a v 将k l e e n e 三值逻辑和l u k a s i e w i c z 三值逻辑的 思想集成，提出了一种处理不完全信息的六值逻辑m 8 ，但缺乏作为自动推理基础的 证明论。a k a m a 给出了该逻辑的一种矢列型证明方法，并讨论它和b e l n a p 四值逻辑 之间的联系“。主要不足有： ( 1 ) 没有相应的谓词逻辑，需进步建立对量词的有效证明机制； ( 2 ) 不能处理假言推理，在地中很难给出蕴涵词的定义； ( 3 ) 基于时态逻辑，选择了四种不同的未知真值，对数据库的实际应用带来 不便。 近年，以中介逻辑“6 ”1 为基础，创立了适合处理不完全信息的中介逻辑命题演 算系统m 和中介逻辑谓词演算系统! i l 一。在此基础上建立了一种新的适用于不完 全信息数据库应用需求的理论体系“。目前对于该系统的研究一直在进行当中， 本文是该研究的一个组成部分。 南京肮空肮犬人学硕十学 ：) = 论文 1 3 不完全信息数据库的解决方案 1 3 1 多值逻辑( m a n y v a l u e dl o g i c ) l b 于在空值环境下，二值逻辑较难胜任不完全信息的处理，不能充分体现空值 的语义更不能适应精确记录比较及逻辑运算结果的需要，因此应引入多值逻辑 ( m v l ) 。为了充分体现空值的语义，许多学者在不完全信息数据库的研究中引入了 3 v l 、r t v l 、5 v l 和7 v l 。它的发展经历了出3 v l 到4 v l 又到7 v l ，最后由7 v l 又回到 3 v ，的过程。3 v l 的产生是基于空值数据可用但值未知语义的，它是在传统二值逻 辑真与假的基础上加上未知( u n k n o w n ) 逻辑值构成的。当不可用数据语义引入空 值后，为区分不可用这种结果，在3 v l 中加入了不可用逻辑值构成4 v l 。4 v l 的出 现是空值不可用及可用值未知两种语义的必然结果，与3 v l 相比，4 v l 能区分出假 与不可用的语义差别，因而4 v l 是空值两种语义下适用于不完全信息数据库的多值 逻辑。应当看到，4 v l 虽然比3 v l 精确，但它是基于空值两种语义的，而空值两种 语义是不完全的，完备的空值语义还应当有可用性未知这层意义。如果不作简化， 基于三种空值语义的多值逻辑应是七值逻辑( 7 v l ) ，它们的含义分别是：( 1 ) 真值； ( 2 ) 假值，( 3 ) 不可用值，( 4 ) 或为真或为假值；( 5 ) 或为真、或为假、或为不可用值； ( 6 ) 或为不可用、或为真、但不能为假值；( 7 ) 或为不可用、或为假、但不能为真值。 7 v l 对于精确地描述三种空值语义下的比较运算与逻辑运算结果确实是必要的，但 7 v l 对台空值的关系数掘库来说并不实用。这是由于7 v l 无论在使用上还是在维护 上都太复杂，例如，以a n d 和o r 操作的真值表就需要4 9 个条目。所以，基于上述 考虑，7 v l 必须化简。 对7 v l 的化简有两种考虑：化简成3 v l 或4 v l 。化简成3 v l 是把7 v l 中的不可 用值看成与假值同义而得到，系统实现相对容易，但它不能区分出不可用及假两种 状态的差别且体现不出可用性未知这种逻辑状态。直观地看似乎化筒成4 v l 是最 佳的选择，但实际上化简成4 v l 是不可接受的，这除了因为4 v l 下的a n d 和o r 操 作结果仍不唯一之外，还有一个主要原因就是还没有找到合适的途径来完成7 v l 到 4 v l 的化简。谭桂兰和严丽在文 1 9 考虑将7 v l 化简为5 v l ，在7 v l 中保留不可用 值、或为真或为假值、真值和假值4 个状态，同时引入一个新的状态值：或为不可 用或为可用，构成了5 v l 。5 v l 的真值分配及其含义如下： 0 ：不可用： l ：可用性未知； 2 ：可用但为假： 3 ：可用但值不知真假； 4 ：可用但为真。 k w o k b u ny u e 在文 1 2 中非形式地描述了将7 v l 化简成3 v l 的处理缺失信息的 更一般模型，主要思想是直接简化为3 v l ，再辅以一些逻辑函数便可以处理空值的 “r ：不完全信息数据库的逻辑系统研究 所拈二种解释。 m 不论在理沦研究还是实际系统中，一般只选取7 值中的3 值柬袭达不完 全信息即采用3 v l 。然而当前的三值逻辑由于难于理解和反直觉受到批评，从而 引起了9 0 年代仞的场大辩论。许多学者，包括关系数据库之父e f c o d d ，相 f 占空值和三值逻辑是数据库的f 确解决方案。其存在的问题完全可以通过采用改良 的方法得以解决，而不是采用革命的方法。 1 3 2 特殊值 c j d m e 是强烈反对三值逻辑的代表者之一。1 + i “。以d a t e 为代表的一些学者 提出使用标准化的缺省值的方法来表示缺失信息，在这种方式下自然再也不需要三 值逻辑了1 。 这种方法的基本思想非常简单：在数据库模型里，当某种信息缺失时，用一个 真实的值( 缺省值) 柬代替空值，从而完全不会破坏关系模型。例如：一个关于学 生信息的表，如果某个学生的年龄项缺失，则很自然用个特殊值如一1 来表示该 缺失信息，因为任何人的年龄不会是一1 。 这种方法是基于特殊值和2 v l 的，而不是空值和3 v l 。拥护使用这种方法的学 者认为：“在现实世界里不存在空值这样的事物”“。于是数据库系统在这个方面 应该像现实世界处理问题一样来处理不完全信息。 1 3 3 第六范式( 6 n f ) c j d a t e 和h u g hd a r w e n 提出用第六范式( 6 n f ) 来解决不完全信息问题。“。 利用6 n f 方法可以在理论上解决不完全信息的表示问题。该方法利用第六范式来设计 数据库。 第六范式：一个表满足第六范式( 6 n f ) 当且仅当它由主码外加至多一个其它列 组成。 满足第六范式的关系是不能再化简的关系。一个第六范式表只表达一个唯一含义 的主题。利用第六范式解决不完全信息问题的方法简述如下： 在数据库设计时，需要对数据库做“垂直”分解和“水平”分解。所谓“垂直” 分解是指：利用投影操作将一个表分解成两个或更多的表。使得分解后的表最多只有 2 列，其中一列是主码列。这些分解后的子表可以通过连接( j o i n ) 操作将其复原。 表1 2 。1 3 ，1 4 是对表1 1 做垂直分解的结果。在“垂直”分解的基础上接着再进行“水 平”分解。水平分解的目标是：不要将表达不同意义的行置于同一个表中。所以需要 将表1 3 水平分解成两个表，表1 5 和表1 6 ，这两个表表示不同的主题。由于表1 - 4 中各行的空值具有不同的语义，所以需要将其水平分解成四个表，见表1 7 一1 1 0 a 南京航! ；三航犬人。产硕十学位论文 往j 二述6 x 1 ：的数掂库设计之f ，自然可以知道在数据库的完整性方面以及数据库 的哑新疗【f 【i 和以| j i 的设计模式有所不再j 。此外，由于不能将6 n f 表直接呈现给用户， 所以擂要通过查咖重构建的方法来组合成用户视图。关于该方法的详细讨论参见文 2 1 。 表1 2 年龄 姓名年龄 李天龙 许玉萍 杨冬伟 张立东 4 0 2 3 3 5 2 6 表1 4 配偶姓名 姓名配偶姓名 李天龙 许玉萍 杨冬伟 张立东 韩晓娟 n u l l l n u l l 2 n u l l 3 表1 6 婚姻状态 张立东 衰1 8 配偶姓名 许玉萍 表1 1 0 配偶姓名 张立东 表1 3 婚姻状态 姓名婚姻状态 李天龙 许玉薄 杨冬伟 张立东 已婚 未婚 已婚 n u l l 2 表1 5 婚姻状态 姓名婚姻状态 李天龙 许玉萍 杨冬伟 已婚 未婚 已婚 表1 7 配偶姓名 姓名配偶姓名 李天龙韩晓娟 表1 9 配偶姓名 杨冬伟 r i ；完仝信息数据库的逻辑系统研究 1 4 中介系统 巾介系统1 是基于巾介原则的哲学背景提出来的，以中介逻辑系统为逻辑工具 而建立的一种新的数学理论体系。自创立以来，在语形、语义等方面得到了广泛的 研究是目 讨研究较为彻底的一类逻辑系统。狭义的中介系统仅仅指中介逻辑演算 系统l 。它 b5 个演算系统构成：中介命题逻辑演算系统m p 及其扩张系统m p + ，中 介谓词演算系统m f 及其扩张系统mf - ，带等词的中介谓词演算系统m e 。而广义的中 介系统不仅包括上述的逻辑演算系统扎，还包括如中介代数系统、中介模态逻辑系 统、中介公理系统、中介证明论系统、中介模型论系统、中介模型力迫论系统、不 完全信息推理系统、中介程序设计语言m i l l 及其解释系统、中介自动推理的理论 与实现系统、中介直觉主义系统等内容。 虽然早期的中介逻辑系统在计算机领域尤其是人工智能领域有一定程度的应 用，但由于其哲学背景强，在这些方面的应用一直受到限制。近年来，为了将中介 逻辑系统的研究成果进一步应用于计算机软件与理论，提出了中介逻辑系统m 儿 m 掣。该系统可以作为不完全信息数据库的逻辑基础。 1 5 本文的主要研究内容 随着中介逻辑系统m ，m f 。的提出，对于该系统的相关研究自然提上了议事同 程，本文正是该系列研究的一个组成部分。主要完成如下三个方面的工作： 1 解决中介逻辑系统m 的合式公式规范化问题，奠定m 一的范式理论的基础。 依据该范式理论建立的等值完全析驳范式能够保持和真值表一一对应的优点，而这 一优点通常只有在二值逻辑系统中才具备。这部分内容在本文第三章详细讨论。 2 建立了中介逻辑系统m 的消解理论，为不完全信息的自动推理奠定理论基 础。该消解理论不同于以往的三元消解。本文通过引入了判真、判中和判假三个算 子给出了中介逻辑谓词演算系统一与经典二值逻辑系统的关系，并据此，以经典 二值逻辑系统作为工具讨论了一的消解理论，浚消解理论能够完全利用经典二值 逻辑系统的理论方便地解决m 一的消解问题。这部分内容在本文第四章详细讨论。 3 为了给不完全信息的自动推理提供理论基础，本文为中介逻辑系统m 建立 了表推演系统。提出了i 3 条简洁的推理规则作为自动推演证明的基础，并证明了 该系统的可靠性和完备性。浚系统不需要将公式化为某种特定的标准形式，易于向 非经典逻辑推广，此外，该系统还便于实现人机交互式证明。本文的第五章讨论该 表推演系统。 上述的研究内容将是不完全信息自动推理的理论基础它对于不完全信息的完 整性维护、查询优化等问题的讨论带来很大方便。 6 南京航空航大人学硕十学侥论文 第二章中介逻辑系统m 及m p 本紫讨沦中介系统，介绍中介系统的哲学背景和思想原则以及它在计算机科学 中的应用。另外，还讨论丁用于处理不完全信息的中介逻辑系统m p 和m n 介绍了 这两个系统的构成以及主要定理，并给出了该系统的可靠性和完备性。 2 1 中介系统 本小节的主要内容参考文献 1 6 ，2 2 ，2 3 。 中介系统的第一篇文章“”发表于1 9 8 4 年。至今，中介系统经历了近3 0 年的发 展，已经在语形、语义等方面得到了广泛的研究，是目前研究较为彻底的一类逻辑 系统。中介系统，顾名思义它是基于中介原则的哲学背景提出来的，以中介逻辑系 统为逻辑工具而建立的一种新的数学理论体系。 狭义的中介系统仅仅指中介逻辑演算系统m l 。它由5 个演算系统构成：中介命 题逻辑演算系统p 及其扩张系统m r ，中介谓词演算系统m f 及其扩张系统mf i | 带 等词的中介谓词演算系统m e 。 广义的中介系统不仅包括上述的逻辑演算系统m l ，还包括下列内容和研究方 向： 中介代数系统 中介模念逻辑系统 中介公理集合论系统 中介证明论系统 中介模型论系统 中介模型力追论系统 中介不完全信息推理系统 中介程序设计语言m i l l 及其解释系统 中介自动推理的理论与实现系统 中介直觉主义系统 关于中介系统的详细介绍参考文献 1 6 ，2 2 ，2 3 。 2 1 1 中介系统的哲学背景和思想原则 自从a r i s t o t l e 咀来，形式逻辑就有了对反对对立和矛盾对立的区分。如果两个 概念都有其自身的肯定内容，并在同一内涵的一个更为高级的概念中，两者之间存 】丁不完全信息数据j 车的逻辑系统研究 饭坡火的麓肄，那么这两个溉念就是反对对立概念。例如：善和恶，荚和丑。丽如 粜炳个概念- f j 如辛一个的内涵否定另一个的内涵，那么这两个概念就是矛盾对立 ：【念。例姻：人类和非人类，党员和非党员等。 没p 为一滑词( 概念或者性质) ，若对任意对象x 而言，总是要么x 完全满足p ， 要么x 完全不满足p 办即不存在这样的对象，它部分地满足p ，又部分地不满足p ， 则我们说p 是清晰悄词，并简记为d i s p 。又若对谓词p ，有某个对象x ，它部分地 j 有性质p ，部分地不具有性质p ，则称p 是模糊谓词，简记为f u z p 。用形式符号 ”束表示模糊否定词，解释并读为“部分地”，则p ( x ) 表示对象x 部分地具有 性质p ，而p ( x ) 表示对象x 完全具有性质p 。用符号“了”表示对立否定，对立否 定词“7 ”解释并读作“对立于”。并将谓词p 的反对对立面丑做7p 。这样就可以 用p 和7p 抽象地表示一对反对对立概念。而用p 和一p 抽象地表示一对矛盾对立 概念。 现在任给p 和了p ，如果对象x 满足p ( x ) & 7p ( x ) ，即x 部分地具有性质p ， 又同时部分地具有性质，p ，我们就说x 为p 和亨p 的中介对象，这正是体现了哲 学上“办此办彼”的概念，这旱的“此”与“彼”分别用p 和亨p 表示。对于其中 的x ，它表达了中介的概念，是中介对象。 在经典二值逻辑和精确性经典数学中既不考虑普遍存在且人们常常使用的模 糊性质或模糊概念，也不考虑中介对象的存在。而中介系统是在承认中介对象存在 的前提下建立逻辑演算系统m l 和公理集合论系统m s ，即所谓的中介数学系统 m m 。在m m 中，始终贯彻着这样的一个原则：并非对于任何谓词p 和对象x ，总 是要么p ( x ) 为真，要么了p ( x ) 为真。也就是说，存在这样的谓词p ，对象x 使得p ( x ) 和7p ( x ) 都部分地为真。这条原则称之为“中介原则”。在构建中介系统或中介数 学系统中，它是一条默认的原则，并不是以公理的形式体现的。 综上所述，这就是构造中介系统的哲学背景和思想原则。 2 1 2 中介系统在计算机科学中的应用 由于中介系统贯彻了“中介原则”。相对于经典二值逻辑和经典精确数学而言 能够更准确地表达现实世界。能够在实践中得到广泛的应用。 人的恩维在本质上存在过渡和中介，推理过程也是如此，因而涉及到思维、推 理、判断和决策等涉及到中介对象的地方都可以利用中介系统。 下面将介绍用于不完全信息数据库的中介系统，2 2 2 4 的主要内容参考文献 1 8 。 萄京航j 三航夫人。硕f 傅论文 2 2 中介命题演算系统m 不完全信息问题存在于每一种数据库模型中。传统的二值逻辑难以适应不完全 信息处理的i 精求。而多值逻辑能更多地捕获不完全信息的直觉含义。在关系数据库 系统的实观中，对不完全信息的处理般都采用三值逻辑，但仅使用常用的a n d 、 ( ) rf f ln o t 三个联结词。为满足实际应用的需要，提出了中介逻辑系统m p ”和m f 】， 它选取了适用于刁i 完全信息处理的一组联结词八、v 、一、一和p 作为构造逻辑系 统的原始联结词。构造该三值逻辑演算系统，并证明了m p ”的一些基本定理及与 其它逻辑系统的不等价性。其中，m f m 为研究不完全信息数据库理论建立了逻辑基 础。 对不完全信息的处理，结构查询语言s q l 2 用一个特殊值n u l l ( 空值) 表示缺 失信息，在对个条件表达式进行求值时，采用三值逻辑，即表达式的结果有三种 可能的真值：真( t ) 、假( f ) 和未知( u ) 。复合条件由原子条件经逻辑联结词复 合而成。常用的联结词有与( 八) 、或( v ) 、非( 一) 和蕴涵( 一) 。为便于处理 空值，我们增加了一个新的联结词u ，读作“未知”或“不确定”。故m p ”系统选 取的原始联结词是：八、v 、一、一和u 。二元联结词八、v 、一和一元联结词一 的真值表与k l e e n e 三值逻辑系统的真值表相同，一元联结词u 的真值是，当命题a 的真值为未知时，ua 取真，否则为假，其真值表如表2 1 所示。联结词 、v 、 一和u 分别对应于不完全信息数据库的a n d 、o r 、n o t 和m a y b e 运算符。 表2 1m p ”系统联结词的真值表 如下 m p ”系统的符号系统、合式公式形成规则类似于m p + 。m p m 的形式推理规则 ( )a 。凡，a 。卜a ，( i = l ，2 ，n ) ( tj直口果r _ f a ，贝0r 卜a 坚塞型兰望：鍪塑堕堕望塑墨竺婴壅 ( 八一) a a j 卜a ，【3 ( 八十)a ，b 卜a 八b ( 一八)一( a 八b ) h a v b ( v 一) 如果r ，a 卜c 且r ，bf c ；贝0f a v bf c ( v + )a 卜 v b ，b v a ( 一v )一( a v b ) h a 八b ( 一一)a b ，a a b ，ua 卜b ( 一十) 如果1 7 ，a 卜8 且厂，“a - b ：则rh 一b ( 一一)一( a b ) ha 八一b( 假蕴含律) ( 一一) at - t 一一a ( 重假律) 、 ( up )u 灶a 卜b ( u 3 ) 如果f ，a 卜b ，r ，ua 卜b 且r ，a 卜b ；贝0r 卜b ( 1 1 1 )a ，ua 卜b ( h 2 )a ，、a 卜b ( h 3 )ua ，- 1 a 卜b 其中，( u 3 ) 称为三分律，类似于反证法；( u “) 称为未知律，表示未知的未 知可推出任意；( h i ) 、( h 2 ) 、( h 3 ) 称为海丁律，表示三个文字a ，ua ，a 中任 意两个组合在起都产生矛盾。 2 2 1 基本弓i 理 引理2 1m p m 中下列定理成立： 1 a - b a 2 一b 卜b a 3 a bh a v b 4 a hb 卜“( a b ) 5 pa 八ub 卜u ( a b ) 6 pa a b 卜u ( a - - b ) 引理2 2m p m 中下列定理成立 1 a aub 卜u ( a b ) 2 # a a b 卜4 ( a 八b ) 3 pa a “b 卜“( a a b ) 4 pa aub u ( a v b ) 5 pa 八一b 卜“( a v b ) 6 一a 八ub _ u ( v b ) ( 真后件律) ( 假前件律) 0 一旦! ! ! 堕至堕_ 犬叁兰：堕兰堕堡圣 2 2 2 常j j 的些重要定理 定j 哩2 1m p m 中下歹l l 定理成立： | u ( a 八【j ) h ( a 八ub ) v ( t - ta a b ) v ( ua 八ub ) 2 p ( a v b ) h ( ua aub ) v ( pa 八_ 1 b ) v ( a 八“b ) ：j u ( 一b ) h ( pa 八“b ) v ( ua a b ) v ( a aub ) ，t u ( a 八i 八c ) h ( ua 八b 八c ) v ( a 八pb 八c ) v ( a b 八uc ) v ( ua 八ub 八c ) v ( a 八“b auc ) v ( ua 八b 八uc ) v ( ua 八ub 八i tc ) 5 u ( a v b v c ) h ( ua 一b 一c ) v ( 一a ub a c ) v ( - 1 a 八一b 八uc ) v ( ua 八ub 一c ) v ( 一a ub 八uc ) v ( ua a b uc ) v ( na ub 八pc ) 定理2 2 在m p m 中，下列定理成立： l 一b t aha v a 2 p ah “a 3 a 卜一u a 4 一a 卜一1 ta 5 a v b ，ua 卜b 6 a v b 。一a 卜b 定理2 3 在m p m 中， 1 若a 卜b ，pa 卜ub ，一a 卜r - 1 b 贝0bh ，ub 卜ua ，- 1 b 卜一a 。 2 3 若ahb 且ah b ，则uahub 2 2 。3 等值定理 定理2 4 ( m p m 的替换定理) 在m p m 中，有合式公式的可替换性：如果ahb ， uahub 且- 1 ah b ：则对任何合式公式f ( p ) 有：f ( a ) hf ( b ) ，p f ( a ) h “f ( b ) 且一f ( a ) h f ( b ) 。 定义2 1 如果对m p m 的任何合式公式f ( p ) 总有 f ( a ) hf ( b ) ， 则称 与b 等值，或者说在公式中任何a 的出现和b 的出现可以互相替换，记为 hb 。 定理2 5 在m p ”中，下列定理成立： 1 若a 卜b 且ua 卜b 且一a 卜一b ，则ah b jt1 ：完全信息数据库的逻辑系统研究 ： 嚣ahl j 且一ah b ，则ah b ! ： 若 h1 且“ah ub ，则ahb ，1 若uahub 且一ah b ，则ahb 定理2 6 住m p m 中下列定理成立： 1 一( a 八b ) h a v b 2 一( a v b ) h 一 八一b 3 a bh a v b 钔p ahu a 5 一一ah a 2 3 中介谓词演算系统m 中介逻辑谓词演算系统m f m 是在中介逻辑命题演算系统m p m 的基础上引入谓 词和量词形成的，m f m 中没有常元和函数。m f m 中合式公式的形成规则类似于m f + 的形成规则，形式推理规则在m p ”的基础上增加了有关全称量词和存在量词的推 理规则。 m f m 增加的形式推理规则如下： ( v 一) v x a ( x ) k a ( a ) ( v + )如果厂卜a ( a ) ，其中a 不在r 中出现；则r 卜v x a ( x ) ( j 一) 如果a ( a ) 卜b ，其中a 不在b 中出现：则3 x a ( x ) 卜_ b ( j + )a ( a ) 卜3 x a ( x ) ，其中a ( x ) 是由a ( a ) 把其中a 的某些出现 替换为x 而得。 ( 一v )一v x a ( x ) h3 x _ 1 a ( x ) ( 一 )一j x a ( x ) hv x a ( x ) 其中，( v 一) 、( v + ) 、( 3 一) 、( j + ) 、( _ 、v ) 和( 一i ) 依次叫做全称量词消去 律、全称量词引入律、存在量词消去律、存在量词引入律、全称否定律和存在否定 律。 定理2 7 替换定理( m f m 的替换定理) 设ahb ，而f ( p ) 是m f m 的任一合式公 式，则总有f ( a ) hf ( b ) 。 定理2 8m f m 中下列定理成立： 1 h v u a v - 1 a 2 a v ah u a 3 一( a a b ) h a v b 4 一( a v b ) h a 八一b 5 一ah a 南京航空航犬人学硕十学何论文 6 一bh a v b 7 uah u - 1a ：8 u ( a b ) h ( a 八ub ) v ( ua 八b ) v ( ua 八“b ) 9 u ( a v b ) h ( ua ub ) v ( ua 一b ) v ( - 1 a 八ub ) 1 0 u ( 八b a c ) h ( ua 八b 八c ) v ( a 八ub 八c ) v ( a b 八uc ) v ( ua a b a c ) v ( a ub 八uc ) v ( ua 八b 八pc ) v ( ua pb 八uc ) nl “( a v b v c ) h ( ua 八一b 八一c ) v ( 一a 八ug a c ) v ( 一a 一b 八“c ) v ( u a 八ub c ) v ( 一a 八ub 八“c ) v ( ua 八一b 八“c ) v ( ua ub 八pc ) 1 2 pa vubh “( a 八b ) vu ( a v b ) 1 3 pa 八ubh u ( a a b ) 八p ( a v b ) 定理2 9m f m 中下列定理成立： 1 v x a ( x ) h j x a ( x ) 2 3 x h ( x ) h v x a ( x ) 3 一v x a ( x ) hj x a ( x ) 4 一3 x a ( x ) hv x a ( x ) 5 v x a ( x ) 八v x b ( x ) hv x a ( x ) 八b ( x ) 6 3 x h ( x ) v 3 x g ( x ) h x a ( x ) v b ( x ) 7 v x a ( x ) v v x b ( x ) b v x a ( x ) v b ( x ) 8 3 x a ( x ) 八b ( x ) 卜j x a ( x ) 八3 x b ( x ) 9 l j 3 x a ( x ) hv x ua ( x ) v a ( x ) 八3 x ”a ( x ) 1 0 v x 一a ( x ) vua ( x ) h j x a ( x ) v u3 x h ( x ) 2 4 中介逻辑系统m 的可靠性与完备性 下面的定理说明了中介逻辑系统m r 的语形系统和语义系统的关系： 定理2 i o ( m f 。的可靠性定理) 中介逻辑谓词演算系统m f 。是可靠的，即，设a 是 m 的公式，如果r 卜a ，则r a 。 定理2 1 l ( m f 的完备性定理)设a 是m p 中的公式，如果r a ，则r 卜a 。 2 5m p 。与其它多值逻辑系统的关系 下图表明了m 矿与其它多值逻辑系统的关系，它表明m p 是与历史上已有的逻辑 系统是不害价的m 。 j _ 不完全f 毒息数据库的逻辑系统研究 m p + = m p “= l + 图2 1m 矿和其它三值逻辑系统的关系 2 6 小结 本章讨论了中介系统，并着重介绍了中介逻辑系统m 和m 一，给出了这两个系 统的主要定理和其可靠性与完备性。这部分是本文研究工作的基础，后文将对在这 两个逻辑系统上做更深入的研究。 南京航空航犬人学硕十学能论文 第三章中介命题演算系统m p m 的等值完全析取范式 本f 茸讨论中介命题演算系统m p m 的规范化问题。内容安排如下：第一部分介 绍构造等值完全杌取范式的基本思想，同时也提供了通过真值表构造等值完全析取 范式的方法。第二部分介绍等值完全析取范式的定义及其性质。第三部分证明了等 值完全析取范式的存在性和唯一性，并给出个求等值完全析取范式的例子。最后 是总结。 3 1 基本思想 这部分介绍构造等值完全范式的基本思想且以构造析取范式为例，对于等值完 全合取范式可类似得到。本文不再赘述。 表3 1 定义了几个一元联结词q 、y 、( 肛是m p m 固有的，这里列出便 于讨论) ，这几个一元联结i t n 由m p 的基本联结词“表示。 表3 ，l联结词的定义 定理3 1 q ，p ，y ，；八，v 是m p m 的一个命题联结词组。 证明：已知卜，p ；八，v 是m p m 的一个命题联结词组“，下面的三个公式可以 由真值表得出： oph 1 9 p yph p a 一, p php a g php h 邺 php a - - p a “p 所以， 一，“：八，v q ，y ，；八，v 又一ph op v p 所以 ，p ；八。v o ，p ，y ，；八，v 故： 一， ，v = a ，p ，y ，；八，v 即 a ，斗y ，：八，v 也是m p m 的联结词组。口 注：上述联结词并不是独立的，但这样便于实际应用。 设a 是m p m 的合式公式，包含三个原子命题p 、q 、r ，表3 ，2 是a 的真值表， 其中，第1 列是a 的真值。 依据上述联结词，可以写出和a 等值的析取范式： 丁不完全信息数据阼的逻辑系统研究 时j 二第一、第二行，a 取真值，构造yp 八oq 八g r 、yp 八yq qr 分别与之 z 、rj 、t 。 对卜第三行，a 取中值构造op ayq a r 与之对应。 将l 述三式析取得：a = ( gp a 。q 八g r ) v ( yp ayq 八qr)v(a f ) 八yq 八r ) 表3 2a 的真值表 这种方法的正确性，出真值表易知。 对于上式的第一、二项，它们和a 取真值的项分别对应，称之为真值项。类似 地，称第三项为中值项。这样构造的关于a 的范式，正是本文讨论的等值完全析取 范式。下文将给出它们的具体定义。 这里要提到的是，若公式a 的真值表中有这样一行：其p 、q 、r 的取值都不是 u ，而a 的值为u 。则无法用上述的联结词组找到对应项。幸运的是，在m p ”中任 何合式公式的真值表不会出现这样的情况，这正是m p ”所不能表达的“，即，a 不 是m p ”的合式公式。实际上这正符合m p m 的直观解释：在信息完全的情况下，总 可以做出一个或真或假的判断，而不是未知u 。 3 2 等值完全析取范式的定义及性质 定义3 1 设a 是m p m 的合式公式，有r 1 个不同的命题词p l ，p 2 ，n 。且将 其按照某一固定的顺序排列( 本文约定其原子命题总是按照某一固定的顺序的) r = 全p j 称为真值项，如果p j = ap ，或扯p ，或gp ， r = np j 称为中值项，如果p j ：np 或yp ，或p 。 定义3 2 设a 是m p m 的合式公式，有n 个不同的命题词n ，p 2 ，p 。r = - p ： 为真值项或中值项，则( r ) 定义为这样一个1 3 位数，其个位与p 对应，十位与p 。 对应，以此类推，每一位的值由如下方法得出： 堂窒壁羔笪盔叁：! i ! 堡主堂丝堡茎 蔷该位对应的，的彤式楚up ，则该位为0 ； 若该位对应的p 。的形式是斗p ，或p 。，则该位为1 ： 符咳位对应的n 的形式足yp ，则浚位记为2 ； 如：对fyp a oq a r ，a ( y p a c i q a r ) = 2 0 1 。 以f 的结论是显然的： 引理3 1 设r 和q 同为真值项或同为中值项，则a ( r ) = ( q ) 当且仅当r 和q 相同。 引理3 2 设r 和q 是真值或中值项，若( r ) = a ( q ) 且r q ，则在r 、q 中， 其中之一必是真值项，另一个必是中值项。 引理3 3 设月，9 分别为合式公式a 的真值项和中值项，若a ( r ，) = a ( 幺) ， 则兄，vg 目r ，。 定义3 3 ( 等值完全析取范式) m p m 中含有n 个不同的原子命题n ，p ：，以 的合式公式a 称为m p m 在等值意义下的完全析取范式，如果下列条件成立： ( 1 ) a 5 ( 苫r ，) v ( 芒g ) 其中： 只，和q 。分别是关于a 的n 个原子命题的真值项