Browse Prior Art Database

A Nonmonotonic Logic of Belief

IP.com Disclosure Number: IPCOM000128374D
Original Publication Date: 1988-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 16 page(s) / 41K

Publishing Venue

Software Patent Institute

Related People

Louise E. Moser: AUTHOR [+3]

Abstract

A nonmonotonic logic of belief based on a combined monotonic logic of knowledge and belief is presented. Unlike previous nonmonotonic logics of belief, our logic contains an unless operator by means of which preference for beliefs and refutation of those beliefs can be expressed, thereby providing for explicit representation of nonmonotonicity. A decision procedure based on Kripke structures for deciding validity of formulas in the logic is described and proved correct.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Nonmonotonic Logic of Belief

Louise E. Moser

Department of Computer Science University of California Santa Barbara, CA 93106

Abstract

A nonmonotonic logic of belief based on a combined monotonic logic of knowledge and belief is presented. Unlike previous nonmonotonic logics of belief, our logic contains an unless operator by means of which preference for beliefs and refutation of those beliefs can be expressed, thereby providing for explicit representation of nonmonotonicity. A decision procedure based on Kripke structures for deciding validity of formulas in the logic is described and proved correct.

I Introduction

The modal logic of knowledge 121, based on S5 modal logic, is quite well es-tablished and has been used to reason about complex properties of distributed systems [3]. Logics of belief, on the other hand, are less tractable. The most straightforward approach [2] involves weakening the knowledge logic by replac-ing the axiom that requires known propositions to be true with an axiom that requires propositions that are provably false not to be believed. While this gives a well-behaved modal logic known as KD45 [1], it does not accurately model our ntuitive concept of belief and does not easily model refutation of a belief by additional conflicting information.

Closer to what we need axe the nonmonotonic logics of belief [7,9,11,13,151-However, these logics, while they may be of use in their intended domain of Artificial Intelligence, fail to capture the essence of the concept of belief that is appropriate for our intended application axeas of distributed systems, fault tolerance, computer security, and other areas of Computer Science in which opti-mistic algorithms arise. In these areas, a belief is a predicate justified with a high degree of probability by arguments that lie outside the domain of the logic. Such arguments usually do not provide complete certainty, and frequently they permit the refutation of beliefs by other information. Nonmonotonic logics, which have the characteristic that established theorems may be invalidated when new axioms are introduced, thus are more appropriate for our intended application areas.

In our logic we wish to distinguish between beliefs of different agents and to reason about beliefs of propositions together with knowledge of propositions and primitive propositions. Thus, to denote that agent i believes proposition p, we prefix p with the belief operator Bi, as in Bi(p), and similarly Ki(p) for knowledge.

To provide nonmonotonicity in the logic, one might adopt an inference rule such as

(Equation Omitted)

University of California at Santa Barbara Page 1 Dec 31, 1988

Page 2 of 16

A Nonmonotonic Logic of Belief

which states that if proposition p is not provable, then agent i does not believe p. But this rule, when added to S5 or KD45, yields monotonic S5. Another objection is that the hypothesis that p is not provable d...