This paper contributes to the principled construction of tableau-based decision procedures for hybrid logic with global, difference, and converse modalities. We also consider reflexive and transitive relations. For converse-free formulas we present a terminating control that does not rely on the usual chain-based blocking scheme. Our tableau systems are based on a new model existence theorem.

Labelled tableau systems are developed for subintuitionistic logics \, \ and \. These subintuitionistic logics are embedded into corresponding normal modal logics. Hintikka’s model systems are applied to prove the completeness of labelled tableau systems. The finite model property, decidability and disjunction property are obtained by labelled tableau method.

Most of this work is devoted to presenting aspects of proof theory that have developed out of Gentzen's work. Thus the them is "cut elimination" and transfinite induction over constructive ordinals. Smullyan's tableau systems will be used for the formalisms and some of the basic logical results as presented in Smullyan [1] will be assumed to be known (essentially only the classical completeness and consistency proofs for propositional and first order logic).

We introduce a family of tableau calculi for deontic action logics based on finite boolean algebras, these logics provide deontic operators which are applied to a finite number of actions ; furthermore, in these formalisms, actions can be combined by means of boolean operators, this provides an expressive algebra of actions. We define a tableau calculus for the basic logic and then we extend this calculus to cope with extant variations of this formalism; we prove the soundness and (...) completeness of these proof systems. In addition, we investigate the computational complexity of the satisfiability problem for DAL and its extensions; we show this problem is NP-complete when the number of actions considered is fixed, and it is \-Hard when the number of actions is taken as an extra parameter. The tableau systems introduced here can be implemented in PSPACE, this seems reasonable taking into consideration the computational complexity of the logics. (shrink)

In this paper a first-order version of hybrid logic is presented. The language is obtained by adding nominals, satisfaction operators and the down-arrow binder to classical first-order modal logic. The satisfaction operators are applied to both formulas and terms. Moreover adding the universal modality is discussed. This first-order hybrid language is interpreted over varying domains and a sound and complete, fully internalized tableau system for this logic is given.

We give complete sequent-like tableau systems for the modal logics KB, KDB, K5, and KD5. Analytic cut rules are used to obtain the completeness. Our systems have the analytic superformula property and can thus give a decision procedure. Using the systems, we prove the Craig interpolation lemma for the mentioned logics.

The goal of the article is twofold. The first one is to provide logics based on positional semantics which will be suitable for the analysis of epistemic modalities such as ‘agent... knows/beliefs that...’. The second one is to define tableau systemsfor such logics. Firstly, we present the minimal positional logic MR. Then, we change the notion of formulas and semantics in order to consider iterations of the operator of realization and “free” classical formulas. After that, we move on to (...) weaker logics in order to avoid the well known problem of logical omniscience. At the same time, we keep the positional counterparts of modal axioms, and. For all of the considered logics we present sound and complete tableau systems. (shrink)

Logic has its roots in the study of valid argument, but while traditional logicians worked with natural language directly, modern approaches first translate natural arguments into an artificial language. The reason for this step is that some artificial languages now have very well developed inferential systems. There is no doubt that this is a great advantage in general, but for the study of natural reasoning it is a drawback that the original linguistic forms get lost in translation. An alternative approach (...) would be to develop a general theory of the natural logic behind human reasoning and human information processing by studying formal logics that operate directly on linguistic representations. That this is possible we will try to make plausible in this paper. It will turn out that one level of representation, that of Logical Form, can meaningfully be identified with the language of an existing and well-understood logic, a restricted form of the theory of types. It is not difficult to devise inference systems for this language, and it is thus possible to study reasoning systems that are based directly on language. (shrink)

In 1953, Jerzy Kalinowski published his paper on the logic of normative sentences. The paper is recognized as one of the first publications on the formal system of deontic logic. The aim of this paper is to present a tableau system for Kalinowski’s deontic logic and to discuss some of the topics related to the paradoxes of deontic logic.

