This is a tutorial for the Minlog Proof Assistant, version 5.0.

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)

We investigate some logics which use the concept of minimal models in their definition. Minimal objects are widely used in Logic and Computer Science. They are applied in the context of Inductive Definitions, Logic Programming and Artificial Intelligence. An example of logic which uses this concept is the MIN logic due to van Benthem [20]. He shows that MIN is equivalent to the Least Fixed Point logic in expressive power. In [6], we extended MIN to the MIN Logic (...) and proved it is equivalent to second-order logic in expressive power. Here, we exhibit a fragment of MIN, the MINΔ logic, which is more expressive than LFP, less expressive than MIN and closed under boolean connectives and first-order quantification. In order to do this, in the Section 2, we prove that the Downward Löwenheim-Skolem Theorem holds for arbitrary countable sets of LFP-formulas by showing that every infinite structure has a countable LFP-substructure. The method may be used to generalize this theorem to any set of LFP-formulas. We also analyse the expressive power of the Nested Abnormality Theories of Lifschitz, another formalism based on minimal models used in Artificial Intelligence, and we demonstrate that for each second-order theory Γ there is a NAT which is a conservative extension of Γ. We give a translation from second-order sentences into such NATs which is linear in the size of the sentence in prenex normal form. Finally, we establish a hierarchy of expressiveness of these logics that deal with the concept of minimal models. (shrink)

THINKER is an automated natural deduction first-order theorem proving program. This paper reports on how it was adapted so as to prove theorems in modal logic. The method employed is an indirect semantic method, obtained by considering the semantic conditions involved in being a valid argument in these modal logics. The method is extended from propositional modal logic to predicate modal logic, and issues concerning the domain of quantification and existence in a world's domain are discussed. Finally, we (...) look at the very interesting issues involved with adding identity to the theorem prover in the realm of modal predicate logic. Various alternatives are discussed. (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.

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)

Proof assistants are software-based tools that are used in the mechanization of proof construction and validation in mathematics and computer science, and also in certified program development. Different such tools are being increasingly used in order to accelerate and simplify proof checking, and the Coq proof assistant is one of the most well known and used in large-scale projects. Language and automata theory is a well-established area of mathematics, relevant to computer science foundations and information technology. In particular, context-free (...) language theory is of fundamental importance in the analysis, design, and implementation of computer programming languages. This work describes a formalization effort, using the Coq proof assistant, of fundamental results of the classical theory of contextfree grammars and languages. These include closure properties (union, concatenation, and Kleene star), grammar simplification (elimination of useless symbols, inaccessible symbols, empty rules, and unit rules), the existence of a Chomsky Normal Form for context-free grammars and the Pumping Lemma for context-free languages. The result is an important set of libraries covering the main results of context-free language theory, with more than 500 lemmas and theorems fully proved and checked. As it turns out, this is a comprehensive formalization of the classical context-free language theory in the Coq proof assistant and includes the formalization of the Pumping Lemma for context-free languages. The perspectives for the further development of this work are diverse and can be grouped in three different areas: inclusion of new devices and results, code extraction, and general enhancements of its libraries. (shrink)

This paper contains the full code of a prototype implementation in Haskell [5], in ‘literate programming’ style [6], of the tableau-based calculus and proof procedure for hybrid logic presented in [4].

This paper describes formalizations of Tait's normalization proof for the simply typed λ-calculus in the proof assistants Minlog, Coq and Isabelle/HOL. From the formal proofs programs are machine-extracted that implement variants of the well-known normalization-by-evaluation algorithm. The case study is used to test and compare the program extraction machineries of the three proof assistants in a non-trivial setting.

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)

We present a method for integrating rippling-based rewriting into matrix-based theorem proving as a means for automating inductive specification proofs. The selection of connections in an inductive matrix proof is guided by symmetries between induction hypothesis and induction conclusion. Unification is extended by decision procedures and a rippling/reverse-rippling heuristic. Conditional substitutions are generated whenever a uniform substitution is impossible. We illustrate the integrated method by discussing several inductive proofs for the integer square root problem as well as the algorithms (...) extracted from these proofs. (shrink)

