Eliminability of cut in hypersequent calculi for some modal logics of linear frames

Hypersequent calculi, introduced independently by Pottinger and Avron, provide a powerful generalization of ordinary sequent calculi. In the paper we present a proof of eliminability of cut in hypersequent calculi for three modal logics of linear frames: K4.3, KD4.3 and S4.3. Our cut-free calculus is based on Avron's HC formalization for Gödel–Dummett's logic. The presented proof of eliminability of cut is purely syntactical and based on Ciabattoni, Metcalfe, Montagna's proof of eliminability of cut for hypersequent calculi for some fuzzy logics with modalities.     

Cut-free proof systems for logics of weak excluded middle

 In this work we perform a proof-theoretical investigation of some logical systems in the neighborhood of substructural, intermediate and many-valued logics. The common feature of the logics we consider is that they satisfy some weak forms of the excluded-middle principle. We first propose a cut-free hypersequent calculus for the intermediate logic LQ, obtained by adding the axiom *A∨**A to intuitionistic logic. We then propose cut-free calculi for systems W _n , obtained by adding the axioms *A∨(A ⊕ ⋯ ⊕ A) (n−1 times) to affine linear logic (without exponential connectives). For n=3, the system W _n coincides with 3-valued Łukasiewicz logic. For n>3, W _n is a proper subsystem of n-valued Łukasiewicz logic. Our calculi can be seen as a first step towards the development of uniform cut-free Gentzen calculi for finite-valued Łukasiewicz logics.     

Hypersequents,logical consequence and intermediate logics for concurrency

