Skip Navigation



Journal of Logic and Computation Advance Access published online on September 17, 2009
Journal of Logic and Computation, doi:10.1093/logcom/exp052
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Montagna, F.
Right arrow Articles by Noguera, C.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2009. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Papers

Arithmetical Complexity of First-order Predicate Fuzzy Logics Over Distinguished Semantics

Franco Montagna and Carles Noguera

Department of Mathematics and Computer Science, University of Siena, Pian dei Mantellini 44, 53100 Siena, Italy.
E-mail: montagna{at}unisi.it; cnoguera{at}iiia.csic.es

Received 16 March 2009.

All promiment examples of first-order predicate fuzzy logics are undecidable. This leads to the problem of the arithmetical complexity of their sets of tautologies and satisfiable sentences. This article is a contribution to the general study of this problem. We propose the classes of first-order core and {Delta}-core fuzzy logics as a good framework to address these arithmetical complexity issues. We obtain general results providing lower bounds for the complexities associated with arbitrary semantics, and we compute upper bounds and exact positions in the arithmetical hierarchy for distinguished semantics: general semantics given by all chains, finite-chain semantics, standard semantics and rational semantics.

Keywords: Arithmetical complexity; core fuzzy logics; finite-chain semantics; first-order predicate fuzzy logics; mathematical fuzzy logic; rational semantics; standard semantics



References

  1. Baaz M. Infinite-valued Gödel logics with 0-1 projections and relativizations. In GÖDEL ’96 - Logical Foundations of Mathematics, Computer Science and Physics. In: Lecture Notes in Logic—Hájek P, ed. (1996) 6. Springer. 23–33.
  2. Baaz M, Ciabattoni A, Fermüller CG, Veith H. On the undecidability of some subclassical first-order logics. In: Proceedings of FST and TCS 1999 (1999) Springer. 258–268. Vol. 1738 of Lecture Notes in Computer Science.
  3. Blok WJ, Pigozzi D. Algebraizable logics. Memoirs of the American Mathematical Society 396 (1989) 77.
  4. Chang CC. Algebraic analysis of many valued logics. Transactions of the American Mathematical Society (1958) 88:456–490.
  5. Ciabattoni A, Esteva F, Godo L. T-norm based logics with n-contraction. Neural Network World (2002) 12:453–460.
  6. Cintula P, Esteva F, Gispert J, Godo L, Montagna F, Noguera C. Distinguished algebraic semantics for t-norm based fuzzy logics: methods and algebraic equivalencies. Annals of Pure and Applied Logic (2009) 160:53–81.[CrossRef][Web of Science]
  7. Cintula P, Hájek P. Complexity issues in axiomatic extensions of Lukasiewicz logic. Journal of Logic and Computation (2009) 19:245–260.[Abstract/Free Full Text]
  8. Cintula P, Hájek P. Triangular norm based predicate fuzzy logics. Fuzzy Sets and Systems (2009) in press.
  9. Cintula P, Klement EP, Mesiar R, Navara M. Residuated logics based on strict t-norms with an involutive negation. Mathematical Logic Quarterly (2006) 52:269–282.[CrossRef][Web of Science]
  10. Dummett M. A propositional calculus with denumerable matrix. The Journal of Symbolic Logic (1959) 24:97–106.[CrossRef]
  11. Esteva F, Gispert J, Godo L, Noguera C. Adding truth-constants to logics of a continuous t-norm: axiomatization and completeness results. Fuzzy Sets and Systems (2007) 158:597–618.[CrossRef][Web of Science]
  12. Esteva F, Godo L. Monoidal t-norm based logic: towards a logic for left-continuous t-norms. Fuzzy Sets and Systems (2001) 124:271–288.[CrossRef][Web of Science]
  13. Esteva F, Godo L, Hájek P, Montagna F. Hoops and fuzzy logic. Journal of Logic and Computation (2003) 13:531–555.[Web of Science]
  14. Esteva F, Godo L, Hájek P, Navara M. Residuated fuzzy logics with an involutive negation. Archive for Mathematical Logic (2000) 39:103–124.[CrossRef][Web of Science]
  15. Esteva F, Godo L, Montagna F. The L{Pi} and L{Pi}Formula logics: two complete fuzzy systems joining Lukasiewicz and product logics. Archive for Mathematical Logic (2001) 40:39–67.[CrossRef][Web of Science]
  16. Esteva F, Godo L, Noguera C. On rational weak nilpotent minimum logics. Journal of Multiple-Valued Logic and Soft Computing (2006) 12:9–32.
  17. Esteva F, Godo L, Noguera C. First-order t-norm based fuzzy logics with truth-constants: distinguished semantics and completeness properties. Annals of Pure and Applied Logic (2009) in press.
  18. Flaminio T, Marchioni E. T-norm based logics with an independent involutive negation. Fuzzy Sets and Systems (2006) 157:3125–3144.[CrossRef][Web of Science]
  19. Gödel K. Zum intuitionistischen Aussagenkalkl. Anzeiger Akademie der Wissenschaften Wien, Math. naturwiss. Klasse (1932) 69:65–66.
  20. Hájek P. Metamathematics of Fuzzy Logic. In: Trends in Logic-Studia Logica Library (1998) 4. Kluwer.
  21. Hájek P. Fuzzy logic and arithmetical hierarchy III. Studia Logica (2001) 68:129–142.[CrossRef]
  22. Hájek P. Observations on the monoidal t-norm logic. Fuzzy Sets and Systems (2002) 132:107–112.[CrossRef][Web of Science]
  23. Hájek P. Fuzzy logics with noncommutative conjunctions. Journal of Logic and Computation (2003) 13:469–479.[Abstract/Free Full Text]
  24. Hájek P. Fuzzy logic and arithmetical hierarchy IV. In: First Order Logic Revisited—Hendricks, et al, eds. (2005) Logos. 107–115.
  25. Hájek P. Arithmetical complexity of fuzzy predicate logics – a survey. Soft Computing (2005) 9:935–941.[CrossRef][Web of Science]
  26. Hájek P. On arithmetical complexity of fragments of prominent fuzzy predicate logics. Soft Computing (2008) 12:335–340.[CrossRef][Web of Science]
  27. Hájek P. Arithmetical complexity of fuzzy predicate logics – a survey II. Annals of Pure and Applied Logic (2009) in press.
  28. Hájek P, Cintula P. On theories and models in fuzzy predicate logics. The Journal of Symbolic Logic (2006) 71:863–880.[CrossRef]
  29. Hájek P, Godo L, Esteva F. A complete many-valued logic with product-conjunction. Archive for Mathematical Logic (1996) 35:191–208.[Web of Science]
  30. Hájek P, Montagna F. A note on the first-order logic of complete BL-chains. Mathematical Logic Quarterly (2008) 54:435–448.[CrossRef][Web of Science]
  31. Horcík R, Cintula P. Product lukasiewicz logic. Archive for Mathematical Logic (2004) 43:477–503.[CrossRef][Web of Science]
  32. Jenei S, Montagna F. A proof of standard completeness for Esteva and Godo's logic MTL. Studia Logica (2002) 70:183–192.[CrossRef]
  33. Lukasiewicz J, Tarski A. Untersuchungen ber den Aussagenkalkl. Comptes Rendus de la Societé des Sciences et des Lettres de Varsovie (1930) cl. iii 23:1–21.
  34. Metcalfe G, Montagna F. Substructural fuzzy logics. Journal of Symbolic Logic (2007) 72:834–864.[CrossRef][Web of Science]
  35. Metcalfe G, Olivetti N, Gabbay D. Proof Theory for Fuzzy Logics. In: Applied Logic Series (2008) 36. Springer.
  36. Montagna F. Three complexity problems in quantified fuzzy logic. Studia Logica (2001) 68:143–152.[CrossRef]
  37. Montagna F. On the predicate logics of continuous t-norm BL-algebras. Archive for Mathematical Logic (2005) 44:97–114.[CrossRef][Web of Science]
  38. Montagna F. Subreducts of MV-algebras with product and product residuation. Algebra Universalis (2005) 53:109–137.[CrossRef][Web of Science]
  39. Montagna F, Noguera C, Horcík R. On weakly cancellative fuzzy logics. Journal of Logic and Computation (2006) 16:423–450.[Abstract/Free Full Text]
  40. Montagna F, Ono H. Kripke semantics, undecidability and standard completeness for Esteva and Godo's logic MTL{forall}. Studia Logica (2002) 71:227–245.[CrossRef]
  41. Noguera C, Esteva F, Gispert J. On triangular norm based axiomatic extensions of the weak nilpotent minimum logic. Mathematical Logic Quarterly (2008) 54:387–409.[CrossRef][Web of Science]
  42. Novák V, Perfilieva I, Mockor J. Mathematical Principles of Fuzzy Logic (1999) Kluwer Academic Publishers.
  43. Ragaz ME. Arithmetische Klassifikation von Formelnmengen der unendlichwertigen Logik (1981) ETH Zürick Thesis.
  44. Savicky P, Cignoli R, Esteva F, Godo L, Noguera C. On product logic with truth-constants. Journal of Logic and Computation (2006) 16:205–225.[Abstract/Free Full Text]
  45. Zadeh LA. Fuzzy sets. Information Control (1965) 8:338–353.[CrossRef]

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Montagna, F.
Right arrow Articles by Noguera, C.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?