An approach to a systematic theorem proving procedure in first-order logic

A complexity degree for theorems in first-order logic is introduced which naturally reflects the difficulty of proving them. Relative to that degree it is required that a systematic proof procedure should prove simple theorems faster than harder ones. Such a systematic but relatively inefficient procedure and a semisystematic but efficient procedure are presented. Both are developed on the basis of the consistency and completeness theorem for the underlying formal system rather than Herbrand's theorem.     

Tableau-based characterization and theorem proving for default logic

In this paper, we present a new method for computing extensions and for deriving formulae from a default theory. It is based on the semantic tableaux method and works for default theories with a finite set of defaults that are formulated over a decidable subset of first-order logic. We prove that all extensions (if any) of a default theory can be produced by constructing the semantic tableau ofone formula built from the general laws and the default consequences. This result allows us to describe an algorithm that provides extensions if there are any, and to decide if there are none. Moreover, the method gives a necessary and sufficient criterion for the existence of extensions of default theories with finitely many defaults provided they are formulated on a decidable subset of FOL.This work was completed while the author was at CNRS, Marseille.     

Automated Theorem Proving in Temporal Logic:T-Resolution

This paper presentes a novel resolution method,T-resolution,based on the first order temporal logic.The primary claim of this method is its soundness and completeness.For this purpose,we construct the corresponding semantic trees and extend Herbrand‘s Theorem.     

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.     

A case study in automated theorem proving: Finding sages in combinatory logic

We present in this article an application of automated theorem proving to a study of a theorem in combinatory logic. The theorem states: the strong fixed point property is satisfied in a system that contains the B and W combinators. The theorem can be stated in terms of Smullyan's forests of birds: a sage exists in a forest that contains a bluebird and a warbler. Proofs of the theorem construct sages from B and W. Prior to the study, one sage, discovered by Statman, was known to exist. During the study, with much assistance from two automated theorem-proving programs, four new sages were discovered. The study was conducted from a syntactic point of view because the authors know very little about combinatory logic. The uses of the automated theorem-proving programs are described in detail.This work was supported by the Applied Mathematical Sciences subprogram of the office of Energy Research, U.S. Department of Energy, under contract W-31-109-Eng-38.     

An approach for lifetime reliability analysis using theorem proving

Recently proposed formal reliability analysis techniques have overcome the inaccuracies of traditional simulation based techniques but can only handle problems involving discrete random variables. In this paper, we extend the capabilities of existing theorem proving based reliability analysis by formalizing several important statistical properties of continuous random variables like the second moment and the variance. We also formalize commonly used concepts about the reliability theory such as survival, hazard, cumulative hazard and fractile functions. With these extensions, it is now possible to formally reason about important measures of reliability (the probabilities of failure, the failure risks and the mean-time-to failure) associated with the life of a system that operates in an uncertain and harsh environment and is usually continuous in nature. We illustrate the modeling and verification process with the help of examples involving the reliability analysis of essential electronic and electrical system components.     

Vectorization of a generalized procedure for theorem proving inpropositional logic on vector computers

Vectorization techniques for solving the theorem-proving problem in propositional logic on vector computers is presented. To take advantage of vector processing, the rules used in the deduction process are first generalized by considering more than one literal at a time. The soundness of the generalized rules is proved. The vectorized representation of the problem and algorithms based on the generalized rules is proposed. Experiments conducted on vector computers show that the vectorized procedure is effective     

Theorem proving for intensional logic

For a number of tasks in knowledge representation, and particularly in natural language semantics, it is useful to be able to treat propositions and properties as objects — as items that can appear as arguments of predicates, as things one can quantify over, and so on. Logics that support such intensional operations are notoriously hard to work with. The current paper presents a theorem prover for one such logic, namely, Turner's property theory.     

A generalized Euclidean algorithm for geometry theorem proving

In the first part of this paper, we present an algorithm that computes an unmixed-dimensional decomposition of a varietyV. EachV _i in the decompositionV=V ₁U...UV _m is given by a finite set of polynomials which represents the generic points of the irreducible components ofV _i . The basic operation in our algorithm is the computation of greatest common divisors of univariate polynomials over extension fields given by regular chains. No factorization is needed. In the second part, this algorithm is applied to geometry theorem proving. We show that it can be used for deciding whether geometry statements are generically true or whether they are true under given nondegeneracy conditions. If a geometry statement is generically true, the simplest nondegeneracy condition with respect to a lexicographical degree ordering can be constructed by means of our algorithm.This work was supported by the Austrian Fonds zur Förderung der wissenschaftlichen Forschung, project no. P6763, the Austrian Ministry of Science, project ESPRIT BRA 3125 MEDLAR, and the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C-0027.     

Bounded-overhead caching for definite-clause theorem proving