Reverse Mathematics (RM) is a program in the foundations of mathematics where the aim is to find the minimal axioms needed to prove a given theorem of ordinary mathematics. Generally, the minimal axioms are equivalent to the theorem at hand, assuming a weak logical system called the base theory. Moreover, many theorems are either provable in the base theory or equivalent to one of four logical systems, together called the Big Five. For instance, the Weierstrass (...) approximation theorem, i.e., that a continuous function can be approximated uniformly by a sequence of polynomials, has been classified in RM as being equivalent to weak König’s lemma, the second Big Five system. In this paper, we study approximation theorems for discontinuous functions via Bernstein polynomials from the literature. We obtain many equivalences between the latter and weak König’s lemma. We also show that slight variations of these approximation theorems fall far outside of the Big Five but fit in the recently developed RM of new ‘big’ systems, namely the uncountability of ${\mathbb R}$, the enumeration principle for countable sets, the pigeon-hole principle for measure, and the Baire category theorem. (shrink)

This volume contains finalized versions of papers presented at an international workshop on extensions of logic programming, held at the Seminar for Natural Language Systems at the University of Tübingen in December 1989. Several recent extensions of definite Horn clause programming, especially those with a proof-theoretic background, have much in common. One common thread is a new emphasis on hypothetical reasoning, which is typically inspired by Gentzen-style sequent or natural deduction systems. This is not only of theoretical significance, but also (...) bears upon computational issues. It was one purpose of the workshop to bring some of these recent developments together. The volume covers topics such as the languages Lambda-Prolog, N-Prolog, and GCLA, the relationship between logic programming and functional programming, and the relationship between extensions of logic programming and automated theorem proving. It contains the results of the first conference concentrating on proof-theoretic approaches to logic programming. (shrink)

This paper addresses the strength of Ramsey's theorem for pairs ($RT^2_2$) over a weak base theory from the perspective of 'proof mining'. Let $RT^{2-}_2$ denote Ramsey's theorem for pairs where the coloring is given by an explicit term involving only numeric variables. We add this principle to a weak base theory that includes weak König's Lemma and a substantial amount of $\Sigma^0_1$-induction (enough to prove the totality of all primitive recursive functions but not of all primitive recursive functionals). (...) In the resulting theory we show the extractability of primitive recursive programs and uniform bounds from proofs of $\forall\exists$-theorems. There are two components of this work. The first component is a general proof-theoretic result, due to the second author, that establishes conservation results for restricted principles of choice and comprehension over primitive recursive arithmetic PRA as well as a method for the extraction of primitive recursive bounds from proofs based on such principles. The second component is the main novelty of the paper: it is shown that a proof of Ramsey's theorem due to Erdős and Rado can be formalized using these restricted principles. So from the perspective of proof unwinding the computational content of concrete proofs based on $RT^2_2$ the computational complexity will, in most practical cases, not go beyond primitive recursive complexity. This even is the case when the theorem to be proved has function parameters f and the proof uses instances of $RT^2_2$ that are primitive recursive in f. (shrink)

Reverse Mathematics (RM hereafter) is a program in the foundations of mathematics where the aim is to identify the minimal axioms needed to prove a given theorem from ordinary, i.e., non-set theoretic, mathematics. This program has unveiled surprising regularities: the minimal axioms are very often equivalent to the theorem over the base theory, a weak system of ‘computable mathematics’, while most theorems are either provable in this base theory, or equivalent to one of only (...) four logical systems. The latter plus the base theory are called the ‘Big Five’ and the associated equivalences are robust following Montalbán, i.e., stable under small variations of the theorems at hand. Working in Kohlenbach’s higher-order RM, we obtain two new and long series of equivalences based on theorems due to Bolzano, Weierstrass, Jordan, and Cantor; these equivalences are extremely robust and have no counterpart among the Big Five systems. Thus, higher-order RM is much richer than its second-order cousin, boasting at least two extra ‘Big’ systems. (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)

The paper expands upon the work by Wang [4], who proposes a new framework based on quantifier-free predicate language extended by a new modality ∃x□\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\exists x\Box $$\end{document} and axiomatizes the logic over S5 frames. This paper gives the logics over K, D, T, 4, S4 frames with increasing and constant domains. And we provide a general strategy for proving completeness theorems for logics w.r.t. the increasing domain and logics w.r.t. the (...) constant domain respectively. (shrink)

