A Deduction Model Of Belief and Its Logics

Abstract

Reasoning about the knowledge and beliefs of computer and human agents is assuming increasing importance in artificial intelligence systems for natural language, understanding, planning, and knowledge representation. A natural model of belief for robot agents is the deduction model: an agent is represented as having an initial set of beliefs about the world in some internal language and a deduction process for deriving some (but not necessarily all) logical consequences of these beliefs. Because the deduction model is explicitly computational model, it is possible to take into account limitations of an agent’s resources when reasoning. This thesis is an investigation of a Gentzen-type formalization of the deductive model of belief. Several original results are proved. Among these are soundness and completeness theorems for a deductive belief logic; a correspondence result that relates our deduction model to competing possible-world models; and a model analog to Herbrand’s Theorem for the belief logic. Specialized techniques for automatic deduction based on resolution are developed using this theorem. Several other topics of knowledge and belief are explored in the thesis from the viewpoint of the deduction model, including:

• A theory of introspection about self-beliefs
• A theory of circumscriptive ignorance, in which facts that an agent doesn’t know are formalized by limiting or circumscribing the information available to him.

This report is a slightly revised version of a thesis submitted to the Department of Computer Science at Stanford University in June 1984, in partial fulfillment of the requirements for the degree of Doctor of Philosophy.