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

In this 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)

We offer tableaux systems for logics of essence and accident and logics of non-contingency, showing their soundness and completeness for Kripke semantics. We also show an interesting parallel between these logics based on the semantic insensitivity of the two non-normal operators by which these logics are expressed.

The tableaux-constructions have a number of properties which advantageously distinguish them from equivalent axiomatic systems . The proofs in the form of tableaux-constructions have a full accordance with semantic interpretation and subformula property in the sense of Gentzen’s Hauptsatz. Method of tatleaux-construction gives a good substitute of Gentzen’s methods and thus opens a good perspective for the investigations of theoretical as well as applied aspects of logical calculi. It should be noted that application of tableau method in modal, (...) tense, relevant and other non-classical logics is connected with serious difficulties. Tableaux variants are constructed only for a few normal modal systems. As to relevant and paraconsistent logic, the absence of its tableau variants may be considered as a question of special interest. We shall formulate the tableaux for propositional modal system S4.1, S4.2, S4.3, S4.4 and relevant R∗ and E ∗ using Beth’s tableaux construction with indexed formulas. (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.

In this work, we shall study structural abduction and how ways of searching for solutions to the corresponding abductive problems could be modeled. Specifically, we shall define modal semantic tableaux for normal modal systems and study its applications to structural abduction. This method even makes structural abduction clearer and, as it shall be seen, when a radical change of logic is epistemologically required, the corresponding tableau will have pertinent information to suggest it.

In the paper, we examine tableau systems for R. Epstein’s logics of content relationship: D (Dependence Logic), DD (Dual Dependence Logic), Eq (Logic of Equality of Content), S (Symmetric Relatedness Logic) and R (Nonsymmetric Relatedness Logic) (cf. Epstein in Philos Stud 36:137–173, 1979, Epstein in Rep. Math. Logic 21:19–34, 1987, Klonowski in Logic Log Philos 30(4):579–629, 2021, Krajewski in J Non Class Logic 8:7–33, 1991). The first tableau systems for those logics were defined by Carnielli. However, his approach has some (...) limitations, for example, it requires a proof of functional completeness and axiomatization. Notwithstanding the first two constraints, it does not include all Epstein logics, e.g., logic Eq. Unlike Carnielli’s approach, here we use set-assignment semantics to determine those logics. Since syntax and semantics of a given logic usually determine a minimal syntax and structure of a tableau system for the logic along with other properties, we propose a uniform tableau framework for the logics determined by set-assignment semantics. What distinguishes our tableau systems is that they combine the features of tableaux for propositional logics and syllogistic logics when the problem of content of propositions is analysed in tableau proofs. To denote the content of propositions in the proofs, we use generalised labels (see Jarmużek and Goré in Landscapes in Logic, College Publications, London, 2021). (shrink)

We show how to correct the analytic tableaux system from the paper Olkhovikov and Wansing, 259–279, 2018).

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)

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

Temporal epistemic logics are known, from results of Halpern and Vardi, to have a wide range of complexities of the satisfiability problem: from PSPACE, through non-elementary, to highly undecidable. These complexities depend on the choice of some key parameters specifying, inter alia, possible interactions between time and knowledge, such as synchrony and agents' abilities for learning and recall. In this work we develop practically implementable tableau-based decision procedures for deciding satisfiability in single-agent synchronous temporal-epistemic logics with interactions between time and (...) knowledge. We discuss some complications that occur, even in the single-agent case, when interactions between time and knowledge are assumed and show how the method of incremental tableaux can be adapted to work in EXPSPACE, respectively 2EXPTIME, for these logics, thereby also matching the upper bounds obtained for them by Halpern and Vardi. (shrink)

The book presents logical foundations of dual tableaux together with a number of their applications both to logics traditionally dealt with in mathematics and philosophy (such as modal, intuitionistic, relevant, and many-valued logics) and to various applied theories of computational logic (such as temporal reasoning, spatial reasoning, fuzzy-set-based reasoning, rough-set-based reasoning, order-of magnitude reasoning, reasoning about programs, threshold logics, logics of conditional decisions). The distinguishing feature of most of these applications is that the corresponding dual tableaux are built (...) in a relational language which provides useful means of presentation of the theories. In this way modularity of dual tableaux is ensured. We do not need to develop and implement each dual tableau from scratch, we should only extend the relational core common to many theories with the rules specific for a particular theory. (shrink)

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

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

