In 1944 Hans Reichenbach developed a three-valued propositional logic (RQML) in order to account for certain causal anomalies in quantum mechanics. In this logic, the truth-value _indeterminate_ is assigned to those statements describing physical phenomena that cannot be understood in causal terms. However, Reichenbach did not develop a deductive calculus for this logic. The aim of this paper is to develop such a calculus by means of First Degree Entailment logic (FDE) and to prove it sound and complete (...) with respect to RQML semantics. In Section 1 we explain the main physical and philosophical motivations of RQML. Next, in Sections 2 and 3, respectively, we present RQML and FDE syntax and semantics and explain the relation between both logics. Section 4 introduces \(\varvec{\mathcal {Q}}\) calculus, an FDE-based tableaux calculus for RQML. In Section 5 we prove that \(\varvec{\mathcal {Q}}\) calculus is sound and complete with respect to RQML three-valued semantics. Finally, in Section 6 we consider some of the main advantages of \(\varvec{\mathcal {Q}}\) calculus and we apply it to Reichenbach’s analysis of causal anomalies. (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.

Wittgensteinian predicate logic (W-logic) is characterized by the requirement that the objects mentioned within the scope of a quantifier be excluded from the range of the associated bound variable. I present a sound and complete tableaux calculus for this logic and discuss issues of translatability between Wittgensteinian and standard predicate logic in languages with and without individual constants. A metalinguistic co-denotation predicate, akin to Frege’s triple bar of the Begriffsschrift, is introduced and used to bestow the full expressive (...) power of first-order logic with identity on W-logic in the presence of constants. (shrink)

Motivated by H. Curry’s well-known objection and by a proposal of L. Henkin, this article introduces the positive tableaux, a form of tableau calculus without refutation based upon the idea of implicational triviality. The completeness of the method is proven, which establishes a new decision procedure for the (classical) positive propositional logic. We also introduce the concept of paratriviality in order to contribute to the question of paradoxes and limitations imposed by the behavior of classical implication.

The inference systems proposed for solving SAT are unsound for solving MaxSAT and MinSAT, because they preserve satisfiability but not the minimum and maximum number of clauses that can be falsified, respectively. To address this problem, we first define a clause tableau calculus for MaxSAT and prove its soundness and completeness. We then define a clause tableau calculus for MinSAT and also prove its soundness and completeness. Finally, we define a complete clause tableau calculus for solving both (...) MaxSAT and MinSAT, in that the minimum number of generated empty clauses provides an optimal MaxSAT solution and the maximum number provides an optimal MinSAT solution. (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)

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.

The formalization of abductive reasoning has received increasing attention from logicians. However, few work is found beyond abduction in propositional logic, given that in a first order formalism, the undecidability problem naturally appears, and therefore an abductive problem cannot even be appropriately formulated. Still, many applications in artificial intelligence allow finite domains to work with, and this gives an opportunity to apply abduction in first order logic with restricted domains. In this paper, we present an approach to abductive reasoning in (...) C-structures, first order structures with a finite domain in which each of its elements has a corresponding constant representing its interpretation. By using semantic tableaux with bounded depth, that is, C-tableaux (a modification of N-tableaux, introduced by the authors in previous papers) and δ-resolution calculus, we build an effective procedure for the searching of minimal abductive solutions within the proposed semantics. (shrink)

Hyper tableau reasoning is a version of clausal form tableau reasoning where all negative literals in a clause are resolved away in a single inference step. Constrained hyper tableaux are a generalization of hyper tableaux, where branch closing substitutions, from the point of view of model generation, give rise to constraints on satisfying assignments for the branch. These variable constraints eliminate the need for the awkward ‘purifying substitutions’ of hyper tableaux. The paper presents a non-destructive and proof (...) confluent calculus for constrained hyper tableaux, together with a soundness and completeness proof, with completeness based on a new way to generate models from open tableaux. It is pointed out that the variable constraint approach applies to free variable tableau reasoning in general. (shrink)

The aim of this paper is to emphasize the fact that for all finitely-many-valued logics there is a completely systematic relation between sequent calculi and tableau systems. More importantly, we show that for both of these systems there are al- ways two dual proof sytems (not just only two ways to interpret the calculi). This phenomenon may easily escape one’s attention since in the classical (two-valued) case the two systems coincide. (In two-valued logic the assignment of a truth value and (...) the exclusion of the opposite truth value describe the same situation.). (shrink)

We present a cut-free tableau calculus with histories and variables for the EXPTIME-complete multi-modal logic of common knowledge. Our calculus constructs the tableau using only one pass, so proof-search for testing theoremhood of ϕ does not exhibit the worst-case EXPTIME-behaviour for all ϕ as in two-pass methods. Our calculus also does not contain a “finitized ω-rule” so that it detects cyclic branches as soon as they arise rather than by worst-case exponential branching with respect to the size (...) of ϕ. Moreover, by retaining the rooted-tree form from traditional tableaux, our calculus becomes amenable to the vast array of optimisation techniques which have proved essential for “practical” automated reasoning in very expressive description logics. Our calculus forms the basis for developing a uniform framework for the family of all fix-point logics of common knowledge. However, there is still no “free lunch” as, in the worst case, our method exhibits 2EXPTIME-behaviour. A prototype implementation can be found at twb.rsise.anu.edu.au which allows users to test formulae via a simple graphical interface. (shrink)

We use formal semantic analysis based on new constructions to study abstract realizability, introduced by Läuchli in 1970, and expose its algebraic content. We claim realizability so conceived generates semantics-based intuitive confidence that the Heyting Calculus is an appropriate system of deduction for constructive reasoning.Well-known semantic formalisms have been defined by Kripke and Beth, but these have no formal concepts corresponding to constructions, and shed little intuitive light on the meanings of formulae. In particular, the completeness proofs for these (...) semantics do not generate confidence in the sufficiency of the Heyting Calculus, since we have no reason to believe that every intuitively constructive truth is valid in the formal semantics.Läuchli has proved completeness for a realizability semantics with formal concepts analogous to constructions. We argue in some detail that, in spite of a certain inherent inexactness of the analogy, every intuitively constructive truth is valid in Läuchli semantics, and therefore the Heyting Calculus is powerful enough to prove all constructive truths. Our argument is based on the postulate that a uniformly constructible object must be communicable in spite of imprecision in our language, and that the permutations in Läuchli's semantics represent conceivable imprecision in a language, while allowing a certain amount of freedom in choosing the particular structure of the language.We give a detailed generalization of Läuchli's proof of completeness for the propositional part of the Heyting Calculus, in order to make explicit constructive and algebraic content.In our treatment, we establish several new results about Läuchli models. We show how to extend the sconing and gluing constructions familiar from Kripke and Frame semantics and Topos theory, to Läuchli models, and use them to give an algebraic approach to countermodel construction. In particular, the Läuchli arguments are given without the restriction to the integers, Z, as a group of permutations, which makes much of the coding scheme used in Läuchli's original paper transparent.We also make use of a new propositions-as-types syntax for the Heyting calculus, with limited nondeterminism, in which validity of formulae can be decided without loop-detection. (shrink)

In this paper we describe an improvement of Smullyan's analytic tableau method for the propositional calculus-Improved Parent Clash Restricted (IPCR) tableau-and show that it is equivalent to SL-resolution in complexity.

Basic hybrid logic extends modal logic with the possibility of naming worlds by means of a distinguished class of atoms (called nominals) and the so-called satisfaction operator, that allows one to state that a given formula holds at the world named a, for some nominal a. Hence, in particular, hybrid formulae include “equality” assertions, stating that two nominals are distinct names for the same world. The treatment of such nominal equalities in proof systems for hybrid logics may induce many redundancies. (...) This paper introduces an internalized tableau system for basic hybrid logic, significantly reducing such redundancies. The calculus enjoys a strong termination property: tableau construction terminates without relying on any specific rule application strategy, and no loop-checking is needed. The treatment of nominal equalities specific of the proposed calculus is briefly compared to other approaches. Its practical advantages are demonstrated by empirical results obtained by use of implemented systems. Finally, it is briefly shown how to extend the calculus to include the global and converse modalities. (shrink)

In this paper we give relational semantics and an accompanying relational proof theory for full Lambek calculus (a sequent calculus which we denote by FL). We start with the Kripke semantics for FL as discussed in [11] and develop a second Kripke-style semantics, RelKripke semantics, as a bridge to relational semantics. The RelKripke semantics consists of a set with two distinguished elements, two ternary relations and a list of conditions on the relations. It is accompanied by a Kripke-style (...) valuation system analogous to that in [11]. Soundness and completeness theorems with respect to FL hold for RelKripke models. Then, in the spirit of the work of Orlowska [14], [15], and Buszkowski and Orlowska [3], we develop relational logic RFL. The adjective relational is used to emphasize the fact that RFL has a semantics wherein formulas are interpreted as relations. We prove that a sequent Γ → α in FL is provable if and only if a translation, t( $\gamma_1 \bullet \cdots \bullet \gamma_n \supset \alpha)\varepsilon \upsilon u$ , has a cut-complete fundamental proof tree. This result is constructive: that is, if a cut-complete proof tree for $t(\gamma_1 \bullet \cdots \bullet \gamma_n \supset \alpha)\varepsilon \upsilon u$ is not fundamental, we can use the failed proof search to build a relational countermodel for $t(\gamma_1 \bullet \cdots \bullet \gamma_n \supset \alpha)\varepsilon \upsilon u$ and from this, build a RelKripke countermodel for $\gamma_1 \bullet \cdots \bullet \gamma_n \supset \alpha$ . These results allow us to add FL, the basic substructural logic, to the list of those logies of importance in computer science with a relational proof theory. (shrink)

The logical formalism of abductive reasoning is still an open discussion and various theories have been presented about it. Abduction is a type of non-monotonic and defeasible reasonings, and the logic containing such a reasoning is one of the types of non-nonmonotonic and defeasible logics, such as inductive logic. Abduction is a kind of natural reasoning and it is a solution to the problems having this form "the phenomenon of φ cannot be explained by the theory of Θ" and we (...) need to search for (or to adduce) an explanation for φ. Taking α as the explanation and <Θ,φ> as the abductive problem, Θ∪{α}⊨φ is the logical format of a strong abductive reasoning. In this article, the proof theory for first-order abductive calculus is proposed based on Gentzen-type first-order proof theory. Considering its dual, i.e., the semantic tableaux, and without the need to translate the formulas, this calculation is sound and complete. After examining the structural rules of this calculus, some metalogical considerations and open problems such as consistency, completeness and undecidability of this account have been addressed. (shrink)

In this paper we integrate a sorted unification calculus into free variable tableau methods for logics with term declarations. The calculus we define is used to close a tableau at once, unifying a set of equations derived from pairs of potentially complementary literals occurring in its branches. Apart from making the deduction system sound and complete, the calculus is terminating and so, it can be used as a decision procedure. In this sense we have separated the complexity (...) of sorts from the undecidability of first order logic. (shrink)

Angell's logic of analytic containment AC has been shown to be characterized by a 9-valued matrix NC by Ferguson, and by a 16-valued matrix by Fine. We show that the former is the image of a surjective homomorphism from the latter, i.e., an epimorphic image. The epimorphism was found with the help of MUltlog, which also provides a tableau calculus for NC extended by quantifiers that generalize conjunction and disjunction.

Paraconsistent Weak Kleene Logic is the 3-valued propositional logic defined on the weak Kleene tables and with two designated values. Most of the existing proof systems for PWK are characterised by the presence of linguistic restrictions on some of their rules. This feature can be seen as a shortcoming. We provide a cut-free calculus for PWK that is devoid of such provisos. Moreover, we introduce a Priest-style tableaux calculus for PWK.

The proof theory of many-valued systems has not been investigated to an extent comparable to the work done on axiomatizatbility of many-valued logics. Proof theory requires appropriate formalisms, such as sequent calculus, natural deduction, and tableaux for classical (and intuitionistic) logic. One particular method for systematically obtaining calculi for all finite-valued logics was invented independently by several researchers, with slight variations in design and presentation. The main aim of this report is to develop the proof theory of finite-valued (...) first order logics in a general way, and to present some of the more important results in this area. In Systems covered are the resolution calculus, sequent calculus, tableaux, and natural deduction. This report is actually a template, from which all results can be specialized to particular logics. (shrink)

We discuss two-layered logics formalising reasoning with paraconsistent probabilities that combine the Łukasiewicz [0, 1]-valued logic with Baaz ▵\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\triangle $$\end{document} operator and the Belnap–Dunn logic. The first logic (introduced in [7]) formalises a ‘two-valued’ approach where each event ϕ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi $$\end{document} has independent positive and negative measures that stand for, respectively, the likelihoods of ϕ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi (...) $$\end{document} and ¬ϕ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lnot \phi $$\end{document}. The second logic that we introduce here corresponds to ‘four-valued’ probabilities. There, ϕ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi $$\end{document} is equipped with four measures standing for pure belief, pure disbelief, conflict and uncertainty of an agent in ϕ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi $$\end{document}.We construct faithful embeddings of and into one another and axiomatise using a Hilbert-style calculus. We also establish the decidability of both logics and provide complexity evaluations for them using an expansion of the constraint tableaux calculus for. (shrink)

In a preceding paper [1] it was shown that quantum logic, given by the tableaux-calculus Teff, is complete and consistent with respect to the dialogic foundation of logics. Since in formal dialogs the special property of the 'value-definiteness' of propositions is not postulated, the calculus $T_{eff}$ represents a calculus of effective (intuitionistic) quantum logic. Beginning with the tableaux-calculus the equivalence of $T_{eff}$ to calculi which use more familiar figures such as sequents and implications can (...) be investigated. In this paper we present a sequents-calculus of Gentzen-type and a propositional calculus of Brouwer-type which are shown to be equivalent to $T_{eff}$ . The effective propositional calculus provides an interpretation for a lattice structure, called quasi-implicative lattice. If, in addition, the value-definiteness of quantum mechanical propositions is postulated, a propositional calculus is obtained which provides an interpretation for a quasi-modular orthocomplemented lattice which, as is well-known, has as a model the lattice of subspaces of a Hilbert space. (shrink)

Since Plaza [1989], which is most of the time considered as the inaugural paper on announcement logics in public communication contexts, a lot of papers on dynamic epistemic logics have been published. The most famous dynamic epistemic logic is known by the name of PAL (Public Announcement Logic). The logic PAC is an extension of PAL with the common knowledge operator (CG). Soundness and completeness proofs of those logics are presented in van Ditmarsch et al. [2008], in Balbiani et al. (...) [2010] and in de Boer [2007]. Each of them used either a model-theoretic approach or a tableaux calculus. In the present paper, we propose an alternative approach to PAC based on the dialogical framework. (shrink)

In the late forties, Stanisław Jaśkowski published two papers onthe discursive sentential calculus, D2. He provided a definition of it by an interpretation in the language of S5 of Lewis. The knownaxiomatization of D2 with discursive connectives as primitives was introduced by da Costa, Dubikajtis and Kotas in 1977. It turns out, however,that one of the axioms they used is not a thesis of the real Jaśkowski’s calculus. In fact, they built a new system, D∗2 for short, that (...) differs from D2 inmany respects. The aim of this paper is to introduce a direct Kripke-type semantics for the system, axiomatize it in a new way and prove soundness andcompleteness theorems. Additionally, we present labelled tableaux for D∗2.1. (shrink)

In their recent paper Bi-facial truth: a case for generalized truth values Zaitsev and Shramko [7] distinguish between an ontological and an epistemic interpretation of classical truth values. By taking the Cartesian product of the two disjoint sets of values thus obtained, they arrive at four generalized truth values and consider two “semi-classical negations” on them. The resulting semantics is used to define three novel logics which are closely related to Belnap’s well-known four valued logic. A syntactic characterization of these (...) logics is left for further work. In this paper, based on our previous work on a functionally complete extension of Belnap’s logic, we present a sound and complete tableau calculus for these logics. It crucially exploits the Cartesian nature of the four values, which is reflected in the fact that each proof consists of two tableaux. The bi-facial notion of truth of Z&S is thus augmented with a bi-facial notion of proof. We also provide translations between the logics for semi-classical negation and classical logic and show that an argument is valid in a logic for semi-classical negation just in case its translation is valid in classical logic. (shrink)

This introduction to mathematical logic starts with propositional calculus and first-order logic. Topics covered include syntax, semantics, soundness, completeness, independence, normal forms, vertical paths through negation normal formulas, compactness, Smullyan's Unifying Principle, natural deduction, cut-elimination, semantic tableaux, Skolemization, Herbrand's Theorem, unification, duality, interpolation, and definability. The last three chapters of the book provide an introduction to type theory (higher-order logic). It is shown how various mathematical concepts can be formalized in this very expressive formal language. This expressive notation (...) facilitates proofs of the classical incompleteness and undecidability theorems which are very elegant and easy to understand. The discussion of semantics makes clear the important distinction between standard and nonstandard models which is so important in understanding puzzling phenomena such as the incompleteness theorems and Skolem's Paradox about countable models of set theory. Some of the numerous exercises require giving formal proofs. A computer program called ETPS which is available from the web facilitates doing and checking such exercises. Audience: This volume will be of interest to mathematicians, computer scientists, and philosophers in universities, as well as to computer scientists in industry who wish to use higher-order logic for hardware and software specification and verification. (shrink)

We present a syntactical cut-elimination proof for an extended sequent calculus covering the classical modal logics in the \(\mathsf{K}\), \(\mathsf{D}\), \(\mathsf{T}\), \(\mathsf{K4}\), \(\mathsf{D4}\) and \(\mathsf{S4}\) spectrum. We design the systems uniformly since they all share the same set of rules. Different logics are obtained by “tuning” a single parameter, namely a constraint on the applicability of the cut rule and on the (left and right, respectively) rules for \(\Box\) and \(\Diamond\). Starting points for this research are 2-sequents and indexed-based (...) calculi (sequents and tableaux). By extending and modifying existing proposals, we show how to achieve a syntactical proof of the cut-elimination theorem that is as close as possible to the one for first-order classical logic. In doing this, we implicitly show how small is the proof-theoretical distance between classical logic and the systems under consideration. (shrink)

Four-valued semantics proved useful in many contexts from relevance logics to reasoning about computers. We extend this approach further. A sequent calculus is defined with logical connectives conjunction and disjunction that do not distribute over each other. We give a sound and complete semantics for this system and formulate the same logic as a tableaux system. Intensional conjunction and its residuals can be added to the sequent calculus straightforwardly. We extend a simplified version of the earlier semantics (...) for this system and prove soundness and completeness. Then, with some modifications to this semantics, we arrive at a mathematically elegant yet powerful semantics that we call generalized Kripke semantics. (shrink)

Our aim is to express in exact terms the old idea of solving problems by pure questioning. We consider the problem of derivability: "Is A derivable from Δ by classical propositional logic?". We develop a calculus of questions E*; a proof (called a Socratic proof) is a sequence of questions ending with a question whose affirmative answer is, in a sense, evident. The calculus is sound and complete with respect to classical propositional logic. A Socratic proof in E* (...) can be transformed into a Gentzen-style proof in some sequent calculi. Next we develop a calculus of questions E**; Socratic proofs in E** can be transformed into analytic tableaux. We show that Socratic proofs can be grounded in Inferential Erotetic Logic. After a slight modification, the analyzed systems can also be viewed as hypersequent calculi. (shrink)

In this paper we explore a generalization of traditional abduction which can simultaneously perform two different tasks: given an unprovable sequent Γ ⊢ G, find a sentence H such that Γ, H ⊢ G is provable ; given a provable sequent Γ ⊢ G, find a sentence H such that Γ ⊢ H and the proof of Γ, H ⊢ G is simpler than the proof of Γ ⊢ G . We argue that the two tasks should not be distinguished, (...) and present a general procedure for finding suitable hypotheses or lemmas. When the original sequent is provable, the abduced formula can be seen as a cut formula with respect to Gentzen's sequent calculus, so the abduction method is cut-based. Our method is based on the tableau-like system KE and we argue for its advantages over existing abduction methods based on traditional Smullyan-style Tableaux. (shrink)

Mathematical Logic for Computer Science is a mathematics textbook with theorems and proofs, but the choice of topics has been guided by the needs of computer science students. The method of semantic tableaux provides an elegant way to teach logic that is both theoretically sound and yet sufficiently elementary for undergraduates. To provide a balanced treatment of logic, tableaux are related to deductive proof systems.The logical systems presented are:- Propositional calculus (including binary decision diagrams);- Predicate calculus;- (...) Resolution;- Hoare logic;- Z;- Temporal logic.Answers to exercises (for instructors only) as well as Prolog source code for algorithms may be found via the Springer London web site: http://www.springer.com/978-1-85233-319-5 Mordechai Ben-Ari is an associate professor in the Department of Science Teaching of the Weizmann Institute of Science. He is the author of numerous textbooks on concurrency, programming languages and logic, and has developed software tools for teaching concurrency. In 2004, Ben-Ari received the ACM/SIGCSE Award for Outstanding Contributions to Computer Science Education. (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)

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)

