Algorithmic Proof Methods and Cut Elimination for Implicational Logics Part I: Modal Implication

In this work we develop goal-directed deduction methods for the implicational fragment of several modal logics. We give sound and complete procedures for strict implication of K, T, K4, S4, K5, K45, KB, KTB, S5, G and for some intuitionistic variants. In order to achieve a uniform and concise presentation, we first develop our methods in the framework of Labelled Deductive Systems [Gabbay 96]. The proof systems we present are strongly analytical and satisfy a basic property of cut admissibility. We then show that for most of the systems under consideration the labelling mechanism can be avoided by choosing an appropriate way of structuring theories. One peculiar feature of our proof systems is the use of restart rules which allow to re-ask the original goal of a deduction. In case of K, K4, S4 and G, we can eliminate such a rule, without loosing completeness. In all the other cases, by dropping such a rule, we get an intuitionistic variant of each system. The present results are part of a larger project of a goal directed proof theory for non-classical logics; the purpose of this project is to show that most implicational logics stem from slight variations of a unique deduction method, and from different ways of structuring theories. Moreover, the proof systems we present follow the logic programming style of deduction and seem promising for proof search [Gabbay and Reyle 84, Miller et al. 91].     

Many-Valued Logics and Suszko's Thesis Revisited

Suszko's Thesis maintains that many-valued logics do not exist at all. In order to support it, R. Suszko offered a method for providing any structural abstract logic with a complete set of bivaluations. G. Malinowski challenged Suszko's Thesis by constructing a new class of logics (called q-logics by him) for which Suszko's method fails. He argued that the key for logical two-valuedness was the "bivalent" partition of the Lindenbaum bundle associated with all structural abstract logics, while his q-logics were generated by "trivalent" matrices. This paper will show that contrary to these intuitions, logical two-valuedness has more to do with the geometrical properties of the deduction relation of a logical structure than with the algebraic properties embedded on it.     

On Vagueness,Truth Values and Fuzzy Logics

Some aspects of vagueness as presented in Shapiro’s book Vagueness in Context [23] are analyzed from the point of fuzzy logic. Presented are some generalizations of Shapiro’s formal apparatus. Presented by Daniele Mundici     

Kripke Semantics, Undecidability and Standard Completeness for Esteva and Godo's Logic MTL∀

The present paper deals with the predicate version MTL of the logic MTL by Esteva and Godo. We introduce a Kripke semantics for it, along the lines of Ono's Kripke semantics for the predicate version of FL_ew (cf. [O85]), and we prove a completeness theorem. Then we prove that every predicate logic between MTL and classical predicate logic is undecidable. Finally, we prove that MTL is complete with respect to the standard semantics, i.e., with respect to Kripke frames on the real interval [0,1], or equivalently, with respect to MTL-algebras whose lattice reduct is [0,1] with the usual order.     

Subjective Situations and Logical Omniscience

The beliefs of the agents in a multi-agent system have been formally modelled in the last decades using doxastic logics. The possible worlds model and its associated Kripke semantics provide an intuitive semantics for these logics, but they commit us to model agents that are logically omniscient. We propose a way of avoiding this problem, using a new kind of entities called subjective situations. We define a new doxastic logic based on these entities and we show how the belief operators have some desirable properties, while avoiding logical omniscience. A comparison with two well-known proposals (Levesque's logic of explicit and implicit beliefs and Thijsse's hybrid sieve systems) is also provided.     

Special issue: Combining probability and logic

This editorial explains the scope of the special issue and provides a thematic introduction to the contributed papers.     

Combinator Logics

Combinator logics are a broad family of substructual logics that are formed by extending the basic relevant logic B with axioms that correspond closely to the reduction rules of proper combinators in combinatory logic. In the Routley-Meyer relational semantics for relevant logic each such combinator logic is characterized by the class of frames that meet a first-order condition that also directly corresponds to the same combinator's reduction rule. A second family of logics is also introduced that extends B with the addition of propositional constants that correspond to combinators. These are characterized by relational frames that meet first-order conditions that reflect the structures of the combinators themselves.     

Measuring coherence using LP-models

This paper introduces a technique for measuring the degree of (in)coherence of inconsistent sets of propositional formulas. The coherence of these sets of formulas is calculated using the minimal models of those sets in G. Priest's Logic of Paradox. The compatibility of the information expressed by a set of formulas with the background or domain knowledge can also be measured with this technique. In this way, Hunter's objections to many-valued paraconsistent logics as instruments for measuring (in)coherence are addressed.     

An analytic tableau calculus for a temporalised belief logic

A tableau is a refutation-based decision procedure for a related logic, and is among the most popular proof procedures for modal logics. In this paper, we present a labelled tableau calculus for a temporalised belief logic called TML⁺, which is obtained by adding a linear-time temporal logic onto a belief logic by the temporalisation method of Finger and Gabbay. We first establish the soundness and the completeness of the labelled tableau calculus based on the soundness and completeness results of its constituent logics. We then sketch a resolution-type proof procedure that complements the tableau calculus and also propose a model checking algorithm for TML⁺ based on the recent results for model checking procedures for temporalised logics. TML⁺ is suitable for formalising trust and agent beliefs and reasoning about their evolution for agent-based systems. Based on the logic TML⁺, the proposed labelled tableau calculus could be used for analysis, design and verification of agent-based systems operating in dynamic environments.