Paraconsistent Declarative Semantics for Extended Logic Programs

We introduce a fixpoint semantics for logic programs with two kinds of negation: an explicit negation and a negation-by-failure. The programs may also be prioritized, that is, their clauses may be arranged in a partial order that reflects preferences among the corresponding rules. This yields a robust framework for representing knowledge in logic programs with a considerable expressive power. The declarative semantics for such programs is particularly suitable for reasoning with uncertainty, in the sense that it pinpoints the incomplete and inconsistent parts of the data, and regards the remaining information as classically consistent. As such, this semantics allows to draw conclusions in a non-trivial way, even in cases that the logic programs under consideration are not consistent. Finally, we show that this formalism may be regarded as a simple and flexible process for belief revision.     

Classical negation in logic programs and disjunctive databases

An important limitation of traditional logic programming as a knowledge representation tool, in comparison with classical logic, is that logic programming does not allow us to deal directly with incomplete information. In order to overcome this limitation, we extend the class of general logic programs by including classical negation, in addition to negation-as-failure. The semantics of such extended programs is based on the method of stable models. The concept of a disjunctive database can be extended in a similar way. We show that some facts of commonsense knowledge can be represented by logic programs and disjunctive databases more easily when classical negation is available. Computationally, classical negation can be eliminated from extended programs by a simple preprocessor. Extended programs are identical to a special case of default theories in the sense of Reiter.     

A new approach to hybrid probabilistic logic programs

This paper presents a novel revision of the framework of Hybrid Probabilistic Logic Programming, along with a complete semantics characterization, to enable the encoding of and reasoning about real-world applications. The language of Hybrid Probabilistic Logic Programs framework is extended to allow the use of non-monotonic negation, and two alternative semantical characterizations are defined: stable probabilistic model semantics and probabilistic well-founded semantics. These semantics generalize the stable model semantics and well-founded semantics of traditional normal logic programs, and they reduce to the semantics of Hybrid Probabilistic Logic programs for programs without negation. It is the first time that two different semantics for Hybrid Probabilistic Programs with non-monotonic negation as well as their relationships are described. This proposal provides the foundational grounds for developing computational methods for implementing the proposed semantics. Furthermore, it makes it clearer how to characterize non-monotonic negation in probabilistic logic programming frameworks for commonsense reasoning. An erratum to this article can be found at     

Computing change and specificity with equational logic programs

Recent deductive approaches to reasoning about action and chance allow us to model objects and methods in a deductive framework. In these approaches, inheritance of methods comes for free, whereas overriding of methods is unsupported. In this paper, we present an equational logic framework for objects, methods, inheritance and overriding of methods. Overriding is achieved via the concept of specificity, which states that more specific methods are preferred to less specific ones. Specificity is computed with the help of negation as failure. We specify equational logic programs and show that their completed versions behave as intended. Furthermore, we prove that SLDENF-resolution is complete if the equational theory is finitary, the completed programs are consistent and no derivation flounders or is infinite. Moreover, we give syntactic conditions which guarantee that no derivation flounders or is infinite. Finally, we discuss how the approach can be extended to reasoning about the past in the context of incompletely specified objects or situations. It will turn out that constructive negation is needed to solve these problems.     

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

Formalizing Default Reasoning

Fuzzy set systems can be used to solve the problem with uncertain knowledge,and default logic can be used to solve the problem with incomplete knowledge,in some sense.In this paper,based on interval-valued fuzzy sets we introduce a method of inference which combines approximate reasoning an default ogic,and give the procedure of transforming monotonic reasoning into default reasoning.     

一类具有3种否定的模糊模态命题逻辑

对不同否定知识的认知、区分、表达、推理及计算是模糊知识研究处理的一个基础。具有矛盾否定、对立否定和中介否定的模糊命题逻辑形式系统FLCOM是一种能够完整描述模糊知识中的不同否定及其关系与规律的理论。基于FLCOM和中介模态命题逻辑MK,提出一类具有3种否定的模糊模态命题逻辑MKCOM及其扩充系统MTCOM,MS₄COM和MS₅COM;讨论了MKCOM的语义和语法解释,并证明了MKCOM的可靠性定理和完备性定理。     

