Complexity of t-tautologies (Q5957903)

The paper focuses on propositional fuzzy logics based on continuous triangular norms (t-norms). After a brief overview of some principal results in the theory of t-norms, the proof of the main theorem is provided: The set of all t-tautologies (i.e. tautologies w.r.t. arbitrary continuous t-norm) is coNP-complete. From this, it also follows that the universal first-order theory of t-algebras (i.e. algebras \(\langle[0, 1], \star, \rightarrow, 0, 1\rangle\) where \(\star\) is a continuous t-norm and \(\rightarrow\) is its residuum) is coNP-complete.