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)

In this paper we present a new hierarchy of analytical tableaux systems TNDC n, 1≤n<ω, for da Costa's hierarchy of propositional paraconsistent logics Cn, 1≤n<ω. In our tableaux formulation, we introduce da Costa's “ball” operator “o”, the generalized operators “k” and “(k)”, for 1≤k, and the negations “~k”, for k≥1, as primitive operators, differently to what has been done in the literature, where these operators are usually defined operators. We prove a version of Cut Rule for the TNDC (...) n, 1≤n<ω, and also prove that these systems are logically equivalent to the corresponding systems Cn, 1≤n<ω. The systems TNDC n constitute completely automated theorem proving systems for the systems of da Costa's hierarchy Cn, 1≤n<ω. (shrink)

The method of analytic tableaux is employed in many introductory texts and has also been used quite extensively as a basis for automated theorem proving. In this paper, we discuss the complexity of the system as a method for refuting contradictory sets of clauses, and resolve several open questions. We discuss the three forms of analytic tableaux: clausal tableaux, generalized clausal tableaux, and binary tableaux. We resolve the relative complexity of these (...) three forms of tableaux proofs and also resolve the relative complexity of analytic tableaux versus resolution. We show that there is a quasi-polynomial simulation of tree resolution by analytic tableaux; this simulation is close to optimal, since we give a matching lower bound that is tight to within a polynomial. (shrink)

We show that Smullyan's analytic tableaux cannot p-simulate the truth-tables. We identify the cause of this computational breakdown and relate it to an underlying semantic difficulty which is common to the whole tradition originating in Gentzen's sequent calculus, namely the dissonance between cut-free proofs and the Principle of Bivalence. Finally we discuss some ways in which this principle can be built into a tableau-like method without affecting its analytic nature.

In this dissertation we present proof systems for several modal logics. These proof systems are based on analytic (or semantic) tableaux. -/- Modal logics are logics for reasoning about possibility, knowledge, beliefs, preferences, and other modalities. Their semantics are almost always based on Saul Kripke’s possible world semantics. In Kripke semantics, models are represented by relational structures or, equivalently, labeled graphs. Syntactic formulas that express statements about knowledge and other modalities are evaluated in terms of such models. -/- (...) This dissertation focuses on modal logics with dynamic operators for public announcements, belief revision, preference upgrades, and so on. These operators are defined in terms of mathematical operations on Kripke models. Thus, for example, a belief revision operator in the syntax would correspond to a belief revision operation on models. -/- The ‘dynamic’ semantics of dynamic modal logics are a clever way of extending languages without compromising on intuitiveness. We present ‘dynamic’ tableau proof systems for these dynamic semantics, with the express aim to make them conceptually simple, easy to use, modular, and extensible. This we do by reflecting the semantics as closely as possible in the components of our tableau system. For instance, dynamic operations on Kripke models have counterpart dynamic relations between tableaux. -/- Soundness, completeness, and decidability are three of the most important properties that a proof system may have. A proof system is sound if and only if any formula for which a proof exists, is true in every model. A proof system is complete if and only if for any formula that is true in all models, a proof exists. A proof system is decidable if and only if any formula can be proved to be a theorem or not a theorem in a finite number of steps. All proof systems in this dissertation are sound, complete, and decidable. -/- Part of our strategy to create modular tableau systems is to delay concerns over decidability until after soundness and completeness have been established. Decidability is attained through the operations of folding and through operations on ‘tableau cascades’, which are graphs of tableaux. -/- Finally, we provide a proof-of-concept implementation of our dynamic tableau system for public announcement logic in the Clojure programming language. (shrink)

