谓词公式输入的定理证明

子句格式是广泛采用的定理证明的一种输入格式,然而,人们从抽象实际问题中得到的却常常是谓词公式。因此使用谓词公式直接输入来做定理证明是相当有意义的。作者于1984年2月以LISP语言的形式在PDP11/03微机上实现了这种输入格式的定理     

量化带标公式的消解

首先引入量化带标公式,然后研究了量化带标公式的消解并且证明其健全性和拒绝完备性.另外,还引入了二元消解并证明其针对正规量化带标公式(一个量化带标公式的子集)是健全的和拒绝完备的.最后证明如果正规量化带标公式的每一个子句如果最多包含两个文字,则该公式的可满足性问题是易解的.     

一种基于超连接的一阶逻辑反演推理算法

研究一种一阶谓词逻辑公式的反演求证算法,它是应用超连接过程来处理子句集的消解的,该算法具有比Ｒｏｂｉｎｓｏｎ的传统消解方法更高的效率,以一个实例讨论了该算法的应用,结果表明此算法可以保证在预定义的相关边界内,对任意一阶逻辑的推理具有终止性。     

一种基于超连接的一阶逻辑反演推理算法

研究一种一阶谓词逻辑公式的反演求证算法,它是应用超连接过程来处理子句集的消解的,该算法具有比Ｒｏｂｉｎｓｏｎ的传统消解方法更高的效率．以一个实例讨论了该算法的应用,结果表明此算法可以保证在预定义的相关边界内,对任意一阶逻辑的推理具有终止性     

不可满足公式的完备证明系统

合取范式(CNF)公式H到F的同态是一个从H的文字集合到F的文字集合的映射、并保持补运算和子句映到子句。同态映射保持一个公式的不可满足性。一个公式是极小不可满足的是指公式不可满足而且从中删去任一个子句后得到的公式可满足。MU(1)是子句数与变元数的差等于1的极小不可满足公式类。S．Szeider证明了：每个不可满足公式F是MU(1)中某个公式日的同态像。从而，基于MU(1)的同态证明系统与树消解证明系统是p-等价的。MU(1)中的公式可以用基础矩阵表示，本文用基础矩阵的方法证了同态证明系统ПMU（1）的完备性。     

Horn集上的HOI消解与HOL消解

OI消解法对一般子句集是不完备的,甚至对基子句集都不完备,多年来,人们在寻求提高消解效率方面作了许多努力,诸如改进消解策略、限制不可满足的子句集等。Renschen与Wos提出了一类子句集,称Horn集,许多机器证明问题都可归结为     

负超有序消解原理

Robinson在1965年提出消解原理后,定理机械证明的研究工作取得了重大进展。但消解原理过于一般化,在消解过程中产生了许多不相干的多余子句。为了提高消解效率,继又提出了各种消解策略,其中语义消解原理是研究得较多的消解策略。在语义消解中,为了减少消解过程中多余子句的生成,主要采取三项措施:(1)利用(任意)     

图元的子句时新性

为了给出消息子句的测试关系,选择主体角色进程演算为π演算的一个子集,以该子集刻画并发密码协议系统,事件图为其指称语义模型,由图元的前缀、非确定选择和并发合成运算得到,对于图元及其组合运算来说,图元的子句时新性质确定了主体角色消息语句的子句测试关系,且出现在图元中的消息事件满足通信关系和前驱关系约束.由图元生成的事件图涵盖了由子句测试关系构造的未知主体角色串,且通过定义图元互模拟刻画事件图的互模拟等价关系可实现并发密码协议系统安全性验证.     

MARG-MU(2)的结构和复杂度

SAT问题(可满足性问题)是理论计算机科学的核心问题,研究SAT问题的方法很多,利用极小不可满足公式的性质来研究SAT问题是近几年兴起的一个热点研究方向.本文主要利用(1,*)-消解方法研究了差为2的边缘极小不可满足公式集(MARG-MU(2))的结构和复杂度:在结构方面,MARG-MU(2)中的公式要么是F22,要么是某一文字在其中仅出现一次的公式;在复杂度方面,如果MARG-MU(2)对(1,*)-消解封闭,则某个含有n个变元和n+2个子句的公式是否为MARG-MU(2)中的公式的问题可以在时间0(n3)内被判定.     

关于单元证明的几个结果

本文讨论了基本子句集合有单元(线性-单元、输入-单元、输入-正的单元)反驳的条件,证明了子句的文字不超过两个的不可满足的Horn集有输入-单元反驳.     

NT-HIT(k)公式的存在性

