一种子句重构的增强Tableau算法

利用非循环定义的概念可展开的特性,提出一个基于子句重构的增强Tableau算法.采用最简洁的概念合取子句代替原来的子概念集对完整树/图上的结点进行标记,并设计一组推理规则以构建这样的完整树/图,从而消除传统Tableau算法中的∩-规则、∪-规则所带来的概念描述重复.因而在非循环定义概念可满足性判定问题上,空间性能有明显提高.此外,虽然文中只提供针对SI语言的规则和证明,可是这种处理思路同样适用于其它描述逻辑语言,因而具有一定的推广价值.     

一个在Horn子句中求解极大缩减的算法

在信念修正理论中,一个核心问题是求解一个公式集合关于事实集合的所有极大协调子集,即极大缩减.本文尝试从算法的角度来解决这一问题,研究在Horn子句中求解所有极大缩减的算法.首先,本文指出并证明了公式集合和事实集合并集的极小不协调子集与公式集合关于事实集合的极大缩减之间的转化关系.其次,给出并证明了Horn子句集合极小不协调的一个必要条件.然后,基于上述两个结论,本文提出了一个在Horn子句中枚举公式集合和事实集合并集的极小不协调子集的交互式算法和一个通过这些极小不协调子集计算所有极大缩减的算法.最后,综合这两个算法,提出了一个在Horn子句中求解所有极大缩减的交互式算法.     

An algorithm to compute maximal contractions for Horn clauses

In the theory of belief revision, the computation of all maximal subsets (maximal contractions) of a formula set with respect to a set of facts is one of the key problems. In this paper, we try to solve this problem by studying the algorithm to compute all maximal contractions for Horn clauses. First, we point out and prove the conversion relationship between minimal inconsistent subsets of union of the formula set and the set of facts and maximal contractions of the formula set with respect to th...     

C语言中嵌套选择语句的逻辑关系浅析

本文介绍了如何用分析嵌套选择语句的逻辑关系，主要方法是借助分裂图画出N-S图，最后再根据IF…ELSE…语句配对原理分析出各子句的关系。     

命题逻辑提升到一阶逻辑上的子句消去方法

在基于命题逻辑的可满足性问题（SAT）求解器和基于一阶逻辑的定理证明器上，子句集简化一直是必不可少的步骤，而其中子句消去方法在这些子句集简化方法中是非常重要的组成部分。将命题逻辑中的子句消去方法归结隐藏恒真消去方法（RHTE）和归结隐藏包含消去方法（RHSE）提升到一阶逻辑上，并且利用蕴含模归结原则（IMR）证明了这种提升方式在一阶逻辑上具有可靠性（Soundness），即依据这两种子句消去方法删除一阶逻辑公式集中的子句，并不会改变公式集的可满足性或者不可满足性。此外，将这两个方法与一阶逻辑子句消去方法锁子句消去方法（BCE）和归结包含消去方法（RSE）进行组合推广，发展得到一阶逻辑上新型子句消去方法（BC+RHS）E、（RS+RHT）E和（RHS+RHT）E，并且证明了这3种子句消去方法在一阶逻辑上的可靠性。最后，分析比较了这些子句消去方法的有效性，并且证明了这3种新型子句消去方法比组成它们的原始子句消去方法均具有更高的有效性。     

一种新的SAT问题预处理算法

提出了一项新的正向推理技术:对称扩展的一元子句推导(Symmetric Extended Unit Propagation)。与传统的一元子句推导技术相比,文中的方法通过在一元子句推导过程中添加对称的蕴涵关系从而能够推导出更多的一元子句。基于这项新技术实现了一个可满足性问题(SAT)预处理器Snowball。实验结果验证了该项技术的有效性,表明该预处理器Snowball能够有效地化简SAT问题的规模并减少解决SAT问题的时间。     

On the Complexities of Non-Horn Clause Logic Programming

There have been active work to extend th Prology styl Horn Clause logic programming to non-Hron clauses.In this paper,we will analyze the complexities of several such extensions.The purpose is to understand the computational complexity of these inference systems.The analyses do not prove that any one system is better than the others all the time.But they o suggest that one system may be better than the others for some particular problems.We also discuss the effect of caching.     

逻辑推理理论的定量发展

本文在一阶谓词逻辑的基础上,为每个定性的Horn子句规则赋予一个蕴涵强度f,从而得到定量的f-Horn子句规则及其Herbrand解释.最后,我们成功地给出了f-Horn子句规则的模糊过程解释,并由此引入了模糊逻辑程序系统.     

基于变量混合特征的分支启发式策略

先进的SAT求解器能够通过有效的分支启发式策略解决大型应用实例.目前VSIDS策略是最具有代表性的基于冲突分析的分支策略,它因其稳健性而被广泛使用,但在每次冲突分析中其判定变量活性的增量方式过于单一.针对此问题,本文提出了一种基于变量混合特征的分支启发式算法,目的是充分地利用参与冲突分析的变量所携带的不同信息特征来区分变量,来进一步指导变量活性增长.并将所提出的分支策略算法嵌入到Glucose4.1中形成求解器Glucose4.1+MFBS,通过对比测试,实验结果表明改进的分支算法比原本的VSIDS策略,具有一定的优势,求解明显个数增加.     

基于扩展Petri网的软件服务模型设计方法

为了提高复杂软件服务系统的构建效率,文章提出了一种基于扩展Petri网的软件服务模型设计方法。首先,该方法将注册的软件服务转换成Horn子句,并将用户需求转换为Horn子句的事实和目标,接着通过逻辑推理来构建完整的软件服务流程,将得出的Horn子句映射至扩展Petri网上,构建出满足用户需求的抽象服务集,最后通过案例验证了该方法的可行性。