zbMATH — the first resource for mathematics

Complexity of t-tautologies. (English) Zbl 1006.03022
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.

03B52 Fuzzy logic; logic of vagueness
03B25 Decidability of theories and sets of sentences
03D15 Complexity of computation (including implicit computational complexity)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI
[1] M. Baaz, Infinite-valued Gödel logics with 0-1-projections and relativizations, in Proc Gödel 96—Kurt Gödel’s Legacy, LNL, vol. 6, Springer, Berlin, pp. 23-33. · Zbl 0862.03015
[2] M. Baaz, H. Veith, Interpolation in fuzzy logic, Arch. Math. Logic, accepted for publication. · Zbl 0936.03026
[3] R. Cignoli, F. Esteva, L. Godo, A. Torrens, Basic fuzzy logic is the logic of continuous t-norms and their residua, submitted.
[4] Hájek, P., Basic fuzzy logic and BL-algebras, Soft comput., 2, 124-128, (1998)
[5] Hähnle, R., Many-valued logics and mixed integer programming, Ann. math. artificial intelligence, 12, 213-264, (1994)
[6] Hájek, P., Metamathematics of fuzzy logic, (1998), Kluwer Dordrecht · Zbl 0937.03030
[7] Hájek, P.; Godo, L.; Esteva, F., A complete many-valued logic with product-conjunction, Arch. math. logic, 35/3, 191-208, (1996) · Zbl 0848.03005
[8] Mostert, P.S.; Shields, A.L., On the structure of semigroups on a compact manifold with boundary, Ann. math., 65, 117-143, (1957) · Zbl 0096.01203
[9] Mundici, D., Satisfiability in many-valued logics is NP-complete, Theoret. comput. sci., 52, 145-153, (1987) · Zbl 0639.03042
[10] Schweizer, B.; Sklar, A., Statistical metric spaces, Pacific J. math., 10, 313-334, (1960) · Zbl 0091.29801
[11] Schweizer, B.; Sklar, A., Associative functions and statistical triangle inequalities, Publ. math. debrecen, 8, 169-186, (1961) · Zbl 0107.12203
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.