Recent years have been blessed with an abundance of logical systems, arising from a multitude of applications. A logic can be characterised in many different ways. Traditionally, a logic is presented via the following three components: 1. an intuitive non-formal motivation, perhaps tie it in to some application area 2. a semantical interpretation 3. a proof theoretical formulation. There are several types of proof theoretical methodologies, Hilbert style, Gentzen style, goal directed style, labelled deductive system style, and so on. The (...) tableau methodology, invented in the 1950s by Beth and Hintikka and later per fected by Smullyan and Fitting, is today one of the most popular, since it appears to bring together the proof-theoretical and the semantical approaches to the pre of a logical system and is also very intuitive. In many universities it is sentation the style first taught to students. Recently interest in tableaux has become more widespread and a community crystallised around the subject. An annual tableaux conference is being held and proceedings are published. The present volume is a Handbook a/Tableaux pre senting to the community a wide coverage of tableaux systems for a variety of logics. It is written by active members of the community and brings the reader up to frontline research. It will be of interest to any formal logician from any area. (shrink)

In this paper we give an analytic tableau calculus P L 1 6 for a functionally complete extension of Shramko and Wansing’s logic. The calculus is based on signed formulas and a single set of tableau rules is involved in axiomatising each of the four entailment relations ⊧ t, ⊧ f, ⊧ i, and ⊧ under consideration—the differences only residing in initial assignments of signs to formulas. Proving that two sets of formulas are in one of the first (...) three entailment relations will in general require developing four tableaux, while proving that they are in the ⊧ relation may require six. (shrink)

In this paper we present a new hierarchy of analytical tableaux systems TNDC n, 1≤ntableaux formulation, we introduce da Costa's ?ball? operator ?o?, the generalized operators ?k? and ?(k)?, for 1≤k, and the negations ?~k?, for k≥1, as primitive operators, differently to what has been done in the literature, where these operators are usually defined operators. We prove a version of Cut Rule for the TNDC (...) n, 1≤ntheorem proving systems for the systems of da Costa's hierarchy Cn, 1≤nshrink)

A Prolog implementation of a new theorem-prover for first-order classical logic is described. The prover is based on the calculus KE and the rules used for analysing quantifiers in free variable semantic tableaux. A formal specification of the rules used in the implementation is described, for which soundness and completeness is straightforwardly verified. The prover has been tested on the first 47 problems of the Pelletier set, and its performance compared with a state of the art semantic (...) class='Hi'>tableaux theorem-prover. It has also been applied to model building in a prototype system for logical animation, a technique for symbolic execution which can be used for validation. The interest of these experiments is that they demonstrate the value of certain “characteristics” of the KE calculus, such as the significant space-saving in theorem-proving, the mutual inconsistency of open branches in KE trees, and the relation of the KE rules to “traditional” forms of reasoning. (shrink)

The history of building automated theorem provers for higher-order logic is almost as old as the field of deduction systems itself. The first successful attempts to mechanize and implement higher-order logic were those of Huet [13] and Jensen and Pietrzykowski [17]. They combine the resolution principle for higher-order logic (first studied in [1]) with higher-order unification. The unification problem in typed λ-calculi is much more complex than that for first-order terms, since it has to take the theory of αβη-equality (...) into account. As a consequence, the higher-order unification problem is undecidable and sets of solutions need not even always have most general elements that represent them. Thus the mentioned calculi for higher-order logic have take special measures to circumvent the problems posed by the theoretical complexity of higher-order unification. In this paper, we will exemplify the methods and proof- and model-theoretic tools needed for extending first-order automated theorem proving to higherorder logic. For the sake of simplicity take the tableau method as a basis (for a general introduction to first-order tableaux see part I.1) and discuss the higherorder tableau calculi HT and HTE first presented in [19]. The methods in this paper also apply to higher-order resolution calculi [1, 13, 6] or the higher-order matings method of Peter [3], which extend their first-order counterparts in much the same way. Since higher-order calculi cannot be complete for the standard semantics by Gödel’s incompleteness theorem [11], only the weaker notion of Henkin models [12] leads to a meaningful notion of completeness in higher-order logic. It turns out that the calculi in [1, 13, 3, 19] are not Henkin-complete, since they fail to capture the extensionality principles of higher-order logic. We will characterize the deductive power of our calculus HT (which is roughly equivalent to these calculi) by the semantics of functional Σ-models. To arrive at a calculus that is complete with respect to Henkin models, we build on ideas from [6] and augment HT with tableau construction rules that use the extensionality principles in a goal-oriented way.. (shrink)

