Satisfiability in Łukasiewicz Logic and Its Unbounded Relative

In the realm of nonclassical logics, and particularly in its subarea known as many-valued logics, the infinite-valued Łukasiewicz logic Ł has long occupied a prominent position. Its evolution (discussed in detail in, e.g., [8, 36, 22]) spanned the introduction of its three-valued antecedent by Łukasiewicz in his famous analysis of future contingents [29], as well as the infinite-valued calculus also introduced by Łukasiewicz and elaborated by himself and Tarski in the paper [30], which first discussed, but did not prove, completeness w.r.t. the intended semantics. A completeness theorem was given much later by Rose and Rosser [40]. MV-algebras, the equivalent algebraic semantics, were introduced and analyzed by Chang, and completeness was proved [6, 7]. Numerous monographs deal exclusively or substantially in the topic, e.g., [8, 22, 33, 36, 11]. Moreover, Łukasiewicz logic and its extensions can fruitfully be investigated in the framework of substructural logics [39, 19].

Increasingly then, the well-established area of Łukasiewicz logic and MV-algebras has been taken as a vantage point for various theoretical or applied problems, be it expansions of its language with constants in the pioneering works of Pavelka [37], modal expansions [16, 17, 23, 42], or reasoning about probabilities [18], to name a few.

Mundici initiated the study of computational complexity problems raised by Łukasiewicz logic in his famous work [35] which showed satisfiability and positive satisfiability of terms in the MV-algebra on the real unit interval with the natural order, ${[0,1]}_{\text{Ł}}$, to be NP-complete. An earlier important work, relevant to many subsequent contributions to the area of algorithmic problems in Łukasiewicz logic, came in McNaughton’s work [32] that characterized term-definable functions in ${[0,1]}_{\text{Ł}}$ as continuous, piecewise linear functions with integer coefficients. Algebraic methods are the mainstay of studying computational problems in the area, see especially [2, 4, 5, 3]. Komori’s classification of subvarieties of MV [27, 28] yielded the coNP-completeness result for axiomatic extensions of Ł [10], and Mundici’s NP-completeness result for term satisfiability generalizes to the existential theory of ${[0,1]}_{\text{Ł}}$ [24]. While Mundici’s results place the satisfiability and the tautology problems in Ł on a par with their counterparts in classical propositional logic (either being NP-complete and coNP-complete respectively), this is not a given in the infinite-valued setting. More generally, Łukasiewicz logic is dissimilar from classical logic in many respects and a list to showcase this phenomenon ought not to omit Ł not being structurally complete [14], the admissible rules being PSPACE complete [26], the first-order standard tautologies not being recursively enumerable [41] and in fact ${\mathrm{\Pi }}_2$-complete in the arithmetical hierarchy [38], or the complex structure of the lattice of extensions of Ł, which is dually isomorphic to the lattice of subquasivarieties of the variety of MV-algebras. This lattice is Q-universal [1]. Consequently, the extensions cannot all be decidable for cardinality reasons; this is also the case already for term satisfiability problems for various MV-algebras on the rational domain [25].

Unbounded Łukasiewicz logic Łu was considered recently in the papers [9, 12]. Formally, it is obtained by expanding the language of lattice-ordered abelian groups with a propositional constant $-1$ with suitable axioms ensuring that in any algebra within its equivalent algebraic semantics, the upset of the interpretation of $0$ is the set of designated elements, representing truth, whereas the downset of $-1$ represents falsity. By design, then, the logic bears resemblance to both Łukasiewicz logic and to abelian logic, as considered in Meyer and Slaney’s paper [34]. Unlike Ł, and like abelian logic, Łu is inconsistent with classical logic.

Weispfenning [43] proved that the existential theory of the variety of $\mathrm{\ell }$-groups is NP-complete. So the universal theory of $\mathrm{\ell }$-groups is coNP-complete and a fortiori, the quasiequational theory and the equational theory are in coNP. It is also known that $\mathrm{\ell }$-groups are generated as a quasivariety by the totally ordered members [13], in fact, by any nontrivial totally ordered member, since the universal theories of each two nontrivial totally ordered abelian groups coincide [20]. One easily shows that the equational theory of the totally ordered additive group on the integers is coNP-hard, thus any of the above universal fragments is coNP-complete.

