Epistemic Logic for Rule-Based Agents

The logical omniscience problem, whereby standard models of epistemic logic treat an agent as believing all consequences of its beliefs and knowing whatever follows from what else it knows, has received plenty of attention in the literature. But many attempted solutions focus on a fairly narrow specification of the problem: avoiding the closure of belief or knowledge, rather than showing how the proposed logic is of philosophical interest or of use in computer science or artificial intelligence. Sentential epistemic logics, as opposed to traditional possible worlds approaches, do not suffer from the problems of logical omniscience but are often thought to lack interesting epistemic properties. In this paper, I focus on the case of rule-based agents, which play a key role in contemporary AI research but have been neglected in the logical literature. I develop a framework for modelling monotonic, nonmonotonic and introspective rule-based reasoners which have limited cognitive resources and prove that the resulting models have a number of interesting properties. An axiomatization of the resulting logic is given, together with completeness, decidability and complexity results.     

An Interpretation of Default Logic in Minimal Temporal Epistemic Logic

When reasoning about complex domains, where information available is usually only partial, nonmonotonic reasoning can be an important tool. One of the formalisms introduced in this area is Reiter's Default Logic (1980). A characteristic of this formalism is that the applicability of default (inference) rules can only be verified in the future of the reasoning process. We describe an interpretation of default logic in temporal epistemic logic which makes this characteristic explicit. It is shown that this interpretation yields a semantics for default logic based on temporal epistemic models. A comparison between the various semantics for default logic will show the differences and similarities of these approaches and ours.     

Operational Concepts of Nonmonotonic Logics Part 2: Autoepistemic Logic

The subject of nonmonotonic reasoning is reasoning with incompleteinformation. One of the main approaches is autoepistemic logic inwhich reasoning is based on introspection. This paper aims at providing a smooth introduction to this logic,stressing its motivation and basic concepts. The meaning (semantics)of autoepistemic logic is given in terms of so-called expansionswhich are usually defined as solutions of a fixed-point equation. Thepresent paper shows a more understandable, operational method fordetermining expansions. By improving applicability of the basicconcepts to concrete examples, we hope to make a contribution to awider usage of autoepistemic logic in practical applications.     

Default reasoning and belief revision: A syntax-independent approach

As an important variant of Reiter‘s default logic.Poole(1988) developed a nonmonotonic reasoning framework in the classical first-order language,Brewka and Nebel extended Poole‘s approach in order to enable a representation of priorities between defaults.In this paper a general framework for default reasoning is presented,which can be viewed as a generalization of the three approaches above.It is proved that the syntax-independent default reasoning in this framework is identical to the general belief revision operation introduced by Zhang et al.(1997).This esult provides a solution to the problem whether there is a correspondence between belief revision and default logic for the infinite case .As a by-product,an answer to the the question,raised by Mankinson and Gaerdenfors(1991),is also given about whether there is a counterpart contraciton in nonmonotonic logic.     

'Classical' Negation in Nonmonotonic Reasoning and Logic Programming

Gelfond and Lifschitz were the first to point out the need for a symmetric negation in logic programming and they also proposed a specific semantics for such negation for logic programs with the stable semantics, which they called 'classical'. Subsequently, several researchers proposed different, often incompatible, forms of symmetric negation for various semantics of logic programs and deductive databases. To the best of our knowledge, however, no systematic study of symmetric negation in non-monotonic reasoning was ever attempted in the past. In this paper we conduct such a systematic study of symmetric negation. We introduce and discuss two natural, yet different, definitions of symmetric negation: one is called strong negation and the other is called explicit negation. For logic programs with the stable semantics, both symmetric negations coincide with Gelfond–Lifschitz' 'classical negation'. We study properties of strong and explicit negation and their mutual relationship as well as their relationship to default negation 'not', and classical negation '¬'. We show how one can use symmetric negation to provide natural solutions to various knowledge representation problems, such as theory and interpretation update, and belief revision. Rather than to limit our discussion to some narrow class of nonmonotonic theories, such as the class of logic programs with some specific semantics, we conduct our study so that it is applicable to a broad class of non-monotonic formalisms. In order to achieve the desired level of generality, we define the notion of symmetric negation in the knowledge representation framework of AutoEpistemic logic of Beliefs, introduced by Przymusinski.     