This work studies some problems connected to the role of negation in logic, treating the positive fragments of propositional calculus in order to deal with two main questions: the proof of the completeness theorems in systems lacking negation, and the puzzle raised by positive paradoxes like the well-known argument of Haskel Curry. We study the constructive com- pleteness method proposed by Leon Henkin for classical fragments endowed with implication, and advance some reasons explaining what makes difficult to extend this (...) constructive method to non-classical fragments equipped with weaker implications (that avoid Curry's objection). This is the case, for example, of Jan Lukasiewicz's n-valued logics and Wilhelm Ackermann's logic of restricted implication. Besides such problems, both Henkin's method and the triviality phenomenon enable us to propose a new positive tableau proof system which uses only positive meta-linguistic resources, and to mo- tivate a new discussion concerning the role of negation in logic proposing the concept of paratriviality. In this way, some relations between positive reasoning and infinity, the possibilities to obtain a ¯first-order positive logic as well as the philosophical connection between truth and meaning are dis- cussed from a conceptual point of view. (shrink)

We prove that the intuitionistic sentential calculus is Ł-decidable, i.e. the sets of these of Int and of rejected formulas are disjoint and their union is equal to all formulas. A formula is rejected iff it is a sentential variable or is obtained from other formulas by means of three rejection rules. One of the rules is original, the remaining two are Łukasiewicz's rejection rules: by detachement and by substitution. We extensively use the method of Beth's semantic tableaux.

We present a semantic game for Gödel logic and its extensions, where the players’ interaction stepwise reduces arbitrary claims about the relative order of truth degrees of complex formulas to atomic ones. The paper builds on a previously developed game for Gödel logic with projection operator in Fermüller et al., Information processing and management of uncertainty in knowledge-based systems, Springer, Cham, 2020, pp. 257–270). This game is extended to cover Gödel logic with involutive negations and constants, and then lifted to (...) a provability game using the concept of disjunctive strategies. Winning strategies in the provability game, with and without constants and involutive negations, turn out to correspond to analytic proofs in a version of \ :1941–1958, 2010) and in a sequent-of-relations calculus, Automated reasoning with analytic tableaux and related methods, Springer, Berlin, 1999, pp. 36–51) respectively. (shrink)

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 [email protected]. Have fun! (shrink)

