Propositional belief base update and minimal change

摘要

In this paper we examine ten concrete propositional update operations of the literature. We start by completely characterizing their relative strength and their computational complexity. Then we evaluate the competing update operations with respect to the postulates proposed by Katsuno and Mendelzon. It turns out that the majority violates most of the postulates. We argue that all violated postulates are undesirable except one. After that we evaluate the update operations with respect to another property which has been investigated extensively in the literature, viz. that disjunctive updates should not be identified with the exclusive disjunction. We argue that this is desirable, and show that the argument gives further support to the rejection of two of the postulates. Finally we study how the different approaches accommodate general laws governing the world, alias integrity constraints. Summing up our results, we conclude that only two of the update operations are satisfactory.