A sequent calculus for logic of knowledge and past time: Completeness and decidability

We consider logic of knowledge and past time. This logic involves the discrete-time linear temporal operators next, until, weak yesterday, and since. In addition, it contains an indexed set of unary modal operators agent i knows.We consider the semantic constraint of the unique initial states for this logic. For the logic, we present a sequent calculus with a restricted cut rule. We prove the soundness and completeness of the sequent calculus presented. We prove the decidability of provability in the considered calculus as well. So, this calculus can be used as a basis for automated theorem proving. The proof method for the completeness can be used to construct complete sequent calculi with a restricted cut rule for this logic with other semantical constraints as well. Published in Lietuvos Matematikos Rinkinys, Vol. 46, No. 3, pp. 427–437, July–September, 2006.     

A Sequent Calculus for Propositional Dynamic Logic for Agents

We consider propositional dynamic logic for agents. For this logic, we present a sequent calculus with a restricted cut rule and prove the soundness and completeness for the calculus.     

On a logic of involutive quantales

The logic just corresponding to (non‐commutative) involutive quantales, which was introduced by Wendy MacCaull, is reconsidered in order to obtain a cut‐free sequent calculus formulation, and the completeness theorem (with respect to the involutive quantale model ) for this logic is proved using a new admissible rule. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

TOPOS BASED SEMANTIC FOR CONSTRUCTIVE LOGIC WITH STRONG NEGATION

The aim of the paper is to show that topoi are useful in the categorial analysis of the constructive logic with strong negation. In any topos ? we can distinguish an object Λ and its truth-arrows such that sets ?(A, Λ) (for any object A) have a Nelson algebra structure. The object Λ is defined by the categorial counterpart of the algebraic FIDEL-VAKARELOV construction. Then it is possible to define the universal quantifier morphism which permits us to make the first order predicate calculus. The completeness theorem is proved using the Kripke-type semantic defined by THOMASON .     

A Sequent Calculus for Propositional Dynamic Logic for Agents with Interactions

We consider a propositional dynamic logic for agents with interactions such as known commitment, no learning, and perfect recall. For this logic, we present a sequent calculus with a restricted cut rule and prove the soundness and completeness for the calculus.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 2, pp. 261–269, April–June, 2005.     

Cut‐elimination Theorems for Some Infinitary Modal Logics

In this article, a cut‐free system TLM_ω1 for infinitary propositional modal logic is proposed which is complete with respect to the class of all Kripke frames.The system TLM_ω1 is a kind of Gentzen style sequent calculus, but a sequent of TLM_ω1 is defined as a finite tree of sequents in a standard sense. We prove the cut‐elimination theorem for TLM_ω1 via its Kripke completeness.     

Specialization of Loop Rules of a Sequent Calculus of Intuitionistic Temporal Logic with Time Gaps

The paper deals with the loop-rule problem in the first-order intuitionistic temporal logic sequent calculus LBJ. The calculus LBJT is intended for the specialization of the antecedent implication rule. The invertibility of some of the LBJT rules and the syntactic admissibility of the structural rules and the cut rule in LBJT, as well as the equivalence of LBJ and LBJT, are proved. The calculus LBJT2 is intended for the specialization of the antecedent universal quantifier and antecedent box rules. The decidability of LBJT2 is proved.     

A coding method for a sequent calculus of propositional logic

The paper deals with a coding method for a sequent calculus of the propositional logic. The method is based on the sequent calculus. It allows us to determine if a formula is derivable in the calculus without constructing a derivation tree. The main advantage of the coding method is its compactness in comparison with derivation trees of the sequent calculus. The coding method can be used as a decision procedure for the propositional logic.     

Cut elimination for S4n and K4n with the central agent axiom

We analyze the multimodal logic S4 _n with the central agent axiom. We present a Hilbert-type calculus, then derive a Gentzen-type calculus with cut, and prove a cut-elimination theorem. The work shows that it is possible to construct a cut-free Gentzen-type calculus for this logic. Moreover, it also provides analogous results for the multimodal logic K4 _n with the central agent axiom.     

A two-dimensional metric temporal logic

We introduce a two-dimensional metric (interval) temporal logic whose internal and external time flows are dense linear orderings. We provide a suitable semantics and a sequent calculus with axioms for equality and extralogical axioms. Then we prove completeness and a semantic partial cut elimination theorem down to formulas of a certain type.     

Proof-theoretical investigation of temporal logic with time gaps

In the paper, the first-order intuitionistic temporal logic sequent calculus LBJ is considered. The invertibility of some of the LBJ rules, syntactic admissibility of the structural rules and the cut rule in LBJ, as well as Harrop and Craig's interpolation theorems for LBJ are proved. Gentzen's midsequent theorem is proved for the LBJ' calculus which is obtained from LBJ by removing the antecedent disjunction rule from it. Published in Lietuvos Matematikos Rinkinys, Vol. 40, No. 3, pp. 255–276, July–September, 2000.     

Local computation in linear logic