The purpose of this paper is to provide a complexity estimate for Łu by exhibiting a polynomial-time reduction of the existential theory of the intended semantics of Łu – the algebra ${𝑹}_{-1}$, the pointed abelian totally ordered additive group on the reals where $-1$ is interpreted by itself – to the existential theory of the intended semantics of Ł, namely ${[0,1]}_{\text{Ł}}$, the standard MV-algebra on the reals. In both cases, the logics are finitely strongly complete w.r.t. the intended semantics. In our opinion the method surpasses the result in terms of interest, since the result might be anticipated. The method consists in taking a linear map of a sufficiently large neighbourhood of the element $0$ to the interval $[0,1]$, with the coefficient of the linear map determined by the instance (i.e., a given existential sentence).

In combination with the extant method of [12] that reduces in polynomial time the set of valid universal formulas (valid identities) of ${[0,1]}_{\text{Ł}}$ to the set of valid universal formulas (valid identities respectively) of the algebra ${𝑹}_{-1}$ one obtains firstly, a coNP-completeness of each of the universal fragments (i.a., the logic Łu is coNP-complete) and secondly, a non-trivial interpretation of the existential theory of the standard MV-algebra in itself.

The result invites a comparison with the work of Marchioni and Montagna [31], which concerns the logic $\text{Ł}\mathrm{\Pi }1/2$ and its relation to the universal theory of real closed fields (RCF). The authors show that the universal fragment of RCF has a polynomial time reduction to the (theorems of) the logic $\text{Ł}\mathrm{\Pi }1/2$. The relevance consists in, on the one hand, the logic $\text{Ł}\mathrm{\Pi }1/2$ being a conservative expansion of the logic Ł (the theorems of Ł are exactly those theorems of $\text{Ł}\mathrm{\Pi }1/2$ that only use the language ${ℒ}_{\mathrm{MV}}$) and on the other hand, the universal theory of pointed abelian totally ordered group being term-equivalent to the multiplication- and division-free fragment of the universal theory of RCF. Their reduction starts with fixing a bijection between $𝑹$ and the interval $(0,1)$ and then defining the operations of the real closed field on $𝑹$ in the $\text{Ł}\mathrm{\Pi }1/2$-algebra on the reals. This approach cannot be used in the present case because it relies on the multiplicative function symbols of the logic $\mathrm{\Pi }$ even when defining the real addition; so it does not scale well to language fragments.

This paper is structured as follows. Key notions are presented in section 2. Section 3 establishes that assignments that make an open formula of the language of pointed $\mathrm{\ell }$-groups true, if any, can be found in a suitably bounded interval. Section 4 presents the main result, the polynomial-time reduction. Section 5 then composes two reductions in order to obtain a nontrivial reduction of the existential theory of ${[0,1]}_{\text{Ł}}$ to itself.

Let $\mathrm{Var}=\{x_1,x_2,\mathrm{\dots }\}$ be a denumerable set of variables. A first-order language $ℒ$ uniquely determines the set ${\mathrm{𝑇𝑚}}_{ℒ}$ of terms of $ℒ$. The logical symbol $=$ is the only predicate symbol of any algebraic language; however, we may additionally use binary predicate symbols $\le$, (in Section 3). If $\phi$ and $\psi$ are terms of $ℒ$, then $\phi \diamond \psi$ is an atomic formula (or “atom”) of $ℒ$ for . If there are no predicate symbols in $ℒ$ then $ℒ$-atoms are just $ℒ$-identities $\phi =\psi$. We use lowercase Greek for terms and uppercase Greek for first-order formulas. For boolean symbols occurring in first-order formulas (boolean combinations of atoms of $ℒ$) we use $\neg$$\neg$ for boolean negation, $\wedge \wedge$ and $\vee \vee$ for boolean conjunction and disjunction respectively, $\bigwedge \bigwedge$ and $\bigvee \bigvee$ for finite boolean conjunctions and disjunctions respectively. An open formula of $ℒ$ is an arbitrary finite boolean combination (i.e., a $\{\neg \neg ,\wedge \wedge ,\vee \vee \}$-combination) of $ℒ$-atoms; we do not in general assume a normal form for first-order boolean formulas. Moreover, if $\Rightarrow$ denotes boolean implication, quasiidentities of $ℒ$ are formulas of the form ${\bigwedge \bigwedge }_{i=1}^n({\phi }_i={\psi }_i)\Rightarrow ({\phi }_0={\psi }_0)$ where ${\{{\phi }_i,{\psi }_i\}}_{0\le i\le n}$ is a set of $ℒ$-terms. Since quasiequational theories are not of particular interest in this work, $\Rightarrow$ is not taken as primitive and a formula $\mathrm{\Phi }\Rightarrow \mathrm{\Psi }$ is understood as $\neg \neg \mathrm{\Phi }\vee \vee \mathrm{\Psi }$ with only an insubstantial increase in length. An existential (universal) sentence of a language $ℒ$ is an existential (universal respectively) closure of an open formula of $ℒ$.