基于四值语义的缺省逻辑

基于公式变换,给出一组缺省理论的变换方法,将命题语言L中的缺省理论变换到对应的命题语言L^-＋中,保证了所得到的缺省理论的所有扩张均不平凡,并通过一种弱变换可同时保证缺省扩张的存在性．为缺省理论定义了各种四值模型,使得缺省逻辑具有非单调超协调推理能力,并证明了L^-＋中的缺省扩张与L中缺省理论的四值模型之间具有一一对应关系．四值模型描述了公式变换的语义,基于四值语义的缺省推理通过缺省理论的变换技术能在标准的缺省逻辑中实现．     

超协调限制逻辑

本文给出了一阶超协调限制逻辑ＬＰｓ的定义，并证明了它与悖论逻辑（ＬＰ与ＬＰｍ）和限制逻辑（ＣＩＲＣ）的关系，ＬＰ作为一种非单调超协调逻辑具有非单逻辑和超协调逻辑的优点，而用能解决非单调逻辑和超协调逻辑存在的问题，它可作为在不完全与不协调知识下常识推理的形式化，因此它的知识表示中具有广泛的应用。     

Uniform Closures: Order-Theoretically Reconstructing Logic Program Semantics and Abstract Domain Refinements

The notion of uniform closure operator is introduced, and it is shown how this concept surfaces in two different areas of application of abstract interpretation, notably in semantics design for logic programs and in the theory of abstract domain refinements. In logic programming, uniform closures permit generalization, from an order-theoretic perspective, of the standard hierarchy of declarative semantics. In particular, we show how to reconstruct the model-theoretic characterization of the well-known s-semantics using pure order-theoretic concepts only. As far as the systematic refinement operators on abstract domains are concerned, we show that uniform closures capture precisely the property of a refinement of being invertible, namely of admitting a related operator that simplifies as much as possible a given abstract domain of input for that refinement. Exploiting the same argument used to reconstruct the s-semantics of logic programming, we yield a precise relationship between refinements and their inverse operators: we demonstrate that they form an adjunction with respect to a conveniently modified complete order among abstract domains.     

逻辑函数的双逻辑综合与优化

针对传统布尔逻辑在电路面积优化中存在的不足,提出了一种用传统布尔逻辑和Reed-Muller(RM)逻辑相结合的双逻辑优化算法.通过将原逻辑函数的乘积项转化为不相交乘积项,并利用不相交乘积项的位操作,将逻辑函数的覆盖分成2个部分,使之分别适合布尔逻辑综合和RM逻辑综合;同时提出了适合双逻辑函数的逻辑功能验证方法.双逻辑优化算法用C语言编程实现并用MCNC标准电路进行测试.实验结果表明,与单一的布尔逻辑综合结果相比,在绝大多数情况下文中算法可使电路面积获得进一步优化.     

一个在弗协调逻辑中的限制

本文通过应用限制到一个弗协调逻辑给出一种弗协调限制，弗协调限制是一种弗协调非单调逻辑，它能被极小化语义所刻划，并具有两方面优点：非单调逻辑在包含矛盾时是不平凡的；弗协调逻辑在矛盾没有影响时等价于经典逻辑．     

Real Logic is Nonmonotonic

Charles Morgan has argued that nonmonotonic logic is ``impossible'. We show here that those arguments are mistaken, and that Morgan's preferred alternative, the representation of nonmonotonic reasoning by ``presuppositions' fails to provide a framework in which nonmonotonic reasoning can be constructively criticised. We argue that an inductive logic, based on probabilistic acceptance, offers more than Morgan's approach through presuppositions.     

基于描述逻辑的策略冲突检测方法研究及实现