The forward convergence constraint is important to time analysis. Without it, given two future moments to the same point, the time branches. This is unacceptable if one assumes that time is linear. Nevertheless, one may wish to consider time-branching in order to discuss future possibilities. One can have both a linear order for the time and branching through the combination of the tense logic semantics with those of an alethic logic which allows the evaluation of the timelines of other possible (...) worlds. In this paper, I give the semantics and the tableaux systems for some alethic-tense logics. I review one in which worlds differ on their time orders, another in which they agree on the time order, a pair of conditional tense logics ), and the first-order version of MT. A brief philosophical discussion arises from every system. (shrink)

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

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.

Throughout the last decade, there has been an increased interest in various forms of dynamic epistemic logics to model the flow of information and the effect this flow has on knowledge in multi-agent systems. This enterprise, however, has mostly been applicationally and semantically driven. This results in a limited amount of proof theory for dynamic epistemic logics. In this paper, we try to compensate for a part of this by presenting terminating tableau systems for full dynamic epistemic logic with action (...) models and for a hybrid public announcement logic. The tableau systems are extensions of already existing tableau systems, in addition to which we have used the reduction axioms of dynamic epistemic logic to define rules for the dynamic part of the logics. Termination is shown using methods introduced by Braüner, Bolander, and Blackburn. (shrink)

From picture to photography and back. Tableau vivants, in their gestural synthetic dimension, represent for Diderot the apex of expression that the image can make explicit. Nothing closer to Wall’s poetics. His works show outstanding attention to detail: from scenic design to protagonists’ costumes, from light to actors’ action. And the result is exactly what Diderot saw in the eyes of people observing Chardin’s art: imagination at work.

The paper describes tableaux based proof methods for temporal logics of knowledge allowing non-trivial interaction axioms between the modal and temporal components, namely those of synchrony and no learning and synchrony and perfect recall. The interaction axioms allow the description of how knowledge evolves over time and makes reasoning in such logics theoretically more complex. Such logics can be used to specify systems that involve the knowledge of processes or agents and which change over time, for example agent based (...) systems, knowledge games or security protocols. Soundness, completeness and termination results for the tableaux are proved. (shrink)

This is the first paper on constructive concurrent dynamic logic . For the first time, either for concurrent or sequential dynamic logic, we give a satisfactory treatment of what statements are forced to be true by partial information about the underlying computer. Dynamic logic was developed by Pratt [V. Pratt, Semantical considerations on Floyd–Hoare logic, in: 17th Annual IEEE Symp. on Found. Comp. Sci., New York, 1976, pp. 109–121, V. Pratt, Applications of modal logic to programming, Studia Logica 39 257–274] (...) for nondeterministic sequential programs, and by Peleg [D. Peleg, Concurrent dynamic logic, Journal of the Association for Computing Machinery 34 , D. Peleg, Communication in concurrent dynamic logic, Journal of Computer and System Sciences 35 ] for concurrent programs, for the purpose of proving properties of programs such as correctness. Here we define what it means for a dynamic logic formula to be forced to be true knowing only partial information about the results of assignments and tests. This informal CCDL semantics is formalized by intuitionistic Kripke frames modeling this partial information, and each such frame is interpreted as an idealized concurrent machine . In CCDL, proofs and deductions are ω-height, ω-branching, well-founded labeled subtrees of ωω. These are a generalization of the signed tableaux of Nerode [A. Nerode, Some lectures in modal logic, Technical Report, M.S.I. Cornell University, 1989, CIME Logic and Computer Science Montecatini Volume, Springer-Verlag Lecture Notes, 1990, A. Nerode, Some lectures in intuitionistic logic, Technical Report, M.S.I. Cornell University, 1988, Marktoberdorf Logic and Computation NATO Summer School Volume, NATO Science Series, 1990 ] stemming from the prefix tableaux of Fitting [M.C. Fitting, Proof Methods for Modal and Intuitionistic Logic, Reidel, 1983]. We demonstrate the correctness of our tableau proofs, define consistency properties, prove that consistency properties yield models, construct systematic tableaux, prove that systematic tableaux yield a consistency property, and conclude that CCDL is complete. This infinitary semantics and proof procedure will be the primary guide for defining, in a sequel, the correct finitary CCDL based on induction principles. FCCDL is suitable for implementation in constructive logic software systems such as Constable’s NUPRL or Huet-Coquand’s CONSTRUCTIONS. Our goal is to develop a constructive logic programming tool for specification and modular verification of programs in any imperative concurrent language, and for the extraction of concurrent programs from constructive proofs. Subsequent papers will introduce analogous logics for declarative and functional concurrent languages. (shrink)

