超协调限制逻辑

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

Reasoning about Minimal Knowledge in Nonmonotonic Modal Logics

We study the problem of embedding Halpern and Moses's modal logic of minimal knowledge states into two families of modal formalism for nonmonotonic reasoning, McDermott and Doyle's nonmonotonic modal logics and ground nonmonotonic modal logics. First, we prove that Halpern and Moses's logic can be embedded into all ground logics; moreover, the translation employed allows for establishing a lower bound (3p) for the problem of skeptical reasoning in all ground logics. Then, we show a translation of Halpern and Moses's logic into a significant subset of McDermott and Doyle's formalisms. Such a translation both indicates the ability of Halpern and Moses's logic of expressing minimal knowledge states in a more compact way than McDermott and Doyle's logics, and allows for a comparison of the epistemological properties of such nonmonotonic modal formalisms.     

A generalization of the Lin-Zhao theorem

The theorem on loop formulas due to Fangzhen Lin and Yuting Zhao shows how to turn a logic program into a propositional formula that describes the program’s stable models. In this paper we simplify and generalize the statement of this theorem. The simplification is achieved by modifying the definition of a loop in such a way that a program is turned into the corresponding propositional formula by adding loop formulas directly to the conjunction of its rules, without the intermediate step of forming the program’s completion. The generalization makes the idea of a loop formula applicable to stable models in the sense of a very general definition that covers disjunctive programs, programs with nested expressions, and more.     

Modal nonmonotonic logics demodalized

The study of the relation between default logic and modal nonmonotonic logics has been mostly concerned with the task of translating default logic to autoepistemic or some other modal nonmonotonic logic. Here, we discuss the reverse problem, that is, the possibility of translating modal nonmonotonic logics into default-type systems formulated in the language without modal operators. To this end, we first consider a reformulation of both formalisms in terms of what we call default consequence relations. These consequence relations turn out to be especially suitable for studying default and modal nonmonotonic reasoning. We show, in particular, that different kinds of such reasoning naturally correspond to different structural rules imposed on default consequence relations. Our main results also demonstrate that all modal nonmonotonic objects considered have exact nonmodal counterparts. As an immediate consequence of these results, we obtain a method of reducing common types of modal nonmonotonic reasoning to nonmodal default reasoning.     

Negation as Failure as Resolution

Providing a clean procedural semantics of the Negation As Failure rule in Logic Programming has been an open problem for some time now. This rule has been treated as a technique in nonmonotonic reasoning, not as a rule in classical logic. This paper contains a demonstration of the negation as failure rule as a resolution procedure in first-order logic. We present a sound and complete resolution scheme for negation as failure rule for the larger class of constraint logic programs. The approach is to consider a canonical partition of the completion of a definite (constraint) program into the IF and the FI programs. We show that a negated goal, provable from the completed definite program is provable from just the FI part. The clauses in this program have a structure dual to that of definite Horn clauses. We describe a sound and complete linear resolution rule for this fragment, and show that a resolution proof of the negated goal from the FI part corresponds to a finite failure tree resulting from classical linear resolution applied to the goal on the If part of the original definite program. Our work shows that negation as failure rule can be computationally efficient in the sense that the SLD-resolution on the If part of a definite program along with the negation as failure rule is more efficient than a direct resolution procedure on the completion of that program.     

计算机科学中的一些逻辑理论的推理性质研究

由于一阶 词逻辑的基本特征是具有可靠性,完全性,在推广一阶谓词逻辑表达能力及扩充其推理能力时,可以定义了了一些具有可靠性,完全性的逻辑,对此,在分析逻辑理论特征的基础上,给出了一些逻辑的推理系统之间相似性的实质,证明这些逻辑在实质上并不能扩充一阶谓词逻辑的推理能力,并指出非常单调推理中的缺省推理及限定推理所采用的技术是扩充时必需的。     

Propositional semantics for disjunctive logic programs

In this paper we study the properties of the class of head-cycle-free extended disjunctive logic programs (HEDLPs), which includes, as a special case, all nondisjunctive extended logic programs. We show that any propositional HEDLP can be mapped in polynomial time into a propositional theory such that each model of the latter corresponds to an answer set, as defined by stable model semantics, of the former. Using this mapping, we show that many queries over HEDLPs can be determined by solving propositional satisfiability problems. Our mapping has several important implications: It establishes the NP-completeness of this class of disjunctive logic programs; it allows existing algorithms and tractable subsets for the satisfiability problem to be used in logic programming; it facilitates evaluation of the expressive power of disjunctive logic programs; and it leads to the discovery of useful similarities between stable model semantics and Clark's predicate completion.     

Yet some more complexity results for default logic

We identify several new tractable subsets and several new intractable simple cases for reasoning in the propositional version of Reiter's default logic. The majority of our findings are related to brave reasoning. By making some intuitive observations, most classes that we identify can be derived quite easily from some subsets of default logic already known in the literature. Some of the subsets we discuss are subclasses of the so-called “extended logic programs”. All the tractable subsets presented in this paper can be recognized in linear time.     

Logics to formalise p-adic valued probability and their applications

Abstract

In this paper, we focus on the main results which we have developed to obtain different propositional logics for reasoning about p-adic valued probabilities. Each of these logics is a sound, complete, and decidable extension of classical propositional logic. Also, we show some applications of these logics in modelling cognitions.     

The universe of propositional approximations

The idea of approximate entailment has been proposed by Schaerf and Cadoli [Tractable reasoning via approximation, Artif. Intell. 74(2) (1995) 249–310] as a way of modelling the reasoning of an agent with limited resources. In that framework, a family of logics, parameterised by a set of propositional letters, approximates classical logic as the size of the set increases.     

Strong and uniform equivalence of nonmonotonic theories – an algebraic approach

We show that the concepts of strong and uniform equivalence of logic programs can be generalized to an abstract algebraic setting of operators on complete lattices. Our results imply characterizations of strong and uniform equivalence for several nonmonotonic logics including logic programming with aggregates, default logic and a version of autoepistemic logic. This work was partially supported by the NSF grant IIS-0325063.     

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

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

A causal approach to nonmonotonic reasoning

We introduce logical formalisms of production and causal inference relations based on input/output logics of Makinson and Van der Torre [J. Philos. Logic 29 (2000) 383–408]. These inference relations will be assigned, however, both standard semantics (giving interpretation to their rules), and natural nonmonotonic semantics based on the principle of explanation closure. The resulting nonmonotonic formalisms will be shown to provide a logical representation of abductive reasoning, and a complete characterization of causal nonmonotonic reasoning from McCain and Turner [Proc. AAAI-97, Providence, RI, 1997, pp. 460–465]. The results of the study suggest production and causal inference as general nonmonotonic formalisms providing an alternative representation for a significant part of nonmonotonic reasoning.