This papers presents δ-resolution, a dual resolution calculus. It is based on standard resolution, and used appropriate formulae equivalent to disjunctive normal forms, instead of conjunctive normal ones, as it is the case for resolution. This duality is then useful to create a calculus for abductive process, as a way to construct a set of abductive solutions. The proposed calculus is compared to semantic tableaux, an standard logical framework, aslo illuminating when studying abduction.δ-resolution calculus is (...) a contribution to logic programming, and it further suggests new possibilities to explore abduction at a first order level, in the lines of those proposed in [9]. (shrink)

This interesting collection is the Festschrift presented to W. Britzelmayr on his seventieth birthday, and it contains several excellent papers which ought to interest the logician and philosophical analyst alike. The most exciting paper is one by Stegmüller in which a system of set theory combining ideas from Bernays and Quine is formulated; one by Kurt Schütte discusses the limitations imposed by constructive logic on the theory of trans finite arithmetic; there are papers by each of the editors: the first (...) analyzes the deduction theorem for the first order predicate calculus, while the second treats logics with predicate quantifiers. Other papers include studies by Behmann on the philosophico-logical status of identity; by Beth on the application of his semantic tableaux to classical logic; by Wilhelmy on the semantics of quantified, many-valued logics; and by E. M. Fels concerning the work of Markov and his school in the theory of canonical systems. There are still further papers which take as their topics the logical analysis of legal concepts and reasoning, the logic of questions, the semantics of implication in ordinary language, and the relation of the theory of logical types to Frege's work. In general, this is an excellent collection which affords a wide view of the logico-linguistic concerns of recent German philosophy.—P. J. M. (shrink)

