Paper Info
Title
Probability distribution for simple tautologies
Abstract
In this paper we investigate the size of the fraction of tautologies of the given length n against the number of all formulas of length n for implicational logic. We are specially interested in asymptotic behavior of this fraction. We demonstrate the relation between a number of premises of implicational formula and asymptotic probability of finding formula with this number of premises. Furthermore, we investigate the distribution of this asymptotic probabilities. Distribution for all formulas is contrasted with the same distribution for tautologies only. We prove those distributions to be so different that enable us to estimate likelihood of truth for a given long formula. Despite the fact that all discussed problems and methods in this paper are solved by mathematical means, the paper may have some philosophical impact on the understanding how much the phenomenon of truth is sporadic or frequent in random logical sentences.
Year
DOI
Venue
2006
10.1016/j.tcs.2006.01.002
Theor. Comput. Sci.
Keywords
DocType
Volume
implicational formula,simple tautology,random logical sentence,asymptotic behavior,philosophical impact,long formula,length n,asymptotic probability in logic,implicational logic,asymptotic probability,probability distribution,mathematical mean
Journal
355
Issue
ISSN
Citations 
2
Theoretical Computer Science
10
PageRank 
References 
Authors
0.96
4
1
Name
Order
Citations
PageRank
Marek Zaionc111117.27