一种新的基于扩展规则的定理证明算法

基于扩展规则的定理证明方法是一种与归结方法互补的新的定理证明方法,首先通过对扩展规则的深入研究,给出了扩展规则的一个重要性质,设计并实现了该性质的判定算法.此外,从理论上分析及证明了该判定算法的时问和空间复杂性.基于此,提出了一种新的基于扩展规则的定理证明算法NER,将判定子句集可满足性问题转化为一系列文字集合的包含问题,而非计数问题.实验结果表明,算法NER的执行效率较原有扩展规则算法IER和基于归结的有向归结算法DR有明显提高,有些问题可以提高两个数量级.     

A mechanical solution of Schubert's Steamroller by many-sorted resolution

We demonstrate the advantage of using a many-sorted resolution calculus by a mechanical solution of a challenge problem. This problem known as ‘Schubert's Steamroller’ had been unsolved by automated theorem provers before. Our solution clearly demonstrates the power of a many-sorted resolution calculus. The proposed method is applicable to all resolution-based inference systems.     

Eliminating duplication with the hyper-linking strategy

The efficiency of almost all theorem proving methods suffers from a phenomenon called duplication of instances of clauses. In this paper, we present a novel technique, called the hyper-linking strategy, to eliminate such duplication. This strategy is complete for the full first-order predicate calculus. We show the effectiveness of this strategy by comparing it with other proving methods. We give empirical evidence that both the Davis-Putnam procedure and the hyper-linking strategy are comparable to each other and better than other common theorem proving strategies on propositional calculus problems. The fact that the Davis-Putnam procedure is faster than resolution and other common methods on propositional problems seems not to be appreciated by a large segment of the theorem proving community. Also, we give empirical evidence that the hyper-linking strategy is better than other common theorem proving methods on near-propositional problems like logic puzzles. We attempt to explain the superior behavior of the hyper-linking strategy and the Davis-Putnam procedure by examining the kinds of duplication that can occur during the search with the different methods. In addition, we show the completeness of the hyper-linking strategy combined with several support strategies.This research was partially supported by NSF under grant CCR-8802282.     

Resolution theorem proving in reified modal logics

This paper is concerned with the application of the resolution theorem proving method to reified logics. The logical systems treated include the branching temporal logics and logics of belief based on K and its extensions. Two important problems concerning the application of the resolution rule to reified systems are identified. The first is the redundancy in the representation of truth functional relationships and the second is the axiomatic reasoning about modal structure. Both cause an unnecessary expansion in the search space. We present solutions to both problems which allow the axioms defining the reified logic to be eliminated from the database during theorem proving hence reducing the search space while retaining completeness. We describe three theorem proving methods which embody our solutions and support our analysis with empirical results.Much of the research reported in this paper was supported by DTI IED SERC grant No. GR/F 35968, and was carried out whilst Han Reichgelt was at the University of Nottingham.     

A pragmatic approach to resolution-based theorem proving

Resolution theory offers a simple, complete method for proving theorems but is generally considered impractical. The theorems we are interested in proving arise in the analysis of programs and usually involve quantification. We have developed a system for proving these theorems using resolution, but have embedded in it a simplifier as the central component. The simplifier is an integrated collection of algorithms for normalizing arithmetic, relational, and logical expressions. The knowledge in the simplifier is encoded in procedures, rather than as axioms or rules. We use the simplifier to prove certain theorems, reduce the clutter in theorems, and reduce the cost of unification, Inherent in the normal form algorithms is the notion of strengthening (e.g., inferringa =b froma b ANDb a). We have incorporated the notion into the unification algorithm as well. The design of the system permits its use along a spectrum from pure resolution to resolution with interpretation of the arithmetic and relational operators. Strengthening is a heuristic that permits the movement along this spectrum. We call the approachi-resolution.i-resolution does not preserve completeness; it does define a means for approaching completeness efficiently and systematically. It thus attempts to provide a pragmatic approach to mechanical theorem proving.     

On the Modelling of Search in Theorem Proving- Towards a Theory of Strategy Analysis

We present a model for representing search in theorem proving. This model captures the notion ofcontraction, which has been central in some of the recent developments in theorem proving. We outline an approach to measuring the complexity of search which can be applied to analyze and evaluate the behaviour of theorem-proving strategies. Using our framework, we compare contraction-based strategies of different contraction power and show how they affect the evolution of the respective search spaces during the derivation.     