We present sound, (weakly) complete and cut-free tableau systems for the propositional normal modal logicsS4.3, S4.3.1 andS4.14. When the modality is given a temporal interpretation, these logics respectively model time as a linear dense sequence of points; as a linear discrete sequence of points; and as a branching tree where each branch is a linear discrete sequence of points.Although cut-free, the last two systems do not possess the subformula property. But for any given finite set of formulaeX the superformulae (...) involved are always bounded by a finite set of formulaeX* L depending only onX and the logicL. Thus each system gives a nondeterministic decision procedure for the logic in question. The completeness proofs yield deterministic decision procedures for each logic because each proof is constructive. (shrink)

By a pure modal logic of names we mean a quantifier-free formulation of such a logic which includes not only traditional categorical, but also modal categorical sentences with modalities de re and which is an extension of Propositional Logic. For categorical sentences we use two interpretations: a “natural” one; and Johnson and Thomason’s interpretation, which is suitable for some reconstructions of Aristotelian modal syllogistic :271–284, 1989; Thomason in J Philos Logic 22:111–128, 1993 and J Philos Logic 26:129–141, 1997. In both (...) cases we use Johnson-like models. We also analyze different kinds of versions of PMLN, for both general and singular names. We present complete tableau systems for the different versions of PMLN. These systems enable us to present some decidability methods. It yields “strong decidability” in the following sense: for every inference starting with a finite set of premises we can specify a finite number of steps to check whether it is logically valid. This method gives the upper bound of the cardinality of models needed for the examination of the validity of a given inference. (shrink)

The main technical errors are in the literature survey. On pages 44, 93-94, 131 and 133 I claim that Fitting's and/or Rautenberg's systems are incomplete because they omit contraction. The claim is wrong because contraction is implicit in their set notation. Their systems are complete because they allow contraction on any formula whereas the systems in this technical report explicitly build contraction into certain rules, allowing contraction only on certain types of formulae. Please accept my apologies for any confusion this (...) causes you. (shrink)

In Symbolic Logic (1932), C. I. Lewis developed five modal systems S1 − S5. S4 and S5 are so-called normal modal systems. Since Lewis and Langford’s pioneering work many other systems of this kind have been investigated, among them the 32 systems that can be generated by the five axioms T, D, B, 4 and 5. Lewis also discusses how his systems can be augmented by propositional quantifiers and how these augmented logics allow us to express some interesting ideas that (...) cannot be expressed in the corresponding quantifier-free logics. In this paper, I will develop 64 normal modal semantic tableau systems that can be extended by propositional quantifiers yielding 64 extended systems. All in all, we will investigate 128 different systems. I will show how these systems can be used to prove some interesting theorems and I will discuss Lewis’s so-called existence postulate and some of its consequences. Finally, I will prove that all normal modal systems are sound and complete and that all systems (including the extended systems) are sound with respect to their semantics. It is left as an open question whether or not the extended systems are complete. (shrink)

We formulate a Hilbert-style axiomatic system and a tableau calculus for the STIT-based logic of imagination recently proposed in Wansing. Completeness of the axiom system is shown by the method of canonical models; completeness of the tableau system is also shown by using standard methods.

In order to modelize the reasoning of intelligent agents represented by a poset T, H. Rasiowa introduced logic systems called “Approximation Logics”. In these systems a set of constants constitutes a fundamental tool. In this paper, we consider logic systems called L'T without this kind of constants but limited to the case where T is a finite poset. We study the tableau method for this system and we prove its completeness for a class of formulas with respect to (...) an algebraic semantics. (shrink)

Peirce’s triadic logic has been under discussion since its discovery in the 1960s by Fisch and Turquette. The experiments with matrices of three-valued logic are recorded in a few pages of unpublished manuscripts dated 1909, a decade before similar systems have been developed by logicians. The purposes of Peirce’s work on such logic, as well as semantical aspects of his system, are disputable. In the most extensive work about it, Turquette suggested that the matrices are related in dual pairs (...) of axiomatic Hilbert-style systems. In this paper, we present a simple tableau proof for a fragment of Peirce three-valued logic, called P3, based on similar approaches in many-valued literature. We demonstrated that this proof is sound and complete. Besides that, taking the false as the only undesignated value and adding non-classical negations to the calculus, we can explore paraconsistent and paracompleteness theories into P3. Keywords: Charles S. Peirce, many-valued logics, theory of proof, tableau method. (shrink)