As a remedy for the bad computational behaviour of first-order temporal logic (FOTL), it has recently been proposed to restrict the application of temporal operators to formulas with at most one free variable thereby obtaining so-called monodic fragments of FOTL. In this paper, we are concerned with constructing tableau algorithms for monodic fragments based on decidable fragments of first-order logic like the two-variable fragment or the guarded fragment. We present a general framework that shows how existing decision procedures for first-order (...) fragments can be used for constructing a tableau algorithm for the corresponding monodic fragment of FOTL. Some example instantiations of the framework are presented. (shrink)

This paper, we propose a modal logic satisfying minimal requirements for reasoning about diagrams via collection of sets and relations between them, following Harel's proposal. We first give an axiomatics of such a theory and then provide its Kripke semantics. Then we extend previous works of ours in order to obtain a decision procedure based on tableaux for this logic. Beside soundness and completeness of our tableaux, we manage to define a strategy of rule application ensuring termination by (...) extending the usual loop test of modal logic S4 to whole sub-structures of the model being computed. (shrink)

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

In this work we propose a labelled tableau method for Łukasiewicz infinite-valued logic Lω. The method is based on the Kripke semantics of this logic developed by Urquhart [25] and Scott [24]. On the one hand, our method falls under the general paradigm of labelled deduction [8] and it is rather close to the tableau systems for sub-structural logics proposed in [4]. On the other hand, it provides a CoNP decision procedure for Lω validity by reducing the check of branch (...) closure to linear programming. (shrink)

In this work we propose a labelled tableau method for ukasiewicz infinite-valued logic L . The method is based on the Kripke semantics of this logic developed by Urquhart [25] and Scott [24]. On the one hand, our method falls under the general paradigm of labelled deduction [8] and it is rather close to the tableau systems for sub-structural logics proposed in [4]. On the other hand, it provides a CoNP decision procedure for L validity by reducing the check of (...) branch closure to linear programming. (shrink)

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)

Les rituels sont les synapses dans le tissu culturel d'où sont issus les éléments qui gouvernent la vie en commun et la communication des êtres humains. Il en est ainsi depuis le commencement de toute société humaine. Mais ce n'est qu'au XX siècle que se manifeste un véritable intérêt pour le fonctionnement et l'importance culturelle des rituels. Il s'agit d'un tournant inspiré par les théories des ethnologues, et placé sous le signe du cultural turn et du performative turn du XX (...) siècle. On se détourne alors des pratiques jusque-là en vigueur de l'abstraction et de la représentation. Or, depuis le «Banquet» de Platon et l'instauration de la «Cène» chrétienne, l'un des rituels les plus importants est l'acte socialement codé de l'ingestion de nourriture, le repas. Avec l'Eat art dont il est le concepteur, Daniel Spoerri a repris ce thème et contribué, par le truchement du rituel piège, à poser un regard neuf sur l'acte de manger au XXe siècle. Tel que Spoerri le met en scène, le «rituel piège» attire l'attention sur le rôle de fondation de sens que joue le rituel dans la culture. Mais il fait apparaître également que les rituels se transforment en pièges idéologiques où tombe quiconque les prend « à la lettre » ou comme des évidences. Spoerri est un des artistes du XX et de ce début du XXI siècle qui, par le biais de leur art, rendent compte de la double fonction du rituel dans la culture: d'une part, le rituel maintient en vie le processus culturel; d'autre part, il est producteur d'idéologies qui font passer des mythes politiques pour naturels, prenant au piège consommateur de nourriture et consommateur d'art tout à la fois.Rituals are the synapses in the cultural fabric which has produced the elements that govern the coexistence and communication of human beings. This is so since the beginning of human society. But it is only 20th century that demonstrates a genuine interest in the operation and cultural importance of rituals. It is a milestone inspired by the theories of ethnologists, and placed under the sign of the cultural turn and performative turn of the twentieth century. It then turns practices far into force of abstraction and representation. However, since the "Banquet" of Plato and the establishment of the "Last Supper" Christian, one of the most important rituals is the act socially coded ingestion of food, meal. Eat with the art of which he is the designer, Daniel Spoerri took up this theme and contributed through the ritual trap, put a new perspective on the act of eating in the twentieth century. Spoerri as the stages, the "ritual trap" draws attention to the role of Foundation meaningful ritual plays in the culture. But it also shows that the rituals are transformed into ideological traps which falls whoever takes "the letter" or as evidence. Spoerri is one of the artists of the 20th and the beginning of the 21st century, through their art, reflect the dual role of ritual in culture: on the one hand, the ritual keeps life the cultural process, on the other hand, it is a producer of ideologies that pass for political myths natural trapping consumer food and consumer of art at the same time. (shrink)