A simple method is provided for translating proofs in Grentzen's LK into proofs in Gentzen's LJ with the Peirce rule adjoined. A consequence is a simpler cut elimination operator for LJ + Peirce that is primitive recursive.

We extend first-order logic to include variadic function symbols, and prove a substitution lemma. Two applications are given: one to bounded quantifier elimination and one to the definability of certain Borel sets.

For first order languages with no individual constants, empty structures and truth values (for sentences) in them are defined. The first order theories of the empty structures and of all structures (the empty ones included) are axiomatized with modus ponens as the only rule of inference. Compactness is proved and decidability is discussed. Furthermore, some well known theorems of model theory are reconsidered under this new situation. Finally, a word is said on other approaches to the whole problem.

Basic Predicate Logic, BQC, is a proper subsystem of Intuitionistic Predicate Logic, IQC. For every formula in the language {, , , , , , }, we associate two sequences of formulas 0,1,... and 0,1,... in the same language. We prove that for every sequent , there are natural numbers m, n, such that IQC , iff BQC n m. Some applications of this translation are mentioned.

From proofs in any classical first-order theory that proves the existence of at least two elements, one can eliminate definitions in polynomial time. From proofs in any classical first-order theory strong enough to code finite functions, including sequential theories, one can also eliminate Skolem functions in polynomial time.

This article identifies problems with regard to providing criteria that regulate the matching of logical formulae and natural language. We then take on to solve these problems by defining a necessary and sufficient criterion of adequate formalization. On the basis of this criterion we argue that logic should not be seen as an ars iudicandi capable of evaluating the validity or invalidity of informal arguments, but as an ars explicandi that renders transparent the formal structure of informal reasoning.

Two subject-predicate calculi with equality,SP = and its extensionUSP =, are presented as systems of natural deduction. Both the calculi are systems of free logic. Their presentation is preceded by an intuitive motivation.It is shown that Aristotle's syllogistics without the laws of identitySaP andSiP is definable withinSP =, and that the first-order predicate logic is definable withinUSP =.

Deep inference is a natural generalisation of the one-sided sequent calculus where rules are allowed to apply deeply inside formulas, much like rewrite rules in term rewriting. This freedom in applying inference rules allows to express logical systems that are difficult or impossible to express in the cut-free sequent calculus and it also allows for a more fine-grained analysis of derivations than the sequent calculus. However, the same freedom also makes it harder to carry out this analysis, in particular it (...) is harder to design cut elimination procedures. In this paper we see a cut elimination procedure for a deep inference system for classical predicate logic. As a consequence we derive Herbrand's Theorem, which we express as a factorisation of derivations. (shrink)

There exist valuable methods for theorem proving in non classical logics based on translation from these logics into first-order classical logic (abbreviated henceforth FOL). The key notion in these approaches istranslation from aSource Logic (henceforth abbreviated SL) to aTarget Logic (henceforth abbreviated TL). These methods are concerned with the problem offinding a proof in TL by translating a formula in SL, but they do not address the very important problem ofpresenting proofs in SL via a backward translation. We propose a (...) framework for presenting proofs in SL based on a partial backward translation of proofs obtained in a familiar TL: Order-Sorted Predicate Logic. The proposed backward translation transfers some formulasF TL belonging to the proof in TL into formulasF SL , such that the formulasF SL either (a) belong to a corresponding deduction in SL (in the best case) or, (b) are semantically related in some precise way, to formulas in the corresponding deduction in SL (in the worst case). The formulasF TL andF SL can obviously be considered aslemmas of their respective proofs. Therefore the transfer of lemmas of TL gives at least a skeleton of the corresponding proof in SL. Since the formulas of a proof keep trace of the strategy used to obtain the proof, clearly the framework can also help in solving another fundamental and difficult problem:the transfer of strategies from classical to non classical logics. We show how to apply the proposed framework, at least to S5, S4(p), K, T, K4. Two conjectures are stated and we propose sufficient (and in general satisfactory) conditions in order to obtain formulas in the proof in SL. Two particular cases of the conjectures are proved to be theorems. Three examples are treated in full detail. The main lines of future research are given. (shrink)

