Satisfiability in Lukasiewicz logic and its unbounded relative

Abstrakt

Unbounded Lukasiewicz logic is a substructural logic that combines features of infinite-valued Lukasiewicz logic with those of abelian logic. The logic is finitely strongly complete w.r.t. the additive l-group on the reals expanded with a distinguished element -1. We show that the existential theory of this structure is NP-complete. This provides a complexity upper bound for the set of theorems and the finite consequence relation of unbounded Lukasiewicz logic. The result is obtained by reducing the problem to the existential theory of the MV-algebra on the reals, the standard semantics of Lukasiewicz logic. This provides a new connection between both logics. The result entails a translation of the existential theory of the standard MV-algebra into itself.