Skip Navigation



Journal of Logic and Computation Advance Access published online on September 17, 2009
Journal of Logic and Computation, doi:10.1093/logcom/exp054
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 Aguzzoli, S.
Right arrow Articles by Marra, V.
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

Computing Minimal Axiomatizations in Gödel Propositional Logic

Stefano Aguzzoli

Dipartimento di Scienze dell’Informazione, Università degli Studi di Milano, via Comelico 39-41, 20135 Milano, Italy.
E-mail: aguzzoli{at}dsi.unimi.it

Ottavio M. D’Antona and Vincenzo Marra

Dipartimento di Informatica e Comunicazione, Università degli Studi di Milano, via Comelico 39-41, 20135 Milano, Italy.
E-mail: dantona{at}dico.unimi.it; marra{at}dico.unimi.it

Received 31 August 2008.

We solve the minimization problem for finitely axiomatizable theories in Gödel infinite-valued propositional logic. That is, we obtain an algorithm that when input a formula {alpha}(X1,...,Xn) outputs a formula β(X1,...,Xm) such that (i) the theories singly axiomatized by {{alpha}} and {β} have isomorphic algebraic semantics, and (ii) if β'(X1,...,Xm') is any formula satisfying (i), then m'≥m.

Keywords: Gödel propositional logic; minimal axiomatizations; normal forms



References

  1. Abad M, Monteiro L. On Free L-algebras (1987) 35. Notas de Lógica Matemática, Universidad Nacional del Sur.
  2. Aguzzoli S, Gerla B. Normal forms and free algebras for some extensions of MTL. Fuzzy Sets and Systems (2008) 159:1131–1152.[CrossRef][Web of Science]
  3. Baaz M, Veith H. Interpolation in fuzzy logic. Archive Mathematical Logic (1999) 38:461–489.[CrossRef]
  4. Casari E. Comparative logics and Abelian l-groups. In: Logic Colloquium’88 (Padova, 1988) (1989) North-Holland. 161–190. Vol. 127 of Studuies Logic Foundtation Mathematics.
  5. Cignoli RLO, D’Ottaviano IML, Mundici D. Algebraic Foundations of Many-valued Reasoning (2000) Kluwer Academic Publishers. Vol. 7 of Trends in Logic—Studia Logica Library.
  6. Cintula P, Metcalfe G. Normal forms for fuzzy logics: a proof-theoretic approach. Archive Mathematical Logic (2007) 46:347–363.[CrossRef]
  7. D’Antona OM, Marra V. Computing coproducts of finitely presented Gödel algebras. Annals of Pure and Applied Logic (2006) 142:202–211.[CrossRef][Web of Science]
  8. Gerla B. A note on functions associated with Gödel formulas. Soft Computing (2000) 4:206–209.[CrossRef]
  9. Glass AMW, Madden JJ. The word problem versus the isomorphism problem. Journal of London Mathematical Society (1984) 30:53–61.[CrossRef]
  10. Glass AMW. Partially Ordered Groups (1999) World Scientific Publishing Co. Inc. Vol. 7 of Series in Algebra.
  11. Hájek P. Metamathematics of Fuzzy Logic (1998) Kluwer Academic Publishers. Vol. 4 of Trends in Logic—Studia Logica Library.
  12. Horn A. Free L-algebras. Journal of Symbolic Logic (1969) 34:475–480.[CrossRef][Web of Science]
  13. Horn A. Logic with truth values in a linearly ordered Heyting algebra. Journal of Symbolic Logic (1969) 34:395–408.[CrossRef][Web of Science]
  14. Johnstone PT. Stone Spaces (1986) Cambridge University Press. Vol. 3 of Cambridge Studies in Advanced Mathematics. Reprint of the 1982 edition.
  15. Marra V. The minimal axiomatization problem for Abelian logic is undecidable. (2006) Unpublished manuscript.
  16. Mac Lane S. Categories for the Working Mathematician (1998) 2nd edn. Springer. Vol. 5 of Graduate Texts in Mathematics.
  17. Metcalfe G, Olivetti N, Gabbay D. Sequent and hypersequent calculi for abelian and Lukasiewicz logics. ACM Transactions on Computational Logic (2005) 6:578–613.[CrossRef]
  18. Meyer RK, Slaney JK. Abelian logic from A to Z. In: Paraconsistent Logic—Priest G, Routley R, Norman J, eds. (1989) Philosophia Verlag GmbH. 245–288. Analytica.

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 Aguzzoli, S.
Right arrow Articles by Marra, V.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?