Forgetting in logic programs

Abstract

Forgetting is an operation which removes information from a set of logical statements, such that a) the language used by the logic is simplified; and b) as much information as possible from the original logical statements are preserved. Forgetting operations are useful in a variety of contexts, including knowledge representation, where it is necessary to have an operation for removing information from knowledge bases; and the problem of relevance, where logical statements are simplified by removing irrelevant information. In this thesis we consider forgetting operations on logic programs with negation-as-failure according to the stable model semantics.

There are existing notions of forgetting on logic programs in the literature: the strong forgetting and weak forgetting of Zhang and Foo, and the semantic approach to forgetting introduced by Wang et al. However, these notions are inadequate: the strong and weak forgettings are defined syntactically with no obvious connections to semantic notions of forgetting; while the semantic approach of Wang et al. does not take into account ``hidden'' information encoded in unused rules.

The idea of equivalence on logic programs capture the extent of information contained in a logic program. We consider that two logic programs are equivalent iff the two programs contain the same information. For logic programs, there are many different possible notions of equivalence. We look at the well-known notion of strong equivalence and a new notion of equivalence which we call T-equivalence. Associated with each of these equivalences is a consequence relation on logic program rules. We present sound and complete set of inference rules for both consequence relations.

We present a novel approach to logic program forgetting which uses as its basis a set of postulates, which are defined relative to a notion of equivalence. We show that if we use T-equivalence as the equivalence relation, then the only possible forgetting operations (up to equivalence) are strong forgetting and weak forgetting. If strong equivalence is used instead, then there are also only two possible forgetting operations (up to equivalence).