Ordering Default Theories

Abstract

In first-order logic, a theory T 1 is considered stronger than another theory T 2 if every formula derived from T 2 is also derived from T1. Such an order relation is useful to know relative value between different theories. In the context of default logic, a theory contains default information as well as definite information. To order default theories, it is necessary to assess the information content of a default theory. To this end, we introduce a multi-valued interpretation of default theories based on a nine-valued bilattice. It distinguishes definite and credulous/skeptical default information derived from a theory, and is used for ordering default theories based on their information contents. The technique is also applied to order nonmonotonic logic programs. The results of this paper provide a method for comparing different default theories and have important application to learning nonmonotonic theories.