Presenting functors on many-sorted varieties and applications

This paper studies several applications of the notion of a presentation of a functor by operations and equations. We show that the technically straightforward generalisation of this notion from the one-sorted to the many-sorted case has several interesting consequences. First, it can be applied to give equational logic for the binding algebras modelling abstract syntax. Second, it provides a categorical approach to algebraic semantics of first-order logic. Third, this notion links the uniform treatment of logics for coalgebras of an arbitrary type T with concrete syntax and proof systems. Analysing the many-sorted case is essential for modular completeness proofs of coalgebraic logics.     

A more expressive formulation of many sorted logic

Many sorted logics can increase deductive efficiency by eliminating useless branches of the search space, but usually this results in reduced expressiveness. The many sorted logic described here has several unusual features which not only increase expressiveness but also can reduce the search space even more than a conventional many sorted logic. The quantifiers are unsorted: the restriction on the range of a variable derives from the argument positions of the nonlogical symbols that it occupies. Polymorphic sort specifications are allowed; thus statements usually requiring several assertions may be compactly expressed by a single assertion. The sort structure may be an arbitrary lattice and the sort of a term can be more general than the sort of the argument position it occupies. It is also shown how it is sometimes possible to use sort information to determine the truth value of a formula without resort normal inference. Inference rules for a resolution based system are discussed; these can be proved to be sound and complete.     

Decidable fragments of many-sorted logic

Many natural specifications use types. We investigate the decidability of fragments of many-sorted first-order logic. We identified some decidable fragments and illustrated their usefulness by formalizing specifications considered in the literature. Often the intended interpretations of specifications are finite. We prove that the formulas in these fragments are valid iff they are valid over the finite structures. We extend these results to logics that allow a restricted form of transitive closure.     

Rasiowa–Sikorski deduction systems in computer science applications

A Rasiowa-Sikorski system is a sequence-type formalization of logics. The system uses invertible decomposition rules which decompose a formula into sequences of simpler formulae whose validity is equivalent to validity of the original formula. There may also be expansion rules which close indecomposable sequences under certain properties of relations appearing in the formulae, like symmetry or transitivity. Proofs are finite decomposition trees with leaves having “fundamental”, valid labels. The author describes a general method of applying the R-S formalism to develop complete deduction systems for various brands of C.S and A.I. logic, including a logic for reasoning about relative similarity, a three-valued software specification logic with McCarthy's connectives and Kleene quantifiers, a logic for nondeterministic specifications, many-sorted FOL with possibly empty carriers of some sorts, and a three-valued logic for reasoning about concurrency.     

Towards Behavioral Maude: Behavioral Membership Equational Logic

How can algebraic and coalgebraic specifications be integrated? How can behavioral equivalence be addressed in an algebraic specification language? The hidden-sorted approach, originating in work of Goguen and Meseguer in the early 80's, and further developed into the hidden-sorted logic approach by researchers at Oxford, UC San Diego, and Kanazawa offers some attractive answers, and has been implemented in both BOBJ and CafeOBJ. In this work we investigate both further extensions of hidden logic, and an extension of the Maude specification language called BMaude supporting this extended hidden-sorted semantics.Maude's underlying equational logic, membership equational logic, generalizes and increases the expressive power of many-sorted and order-sorted equational logics. We develop a hidden-sorted extension of membership equational logic, and give conditions under which theories have both an algebraic and a coalgebraic semantics, including final (co-)algebras. We also discuss the language design of BMaude, based on such an extended logic and using categorical notions in and across the different institutions involved. We also explain how Maude's reflective semantics provides a systematic method to extend Maude to BMaude within Maude, including module composition operations, evaluation, and automated proof methods.     

Using Many-Sorted Logic in the Object-Oriented Data Model for Fast Robot Task Planning