Certain extensions of Nelson's constructive logic N with strong negation have recently become important in arti.cial intelligence and nonmonotonic reasoning, since they yield a logical foundation for answer set programming (ASP). In this paper we look at some extensions of Nelson's .rst-order logic as a basis for de.ning nonmonotonic inference relations that underlie the answer set programming semantics. The extensions we consider are those based on 2-element, here-and-there Kripke frames. In particular, we prove completeness for .rst-order here-and-there logics, and their (...) minimal strong negation extensions, for both constant and varying domains. We choose the constant domain version, which we denote by QNc5, as a basis for de.ning a .rst-order nonmonotonic extension called equilibrium logic. We establish several metatheoretic properties of QNc5, including Skolem forms and Herbrand theorems and Interpolation, and show that the .rst-oder version of equilibrium logic can be used as a foundation for answer set inference. (shrink)

We introduce a new typed combinatory calculus with a type constructor that, to each type σ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma $$\end{document}, associates the star type σ∗\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma ^*$$\end{document} of the nonempty finite subsets of elements of type σ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma $$\end{document}. We prove that this calculus enjoys the properties of strong normalization and confluence. With the aid of (...) this star combinatory calculus, we define a functional interpretation of first-order predicate logic and prove a corresponding soundness theorem. It is seen that each theorem of classical first-order logic is connected with certain formulas which are tautological in character. As a corollary, we reprove Herbrand’s theorem on the extraction of terms from classically provable existential statements. (shrink)

Providing a possible worlds semantics for a logic involves choosing a class of possible worlds models, and setting up a truth definition connecting formulas of the logic with statements about these models. This scheme is so flexible that a danger arises: perhaps, any logic whatsoever can be modelled in this way. Thus, the enterprise would lose its essential 'tension'. Fortunately, it may be shown that the so-called 'incompleteness-examples' from modal logic resist possible worlds modelling, even in the above wider sense. (...) More systematically, we investigate the interplay of truth definitions and model conditions, proving a preservation theorem characterizing those types of truth definition which generate the minimal modal logic. (shrink)

Providing a possible worlds semantics for a logic involves choosing a class of possible worlds models, and setting up a truth definition connecting formulas of the logic with statements about these models. This scheme is so flexible that a danger arises: perhaps, any (reasonable) logic whatsoever can be modelled in this way. Thus, the enterprise would lose its essential tension. Fortunately, it may be shown that the so-called incompleteness-examples from modal logic resist possible worlds modelling, even in the above wider (...) sense. More systematically, we investigate the interplay of truth definitions and model conditions, proving a preservation theorem characterizing those types of truth definition which generate the minimal modal logic. (shrink)

This is the 3rd edition. Although a number of new technological applications require classical deductive computation with non-classical logics, many key technologies still do well—or exclusively, for that matter—with classical logic. In this first volume, we elaborate on classical deductive computing with classical logic. The objective of the main text is to provide the reader with a thorough elaboration on both classical computing – a.k.a. formal languages and automata theory – and classical deduction with the classical first-order predicate calculus with (...) a view to computational implementations, namely in automated theorem proving and logic programming. The present third edition improves on the previous ones by providing an altogether more algorithmic approach: There is now a wholly new section on algorithms and there are in total fourteen clearly isolated algorithms designed in pseudo-code. Other improvements are, for instance, an emphasis on functions in Chapter 1 and more exercises with Turing machines. (shrink)

Denotational semantics of logic programming and its extensions have been studied thoroughly for many years. In 1998, a game semantics was given to definite logic programs by Di Cosmo, Loddo, and Nicolet, and a few years later it was extended to deal with negation by Rondogiannis and Wadge. Both approaches were proven equivalent to the traditional semantics. In this paper we define a game semantics for disjunctive logic programs and prove soundness and completeness with respect to the minimal model (...) semantics of Minker. The overall development has been influenced by the games studied for PCF and functional programming in general, in the styles of Abramsky–Jagadeesan–Malacaria and Hyland–Ong–Nickau. (shrink)

This volume contains several invited papers as well as a selection of the other contributions. The conference was the first meeting of the Soviet logicians interested in com- puter science with their Western counterparts. The papers report new results and techniques in applications of deductive systems, deductive program synthesis and analysis, computer experiments in logic related fields, theorem proving and logic programming. It provides access to intensive work on computer logic both in the USSR and in Western countries.

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)

