Prime forms and minimal change in propositional belief bases (Q622590)

The main purpose of this paper is to reconstruct the abstract theories of belief revision and update, as well as their instantiations using preference relations induced by Hamming-style distances, as accounts in which valuations are replaced by prime implicants of formulae as ``worlds''. The motivation is partly intuitive, partly computational. On the intuitive level, one may wish to deploy notions of distance and preference that are responsive to the logical power of the belief base under consideration, though not to its syntactic form. Computationally, prime implicants are smaller items than full valuations and fewer of them are needed. Execution of the first part of the project leads the authors to reformulate the familiar semantics of Grove and of Katsuno/Mendelzon for revision and update respectively, in terms of prime implicants. For the second part, they transform the Hamming-style notions of distance between valuations, originally introduced by Dalal (with a numerical ordering) and by Forbus (with a set-inclusion one), into analogous notions of distance between prime implicants, in such a way that the induced preference relations still satisfy the conditions demanded of them in the abstract semantics. They also define a variant of the numerical distance relation between prime implicants, via a ``holograph'' with dual prime implicates. A computational experiment is reported, comparing the various revision and update operations with respect to their performances on a collection of a hundred randomly chosen theories, each with twenty sentence letters and ninety-one clauses. Finally, comparisons are made with several other reconstructions of belief revision and update already in the literature, using prime implicants, prime implicates or BDDs.