О вероятностях значений случайных булевых выражений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

од

□□ЗОВТОЗЭ На правах рукописи В 7ПП7 УДК 519.7

Яшунский Алексей Дмитриевич

О ВЕРОЯТНОСТЯХ ЗНАЧЕНИЙ СЛУЧАЙНЫХ БУЛЕВЫХ ВЫРАЖЕНИЙ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

МОСКВА - 2006

003067039

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета им. М.В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор О. М. Касим-Заде.

Официальные оппоненты: доктор физико-математических наук,

профессор В. А. Малышев; кандидат физико-математических наук, доцент В. А. Стеценко.

Ведущая организация: Институт математики им. С. Л. Соболева

СО РАН.

Защита диссертации состоится 9 февраля 2007 г. в 16 часов 15 минут на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М. В. Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М. В. Ломоносова (Главное здание, аудитория 14-08).

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 9 января 2007 г.

Учёный секретарь диссертационного совета Д.501.001.84 в МГУ доктор физико-математических наук, профессор

В.Н. Чубариков

Общая характеристика работы Актуальность темы

Вероятностные модели и методы используются в различных разделах дискретной математики. Они могут выступать как в качестве инструмента решения задач, так и в качестве объекта исследования. При этом использование вероятностностых методов в некоторой задаче может привести к появлению вероятностной модели, представляющей самостоятельный интерес.

Примером плодотворного применения вероятностных методов могут служить исследования сложности булевых функций. Использование вначале комбинаторных (Б. А. Субботовская, Л. С. Хасин), а затем и вероятностных методов (JI. Вэлиант, А. Е. Андреев, Й. Хостад, М. Айтай) позволило существенно продвинуться в этой области. Достижения, полученные вероятностными методами, послужили причиной интереса к вероятностным пространствам булевых формул как таковым. X. Леф-манн и П. Савицкий1, а также Б. Шовин с соавторами2, исследовали вероятностное пространство булевых функций, заданных в виде случайных формул. В этих работах установливается связь между сложностью булевых функций и их вероятностью в указанном вероятностном пространстве.

А. Бродский и Н. Пиппенджер рассматривали аналогичные вероятностные пространства уже как самостоятельный объект исследования. В их работе3 изучается линейность, монотонность и самодвойственность булевых функций, реализованных в виде случайных булевых формул.

Исследование вероятностных автоматных моделей привело к созданию теории вероятностных автоматов (см. книгу Р. Г. Бухараева4). В рамках этой теории, в частности, возникает задача о синтезе источника вероятности. В более общем виде, как задача порождения значений вероятности булевыми функциями, эта задача исследовалась P. JI. Схирт-ладзе, Ф. И. Салимовым и Р. М. Колпаковым.

В задаче порождения значений вероятности достаточно естественно

'Lefmann Н., Savicky P. Some typical properties of large AND/OR Boolean formulas // Random structures algorithms. — 1997. — Vol. 10. — P. 337-351.

2Chauvin В., Flajolet Ph., Gardy D. and Gittenberger B. And/Or trees revisited // Combinatorics, probability and computing. — 2004. — Vol. 13 No. 4-5. — P. 475-497.

3Brodsky A., Pippenger N. The Boolean functions computed by random Boolean formulas or how to grow the right function // ArXiv Computer Science e-prints, Feb. 2003.

4Бухараев P. Г. Основы теории вероятностных автоматов — М.: Наука, 1985.

возникает модель, в которой бесповторные булевы формулы играют роль „преобразователей вероятности". Такая модель использовалась, в частности, С. Голдманом с соавторами5 для решения задачи распознавания булевых формул над специальными базисами.

Кроме отмеченных выше вероятостных моделей, следует также упомянуть следующие задачи, в которых были использованы вероятностные конструкции: надёжность схем (см. обзор C.B. Яблонского6), выполнимость конъюнктивных нормальных форм (в частности, А. Гоердт, Г. Сор-кин, А. А. Сапоженко), свойства логик с конечной моделью (Ю. В. Глеб-ский, В. В. Князев, В. А. Таланов, Р. Фагин и др.), построение вероятностных вычислительных устройств (В. В. Яковлев, Р. Ф. Фёдоров, А. В. Рябинин).

Таким образом, исследования свойств вероятностных моделей, связанных с булевыми функциями, представляются весьма актуальными.

Данная диссертация посвящена изучению свойств вероятностных пространств случайных булевых выражений. Порождение случайных булевых выражений может рассматриваться, в частности, как имитация некоторого „сложного" вычислительного процесса. В рамках такой интерпретации ставятся и решаются различные содержательные задачи о случайных булевых выражениях.

Кроме того, рассматриваемые в диссертации задачи, не являясь частным случаем или обобщением упомянутых ранее задач, связаны как с исследованием свойств случайных булевых формул, так и с задачей порождения значений вероятности.

Цель работы

В работе изучаются вероятностные пространства случайных булевых выражений. Основной целью диссертации является исследование задач о вероятностях значений случайных булевых выражений и связанных с ними комбинаторно-вероятностных свойств указанных пространств. Изучается зависимость вероятностей значений случайных булевых выражений от вероятностей входящих в них констант и от свойств базиса, над которым строятся выражения.

5Goldman S., Kearns M., and Schapire R. Exact identification of read-once formulas using fixed points of amplification functions // SIAM Journal on computing. — 1993. — Vol. 22, No. 4. — P. 705-726.

6Яблонский C.B. Некоторые вопросы надёжности и контроля управляющих систем // Математические вопросы кибернетики, вып. 1. — М.: Наука, 1988. — С. 5-25.

Методы исследования

В диссертации используются методы комбинаторного анализа, в частности, теории производящих функций, методы теории булевых функций, а также методы элементарной теории вероятности.

Научная новизна

Все основные результаты диссертации являются новыми. В диссертации получены следующие основные результаты.

1. Доказано существование предела вероятности значений случайных булевых выражений при стремлении сложности выражений к бесконечности и получено явное выражение этого предела (функция вероятности) для произвольного базиса.

2. Доказана непрерывность и бесконечная дифференцируемость функции вероятности произвольного базиса на интервале р 6 (0,1), исследовано поведение функции вероятности в граничных точках в зависимости от свойств базиса.

3. Изучены свойства базисов, имеющих постоянную функцию вероятности. Построены классы базисов с постоянной функцией вероятности, замкнутые относительно операции объединения.

4. Доказана возможность сколь угодно точного равномерного приближения произвольной непрерывной функции, отображающей отрезок [0,1] в себя, функциями вероятности булевых базисов.

5. Исследовано множество значений функций вероятности формул в произвольной точке р для различных базисов. Установлены необходимые и достаточные условия того, что такое множество для заданного базиса и заданного значения р является всюду плотным на отрезке [0,1].

Теоретическая и практическая ценность

Работа носит теоретический характер. Результаты работы могут быть использованы в дальнейших исследованиях в теории булевых функций и других разделах дискретной математики и математической кибернетики. Результаты диссертации могут быть полезны специалистам

Московского государственного университета им. М. В. Ломоносова, Института прикладной математики им. М.В. Келдыша РАН, Вычислительного центра им. А. А. Дородницына РАН, Института математики им. С. Л. Соболева СО РАН, Нижегородского государственного университета им. Н. И. Лобачевского, Новосибирского государственного университета, Санкт-Петербурского государственного университета.

Апробация работы

Результаты диссертации докладывались на семинаре «Синтез управляющих систем» под руководством академика РАН О. В. Лупанова (октябрь-ноябрь 2005 г. и март-апрель 2006 г.), на семинаре профессора О. М. Касим-Заде «Математические вопросы кибернетики» (ноябрь 2006 г.), на третьем Международном симпозиуме «Стохастические алгоритмы: теория и приложения» (3rd International Symposium «Stochastic Algorithms: Foundations and Applications», Москва, октябрь 2005 г.), на VII Международной конференции «Дискретные модели в теории управляющих систем» (Покровское, март 2006 г.), на XXVIII Конференции молодых ученых механико-математического факультета МГУ (Москва, апрель 2006 г.), на XVI Международной школе-семинаре «Синтез и сложность управляющих систем» (С.-Петербург, июнь 2006 г.).

Публикации

Основные результаты диссертации опубликованы в 4 работах автора, перечисленных в конце автореферата [1-4].

Структура и объём работы

Диссертация состоит из введения и пяти глав, разбитых на разделы. Текст диссертации изложен на 108 страницах. Список литературы содержит 42 наименования.

Краткое содержание диссертации

Во Введении содержится обзор результатов, полученных в смежных областях другими авторами, приводится постановка задач, дано краткое изложение основных результатов диссертации.

