Axiomatizing hybrid products: How can we reason many-dimensionally in hybrid logic?

The aim of this paper is to propose a two-dimensional hybrid logic in order to formalize inferences containing both spatial and temporal propositions. The semantic idea behind the proposal is to name both horizontal and vertical lines in a 2D-plane by two kinds of nominals. This is a generalization of the idea of naming a point in one-dimensional hybrid logic. I give an axiomatization of the proposed two-dimensional hybrid logic and show that it enjoys a general completeness result (called pure completeness) with respect to product Kripke frames. Moreover, in order to capture $T\times W$-frames studied by R.H. Thomason (1984), I introduce the notion of a dependent product frame, which enables us to represent the dependence of space over time. I also give a complete axiomatization of this dependent two-dimensional hybrid logic, and, as a corollary, reveal that a hybridization of $T\times W$-logic enjoys strong completeness.     

Gentzen Calculi for the Existence Predicate

We introduce Gentzen calculi for intuitionistic logic extended with an existence predicate. Such a logic was first introduced by Dana Scott, who provided a proof system for it in Hilbert style. We prove that the Gentzen calculus has cut elimination in so far that all cuts can be restricted to very simple ones. Applications of this logic to Skolemization, truth value logics and linear frames are also discussed.     

Using temporal logics of knowledge for specification and verification—a case study

Temporal logics of knowledge are useful for reasoning about situations where the knowledge of an agent or component is important, and where change in this knowledge may occur over time. Here we use temporal logics of knowledge to reason about the game Cluedo. We show how to specify Cluedo using temporal logics of knowledge and prove statements about the knowledge of the players using a clausal resolution calculus for this logic. We discuss the advantages and disadvantages of using this logic to specify and verify the game Cluedo and describe related implementations.     

A general method for proving decidability of intuitionistic modal logics

We generalise the result of [H. Ganzinger, C. Meyer, M. Veanes, The two-variable guarded fragment with transitive relations, in: Proc. 14th IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, 1999, pp. 24–34] on decidability of the two variable monadic guarded fragment of first order logic with constraints on the guard relations expressible in monadic second order logic. In [H. Ganzinger, C. Meyer, M. Veanes, The two-variable guarded fragment with transitive relations, in: Proc. 14th IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, 1999, pp. 24–34], such constraints apply to one relation at a time. We modify their proof to obtain decidability for constraints involving several relations. Now we can use this result to prove decidability of multi-modal modal logics where conditions on accessibility relations involve more than one relation. Our main application is intuitionistic modal logic, where the intuitionistic and modal accessibility relations usually interact in a non-trivial way.     

Rough Sets and 3-Valued Logics

In the paper we explore the idea of describing Pawlak’s rough sets using three-valued logic, whereby the value t corresponds to the positive region of a set, the value f — to the negative region, and the undefined value u — to the border of the set. Due to the properties of the above regions in rough set theory, the semantics of the logic is described using a non-deterministic matrix (Nmatrix). With the strong semantics, where only the value t is treated as designated, the above logic is a “common denominator” for Kleene and Łukasiewicz 3-valued logics, which represent its two different “determinizations”. In turn, the weak semantics—where both t and u are treated as designated—represents such a “common denominator” for two major 3-valued paraconsistent logics. We give sound and complete, cut-free sequent calculi for both versions of the logic generated by the rough set Nmatrix. Then we derive from these calculi sequent calculi with the same properties for the various “determinizations” of those two versions of the logic (including Łukasiewicz 3-valued logic). Finally, we show how to embed the four above-mentioned determinizations in extensions of the basic rough set logics obtained by adding to those logics a special two-valued “definedness” or “crispness” operator.     

Interpolation in non-classical logics

We discuss the interpolation property on some important families of non classical logics, such as intuitionistic, modal, fuzzy, and linear logics. A special paragraph is devoted to a generalization of the interpolation property, uniform interpolation. Supported by PRIN project 2006/2007 ‘Large-scale development of certified mathematical proofs’.     

Permission from an Input/Output Perspective

Input/output logics are abstract structures designed to represent conditional obligations and goals. In this paper we use them to study conditional permission. This perspective provides a clear separation of the familiar notion of negative permission from the more elusive one of positive permission. Moreover, it reveals that there are at least two kinds of positive permission. Although indistinguishable in the unconditional case, they are quite different in conditional contexts. One of them, which we call static positive permission, guides the citizen and law enforcement authorities in the assessment of specific actions under current norms, and it behaves like a weakened obligation. Another, which we call dynamic positive permission, guides the legislator. It describes the limits on the prohibitions that may be introduced into a code, and under suitable conditions behaves like a strengthened negative permission.     

Routes to Triviality

It is known that a number of inference principles can be used to trivialise the axioms of naïve comprehension – the axioms underlying the naïve theory of sets. In this paper we systematise and extend these known results, to provide a number of general classes of axioms responsible for trivialising naïve comprehension.     

Light Affine Set Theory: A Naive Set Theory of Polynomial Time

In [7], a naive set theory is introduced based on a polynomial time logical system, Light Linear Logic (LLL). Although it is reasonably claimed that the set theory inherits the intrinsically polytime character from the underlying logic LLL, the discussion there is largely informal, and a formal justification of the claim is not provided sufficiently. Moreover, the syntax is quite complicated in that it is based on a non-traditional hybrid sequent calculus which is required for formulating LLL.In this paper, we consider a naive set theory based on Intuitionistic Light Affine Logic (ILAL), a simplification of LLL introduced by [1], and call it Light Affine Set Theory (LAST). The simplicity of LAST allows us to rigorously verify its polytime character. In particular, we prove that a function over {0, 1}* is computable in polynomial time if and only if it is provably total in LAST.