The Logical Difference Between Propositional Horn Theories

Abstract

The logical difference between knowledge bases is an important issue for the dynamic update of knowledge base. Computing the logical difference for knowledge bases is intractable in general, and its result is not necessarily category in the sense that the logical difference between two theories in a class is possibly not in the same class any more. This paper proves that computing logical difference between Horn theories is easier than that of CNF theories, and its result is still Horn expressible, though some deciding problems relating to logical difference are still intractable for Horn theories. A preliminary experiment illustrates an interesting phenomenon for the size of logical differences.