Том 13, серия 1, номер 2, 2006 г., Стр. 59-96

УДК 519.716
А. Д. Яшунский
Об асимптотике вероятности значений случайных булевых выражений

Аннотация:
Рассматриваются случайные булевы выражения, получаемые случайной и независимой подстановкой констант 1, 0 соответственно с вероятностями $p$, $1-p$ в случайные бесповторные формулы над заданным базисом. Изучается вероятность, с которой указанные выражения принимают значение 1. Показано, что для любого конечного базиса при любом $p$, $0<p<1$, эта вероятность стремится с ростом длины выражений к некоторому конечному пределу $P_1(p)$. Получено явное представление функции вероятности $P_1(p)$ для всех конечных базисов, изучены аналитические свойства этой функции, исследовано её поведение в зависимости от свойств базиса.
Библ. 9.

Яшунский А. Д. ¹
1. МГУ, мех.-мат. факультет, Воробьёвы горы,
119992 Москва, Россия
е-mail: yashunsky@comtv.ru

Статья поступила 17 марта 2006 г.