基于广义归结的定理机器证明系统

本文使用Ｃ—ＰＲＯＬＯＧ语言在ＳＵＮ工作站上设计实现了基于广义归结和基于归结的两个定理机器证明系统ＧＲＭ,ＲＭ,证明了《数学原理》中Ｐａｒｔ１：ｍａｔｈｅｍａｔｉｃａｌｌｏｇｉｃ中ＳｅｃｔｉｏｎＡ与ＳｅｃｔｉｏｎＢ中全部定理（３５０个）．讨论ＧＲＭ和ＲＭ的时、空复杂性,并在实现设计中提出新的全局调度策略及归结式的化简、排序策略,以单子句恒真、恒假的判断代替了广义归结中的自归结,实现了带ＯＣＣＵＲ检查的模式匹配．     

半扩展规则下分解的定理证明方法

基于扩展规则的定理证明方法在一定意义上是与归结原理对偶的方法,通过子句集能否推导出所有极大项来判定可满足性.IER(improved extension rule)算法是不完备的算法,在判定子句集子空间不可满足时,并不能判定子句集的满足性,算法还需重新调用ER(extension rule)算法,降低了算法的求解效率.通过对子句集的极大项空间的研究,给出了子句集的极大项空间分解后子空间的求解方法.通过对扩展规则的研究,给出了极大项部分空间可满足性判定方法PSER(partial semi-extension rule).在IER算法判定子空间不可满足时,可以调用PSER算法判定子空间对应的补空间的可满足性,从而得到子句集的可满足性,避免了不能判定极大项子空间可满足性时需重新调用ER算法的缺点,使得IER算法更完备.在此基础上,还提出DPSER(degree partial semi-extension rule)定理证明方法.实验结果表明:所提出的DPSER和IPSER的执行效率较基于归结的有向归结算法DR、IER及NER算法有明显的提高.     

On the resolution-based family of abstract argumentation semantics and its grounded instance

This paper introduces a novel parametric family of semantics for abstract argumentation called resolution-based and analyzes in particular the resolution-based version of the traditional grounded semantics, showing that it features the unique property of satisfying a set of general desirable properties recently introduced in the literature. Additionally, an investigation of its computational complexity properties reveals that resolution-based grounded semantics is satisfactory also from this perspective.     

Theorem Proving Modulo

Deduction modulo is a way to remove computational arguments from proofs by reasoning modulo a congruence on propositions. Such a technique, issued from automated theorem proving, is of general interest because it permits one to separate computations and deductions in a clean way. The first contribution of this paper is to define a sequent calculus modulo that gives a proof-theoretic account of the combination of computations and deductions. The congruence on propositions is handled through rewrite rules and equational axioms. Rewrite rules apply to terms but also directly to atomic propositions. The second contribution is to give a complete proof search method, called extended narrowing and resolution (ENAR), for theorem proving modulo such congruences. The completeness of this method is proved with respect to provability in sequent calculus modulo. An important application is that higher-order logic can be presented as a theory in deduction modulo. Applying the ENAR method to this presentation of higher-order logic subsumes full higher-order resolution. This revised version was published online in August 2006 with corrections to the Cover Date.     

机械化定理证明研究综述

随着现代社会计算机化程度的提高,与计算机相关的各种系统故障足以造成巨大的经济损失.机械化定理证明能够建立更为严格的正确性,从而奠定系统的高可信性.针对机械化定理证明的逻辑基础和关键技术,详细剖析了一阶逻辑和基于消解的证明技术、自然演绎和类型化的λ演算、3种编程逻辑、基于高阶逻辑的硬件验证技术、程序构造和求精技术之间的联系和发展变迁,其中,3种编程逻辑包括一阶编程逻辑及变体、Floyd-Hoare逻辑和可计算函数逻辑.然后分析、比较了各类主流证明助手的设计特点,阐述了几个具有代表性的证明助手的开发和实现.接下来对它们在数学、编译器验证、操作系统微内核验证、电路设计验证等领域的应用成果进行了细致的分析.最后,对机械化定理证明进行了总结,并提出面临的挑战和未来研究方向.     

基于MCN和MO启发式策略的扩展规则知识编译方法