Even though it is not very often admitted, partial functions do play a significant role in many practical applications of deduction systems. Kleene has already given a semantic account of partial functions using a three-valued logic decades ago, but there has not been a satisfactory mechanization. Recent years have seen a thorough investigation of the framework of many-valued truth-functional logics. However, strong Kleene logic, where quantification is restricted and therefore not truthfunctional, does not fit the framework directly. We solve this (...) problem by applying recent methods from sorted logics. This paper presents a tableau calculus that combines the proper treatment of partial functions with the efficiency of sorted calculi. (shrink)

We present a dual tableau system, RLK, which is itself a deterministic decision procedure verifying validity of K-formulas. The system is constructed in the framework of the original methodology of relational proof systems, determined only by axioms and inference rules, without any external techniques. Furthermore, we describe an implementation of the system in Prolog, and we show some of its advantages.

Monoidal triangular norm logic MTL is the logic of left-continuous triangular norms. In the paper we present a relational formalization of the logic MTL and then we introduce relational dual tableau that can be used for verification of validity of MTL-formulas. We prove soundness and completeness of the system.

We present a dual tableau system, RLK, which is itself a deterministic decision procedure verifying validity of K-formulas. The system is constructed in the framework of the original methodology of relational proof systems, determined only by axioms and inference rules, without any external techniques. Furthermore, we describe an implementation of the system RLK in Prolog, and we show some of its advantages.

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

Description logics are a family of knowledge representation formalisms that are descended from semantic networks and frames via the system Kl-one. During the last decade, it has been shown that the important reasoning problems (like subsumption and satisfiability) in a great variety of description logics can be decided using tableau-like algorithms. This is not very surprising since description logics have turned out to be closely related to propositional modal logics and logics of programs (such as propositional dynamic logic), (...) for which tableau procedures have been quite successful.Nevertheless, due to different underlying institutions and applications, most description logics differ significantly from run-of-the-mill modal and program logics. Consequently, the research on tableau algorithms in description logics led to new techniques and results, which are, however, also of interest for modal logicians. In this article, we will focus on three features that play an important rôle in description logics (number restrictions, terminological axioms, and role constructors), and show how they can be taken into account by tableau algorithms. (shrink)

We present a relational proof system in the style of dual tableaux for the relational logic associated with a multimodal propositional logic for order of magnitude qualitative reasoning with a bidirectional relation of negligibility. We study soundness and completeness of the proof system and we show how it can be used for verification of validity of formulas of the logic.

While symbolic colour use has always played a conspicuous role in science research and education, the use of colour in historic diagrams remains a lacuna in the history of science. Investigating the colour use in diagrams often means uncovering a whole cosmology that is not otherwise explicit in the diagram itself. The periodic table is a salient and iconic example of non-mimetic colour use in science. Andreas von Antropoff's (1924) rectangular table of recurrent rainbow colours is famous, as are Alcindo (...) Flores Cabral's (1949) application of colour in his round snail form, using the RGB scheme, and Mazurs's (1967) pine tree system, consisting of warm and cold colours that he attributed to specific groups of elements—an attribution that we can relate back to humoralism and alchemy. From the first periodic tables in the 19th century, individual researchers have used different colour regimes. While standardization may play an obvious role in chemistry and its diagrams, all the more impressive is the anarchistic use of colour in the various diagrams which continue to be created. This article focuses on periodic tables in chemical journals and text books, and explores and compares the development of colour codes found in the few existing polychrome diagrams from the 1920s to the 1970s. (shrink)

Ecumenical logic aims to peacefully join classical and intuitionistic logic systems, allowing for reasoning about both classical and intuitionistic statements. This paper presents a semantic tableau for propositional ecumenical logic and proves its soundness and completeness concerning Ecumenical Kripke models. We introduce the Ecumenical Propositional Tableau ( $$E_T$$ ) and demonstrate its effectiveness in handling mixed statements.