DEFAULT LOGICS: A UNIFIED VIEW

Default logic has been introduced for handling reasoning with incomplete knowledge. It has been widely studied, and various definitions have been proposed for it. Most of the variants have been defined by means of fixed points of some operator. We propose here another approach, which is based on a study of the way in which general rules with exceptions, used in a default reasoning process, can contradict one another. We then isolate sets of noncontradicting rules, as large as possible in order to exploit as much information as possible, and construct, for each of these sets of rules, the set of conclusions that can be deduced from it. We show that our framework encompasses most of the existing variants of default logic, allowing those variants to be compared from a knowledge representation point of view. Our approach also enables us to provide an operational definition of extensions in some interesting cases. Proof-theoretical and semantical aspects are investigated.     

Complete logic programs with domain-closure axiom

Complete logic programs augmented with the domain-closure axiom are proposed as the reference theory for logic programming with negation as failure. An inference rule corresponding to “proof by case analysis” is proved correct within this framework. As a major consequence, the completeness results for SLD resolution and negation as failure still hold. An interesting outcome is that some novel operational properties of SLD resolution can be proved.     

Reasoning in inconsistent knowledge bases

Databases and knowledge bases could be inconsistent in many ways. For example, during the construction of an expert system, we may consult many different experts. Each expert may provide us with a group of rules and facts which are self-consistent. However, when we coalesce the facts and rules provided by these different experts, inconsistency may arise. Alternatively, knowledge bases may be inconsistent due to the presence of some erroneous information. Thus, a framework for reasoning about knowledge bases that contain inconsistent information is necessary. However, existing frameworks for reasoning with inconsistency do not support reasoning by cases and reasoning with the law of excluded middle (“everything is either true or false”). In this paper, we show how reasoning with cases, and reasoning with the law of excluded middle may be captured. We develop a declarative and operational semantics for knowledge bases that are possibly inconsistent. We compare and contrast our work with work on explicit and non-monotonic modes of negation in logic programs and suggest under what circumstances one framework may be preferred over another     

ANGLE: An autonomous, normative and guidable agent with changing knowledge

Some emerging computing systems (especially autonomic computing systems) raise several challenges to autonomous agents, including (1) how to reflect the dynamics of business requirements, (2) how to coordinate with external agents with sufficient level of security and predictability, and (3) how to perform reasoning with dynamic and incomplete knowledge, including both informational knowledge (observations) and motivational knowledge (for example, policy rules and contract rules). On the basis of defeasible logic and argumentation, this paper proposes an autonomous, normative and guidable agent model, called ANGLE, to cope with these challenges. This agent is established by combining beliefs-desires-intentions (BDI) architecture with policy-based method and the mechanism of contract-based coordination. Its architecture, knowledge representation, as well as reasoning and decision-making, are presented in this paper. ANGLE is characteristic of the following three aspects. First, both its motivational knowledge and informational knowledge are changeable, and allowed to be incomplete, inconsistent/conflicting. Second, its knowledge is represented in terms of extended defeasible logic with modal operators. Different from the existing defeasible theories, its theories (including belief theory, goal theory and intention theory) are dynamic (called dynamic theories), reflecting the variations of observations and external motivational knowledge. Third, its reasoning and decision-making are based on argumentation. Due to the dynamics of underlying theories, argument construction is not a monotonic process, which is different from the existing argumentation framework where arguments are constructed incrementally.     

Graph theoretical structures in logic programs and default theories

In this paper we present a graph representation of logic programs and default theories. We show that many of the semantics proposed for logic programs with negation can be expressed in terms of notions emerging from graph theory, establishing in this way a link between the fields. Namely the stable models, the partial stable models, and the well-founded semantics correspond respectively to the kernels, semikernels and the initial acyclic part of an associated graph. This link allows us to consider both theoretical (existence, uniqueness) and computational problems (tractability, algorithms, approximations) from a more abstract and rather combinatorial point of view. It also provides a clear and intuitive understanding about how conflicts between rules are resolved within the different semantics. Furthermore, we extend the basic framework developed for logic programs to the case of Default Logic by introducing the notions of partial, deterministic and well-founded extensions for default theories. These semantics capture different ways of reasoning with a default theory.     