Search space explosion is a critical problem in robot task planning. This problem limits current robot task planners to solve only simple block world problems and task planning in a real robot working environment to be impractical. This problem is mainly due to the lack of utilization of domain information in task planning. In this paper, we describe a fast task planner for indoor robot applications that effectively uses domain information to speed up the planning process. In this planner, domain information is explicitly represented in an object-oriented data model (OODM) that uses many-sorted logic (MSL) representation. The OODM is convenient for the management of complex data and many-sorted logic is effective for pruning in the rule search process. An inference engine is designed to take advantage of the salient features of these two techniques for fast task planning. A simulation example and complexity analysis are given to demonstrate the advantage of the proposed task planner.     

纤维逻辑

形式逻辑已经从简单命题逻辑发展到比较复杂的模态逻辑系列。但是在主体环境下,已有逻辑的复杂性仍然不能有效刻画主体复杂的心智。有一些人工智能研究者根据主体心智的多重性,在模态逻辑中引入多种模态算子,并借此对主体加以刻画。但是原来的可能世界语义却难以容纳如此复杂的语法,出现了很多不合理的地方。本文首先介绍了新近出现的纤维逻辑（fibring logics）,然后归纳了目前将此理论应用在主体BDI建模的研究现状,最后分析纤维逻辑的不足之处,讨论了其他可能的应用,并对今后的工作做了展望。     

国家知识基础设施中的数学知识表示

数学知识表示是知识表示中的一个重要方面,是数学知识检索、自动定理机器证明、智能教学系统等的基础.根据在设计NKI(national knowledge infrastructure)的数学知识表示语言中遇到的问题,并在讨论了数学对象的本体论假设的基础上提出了两种数学知识的表示方法:一种是以一个逻辑语言上的公式为属性值域的描述逻辑;另一种是以描述逻辑描述的本体为逻辑语言的一部分的一阶逻辑.在前者的表示中,如果对公式不作任何限制,那么得到的知识库中的推理不是可算法化的;在后者的表示中,以描述逻辑描述的本体中的推理是可算法化的,而以本体为逻辑语言的一部分的一阶逻辑所表示的数学知识中的推理一般是不可算法化的.因此,在表示数学知识时,需要区分概念性的知识(本体中的知识)和非概念性的知识(用本体作为语言表示的知识).框架或者描述逻辑可以表示和有效地推理概念性知识,但如果将非概念性知识加入到框架或知识库中,就可能使得原来可以有效推理的框架所表示的知识库不存在有效的推理算法,甚至不存在推理算法.为此,建议在表示数学知识时,用框架或描述逻辑来表示概念性知识;然后,用这样表示的知识库作为逻辑语言的一部分,以表示非概念性知识.     

Converting untyped formulas to typed ones

We observe that every first-order logic formula over the untyped version of some many-sorted vocabulary is equivalent to a union of many-sorted formulas over that vocabulary. This result has as direct corollary a theorem by Hull and Su on the expressive power of active-domain quantification in the relational calculus. Received: 1 April 1998     

基于并行处理环境的多类命题动态逻辑系统

本文提出了一个描述并行处理环境下程序动态特性的多类命题动态逻辑和多类结构，并使用ＭＰＤＬ描述一个实际问题。本文使用了新算子Ｇ＾ｉｊ来描述并行程序间的关系，最后，本文简单地讨论了ＭＰＤＬ的一致性和完备性。     

普适计算隐私保护策略研究

普适计算环境中,用户的隐私保护意志可以通过让用户自己制定隐私信息的访问控制策略(隐私策略)而得到实现,研究隐私策略的统一表示及其执行机制可以有效地解决隐私策略的多样性问题.文中使用多类逻辑和描述逻辑,建立了隐私策略模型和隐私策略公理,提出了隐私规则知识库的概念,给出了隐私策略的逻辑推理方法.在此之上,从应用的角度,定义了隐私策略本体,提出了隐私规则的执行流程.通过规则引擎,验证了隐私规则的有效性和可用性.     

Annotated Logic Applications for Imperfect Information