In this paper we provide cut-free tableau calculi for the intuitionistic modal logics IK, ID, IT, i.e. the intuitionistic analogues of the classical modal systems K, D and T. Further, we analyse the necessity of duplicating formulas to which rules are applied. In order to develop these calculi we extend to the modal case some ideas presented by Miglioli, Moscato and Ornaghi for intuitionistic logic. Specifically, we enlarge the language with the new signs Fc and CR near to the (...) usual signs T and F. In this work we establish the soundness and completeness theorems for these calculi with respect to the Kripke semantics proposed by Fischer Servi. (shrink)

This paper introduces Basic Intuitionistic Set Theory BIST, and investigates it as a first-order set theory extending the internal logic of elementary toposes. Given an elementary topos, together with the extra structure of a directed structural system of inclusions on the topos, a forcing-style interpretation of the language of first-order set theory in the topos is given, which conservatively extends the internal logic of the topos. This forcing interpretation applies to an arbitrary elementary topos, since any such is equivalent (...) to one carrying a dssi. We prove that the set theory BIST+Coll is sound and complete relative to forcing interpretations in toposes with natural numbers object . Furthermore, in the case that the structural system of inclusions is superdirected, the full Separation schema is modelled. We show that all cocomplete and realizability toposes can be endowed with such superdirected systems of inclusions.A large part of the paper is devoted to an alternative notion of category-theoretic model for BIST, which, following the general approach of Joyal and Moerdijkʼs Algebraic Set Theory, axiomatizes the structure possessed by categories of classes compatible with BIST. We prove soundness and completeness results for BIST relative to the class-category semantics. Furthermore, BIST+Coll is complete relative to the restricted collection of categories of classes given by categories of ideals over elementary toposes with nno and dssi. It is via this result that the completeness of the original forcing interpretation is obtained, since the internal logic of categories of ideals coincides with the forcing interpretation. (shrink)

This paper introduces Basic Intuitionistic Set Theory BIST, and investigates it as a first-order set theory extending the internal logic of elementary toposes. Given an elementary topos, together with the extra structure of a directed structural system of inclusions on the topos, a forcing-style interpretation of the language of first-order set theory in the topos is given, which conservatively extends the internal logic of the topos. This forcing interpretation applies to an arbitrary elementary topos, since any such is equivalent (...) to one carrying a dssi. We prove that the set theory BIST+Coll is sound and complete relative to forcing interpretations in toposes with natural numbers object. Furthermore, in the case that the structural system of inclusions is superdirected, the full Separation schema is modelled. We show that all cocomplete and realizability toposes can be endowed with such superdirected systems of inclusions.A large part of the paper is devoted to an alternative notion of category-theoretic model for BIST, which, following the general approach of Joyal and Moerdijkʼs Algebraic Set Theory, axiomatizes the structure possessed by categories of classes compatible with BIST. We prove soundness and completeness results for BIST relative to the class-category semantics. Furthermore, BIST+Coll is complete relative to the restricted collection of categories of classes given by categories of ideals over elementary toposes with nno and dssi. It is via this result that the completeness of the original forcing interpretation is obtained, since the internal logic of categories of ideals coincides with the forcing interpretation. (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)

Standard deontic logic (SDL) is defined on the basis of possible world semantics and is a logic of alethic-deontic modalities rather than deontic modalities alone. The interpretation of the concepts of obligation and permission comes down exclusively to the logical value that a sentence adopts for the accessible deontic alternatives. Here, we set forth a different approach, this being a logic which additionally takes into consideration whether sentences stand in relation to the normative system or to the system (...) of values under which we predicate the deontic qualifications. By taking this aspect into account, we arrive at a logical system which preserves laws proper to a deontic logic but where the standard paradoxes of deontic logic do not arise. It is a logic of strictly-deontic modalities DR. (shrink)

The Tableaux Work Bench (TWB) is a meta tableau system designed for logicians with limited programming or automatic reasoning knowledge to experiment with new tableau calculi and new decision procedures. It has a simple interface, a history mechanism for controlling loops or pruning the search space, and modal simplification.