采用基于策略的方法对安全管理、服务质量等进行监管,已经得到广泛应用。本文提供了一种基于描述逻辑的策略建模方式,将策略定义为两种类型,即授权策略和义务策略;建立策略相关的概念,结合概念之间的关系得到基于描述逻辑的策略模型。策略冲突会导致不一致的系统行为,是策略分析最重要的内容。本文深入研究了不同类型的策略 略冲突,在所建立的模型基础上提出了一套基于描述逻辑的策略冲突检测方法,并使用推理机Racer举例验证了这种检测方法。     

N-SHOQ(D): 描述逻辑SHOQ(D)的一个非单调扩展

描述逻辑SHOQ(D)给出了Web本体语言DAML+OIL的语义,但SHOQ(D)只能处理严格成立的完备 知识,不能处理在实际情况中经常出现的不完备知识.对描述逻辑SHOQ(D)进行扩展,提出了 能够处理不完备知识的非单调描述逻辑N-SHOQ(D).给出了N-SHOQ(D)的语法和语义,定义了N -SHOQ(D)中的蕴涵推理关系,研究了N-SHOQ(D)所具有的性质. N-SHOQ(D)为扩展DAML+OIL语 言到能够处理不完备知识的情形提供了语义支持.     

多智体系统时序认知规范的SPIN模型检测

SPIN模型检测器主要用来检测线性时序逻辑描述的规范,而多智体系统的规范采用时序认知逻辑描述比较方便。本文着重讨论了如何利用SPIN模型检测线性时序认知逻辑的方法,根据局部命题的理论,将模型检测知识算子和公共算子表述的规范规约为模型检测线性时序逻辑的问题,从而使SPIN的检测功能由线性时序逻辑扩充到线性时序认知逻辑。本文通过一个RPC协议分析实例来说明模型检测线性时序认知逻辑的方法。     

Nonmonotonic logic and temporal projection

Nonmonotonic formal systems have been proposed as an extension to classical first-order logic that will capture the process of human “default reasoning” or “plausible inference” through their inference mechanisms, just as modus ponens provides a model for deductive reasoning. But although the technical properties of these logics have been studied in detail and many examples of human default reasoning have been identified, for the most part these logics have not actually been applied to practical problems to see whether they produce the expected results.We provide axioms for a simple problem in temporal reasoning which has long been identified as a case of default reasoning, thus presumably amenable to representation in nonmonotonic logic. Upon examining the resulting nonmonotonic theories, however, we find that the inferences permitted by the logics are not those we had intended when we wrote the axioms, and in fact are much weaker. This problem is shown to be independent of the logic used; nor does it depend on any particular temporal representation. Upon analyzing the failure we find that the nonmonotonic logics we considered are inherently incapable of representing this kind of default reasoning.The first part of the paper is an expanded version of one that appeared in the 1986 AAAI proceedings. The second part reports on several responses to our result that have appeared since the original paper was published.     

逻辑函数的卡诺图化简法

从卡诺图化简法与公式化简法的比较入手,说明卡诺图化简法的优点及适用范围,阐述了卡诺图的特点、最小项的定义和性质、用卡诺图化简逻辑函数的基本原理以及化简是否达到最简形式的判定标准。然后给出了具体实例来诠释卡诺图化简法并给出其应用的一般步骤。最后总结出卡诺图化简法易出错的几种情况,从而得出用卡诺图化简逻辑函数的一般方法。     

一种分布式动态描述逻辑

分析了目前描述逻辑(DL)的研究现状和存在的问题,特别是动态描述逻辑(DDL)作为语义Web逻辑基础所存在的问题.针对语义Web的特点和需求,对DDL进行了扩充,提出了一种新的描述逻辑,即分布式动态描述逻辑(D3L),给出了D3L的语法和语义,并研究了D3L的推理机制,提出了两种推理方法: 直接推理和转化推理.与动态描述逻辑DDL相比,该D3L可以为语义Web提供更为合理的逻辑基础,弥补了DDL作为语义Web逻辑基础的不足.