Imperfect information is a very general term that comprises different types of information, such as uncertain, vague, fuzzy, inconsistent, possibilistic, probabilistic, partially or totally incomplete information [2]. In the literature of knowledge representation we find a different formal model for each one of these distinct types. For example, annotated logic is a formal model to represent inconsistent information.Annotated logics are non-classical logics introduced in [20] as a logic programming theory. They were proved to be paraconsistent. Based on [5], we present in this work the annotated logic programming theory and some of its applications in Artificial Intelligence (AI). We present it as a formalism to reason with inconsistent information and investigate its possibility to represent other types of imperfect information, such as possibilistic and non-monotonic reasoning. Our main goal is to verify and confirm the importance of annotated logics as a tool for developing knowledge-based and automated reasoning systems in AI.     

Epistemic logic and logical omniscience II: A unifying framework

In a published paper entitled Epistemic Logic and Logical Omniscience: A Survey (Int J Intell Syst 1997, 12, 57–81) a collection of epistemic logics were reviewed and critiqued. This sequel paper provides evidence for the claim that a unifying framework for various existing epistemic logics can be defined. Of particular interest is the logic of implicit and explicit belief, the logic of awareness, and the Cadoli–Schaerf epistemic model. Although these logics appear to have surface dissimilarities, a closer examination shows that they have a strong resemblance. The contribution of this paper is to show that a unifying framework MEL (multi‐valued epistemic logic) that integrates the features of these three logics can be defined. In this paper, it is proven that the semantics of MEL subsumes the semantics of the logic of implicit and explicit belief, the logic of awareness, and the Cadoli–Schaerf epistemic model. By placing some constraints on MEL , various epistemic notions such as implicit belief, explicit belief, and awareness can be modeled. ©2000 John Wiley & Sons, Inc.     

对象语义约束检验系统的设计和实现

我们使用一阶谓词逻辑公式表示对象的语义约束，即对象结构特片和操作行为特征约束，这些逻辑公式必须保证是一致的，并且对象在其演变的历史过程中必须满足对象约束，本文介绍一个对象语义约束检验系统。     

A Many-Sorted Natural Deduction

The goal of this paper is to motivate and define yet another sorted logic, called SND. All the previous sorted logics that can be found in the Artificial Intelligence literature have been designed to be used in (completely) automated deduction . SND has been designed to be used in interactive theorem proving. Because of this shift of focus, SND has been designed to satisfy three innovative design requirements: it is defined on top of a natural deduction calculus, and in a way to be a definitional extension of such calculus; and it is implemented on top of its implementation. In turn, because of this fact, SND has various innovative technical properties; among them: it allows us to deal with free variables, it has no notion of well-sortedness and of well-sortedness being a prerequisite of well-formedness, its implementation is such that, in the default mode, the system behaves exactly as with the original unsorted calculus.     

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).     

Goedel语言类型系统

Goedel语言是一种说明性逻辑程序设计语言。该语言基于一阶逻辑，引入了一个多态多类的类型系统和多种新的语言成分，支持抽象数据类型和模块化程序设计等技术，语言本身也具有很强的说明性语义。详细介绍了Goedel语言的类型系统及其构造，对在逻辑程序设计语言中引入类型系统的作用进行了一些深入的分析和讨论。     

带函数的描述逻辑

描述逻辑是包含了概念、角色以及概念和角色构造子的一阶逻辑的子逻辑,具有表达能力强且推理可判定的特征。但现有描述逻辑无法表示概念和角色上的函数,因此在图书馆的概念模型中,有一些问题便不能表示,如图书的本数、借书的条目数等。在现有描述逻辑基础上引入函数来解决这个问题。首先分析现有描述逻辑在图书馆的概念模型中不能表示的一些问题并提出解决方法,然后给出带函数的描述逻辑的语法和形式语义,最后用带函数的描述逻辑形式化表示图书馆概念模型中的一些实际问题。