Higher-Order Logic (HOL) is a proof development system intended for applications to both hardware and software. It is principally used in two ways: for directly proving theorems, and as theorem-proving support for application-specific verification systems. HOL is currently being applied to a wide variety of problems, including the specification and verification of critical systems. Introduction to HOL provides a coherent and self-contained description of HOL containing both a tutorial introduction and most of the material that is needed (...) for day-to-day work with the system. After a quick overview that gives a "hands-on feel" for the way HOL is used, there follows a detailed description of the ML language. The logic that HOL supports and how this logic is embedded in ML, are then described in detail. This is followed by an explanation of the theorem-proving infrastructure provided by HOL. Finally two appendices contain a subset of the reference manual, and an overview of the HOL library, including an example of an actual library documentation. (shrink)

This books presents the refereed proceedings of the Fifth International Workshop on Analytic Tableaux and Related Methods, TABLEAUX '96, held in Terrasini near Palermo, Italy, in May 1996. The 18 full revised papers included together with two invited papers present state-of-the-art results in this dynamic area of research. Besides more traditional aspects of tableaux reasoning, the collection also contains several papers dealing with other approaches to automated reasoning. The spectrum of logics dealt with covers several nonclassical logics, including modal, intuitionistic, (...) many-valued, temporal and linear logic. (shrink)

This book contains an introduction to symbolic logic and a thorough discussion of mechanical theorem proving and its applications. The book consists of three major parts. Chapters 2 and 3 constitute an introduction to symbolic logic. Chapters 4–9 introduce several techniques in mechanical theorem proving, and Chapters 10 an 11 show how theorem proving can be applied to various areas such as question answering, problem solving, program analysis, and program synthesis.

Checking the equivalence of two Boolean functions, or combinational circuits modeled as Boolean functions, is often desired when reliable and correct hardware components are required. The most common approaches to equivalence checking are based on simulation and model checking, which are constrained due to the popular memory and state explosion problems. Furthermore, such tools are often not user-friendly, thereby making it tedious to check the equivalence of large formulas or circuits. An alternative is to use mathematical tools, called interactive (...) class='Hi'>theorem provers, to prove the equivalence of two circuits; however, this requires human effort and expertise to write multiple output functions and carry out interactive proof of their equivalence. In this paper, we define two simple, one formal and the other informal, gate-level hardware description languages, design and develop a formal automatic combinational circuit equivalence checker tool, and test and evaluate our tool. The tool CoCEC is based on human-assisted theorem prover Coq, yet it checks the equivalence of circuit descriptions purely automatically through a human-friendly user interface. It either returns a machine-readable proof of circuits’ equivalence or a counterexample of their inequality. The interface enables users to enter or load two circuit descriptions written in an easy and natural style. It automatically proves, in few seconds, the equivalence of circuits with as many as 45 variables. CoCEC has a mathematical foundation, and it is reliable, quick, and easy to use. The tool is intended to be used by digital logic circuit designers, logicians, students, and faculty during the digital logic design course. (shrink)

By operations on models we show how to relate completeness with respect to permissivenominal models to completeness with respect to nominal models with finite support. Models with finite support are a special case of permissive-nominal models, so the construction hinges on generating from an instance of the latter, some instance of the former in which sufficiently many inequalities are preserved between elements. We do this using an infinite generalisation of nominal atoms-abstraction. The results are of interest in their own right, (...) but also, we factor the mathematics so as to maximise the chances that it could be used off-the-shelf for other nominal reasoning systems too. Models with infinite support can be easier to work with, so it is useful to have a semi-automatic theorem to transfer results from classes of infinitely-supported nominal models to the more restricted class of models with finite support. In conclusion, we consider different permissive-nominal syntaxes and nominal models and discuss how they relate to the results proved here. (shrink)

In this paper we present an approach to automated learning within mathematical reasoning systems. In particular, the approach enables proof planning systems to automatically learn new proof methods from well-chosen examples of proofs which use a similar reasoning pattern to prove related theorems. Our approach consists of an abstract representation for methods and a machine learning technique which can learn methods using this representation formalism. We present an implementation of the approach within the ΩMEGA proof planning system, which we call (...) LEARNΩMATIC. We also present the results of the experiments that we ran on this implementation in order to evaluate if and how it improves the power of proof planning systems. (shrink)