Introduction This is an elementary logic book designed for people who have no technical familiarity with modern logic but who have been reasoning, ...

1. Logic programming did not seize the attention of most programmers until the Japanese announced that they had chosen Prolog for their ambitious Fifth Generation Computer Systems project. While that project appeàrs now to be hampered by bureaucratic difficulties, the interest it aroused in Prolog lives on. Part of the attraction of Prolog stems from the fact that the beginner will very quickly be able to write toy programs, even spectacular ones. Difficulties in creating larger programs, however, seem to bring (...) back Prolog to the level of other programming languages. Such difficulties arise from numerous defects of Prolog, some of which are purely logicai in nature. Among the latter at least two should be mentioned: (a) the peculiar meaning of negation; (b) the fact that reduction to clausal form is not part of the language. As to (a), strictly speaking Prolog has no negation. Its notion ot.negation- as-failure - by which -i <p is inferred from fatture to infer y - is a tricky one. For instance, suppose that the goal likes (John, X ) succeeds with X instantiated to mary. Then not (likes (John, X )) fails, so X becomes uninstantiated and hence has no value. However not (not (likes (John, X ))) succeeds with X instantiated to mary. This makes the meaning of negation almost incomprehensible. As to (b), for efficiency Prolog uses the programmer, as it were, as a preprocessor for reduction to clausal form: with the gain in efficiency that one can very well imagine. Of course reduction to clausal form can be implemented in Prolog and bùilt up within every Prolog program together with a suitable user interface, but this is very much like designing a new programming language. (shrink)

Building on the work of Peter Hinst and Geo Siegwart, we develop a pragmatised natural deduction calculus, i.e., a natural deduction calculus that incorporates illocutionary operators at the formal level, and prove its adequacy. In contrast to other linear calculi of natural deduction, derivations in this calculus are sequences of object-language sentences which do not require graphical or other means of commentary in order to keep track of assumptions or to indicate subproofs.