The existence of simple semantics and appropriate cut-free Gentzen-type formulations are fundamental intrinsic criteria for the usefulness of logics. In this paper we show that by using hypersequents (which are multisets of ordinary sequents) we can provide such Gentzen-type systems to many logics. In particular, by using a hypersequential generalization of intuitionistic sequents we can construct cut-free systems for some intermediate logics (including Dummett's LC) which have simple algebraic semantics that suffice, e.g., for decidability. We discuss the possible interpretations of these logics in terms of parallel computation and the role that the usual connectives play in them (which is sometimes different than in the sequential case).     

Cut-free sequent systems for temporal logic

Currently known sequent systems for temporal logics such as linear time temporal logic and computation tree logic either rely on a cut rule, an invariant rule, or an infinitary rule. The first and second violate the subformula property and the third has infinitely many premises. We present finitary cut-free invariant-free weakening-free and contraction-free sequent systems for both logics mentioned. In the case of linear time all rules are invertible. The systems are based on annotating fixpoint formulas with a history, an approach which has also been used in game-theoretic characterisations of these logics.     

A binary modal logic for the intersection types of lambda-calculus

Intersection types discipline allows to define a wide variety of models for the type free lambda-calculus, but the Curry–Howard isomorphism breaks down for this kind of type systems. In this paper we show that the correspondence between types and suitable logical formulas can still be recovered appealing to the fact that there is a strict connection between the semantics for lambda-calculus induced by the intersection types and a Kripke-style semantics for modal and relevant logics. Indeed, we present a modal logic hinted by the analysis of the sub-typing relation for intersection types, and we show that the deduction relation for such a modal system is a conservative extension of the relation of sub-typing. Then, we define a Kripke-style semantics for the formulas of such a system, present suitable sequential calculi, prove a completeness theorem and give a syntactical proof of the cut elimination property. Finally, we define a decision procedure for theorem-hood and we show that it yields the finite model property and cut-redundancy.     

Focusing and polarization in linear,intuitionistic, and classical logics

A focused proof system provides a normal form to cut-free proofs in which the application of invertible and non-invertible inference rules is structured. Within linear logic, the focused proof system of Andreoli provides an elegant and comprehensive normal form for cut-free proofs. Within intuitionistic and classical logics, there are various different proof systems in the literature that exhibit focusing behavior. These focused proof systems have been applied to both the proof search and the proof normalization approaches to computation. We present a new, focused proof system for intuitionistic logic, called LJF, and show how other intuitionistic proof systems can be mapped into the new system by inserting logical connectives that prematurely stop focusing. We also use LJF to design a focused proof system LKF for classical logic. Our approach to the design and analysis of these systems is based on the completeness of focusing in linear logic and on the notion of polarity that appears in Girard’s LC and LU proof systems.     

The Nature of Nonmonotonic Reasoning

Conclusions reached using common sense reasoning from a set of premises are often subsequently revised when additional premises are added. Because we do not always accept previous conclusions in light of subsequent information, common sense reasoning is said to be nonmonotonic. But in the standard formal systems usually studied by logicians, if a conclusion follows from a set of premises, that same conclusion still follows no matter how the premise set is augmented; that is, the consequence relations of standard logics are monotonic. Much recent research in AI has been devoted to the attempt to develop nonmonotonic logics. After some motivational material, we give four formal proofs that there can be no nonmonotonic consequence relation that is characterized by universal constraints on rational belief structures. In other words, a nonmonotonic consequence relation that corresponds to universal principles of rational belief is impossible. We show that the nonmonotonicity of common sense reasoning is a function of the way we use logic, not a function of the logic we use. We give several examples of how nonmonotonic reasoning systems may be based on monotonic logics.     

Controlled integration of the cut rule into connection tableau calculi

In this paper techniques are developed and compared that increase the inferential power of tableau systems for classical first-order logic. The mechanisms are formulated in the framework of connection tableaux, which is an amalgamation of the connection method and the tableau calculus, and a generalization of model elimination. Since connection tableau calculi are among the weakest proof systems with respect to proof compactness, and the (backward) cut rule is not suitable for the first-order case, we study alternative methods for shortening proofs. The techniques we investigate are the folding-up and the folding-down operations. Folding up represents an efficient way of supporting the basic calculus, which is top-down oriented, with lemmata derived in a bottom-up manner. It is shown that both techniques can also be viewed as controlled integrations of the cut rule. To remedy the additional redundancy imported into tableau proof procedures by the new inference rules, we develop and apply an extension of the regularity condition on tableaux and the mechanism of anti-lemmata which realizes a subsumption concept on tableaux. Using the framework of the theorem prover SETHEO, we have implemented three new proof procedures that overcome the deductive weakness of cut-free tableau systems. Experimental results demonstrate the superiority of the systems with folding up over the cut-free variant and the one with folding down.Work supported by the Deutsche Forschungsgemeinschaft and the Esprit Basic Research Action 6471 Medlar II.     

SAT-Based Decision Procedures for Classical Modal Logics

We present a set of SAT-based decision procedures for various classical modal logics. By SAT based, we mean built on top of a SAT solver. We show how the SAT-based approach allows for a modular implementation for these logics. For some of the logics we deal with, we are not aware of any other implementation. For the others, we define a testing methodology that generalizes the 3CNF _K methodology by Giunchiglia and Sebastiani. The experimental evaluation shows that our decision procedures perform better than or as well as other state-of-the-art decision procedures.     

Finite-valued Semantics for Canonical Labelled Calculi

We define a general family of canonical labelled calculi, of which many previously studied sequent and labelled calculi are particular instances. We then provide a uniform and modular method to obtain finite-valued semantics for every canonical labelled calculus by introducing the notion of partial non-deterministic matrices. The semantics is applied to provide simple decidable semantic criteria for two crucial syntactic properties of these calculi: (strong) analyticity and cut-admissibility. Finally, we demonstrate an application of this framework for a large family of paraconsistent logics.     

人工智能科学中的概率逻辑

人工智能科学,从其诞生之日起便与逻辑学密不可分。本文首先对逻辑学的分类、相互关系以及泛逻辑的概念等进行了讨论,并对人工智能中逻辑学的应用及发展进行了必要的分析。然后讲述了逻辑学与概率论两大理论基础之上的不确定性推理方法——概率逻辑,重点研究了二值概率逻辑与三值概率逻辑。最后阐述了概率逻辑在人工智能科学中的应用以及对它的思考。     

Toward a programming theory for rational agents

An important problem in agent verification is a lack of proper understanding of the relation between agent programs on the one hand and agent logics on the other. Understanding this relation would help to establish that an agent programming language is both conceptually well-founded and well-behaved, as well as yield a way to reason about agent programs by means of agent logics. As a step toward bridging this gap, we study several issues that need to be resolved in order to establish a precise mathematical relation between a modal agent logic and an agent programming language specified by means of an operational semantics. In this paper, we present an agent programming theory that provides both an agent programming language as well as a corresponding agent verification logic to verify agent programs. The theory is developed in stages to show, first, how a modal semantics can be grounded in a state-based semantics, and, second, how denotational semantics can be used to define the mathematical relation connecting the logic and agent programming language. Additionally, it is shown how to integrate declarative goals and add precompiled plans to the programming theory. In particular, we discuss the use of the concept of higher-order goals in our theory. Other issues such as a complete axiomatization and the complexity of decision procedures for the verification logic are not the focus of this paper and remain for future investigation. Part of this research was carried out while the first author was affiliated with the Nijmegen Institute for Cognition and Information, Radboud University Nijmegen.     

A Logic with Relative Knowledge Operators

We study a knowledge logic that assumes that to each set of agents, an indiscernibility relation is associated and the agents decide the membership of objects or states up to this indiscernibility relation. Its language contains a family of relative knowledge operators. We prove the decidability of the satisfiability problem, we show its EXPTIME-completeness and as a side-effect, we define a complete Hilbert-style axiomatization.     

Diversity of Agents and Their Interaction

Diversity of agents occurs naturally in epistemic logic, and dynamic logics of information update and belief revision. In this paper we provide a systematic discussion of different sources of diversity, such as introspection ability, powers of observation, memory capacity, and revision policies, and we show how these can be encoded in dynamic epistemic logics allowing for individual variation among agents. Next, we explore the interaction of diverse agents by looking at some concrete scenarios of communication and learning, and we propose a logical methodology to deal with these as well. We conclude with some further questions on the logic of diversity and interaction. This work was supported by the Chinese National Social Science Foundation (Grant Number: 04CZX011) and the Dutch Science Organization NWO.     

Uniform semantic treatment of default and autoepistemic logics

We revisit the issue of epistemological and semantic foundations for autoepistemic and default logics, two leading formalisms in nonmonotonic reasoning. We develop a general semantic approach to autoepistemic and default logics that is based on the notion of a belief pair and that exploits the lattice structure of the collection of all belief pairs. For each logic, we introduce a monotone operator on the lattice of belief pairs. We then show that a whole family of semantics can be defined in a systematic and principled way in terms of fixpoints of this operator (or as fixpoints of certain closely related operators). Our approach elucidates fundamental constructive principles in which agents form their belief sets, and leads to approximation semantics for autoepistemic and default logics. It also allows us to establish a precise one-to-one correspondence between the family of semantics for default logic and the family of semantics for autoepistemic logic. The correspondence exploits the modal interpretation of a default proposed by Konolige. Our results establish conclusively that default logic can be viewed as a fragment of autoepistemic logic, a result that has been long anticipated. At the same time, they explain the source of the difficulty to formally relate the semantics of default extensions by Reiter and autoepistemic expansions by Moore. These two semantics occupy different locations in the corresponding families of semantics for default and autoepistemic logics.     

An Optimal Decision Procedure for Right Propositional Neighborhood Logic

Propositional interval temporal logics are quite expressive temporal logics that allow one to naturally express statements that refer to time intervals. Unfortunately, most such logics turn out to be (highly) undecidable. In order to get decidability, severe syntactic or semantic restrictions have been imposed to interval-based temporal logics to reduce them to point-based ones. The problem of identifying expressive enough, yet decidable, new interval logics or fragments of existing ones that are genuinely interval-based is still largely unexplored. In this paper, we focus our attention on interval logics of temporal neighborhood. We address the decision problem for the future fragment of Neighborhood Logic (Right Propositional Neighborhood Logic, RPNL for short), and we positively solve it by showing that the satisfiability problem for RPNL over natural numbers is NEXPTIME-complete. Then, we develop a sound and complete tableau-based decision procedure, and we prove its optimality.     

Proving the Asymmetry Thesis Principles for a BDI Agent-Oriented Programming Language

In this paper, we consider each of the nine principles of BDI logics as defined by Rao and Georgeff based on Bratman's asymmetry thesis, and we verify which ones are satisfied by Rao's AgentSpeak(L), a computable logic language inspired by the BDI architecture for cognitive agents. This is in line with Rao's original motivation for defining AgentSpeak(L): to bridge the gap between the theory and practice of BDI agent systems. In order to set the grounds for the proof, we first introduce a particular way in which to define the informational, motivational, and deliberative modalities of BDI logics for AgentSpeak(L) agents, according to its structural operational semantics (that we introduced in a recent paper). This provides a framework that can be used to investigate further properties of AgentSpeak(L) agents, contributing towards giving firm theoretical grounds for BDI agent programming.     

First-Order Temporal Verification in Practice

First-order temporal logic, the extension of first-order logic with operators dealing with time, is a powerful and expressive formalism with many potential applications. This expressive logic can be viewed as a framework in which to investigate problems specified in other logics. The monodic fragment of first-order temporal logic is a useful fragment that possesses good computational properties such as completeness and sometimes even decidability. Temporal logics of knowledge are useful for dealing with situations where the knowledge of agents in a system is involved. In this paper we present a translation from temporal logics of knowledge into the monodic fragment of first-order temporal logic. We can then use a theorem prover for monodic first-order temporal logic to prove properties of the translated formulas. This allows problems specified in temporal logics of knowledge to be verified automatically without needing a specialized theorem prover for temporal logics of knowledge. We present the translation, its correctness, and examples of its use. Partially supported by EPSRC project: Analysis and Mechanisation of Decidable First-Order Temporal Logics (GR/R45376/01).     

Minimal Belief and Negation as Failure in Multi-Agent Systems

We propose an epistemic, nonmonotonic approach to the formalization of knowledge in a multi-agent setting. From the technical viewpoint, a family of nonmonotonic logics, based on Lifschitz's modal logic of minimal belief and negation as failure, is proposed, which allows for formalizing an agent which is able to reason about both its own knowledge and other agents' knowledge and ignorance. We define a reasoning method for such a logic and characterize the computational complexity of the major reasoning tasks in this formalism. From the practical perspective, we argue that our logical framework is well-suited for representing situations in which an agent cooperates in a team, and each agent is able to communicate his knowledge to other agents in the team. In such a case, in many situations the agent needs nonmonotonic abilities, in order to reason about such a situation based on his own knowledge and the other agents' knowledge and ignorance. Finally, we show the effectiveness of our framework in the robotic soccer application domain.