We prove that the minimal Logic of Formal Inconsistency $\mathsf{QmbC}$ validates a weaker version of Fraïssé’s theorem. LFIs are paraconsistent logics that relativize the Principle of Explosion only to consistent formulas. Now, despite the recent interest in LFIs, their model-theoretic properties are still not fully understood. Our aim in this paper is to investigate the situation. Our interest in FT has to do with its fruitfulness; the preservation of FT indicates that a number of other classical semantic properties (...) can be also salvaged in LFIs. Further, given that FT depends on truth-functionality, whether full FT holds for $\mathsf{QmbC}$ becomes a challenging question. (shrink)

The European Workshop on Logics in Artificial Intelligence was held at the Centre for Mathematics and Computer Science in Amsterdam, September 10-14, 1990. This volume includes the 29 papers selected and presented at the workshop together with 7 invited papers. The main themes are: - Logic programming and automated theorem proving, - Computational semantics for natural language, - Applications of non-classical logics, - Partial and dynamic logics.

Reverse mathematics is a program in the foundations of mathematics. It provides an elegant classification in which the majority of theorems of ordinary mathematics fall into only five categories, based on the “big five” logical systems. Recently, a lot of effort has been directed toward finding exceptional theorems, that is, those which fall outside the big five. The so-called reverse mathematics zoo is a collection of such exceptional theorems. It was previously shown that a number of uniform versions of (...) the zoo theorems, that is, where a functional computes the objects stated to exist, fall in the third big five category, arithmetical comprehension, inside Kohlenbach’s higher-order reverse mathematics. In this paper, we extend and refine these previous results. In particular, we establish analogous results for recent additions to the reverse mathematics zoo, thus establishing that the latter disappear at the uniform level. Furthermore, we show that the aforementioned equivalences can be proved using only intuitionistic logic. Perhaps most surprisingly, these explicit equivalences are extracted from nonstandard equivalences in Nelson’s internal set theory, and we show that the nonstandard equivalence can be recovered from the explicit ones. Finally, the following zoo theorems are studied in this paper: Π10G, FIP, 1-GEN, OPT, AMT, SADS, AST, NCS, and KPT. (shrink)

Dp-minimality is a common generalization of weak minimality and weak o-minimality. If T is a weakly o-minimal theory then it is dp-minimal (Fact 2.2), but there are dp-minimal densely ordered groups that are not weakly o-minimal. We introduce the even more general notion of inp-minimality and prove that in an inp-minimal densely ordered group, every definable unary function is a union of finitely many continuous locally monotonic functions (Theorem 3.2).

This volume contains the proceedings of JELIA '92, les Journ es Europ ennes sur la Logique en Intelligence Artificielle, or the Third European Workshop on Logics in Artificial Intelligence. The volume contains 2 invited addresses and 21 selected papers covering such topics as: - Logical foundations of logic programming and knowledge-based systems, - Automated theorem proving, - Partial and dynamic logics, - Systems of nonmonotonic reasoning, - Temporal and epistemic logics, - Belief revision. One invited paper, by D. Vakarelov, (...) is on arrow logics, i.e., modal logics for representing graph information. The other, by L.M. Pereira,J.J. Alferes, and J.N. Apar cio, is on default theory for well founded semantics with explicit negation. (shrink)

We prove two antibasis theorems for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} classes. The first is a jump inversion theorem for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} classes with respect to the global structure of the Turing degrees. For any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${P\subseteq 2^\omega}$$\end{document}, define S(P), the degree spectrum of P, to be the set of all Turing degrees a such that (...) there exists \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A \in P}$$\end{document} of degree a. For any degree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a \geq 0'}}$$\end{document}, let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textrm{Jump}^{-1}({\bf a) = \{b : b' = a \}}}$$\end{document}. We prove that, for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a \geq 0'}}$$\end{document} and any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} class P, if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textrm{Jump}^{-1} ({\bf a}) \subseteq S(P)}$$\end{document} then P contains a member of every degree. For any degree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a \geq 0'}}$$\end{document} such that a is recursively enumerable (r.e.) in 0', let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${Jump_{\bf \leq 0'} ^{-1}({\bf a)=\{b : b \leq 0' \textrm{and} b' = a \}}}$$\end{document}. The second theorem concerns the degrees below 0'. We prove that for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\bf a\geq 0'}}$$\end{document} which is recursively enumerable in 0' and any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} class P, if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textrm{Jump}_{\bf \leq 0'} ^{-1}({\bf a)} \subseteq S(P)}$$\end{document} then P contains a member of every degree. (shrink)

