Asymptotic Properties of Logics

• Autorzy: Zaionc M.
• Języki publikacji: PL

Abstrakty

EN

This paper presents the number of results concerning problems of asymptotic densities in the variety of propositional logics. We investigate, for propositional formulas, the proportion of tautologies of the given length n against the number of all formulas of length n. We are specially interested in asymptotic behavior of this fraction. We show what the relation between a number of premises of an implicational formula and asymptotic probability of finding a formula with this number of premises is. Furthermore we investigate the distribution of this asymptotic probabilities. Distribution for all formulas is contrasted with the same distribution for tautologies only.

Słowa kluczowe

EN

propositional logic; asymptotic density of tautologies; probabilistc methods in logic

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2003
• Tom: Vol. 12
• Strony: 129--138
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Zaionc M.

• Institute of Computer Science, Jagiellonian University, Nawojki 11, Kraków, 30-072, Poland,

Bibliografia

• [1] Comtet L.; Advanced combinatorics. The art of finite and infinite expansions., Revised and enlarged edition, Reidel, Dordrecht 1974.
• [2] Kostrzycka Z., Zaionc M.: Statistics of intuitionistic versus classical logics, to appear in Studia Logica.
• [3] Moczurad M., Tyszkiewicz J., Zaionc M.; Statistical properties of simple types, Mathematical Structures in Computer Science, Vol. 10, 2000, pp. 575–594.
• [4] Wilf H.S.; Generatingfunctionology, Second edition, Academic Press, Boston 1994.
• [5] Zaionc M.; Statistics of implicational logic, to appear in: Electronic Notes in Theoretical Computer Science, Vol. 84.
• [6] Zaionc M.; On the asymptotic density of tautologies in logic of implication and negation, to appear in: Reports on Mathematical Logic.