×

Complexity and definability issues in Ł\(\Pi \frac 1 2\). (English) Zbl 1142.03015

This paper is devoted to the logic \textŁ\(\Pi\frac 1 2\), which unites Łukasiewicz logic and product logic and, in addition, has a constant interpreted by \(\frac 1 2\). It is first shown that there is a way to translate any quantifier-free formula \(\Phi\) of the language of the real closed field \(\mathcal R\) of real numbers to a formula \(t(\Phi)\) of \textŁ\(\Pi\frac 1 2\) such that \(\Phi\) is valid in \(\mathcal R\) if and only if \(t(\Phi)\) is valid in \textŁ\(\Pi\frac 1 2\). One consequence is that \textŁ\(\Pi\frac 1 2\){} and the universal theory of \(\mathcal R\) have the same complexity. Furthermore, several definability issues are discussed. For instance, if the graph of a left-continuous t-norm \(\star\) is definable by means of a (two-valued) \textŁ\(\Pi\frac 1 2\){} formula, then the logic based on \(\star\) and the corresponding residuum, is in PSPACE. Finally, it is shown for several well-known fuzzy logics which are, like e.g. BL, based on specific t-norms and their residua, that completeness theorems still hold when restricting the respective class of t-norms to those which are term-definable in \textŁ\(\Pi\frac 1 2\).
We note that in the definition of an \textŁ\(\Pi\frac 1 2\){} algebra, the constant \(\frac 1 2\) was accidentally omitted.

MSC:

03B52 Fuzzy logic; logic of vagueness
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI