Abstract. Given a class
C of t-norm BL-algebras, one may wonder which is the complexity of the set
Taut(
C
) of predicate formulas which are valid in any algebra in
C. We first characterize the classes
C for which
Taut(
C) is recursively axiomatizable, and we show that this is the case iff
C only consists of the Gödel algebra on [0,1]. We then prove that in all cases except from a finite number
Taut(
C) is not even arithmetical. Finally we consider predicate monadic logics
TautM(
C) of classes
C of t-norm BL-algebras, and we prove that (possibly with finitely many exceptions) they are undecidable.
Mathematics Subject Classification (2000): Primary: 03B50, Secondary: 03B47Acknowledgement The author is deeply indebted to Petr Hájek, whose results about the complexity problems of predicate fuzzy logics constitute the main motivation for this paper, and whose suggestions and remarks have been always stimulating. He is also indebted to Matthias Baaz, who pointed out to him a method used in [BCF] for the case of monadic Gödel logic which works with some modifications also in the case of monadic BL logic.