zbMATH — the first resource for mathematics

On the predicate logics of continuous t-norm BL-algebras. (English) Zbl 1070.03013
Let \(\mathbf{C}\) be a class of BL-algebras whose lattice reduct is the real unit interval \([0,1]\) with the usual order.
Firstly, the paper deals with the task when the set Taut(\(\mathbf{C}\forall\)) of predicate formulas valid in all members of \(\mathbf{C}\) is recursively axiomatizable. The author shows that Taut(\(\mathbf{C}\forall\)) is recursively axiomatizable iff \(\mathbf{C}\) consists only of \([0,1]_G\) (i.e., the Gödel algebra on \([0,1]\)). If \(\mathbf{C}\) contains at least one algebra not isomorphic to \([0,1]_G\) then he recursively reduces Taut(\(\L\forall\)) to Taut(\(\mathbf{C}\forall\)), where \(\L\forall\) denotes Łukasiewicz predicate logic. As it is known that Taut(\(\L\forall\)) is \(\Pi_2\)-complete, he gets that Taut(\(\mathbf{C}\forall\)) is \(\Pi_2\)-hard. If \(\mathbf{C}\) contains only \([0,1]_G\) then Taut(\(\mathbf{C}\forall\)) is recursively axiomatizable since it is well known that Taut(\([0,1]_G\forall\)) is in \(\Sigma_1\).
Secondly, it is known that each t-norm is isomorphic to an ordinal sum of the three basic t-norms (Gödel, Łukasiewicz, product). The author proves that if \(\mathbf{C}\) contains a member whose monoidal operation is an ordinal sum containing either product t-norm or Łukasiewicz t-norm which is neither the first component nor the last component in the ordinal sum then Taut(\(\mathbf{C}\forall\)) is not arithmetical. In the case with the product component he recursively reduces Taut(\(\Pi\forall\)) (i.e., tautologies of the product predicate fuzzy logic) to Taut(\(\mathbf{C}\forall\)). Since Taut(\(\Pi\forall\)) is not arithmetical, the result follows. In the case with Łukasiewicz component he recursively reduces true arithmetic to Taut(\(\mathbf{C}\forall\)). Thus there remain only finitely many cases when the complexity of Taut(\(\mathbf{C}\forall\)) is not known.
Finally, the monadic fragment of Taut(\(\mathbf{C}\forall\)) is investigated. The author shows that if \(\mathbf{C}\) contains a member which is not isomorphic to any of product algebra on \([0,1]\) and MV-algebra on \([0,1]\), then the monadic fragment of Taut(\(\mathbf{C}\forall\)) is undecidable. For this purpose he reduces the theory of two equivalence relations to the monadic fragment of Taut(\(\mathbf{C}\forall\)). Since the theory of two equivalence relations is undecidable, the result follows. Moreover, the author shows that it is possible to use the same method to prove that the monadic fragment of Hájek’s basic predicate fuzzy logic is undecidable.

03B52 Fuzzy logic; logic of vagueness
03D15 Complexity of computation (including implicit computational complexity)
03G25 Other algebras related to logic
03D35 Undecidability and degrees of sets of sentences
Full Text: DOI
[1] Aglianó, P., Montagna, F.: Varieties of basic algebras I: general properties. J. Pure Appl. Algebra 181, 105-129 (2003) · Zbl 1034.06009
[2] Aglianó, P., Ferreirim, I.M.A., Montagna, F.: Basic hoops: an algebraic study of continuous t-norms. Preprint 2000 · Zbl 1127.03049
[3] Baaz, M., Ciabattoni, A., Fermüller, C.: Herbrand?s Theorem for Prenex Gödel logic and its consequences for Theorem Proving. Proceedings of logic for Programming and Automated Reasoning (LPAR?2001), Cuba, December 2001. LNAI 2250. pp. 201-216 · Zbl 1275.03098
[4] Blok, W.J., Ferreirim, I.M.A.: On the structure of hoops. Algebra Universalis 43, 233-257 (2000) · Zbl 1012.06016
[5] Chang, C.C.: Algebraic analysis of many-valued logic. Trans. Amer. Math. Soc. 88, 467-490 (1958) · Zbl 0084.00704
[6] Cignoli, R., Esteva, F., Godo, L., Torrens, A.: Basic fuzzy logic is the logic of continuous t-norms and their residua. Soft. Comput. 4, 106-112 (2000) · Zbl 02181428
[7] Cignoli, R., Mundici, D., D?Ottaviano, I.M.L.: Algebraic foundations of many-valued reasoning. Kluwer 2000 · Zbl 0937.06009
[8] Esteva, F., Godo, L.: Monoidal t-norm based logics: towards an axiomatization of the logic of left-continuous t-norms. Fuzzy sets and systems 124, 271-288 (2001) · Zbl 0994.03017
[9] Ferreirim, I.M.A.: On varieties and quasi varieties of hoops and their reducts, PhD thesis, University of Illinois at Chicago, 1992
[10] Hájek, P.: Metamathematics of Fuzzy Logic. Kluwer, 1998 · Zbl 0937.03030
[11] Hájek, P.: Fuzzy Logic and arithmetical hierarchy 3. Studia Logica 68, 129-142 (2001) · Zbl 0988.03042
[12] Hájek, P.: Fuzzy Logic and arithmetical hierarchy 4. Preprint 2003
[13] Hájek, P.: Monadic Fuzzy Predicate Logics. Studia Logica 71 (2), 165-176 (2002) · Zbl 1006.03023
[14] Esteva, F., Godo, L., Hájek, P., Montagna, F.: Hoops and Fuzzy Logic. J. Logic Computat. 13 (4), 531-355 (2003) · Zbl 1039.03016
[15] Montagna, F.: Three complexity problems in quantified fuzzy logic. Studia Logica 68, 143-152 (2001) · Zbl 0985.03014
[16] 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
[17] Pa?asinski, M.: Some remarks on BCK-algebras. Math. Seminar Notes, Kobe Univ. 8, 137-144 (1980)
[18] Ragaz, M.E.: Arithmetische Klassification von Formelnmenge der unendlichwertigen Logik. Thesis, ETH Zürich, 1981 · Zbl 0516.03011
[19] Rogers, H.: Certain logical reduction and decision problems. Annals of Mathematics Vol. 4, 264-284 (1956) · Zbl 0074.01403
[20] Ward, M., Diilworth, R.P.: Resisuated lattices. Trans. Amer. Math. Soc. 45, 335-354 (1939) · JFM 65.0084.01
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.