In this paper we describe the design of an effective caching mechanism for resource-limited, definite-clause theorem-proving systems. Previous work in adapting caches for theorem proving relies on the use of unlimited-size caches. We show how unlimited-size caches are unsuitable in application contexts where resource-limited theorem provers are used to solve multiple problems from a single problem distribution. We introduce bounded-overhead caches, that is, those caches that contain at most a fixed number of entries and entail a fixed amount of overhead per lookup, and we examine cache design issues for bounded-overhead caches. Finally, we present an empirical evaluation of bounded-overhead cache performance, relying on a specially designed experimental methodology that separates hardware-dependent, implementation-dependent, and domain-dependent effects.     

Automated theorem proving in mathematics

TheMuscadet theorem prover is a knowledge-based system able to prove theorems in some non-trivial mathematical domains. The knowledge bases contain some general deduction strategies based onnatural deduction, mathematical knowledge and metaknowledge. Metarules build new rules, easily usable by the inference engine, from formal definitions. Mathematical knowledge may be general or specific to some particular field.Muscadet proved many theorems in set theory, mappings, relations, topology, geometry, and topological linear spaces. Some of the theorems were rather difficult.Muscadet is now intended to become an assistant for mathematicians in discrete geometry for cellular automata. In order to evaluate the difficulty of such a work, researchers were observed while proving some lemmas, andMuscadet was tested on easy ones. New methods have to be added to the knowledge base, such as reasoning by induction, but also new heuristics for splitting and reasoning by cases. It is also necessary to find good representations for some mathematical objects.     

Analytic resolution in theorem proving

Analytic resolution is a proof procedure for predicate calculus based on the ideas of semantic trees and analytic tableaux. It is related to the unit preference with set-of-support strategy, and incorporates some features of model elimination. The philosophy is to expect and compensate for “blind alleys” by a stack discipline. This eliminates pollution of the search space by a bad choice of the next step in a proof. Experimental results included compare favourably with others from the literature.     

Completely non-clausal theorem proving

The proof procedure we describe operates on quantifier-free formulas of the predicate calculus which are not truth-functionally normalized in any way. The procedure involves a single inference rule called NC-resolution, and is shown to be complete. Completeness is also obtained for a simple restriction on the rule's application.Examples are given using NC-resolution to derive a logic program from its specification, and to ‘execute’ a program specification in its original form.     

Elimination procedures for mechanical theorem proving in geometry

In this paper, methods for the algebraic decision problem of mechanical theorem proving in elementary geometry are described on the basis of some elimination procedures for polynomial systems. The methods can determine whether or not a geometric theorem is generically true and whether it is true or false for each of the components including degenerate ones, with projection and irreducible decomposition. Theorems which have been proved using an implementation of the methods in Maple include the Simson Theorem, Butterfly Theorem, Secant Theorem, Feuerbach Theorem, Steiner Theorem, Steiner-Lehmus Theorem, Morely Theorem and Thébault-Taylor Theorem, of which some are taken as illustrative examples in the paper.     

Lazy techniques for fully expansive theorem proving

The HOL system is afully expansive theorem prover: proofs generated in the system are composed of applications of the primitive inference rules of the underlying logic. One can have a high degree of confidence that such systems are sound, but they are far slower than theorem provers that exploit metatheoretic or derived properties.This paper presents techniques for postponing part of the computation so that the user of a fully expansive theorem prover can be more productive. The notions oflazy theorem andlazy conversion are introduced. These not only allow part of the computation to be delayed, but also permit nonlocal optimizations that are only possible because the primitive inferences are not performed immediately. The approach also opens the way to proof procedures that exploit metatheoretic properties without sacrificing security; the primitive inferences still have to be performed in order to generate a theorem, but during the proof development the user is free of the overheads they entail.     

Mechanical theorem proving in projective geometry

We present an algorithm that is able to confirm projective incidence statements by carrying out calculations in the ring of all formal determinants (brackets) of a configuration. We will describe an implementation of this prover and present a series of examples treated by the prover, includingPappus' andDesargues' theorems, thesixteen point theorem, Saam's theorem, thebundle condition, theuniqueness of a harmonic point andPascal's theorem.     

Automatic theorem proving in set theory

This paper describes a program which proves theorems in set theory by the use of heuristics. The use of methods which are analogous to human methods is its main characteristics. By splitting, a different theorem is first brokes into more easily proud parts. The heuristics for the following steps, which are the resuse of observation and imitation of the mathematics' methods, emphasize the use of many selections methods and the choice of suitable representations. In particular, a graph is constructed to represent binary relations. The program has been used to prove about 150 theorems in more and axiomatic set theory, sampling with functions, orderings, congruence relations and ordinal numbers.