The automatic verification of large parts of mathematics has been an aim of many mathematicians from Leibniz to Hilbert. While Gödel's first incompleteness theorem showed that no computer program could automatically prove certain true theorems in mathematics, the advent of electronic computers and sophisticated software means in practice there are many quite effective systems for automated reasoning that can be used for checking mathematical proofs. This book describes the use of a computer program to check the proofs of (...) several celebrated theorems in metamathematics including those of Gödel and Church-Rosser. The computer verification using the Boyer-Moore theorem prover yields precise and rigorous proofs of these difficult theorems. It also demonstrates the range and power of automated proof checking technology. The mechanization of metamathematics itself has important implications for automated reasoning, because metatheorems can be applied as labor-saving devices to simplify proof construction. (shrink)

Reflecting Alan Robinson's fundamental contribution to computational logic, this book brings together seminal papers in inference, equality theories, and logic programming. It is an exceptional collection that ranges from surveys of major areas to new results in more specialized topics. Alan Robinson is currently the University Professor at Syracuse University. Jean-Louis Lassez is a Research Scientist at the IBM Thomas J. Watson Research Center. Gordon Plotkin is Professor of Computer Science at the University of Edinburgh. Contents: Inference. Subsumption, A Sometimes (...) Undervalued Procedure, Larry Wos, Ross Overbeek, and Ewing Lusk. The Markgraf Karl Refutation Procedure, Hans Jurgen Ohlbach and Jorg H. Siekmann. Modal Logic Should Say More than it Does, Melvin Fitting. Interactive Proof Presentation, W. W. Bledsoe. Intelligent Backtracking Revisited, Maurice Bruynooghe. A Science of Reasoning, Alan Bundy. Inductive Inference of Theories from Facts, Ehud Y. Shapiro. Equality. Solving Equations in Abstract Algebras: A Rule-based Survey of Unification, Jean-Pierre Jouannaud and Claude Kirchner. Disunification: A Survey, Hubert Comon. A Case Study of the Completion Procedure: Proving Ring Commutativity Problems, Deepak Kapur and Hantao Zhang. Computations in Regular Rewriting Systems I and II, Girard Huet and JeanJacques Levy. Unification and ML Type Reconstruction, Paris Kanellakis, Harry Mairson, and John Mitchell. Automatic Dimensional Analysis, Mitchell Wand. Logic Programming. Logic Programming Schemes and Their Implementations, Keith Clark. A Near-Horn Prolog for Compilation, Donald Loveland and David Reed. Unfold/Fold Transformations of Logic Programs, P. A. Gardner and J. C. Shepherdson. An Algebraic Representation of Logic Program Computations, Andrea Corradini and Ugo Montanari. Theory of Disjunctive Logic Programs, Jack Minker, Arcot Rajasekar, and Jorge Lobo. Bottom-Up Evaluation of Logic Programs, Jeffrey Naughton and Raghu Ramakrishnan. Absys, the First Logic Programming Language: A View of the Inevitability of Logic Programming, E. W. Elcock. (shrink)

The refereed proceedings of the 19th International Conference on Automated Deduction, CADE 2003, held in Miami Beach, FL, USA in July 2003. The 29 revised full papers and 7 system description papers presented together with an invited paper and 3 abstracts of invited talks were carefully reviewed and selected from 83 submissions. All current aspects of automated deduction are discussed, ranging from theoretical and methodological issues to the presentation of new theorem provers and systems.

In a fluent, clear, and lively style this translation by two of Maslov's junior colleagues brings the work of the late Soviet scientist S. Yu. Maslov to a wider audience. Maslov was considered by his peers to be a man of genius who was making fundamental contributions in the fields of automatic theorem proving and computational logic. He published little, and those few papers were regarded as notoriously difficult. This book, however, was written for a broad audience (...) of readers and describes elegant examples of applications in such fields as computer science, artificial intelligence, operations research, economic modeling, and biological modeling, among others. The book also brings to light the work by the American mathematician E. L. Post, which inspired Maslov's own work in the development of a general theory and which has been long neglected by mathematicial logicians and systems theorists in the United States. The book's first chapter introduces the Rules of the Game. Part I, Mathematics of Calculi, covers E. L. Post's canonical systems, deductive systems and algorithms, and probabilistic calculi and deductive information. Part II, Horizonal Modeling, takes up a "toy" economy, the calculi of technological possibilities, and the development of rules. Part III, Vertical Modeling, deals with the topics of "to fight and to search" and the consequences of the asymmetry of cognitive mechanisms. Vladimir Lifschitz is affiliated with the Department of Computer Science at Stanford University, and Michael Gelfond with the Department of Electrical Engineering and Computer Science at the University of Texas, El Paso. Theory of Deductive Systems and Its Applicationsis included in the Foundation of Computing Series, edited by Michael Garey. (shrink)