Theorem 1 states a negative result about the classical semantics j= ! of program schemes. Theorem 2 investigates the reason for this. We conclude that Theorem 2 justies the Henkin-type semantics j= for which the opposite of the present Theorem 1 was proved in [1]{[3] and also in a dierent form in part III of [5]. The strongest positive result on j= is Corollary 6 in [3].

Cartesian closed categories (CCCs) have played and continue to play an important role in the study of the semantics of programming languages. An axiomatization of the isomorphisms which hold in all Cartesian closed categories discovered independently by Soloviev and Bruce, Di Cosmo and Longo leads to seven equalities. We show that the unification problem for this theory is undecidable, thus settling an open question. We also show that an important subcase, namely unification modulo the linear isomorphisms, is NP-complete. Furthermore, the (...) problem of matching in CCCs is NP-complete when the subject term is irreducible. CCC-matching and unification form the basis for an elegant and practical solution to the problem of retrieving functions from a library indexed by types investigated by Rittri. It also has potential applications to the problem of polymorphic type inference and polymorphic higher-order unification, which in turn is relevant to theorem proving and logic programming. (shrink)

Depending on what one means by the main connective of logic, the -if..., then... -, several systems of logic result: classic and modal logics, intuitionistic logic or relevance logic. This book presents the underlying ideas, the syntax and the semantics of these logics. Soundness and completeness are shown constructively and in a uniform way. Attention is paid to the interdisciplinary role of logic: its embedding in the foundations of mathematics and its intimate connection with philosophy, in particular the philosophy of (...) language. Set theory is presented both as a conditio sine qua non for logic and as a interesting exact ontology. The study of infinite sets yields perplexing results. Formalization of informal number theory results in formal number theory; Godel's incompleteness is treated. At appropriate places attention is paid to paradoxes, intuitionism, conditionals, the historical development of logic, to logic programming and automated theorem proving for classical logic.". (shrink)

Two algebraic structures, the contrapositionally complemented Heyting algebra (ccHa) and the contrapositionally |$\vee $| complemented Heyting algebra (c|$\vee $|cHa), are studied. The salient feature of these algebras is that there are two negations, one intuitionistic and another minimal in nature, along with a condition connecting the two operators. Properties of these algebras are discussed, examples are given and comparisons are made with relevant algebras. Intuitionistic Logic with Minimal Negation (ILM) corresponding to ccHas and its extension |${\textrm {ILM}}$|-|${\vee }$| (...) for c|$\vee $|cHas are then investigated. Besides its relations with intuitionistic and minimal logics, ILM is observed to be related to Peirce’s logic and Vakarelov’s logic MIN. With a focus on properties of the two negations, relational semantics for ILM and |${\textrm {ILM}}$|-|${\vee }$| are obtained with respect to four classes of frames, and inter-translations between the classes preserving truth and validity are provided. ILM and |${\textrm {ILM}}$|-|${\vee }$| are shown to have the finite model property with respect to these classes of frames and proved to be decidable. Extracting features of the two negations in the algebras, a further investigation is made, following logical studies of negations that define the operators independently of the binary operator of implication. Using Dunn’s logical framework for the purpose, two logics |$K_{im}$| and |$K_{im-{\vee }}$| are discussed, where the language does not include implication. The |$K_{im}$|-algebras are reducts of ccHas and are different from relevant algebraic structures having two negations. The negations in the |$K_{im}$|-algebras and |$K_{im-{\vee }}$|-algebras are shown to occupy distinct positions in an enhanced form of Dunn’s kite of negations. Relational semantics for |$K_{im}$| and |$K_{im-{\vee }}$| is provided by a class of frames that are based on Dunn’s compatibility frames. It is observed that this class coincides with one of the four classes giving the relational semantics for ILM and |${\textrm {ILM}}$|-|${\vee }$|⁠. (shrink)

Suppose $D \subset M$ is a strongly minimal set definable in M with parameters from C. We say D is locally modular if for all $X, Y \subset D$ , with $X = \operatorname{acl}(X \cup C) \cap D, Y = \operatorname{acl}(Y \cup C) \cap D$ and $X \cap Y \neq \varnothing$ , dim(X ∪ Y) + dim(X ∩ Y) = dim(X) + dim(Y). We prove the following theorems. Theorem 1. Suppose M is stable and $D \subset M$ is (...) strongly minimal. If D is not locally modular then in M eq there is a definable pseudoplane. (For a discussion of M eq see [M, § A].) This is the main part of Theorem 1 of [Z2] and the trichotomy theorem of [Z3]. Theorem 2. Suppose M is stable and $D, D' \subset M$ are strongly minimal and nonorthogonal. Then D is locally modular if and only if D' is locally modular. (shrink)

We prove a definable analogue to Brouwer's Fixed Point Theorem for o-minimal structures of real closed field expansions: A continuous definable function mapping from the unit simplex into itself admits a fixed point, even though the underlying space is not necessarily topologically complete. Our proof is direct and elementary; it uses a triangulation technique for o-minimal functions, with an application of Sperner's Lemma.

We introduce a new type system called “System ST” , based on subtyping, and prove the basic property of the system. We show the extraordinary expressive power of the system which leads us to think that it could be a good candidate for doing both proof and extraction of programs.

Reverse mathematics is a program in the foundations of mathematics founded by Friedman and developed extensively by Simpson and others. The aim of RM is to find the minimal axioms needed to prove a theorem of ordinary, that is, non-set-theoretic, mathematics. As suggested by the title, this paper deals with the study of the topological notions of dimension and paracompactness, inside Kohlenbach’s higher-order RM. As to splittings, there are some examples in RM of theorems A, B, C (...) such that A ↔, that is, A can be split into two independent parts B and C, and the aforementioned topological notions give rise to a number of splittings involving highly natural A, B, C. Nonetheless, the higher-order picture is markedly different from the second-one: in terms of comprehension axioms, the proof in higher-order RM of, for example, the paracompactness of the unit interval requires full second-order arithmetic, while the second-order/countable version of paracompactness of the unit interval is provable in the base theory RCA 0. We obtain similarly “exceptional” results for the Urysohn identity, the Lindelöf lemma, and partitions of unity. We show that our results exhibit a certain robustness, in that they do not depend on the exact definition of cover, even in the absence of the axiom of choice. (shrink)

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)

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