The aim of the paper is to prove tha analytic completeness theorem for a logic LAs with two integral operators in the singular case. The case of absolute continuity was proved in [4]. MSC: 03B48, 03C70.

Hoover [2] proved a completeness theorem for the logic L[MATHEMATICAL SCRIPT CAPITAL A]. The aim of this paper is to prove a similar completeness theorem with respect to product measurable biprobability models for a logic Lmath image with two integral operators. We prove: If T is a ∑1 definable theory on [MATHEMATICAL SCRIPT CAPITAL A] and consistent with the axioms of Lmath image, then there is an analytic absolutely continuous biprobability model in which every sentence in T (...) is satified. (shrink)

The question that is the subject of this article is not intended to be a sociological or statistical question about the practice of today’s mathematicians, but a philosophical question about the nature of mathematics, and specifically the method of mathematics. Since antiquity, saying that mathematics is problem solving has been an expression of the view that the method of mathematics is the analytic method, while saying that mathematics is theorem proving has been an expression of the view (...) that the method of mathematics is the axiomatic method. In this article it is argued that these two views of the mathematical method are really opposed. In order to answer the question whether mathematics is problem solving or theorem proving, the article retraces the Greek origins of the question and Hilbert’s answer. Then it argues that, by Gödel’s incompleteness results and other reasons, only the view that mathematics is problem solving is tenable. (shrink)

We prove the following version of Hechler's classical theorem: For each partially ordered set (Q, ≤) with the property that every countable subset of Q has a strict upper bound in Q, there is a ccc forcing notion such that in the generic extension for each tall analytic P-ideal J (coded in the ground model) a cofinal subset of (J, ⊆*) is order isomorphic to (Q, ≤).

Free-variable semantic tableaux are a well-established technique for first-order theorem proving where free variables act as a meta-linguistic device for tracking the eigenvariables used during proof search. We present the theoretical foundations to extend this technique to propositional modal logics, including non-trivial rigorous proofs of soundness and completeness, and also present various techniques that improve the efficiency of the basic naive method for such tableaux.

