Characterization of Strongly Equivalent Logic Programs in Intermediate Logics
Lex Hendriks, Dick de Jongh

Abstract:
The non-classical, nonmonotonic inference relation associated with the
stable model semantics for logic programs gives rise to a relationship
of {\em strong equivalence} between logical programs that can be
verified in the 3-valued G\"odel logic, {\bf G3}, the strongest
non-classical intermediate propositional logic (see~\cite{lpv}). In
this paper we will show that {\bf KC} (the logic of $\neg
p\vee\neg\neg p$) is the weakest intermediate logic for which strongly
equivalent logic programs in a language allowing negations are
logically equivalent.