一个合取范式(CNF)公式F是NT-HIT公式,如果F中的任意两个不同的子句中恰有一对互补文字。NT-HIT(k)是公式的子句数与变元数之差为k的NT-HIT公式类。通过构造一个命题公式Hn,m,我们证明了：(1)Hn,m可满足当且仅当存在一个含有n个变元和m个子句的NT-HIT公式。(2)对于NT-HIT(1)中的任意一个公式F,存在一个文字L,L在F中仅出现一次。进一步,我们证明了：对于k≥2,公式Hn,n k是一个不可满足公式。于是,对于k≥2,NT-HIT(k)是一个空集。从而就解决了[1]中的两个公开的问题。     

SQL语句中UNION子句的使用

本文通过两个常见查询的产生来介绍如何利用VisualFoxPRO的SQL语句中UNION子句产生复杂查询．     

一次性求解多个SAT问题

在实际应用中通常需要求解对应CNF(Conjunctive Normal Form)公式之间仅相差几个子句的一系列SAT(Satisfiability Problem)问题,但目前绝大多数SAT求解算法都是针对单一SAT问题设计的。为此,基于DPLL提出了nDPLL算法,并在随机问题上对该算法的效率进行测试。实验结果表明,nDPLL算法能一次性求解多个SAT问题,对于特定范围的CNF公式集具有较高的效率,CNF公式集的规模越大、相近因子越高、子句数和变量数的比值越大,则nDPLL算法的效率越高。     

关于Henschen和Wos推测的证明

Ｈｅｎｓｃｈｅｎ和 Ｗｏｓ在［２］中的定理 １和定理 ２分别证明了不可满足的 Ｈｏｒｎ集有严 格－正的－单元反驳和严格－输入反驳，如果子句（ｃｌａｕｓｅ）集合Ｓ是一个Ｒ－不可满足的 Ｈｏｒｎ集，该集合包含子句Ｒｘ，ｘ和它的函数反身公理，当Ω由调换（ｐａｒａｍｏｄｕｌａｔｉｏｎ）、 归结（ｒｅｓｏｌｕｔｉｏｎ）和因子（ｆａｃｔｏｒｉｎｇ） 三个推理规律组成时，Ｈｅｎｓｃｈｅｎ 和 Ｗｏｓ在［２］中的 定理 ３证明了：利用这三个推理规律从该子句集可以得到一个输入反驳（ｉｎｐｕｔ ｒｅｔｕｔａｔｉｏｎ） Ｄ１和一个单元反驳（ｕｎｉｔ ｒｅｆｕｆａｔｉｏｎ）Ｄ２，而且他们认为如 Ω’由调换和归结两个规律 组成时，利用这二个规律从上述子句集合有可能得到一个严格－正的－单元反驳和一个 严格－输入反驳，本文证明了这一估计是对的。     

利用正交方法解SAT问题

提出了一种解决SAT问题的新算法.该算法首先定义了子句之间的正交关系;然后从消除子句之间的交叠信息出发,利用正交子句的特性,结合有效的简化技术,逐渐将问题简化为一组与原问题完全等价的正交子句组;最后,根据正交子句组对整个赋值空间的覆盖情况来判断SAT是否满足.该算法为SAT问题的解决提供了一个新的思路.     

量化单一带标公式的消解

在引入量化单一带标公式的概念后,给出其消解算法,并证明该消解算法是健全的和拒绝性完备的。因此该算法可用于对量化单一带标公式进行理论上的研究,同时也可用于在实际应用中解决这类公式的可满足性问题。最后,根据消解算法,得出一个可以在多项式时间内判定可满足性的量化单一带标公式的子类。     

关于随机MAX k-SAT模型的上界研究

对于包含n个变量和m=αn个长度为k的子句的CNF公式,人们比较关注公式中最大可满足子句的个数max Fk(MAX k-SAT).当子句密度α比较大时,随机MAX k-SAT模型中的变量f k(n,αn)E(max Fk)的上界可以用一阶矩方法给出.通过对一阶矩方法放缩精度的改进,得到了它的一个更紧的上界(1-1/2 k)αn+h(α,t)·αn.同时,可以证明这个新的上界随着t的增大而变得更紧.     

基于Thiele连分式逼近的四阶迭代公式

基于Thiele连分式逼近,建立了一个求解非线性方程的迭代公式.在一定条件下,证明了该迭代公式收敛阶数至少为四阶.实例证明该迭代格式是有效的且优于Newton迭代格式.     

判断基本子句集合不可满足性的一个方法

一个子句(或基本子句集合)的非模型是不满足该子句(或基本子句集合)的解释.本文给出计算有限基本子句集合的非模型个数的一种方法,并使用概率的观点从理论上加以证明.     

制约逻辑, 消解原理及其应用

本文首先简要介绍了制约逻辑，然后提出制约逻辑的子句类型和消解方法，并对简称为ＬＥＬＡＩＬ的实验系统（我们自己在这个原理的基础上开发的问题求解软件系统）及其求解实例进行了讨论。