Let us recall that Raphael Robinson's Arithmetic Q is an axiom system that differs from Peano Arithmetic essentially by containing no Induction axioms [13], [18]. We will generalize the semantic-tableaux version of the Second Incompleteness Theorem almost to the level of System Q. We will prove that there exists a single rather long Π 1 sentence, valid in the standard model of the Natural Numbers and denoted as V, such that if α is any finite consistent extension of (...) Q + V then α will be unable to prove its Semantic Tableaux consistency. The same result will also apply to axiom systems α with infinite cardinality when these infinite-sized axiom systems satisfy a minor additional constraint, called the Conventional Encoding Property. Our formalism will also imply that the semantic-tableaux version of the Second Incompleteness Theorem generalizes for the axiom system IΣ 0 , as well as for all its natural extensions. (This answers an open question raised twenty years ago by Paris and Wilkie [15].). (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Reviewed by:The Logic Pamphlets of Charles Lutwidge Dodgson and Related PiecesIrving H. AnellisFrancine F. Abeles, editor. The Logic Pamphlets of Charles Lutwidge Dodgson and Related Pieces. The Pamphlets of Lewis Carroll, 4. New York-Charlottesville-London: Lewis Carroll Society of North America-University Press of Virginia, 2010. Pp. xx + 271. Cloth, $75.00.Until William Bartley’s rediscovery and reconstruction of Dodgson’s lost Part II of Symbolic Logic, Lewis Carroll’s reputation in logic, when (...) taken seriously, rested upon his few published articles on logical paradoxes and puzzles, while his published books, The Game of Logic and Symbolic Logic, were regarded as suitable perhaps as pedagogical tools, but dismissed otherwise as amusements, on a par with the Alice works. Richard Braithwaite asserted (“Lewis Carroll as Logician”) that “Carroll regarded formal and symbolic logic not as a corpus of systematic knowledge about valid thought nor yet as an art for teaching a person to think correctly.” He suggested that Dodgson used his pseudonym for his popular and whimsical writings, reserving his legal name only for his serious mathematical products. Philosophers practicing linguistic analysis in their assault on nonsense deriving from misuse of language meanwhile developed an interest in Carroll (e.g. George Pitcher, “Wittgenstein, Nonsense, and Lewis Carroll”). Abeles, on the contrary, stresses the seriousness of Dodgson’s pedagogical and popularizing mission (195–99).Bartley’s discovery opened the door for reevaluating Dodgson as a serious logician, and Abeles has been in the forefront of that reevaluation. Her general introduction and introductions to the main divisions of this collection of Carroll’s publications (and additional material from his Nachlass and a handful of publications of others, composed in response to Carroll’s published articles) place his serious logical work and its significance in historical perspective, providing a deeper, more sophisticated view than found in Bartley’s “Editor’s Introduction” to Lewis Carroll’s Symbolic Logic. Abeles also offers brief introductions to the individual entries, which describe their physical characteristics and circumstances of composition.Dodgson aligned with the majority of those British logicians of his day, starting with George Boole, who understood formal logic to be Aristotelian syllogistic, and symbolic logic to be syllogistic logic expressed algebraically. His notational innovation was employing indices to terms so that, independently of the arrangement of terms, propositions could easily be read; thus, “xy0” can be read as “no x are y” or “no y are x” and “x1y0” as “all x are not y” or “no x are y”. In dealing with the classical elimination problem in the class calculus—to determine the maximum information, without duplications, obtainable from a given set of premises—Dodgson in his later work and unpublished letters anticipated several concepts of automated theorem proving.Central to both geometry and to formal logic are the rules of logical inference that establish the validity of arguments and guarantee that conclusions inferred from true [End Page 506] premises are true. The modern analytic tableaux, or tree method, is a fundamental tool in this regard, both for deriving theorems and for determining the validity or invalidity of the proofs for propositional calculus and first-order predicate calculus.Introducing his reconstruction of Part II of Symbolic Logic, Bartley noted that, along with the logic diagrams that Carroll devised, he also devised a tableau method that strongly resembled Beth’s semantic tableaux. Abeles went more deeply and convincingly into that resemblance in her earlier research. Beth’s tableaux, together with Hintikka’s model sets, were the direct ancestors of Smullyan’s analytic tableaux, which in turn are the theoretical basis for the Robinson resolution method that continues to be central to much work in programming logic.Abeles has also shown that the work in Studies in Logic by Charles Peirce and his logic students at Johns Hopkins University served as a source of inspiration for Dodgson. More critically, she demonstrated that Dodgson devised and employed the tree method for carrying out proofs of syllogisms and chains of syllogisms, or soriteses, in Part II of Symbolic Logic (see her “Lewis Carroll’s Method of Trees: Its Origins in Studies in Logic,” Modern Logic 1 [1990]: 25–34). The tree... (shrink)

Smullyan wrote his famous book of puzzles before the boom in automated theorem proving and he solved the puzzles by hand. Hence it is interesting to investigate whether all the puzzles can be solved with one method or not. The paper shows how this can be done with analytic tableaux.

We present tableau proof systems for the annotated version of propositional justification logics, that is, justification logics which are formulated using annotated application operators. We show that the tableau systems are sound and complete with respect to Mkrtychev models, and some tableau systems are analytic and provide a decision procedure for the annotated justification logics. We further show Craig’s interpolation property and Beth’s definability theorem for some annotated justification logics.

