Let phi be a formula of Łukasiewicz infinite-valued propositional logic having a total of l many occurrences of n distinct propositional variables (call l the length of phi). Results in Aguzzoli and Ciabattoni [Finiteness in infinite-valued Łukasiewicz logic, Journal of Logic, Language and Information, 9 (2000) 5–29] show that if phi is not a tautology then there is an MV chain View the MathML source of cardinality less-than-or-equals, slant left floor(l/n)nright floor + 1 together with an evaluation View the MathML source of propositional variables in View the MathML source, such that View the MathML source is a countermodel for phi, that is View the MathML source. We show that for each integer n > 0 the function b(n, l) = (l/n)n + 1 yields an asymptotically tight upper bound on the maximum cardinality of the smallest MV algebras having countermodels for formulas of length l.

An asymptotically tight bound on countermodels for Łukasiewicz logic / S. Aguzzoli. - In: INTERNATIONAL JOURNAL OF APPROXIMATE REASONING. - ISSN 0888-613X. - 43:1(2006 Sep), pp. 76-89.

An asymptotically tight bound on countermodels for Łukasiewicz logic

S. Aguzzoli
Primo
2006

Abstract

Let phi be a formula of Łukasiewicz infinite-valued propositional logic having a total of l many occurrences of n distinct propositional variables (call l the length of phi). Results in Aguzzoli and Ciabattoni [Finiteness in infinite-valued Łukasiewicz logic, Journal of Logic, Language and Information, 9 (2000) 5–29] show that if phi is not a tautology then there is an MV chain View the MathML source of cardinality less-than-or-equals, slant left floor(l/n)nright floor + 1 together with an evaluation View the MathML source of propositional variables in View the MathML source, such that View the MathML source is a countermodel for phi, that is View the MathML source. We show that for each integer n > 0 the function b(n, l) = (l/n)n + 1 yields an asymptotically tight upper bound on the maximum cardinality of the smallest MV algebras having countermodels for formulas of length l.
Many-valued logics
Settore INF/01 - Informatica
Settore MAT/01 - Logica Matematica
set-2006
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/19762
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 6
social impact