В главе 1 диссертации даётся формальное определение функции вероятности булева базиса В и доказываются теоремы о виде функции вероятности произвольного базиса.

Рассматривается множество всех правильно построенных булевых выражений, содержащих ровно п символов функций из некоторого заданного базиса7 В, а также константы 0 и 1. На множестве таких выражений определяется распределение вероятностей V следующим образом: для выражения Ф полагаем ■р(Ф) = ^-7г(Ф), где sn — число бесповторных формул сложности п над базисом Ъ с точностью до переименования переменных, а 7г(Ф) — произведение вероятностей констант в выражении Ф (вероятность 1 равна р, вероятность 0 равна 1 — р). Рассматривается предел вероятности выражений со значением 1, Р\,п{р) = = 1}, при 71 —► оо. Функция вероятности Р\{р) базиса В определяется как значение предела lim Р\ п(р), если предел существует, в противном случае

П—»00 '

считается, что значение функции вероятности в точке р не определено.

Для базиса В вводятся понятия базисного многочлена B(S) = 23fc=o \Bk\Sk, где Bk — множество всех функций от к переменных в базисе В, и характеристического многочлена A(T,F) = ]Cfc=o Хл=о akiTlFk~l, где а** — число единиц среди значений функций из Bk на наборах значений переменных, содержащих ровно i единиц. Основным результатом первой главы является

Теорема 7. Пусть В — некоторый базис с базисным многочленом B(S) и характеристическим многочленом A(T,F). Тогда для любого фиксированного р, 0 < р < 1, существует предел Р\{р) = lim P\,n(jp), и

П—»00

имеет место равенство:

р/п\-_А'р(т,сг-т)_

где и ист — однозначно определённые положительные действительные числа, образующие решение системы уравнений:

( а = 1 + иВ(а), , .

\1 =шВ'(а), W

с минимальным значением (среди всех решений (2)), А'Т и A'F — частные производные многочлена A(T,F), т = т(р) — однозначно опре-

7Предполагаем, что базис содержит хотя бы одну функцию от двух или более переменных.

делённая алгебраическая функция, удовлетворяющая уравнению:

Т(р)=р + шА(т(р), а - т(р)), и условиям 0 < т(р) < с.

Доказательство теоремы 7 опирается на построение формального языка булевых выражений над базисом В. Для построенного языка и его подъязыков выписываются связывающие их уравнения. Эти уравнения гомоморфно отображаются в алгебраические уравнения, связывающие производящие функции вероятностей булевых выражений. Анализ асимптотики коэффициентов производящих функций завершает доказательство теоремы.

В диссертации показано, что на любом замкнутом отрезке, целиком содержащимся в интервале (0,1) последовательность функций Р1п(р) сходится к Р\(р) равномерно, и при этом Р^п(р) = Р\(р) + 0(1/\/п).

Теорема 7 позволяет вычислить значение функции вероятности произвольного базиса В в любой точке 0 < р < 1. Поведение функции вероятности в граничных точках р = 0 и р = 1 описывает

Теорема 9. Пусть задан базис В. Значение .Р^О) (соответственно, ^1(1)) определено тогда и только тогда, когда в базисе В найдётся функция, отличная от линейной, существенно зависящей от всех переменных, не сохраняющей ноль (не сохраняющей единицу) функции. Если в В найдётся функция, не сохраняющая ноль (не сохраняющая единицу), то значение Р^О) (Р1(1)) вычисляется по формуле (1), в противном случае Р\(0) = О (Р1(1) = 1).

В главе 2 с помощью теорем 7 и 9, доказанных в главе 1, найдены явные выражения для функций вероятности некоторых конкретных базисов. Также исследуется непрерывность и дифференцируемость функций вероятности и рассматривается задача восстановления значения вероятности.

Результаты о непрерывности и дифференцируемости функций вероятности во внутренних и граничных точках отрезка [0,1] сформулированы в виде двух теорем.

Теорема 13. Для всякого базиса В функция Р\{р) является бесконечно непрерывно-дифференцируемой на интервале р € (0,1).

Теорема 14. Пусть В — базис с базисным многочленом В(8) и характеристическим многочленом А(Т, F). Функция Р\{р) имеет разрыв в точке р = 0 (соответственно, р = 1) тогда и только тогда, когда выполнены равенства адо = 0, а¡¡х = к\Вк\ (соответственно, аьк-1 = О, &кк — |Дь|) для всех к = 0,..., г.

Установленные выше свойства функций вероятности позволяют решать некоторые содержательные задачи о случайных булевых выражениях. Источником таких задач являются различные интерпретации модели случайных булевых выражений. В частности, с содержательной точки зрения случайные булевы выражения можно рассматривать как модельный объект, имитирующий ход некоторого „сложного" вычислительного процесса.

Одной из задач, возникающих в таком контексте, является задача восстановления значения вероятности. Эта задача заключается в том, чтобы для заданного базиса В по заданному значению функции вероятности Р\(р) определить значение р.

С помощью теоремы 13 в диссертации доказывается, что эта задача либо неразрешима вообще (если функция вероятности базиса В постоянная), либо число решений не превышает 2г — 2, где г — максимальное число переменных у функций базиса В.

В случае бинарного базиса (т. е. г = 2) доказывается более точный результат: функция вероятности является либо строго монотонной на интервале (0,1), либо постоянной при всех р € (0,1). В первом случае задача восстановления значения вероятности имеет единственное решение, а во втором случае — неразрешима.

В главе 3 исследуются свойства базисов с постоянной функцией вероятности. Интерес к таким базисам обусловлен, во-первых, тем, что они представляют собой особый случай в описанной выше задаче восстановления вероятности. Во-вторых, такие базисы позволяют строить различные примеры, демонстрирующие, какого рода информация о базисе может быть получена по его функции вероятности. Задача определения свойств базиса по его функции вероятности является ещё одним примером содержательной задачи, связанной с моделью случайных булевых выражений.

В рассмотрении базисов с постоянной функцией вероятности особую роль играют однородные базисы, т. е. базисы, все функции которых имеют одинаковое число переменных. Доказывается, что коэффициенты характеристического и базисного многочленов однородных базисов с по-

стоянной функцией вероятности удовлетворяют некоторым специальным соотношениям.

Теорема 17. Пусть В — однородный базис с базисным многочленом 5(5) и характеристическим многочленом А(Т, Р), и пусть <1$ — ■

Функция вероятности базиса В постоянна и равна С, 0 < С < 1, при всех р € (0,1) тогда, и только тогда, когда разности — С образуют

С— 1

геометрическую прогрессию со знаменателем

Таким образом, у однородного базиса с постоянной функцией вероятности доли единичных значений на слоях булева куба „колеблются" около величины С — постоянного значения функции вероятности.

Исследование неоднородных базисов во многих случаях сводится к рассмотрению однородных. В частности, выполнено

Следствие 9. Любое конечное объединение однородных базисов с постоянными функциями вероятности, равными некоторой постоянной С, одной и той же для всех базисов, является базисом с постоянной функцией вероятности, равной С.

Утверждение следствия 9 можно обратить при некоторых дополнительных условиях:

Теорема 24. Пусть базис В имеет вид Вд и Вд+1 и... и и Вг, где ц > 0, Вд 0 и Вт ^ 0. Пусть число а, соответствующее базису В, является алгебраическим, степени г — д + 1. Пусть функция вероятности базиса В постоянна и равна некоторому рациональному числу С. Тогда каждое из множеств Вк для к = д,..., г является базисом с постоянной функцией вероятности, равной С.

С помощью следствия 9 строятся примеры, показывающие, что по заданной функции вероятности базиса, вообще говоря, невозможно определить ни число функций в базисе, ни количество переменных у функций базиса. Более того, для произвольного базиса В по функции вероятности невозможно определить принадлежность некоторой функции этому базису. Однако, теорема 24 показывает, что при соответствующем сужении класса рассматриваемых базисов информацию о долях единичных значений функций на слоях булева куба по функции вероятности базиса получить всё же можно.

В главе 4 рассматривается вопрос о том, насколько богат класс функций вероятности булевых базисов. Доказывается, что существуют базисы, функции вероятности которых сколь угодно близки к любой наперёд заданной непрерывной функции /(р), отображающей отрезок [0,1] в себя.

Доказательство теоремы о равномерном приближении функциями вероятности конструктивно и осуществляется в два этапа. Вначале доказывается теорема о равномерном приближении многочленов функциями вероятности.

Теорема 25. Пусть В — некоторый базис с базисным многочленом B(S) и характеристическим многочленом A{T,F), и базис В^ получается из В добавлением в каждую функцию из В ровно m несущественных переменных. Тогда для функции вероятности Р^т\р) базиса £(т) выполняется соотношение:

причём сходимость является равномерной по р на отрезке [0,1].

Затем с помощью теоремы Вейерштрасса в формулировке С. Н. Берн-штейна8 (о равномерном приближении непрерывных функций многочленами) доказывается

Теорема 27. Пусть f{p) — непрерывная функция, отображающая отрезок [0,1] в себя. Тогда для любого е > 0 найдётся базис Вс с функцией вероятности Р\{р) такой, что для всякого р £ [0,1] имеет место неравенство I f(p) — Pi(p)| < е.

Конструкция, используемая в теореме 27 для построения базиса Ве, является достаточно гибкой и позволяет строить приближающие базисы с некоторыми наперёд заданными свойствами. В частности, в диссертации доказано, что базис ВЕ в теореме 27 может быть выбран так, чтобы все функции базиса оказались различными, а все переменные каждой функции — существенными.

В главе 5 в вероятностных пространствах булевых выражений рассматриваются вероятности некоторых событий, связанных с бесповторными булевыми формулами.

"Bernstein S. Démonstration du théorème de Weierstrass fondée sur le calcul des probabihtées // Comm. Soc. Math. Kharkov. - 1912. - Vol. 13. - P. 1-2.

Каждому булеву выражению ставится в соответствие единственная с точностью до переименования переменных бесповторная формула, из которой это выражение получается в результате подстановки констант вместо переменных. Функцией вероятности бесповторной булевой формулы Ф, обозначаемой Р1(р|Ф), называется вероятность того, что случайное выражение Ф принимает значение 1, при условии, что оно порождается формулой Ф. Рассмотренные ранее функции Р11П(р), пределом которых является функция вероятности базиса, связаны с функциями Рх(р|Ф) равенством Ра,„(р) = ¿Е|4|=п А(р|Ф)-

Вычисление функции вероятности отдельно взятой бесповторной формулы Ф не представляет особой сложности, однако получить описание множества всевозможных функций вероятности бесповторных формул над заданным базисом В оказывается гораздо более сложной задачей. Наиболее продуктивным методом исследования функций вероятности формул над заданным базисом оказалось рассмотрение множеств их значений при фиксированных значениях р.

Для целей классификации таких множеств представляется естественным рассматривать их замыкания относительно операции предельного перехода. Множество значений функций вероятности формул для базиса В в точке р, дополненное всеми своими предельными точками, обозначается IУв{р)-

Рассмотрение различных базисов В позволяет выявить некоторые специальные случаи множеств \¥в(р). Если базис целиком лежит в К (множестве конъюнкций переменных или констант), в Б (множестве дизъюнкций переменных или констант), или в Ь (множестве линейных булевых функций), то множество Игв(р) имеет единственную предельную точку (0, если В С К; 1, если В С А; 1/2, если В С Ь). В этих случаях множество №в{р) является нигде не плотным на отрезке [0,1].

У базисов {&, ->} и {&, V} при любом р € (0,1) множество \¥в(р) совпадает с отрезком [0,1], т.е. все точки множества являются предельными. Совпадение множества \¥в{р) с отрезком [0,1] означает, что в сколь угодно малой окрестности произвольной точки отрезка [0,1] обязательно лежит значение функции вероятности некоторой бесповторной формулы над В. Условия, при которых множество У/в{р) совпадает с отрезком [0,1], описываются следующей теоремой.

Теорема 34. Пусть задан базис В и число р € (0,1). Множество \Ув(р) совпадает с отрезком [0,1] тогда и только тогда, когда В % Ь, К, В и 0,1 € \Ув{р).

Кроме упомянутых выше случаев совпадения Wß(p) с отрезком [0,1] и множеств Wb(p) с единственной предельной точкой, возможны и другие, более сложно устроенные множества Wb (р) ■ Например, для базиса В = {ху V yz V xz} при р € (0,1/2) множество Wb{p) содержит бесконечно много предельных точек на отрезке [0,р], но не является всюду плотным на этом отрезке.

В заключение автор хотел бы выразить глубокую признательность своему научному руководителю доктору физико-математических наук, профессору О. М. Касим-Заде за постановку задачи, постоянное внимание к работе, многочисленные плодотворные обсуждения, и огромную моральную поддержку.

Публикации автора по теме диссертации

1. Яшунский А. Д. Об асимптотике вероятности значений случайных булевых выражений // Дискретный анализ и исследование операций. — 2006. - Серия 1. Том 13, Ш - С. 59-96.

2. Yashunsky A.D. On the properties of asymptotic probability for random Boolean expression values in binary bases // Proc. of the 3rd Int. Symp. "Stochastic Algorithms: Foundations and Applications" (SAGA 2005), Moscow, October 20-22, 2005. Lecture Notes on Computer Science. Vol. 3777. Berlin: Springer, 2005. — P. 202-212.

3. Яшунский А. Д. О равномерном приближении непрерывных функций функциями вероятности булевых базисов // Дискретные модели в теории управляющих систем: VII Международная конференция, Покровское, 4-6 марта 2006 г.: Труды. — М.: МАКС Пресс, 2006. С. 426-430.

4. Яшунский А. Д. О преобразованиях вероятности бесповторными булевыми формулами // Материалы XVI Международной школы-семинара «Синтез и сложность управляющих систем» (Санкт-Петербург, 26-30 июня 2006 г.) — М.: Изд-во механико-математического факультета МГУ, 2006. — С. 150-155.

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. Подписано в печать ¿С>. 12 06

Формат 60 х 90 1 /16 . Усл. печ. л. 0,75

Тираж 100 экз. Заказ 35

Введение

Глава 1 Нахождение функции вероятности

1.1 Основные понятия и определения

1.2 Элементарные примеры.

1.3 Языки и производящие функции.

1.4 Функция вероятносги на интервале (0,1).

1.5 Функция вероятности в граничных точках

1.6 Связь с другими вероятностными пространствами

1.7 Функции вероятности базисов первого порядка.

Глава 2 Некоторые свойства функций вероятности

2.1 Примеры функций вероятности.

2 2 Непрерывность функции вероятности на интервале (ОД)

2.3 Непрерывность функции вероятносги в граничных точках

2.4 Задача восстановления вероятности

Глава 3 Постоянство функции вероятности

3.1 Векторное пространство многочленов.

3 2 Постоянство функции вероятности однородных базисов

3 3 Постоянство функции вероятности неоднородных базисов

Глава 4 Приближение непрерывных функций функциями вероятности

4.1 Равномерное приближение многочленов.

4 2 Равномерное приближение непрерывных функций.

4 3 Преобразование аппроксимирующих базисов.

Глава 5 Функции вероятности формул

5.1 Постановка задачи.

5.2 Некоторые примеры.

5.3 Всюду плотные множества значений.

Современное понимание термина „вычисление" столь широко, что давать определение этого понятия представляется довольно затруднительным. Неформально можно говорить, что вычислением называется процесс преобразования исходных данных (чаще всего числовых или текстовых), согласно некоторой процедуре (алгоритму) Формализация понятия „вычисление" приводит к математическим моделям, таким как машины Тьюринга, конечные автоматы, логические схемы, и многие другие.

Эти модели, как правило, являются детерминированными, но могут быть модифицированы таким образом, что выполняемые ими действия приобретут случайный характер: элементы случайности могут быть внесены в исходные данные вычисления или же в саму процедуру. Результатом таких модификаций будет некоторая модель случайных вычислений.

Изученные к настоящему времени модели случайных вычислений можно условно разделить на две группы: к первой относятся модели, в которых случайность являехся „неотъемлемой" частью — в силу природы моделируемого обьекта, или же потому, что сама случайность является обьекюм изучения. Ко вюрой группе относятся модели, в которых случайность является „привнесённой извне". При этом случайность может быть как инструментом построения более удобной вычислительной модели, так и инструментом изучения модели Такая классификация моделей, как уже отмечалось, достаточно условна, так как не всегда легко различить „врождённые" и „привнесенные" элементы случайности в вычислительной модели.

Приведём краткий обзор основных направлений исследований в области случайных вычислений. Хотя, строго говоря, большинство упомянутых в нём задач связаны с темой данной работы лишь косвенным образом, знакомство с ними позволяет лучше понять место и значение данной работы в общей картине исследований в области случайных вычислений. Сначала перечислим некоторые работы, рассматривающие модели, которые можно отнести к первой группе.