This book stands at the intersection of two topics: the decidability and computational complexity of hybrid logics, and the deductive systems designed for them. Hybrid logics are here divided into two groups: standard hybrid logics involving nominals as expressions of a separate sort, and non-standard hybrid logics, which do not involve nominals but whose expressive power matches the expressive power of binder-free standard hybrid logics.The original results of this book are split into two parts. This division reflects the division of (...) the book itself. The first type of results concern model-theoretic and complexity properties of hybrid logics. Since hybrid logics which we call standard are quite well investigated, the efforts focused on hybrid logics referred to as non-standard in this book. Non-standard hybrid logics are understood as modal logics with global counting operators ) whose expressive power matches the expressive power of binder-free standard hybrid logics. The relevant results comprise: 1. Establishing a sound and complete axiomatization for the modal logic K with global counting operators ), which can be easily extended onto other frame classes, 2. Establishing tight complexity bounds, namely NExpTime-completeness for the modal logic with global counting operators defined over the classes of arbitrary, reflexive, symmetric, serial and transitive frames ), MT), MD), MB), MK4) with numerical subscripts coded in binary. Establishing the exponential-size model property for this logic defined over the classes of Euclidean and equivalential frames ), MS5).Results of the second type consist of designing concrete deductive systems for standard and non-standard hybrid logics. More precisely, they include: 1. Devising a prefixed and an internalized tableau calculi which are sound, complete and terminating for a rich class of binder-free standard hybrid logics. An interesting feature of indicated calculi is the nonbranching character of the rule, 2. Devising a prefixed and an internalized tableau calculi which are sound, complete and terminating for non-standard hybrid logics. The internalization technique applied to a tableau calculus for the modal logic with global counting operators is novel in the literature, 3. Devising the first hybrid algorithm involving an inequality solver for modal logics with global counting operators. Transferring the arithmetical part of reasoning to an inequality solver turned out to be sufficient in ensuring termination.The book is directed to philosophers and logicians working with modal and hybrid logics, as well as to computer scientists interested in deductive systems and decision procedures for logics. Extensive fragments of the first part of the book can also serve as an introduction to hybrid logics for wider audience interested in logic.The content of the book is situated in the areas of formal logic and theoretical computer science with some elements of the theory of computational complexity. (shrink)

The paper is devoted to the concise description of some Natural Deduction System (ND for short) for Linear Temporal Logic. The system's distinctive feature is that it is labelled and analytical. Labels convey necessary semantic information connected with the rules for temporal functors while the analytical character of the rules lets the system work as a decision procedure. It makes it more similar to Labelled Tableau Systems than to standard Natural Deduction. In fact, our solution of (...) linearity representation is rather independent of the underlying proof method, provided that some form of (analytic) cut is admissible. We will also discuss some generalisations of the system and compare it with other formalizations of linearity. (shrink)

This paper is about non-labelled proof-systems for hybrid logic, that is, proofsystems where arbitrary formulas can occur, not just satisfaction statements. We give an overview of such proof-systems, focusing on analytic systems: Natural deduction systems, Gentzen sequent systems and tableau systems. We point out major results and we discuss a couple of striking facts, in particular that nonlabelled hybrid-logical natural deduction systems are analytic, but this is not proved in the usual way via step-by-step normalization of derivations.

Philosophe structural tout autant qu’historien structural de la philosophie, Jules Vuillemin fonde la classification des systèmes philosophiques sur une structure jumelle : la classification des formes de prédication. Essayant d’appliquer à l’œuvre de Vuillemin la méthode qu’il appliquait à ses objets d’étude, nous montrons que la structure de ces deux classifications peut être déduite de la combinaison de trois critères : le caractère intelligible ou sensible de l’objet, le caractère a priori ou a posteriori de la connaissance et le caractère (...) objectif ou subjectif de l’état de choses décrit. La classification peut ainsi être décrite comme un tableau cubique contenant cinq systèmes cohérents et trois systèmes contradictoires. (shrink)