This work deals with the exponential fragment of Girard's linear logic ([3]) without the contraction rule, a logical system which has a natural relation with the direct logic ([10], [7]). A new sequent calculus for this logic is presented in order to remove the weakening rule and recover its behavior via a special treatment of the propositional constants, so that the process of cut-elimination can be performed using only “local” reductions. Hence a typed calculus, which admits only local rewriting rules, can be introduced in a natural manner. Its main properties — normalizability and confluence — has been investigated; moreover this calculus has been proved to satisfy a Curry-Howard isomorphism ([6]) with respect to the logical system in question. MSC: 03B40, 03F05.     

Uniform interpolation and the existence of sequent calculi

This paper presents a uniform and modular method to prove uniform interpolation for several intermediate and intuitionistic modal logics. The proof-theoretic method uses sequent calculi that are extensions of the terminating sequent calculus $\mathsf{G4ip}$ for intuitionistic propositional logic. It is shown that whenever the rules in a calculus satisfy certain structural properties, the corresponding logic has uniform interpolation. It follows that the intuitionistic versions of $\mathsf{K}$ and $\mathsf{KD}$ (without the diamond operator) have uniform interpolation. It also follows that no intermediate or intuitionistic modal logic without uniform interpolation has a sequent calculus satisfying those structural properties, thereby establishing that except for the seven intermediate logics that have uniform interpolation, no intermediate logic has such a sequent calculus.     

An epistemic model of an agent who does not reflect on reasoning processes

This paper introduces an epistemic model of a boundedly rational agent under the two assumptions that (i) the agent’s reasoning process is in accordance with the model but (ii) the agent does not reflect on these reasoning processes. For such a concept of bounded rationality a semantic interpretation by the possible world semantics of the Kripke (1963) type is no longer available because the definition of knowledge in these possible world semantics implies that the agent knows all valid statements of the model. The key to my alternative semantic approach is the extension of the method of truth tables, first introduced for the propositional logic by Wittgenstein (1922), to an epistemic logic so that I can determine the truth value of epistemic statements for all relevant truth conditions. In my syntactic approach I define an epistemic logic–consisting of the classical calculus of propositional logic plus two knowledge axioms–that does not include the inference rule of necessitation, which claims that an agent knows all theorems of the logic. As my main formal result I derive a determination theorem linking my semantic with my syntactic approach. The difference between my approach and existing knowledge models is illustrated in a game-theoretic application concerning the epistemic justification of iterative solution concepts.     

Deep sequent systems for modal logic

We see a systematic set of cut-free axiomatisations for all the basic normal modal logics formed by some combination the axioms d, t, b, 4, 5. They employ a form of deep inference but otherwise stay very close to Gentzen’s sequent calculus, in particular they enjoy a subformula property in the literal sense. No semantic notions are used inside the proof systems, in particular there is no use of labels. All their rules are invertible and the rules cut, weakening and contraction are admissible. All systems admit a straightforward terminating proof search procedure as well as a syntactic cut elimination procedure.      

Strategies and simulations in a semantic framework

By means of several examples of structural operational semantics for a variety of languages, we justify the importance and interest of using the notions of strategies and simulations in the semantic framework provided by rewriting logic and implemented in the Maude metalanguage. On the one hand, we describe a basic strategy language for Maude and show its application to CCS, the ambient calculus, and the parallel functional language Eden. On the other hand, we show how the concept of stuttering simulation can be used inside Maude to show that a stack machine correctly implements the operational semantics of a simple functional language.     

A BRIEF SURVEY OF FRAMES FOR THE LAMBEK CALCULUS

Models for the Lambek calculus of syntactic categories surveyed here are based on frames that are in principle of the same type as Kripke frames for intuitionistic logic. These models are extracted from the literature on models for relevant logics, in particular the ternary relationed models introduced in the early seventies. The purpose of this brief survey is to locate some open completeness problems for variants of the Lambek calculus in the context of completeness results based on various types of ternary relational models.     

中介命题演算系统$MP^{M}$的代数系统

MP~M系统是在中介逻辑系统的基础上建立起来的,用于处理数据库中不完全信息的三值逻辑命题演算系统．本文通过在MP~M系统上建立一个代数系统,对MP~M系统进行了代数抽象,讨论了MP~M系统的代数性质．本文还研究了该代数系统的次直积,以及与其它一些代数系统之间的关系．     

Dual‐Context Sequent Calculus and Strict Implication

We introduce a dual‐context style sequent calculus which is complete with respectto Kripke semantics where implication is interpreted as strict implication in the modal logic K. The cut‐elimination theorem for this calculus is proved by a variant of Gentzen's method.     

The Operators of Vector Logic

Vector logic is a mathematical model of the propositional calculus in which the logical variables are represented by vectors and the logical operations by matrices. In this framework, many tautologies of classical logic are intrinsic identities between operators and, consequently, they are valid beyond the bivalued domain. The operators can be expressed as Kronecker polynomials. These polynomials allow us to show that many important tautologies of classical logic are generated from basic operators via the operations called Type I and Type II products. Finally, it is described a matrix version of the Fredkin gate that extends its properties to the many-valued domain, and it is proved that the filtered Fredkin operators are second degree Kronecker polynomials that cannot be generated by Type I or Type II products. Mathematics Subject Classification: 03B05, 03B50.