If $\phi$ is an $ℒ$-term, $\mathrm{Var}(\phi )$ denotes the set of variables that occur in $\phi$, and analogously for $\mathrm{Var}(\mathrm{\Phi })$ if $\mathrm{\Phi }$ is an $ℒ$-formula. We use $\overline{x}$ for $⟨x_1,\mathrm{\dots },x_n⟩$ if $n$ is of no consequence.

The following languages will be used:¹¹1We write ${\mathrm{𝑇𝑚}}_{\mathrm{Ab}}$ instead of ${\mathrm{𝑇𝑚}}_{{ℒ}_{\mathrm{Ab}}}$. We use the same notation for a function symbol of a language and for its interpretation in a particular algebra where possible, to avoid cluttering.

• $\mathrm{■}$

  ${ℒ}_{\mathrm{Ab}}=⟨+,-,0,\wedge ,\vee ⟩$ is the language of abelian lattice-ordered groups ($\mathrm{\ell }$-groups) and ${\mathrm{𝑇𝑚}}_{\mathrm{Ab}}$ is the corresponding set of well-formed terms;

• $\mathrm{■}$

  ${ℒ}_{\mathrm{pAb}}=⟨+,-,0,-1,\wedge ,\vee ⟩$ is the language of pointed $\mathrm{\ell }$-groups and ${\mathrm{𝑇𝑚}}_{\mathrm{pAb}}$ the set of its well-formed terms;

• $\mathrm{■}$

  ${ℒ}_{\mathrm{MV}}=⟨\oplus ,\otimes ,\neg ,\to ,0,1,\wedge ,\vee ⟩$ is the language of MV-algebras and ${\mathrm{𝑇𝑚}}_{\mathrm{MV}}$ the set of its well-formed terms;

• $\mathrm{■}$

  ${ℒ}_{\mathrm{MV}[\frac{1}{2}]}=⟨\oplus ,\otimes ,\neg ,\to ,0,1,1/2,\wedge ,\vee ⟩$ expands the language of MV-algebras with a new constant $1/2$ and ${\mathrm{𝑇𝑚}}_{\mathrm{MV}[\frac{1}{2}]}$ is the set of its well-formed terms.

$𝑹=⟨ℝ,+,-,\wedge ,\vee ,0⟩$ is an abelian lattice-ordered group ($\mathrm{\ell }$-group) on the real numbers with the usual order, (the usual) addition, subtraction and $0$. The algebra $𝑹$ provides a semantics to the language ${ℒ}_{\mathrm{Ab}}$.

${𝑹}_{-1}=⟨ℝ,+,-,\wedge ,\vee ,0,-1⟩$ is a pointed abelian $\mathrm{\ell }$-group whose ${ℒ}_{\mathrm{Ab}}$-reduct is $𝑹$ and the element $-1$ interprets the constant $-1$.²²2While the algebra ${𝑹}_{-1}$ seems very similar to $𝑹$, the additional constant in the language grants much more expressivity and brings the logic Łu closer to the logic Ł.