This book constitutes the refereed proceedings of the 5th Kurt Gödel Colloquium on Computational Logic and Proof Theory, KGC '97, held in Vienna, Austria, in August 1997. The volume presents 20 revised full papers selected from 38 submitted papers. Also included are seven invited contributions by leading experts in the area. The book documents interdisciplinary work done in the area of computer science and mathematical logics by combining research on provability, analysis of proofs, proof search, and complexity.

A survey of works on automatic theorem-proving in the ussr 1964-1970. the philosophical problems are not touched.

This book constitutes the refereed proceedings of the 13th International Conference on Automated Deduction, CADE-13, held in July/August 1996 in New Brunswick, NJ, USA, as part of FLoC '96. The volume presents 46 revised regular papers selected from a total of 114 submissions in this category; also included are 15 selected system descriptions and abstracts of two invited talks. The CADE conferences are the major forum for the presentation of new results in all aspects of automated deduction. Therefore, the volume (...) is a timely report on the state-of-the-art in the area. (shrink)

In this paper, we introduce Speedith which is an interactive diagrammatic theorem prover for the well-known language of spider diagrams. Speedith provides a way to input spider diagrams, transform them via the diagrammatic inference rules, and prove diagrammatic theorems. Speedith’s inference rules are sound and complete, extending previous research by including all the classical logic connectives. In addition to being a stand-alone proof system, Speedith is also designed as a program that plugs into existing general purpose theorem provers. (...) This allows for other systems to access diagrammatic reasoning via Speedith, as well as a formal verification of diagrammatic proof steps within standard sentential proof assistants. We describe the general structure of Speedith, the diagrammatic language, the automatic mechanism that draws the diagrams when inference rules are applied on them, and how formal diagrammatic proofs are constructed. (shrink)

The book contains the proceedings of the 12th European Testis Workshop and gives an excellent overview of the state of the art in testicular research. The chapters are written by leading scientists in the field of male reproduction, who were selceted on the basis of their specific area of research. The book covers all important aspects of testicular functioning, for example, Sertoli and Leydig cell functioning, spermatogonial development and transplantation, meiosis and spermiogenesis. Even for those investigators who were not present (...) at the workshop, this volume provides a clear impression of the topics discussed during that meeting. (shrink)

We present an axiomatic approach for a class of finite, extensive form games of perfect information that makes use of notions like “rationality at a node” and “knowledge at a node.” We distinguish between the game theorist's and the players' own “theory of the game.” The latter is a theory that is sufficient for each player to infer a certain sequence of moves, whereas the former is intended as a justification of such a sequence of moves. While in general the (...) game theorist's theory of the game is not and need not be axiomatized, the players' theory must be an axiomatic one, since we model players as analogous to automatic theorem provers that play the game by inferring (or computing) a sequence of moves. We provide the players with an axiomatic theory sufficient to infer a solution for the game (in our case, the backwards induction equilibrium), and prove its consistency. We then inquire what happens when the theory of the game is augmented with information that a move outside the inferred solution has occurred. We show that a theory that is sufficient for the players to infer a solution and still remains consistent in the face of deviations must be modular. By this we mean that players have distributed knowledge of it. Finally, we show that whenever the theory of the game is group-knowledge (or common knowledge) among the players (i.e., it is the same at each node), a deviation from the solution gives rise to inconsistencies and therefore forces a revision of the theory at later nodes. On the contrary, whenever a theory of the game is modular, a deviation from equilibrium play does not induce a revision of the theory. (shrink)

The vision of machines autonomously carrying out substantive conjecture generation, theorem discovery, proof discovery, and proof verification in mathematics and the natural sciences has a long history that reaches back before the development of automatic systems designed for such processes. While there has been considerable progress in proof verification in the formal sciences, for instance the Mizar project’ and the four-color theorem, now machine verified, there has been scant such work carried out in the realm of the (...) natural sciences—until recently. The delay in the case of the natural sciences can be attributed to both a lack of formal analysis of the so-called “theories” in such sciences, and the lack of sufficient progress in automated theorem proving. While the lack of analysis is probably due to an inclination toward informality and empiricism on the part of nearly all of the relevant scientists, the lack of progress is to be expected, given the computational hardness of automated theorem proving; after all, theoremhood in even first-order logic is Turing-undecidable. We give in the present short paper a compressed report on our building upon these formal theories using logic-based AI in order to achieve, in relativity, both machine proof discovery and proof verification, for theorems previously established by humans. Our report is intended to serve as a springboard to machine-produced results in the future that have not been obtained by humans. (shrink)