Building on the work of Peter Hinst and Geo Siegwart, we develop a pragmatised natural deduction calculus, i.e. a natural deduction calculus that incorporates illocutionary operators at the formal level, and prove its adequacy. In contrast to other linear calculi of natural deduction, derivations in this calculus are sequences of object-language sentences which do not require graphical or other means of commentary in order to keep track of assumptions or to indicate subproofs. (Translation of our German paper "Ein Redehandlungskalkül. Ein (...) pragmatisierter Kalkül des natürlichen Schließens nebst Metatheorie"; online available at http://philpapers.org/rec/CORERE.). (shrink)

Work on how to axiomatize the subtheories of a first-order theory in which only a proper subset of their extra-logical vocabulary is being used led to a theorem on recursive axiomatizability and to an interpolation theorem for first-order logic. There were some fortuitous events and several logicians played a helpful role.

First order logic does not distinguish between different forms of universal generalization; in this paper I argue that lawlike and accidental generalizations (broadly construed) have a different logical form, and that this distinction is syntactically marked in English. I then consider the relevance of this broader conception of lawlikeness to the philosophy of science.

The ninth included paper is now fully, formally published with volume number and page numbers, and the second page of the Table of Contents reflects that change, as well. -/- Following Popper on the measure of content, we will combine the concept of logical probability, developed in the nineteenth century, with logical form, and we will answer some objections of Elias to the systematization of Popper's idea by Bar-Hillel and Carnap. We were led along this path by a novel by (...) Isaac Asimov, the biochemist, medical school professor, science fiction writer, and popular science writer—a true polymath with over 400 books to his credit. Elias was concerned that Bar-Hillel and Carnap's theory of semantic content had no philosophical import, no unique properties, and no applications. We will suggest three areas of philosophical import, a unique property based on differences as explained by Peter Milne, and some applications in the general area of abstracting or summarization. We will also suggest that automated language-to-logical-form converters are feasible, necessary for the achievement of various ends, and desirable for the achievement of other ends. In the entire discussion of logical form, we will rely entirely on modern, classical (i.e., two-valued, truth-functional) logic alone, including that most vexatious of connectives, "if." We will close our work with an argument referred to in favor of > from our earlier work, in particular, and truth-functionality, more generally. The connection between the material on content in the first part of this book and the material on a truth-functional approach to logical form in the second part of this book is that the former material presupposes that a certain subset of declarative language is, in fact, truth-functional, a view that is particularly hard to defend for "if," and it is just that defense that is taken up in the second part. This book consists of ten published pieces, as well as three introductory units, and three concluding sections or units. (shrink)

This paper applies the theory of conditional elements to mathematical discourse, rather than ordinary natural-language discourse, in which latter context the theory was first introduced.

This article discusses what is sometimes called the third paradox of material implication. Readers choosing to download this piece should please be so kind as to respect the author's wishes and download the published corrigendum as well, which is available via the "other links" tab.

This piece lays the groundwork for the three 2006 pieces on "Abstracts from Logical Form" (two in /Journal of Pragmatics/, one in /RASK/). The brief introduction to classical logic, propositional and predicate, was inserted at the behest of the referees. Finally, Asimov's conjecture is solved--i.e., formalized--incorrectly here. A corrected version of this paper appeared in the 3rd Volume of /International Journal of Intelligent Systems/, with, as well, a somewhat different emphasis, and /sans/ the introduction to classical logic. However, although that (...) piece /does/ show that Asimov was correct, it does so on a textbook-type example of no intrinsic interest. For the correct solution (formalization) to Asimov's conjecture on Asimov's own story line see "The Logic of 'Double Talk': A Case Study in Diplomatic Deception" (/Journal of Literary Semantics/, 20(1): 53-55.). (shrink)

We discuss the thesis formulated by Hintikka (1973) that certain natural language sentences require non-linear quantification to express their meaning. We investigate sentences with combinations of quantifiers similar to Hintikka's examples and propose a novel alternative reading expressible by linear formulae. This interpretation is based on linguistic and logical observations. We report on our experiments showing that people tend to interpret sentences similar to Hintikka sentence in a way consistent with our interpretation.

We present two proof systems for first-order logic with identity and without function symbols. The first one is an extension of the Rasiowa-Sikorski system with the rules for identity. This system is a validity checker. The rules of this system preserve and reflect validity of disjunctions of their premises and conclusions. The other is a Tableau system, which is an unsatisfiability checker. Its rules preserve and reflect unsatisfiability of conjunctions of their premises and conclusions. We show that the two systems (...) are dual to each other. The duality is expressed in a formal way which enables us to define a transformation of proofs in one of the systems into the proofs of the other. (shrink)

Automated theorem proving amounts to solving search problems in usually tremendous search spaces. A lot of research therefore focuses on search space reductions. Our approach reduces the search space which arises when using so-called connection tableau calculi for first-order automated theorem proving. It uses disjunctive constraints over first-order equations to compress certain parts of this search space. We present the basics of our constrained-connection-tableau calculi, a constraint extension of connection tableau calculi, and deal with the efficient handling of constraints during (...) the search process. The new techniques are integrated into the automated connection tableau prover Setheo. (shrink)

Thus far the logic out of which mathematics has developed has been First-order Predicate Calculus with Identity, that is the logic of the sentential functors, ¬, →, ∧, ∨, etc., together with identity and the existential and universal quotifiers restricted to quotify- ing only over individuals, and not anything else, such as qualities or quotities themselves. Some philosophers—among them Quine— have held that this, First-order Logic, as it is often called, con- stitutes the whole of logic. But that is a (...) mistake. It leaves out Second-order Logic, which we need if we are to characterize the natural numbers precisely, and pays scant attention to the logic of relations, especially transitive relations, which is the key to much of modern mathematics. Quine’s argument for restricting logic to First-order Logice was based on the grounds that only First- order logical theories display “Law and Order” and himself regards modal logic as belonging with witchcraft and superstition.1 Pred- icates are ontologically more suspect than individuals, and have a different logic, which is liable to give rise to paradox and inconsis- tency. Moreover, Second-order Logic lacks the completeness that First-order Logice has, which provides a pleasing parallel between syntactic and semantic notions, and argues for the analyticity of deductive logic. (shrink)

Classical logic has proved inadequate in various areas of computer science, artificial intelligence, mathematics, philosopy and linguistics. This is an introduction to extensions of first-order logic, based on the principle that many-sorted logic (MSL) provides a unifying framework in which to place, for example, second-order logic, type theory, modal and dynamic logics and MSL itself. The aim is two fold: only one theorem-prover is needed; proofs of the metaproperties of the different existing calculi can be avoided by borrowing them from (...) MSL. To make the book accessible to readers from different disciplines, whilst maintaining precision, the author has supplied detailed step-by-step proofs, avoiding difficult arguments, and continually motivating the material with examples. Consequently this can be used as a reference, for self-teaching or for first-year graduate courses. (shrink)

Standard (classical) logic is not independent of set theory. Which formulas are valid in logic depends on which sets we assume to exist in our set-theoretical universe. Second-order logic is just set theory in disguise. The typically logical notions of validity and consequence are not well defined in second-order logic, at least as long as there are open issues in set theory. Such contentious issues in set theory as the axiom of choice, the continuum hypothesis or the existence of inaccessible (...) cardinals, can be equivalently transformed into question about the logical validity of pure sentences of second-order logic, where “pure” means that they only contain logical symbols and bound variables. Even standard first-order logic depends on the acceptance on infinite sets in our set-theoretical universe. Should we choose to admit only finite sets, the number of logically valid pure first-order formulas would increase dramatically and first-order logic would not be recursively enumerable any longer. (shrink)

It is argued that, in the traditional subject-predicate sentence, two interpretations of the subject term coexist, one intensional and the other extensional, which explains the superficial difference between the traditional S-P relation and the predication of predicate logic. Data from psychological studies of syllogistic reasoning support the view that the contrast between predicate and argument is carried over to the traditional S-P sentence.

This text is a short introduction to logic that was primarily used for accompanying an introductory course in Logic for Linguists held at the New University of Lisbon (UNL) in fall 2010. The main idea of this course was to give students the formal background and skills in order to later assess literature in logic, semantics, and related fields and perhaps even use logic on their own for the purpose of doing truth-conditional semantics. This course in logic does not replace (...) a proper introduction to semantics and is not intended as such, although parts of Chapter 1 and 4 could be used to supplement an introductory course in semantics. In contrast to other introductions it has a certain focus on ‘writing things down correctly.’ Proofs of metatheorems are omitted, though. -/- This is work in progress. Please send suggestions and corrigenda to erich@snafu.de. Have fun! (shrink)

Natural deduction (for short: nd-) calculi have not been used systematically as a basis for automated theorem proving in classical logic. To remove objective obstacles to their use we describe (1) a method that allows to give semantic proofs of normal form theorems for nd-calculi and (2) a framework that allows to search directly for normal nd-proofs. Thus, one can try to answer the question: How do we bridge the gap between claims and assumptions in heuristically motivated ways? This informal (...) question motivates the formulation of intercalation calculi. Ic-calculi are the technical underpinnings for (1) and (2), and our paper focuses on their detailed presentation and meta-mathematical investigation in the case of classical predicate logic. As a central theme emerges the connection between restricted forms of nd-proofs and (strategies for) proof search: normal forms are not obtained by removing local "detours", but rather by constructing proofs that directly reflect proof-strategic considerations. That theme warrants further investigation. (shrink)

This completely self-contained study, widely considered the best book in the field, is intended to serve both as an introduction to quantification theory and as ...

We investigate a variant of the variable convention proposed at Tractatus 5.53ff for the purpose of eliminating the identity sign from logical notation. The variant in question is what Hintikka has called the strongly exclusive interpretation of the variables, and turns out to be what Ramsey initially (and erroneously) took to be Wittgenstein's intended method. We provide a tableau calculus for this identity-free logic, together with soundness and completeness proofs, as well as a proof of mutual interpretability with first-order logic (...) with identity. (shrink)

Given a classical theory T, a Kripke model K for the language L of T is called T-normal or locally PA just in case the classical L-structure attached to each node of K is a classical model of T. Van Dalen, Mulder, Krabbe, and Visser showed that Kripke models of Heyting Arithmetic (HA) over finite frames are locally PA, and that Kripke models of HA over frames ordered like the natural numbers contain infinitely many PA-nodes. We show that Kripke models (...) of the latter sort are in fact PA-normal. This result is extended to a somewhat larger class of frames. (shrink)