Одними из первых вычислительные системы с элементами случайности рассмохрели Дж. фон Нейман (J. von Neumann) [36], а также Е Мур (Е. Moore) и К. Шеннон (С. Shannon) [35]. Эти работы посвящены построению надёжных вычислительных схем из ненадёжных элементов. Случайность в таких сис1емах возникает из-за возможных неисправностей некоторых элементов схемы, т.е. у каждого элемента схемы существует ненулевая вероятность сбоя. В указанных работах предложены меюды построения схем высокой надёжности из элементов с ненулевой (но достаточно малой) вероятностью сбоя. Схемы из ненадёжных элементов рассматривались также С Г. Гиндикиным и А. А. Мучником: в [3] они исследовали проблему полноты базисов из ненадёжных элементов. Этой задачей занимались и многие другие авторы (см. обзор в [19]).

Другим примером вычислительных систем с элементами случайное!и могут служить вероятностные автоматы, т.е. авюматы, у которых переходам между состояниями и выходным значениям приписаны некоторые вероятности. Понятие вероятностного автомата было сформулировано в середине 60-х годов прошлого века, и с тех пор была построена достаточно обширная теория вероятностных автоматов, обзор результатов и проблем которой можно найти в книге Р. Г. Бухараева [2]. Одним из интересных результатов теории вероятностных автоматов является утверждение о возможности представления любого вероятностного автомата в виде последовательного соединения „источника вероятности", порождающего случайным и независимым образом символы некоторого алфавита с заданными вероятностями, и детерминированного конечного автомата. Ввиду наличия подобного представления, особый интерес приобретает задача о синтезе такого „источника вероятности".

Впервые задача порождения значений вероятности с помощью булевых преобразователей была, по-видимому, рассмотрена Р. Л. Схиртладзе [14]. В его работе предложен метод получения всех двоично-рациональных значений вероятности пухём комбинирования бернуллиевских случайных величин, имеющих вероятность обращения в 1 равную 1/2, с помощью контактных схем. В дальнейшем вопросы порождения значений вероятности также исследовались Ф И. Салимовым [11].

Наиболее широкое развитие эта проблематика получила в работах Р. М. Колнакова, который рассматривал различные постановки задачи порождения значений вероятности. В его работах (в частности, [9]) получены критерии, позволяющие по искомому значению и заданным исходным значениям вероятности определить, порождается ли искомое значение булевой комбинацией бернуллиевских случайных величин с вероятностями из заданного множества

В рабохе А. Бродского (А. ВгосМу) и Н. Пипиенджера (К. Pippenger) [25] рассматривается модель случайного порождения булевых функций. Функции порождаются с помощью формул, состоящих из символов некоторой функции-связки и литералов из некоторого конечного множества. Для каждого п > 0 на множестве формул сложности п задаётся распределение вероятности, причём для п = 0 оно произвольное, а для следующих значений п определяется естественным образом по индукции. Исследуется предельное (при п —> оо) распределение вероятности, индуцируемое случайными формулами на множестве булевых функций. Установлено, при каких условиях на функцию-связку и на распределение вероятности при п = О, функция, реализуемая случайной формулой, почти наверное обладает свойствами линейности, монотонности, самодвойственности.

Все перечисленные выше работы так или иначе рассматривали случайность как неотъемлемую часть модели. Приведём теперь несколько примеров работ, в которых элементы случайности являются скорее привнесёнными (т. е. работ, относящихся ко второй группе, согласно приведённой ранее классификации). Следует отметить, что к этой группе мы относим и те работы, в которых вероятностный аспект комбинаторных методов исследования присутствовал неявно.

Так, например, „закон 0 и 1" для логик первого порядка с конечной моделью изначально сформулирован без привлечения понятия вероятности, однако имеет, по сути, вероятностную природу. Этот закон, впервые установленный, по-видимому, Ю. В. Глебским с соавторами [4], заключается в следующем. Пусть задана некоторая замкнутая формула в логике первого порядка, составленная из предикатов, кванторов и логических связок. Для этой формулы рассматривается истинность на конечной модели при всевозможных интерпретациях сигнатуры. В [4] показано, что такая формула являехся либо тождественно истинной, либо тождественно ложной на почти всех интерпретациях сигнатуры при стремлении мощности модели к бесконечности. Закон 0 и 1 был независимо доказан Р. Фагиным (R. Fagin) в вероятностной формулировке [28]. Дальнейшие исследования В. А. Таланова [15] и В. В. Князева [8] в этой области были направлены на доказательство закона 0 и 1 для более сложных логических систем.

Комбинаторно-вероятностные методы применялись для исследования сложности булевых функций. В ранних работах, таких как доказательство нижней оценки сложности в классе формул Б. А. Суббоговской [13] и оценка сложности симметрических функций JI. С. Хасиным [16], мех оды исследований позиционируются скорее как чисто комбинаторные. Однако, их вероятностная природа раскрывается явно в более поздних работах, использующих сходную аргументацию Применение вероятностных методов позволило существенно продвинуться в решении различных вопросов сложности булевых функций. Так, например, JI. Вэлиант (L. Valiant) [38] получил верхнюю оценку сложности функции голосования, в работах А. Е. Андреева [1] и Й. Хостд (J. Hstad) [33] получены нижние оценки в классе контактных 7Г-схем и формул, а М. Айтаи (М. Ajtai) [22] исследовал с помощью вероятностных методов вопросы сложности в классе схем ограниченной глубины обзор дальнейших работ в этом направлении см. в [24]).

Расширением вероятностного подхода к вопросам сложности булевых функций являются работы X. Лефманна (Н. Lefmann) и П. Савицкого (P. Savicky) [34, 37]. В этих работах рассматривается некоторое специальное, но достаточно естественное распределение вероятности на множестве формул над заданным базисом, во многом аналогичное распределению, рассмотренному в рабохе [25] Такое распределение индуцирует распределение вероятное™ на множестве булевых функций. Основной результат указанных работ заключается в установлении неравенств, связывающих вероятность булевой функции с её сложностью (рассмотрены случаи базисов {&, ф, 1} и {&, V}). Для базиса {&, V} оценки, связывающие вероятность и сложность функции, были улучшены в работе Б. Шовин (В. Chauvin) с соавторами [26].

Ещё одной областью применения вероятностных методов является исследование задачи выполнимости конъюнктивных нормальных форм (КНФ), т. е. задачи о существовании набора значений переменных, обращающих заданную КНФ в единицу. Интерес к г1аким задачам обусловлен тем, что задача выполнимости 3-КНФ (т. е. КНФ, у которых каждая элементарная дизъюнкция содержит только три символа переменных) являехся NP-полной. Сложность непосредственного рассмотрения задачи выполнимости 3-КНФ заставляет обратиться к вероятностным меюдам исследования. Установлено, что вероятность выполнимости случайно выбранной КНФ зависит от отношения числа элементарных дизъюнкций в КНФ к числу используемых символов переменных. Среди КНФ, у которых эю отношение достаточно мало, почти все являются выполнимыми, и наоборот — среди КНФ, у которых это отношение достаточно велико, почти все невыполнимы Для 2-КНФ доказано (в частности, А. Гоердтом (A. Goerdt) [30]), что существует значение с = 1, являющееся „порогом выполнимости" случайной 2-КНФ. Для 3-КНФ существование точного „порога выполнимости" остаётся открытым вопросом. Численные эксперименты показывают, что если пороговое значение существует, то оно равно примерно 4.25. К настоящему моменту строго доказано, что при с < 3.52 3-КНФ почти наверное выполнима (М.Т. Хаджиакхай (М Т. Hajiaghayi) и Г.Б. Соркин (G.B. Sorkin) [32]), а при при с > 4.31743 — почти наверное невыполнима (А. А. Сапоженко [12]).

Ишерпретация булевых функций как „преобразователей вероятности", упоминавшаяся ранее в связи с задачей порождения вероятностей, была использована в качестве инструмента при решении задач машинного обучения В работе С. Голдмана (S. Goldman), М. Кёрнса (М. Kearns) и Р Шапира (R. Schapire) [31] приведён алгоритм восстановления произвольной заданной бесповюрной формулы по преобразованию вероятности, которое задаёт соответствующая формуле булева функция. Рассмотрены формулы в базисе из функции голосования и в базисе из штриха Шеффера.

Ещё одним примером применения вероятностных методов исследования могут служить приведённые в книге Р В. Хемминга [17] наблюдения о влиянии округлений на результаты вычислений. С помощью модели случайных арифметических вычислений доказывается, что распределение старших разрядов в числах, получающихся в результате большого количества последовательных случайных арифметических операций, не является равномерным: оно смещено в сторону меньших значений старших разрядов. Такое распределение способствует нераспространению ошибок округления при выполнении длинной последовательности арифметических операций.