This volume is written jointly by Witold Marciszewski, who contributed the introductory and the three subsequent chapters, and Roman Murawski who is the author of the next ones - those concerned with the 19th century and the modern inquiries into formalization, algebraization and mechanization of reasonings. Besides the authors there are other persons, as well as institutions, to whom the book owes its coming into being. The study which resulted in this volume was carried out in the Historical Section of (...) the research project _Logical Systems and Algorithms for Automatic Testing of Reasoning,_ 1986-1990, in which participated nine Polish universities; the project was coordinated by the Department of Logic, Methodology and Philosophy of Science of the Bia??l??ystok Branch of the University of Warsaw, and supported by the Ministry of Education 1987). The major part of the project was focussed on the software for computer-aided theorem proving called Mizar MSE ) due to Dr. Andrzej Trybulec. He and other colleagues deserve a grateful mention for a hands-on experience and theoretical stimulants owed to their collaboration. (shrink)

In the theory of programming languages, type inference is the process of inferring the type of an expression automatically, often making use of information from the context in which the expression appears. Such mechanisms turn out to be extremely useful in the practice of interactive theorem proving, whereby users interact with a computational proof assistant to constructformal axiomatic derivations of mathematical theorems. This article explains some of the mechanisms for type inference used by the "Mathematical Components" project, which (...) is working towards a verification of the Feit-Thompson theorem. (shrink)

The position of Polish informatics, as well in research as in didactic, has its roots in achievements of Polish mathematicians of Warsaw School and logicians of Lvov-Warsaw School. Jan Lukasiewicz is considered in the world of computer science as the most famous Polish logician. The parenthesis-free notation, invented by him, is known as PN (Polish Notation) and RPN (Reverse Polish Notation). Lukasiewicz created many-valued logic as a separate subject. The idea of multi-valueness is applied to hardware design (many-valued or fuzzy (...) switching, analog computer). Many-valued approach to vague notions and commonsense reasoning is the method of expert systems, databases and knowledge-based systems. Stanis3aw Jaokowski's system of natural deduction is the base of systems of automatic deduction and theorem proving. He created a system of paraconsistent logic. Such logics are used in AI. Kazimierz Ajdukiewicz with his categorial grammar participated in the development of formal grammars, the field significant for programming languages. Andrzej Grzegorczyk had an important contribution to the development of the theory of recursiveness. (shrink)

Computer assisted theorem proving is an increasingly important part of mathematical methodology, as well as a long-standing topic in artificial intelligence (AI) research. However, the current generation of theorem proving software have limited functioning in terms of providing new proofs. Importantly, they are not able to discriminate interesting theorems and proofs from trivial ones. In order for computers to develop further in theorem proving, there would need to be a radical change in how the (...) software functions. Recently, machine learning results in solving mathematical tasks have shown early promise that deep artificial neural networks could learn symbolic mathematical processing. In this paper, I analyze the theoretical prospects of such neural networks in proving mathematical theorems. In particular, I focus on the question how such AI systems could be incorporated in practice to theorem proving and what consequences that could have. In the most optimistic scenario, this includes the possibility of autonomous automated theorem provers (AATP). Here I discuss whether such AI systems could, or should, become accepted as active agents in mathematical communities. (shrink)

Accessing knowledge of a single knowledge source with different client applications often requires the help of mediator systems as middleware components. In the domain of theorem proving large efforts have been made to formalize knowledge for mathematics and verification issues, and to structure it in databases. But these databases are either specialized for a single client, or if the knowledge is stored in a general database, the services this database can provide are usually limited and hard to adjust (...) for a particular theorem prover. Only recently there have been initiatives to flexibly connect existing theorem proving systems into networked environments that contain large knowledge bases. An intermediate layer containing both, search and proving functionality can be used to mediate between the two. In this paper we motivate the need and discuss the requirements for mediators between mathematical knowledge bases and theorem proving systems. We also present an attempt at a concurrent mediator between a knowledge base and a proof planning system. (shrink)

\ is a 7000 line Prolog parser/theorem-prover for logical categorial grammar. In such logical categorial grammar syntax is universal and grammar is reduced to logic: an expression is grammatical if and only if an associated logical statement is a theorem of a fixed calculus. Since the syntactic component is invariant, being the logic of the calculus, logical categorial grammar is purely lexicalist and a particular language model is defined by just a lexical dictionary. The foundational logic of continuity (...) was established by Lambek while a corresponding extension including also logic of discontinuity was established by Morrill and Valentín :167–192, 2010). \ implements a logic including as primitive connectives the continuous and discontinuous connectives of the displacement calculus, additives, 1st order quantifiers, normal modalities, bracket modalities, and universal and existential subexponentials. In this paper we review the rules of inference for these primitive connectives and their linguistic applications, and we survey the principles of Andreoli’s focusing, and of a generalisation of van Benthem’s count-invariance, on the basis of which \ is implemented. (shrink)