Semantic forgetting in answer set programming

The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.     

Possibilistic uncertainty handling for answer set programming

In this work, we introduce a new framework able to deal with a reasoning that is at the same time non monotonic and uncertain. In order to take into account a certainty level associated to each piece of knowledge, we use possibility theory to extend the non monotonic semantics of stable models for logic programs with default negation. By means of a possibility distribution we define a clear semantics of such programs by introducing what is a possibilistic stable model. We also propose a syntactic process based on a fix-point operator to compute these particular models representing the deductions of the program and their certainty. Then, we show how this introduction of a certainty level on each rule of a program can be used in order to restore its consistency in case of the program has no model at all. Furthermore, we explain how we can compute possibilistic stable models by using available softwares for Answer Set Programming and we describe the main lines of the system that we have developed to achieve this goal.     

High-level Petri net model of logic program with negation

The formalism of nonmonotonic reasoning has been integrated into logic programming to define semantics for logic program with negation. Because a Petri net provides a uniform model for both the logic of knowledge and the control of inference, the class of high-level Petri nets called predicate/transition nets (PrT-nets) has been employed to study production rule based expert systems and Horn clause logic programs. We show that a PrT-net can implement the nonmonotonicity associated with a logic program with negation as well as the monotonicity of Horn clause logic program. In particular, we define a semantics for a normal logic program and implement it with PrT-net. We demonstrate that in the presence of inconsistency in a normal logic program, the semantics still works well by deducing meaningful answers. The variations and potential applications of the PrT-net are also addressed     

Diagnosis and decision making in normative reasoning

Diagnosis theory reasons about incomplete knowledge and only considers the past. It distinguishes between violations and non-violations. Qualitative decision theory reasons about decision variables and considers the future. It distinguishes between fulfilled goals and unfulfilled goals. In this paper we formalize normative diagnoses and decisions in the special purpose formalism DIO(DE)² as well as in extensions of the preference-based deontic logic PDL. The DIagnostic and DEcision-theoretic framework for DEontic reasoning DIO(DE)² formalizes reasoning about violations and fulfillments, and is used to characterize the distinction between normative diagnosis theory and (qualitative) decision theory. The extension of the preference-based deontic logic PDL shows how normative diagnostic and decision-theoretic reasoning — i.e. reasoning about violations and fulfillments — can be formalized as an extension of deontic reasoning.     

A logic-based calculus of events

We outline an approach for reasoning about events and time within a logic programming framework. The notion of event is taken to be more primitive than that of time and both are represented explicitly by means of Horn clauses augmented with negation by failure. The main intended applications are the updating of databases and narrative understanding. In contrast with conventional databases which assume that updates are made in the same order as the corresponding events occur in the real world, the explicit treatment of events allows us to deal with updates which provide new information about the past. Default reasoning on the basis of incomplete information is obtained as a consequence of using negation by failure. Default conclusions are automatically withdrawn if the addition of new information renders them inconsistent. Because events are differentiated from times, we can represent events with unknown times, as well as events which are partially ordered and concurrent.     

基于优先解释的不完全信息推理及其应用

不完全信息下的近似推理是知识工程面临的困难问题之一.文章提出了一种具有非单调性质的优先逻辑程序理论.该理论能够对知识的解释进行综合评判,进而优选解释,使其成为现有知识的最佳理论逼近,达到在择优意义下的理论完全化,避免了对知识的完全性及一致性要求.为获取应用领域的优先逻辑程序,基于归纳逻辑程序设计技术设计了一种多方法归纳学习算法,该算法具有较强的归纳能力.此理论与算法已应用在863农业专家系统中,并获得满意结果.