In the standard MV-algebra ${[0,1]}_{\text{Ł}}$ on the reals, which provides an interpretation to the language ${ℒ}_{\mathrm{MV}}$, the domain is $[0,1]$, as for the basic operations, $\neg a$ is $1-a$ and $a\otimes b$ is $\max (0,a+b-1)$ for $a,b\in [0,1]$. The remaining function symbols are definable.

• $\mathrm{■}$

  $a\oplus b$ is $\neg (\neg a\otimes \neg b)$

• $\mathrm{■}$

  $a\to b$ is $\neg a\oplus b$

• $\mathrm{■}$

  $a\wedge b$ is $a\otimes (a\to b)$

• $\mathrm{■}$

  $a\vee b$ is $(a\to b)\to b$

• $\mathrm{■}$

  $0$ is $a\otimes \neg a$ for some $a$

• $\mathrm{■}$

  $1$ is $\neg 0$

In any MV-algebra, $\neg \neg a=a$ holds (involutive law), analogously in any abelian $\mathrm{\ell }$-group, we have $--a=a$. In view of this, we assume that terms are given in a reduced form within their respective languages, containing no subterms of the form $\neg \neg \phi$ or $--\phi$, respectively.

The two element boolean algebra is a subalgebra of ${[0,1]}_{\text{Ł}}$. The algebra ${[0,1]}_{\text{Ł}}^{1/2}$ interprets the language ${ℒ}_{\mathrm{MV}[\frac{1}{2}]}$. Its ${ℒ}_{\mathrm{MV}}$-reduct is the algebra ${[0,1]}_{\text{Ł}}$ and the element $1/2$ interprets the constant $1/2$.

It is assumed throughout that no well-formed term of the languages under consideration contains two consecutive occurrences of the symbol $-$ or the symbol $\neg$. This can be assumed without a loss of generality, relying on the valid involutive laws.

One can introduce the (infinite-valued) Łukasiewicz logic Ł and the unbounded Łukasiewicz logic $\text{Ł}\mathrm{u}$ axiomatically and then obtain that Ł is finitely strongly complete w.r.t. ${[0,1]}_{\text{Ł}}$ and $\text{Ł}\mathrm{u}$ is finitely strongly complete w.r.t. ${𝑹}_{-1}$. We take these results for granted, referring the reader to the works [8, 22, 12]. Moreover, without further ado we use Mundici’s result on the NP-completeness of the term satisfiability problem in ${[0,1]}_{\text{Ł}}$ and the coNP-completeness of term validity therein. Recall that the designated element of ${[0,1]}_{\text{Ł}}$ is $1$; accordingly, a term $\phi (\overline{x})$ holds under an assignment $\overline{a}$ provided that $\phi (\overline{a})=1$, and $\phi (\overline{x})$ is satisfiable in ${[0,1]}_{\text{Ł}}$ provided that an assignment exists that makes it true there. We retain this terminology also for first-order open formulas: such a formula $\mathrm{\Phi }(\overline{x})$ is satisfiable in ${[0,1]}_{\text{Ł}}$ provided an assignment to its variables exists that makes it true therein. A term $\phi$ of ${ℒ}_{\mathrm{MV}}$ is valid in ${[0,1]}_{\text{Ł}}$ provided it is true under any assignment therein. The set of designated elements of ${𝑹}_{-1}$ is the set of its nonnegative elements (the upset of $0$), and accordingly a term is satisfiable in ${𝑹}_{-1}$ provided some assignment sends it to a nonnegative element; the rest is analogous.

If $ℒ$ is a language and $𝑨$ is an $ℒ$-algebra, the existential theory ($\exists$-theory) of $𝑨$ is the set of all existential $ℒ$-sentences valid in $𝑨$; dually for the universal theory ($\forall$-theory) and universal $ℒ$-sentences. The (quasi)equational theory of $𝑨$ is the set of universal closures of $ℒ$-(quasi)identities valid in $𝑨$. Both the equational theory and the quasiequational theory of an algebra $𝑨$ are fragments of the universal theory of $𝑨$.

Each term $\phi$ of ${ℒ}_{\mathrm{Ab}}$ in $n$ variables $x_1,\mathrm{\dots },x_n$ in $\mathrm{Var}$ uniquely determines a function $f_{\phi }:{ℝ}^n\to ℝ$ (on the domain of the algebra $𝑹$) using the following inductive steps:

• $\mathrm{■}$

  $f_x=x$ for each variable $x$ in $\mathrm{Var}$;

• $\mathrm{■}$

  $f_{\phi +\psi }=f_{\phi }+f_{\psi }$;

• $\mathrm{■}$

  $f_{-\phi }=-f_{\phi }$;

• $\mathrm{■}$

  $f_{\phi \wedge \psi }=\min (f_{\phi },f_{\psi })$;

• $\mathrm{■}$

  $f_{\phi \vee \psi }=\max (f_{\phi },f_{\psi })$;

• $\mathrm{■}$

  $f_0=0$.

Analogously for a term $\phi$ of ${ℒ}_{\mathrm{pAb}}$. Furthermore, a term $\phi$ of ${ℒ}_{\mathrm{MV}}$ uniquely determines a function $f_{\phi }:{[0,1]}^n\to [0,1]$ (on the domain of the standard MV-algebra), i.e.,

• $\mathrm{■}$

  $f_{\phi \otimes \psi }=\max (0,f_{\phi }+f_{\psi }-1)$,

• $\mathrm{■}$

  $f_{\neg \phi }=1-f_{\phi }$,

etc., and analogously for a term of the language ${ℒ}_{\mathrm{MV}[\frac{1}{2}]}$.

For a term $\phi$ of ${ℒ}_{\mathrm{Ab}}$, the depth of $\phi$ is defined by induction: $0pt0=0$; $0ptx=0$ if $x\in \mathrm{Var}$; $0pt-\phi =0pt\phi +1$; and $0pt\phi \circ \psi =\max (0pt\phi ,0pt\psi )+1$ if $\circ$ is one of $\{+,\wedge ,\vee \}$. Analogously for the other languages, with depth of constants set to $0$.

For a term $\phi$ and a first-order formula $\mathrm{\Phi }$ of ${ℒ}_{\mathrm{Ab}}$, $\mathrm{♯}(\phi )$ and $\mathrm{♯}(\mathrm{\Phi })$ will denote the length (or size) of $\phi$ and $\mathrm{\Phi }$ respectively. We define $\mathrm{♯}(\phi )$ as the total number of occurrences of variables and constants in $\phi$; should one view $\phi$ as a tree, $\mathrm{♯}(\phi )$ is the number of leaves. Recalling that in $\phi$ no two consecutive negations “$-$” can occur, the number of occurrences of function symbols in $\phi$ (i.e., of the inner nodes of the tree) is bounded by $2\mathrm{♯}(\phi )$. The sizes of representations of each variable and each constant are neglected and representation in unit length is considered.

For an open $\mathrm{\Phi }$, we use ${\mathrm{At}}^{\mathrm{♯}}(\mathrm{\Phi })$ for the number of occurrences of atomic formulas. We define $\mathrm{♯}(\mathrm{\Phi })$ to be the sum of the sizes of all the occurrences of terms in the atomic identities; we have $\mathrm{♯}(\mathrm{\Phi })\le {\mathrm{At}}^{\mathrm{♯}}(\mathrm{\Phi })\cdot 2\max \{\mathrm{♯}(\phi )\mid \phi \text{ atom in }\mathrm{\Phi }\}$. Again any two consecutive boolean negations are omitted. Analogous considerations apply to the remaining languages.

Let $ℒ$ be a language and $\mathrm{\Phi }$ an open $ℒ$-formula. A Tseitin variant of $\mathrm{\Phi }$ is an open formula ${\mathrm{\Phi }}^{\prime }$ with some desirable properties: $\mathrm{♯}({\mathrm{\Phi }}^{\prime })$ is of polynomial size in $\mathrm{♯}(\mathrm{\Phi })$; every atom of ${\mathrm{\Phi }}^{\prime }$ contains at most one function symbol (in particular, terms of ${\mathrm{\Phi }}^{\prime }$ have depth at most 1); and ${\mathrm{\Phi }}^{\prime }$ is equisatisfiable with $\mathrm{\Phi }$ in any $ℒ$-structure $𝑴$ (i.e., the existential closure of $\mathrm{\Phi }$ holds in $𝑴$ iff so does the existential closure of ${\mathrm{\Phi }}^{\prime }$). We proceed to define Tseitin variants formally.