在基于扩展规则的知识编译算法的基础上提出了2种启发式策略:MCN策略和MO策略.MCN策略和MO策略利用子句集的信息分别选择相应子句和变量,减少扩展规则的使用次数,进而降低知识编译后目标子句集的规模.在此基础上,设计并实现了MCN_KCER,MO_KCER和MCN_MO_KCER算法.实验结果表明:2种启发式策略都可以大幅度减小编译后的子句集规模,同时使用它们的效果更为明显,经过编译后得到的子句集规模是原算法的1/3～1/39,从而大幅度提高之后的在线推理阶段的效率.     

Representations of the language recognition problem for a theorem prover

Two representations of the language recognition problem for a theorem prover in first-order logic are presented and contrasted. One of the representations is based on the familiar method of generating sentential forms of the language, and the other is based on the Cocke parsing algorithm. An augmented theorem prover is described which permits recognition of recursive languages. The state-transformation method developed by Cordell Green to construct problem solutions in resolution-based systems can be used to obtain the parse tree. In particular, the end-order traversal of the parse tree is derived in one of the representations. The paper defines an inference system, termed the cycle inference system, which makes it possible for the theorem prover to model the method on which the representation is based. The general applicability of the cycle inference system to state-space problems is discussed. Given an unsatisfiable setS, where each clause has at most one positive literal, it is shown that there exists an input proof. The clauses for the two representations satisfy these conditions, as do many state-space problems.This work was supported by the National Aeronautics and Space Administration Grant NGR-21-002-270.     

T-Theorem Proving I

In this paper we present a theoretical basis justifying the incorporation of decidability results for a first-order theory T into an automated theorem prover for T. We state rules which extend resolution using decidability results relative to T in both the ground and the non-ground case, and prove the correctness and completeness of these rules. This is done by considering the ground case of such theories first, and then by applying a straightforward lifting argument. Examples are given illustrating the inference speed-ups which can be obtained by considering decision procedures with resolution-based inference.     

On the calculus of positively constructed formulas for automated theorem proving

The paper deals with an expressive logic language LF and its calculus. Formulas of this language consist of some large-scale structural elements, such as type quantifiers. The language LF contains only two logic symbols—∀ and ∃, which form the set of logic connectives of the language. The logic calculus JF and complete strategy for automated proof search based on a single unary rule of inference are considered. This calculus has a number of other features which lead to the reduction of the combinatorial complexity of finding the deductions in comparison to the known systems for automated theorem proving as the Resolution method and Genzen calculus. Problems of effective implementation of JF as a program system for automated theorem proving are considered.     

Theorem proving in technology transfer: the user’s point of view

The aim of this paper is to discuss the potentials, problems and critical factors for the industrial usage of mechanized theorem proving. The approach followed in this paper is somehow unusual. The starting point is the results of an industrial project whose goal was the assessment of the state of the art of provers (and of tools supporting formal methods in general). We describe the project results in terms of evaluation criteria, classification of technologies and tools and critical factors for industrial take-up. We present the results of the assessment in the same spirit, the same kind of analysis and even the same terminology which were used in the presentations and in the deliverables of the project. This should result in a presentation of a “different view” of the problem of technology transfer in theorem proving, that we call the “user’s point of view”. In this way, we hope to give a new perspective in the discussion of the industrial take-up of the theorem proving technology.     

An average case analysis of a resolution principle algorithm in mechanical theorem proving

The satisfiability problem is a well known NP-complete problem. In artificial intelligence, solving the satisfiability problem is called mechanical theorem proving. One of those mechanical theorem proving methods is the resolution principle which was invented by J.R. Robinson. In this paper, we shall show how an algorithm based upon the resolution principle can be analyzed. Letn andr ₀ denote the numbers of variables and input clauses respectively. LetP ₀ denote the probability that a variable appears positively, or negatively, in a clause. Our analysis shows that the expected total number of clauses processed by our algorithm isO(n+r ₀) ifP ₀ is a constant,r ₀ is polynomially related withn, andn is large.This research was supported partially by the National Science Council of the Republic of China under the Grant NSC 78-0408-E007-06.     

Mothers of Pipelines

We present a method for pipeline verification using SMT solvers. It is based on a non-deterministic “mother pipeline” machine (MOP) that abstracts the instruction set architecture (ISA). The MOP vs. ISA correctness theorem splits naturally into a large number of simple subgoals. This theorem reduces proving the correctness of a given pipelined implementation of the ISA to verifying that each of its transitions can be modeled as a sequence of MOP state transitions.