Dopp is one of the very few logicians writing in French today, and so there are few textbooks of logic in that language. This is the newest one, and it is concerned essentially with the propositional and first-order predicate calculi, from both their historical as well as contemporary aspects. After examining the concepts of classical logic, Dopp presents the propositional calculus as a calculus of truth-functions and then gives it an axiomatic underpinning. In the treatment of quantification, first (...) traditional logic is presented, and then modern first-order logic with identity is examined in some detail, with attention to the technique of semantic tableaux. An appendix provides a number of alternative systems of the propositional calculus in axiomatic form.—P. J. M. (shrink)

We present relational proof systems for the four groups of theories of spatial reasoning: contact relation algebras, Boolean algebras with a contact relation, lattice-based spatial theories, spatial theories based on a proximity relation.

This paper presents a sequent calculus and a dual domain semantics for a theory of definite descriptions in which these expressions are formalised in the context of complete sentences by a binary quantifier I. I forms a formula from two formulas. Ix[F, G] means ‘The F is G’. This approach has the advantage of incorporating scope distinctions directly into the notation. Cut elimination is proved for a system of classical positive free logic with I and it is shown to (...) be sound and complete for the semantics. The system has a number of novel features and is briefly compared to the usual approach of formalising ‘the F ’ by a term forming operator. It does not coincide with Hintikka’s and Lambert’s preferred theories, but the divergence is well-motivated and attractive. (shrink)