Let $T$ be the set of all subterms of $ℒ$-terms that occur in $\mathrm{\Phi }(x_1,\mathrm{\dots },x_n)$. Let $|T|$ be the cardinality of $T$. To each term $\phi$ in $T$ that is not a variable among $x_1,\mathrm{\dots },x_n$, assign a new variable $x_{\phi }$ from $\mathrm{Var}$, not occurring in $\mathrm{\Phi }$, with distinct variables assigned to distinct terms. We have $|T|\le 3\mathrm{♯}(\mathrm{\Phi })$. Define a new open formula $\mathrm{\Psi }$ from $\mathrm{\Phi }$ as follows. For every atom $\phi \diamond \psi$ occurring in $\mathrm{\Phi }$ (here $\diamond$ is among ), if either of $\phi$ or $\psi$ is not a variable among $x_1,\mathrm{\dots },x_n$, replace this occurrence of $\phi$ or $\psi$ with the new variable $x_{\phi }$ or $x_{\psi }$ respectively. For convenience, if the term $\phi$ is a variable, $x_{\phi }$ denotes the original variable $\phi$. Then the Tseitin variant of $\mathrm{\Phi }$ is

where $x_{\phi },x_{{\phi }_1},\mathrm{\dots },x_{{\phi }_n}$ are metavariables for elements of $\mathrm{Var}$. Observe ${\mathrm{\Phi }}^{\prime }$ has no compound terms. Furthermore, ${\mathrm{At}}^{\mathrm{♯}}({\mathrm{\Phi }}^{\prime })\le {\mathrm{At}}^{\mathrm{♯}}(\mathrm{\Phi })+|T|$. Lastly, ${\mathrm{\Phi }}^{\prime }$ is indeed equisatisfiable with $\mathrm{\Phi }$ in any $ℒ$-structure $𝑴$: for any assignment $v_{𝑴}$ in $𝑴$ one has that $v_{𝑴}$ satisfies $\mathrm{\Phi }$ in $𝑴$ if and only if ${\mathrm{\Phi }}^{\prime }$ is satisfied by the assignment $v_{𝑴}^{\prime }$, where $v_{𝑴}^{\prime }$ extends $v_{𝑴}$ by sending each added variable $x_{\phi }$ to $v_{𝑴}(\phi )$.

This section establishes a technical result to be used below: if an existential sentence $\exists x_1\exists x_2\mathrm{\dots }\exists x_n\mathrm{\Phi }$ in the language ${ℒ}_{\mathrm{pAb}}$ holds in ${𝑹}_{-1}$, then there is a satisfying (rational) assignment whose binary representation has size polynomial in $\mathrm{♯}(\mathrm{\Phi })$. Our exposition follows (in some detail) the one in the paper [15] as to the general method.

Consider the mapping $\tau :{\mathrm{𝑇𝑚}}_{\mathrm{Ab}}\to {\mathrm{𝑇𝑚}}_{\mathrm{MV}[\frac{1}{2}]}$, assigning to each term $\phi$ of ${ℒ}_{\mathrm{Ab}}$ a term of ${ℒ}_{\mathrm{MV}[\frac{1}{2}]}$ as follows:

1. 1.

   $\tau (x)=x$ for $x\in \mathrm{V}ar(\phi )$;

2. 2.

   $\tau (0)=\frac{1}{2}$;

3. 3.

   $\tau (-\phi )=\neg (\tau (\phi ))$;

4. 4.

   $\tau (\phi +\psi )=(\tau (\phi )\oplus \tau (\psi ))\otimes (\frac{1}{2}\oplus (\tau (\phi )\otimes \tau (\psi )))$;

5. 5.

   $\tau (\phi \vee \psi )=\tau (\phi )\vee \tau (\psi )$;

6. 6.

   $\tau (\phi \wedge \psi )=\tau (\phi )\wedge \tau (\psi )$.

For each pair of nonnegative integers $M$ and $k$, let $r_{M,k}:ℝ\to ℝ$ be defined as