We prove a dichotomy theorem for minimal structures and use it to prove that the number of non-isomorphic countable elementary extensions of an arbitrary countable, infinite first-order structure is infinite.

Wilkie 5 397) proved a “theorem of the complement” which implies that in order to establish the o-minimality of an expansion of with C∞ functions it suffices to obtain uniform bounds on the number of connected components of quantifier free definable sets. He deduced that any expansion of with a family of Pfaffian functions is o-minimal. We prove an effective version of Wilkie's theorem of the complement, so in particular given an expansion of the ordered field with (...) finitely many C∞ functions, if there are uniform and computable upper bounds on the number of connected components of quantifier free definable sets, then there are uniform and computable bounds for all definable sets. In such a case the theory of the structure is effectively o-minimal: there is a recursively axiomatized subtheory such that each of its models is o-minimal. This implies the effective o-minimality of any expansion of with Pfaffian functions. We apply our results to the open problem of the decidability of the theory of the real field with the exponential function. We show that the decidability is implied by a positive answer to the following problem ): given a language L expanding the language of ordered rings, if an L-sentence is true in every L-structure expanding the ordered field of real numbers, then it is true in every o-minimal L-structure expanding any real closed field. (shrink)

This article generalises the refined A-translation method for extracting programs from classical proofs [U. Berger,W. Buchholz, H. Schwichtenberg, Refined program extraction from classical proofs, Annals of Pure and Applied Logic 114 3–25] to the scenario where additional assumptions such as choice principles are involved. In the case of choice principles, this is done by adding computational content to the ‘translated’ assumptions, an idea which goes back to [S. Berardi, M. Bezem, T. Coquand, On the computational content of the (...) axiom of choice, JSL 63 600–622] and has been further elaborated in [U. Berger, P. Oliva, Modified bar recursion and classical dependent choice, in: M. Baaz, S.D. Friedman, J. Kraijcek , Logic Colloquium ’01, in: Lecture Notes in Logic, vol. 20, Springer, Berlin, 2005, pp. 89–107]. We further investigate the applicability of this extension by means of a small but non-trivial example, and discuss the formalisation as well as some optimisations necessary in order to extract terminating programs. Both formalisation and term extraction have been implemented in the interactive proof assistant Minlog. (shrink)