This is a remarkable new French language introduction to elementary logical methods. Although designed primarily for computer and information specialists, it is also sure to interest philosophers and logicians because of its diversity of subjects, emphasis on graphic calculation techniques, and extensive historical background. The book is intelligently divided into nine main chapters with detailed descriptive subsections. It begins with the most fundamental principles of Aristotelian syllogistic and Boolean algebra, working through the essentials of Frege's predicate calculus and Gödel's (...) consistency-completeness metaproofs before systematically articulating standard propositional and predicate logics, interestingly, from synthetic and then analytic perspectives. This leads to a largely informal exposition of Tarski-style model set theoretical semantics, and the modern limiting metatheoretical results underlying what the authors call the "crisis" in the foundations of mathematical logic. Here are included such typical and more unusual topics as Herbrand models, König's Lemma, Herbrand's Theorem, Post machines, Floyd's Theorem, and Church's Theorem. The volume culminates in an expansive treatment of first order theories, including theories of order and models, and decidability. The exposition is somewhat rigorous, but should not be excessively demanding for nonprofessionals interested in the important implications of logic for philosophy, foundations of mathematics, and informatique. Among the book's virtues must be mentioned its profuse illustration of so many different graphic methods in mathematical logic, including Venn diagrams, the square of opposition, Smullyan truth trees, Wallen's reduction technique, Beth's and Hintikka's semantic tableaux method, and several styles of axiomatic and natural deduction. The work is certain to be a valuable resource for French readers in need of a lucid, comprehensive guide to the history and practical techniques of logic in its elementary applications to the philosophy of mathematics and information sciences.--Dale Jacquette, The Pennsylvania State University. (shrink)

In this paper we present tableau methods for two-dimensional modal logics. Although models for such logics are well known, proof systems remain rather unexplored as most of their developments have been purely axiomatic. The logics herein considered contain first-order quantifiers with identity, and all the formulas in the language are doubly-indexed in the proof systems, with the upper indices intuitively representing the actual or reference worlds, and the lower indices representing worlds of evaluation—first and second dimensions, respectively. The tableaux (...) modulate over different notions of validity such as local, general, and diagonal, besides being general enough for several two-dimensional logics proposed in the literature. We also motivate the introduction of a new operator into two-dimensional languages and explore some of the philosophical questions raised by it concerning the relations there are between actuality, necessity, and the a priori, that seem to undermine traditional intuitive interpretations of two-dimensional operators. (shrink)