ABSTRACT We are concerned with the theorem proving in annotated logics. By using annotated polynomials to express knowledge, we develop an inference rule superposition. A proof procedure is thus presented, and an improvement named M- strategy is mainly described. This proof procedure uses single overlaps instead of multiple overlaps, and above all, both the proof procedure and M-strategy are refutationally complete.

Formal verification involves the use of logical and computational methods to establish claims that are expressed in precise mathematical terms. These can include ordinary mathematical theorems, as well as claims that pieces of hardware or software, network protocols, and mechanical and hybrid systems meet their specifications. In practice, there is not a sharp distinction between verifying a piece of mathematics and verifying the correctness of a system: formal verification requires describing hardware and software systems in mathematical terms, at which point (...) establishing claims as to their correctness becomes a form of theorem proving. Conversely, the proof of a mathematical theorem may require a lengthy computation, in which case verifying the truth of the theorem requires verifying that the computation does what it is supposed to do. The gold standard for supporting a mathematical claim is to provide a proof, and twentieth-century developments in logic show most if not all conventional proof methods can be reduced to a small set of axioms and rules in any of a number of foundational systems. With this reduction, there are two ways that a computer can help establish a claim: it can help find a proof in the first place, and it can help verify that a purported proof is correct. Automated theorem proving focuses on the “finding” aspect. Resolution theorem provers, tableau theorem provers, fast satisfiability solvers, and so on provide means of establishing the validity of formulas in propositional and first-order logic. Other systems provide search procedures and decision procedures for specific languages and domains, such as linear or nonlinear expressions over the integers or the real numbers. Architectures like SMT combine domain-general search methods with domain-specific procedures. Computer algebra systems and specialized mathematical software packages provide means of carrying out mathematical computations, establishing mathematical bounds, or finding mathematical objects. A calculation can be viewed as a proof as well, and these systems, too, help establish mathematical claims. Automated reasoning systems strive for power and efficiency, often at the expense of guaranteed soundness. Such systems can have bugs, and it can be difficult to ensure that the results they deliver are correct. In contrast, interactive theorem proving focuses on the “verification” aspect of theorem proving, requiring that every claim is supported by a proof in a suitable axiomatic foundation. This sets a very high standard: every rule of inference and every step of a calculation has to be justified by appealing to prior definitions and theorems, all the way down to basic axioms and rules. In fact, most such systems provide fully elaborated “proof objects” that can be communicated to other systems and checked independently. Constructing such proofs typically requires much more input and interaction from users, but it allows us to obtain deeper and more complex proofs. The Lean Theorem Prover aims to bridge the gap between interactive and automated theorem proving, by situating automated tools and methods in a framework that supports user interaction and the construction of fully specified axiomatic proofs. The goal is to support both mathematical reasoning and reasoning about complex systems, and to verify claims in both domains. (shrink)

Uniform proofs systems have recently been proposed [Mi191j as a proof-theoretic foundation and generalization of logic programming. In [Mom92a] an extension with constructive negation is presented preserving the nature of abstract logic programming language. Here we adapt this approach to provide a complete theorem proving technique for minimal, intuitionistic and classical logic, which is totally goal-oriented and does not require any form of ancestry resolution. The key idea is to use the Godel-Gentzen translation to embed those logics in (...) the syntax of Hereditary Harrop formulae, for which uniform proofs are complete. We discuss some preliminary implementation issues. (shrink)

In this paper we focus on theorem proving for conditional logics. First, we give a detailed description of CondLean, a theorem prover for some standard conditional logics. CondLean is a SICStus Prolog implementation of some labeled sequent calculi for conditional logics recently introduced. It is inspired to the so called “lean” methodology, even if it does not fit this style in a rigorous manner. CondLean also comprises a graphical interface written in Java. Furthermore, we introduce a goal-directed (...) proof search mechanism, derived from the above mentioned sequent calculi based on the notion of uniform proofs. Finally, we describe GOALDUCK, a simple SICStus Prolog implementation of the goal-directed calculus mentioned here above. Both the programs CondLean and GOALDUCK, together with their source code, are available for free download at. (shrink)