Algebraic properties of the space of multivalued and paraconsistent logic programs

Paraconsistent logics are a class of logics proposed by Newton da Costa [7] that provide a framework for formal reasoning about inconsistent systems. In [4, 5, 6], Blair and Subrahmanian, and independently, Fitting [11], showed that paraconsistent logics may be successfully used for logic programming. In this paper, we study the algebraic properties of the space of paraconsistent logic programs over a complete lattice of truth values. We show that this set, under some natural operations generalizing those defined by Mancarella and Pedreschi [18], yields a distributive lattice that satisfies various important non-extensibility conditions. Intuitively, these non-extensibility conditions tell us that the algebraic characterization we provide cannot be (naturally) strengthened any further. As an interesting application, we generalize the notion of subsumption equivalence of classical logic programs to the case of multi-valued logic programs and derive necessary and sufficient conditions for multivalued logic programs to be subsumption-equivalent.