Вероятностные подходы являлись не только инструментом исследования в других задачах, но и рассматривались в качестве инструмента построения вычислительных систем. К этой области относится книга В. В. Яковлева и Р. Ф. Фёдорова „Стохастические вычислительные машины" [21], посвященная различным аспектам конструирования вычислительных устройств, функционирование которых основано на преобразовании случайных величин Примером такого вычисления может служить нахождение произведения чисел р\ и Р2 как вероятности обращения в единицу конъюнкции двух независимых бернуллиевских случайных величин, вероятность обращения в единицу которых равна, соответственно, р\ и Р2- (При этом для реализации подобной схемы вычисления требуется устройство, порождающее именно независимые случайные величины.) В книге исследуются вопросы оперирования со случайными и псевдослучайными величинами, а также вопросы прямого и обратного преобразования между детерминированной и вероятностной формами представления информации.

Другой пример использования вероятностных методов в качестве инструмента вычислений можно найти в работе А. В. Рябинина [10]. В ней рассматриваются вероятностные вычисления, реализуемые конечным автоматом. Автомат, преобразующий некоторую случайную последовательность, для которой известны вероятности появления символов, задаёт очевидным образом некоторое преобразование вероятности, которое можно рассматривать как функцию действительного переменного, вычисляемую этим автоматом. В работе изучен класс функций действительного переменного, которые реализуются указанным способом, а также рассмотрены некоюрые сложностные аспекты такой реализации.

Направления исследований моделей случайных вычислений далеко не исчерпываю 1ся перечисленными выше. В частности, существует множество работ, посвященных вероятностным аспектам машин Тьюринга и других видов алгоритмов, однако, эти вычислительные модели достаточно далеки от рассматриваемых в диссертации, поэтому не упомянуты в приведённом обзоре.

В данной диссертации исследуются свойства случайных булевых выражений, составленных из символов функций, принадлежащих некоторому заранее фиксированному множеству, и символов констант 0 и 1. Такая модель относится к первой группе — распределение вероятности является здесь неогьемлемой частью и, фактически, одним из объектов исследования. Эта модель, вообще говоря, не является ни обобщением, ни частным случаем какой-либо из упомянутых выше моделей, однако некоторые аналогии, касающиеся элементов модели и рассматриваемых задач, провести все-таки можно. Прежде всего, распределение вероятности на множестве булевых выражений имеет общие черты с распределениями на множестве формул, рассмотренных в работах [25, 34, 37, 26]. „Преобразования вероятности", связанные с булевыми формулами, описанные в работах [31, 21, 10], также рассмотрены в данной диссертации в контексте свойств случайных булевых выражений. Наконец, отметим, что исследование свойсгв случайных булевых выражений направлено на установление общих закономерностей булевых вычислений, по аналогии с закономерностями для арифметических вычислений, приведёнными в книге [17].

Приведём краткий список обозначений и понятий, используемых при дальнейшем изложении. Булевы функции обозначаются следующим образом: к, — конъюнкция, V — дизъюнкция, х или -¡х — отрицание, ф — сумма ио модулю 2, I — стрелка Пирса, / — шгрих Шеффера, —» — импликация.