his paper presents a unified treatment of the propositional and first-order many-valued logics through the method of tableaux. It is shown that several important results on the proof theory and model theory of those logics can be obtained in a general way. We obtain, in this direction, abstract versions of the completeness theorem, model existence theorem (using a generalization of the classical analytic consistency properties), compactness theorem and Lowenheim-Skolem theorem. The paper is completely self-contained (...) and includes examples of application to particular many-valued formal systems. (shrink)

We prove the following preservation theorem for the Horn fragment of Equality-free Logic:Theorem 0.1. For any sentence σ ϵ L, the following are equivalent:i ) σ is preserved under Hs, Hs -1 and PR.i i ) σ is logically equivalent to an equality-free Horn sentence.

We prove constructively that, in order to derive the uniform continuity theorem for pointwise continuous mappings from a compact metric space into a metric space, it is necessary and sufficient to prove any of a number of equivalent conditions, such as that every pointwise continuous mapping of [0, 1] into R is bounded. The proofs are analytic, making no use of, for example, fan-theoretic ideas.

We extend the notion of absolute convergence for real series in several variables to a notion of convergence for series in a power series field ℝ((t Γ)) with coefficients in ℝ. Subsequently, we define a natural notion of analytic function at a point of ℝ((t Γ))m. Then, given a real function f analytic on a open box I of ℝ m , we extend f to a function f ★ which is analytic on a subset of ℝ((t (...) Γ)) m containing I. We prove that the functions f ★ share with real analytic functions certain basic properties: they are , they have usual Taylor development, they satisfy the inverse function theorem and the implicit function theorem. (shrink)

