Logic programs P and Q are strongly equivalent if, given any logic program R, programs P∪R and Q∪R are equivalent (that is, have the same answer sets). Strong equivalence is convenient for the study of equivalent transformations of logic programs: one can prove that a local change is correct without considering the whole program. Recently, Lifschitz, Pearce and Valverde showed that Heyting's logic of here-and-there can be used to characterize strong equivalence of logic programs. This paper offers a more direct characterization, and extends it to default logic. In their paper, Lifschitz, Pearce and Valverde study a very general form of logic programs, called ``nested'' programs. For the study of strong equivalence of default theories, it is convenient to introduce a corresponding ``nested'' version of default logic, which generalizes Reiter's default logic.
展开▼
