Safe beliefs for propositional theories

We prove that, in particular, intuitionistic logic can be replaced with any other proper intermediate logic without modifying the resulting semantics. We also show that the answer set semantics satisfies an important property, the “extension by definition”, that can be used to construct program translations. As a result we are able to provide a polynomial translation from propositional theories into the class of disjunctive programs.