We study the structure of analytic ideals of subsets of the natural numbers. For example, we prove that for an analytic ideal I, either the ideal {X (Ω × Ω: En X ({0, 1,…,n} × Ω } is Rudin-Keisler below I, or I is very simply induced by a lower semicontinuous submeasure. Also, we show that the class of ideals induced in this manner by lsc submeasures coincides with Polishable ideals as well as analytic P-ideals. We study (...) this class of ideals and characterize, for example, when the ideals in it are Fσ or when they carry a locally compact group topology. We apply these results to Borel partial orders to rederive a theorem of Todorcevic and to Borel equivalence relations to answer a question of Kechris and Louveau. As another application we give a characterization of σ-ideals of μ-zero sets for Maharam submeasures μ on the Cantor set which is to a large extent analogous to a characterization of the meager ideal due to Kechris and the author. (shrink)

We prove that if V = L then there is a $\Pi _{1}^{1}$ maximal orthogonal (i.e., mutually singular) set of measures on Cantor space. This provides a natural counterpoint to the well-known theorem of Preiss and Rataj [16] that no analytic set of measures can be maximal orthogonal.

The paper is concerned with the psychological relevance of a logical model for deductive reasoning. We propose a new way to analyze logical reasoning in a deductive version of the Mastermind game implemented within a popular Dutch online educational learning system (Math Garden). Our main goal is to derive predictions about the difficulty of Deductive Mastermind tasks. By means of a logical analysis we derive the number of steps needed for solving these tasks (a proxy for working memory load). Our (...) model is based on the analytic tableaux method, known from proof theory. We associate the difficulty of Deductive Mastermind game-items with the size of the corresponding logical trees obtained by the tableaux method. We derive empirical hypotheses from this model. A large group of students (over 37 thousand children, 5–12 years of age) played the Deductive Mastermind game, which gave empirical difficulty ratings of all 321 game-items. The results show that our logical approach predicts these item ratings well, which supports the psychological relevance of our model. (shrink)

We prove that for every family I of closed subsets of a Polish space each Σ 1 1 set can be covered by countably many members of I or else contains a nonempty Π 0 2 set which cannot be covered by countably many members of I. We prove an analogous result for κ-Souslin sets and show that if A ♯ exists for any $A \subset \omega^\omega$ , then the above result is true for Σ 1 2 sets. A (...) class='Hi'>theorem of Martin is included stating that this result is also true for weakly homogeneously Souslin sets. As an application of our results we derive from them a general form of Hurewicz's theorem due to Kechris, Louveau, and Woodin and a theorem of Feng on the open covering axiom. Also some well-known theorems on finding "big" closed sets inside of "big" Σ 1 1 and Σ 1 2 sets are consequences of our results. (shrink)

Priest has provided a simple tableau calculus for Chellas's conditional logic Ck. We provide rules which, when added to Priest's system, result in tableau calculi for Chellas's CK and Lewis's VC. Completeness of these tableaux, however, relies on the cut rule.

This paper is intended to give for a general mathematical audience a survey of intriguing connections between analytic combinatorics and logic. We define the ordinals below ε0 in non-logical terms and we survey a selection of recent results about the analytic combinatorics of these ordinals. Using a versatile and flexible compression technique we give applications to phase transitions for independence results, Hilbert’s basis theorem, local number theory, Ramsey theory, Hydra games, and Goodstein sequences. We discuss briefly universality (...) and renormalization issues in this context. Finally, we indicate how regularity properties of ordinal count functions can be used to prove logical limit laws. (shrink)

We introduce, in a general setting, an ‘‘analytic’’ version of standard equational calculi of combinatory logic. Analyticity lies on the one side in the fact that these calculi are characterized by the presence of combinatory introduction rules in place of combinatory axioms, and on the other side in that the transitivity rule proves to be eliminable. Apart from consistency, which follows immediately, we discuss other almost direct consequences of analyticity and the main transitivity elimination theorem; in particular the (...) Church−Rosser and the leftmostreduction theorems for the associated notions of reduction. The last two sections deal with analytic combinatory calculi with the extensionality rule added. Here, as far as the elimination of transitivity is concerned, we have only partial results, which unfortunately do not cover, at present, full CL + Ext. Yet, they are sufficient to prove the decidability of weaker combinatory calculi with extensionality, including e.g. BCK + Ext. (shrink)

Tableau formulations are given for the relevance logics E (Entailment), R (Relevant implication) and RM (Mingle). Proofs of equivalence to modus-ponens-based formulations are vialeft-handed Gentzen sequenzen-kalküle. The tableau formulations depend on a detailed analysis of the structure of tableau rules, leading to certain global requirements. Relevance is caught by the requirement that each node must be used; modality is caught by the requirement that only certain rules can cross a barrier. Open problems are discussed.

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)

We will study several weak axiom systems that use the Subtraction and Division primitives (rather than Addition and Multiplication) to formally encode the theorems of Arithmetic. Provided such axiom systems do not recognize Multiplication as a total function, we will show that it is feasible for them to verify their Semantic Tableaux, Herbrand, and Cut-Free consistencies. If our axiom systems additionally do not recognize Addition as a total function, they will be capable of recognizing the consistency of their Hilbert-style (...) deductive proofs. Our axiom systems will not be strong enough to recognize their Canonical Reflection principle, but they will be capable of recognizing an approximation of it, called the "Tangibility Reflection Principle". We will also prove some new versions of the Second Incompleteness Theorem stating essentially that it is not possible to extend our exceptions to the Incompleteness Theorem much further. (shrink)

A look at Wittgenstein's comments on the incompleteness theorem with an inter-pretation that is consistent with what Gödel proved.

We generalize Solovay's unfolding technique for infinite games and use an Unfolding Theorem to give a uniform method to prove that all analytic sets are in the $\sigma$ -algebras of measurability connected with well-known forcing notions.

\ 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)

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 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.

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)

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)

A system for the modal logic K furnishes a simple mechanical process for proving theorems.

This paper is concerned with decision proceedures for the 0-valued ukasiewicz logics,. It is shown how linear algebra can be used to construct an automated theorem checker. Two decision proceedures are described which depend on a linear programming package. An algorithm is given for the verification of consequence relations in, and a connection is made between theorem checking in two-valued logic and theorem checking in which implies that determing of a -free formula whether it takes the value (...) one is NP-complete problem. (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)