  Logic Programs with Ordered Disjunction (LPODs) extend classical logic
programs with the capability of expressing preferential disjunctions in the
heads of program rules. The initial semantics of LPODs, although simple and
quite intuitive, is not purely model-theoretic. A consequence of this is that
certain properties of programs appear non-trivial to formalize in purely
logical terms. An example of this state of affairs is the characterization of
the notion of strong equivalence for LPODs. Although the results of Faber et
al. (2008) are accurately developed, they fall short of characterizing strong
equivalence of LPODs as logical equivalence in some specific logic. This comes
in sharp contrast with the well-known characterization of strong equivalence
for classical logic programs, which, as proved by Lifschitz et al. (2001),
coincides with logical equivalence in the logic of here-and-there. In this
paper we obtain a purely logical characterization of strong equivalence of
LPODs as logical equivalence in a four-valued logic. Moreover, we provide a new
proof of the coNP-completeness of strong equivalence for LPODs, which has an
interest in its own right since it relies on the special structure of such
programs. Our results are based on the recent logical semantics of LPODs
introduced by Charalambidis et al. (2021), a fact which we believe indicates
that this new semantics may prove to be a useful tool in the further study of
LPODs.