Функция /*(х\,., Хк) = /(яъ • называется двойственной функции /. Функция /(^1,. ,хп) называется сохраняющей ноль (сохраняющей единицу), если /(0,., 0) = 0 (соответственно, /(1,., 1) = 1). Симметрическими называются функции, значения которых сохраняются при любой перестановке переменных.

Булевым кубом размерности 5 называется множество всех двоичных наборов длины б: {О, I}5. Множество всех наборов й-мерного булева куба с весом к, т. е. содержащих ровно к единиц, называется к-и слоем булева куба

Для числа сочетаний из п по к элементов используется обозначение (£).

Нумерация формул в тексте — отдельная в каждой главе. Нумерация всех утверждений: теорем, лемм, и следствий — сплошная во всем тексте диссертации.

Проиллюстрируем модель случайных булевых выражений простой задачей пусть рассматриваются выражения, составленные из символов конъюнкции, дизьюнкции и констант 0, 1. Будем считать, что выражения с одинаковым количеством функциональных символов равновероятны, а константы 0 и 1 встречаются в выражениях с равной вероятностью. Чему будет равна вероятность выражений со значением 1?

Легко заметить, что двойственные выражения, получающиеся друг из друга заменой каждой из функций и констант на двойственную, имеют равные вероятности. При эхом значения двойственных выражений противоположные. Следова:ельно, для каждого выражения со значением 0 найдётся двойственное ему выражение со значением 1, имеющее ту же вероятность. Таким образом, вероятности выражений со значением 0 и выражений со значением 1 равны между собой, и равны 1/2.

Приведённая выше задача решается элементарными методами, однако, в случае произвольного базиса и неравномерного распределения вероятностей коне I ант решение задачи уже далеко не очевидно

Опишем общую постановку задачи о случайных булевых выражениях. Пусть задан некоторый набор В булевых функций (возможно, с повторениями), далее именуемый базисом. В качестве пространства элементарных исходов будем рассматривать множество всех булевых выражений сложности п над базисом В, т. е. множество всех правильно построенных формул, сосюящих из символов функций базиса В, символов констант 0, 1, и содержащих ровно п функциональных символов1. Примеры булевых выражений: (0&1) V 0, (1 V 0)&(0 V 0), ((1&0)&0)&0.

Каждое булево выражение естес! венным образом получается из некоторой бесповторной формулы в том же базисе (единственной, с точностью до переименования переменных) в результате подстановки констант 0 и 1 вместо её переменных. Сложность выражения равна числу символов функций в порождающей его бесповторной формуле. Например, булево выражение (1 V 0)&(0 V 0) сложности 3 получается подстановкой констант в бесповторную формулу {х\ V Х2)&(%ъ V ж4).

Будем считать, что все бесповторные формулы сложности п равновероятны, т.е., что бесповторная формула, порождающая булево выражение, выбирается случайно и равновероятно из всех бесповторных формул сложное: и п. Пусть 5„ — число бесповторных формул сложности п над базисом В (с точностью до переименования переменных). Тогда вероятность каждой формулы равна 1/бп. Будем считать, что вместо каждой из переменных формулы подставляется константа 1 с вероятностью р или константа 0 с вероятностью 1 —р. Обозначим произведение вероятностей констант, входящих в выражение Ф через 7г(Ф). Вероятность "Р{Ф} выражения Ф определим следующим образом:

Р{Ф} = 1тг(Ф).

Вероятность Р{Ф} является функцией величины р — вероятности подста

1 Другие определения сложности выражений и получающиеся при их использовании вероятностные пространства будут рассмотрены позже новки константы 1 вместо переменной бесповторной формулы. Определим функции Р\,п(р) и Po,n{p)i равные, соответственно, вероятностям выражений со значениями 1 и 0 в множестве выражений сложности п:

Ф=1 Ф=0

Очевидно, что Р\>п(р) + Ро,п(р) — 1, поэтому достаточно исследовать поведение лишь одной из этих величин: Р\,п(р). Как будет показано далее, для любою базиса В существует предел lim Р\п{р) во всех точках р интервап—>00 ' ла 0 < р < 1. Этот предел будем обозначать Р\{р) и называть функцией вероятности базиса В. Фактически, величина Р\(р) может рассматриваться как приближённое значение вероятности обращения в 1 значения случайного выражения достаточно большой сложности, причём, как установлено в диссертации, погрешность такого приближения для выражений сложности п равна 0(1/\/п).

Основной целью данной диссертации является исследование задачи о вероятностях значений булевых выражений в описанной выше постановке, изучение общих свойств функции вероятности Р\(р) и её поведения в зависимости от базиса В, а также других возникающих здесь задач.

Функцию вероятности возможно также интерпретировать как результат работы некоторого устройства, аналогичного упомянутым ранее „преобразователям вероятности". Будем считать, что такой преобразователь вероятности, соответствующий базису В, функционирует следующим образом: получая на вход некоторую вероятность р, этот преобразователь вычисляет значение Р\(р) для базиса В. Такое вычисление может производиться, например, путём произведения серии „экспериментов", т.е. построения некоторого количества случайных выражений достаточно большой сложности и вычисления их значений. По сути, такая серия экспериментов является последовательностью испытаний Бернулли, поэтому в силу центральной предельной теоремы статистика этих экспериментов сходится к функции Phn(p), которая, в свою очередь, с ростом п приближается к Р\(р) со скоростью 0(1/\/п). (Описанные представления об экспериментах и статистической интерпретации функции Р\(р) носят содержательный характер и приведены здесь исключительно в иллюстративных целях. Эти вопросы требуют отдельного изучения и в данной работе не рассматриваются.)

В терминах такого преобразователя вероятности сформулируем несколько содержательных задач. Прежде всего, это задача анализа преобразователя, т е нахождения функции Р\(р) по заданному базису В. Вторая задача заключается в восстановлении для заданного фиксированного базиса В вероятности р по заданному значению Р\{р), или, в более общей постановке, в получении возможно большей информации о значении р по заданному значению Р^р). Третья задача, именуемая задачей о „чёрном ящике", заключается в получении информации о заранее неизвестном базисе В (содержимом „чёрного ящика") по заданной функции вероятности Р\{р). Эти три задачи и некоторые их модификации рассматриваются в данной диссертации

В первой главе диссертации решается задача анализа для булевых выражений над фиксированным базисом, доказывается ряд теорем, позволяющих по заданному базису В получить его функцию вероятности в явном виде. Общий ход рассуждений изложен ниже.

Пусть базис В фиксирован. Функцию Рг,п{р) при каждом значении п представим в виде отношения £п/5га. Здесь есть числовая функция от р, равная сумме величин 7г(Ф) по всем выражениям Ф сложности п со значением 1, а 5„ — упомянутое выше число бесповторных формул сложности п над базисом В От последовательностей ¿п, 5П и ¡п = 5П — ¿п перейдём к их производящим функциям Т(г), в (г) и Р(г) [6]

Множество булевых выражений над базисом В можно рассматривать как формальный язык над некоторым алфавитом. Применение метода М. П Шютценберже (М. Р. БсЫ^гепЬе^ег) [27] позволяет получить систему уравнений, связывающую производящие функции Т(г) и Р(г): она является гомоморфным образом системы уравнений в языках, связывающей язык выражений со значением 1 с языком выражений со значением 0. Эти языки — контекстно-свободные, поэтому система уравнений, связывающая Т(г) и Р(г), является алгебраической.

Для записи этой системы уравнений будем использовать два многочлена, строящихся по базису В: базисный многочлен В(8) = ^2к где Вк есть множество функций от к переменных в базисе В, и характеристический многочлен2 А(Т,Р) = Т^кТ^ч^г^Р^1-, где а^ есть число единиц среди значений функций из Вк на наборах значений переменных с г единицами и к — г нулями. С помощью многочленов В {в) и А(Т, Р) система уравнений, о которой шла речь выше, записывается в виде:

Г Т(г)=р + гА(Т(г),Р(г)), ( ] ОД = 1 - р + гВ{Т{г) + ОД) - гА(Т(г), ОД). [1)

Для нахождения асимптотики коэффициентов производящих функций Т(г) и Р(г) используется теорема Дрмота-Лэлли-Вудса [29] (теорема3 2). Она позволяет усыновить асимптотическое поведение коэффициентов производящих функций Т(г) и .Р(г) по системе уравнений (1) без непосредственного

Характеристический многочлен в виде А(р,1 - р) для базиса из одной функции исполыуется в работах [25, 35]

З3дес1., и далее во Введении, теоремы приводятся с номерами из основного текста нахождения решений уравнений.

Производящие функции T(z) и F(z) рассматриваются как функции комплексного переменного. Согласно теореме 2, при выполнении некоюрых дополнительных условий (см. раздел 1.3 3) ряды T(z) и F{z) сходятся в окрестности нуля и имеют один и тот же радиус сходимости и. При эгом ш являе!ся ближайшей к нулю особой точкой у каждой из Э1их функций. Асимптотическое поведение коэффициентов рядов T(z) и F(z) определяется по коэффициешам соответствующих рядов Пюизо [7] в окрестности

ТОЧКИ Lü.

С помощью теоремы 2 доказывается следующее утверждение

Теорема 7. Пусть В — некоторый базис с базисным многочленом B(S) и характеристическим многочленом A(T,F). Тогда для любого фиксированного р, 0 < р < 1, существует предел Р\(р) = lim Р\,п{р), и имеет место п—»00 ' равенство: д (р) =Л'р(т,а-г)

1 {Р) - А'т(т, а — т) + A'f(t, и — г)' 1 j где lü и а — однозначно определённые положительные действительные числа, образующие решение системы уравнений а = 1 + иВ(а), 1 = LüB'ia), W с минимальным значением |и>| (среди всех решений (3)), А'Т и A'F — частные производные многочлена A(T,F), т = т(р) — однозначно определённая алгебраическая функция, удовлетворяющая уравнению: т(р) = р + и;А{т{р),сг - т(р)), и условиям 0 < т(р) < а.

Более детальный анализ поведения функций T(z) и F(z) в окрестности их общей особой точки ш позволяет не только получить явное выражение для значения предела величин PiíTl(p), но и оценить скорость сходимости Р\,п(р) к Р^р) при п -> оо: Р1(П(р) = Pi(p) + 0(1/y/ñ).

Условия 'хеоремы 7 требуют принадлежности р интервалу 0 < р < 1 В случае р = 0 или р = 1 система уравнений (1) может не удовлетворять условиям теоремы 2, вследствие чего утверждение, аналогичное теореме 7, в соответствующей точке не выполняехся. Анализ поведения предела lim Р\п{р) в точках р = 0 и р = 1 для всевозможных базисов позволил

П-+ОС ' доказать следующую теорему:

Теорема 9. Пусть В — некоторый базис. Значение Р\(0) (соответственно, Pi(l)) определено тогда и только тогда, когда в базисе В найдётся функция, отличная от линейной, существенно зависящей от всех переменных, не сохраняющей ноль (не сохраняющей единицу) функции. Если в В найдётся функция, не сохраняющая ноль (не сохраняющая единицу), то значение Р\(0) (-Pi(l)) вычисляется по формуле (2), в противном случае Р1(0) = 0(Р1(1) = 1)

Если сложность выражения определяется каким-то образом, отличным от указанного ранее, то вероятностное пространство выражений сложности п, естественно, будет другим Функцию Р\,п(р) можно определить и в этом случае, но предел Р\(р) = lim Р\ п(р) может и не существовать. В разделе

П—»00 '

1 6 рассмотрены случаи определения сложности как количества символов констант в выражении, и как суммарного количества символов консхант и функций. Показано, что если функция вероятности определена, то её явное выражение совпадает с указанным в теореме 7 с точностью до значений ш, <т и т(р). Фактически, описанное изменение меры сложности булевых выражений оказывается равносильно замене переменной р функции вероятности

Во второй главе диссертации приводятся примеры функций вероятности различных базисов и исследуются простейшие свойства функций вероятное] и Функции вероятности в рассмотренных примерах оказываются непрерывными и дифференцируемыми при 0 < р < 1, а в точках р = 0 и р — 1 функция вероятности, вообще говоря, может иметь разрывы.

Непрерывность и дифференцируемость функции вероятности на интервале 0 < р < 1 доказывается в работе в общем случае.

Из теоремы 7 следует, что функция вероятности Р\(р) при 0 < р < 1 представляется в виде композиции некоторой дробно-рациональной функции Р(х) (зависящей от характеристического многочлена) и алгебраической функции т(р), т.е. Р\(р) = Р(т(р)). Показано, что функция т(р) является бесконечно непрерывно-дифференцируемой, монотонно возрастающей функцией при 0 < р < 1. Кроме того, функция вероятности представляем в виде Р\(р) = шА'р(т(р), а — т(р))т'(р), откуда вытекает:

Теорема 13. Для всякого базиса В функция Р\(р) является бесконечно непрерывно-дифференцируемой на интервале 0 < р < 1.

Случаи, когда функция вероятности не определена в точке р = 0 или р = 1 (устранимые разрывы) рассмотрены выше в теореме 9. Условия наличия у функции вероятности разрывов первого рода (т.е. РАО) ф \\тР\(р) или р—>0

Pi(l) ф limPi(^)) сформулированы в виде следующей теоремы

Теорема 14. Пусть В — базис с базисным многочленом В(£) и характеристическим многочленом А(Т,Р). Функция Р\(р) имеет разрыв в точке р = 0 (соответственно, р = 1) тогда и только тогда, когда выполнены равенства а&о = 0, а^ = к\Вь\ (соответственно, акк-1 = О, а^ = \Вк\) для всех к = О,., г.

Полученные условия непрерывности и дифференцируемоеги функции вероятности позволили проанализировать задачу о восстановлении значения вероятности р по заданному значению Р\{р) для фиксированного базиса В. В частности, оказывается, что для бинарных базисов (т е. состоящих из функций от не более, чем двух переменных) эта задача, в зависимости от базиса, либо решается однозначно, либо не решается вовсе.

Теорема 15. Для любого бинарного базиса В функция Р\(р) является либо строго монотонной, либо постоянной на всём интервале О < р < 1.

Если функция Р\{р) является постоянной, то однозначно определить значение р по значению Р\{р) невозможно (более того, нельзя получить никакую информацию о значении р). Согласно теореме 15, кроме базисов с постоянной функцией вероятности, для которых определить значение р по заданному Р\(р) невозможно, все остальные бинарные базисы имеют строго монотонную функцию вероятности, для которой значение р определяв!ся по Р\{р) однозначно.

Для базисов, содержащих функции о г большего числа переменных, также выделяются два случая. В работе показано, что базис, содержащий функции ог не более, чем г переменных, имеет либо постоянную функцию вероятности (и тогда найти значение р по Р\(р) невозможно), либо множество возможных значений р конечно и содержит не более 2г — 2 элементов.

Базисы с постоянной функцией вероятности представляют собой особый случай с точки зрения задачи о восстановлении значения вероятности. Оказывается, что такие базисы образуют целый класс, причём базисы из эюго класса, с одной стороны, весьма разнообразны, а с другой стороны, многие из них обладают специальными свойствами, позволяющими построить для них простое описание.

Исследованию свойств базисов с постоянной функцией вероятности посвящена третья глава диссертации. Доказанные далее свойства базисов с постоянной функцией вероятности будут использованы для построения различных примеров, проливающих свет на задачу о „чёрном ящике".

Отметим, что речь идет о постоянстве на интервале (0,1), так как условия постоянства на отрезке [0,1] сводятся к условиям постоянства на интервале и непрерывности в граничных точках, рассмотренной ранее.

Для функции вероятности произвольного базиса установлен общий критерий посшянотва. Проверка этого критерия проще, чем непосредственное вычисление функции вероятности, так как он не требует нахождения функции т(р). г

Теорема 16. Пусть В — базис с базисным многочленом B(S) = Е \Bk\Sk к=о г к и характеристическим многочленом A(T,F) = Y!YlakiTlFk~l. Пусть k=0г=0 числа со и а являются решением системы (3) для базиса В согласно теореме 7. Для j = 0, .,г — 1 положим = о;1ст(Г^1) — г k г к

Е с^Е(г + l)ajfci+i(r7I,), уз = Y, Y, ik ~ г)акг{г~) ■ Функция вероят-к=0 г=0 к=0 г=0 ности Р\(р) базиса В является постоянной при р G (0,1) тогда и только тогда, когда векторы ¡I = (fio,., fir-i) и í> = (vq, ., fr-i) коллинеарны.

Этот критерий позволяет проверить постоянство функции вероятности произвольного базиса, однако, он не выявляет непосредственно содержательные свойства базисов с постоянной функцией вероя! ности.

Вместе с тем, достаточно широкий подкласс таких базисов можно охарактеризовать в терминах относительно простых свойств базиса. Важную роль в такой классификации базисов с постоянной функцией вероятности играют однородные базисы, т. е. базисы, все функции которых имеют одинаковое количество переменных. В работе показано, что базис являющийся объединением однородных базисов с постоянной функцией вероятности, равной одному и тому же числу С, также имеет функцию вероятности равную С. Более того, при некоторых дополнительных условиях на базис, это утверждение можно обратить: всякий базис с постоянной функцией вероятности представляется (при выполнении условий, описанных ниже) в виде обьединения однородных базисов с той же постоянной функцией вероятности.

Для однородных базисов с постоянной функцией вероятности её значение С непосредственно связано с долями единиц среди значений функций базиса В на слоях булева куба Доля единиц среди значений функций однородного базиса В, состоящего из функций от г переменных, на j-м слое определяется как d3 = • Доказана следующая теорема

Теорема 17. Пусть В — однородный базис с базисным многочленом B(S) и характеристическим многочленом A(T,F), и пусть d3 = т^тЬт. Функция вероятности базиса В постоянна и равна С, 0 < С < I, при всех р € (0,1) тогда, и только тогда, когда разности й3 — С образуют геометрическую прогрессию со знаменателем ^г-.

Теорема 17 означает, что у однородного базиса с постоянной функцией вероятности доля единиц среди значений функций базиса на слоях булева куба „колеблется" около величины С, вообще говоря, с изменяющейся „амплитудой колебаний" (амплитуда с ростом номера слоя у увеличивается при С <1/2, постоянна при С — 1/2 и уменьшается при С > 1/2)

С помощью теоремы 17 показано, что операция объединения однородных базисов сохраняет равенство функции вероятности константе С.

Следствие 10. Любое конечное объединение однородных базисов с постоянными функциями вероятности, равными некоторой постоянной С, одной и той оюе для всех базисов, является базисом с постоянной функцией вероятности, равной С.

Отметим, что в следствии 10 допускается объединение однородных базисов с различным числом переменных. Из следствия 10, в частности, вытекает, что все базисы, содержащие только линейные функции без несущественных переменных, имеют постоянную функцию вероятности, равную 1/2.

Следствие 10 представляет собой лишь достаточное условие постоянства функции вероятности. Показано, что существуют базисы с постоянной функцией вероятности, не являющиеся объединением однородных базисов с постоянной функцией вероятности. Построение таких базисов опирается на следующую теорему:

Теорема 18. Пусть задан однородный базис с постоянной функцией вероятности, равной С при всех р Е (0,1). Тогда С — рациональное число.

В силу теоремы 18, базисы, у которых функция вероятности постоянна и иррациональна, не могут быть получены путём объединения однородных базисов с одинаковой постоянной функцией вероятности. В разделе 3.3.4 строятся примеры таких базисов.

Итак, утверждение следствия 10 можно обратить лишь для базисов с рациональной постоянной функцией вероятности Кроме того, должно выполняться ещё одно условие, формулируемое в терминах алгебраической степени числа а:

Теорема 24. Пусть базис В имеет вид ВдиВя+\1). .1)ВГ-\\ЗВГ, где д > 0, В(1 ф 0 и Вг ф 0 Пусть число а, соответствующее базису В, является алгебраическим, степени г — д + 1. Пусть функция вероятности базиса В постоянна и равна некоторому рациональному числу С. Тогда каждое из множеств Bk для к = q,., г является базисом с постоянной функцией вероятности, равной С.

Среди „вырожденных" базисов, у которых алгебраическая степень числа а не достигает максимально возможного значения, существуют базисы с посюянной функцией вероятности, которые не представляются в виде объединения однородных с той же функцией вероятности (пример 9 в разделе 3.3.3)

Построенные в данной главе примеры базисов позволяют продемонстрировать какая информация о базисе может быть получена в рамках задачи о „чёрном ящике". Прежде всего отметим, что существование базисов с одинаковой функцией вероятности показывает, что однозначно восстановить базис В по данной функции вероятности Pi(p), вообще говоря, невозможно. Кроме того, из построенных примеров следует, что по заданной функции Р\{р) в общем случае нельзя не только определить базис В, но даже установить количество функций в нём и число переменных у функций базиса. Некоторая информация о базисе может быть получена при решении задачи о „чёрном ящике" в некоюром специальном классе базисов, например, в классе базисов с постоянной функцией вероятности, удовлетворяющих условиям теоремы 24 В такой постановке по заданной функции вероятности базиса можно выявить соотношения между коэффициентами характеристического и базисного многочленов базиса В.

Четвёртая глава диссертации посвящена исследованию того, насколько богат класс функций вероятности, т.е. выяснению вопроса о том, какие функции действительного переменного р могут являться функциями вероятности булевых базисов. Установлено, чгю множество функций вероятности является достаточно разнообразным: доказано существование базисов, функции вероятности которых сколь угодно близки к любой наперёд заданной непрерывной функции f(p), отображающей отрезок [0,1] в себя.

Доказательство теоремы о равномерном приближении функциями вероятности конструктивно, оно осуществляется в два этапа. Вначале доказывается теорема о равномерном приближении многочленов функциями вероятности.

Теорема 25. Пусть В — некоторый базис с базисным многочленом B(S) и характеристическим многочленом A(T,F), и базис В^ получается из В добавлением в каждую функцию из В ровно m несущественных переменных, соотношение:

Иш ЛМ(г,) =

Тогда для функции вероятности Pim\p) базиса В^ выполняется т-»оо

В| причём сходимость является равномерной по р на отрезке [0,1].

Для доказательства возможности равномерного приближения произвольной непрерывной функции используется, во-первых, теорема Вейер-штрасса (о равномерном приближении непрерывных функций многочленами) в формулировке С. Н Бернштейна [23], а во-вторых, построение базиса с характеристическим многочленом заданного вида. Отметим, что весьма схожие процедуры построения (для частного случая базиса, состоящего из одной функции), фактически, описаны в [21] и в [10] В итоге доказана

Теорема 27. Пусть ¡(р) — непрерывная функция, отобраоюающая отрезок [0,1] в себя. Тогда для любого г > 0 найдётся базис В£ с функцией вероятности Р\{р) такой, что для всякого р £ [0,1] имеет место неравенство |/(р) — Р\(р)\ < е.

По построению, базис, функция вероятности которого приближает заданную функцию /(р), полученный в теореме 27, вообще говоря, может содержать повторяющиеся функции, а функции этого базиса могут иметь несущественные переменные. Однако, в работе показано, что функции базиса можно переопределить так, чтобы функция вероятности базиса сохранилась, и при этом все функции базиса оказались различными, а все переменные каждой функции — существенными. Таким образом, теорема 27 остаётся верна, если понятие базиса рассматривать в более узком (и более традиционном) смысле.

Теорема 28. Пусть /(р) — непрерывная функция, отобрао1сающая отрезок [0,1] в себя. Тогда для любого е > 0 найдётся базис В£, все функции которого различны и существенно зависят от всех своих переменных, с функцией вероятности Р\ (р) такой, что при всех р € [0,1] выполнено соотношение \¡(р) — Р\{р)\ < £■

Рассматривавшаяся в предыдущих главах функция вероятности базиса Р\{р) являются пределом функций Р\,п{р) при п —» оо. Каждая из функций Р\,п{р) выражает вероятность события в вероятностном пространстве выражений сложности п, заключающегося в обращении значения случайного выражения в 1. В пятой главе диссертации изучаются вероятности некоторых других событий в тех же вероятностных пространствах. А именно, рассматривается вероятность обращения в единицу значения случайного выражения, порождённого некоторой фиксированной бесповторной формулой Ф.

Основным объектом исследования являются условные вероятности Т{Ф = 1|Ф порождается формулой Ф}, именуемые функциями вероятности формул и обозначаемые Р\(р\Ф), гдер - вероятность подстановки константы 1 вместо переменных формулы, а Ф - рассматриваемая порождающая формула. Отметим, что функции вероятности формул связаны с функциями Р\,п(р) соотношением Р1,п(р) = -Р1ЫФ), где есть числ0 бесповторных формул сложности п над рассматриваемым базисом. Таким образом, значение функции Р\,п(р) является средним от значений функций вероятности формул, взятым по всем бесповторным формулам сложности п.

Функция Р\(р\Ф) имеет содержательную интерпретацию, позволяющую связать рассматриваемую задачу с некоторыми задачами, упомянутыми ранее во Введении. Фактически, Р\(р\Ф), выражает „преобразование вероятности" р, осуществляемое бесповторной формулой Ф. Такая трактовка устанавливает непосредственную связь рассматриваемой модели с работой [31], в которой также рассматриваются „преобразователи вероятноеги", связанные с бесповторными формулами. Дальнейшее рассмотрение функций вероятности формул позволяет установить связь ещё с одной упоминавшейся ранее задачей.

Вычисление функции вероятности отдельно взятой бесповторной формулы Ф не представляет особой сложности, однако получить описание множества всевозможных функций вероятности бесповторных формул над заданным базисом В оказывается гораздо более сложной задачей. В исследовании множества функций вероятности формул над заданным базисом В наиболее продуктивным оказалось рассмотрение множеств их значений при фиксированных значениях р. Такие множества в точности совпадают с множествами значений, которые могут быть получены в виде булевых комбинаций независимых бернуллиевских случайных величин, имеющих вероятность обращения в единицу равную р. Таким образом, задача о множестве значений функций вероятности формул при фиксированном р эквивалентна специальному случаю задачи о точном получении значений вероятности с помощью булевых комбинаций независимых бернуллиевских случайных величин, рассматривавшейся Р. М. Колпаковым [9] и другими авторами [14, 11].

Представляется естественным рассматривать \¥в(р) — множество значений функций вероятности формул над базисом В, замкнутое относительно операции предельного перехода, т. е. дополненное всеми своими предельными точками4. В терминах задачи порождения значений вероятности множество \¥в(р) соответствует тем значениям вероятности, которые могут быть получены приближённо с любой наперёд заданной точностью. В такой ин

4Предельной точкой множества называется точка, в любой проколотой окрестности которой содержатся точки множества терпретации совпадение множества Wb(p) с отрезком [0,1] представляет особый интерес, так как соответствует случаю, когда любое значение вероятности может быть приближено сколь угодно точно

Приведём примеры множеств Wb{p) для различных базисов В. Если базис В целиком лежит в классе К (всевозможные конъюнкции переменных и все консханты), классе D (всевозможные дизъюнкции переменных и все константы) или классе L (всевозможные линейные функции), то соответствующее множество Wb(p) имеет не более одной предельной точки, ни при каком р G [0,1] не совпадает с отрезком [0,1] и, более того, при любом р является нигде не плотным множеством.

У базисов же, лежащих вне классов К, D, L, множество Wb{p) может напротив содержать все точки отрезка [0,1] Так, например, и для базиса {&,->}, и для базиса {&,V} при каждом р из интервала (0,1) множество значений функций вероятности формул в точке р является всюду плотным на отрезке [0,1]

Устройство множества Wb{p) для фиксированного базиса В может меняться в зависимости от значения р. Так, например, для базиса В = {/}, выполняется равенство W{/} (-^р^ = г-, а ПРИ Р Î "^т^ и Р £ (ОД) множество Wy}(p) совпадает с отрезком [0,1].

В диссертации установлены необходимые и достаточные условия выполнения равенства Wb(p) = [0,1], сформулированные в виде следующей теоремы.

Теорема 31. Пусть задан базис В и число р G (0,1). Множество Wb{p) совпадает с отрезком [0,1] тогда и только тогда, когда В % L,K,D и

0,1 £WB(p).

С помощью теоремы 31 проверка равенства Ws(p) = [0,1] сводится к проверке принадлежности точек 0 и 1 множеству Wb{p)- Однако, и эта проверка не всегда легко осуществима. Для выявления базисов, у которых 0,1 G Wb{p) при всех р G (0,1), доказано следующее простое достаточное условие

Теорема 32. Пусть базис В таков, что для каждой точки q G (0,1) найдется функция f G В такая, что P\{q\j) < q и фугькция g £ В такая, что P\{q\g) > q■ Тогда при любом р G (0,1) множество Wb{p) codepoicum точки Oui.

Использование теорем 31 и 32 позволяет выявить базисы, у коюрых функции вероятности формул всюду плотны при всех р G (0,1). Базисы, у которых \¥в(р) отлично от отрезка [0,1] могут иметь весьма сложное устройство множества \¥в(р). Примером такого базиса может служить базис, состоящий из медианы т(х,у,г) = ту V хг V уг. Для этого базиса при произвольном р £ (0,1) строится счётное множество неизолированных предельных точек, при эюм между предельными точками может, вообще говоря, не лежать ни одной точки из множества \Ув(р)

Автор выражает глубокую признательность своему научному руководителю О М. Касим-Заде за постановку задачи, постоянное внимание к работе, многочисленные плодотворные обсуждения, и огромную моральную поддержку.

1. Андреев А Е. Об одном методе получения более чем квадратичных эффективных нижних оценок сложности 7г-схем // Вестник Московского университета Серия 1. Математика, Механика. — 1987. — Т. 42 — С. 63-66.

2. Бухараев Р. Г Основы теории вероятностных автоматов — М.: Наука, 1985.

3. Гиндикин С.Г., Мучник A.A. Решение проблемы полноты для систем функций алгебры логики с ненадёжной реализацией // Проблемы кибернетики, вып. 15. — М.: Наука, 1965. — С 65-84.

4. Глебский Ю. В , Коган Д И., Лиогонький М И., Таланов В. А. Объём и доля выполнимости формул узкого исчисления предикатов // Кибернетика 1969 - №2. - С. 17-26.

5. Гросс М , Лантен А Теория формальных грамматик. — М.: Мир, 1971.

6. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики — М . Мир, 1998

7. Евграфов М А. Аналитические функции — М.: Наука, 1968.

8. Князев В. В. Закон нуля и единицы для многосортной логики предикатов первого порядка // Дискретная математика. — 1990. — Т. 2, N° 3. — С 97-102.

9. Колпаков Р. М. О преобразованиях булевых случайных величин // Математические вопросы кибернетики, вып. 9. — М.: Физматлит, 2000. — С. 227-252.

10. Рябинин А. В. Автоматная реализация функций вещественного переменного. Дис. канд. физ.-мат. наук. — М.: 1988

11. Салимов Ф И. Об одной системе образующих для алгебр над случайными величинами // Изв. вузов, сер. «Математика». — 1981. — № 5. — С. 78-82.