Abstract Levesque and Lakemeyer proposed a logic called $$\mathcal L$$ L as a first-order logic for knowledge representation and reasoning in knowledge-based systems. A characteristic feature of this logic is that it uses a countably infinite set of what are called standard names, which are syntactically treated like constants, but which are also isomorphic to a fixed universe of discourse. Quantifiers in $$\mathcal L$$ L are then given a substitutional interpretation. This non-standard semantics not only simplifies the proofs for certain meta-theoretic properties, but is also exploited in dedicated reasoning procedures for modal extensions of $$\mathcal L$$ L that include notions of belief, actions, time, and more. However, the only sound and complete proof system provided for $$\mathcal L$$ L so far is a Hilbert-style axiom system, as well as an iterative reasoning mechanism based on resolution and clause subsumption. In this paper, we present a tableau system for $$\mathcal L$$ L , and show its soundness and completeness. Completeness is proved first by reduction to the existing axiom system, and involves the cut rule, and then via Hintikka sets, which does not require the cut rule.

Abstract We present an axiom system for what we call Prior’s Ideal Language and prove its completeness and pure completeness with respect to general models. With this is done, we explain, with examples, why this system provides a useful setting for exploring Arthur Prior’s work.

In this article we define a family of many-valued semantics for hybrid logic, where each semantics is based on a finite Heyting algebra of truth-values. We provide sound and complete tableau systems for these semantics. Moreover, we show how the tableau systems can be made terminating and thereby give rise to decision procedures for the logics in question. Our many-valued hybrid logics turn out to be ‘intermediate’ logics between intuitionistic hybrid logic and classical hybrid logic in a specific sense explained in the article. Our results show that many-valued hybrid logic is indeed a natural enterprise.

Proof systems for hybrid logic typically use @-operators to access information hidden behind modalities; this labelling approach lies at the heart of the best known hybrid resolution, natural deduction and tableau systems. But there is another approach, which we have come to believe is conceptually clearer. We call this Seligman-style inference, as it was first introduced and explored by Jerry Seligman in natural deduction and sequent calculus in the 1990s. The purpose of this article is to introduce a Seligman-style tableau system, to prove its completeness, and to show how it can be made to terminate. The most obvious feature of Seligman-style systems is that they work with arbitrary formulas, not just statements prefixed by @-operators. They do so by introducing machinery for switching to other proof contexts. We capture this idea in the setting of tableaus by introducing a rule called GoTo, which allows us to ‘jump to a named world’ on a tableau branch. We first develop a Seligman-style tableau system for basic hybrid logic and prove its completeness. We then prove termination of a restricted version of the system without resorting to loop checking, and show that the restrictions do not effect completeness. Both completeness and termination results are proved by explicit translations that transform tableaus in a standard labelled system into Seligman-style tableaus and vice-versa.

Journal Article Adding Intensional Machinery to Hybrid Logic Get access Torben Braüner Torben Braüner Programming, Logic and Intelligent Systems Research Group, Roskilde University, DK-4000 Roskilde, Denmark. E-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 18, Issue 4, August 2008, Pages 631–648, https://doi.org/10.1093/logcom/exn005 Published: 13 March 2008

Hybrid logics are a principled generalization of both modal logics and description logics. It is well known that various hybrid logics without binders are decidable, but decision procedures are usually not based on tableau systems, a kind of formal proof procedure that lends itself to computer implementation. In this article, we give four different tableau-based decision procedures for a very expressive hybrid logic including the universal modality; three of the procedures are based on different tableau systems, and one procedure is based on a Gentzen system. The decision procedures make use of so-called loop-checks, which is a standard technique used in connection with tableau systems for other logics, namely, prefixed tableau systems for transitive modal logics as well as for certain description logics. The loop-checks used in our four decision procedures are similar, but the four proof systems on which the procedures are based constitute a spectrum of different systems: prefixed and internalized systems, tableau and Gentzen systems.

In this paper we give a natural deduction formulation of hybrid logic. Our natural deduction system can be extended with additional inference rules corresponding to conditions on the accessibility relations expressed by so-called geometric theories. Thus, we give natural deduction systems in a uniform way for a wide class of hybrid logics which appears to be impossible in the context of ordinary modal logic. We prove soundness and completeness and we prove a normalization theorem. We finally prove a result which says that normal derivations in the natural deduction system correspond to derivations in a cut-free Gentzen system.

Usually types of PCF are interpreted as cpos and terms as continuous functions. It is then the case that non-termination of a closed term of ground type corresponds to the interpretation being bottom; we say that the semantics is adequate. We shall h