کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438882 690345 2006 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Probability distribution for simple tautologies
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Probability distribution for simple tautologies
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 355, Issue 2, 11 April 2006, Pages 243-260