Содержание к диссертации
Введение
Глава 1 Нахождение функции вероятности 22
1.1 Основные понятия и определения 22
1.2 Элементарные примеры 25
1.3 Языки и производящие функции 27
1.4 Функция вероятности на интервале (ОД) 35
1.5 Функция вероятности в граничных точках 44
1.6 Связь с другими вероятностными пространствами . 49
1.7 Функции вероятности базисов первого порядка 52
Глава 2 Некоторые свойства функций вероятности 54
2.1 Примеры функций вероятности 54
2 2 Непрерывность функции вероятности на интервале (0,1) . 56
2.3 Непрерывность функции вероятности в граничных точках . 59
2.4 Задача восстановления вероятности 62
Глава 3 Постоянство функции вероятности 66
3.1 Векторное пространство многочленов 66
3 2 Постоянство функции вероятности однородных базисов . 69
3 3 Постоянство функции вероятности неоднородных базисов . 73
Глава 4 Приближение непрерывных функций функциями вероятности 80
4.1 Равномерное приближение многочленов 80
4 2 Равномерное приближение непрерывных функций 84
4 3 Преобразование аппроксимирующих базисов 86
Глава 5 Функции вероятности формул 90
5.1 Постановка задачи 90
5.2 Некоторые примеры 92
5.3 Всюду плотные множества значений 96
Литература
- Языки и производящие функции
- Непрерывность функции вероятности в граничных точках
- Постоянство функции вероятности однородных базисов
- Равномерное приближение непрерывных функций
Введение к работе
Современное понимание термина „вычисление" столь широко, что давать определение этого понятия представляется довольно затруднительным. Неформально можно говорить, что вычислением называется процесс преобразования исходных данных (чаще всего числовых или текстовых), согласно некоторой процедуре (алгоритму) Формализация понятия „вычисление" приводит к математическим моделям, таким как машины Тьюринга, конечные автоматы, логические схемы, и многие другие.
Эти модели, как правило, являются детерминированными, но могут быть модифицированы таким образом, что выполняемые ими действия приобретут случайный характер: элементы случайности могут быть внесены в исходные данные вычисления или же в саму процедуру. Результатом таких модификаций будет некоторая модель случайных вычислений.
Изученные к настоящему времени модели случайных вычислений можно условно разделить на две группы: к первой относятся модели, в которых случайность является „неотъемлемой" частью — в силу природы моделируемого обьекта, или же потому, что сама случайность является обьекюм изучения. Ко вюрой группе относятся модели, в которых случайность является „привнесённой извне". При этом случайность может быть как инструментом построения более удобной вычислительной модели, так и инструментом изучения модели Такая классификация моделей, как уже отмечалось, достаточно условна, так как не всегда легко различить „врождённые" и „привнесенные" элементы случайности в вычислительной модели.
Приведём краткий обзор основных направлений исследований в области случайных вычислений. Хотя, строго говоря, большинство упомянутых в нём задач связаны с темой данной работы лишь косвенным образом, знакомство с ними позволяет лучше понять место и значение данной работы в общей картине исследований в области случайных вычислений. Сначала перечислим некоторые работы, рассматривающие модели, которые можно отнести к первой группе.
Одними из первых вычислительные системы с элементами случайности рассмоірели Дж. фон Нейман (J. von Neumann) [36], а также Е Мур (Е. Moore) и К. Шеннон (С. Shannon) [35]. Эти работы посвящены построению надёжных вычислительных схем из ненадёжных элементов. Случайность в таких сисіемах возникает из-за возможных неисправностей некоторых элементов схемы, т.е. у каждого элемента схемы существует ненуле-
вая вероятность сбоя. В указанных работах предложены методы построения схем высокой надёжности из элементов с ненулевой (но достаточно малой) вероятностью сбоя. Схемы из ненадёжных элементов рассматривались также С Г. Гиндикиным и А. А. Мучником: в [3] они исследовали проблему полноты базисов из ненадёжных элементов. Этой задачей занимались и многие другие авторы (см. обзор в [19]).
Другим примером вычислительных систем с элементами случайное]и могут служить вероятностные автоматы, т.е. авюматы, у которых переходам между состояниями и выходным значениям приписаны некоторые вероятности. Понятие вероятностного автомата было сформулировано в середине 60-х годов прошлого века, и с тех пор была построена достаточно обширная теория вероятностных автоматов, обзор результатов и проблем которой можно найти в книге Р. Г. Бухараева [2]. Одним из интересных результатов теории вероятностных автоматов является утверждение о возможности представления любого вероятностного автомата в виде последовательного соединения „источника вероятности", порождающего случайным и независимым образом символы некоторого алфавита с заданными вероятностями, и детерминированного конечного автомата. Ввиду наличия подобного представления, особый интерес приобретает задача о синтезе такого „источника вероятности".
Впервые задача порождения значений вероятности с помощью булевых преобразователей была, по-видимому, рассмотрена Р. Л. Схиртладзе [14]. В его работе предложен метод получения всех двоично-рациональных значений вероятности пуіем комбинирования бернуллиевских случайных величин, имеющих вероятность обращения в 1 равную 1/2, с помощью контактных схем. В дальнейшем вопросы порождения значений вероятности также исследовались Ф И. Салимовым [11].
Наиболее широкое развитие эта проблематика получила в работах Р. М. Колпакова, который рассматривал различные постановки задачи порождения значений вероятности. В его работах (в частности, [9]) получены критерии, позволяющие по искомому значению и заданным исходным значениям вероятности определить, порождается ли искомое значение булевой комбинацией бернуллиевских случайных величин с вероятностями из заданного множества
В рабоїе А. Бродского (A. Brodsky) и Н. Пипиенджера (N. Pippenger) [25] рассматривается модель случайного порождения булевых функций. Функции порождаются с помощью формул, состоящих из символов некоторой функции-связки и литералов из некоторого конечного множества. Для каждого п > 0 на множестве формул сложности п задаётся распределение вероятности, причём для п = 0 оно произвольное, а для следующих значений п
определяется естественным образом по индукции. Исследуется предельное (при п —> со) распределение вероятности, индуцируемое случайными формулами на множестве булевых функций. Установлено, при каких условиях на функцию-связку и на распределение вероятности при п — 0, функция, реализуемая случайной формулой, почти наверное обладает свойствами линейности, монотонности, самодвойственности.
Все перечисленные выше работы так или иначе рассматривали случайность как неотъемлемую часть модели. Приведём теперь несколько примеров работ, в которых элементы случайности являются скорее привнесёнными (т. е. работ, относящихся ко второй группе, согласно приведённой ранее классификации). Следует отметить, что к этой группе мы относим и те работы, в которых вероятностный аспект комбинаторных методов исследования присутствовал неявно.
Так, например, „закон 0 и 1" для логик первого порядка с конечной моделью изначально сформулирован без привлечения понятия вероятности, однако имеет, по сути, вероятностную природу. Этот закон, впервые установленный, по-видимому, Ю. В. Глебским с соавторами [4], заключается в следующем. Пусть задана некоторая замкнутая формула в логике первого порядка, составленная из предикатов, кванторов и логических связок. Для этой формулы рассматривается истинность на конечной модели при всевозможных интерпретациях сигнатуры. В [4] показано, что такая формула являеіся либо тождественно истинной, либо тождественно ложной на почти всех интерпретациях сигнатуры при стремлении мощности модели к бесконечности. Закон 0 и 1 был независимо доказан Р. Фагиным (R. Fagin) в вероятностной формулировке [28]. Дальнейшие исследования В. А. Таланова [15] и В. В. Князева [8] в этой области были направлены на доказательство закона 0 и 1 для более сложных логических систем.
Комбинаторно-вероятностные методы применялись для исследования сложности булевых функций. В ранних работах, таких как доказательство нижней оценки сложности в классе формул Б. А. Суббоговской [13] и оценка сложности симметрических функций Л. С. Хасиным [16], меюды исследований позиционируются скорее как чисто комбинаторные. Однако, их вероятностная природа раскрывается явно в более поздних работах, использующих сходную аргументацию Применение вероятностных методов позволило существенно продвинуться в решении различных вопросов сложности булевых функций. Так, например, Л. Вэлиант (L. Valiant) [38] получил верхнюю оценку сложности функции голосования, в работах А. Е. Андреева [1] и Й. Хостад (J. Hstad) [33] получены нижние оценки в классе контактных 7Г-схем и формул, а М. Айтаи (М. Ajtai) [22] исследовал с помощью вероятностных методов вопросы сложности в классе схем ограниченной глубины
(обзор дальнейших работ в этом направлении см. в [24]).
Расширением вероятностного подхода к вопросам сложности булевых функций являются работы X. Лефманна (Н. Lefmann) и П. Савицкого (P. Savicky) [34, 37]. В этих работах рассматривается некоторое специальное, но достаточно естественное распределение вероятности на множестве формул над заданным базисом, во многом аналогичное распределению, рассмотренному в рабоїе [25] Такое распределение индуцирует распределение вероятное на множестве булевых функций. Основной результат указанных работ заключается в установлении неравенств, связывающих вероятность булевой функции с её сложностью (рассмотрены случаи базисов {&, ф, 1} и {&, V}). Для базиса {&, V} оценки, связывающие вероятность и сложность функции, были улучшены в работе Б. Шовин (В. Chauvin) с соавторами [26].
Ещё одной областью применения вероятностных методов является исследование задачи выполнимости конъюнктивных нормальных форм (КНФ), т. е. задачи о существовании набора значений переменных, обращающих заданную КНФ в единицу. Интерес к таким задачам обусловлен тем, что задача выполнимости 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 как вероятности обращения в единицу конъюнкции двух независимых бернуллиевских случайных величин, вероятность обращения в единицу которых равна, соответственно, р\ и рг- (При этом для реализации подобной схемы вычисления требуется устройство, порождающее именно независимые случайные величины.) В книге исследуются вопросы оперирования со случайными и псевдослучайными величинами, а также вопросы прямого и обратного преобразования между детерминированной и вероятностной формами представления информации.
Другой пример использования вероятностных методов в качестве инструмента вычислений можно найти в работе А. В. Рябинина [10]. В ней рассматриваются вероятностные вычисления, реализуемые конечным автоматом. Автомат, преобразующий некоторую случайную последовательность, для которой известны вероятности появления символов, задаёт очевидным образом некоторое преобразование вероятности, которое можно рассматривать как функцию действительного переменного, вычисляемую этим автоматом. В работе изучен класс функций действительного переменного, которые реализуются указанным способом, а также рассмотрены некоюрые сложностные аспекты такой реализации.
Направления исследований моделей случайных вычислений далеко не исчерпываюіся перечисленными выше. В частности, существует множество работ, посвященных вероятностным аспектам машин Тьюринга и других видов алгоритмов, однако, эти вычислительные модели досіаточно далеки от рассматриваемых в диссертации, поэтому не упомянуты в приведённом
обзоре.
В данной диссертации исследуются свойства случайных булевых выражений, составленных из символов функций, принадлежащих некоторому заранее фиксированному множеству, и символов констант 0 и 1. Такая модель относится к первой группе — распределение вероятности являеіся здесь неогьемлемой частью и, фактически, одним из объектов исследования. Эта модель, вообще говоря, не является ни обобщением, ни частным случаем какой-либо из упомянутых выше моделей, однако некоторые аналогии, касающиеся элементов модели и рассматриваемых задач, провести все-таки можно. Прежде всего, распределение вероятности на множестве булевых выражений имеет общие черты с распределениями на множестве формул, рассмотренных в работах [25, 34, 37, 26]. „Преобразования вероятности", связанные с булевыми формулами, описанные в работах [31, 21, 10], также рассмотрены в данной диссертации в контексте свойств случайных булевых выражений. Наконец, отметим, что исследование свойсгв случайных булевых выражений направлено на установление общих закономерностей булевых вычислений, по аналогии с закономерностями для арифметических вычислений, приведёнными в книге [17].
Приведём краткий список обозначений и понятий, используемых при дальнейшем изложении. Булевы функции обозначаются следующим образом: к, — конъюнкция, V — дизъюнкция, х или -*х — отрицание, ф — сумма по модулю 2, I — стрелка Пирса, / — шгрих Шеффера, —» — импликация.
Функция f*(x\,..., х/с) = f(x\,. .,Xk) называется двойственной функции /. Функция f(x\,...,xn) называется сохраняющей ноль (сохраняющей единицу), если /(0,..., 0) = 0 (соответственно, /(1, ...,1) = 1). Симметрическими называются функции, значения которых сохраняются при любой перестановке переменных.
Булевым кубом размерности s называется множество всех двоичных наборов длины s: {0,1}S. Множество всех наборов s-мерного булева куба с весом к, т. е. содержащих ровно к единиц, называется к-и слоем булева куба
Для числа сочетаний из п по к элементов используется обозначение ().
Нумерация формул в тексте — отдельная в каждой главе. Нумерация всех утверждений: теорем, лемм, и следствий — сплошная во всем тексте диссертации.
Проиллюстрируем модель случайных булевых выражений простой задачей пусть рассматриваются выражения, составленные из символов конъюнкции, дизьюнкции и констант 0, 1. Будем считать, что выражения с одинаковым количеством функциональных символов равновероятны, а константы 0 и 1 встречаются в выражениях с равной вероятностью. Чему будет равна вероятность выражений со значением 1?
Легко заметить, что двойственные выражения, получающиеся друг из друга заменой каждой из функций и констант на двойственную, имеют равные вероятности. При эюм значения двойственных выражений противоположные. Следоваїельно, для каждого выражения со значением 0 найдётся двойственное ему выражение со значением 1, имеющее ту же вероятность. Таким образом, вероятности выражений со значением 0 и выражений со значением 1 равны между собой, и равны 1/2.
Приведённая выше задача решается элементарными методами, однако, в случае произвольного базиса и неравномерного распределения вероятностей коне і ант решение задачи уже далеко не очевидно
Опишем общую постановку задачи о случайных булевых выражениях. Пусть задан некоторый набор В булевых функций (возможно, с повторениями), далее именуемый базисом. В качестве пространства элементарных исходов будем рассматривать множество всех булевых выражений сложности п над базисом В, т. е. множество всех правильно построенных формул, сосюящих из символов функций базиса В, символов констант 0, 1, и содержащих ровно п функциональных символов1. Примеры булевых выражений: (0&1) V 0, (1 V 0)&(0 V 0), ((1&0)&0)&0.
Каждое булево выражение естественным образом получается из некоторой бесповторной формулы в том же базисе (единственной, с точностью до переименования переменных) в результате подстановки констант 0 и 1 вместо её переменных. Сложность выражения равна числу символов функций в порождающей его бесповторной формуле. Например, булево выражение (1 V0)&(0 V0) сложности 3 получается подстановкой констант в бесповторную формулу (х\ V Х2)&(хз V ж4).
Будем считать, что все бесповторные формулы сложности п равновероятны, т.е., что бесповторная формула, порождающая булево выражение, выбирается случайно и равновероятно из всех бесповторных формул сложности п. Пусть sn — число бесповторных формул сложности п над базисом В (с точностью до переименования переменных). Тогда вероятность каждой формулы равна l/sn. Будем считать, что вместо каждой из переменных формулы подставляется константа 1 с вероятностью р или констан-іа 0 с вероятностью 1—р. Обозначим произведение вероятностей констант, входящих в выражение Ф через 7г(Ф). Вероятность "Р{Ф} выражения Ф определим следующим образом:
Р{ф} = І-7Г(Ф).
Вероятность Т{Ф} является функцией величины р — вероятности подгіа-
1 Другие определения сложности выражений и получающиеся при их использовании вероятностные пространства будут рассмотрены позже
новки константы 1 вместо переменной бесповторной формулы. Определим функции Р\,п(р) и Ро,п(р), равные, соответственно, вероятностям выражений со значениями 1 и 0 в множестве выражений сложности п:
Л,п(р) = >{*}, Л),п(р) = Х>{Ф}.
Ф=1 Ф=0
Очевидно, что Р\)П(р) + Ро,п(р) — 1) поэтому достаточно исследовать поведение лишь одной из этих величин: Р\,п{р). Как будет показано далее, для любою базиса В существует предел lim Р\п{р) во всех точках р интерва-
П—»00 '
ла 0 < р < 1. Этот предел будем обозначать Р\{р) и называть функцией вероятности базиса В. Фактически, величина Р\{р) может рассматриваться как приближённое значение вероятности обращения в 1 значения случайного выражения достаточно большой сложности, причём, как установлено в диссертации, погрешность такого приближения для выражений сложности п равна 0(1/у/п).
Основной целью данной диссертации является исследование задачи о вероятностях значений булевых выражений в описанной выше постановке, изучение общих свойств функции вероятности Р\{р) и её поведения в зависимости от базиса В, а также других возникающих здесь задач.
Функцию вероятности возможно также интерпретировать как результат работы некоторого устройства, аналогичного упомянутым ранее „преобразователям вероятности". Будем считать, что такой преобразователь вероятности, соответствующий базису В, функционирует следующим образом: получая на вход некоторую вероятность р, этот преобразователь вычисляет значение Р\(р) для базиса В. Такое вычисление может производиться, например, путём произведения серии „экспериментов", т.е. построения некоторого количества случайных выражений достаточно большой сложности и вычисления их значений. По сути, такая серия экспериментов является последовательностью испытаний Бернулли, поэтому в силу центральной предельной теоремы статистика этих экспериментов сходится к функции -Pi,n(p), которая, в свою очередь, с ростом п приближается к Р\(р) со скоростью 0(1/у/п). (Описанные представления об экспериментах и статистической интерпретации функции Р\{р) носят содержательный характер и приведены здесь исключительно в иллюстративных целях. Эти вопросы требуют отдельного изучения и в данной работе не рассматриваются.)
В терминах такого преобразователя вероятности сформулируем несколько содержательных задач. Прежде всего, это задача анализа преобразователя, т е нахождения функции Р\(р) по заданному базису В. Вторая задача заключается в восстановлении для заданного фиксированного базиса В вероятности р по заданному значению Р\{р), или, в более общей постановке, в
получении возможно большей информации о значении р по заданному значению Р\{р). Третья задача, именуемая задачей о „чёрном ящике", заключается в получении информации о заранее неизвестном базисе В (содержимом „чёрного ящика") по заданной функции вероятности Р\(р). Эти три задачи и некоторые их модификации рассматриваются в данной диссертации
В первой главе диссертации решается задача анализа для булевых выражений над фиксированным базисом, доказывается ряд теорем, позволяющих по заданному базису В получить его функцию вероятности в явном виде. Общий ход рассуждений изложен ниже.
Пусть базис В фиксирован. Функцию P\,n{p) при каждом значении п представим в виде отношения tn/sn. Здесь tn есть числовая функция от р, равная сумме величин 7г(Ф) по всем выражениям Ф сложности п со значением 1, a sn — упомянутое выше число бесповторных формул сложности п над базисом В От последовательностей tn, sn и fri = sn — tn перейдём к их производящим функциям T(z), S(z) и F(z) [6]
Множество булевых выражений над базисом В можно рассматривать как формальный язык над некоторым алфавитом. Применение метода М. П Шютценберже (М. P. Schutzenberger) [27] позволяет получить систему уравнений, связывающую производящие функции T(z) и F(z): она является гомоморфным образом системы уравнений в языках, связывающей язык выражений со значением 1 с языком выражений со значением 0. Эти языки — контекстно-свободные, поэтому система уравнений, связывающая T{z) и F(z), является алгебраической.
Для записи этой системы уравнений будем использовать два многочлена, строящихся по базису В: базисный многочлен B(S) = Y^k \Bk\Sk, гДе Вк есть множество функций от к переменных в базисе В, и характеристический многочлен2 А(Т,F) = YkY^takiPl^k~\ гДе аь есть число единиц среди значений функций из Вк на наборах значений переменных с г единицами и к — г нулями. С помощью многочленов B(S) и Л(Т, F) система уравнений, о которой шла речь выше, записывается в виде:
T(z)=p + zA(T(z),F(z)),
F(z) = 1-р + zB{T(z) + F{z)) - zA(T(z),F(z)). [i)
Для нахождения асимптотики коэффициентов производящих функций T(z) и F(z) используется теорема Дрмота-Лэлли-Вудса [29] (теорема3 2). Она позволяет усыновить асимптотическое поведение коэффициентов производящих функций T(z) и F{z) по системе уравнений (1) без непосредственного
Характеристический многочлен в виде А(р, 1 — р) для базиса из одной функции исполыуется в раГютах [25, 35]
33десь, и далее во Введении, теоремы приводятся с номерами из основного текста
нахождения решений уравнений.
Производящие функции T(z) и F(z) рассматриваются как функции комплексного переменного. Согласно теореме 2, при выполнении некоюрых дополнительных условий (см. раздел 1.3 3) ряды T(z) и F{z) сходятся в окрестности нуля и имеют один и тот же радиус сходимости и). При эгом и являеіся ближайшей к нулю особой точкой у каждой из зіих функций. Асимптотическое поведение коэффициентов рядов T(z) и F(z) определяется по коэффициентам соответствующих рядов Пюизо [7] в окрестности точки и>.
С помощью теоремы 2 доказывается следующее утверждение
Теорема 7. Пусть В — некоторый базис с базисным многочленом B(S) и характеристическим многочленом A(T,F). Тогда для любого фиксированного р, 0 < р < 1, существует предел Р\{р) = lim Р\,п{р), и имеет место
П—+00
равенство:
д (Р) = Л'р(т,а-г)
1 {Р) о;"1 - А'т(т,а-т) + А'р(т,а-тУ [ ]
где и) и о — однозначно определённые положительные действительные числа, образующие решение системы уравнений
(а = 1 + иВ(а),
\ 1 = шВ'(а), [6)
с минимальным значением \ш\ (среди всех решений (3)); А'Т и A'F — частные производные многочлена A(T,F), г = т(р) — однозначно определённая алгебраическая функция, удовлетворяющая уравнению:
т(р) =р + и;А(т{р),а - т(р)),
и условиям 0 < т(р) < а.
Более детальный анализ поведения функций T(z) и F(z) в окрестности их общей особой точки ш позволяет не только получить явное выражение для значения предела величин Р\)П(р), но и оценить скорость сходимости P\,n(p) к РМ при п -> оо: Pl}Tl{p) = Piip) + 0(1/д/п).
Условия теоремы 7 требуют принадлежности р интервалу 0 < р < 1 В случае р = 0 или р = 1 система уравнений (1) может не удовлетворять условиям теоремы 2, вследствие чего утверждение, аналогичное теореме 7, в соответствующей точке не вьшолняеіся. Анализ поведения предела lim Р\п{р) в точках р = 0 и р — 1 для всевозможных базисов позволил
П-+ОС '
доказать следующую теорему:
Теорема 9. Пусть В — некоторый базис. Значение Рі(0) (соответственно, Pi (1)) определено тогда и только тогда, когда в базисе В найдётся функция, отличная от линейной, существенно зависящей от всех переменных, не сохраняющей ноль (не сохраняющей единицу) функции. Если в В найдётся функция, не сохраняющая ноль (не сохраняющая единицу), то значение Pi(0) (Pi (1)) вычисляется по формуле (2), в противном случае Рі(0) = 0(Рі(1) = 1)
Если сложность выражения определяется каким-то образом, отличным от указанного ранее, то вероятностное пространство выражений сложности п, естественно, будет другим Функцию Р\,п(р) можно определить и в этом случае, но предел Р\(р) = lim Pi п(р) может и не существовать. В разделе
П—»00 '
1 6 рассмотрены случаи определения сложности как количества символов констант в выражении, и как суммарного количества символов коне і ант и функций. Показано, что если функция вероятности определена, то её явное выражение совпадает с указанным в теореме 7 с точностью до значений ш, а и т(р). Фактически, описанное изменение меры сложности булевых выражений оказывается равносильно замене переменной р функции вероятности
А(р).
Во второй главе диссертации приводятся примеры функций вероятности различных базисов и исследуются простейшие свойства функций вероятное! и Функции вероятности в рассмотренных примерах оказываются непрерывными и дифференцируемыми при 0 < р < 1, а в точках р = 0 и р—1 функция вероятности, вообще говоря, может иметь разрывы.
Непрерывность и дифференцируемость функции вероятности на интервале 0 < р < 1 доказывается в работе в общем случае.
Из теоремы 7 следует, что функция вероятности Р\(р) при 0 < р < 1 предеіавляется в виде композиции некоторой дробно-рациональной функции Р(х) (зависящей от характеристического многочлена) и алгебраической функции т(р), т.е. Р\(р) = Р(т(р)). Показано, что функция т(р) является бесконечно непрерывно-дифференцируемой, монотонно возрастающей функцией при 0 < р < 1. Кроме того, функция вероятности представляє!ся в виде Р\(р) = uA'f(t(p), а — т(р))т'(р), откуда вытекает:
Теорема 13. Для всякого базиса В функция Р\(р) является бесконечно непрерывно-дифференцируемой на интервале О < р < 1.
Случаи, когда функция вероятности не определена в точке р = 0 или р = 1 (устранимые разрывы) рассмотрены выше в теореме 9. Условия наличия у функции вероятности разрывов первого рода (т.е. Рі(0) ф lim Pi (р) или
р-+0
Pi(l) ф lim Pi (р)) сформулированы в виде следующей теоремы
Теорема 14. Пусть В — базис с базисным многочленом B(S) и характеристическим многочленом A(T,F). Функция Р\{р) имеет разрыв в точке р = 0 (соответственно, р = 1) тогда и только тогда, когда выполнены равенства а&о = 0, ajti = k\Bk\ (соответственно, akk-i = О, а^ = \Bk\) для всех к — О,... ,г.
Полученные условия непрерывности и дифференцируемоеги функции вероятности позволили проанализировать задачу о восстановлении значения вероятности р по заданному значению Р\(р) для фиксированного базиса В. В частности, оказывается, что для бинарных базисов (т е. состоящих из функций от не более, чем двух переменных) эта задача, в зависимое!и от базиса, либо решается однозначно, либо не решается вовсе.
Теорема 15. Для любого бинарного базиса В функция Р\(р) является либо строго монотонной, либо постоянной на всём интервале О < р < 1.
Если функция Р\(р) является постоянной, то однозначно определить значение р по значению Р\(р) невозможно (более того, нельзя получить никакую информацию о значении р). Согласно теореме 15, кроме базисов с постоянной функцией вероятности, для которых определить значение р но заданному Р\(р) невозможно, все остальные бинарные базисы имеют строго монотонную функцию вероятности, для которой значение р определяется по Р\(р) однозначно.
Для базисов, содержащих функции о г большего числа переменных, также выделяются два случая. В работе показано, что базис, содержащий функции ог не более, чем г переменных, имеет либо постоянную функцию вероятности (и тогда найти значение р по Р\(р) невозможно), либо множество возможных значений р конечно и содержит не более 2г — 2 элементов.
Базисы с постоянной функцией вероятности представляют собой особый случай с точки зрения задачи о восстановлении значения вероятности. Оказывается, что такие базисы образуют целый класс, причём базисы из эюго класса, с одной стороны, весьма разнообразны, а с другой стороны, многие из них обладают специальными свойствами, позволяющими построить для них простое описание.
Исследованию свойств базисов с постоянной функцией вероятности посвящена третья глава диссертации. Доказанные далее свойства базисов с постоянной функцией вероятности будут использованы для построения различных примеров, проливающих свет на задачу о „чёрном ящике".
Отметим, что речь идет о постоянстве на интервале (0,1), так как условия постоянства на отрезке [0,1] сводятся к условиям постоянства на интервале и непрерывности в граничных точках, рассмотренной ранее.
Для функции вероятности произвольного базиса установлен общий критерий посюянства. Проверка этого критерия проще, чем непосредственное вычисление функции вероятности, так как он не требует нахождения функции т(р).
Теорема 16. Пусть В — базис с базисным многочленом B(S) = ^ 1-^
г к
и характеристическим многочленом A(T,F) = ^ YlakiTlFk~l. Пусть
к=0г=0
числа со и а являются решением системы (3) для базиса В согласно теореме 7. Для j = 0, ...,г — 1 положим \х2 = о;_1сг(г" ) —
г k г к
Е^Е(г + іКн-і(г~ ), у2 = Y, к Y, ік ~ г)аь{Г~) Функция вероят-
к=0 г=0 к=0 1=0
пости Р\(р) базиса В является постоянной при р Є (0,1) тогда и только тогда, когда векторы jl = (fia,..., fir-i) и и = (z/q, ..., ^V-i) коллипеарны.
Этот критерий позволяет проверить постоянство функции вероятности произвольного базиса, однако, он не выявляет непосредственно содержательные свойства базисов с постоянной функцией верояїности.
Вместе с тем, достаточно широкий подкласс таких базисов можно охарактеризовать в терминах относительно простых свойств базиса. Важную роль в такой классификации базисов с постоянной функцией вероятности играют однородные базисы, т. е. базисы, все функции которых имеют одинаковое количество переменных. В работе показано, что базис являющийся объединением однородных базисов с посюянной функцией вероятности, равной одному и тому же числу С, также имеет функцию вероятности равную С. Более того, при некоторых дополнительных условиях на базис, это утверждение можно обратить: всякий базис с постоянной функцией вероятности представляется (при выполнении условий, описанных ниже) в виде обьединения однородных базисов с той же постоянной функцией вероятности.
Для однородных базисов с постоянной функцией вероятности её значение С непосредственно связано с долями единиц среди значений функций базиса В на слоях булева куба Доля единиц среди значений функций однородного базиса В, состоящего из функций от г переменных, на j-u слое определяется как d3 — aj",rV Доказана следующая теорема
Теорема 17. Пусть В — однородный базис с базисным многочленом B(S) и характеристическим многочленом A(T,F), и пусть &2 = т^тттт- Функ-
ция вероятности базиса В постоянна и равна С, О < С < 1, при всех
р Є (0,1) тогда, и только тогда, когда разности d3 — C образуют геометрическую прогрессию со знаменателем ^=^.
Теорема 17 означает, что у однородного базиса с постоянной функцией вероятности доля единиц среди значений функций базиса на слоях булева куба „колеблется" около величины С, вообще говоря, с изменяющейся „амплитудой колебаний" (амплитуда с ростом номера слоя j увеличивается при С < 1/2, постоянна при С = 1/2 и уменьшается при С > 1/2)
С помощью теоремы 17 показано, что операция объединения однородных базисов сохраняет равенство функции вероятности константе С.
Следствие 10. Любое конечное объединение однородных базисов с постоянными функциями вероятности, равными некоторой постоянной С, одной и той оісе для всех базисов, является базисом с постоянной функцией вероятности, равной С.
Отметим, что в следствии 10 допускается объединение однородных базисов с различным числом переменных. Из следствия 10, в частности, вытекает, что все базисы, содержащие только линейные функции без несущественных переменных, имеют постоянную функцию вероятности, равную 1/2.
Следствие 10 представляет собой лишь достаточное условие постоянства функции вероятности. Показано, что существуют базисы с постоянной функцией вероятности, не являющиеся объединением однородных базисов с посюянной функцией вероятности. Построение таких базисов опирается на следующую теорему:
Теорема 18. Пусть задан однородный базис с постоянной функцией вероятности, равной С при всех р Є (0,1). Тогда С — рациональное число.
В силу теоремы 18, базисы, у которых функция вероятности посюянна и иррациональна, не могут быть получены путём объединения однородных базисов с одинаковой постоянной функцией вероятности. В разделе 3.3.4 строятся примеры таких базисов.
Иъак, утверждение следствия 10 можно обратить лишь для базисов с рациональной постоянной функцией вероятности Кроме того, должно выполняться ещё одно условие, формулируемое в терминах алгебраической степени числа а:
Теорема 24. Пусть базис В имеет вид Bq\jBq+\U.. .UBr-iUBr, где q > 0, Bq ф 0 и Вг ф 0 Пусть число а, соответствующее базису В, является алгебраическим, степени r — q + l. Пусть функция вероятности базиса В
постоянна и равна некоторому рациональному числу С. Тогда каждое из множеств Bk для к — q,..., г является базисом с постоянной функцией вероятности, равной С.
Среди „вырожденных" базисов, у которых алгебраическая степень числа и не достигает максимально возможного значения, существуют базисы с посюянной функцией вероятности, которые не представляются в виде объединения однородных с той же функцией вероятности (пример 9 в разделе 3.3.3)
Построенные в данной главе примеры базисов позволяют продемонстрировать какая информация о базисе может быть получена в рамках задачи о „чёрном ящике". Прежде всего отметим, что существование базисов с одинаковой функцией вероятности показывает, что однозначно восстановить базис В поданной функции вероятности Рг(р), вообще говоря, невозможно. Кроме того, из построенных примеров следует, что по заданной функции Р\{р) в общем случае нельзя не только определить базис В, но даже установить количество функций в нём и число переменных у функций базиса. Некоторая информация о базисе может быть получена при решении задачи о „чёрном ящике" в некоюром специальном классе базисов, например, в классе базисов с постоянной функцией вероятности, удовлетворяющих условиям теоремы 24 В такой постановке по заданной функции вероятности базиса можно выявить соотношения между коэффициентами характеристического и базисного многочленов базиса В.
Четвёртая глава диссертации посвящена исследованию того, насколько богат класс функций вероятности, т.е. выяснению вопроса о том, какие функции действительного переменного р могут являться функциями вероятности булевых базисов. Установлено, чгю множество функций верояїно-сти является достаточно разнообразным: доказано существование базисов, функции вероятности которых сколь угодно близки к любой наперёд заданной непрерывной функции f(p), отображающей отрезок [0,1] в себя.
Доказательство теоремы о равномерном приближении функциями вероятности конструктивно, оно осуществляется в два этапа. Вначале доказывается теорема о равномерном приближении многочленов функциями вероятности.
Теорема 25. Пусть В — некоторый базис с базисным многочленом B(S)
и характеристическим многочленом A(T,F), и базис В^т> получается из
В добавлением в каждую функцию из В ровно т несущественных пере
менных. Тогда для функции вероятности Р\т\р) баз иса выполняется
соотношение:
т-'оо \п\
причём сходимость является равномерной по р на отрезке [О,1].
Для доказательства возможности равномерного приближения произвольной непрерывной функции используеіся, во-первых, теорема Вейер-штрасса (о равномерном приближении непрерывных функций многочленами) в формулировке С. Н Бернштейна [23], а во-вторых, построение базиса с характеристическим многочленом заданного вида. Отметим, что весьма схожие процедуры построения (для частного случая базиса, состоящего из одной функции), фактически, описаны в [21] и в [10] В и і ore доказана
Теорема 27. Пусть f(p) — непрерывная функция, отобраоїсающая отрезок [0,1] в себя. Тогда для любого є > 0 найдётся базис В с функцией вероятности Р\{р) такой, что для всякого р Є [0,1] имеет место неравенство \f{p) — Р\(р)\ < є.
По построению, базис, функция вероятности которого приближает заданную функцию f(p), полученный в теореме 27, вообще говоря, может содержать повторяющиеся функции, а функции этого базиса могут иметь несущественные переменные. Однако, в работе показано, что функции базиса можно переопределить так, чтобы функция вероятности базиса сохранилась, и при этом все функции базиса оказались различными, а все переменные каждой функции — существенными. Таким образом, теорема 27 остаётся верна, если понятие базиса рассматривать в более узком (и более традиционном) смысле.
Теорема 28. Пусть f(p) — непрерывная функция, отобраоїсающая отрезок [0,1] в себя. Тогда для любого є > 0 найдётся базис В, все функции которого различны и существенно зависят от всех своих переменных, с функцией вероятности Р\ (р) такой, что при всех р Є [0,1] выполнено соотношение \f(p) — Рі(р)\ < є.
Рассматривавшаяся в предыдущих главах функция вероятности базиса Р\{р) являются пределом функций Р\,п{р) при п —» со. Каждая из функций Р\,п{р) выражает вероятность события в вероятностном пространстве выражений сложности п, заключающегося в обращении значения случайного выражения в 1. В пятой главе диссертации изучаю і ся вероятности некоюрых других событий в тех же вероятностных пространствах. А именно, рассматривается вероятность обращения в единицу значения случайного выражения, порождённого некоторой фиксированной бесповторной формулой Ф.
Основным объектом исследования являются условные вероятности Т{Ф = 1|Ф порождается формулой Ф}, именуемые функциями вероятности
формул и обозначаемые Р\(р\Ф), гдер - вероятность подстановки консіан-ты 1 вместо переменных формулы, а Ф — рассматриваемая порождающая формула. Отметим, что функции вероятности формул связаны с функциями Р\,п(р) соотношением Рі,п(р) = ^|ф|=п^і(р|Ф)» гДе sn есть число бесповторных формул сложности п над рассматриваемым базисом. Таким образом, значение функции Р\,п(р) является средним от значений функций вероятности формул, взятым по всем бесповторным формулам сложности п.
Функция Р\(р\Ф) имеет содержательную интерпретацию, позволяющую связать рассматриваемую задачу с некоторыми задачами, упомянутыми ранее во Введении. Фактически, Р\(р\Ф), выражает „преобразование вероятности" р, осуществляемое бесповторной формулой Ф. Такая трактовка устанавливает непосредственную связь рассматриваемой модели с работой [31], в которой также рассматриваются „преобразователи вероятности", связанные с бесповторными формулами. Дальнейшее рассмотрение функций вероятности формул позволяет установить связь ещё с одной упоминавшейся ранее задачей.
Вычисление функции вероятности отдельно взятой беспов'їорной формулы Ф не представляет особой сложности, однако получить описание множества всевозможных функций вероятности бесповторных формул над заданным базисом В оказывается гораздо более сложной задачей. В исследовании множества функций вероятности формул над заданным базисом В наиболее продуктивным оказалось рассмотрение множеств их значений при фиксированных значениях р. Такие множества в точности совпадают с множествами значений, которые могут быть получены в виде булевых комбинаций независимых бернуллиевских случайных величин, имеющих вероятность обращения в единицу равную р. Таким образом, задача о множестве значений функций вероятности формул при фиксированном р эквивалентна специальному случаю задачи о точном получении значений вероятности с помощью булевых комбинаций независимых бернуллиевских случайных величин, рассматривавшейся Р. М. Колпаковым [9] и другими авторами [14, 11].
Представляется естественным рассматривать Wb(p) — множество значений функций вероятности формул над базисом В, замкнутое относительно операции предельного перехода, т. е. дополненное всеми своими предельными точками4. В терминах задачи порождения значений вероятности множество Wb(p) соответствует тем значениям вероятности, которые могут быть получены приближённо с любой наперёд заданной точностью. В такой ин-
4Предельной точкой множества называется точка, в любой проколотой окрестности которой содержатся точки множества
терпретации совпадение множества Wb(p) с отрезком [0,1] представляет особый интерес, так как соответствует случаю, когда любое значение вероятности может быть приближено сколь угодно точно
Приведём примеры множеств Wb{p) для различных базисов В. Если базис В целиком лежит в классе К (всевозможные конъюнкции переменных и все консіантьі), классе D (всевозможные дизъюнкции переменных и все константы) или классе L (всевозможные линейные функции), то соответствующее множество Wb(p) имеет не более одной предельной точки, ни при каком р Є [0,1] не совпадает с отрезком [0,1] и, более того, при любом р является нигде не плотным множеством.
У базисов же, лежащих вне классов К, D, L, множесгво Wb{p) может напротив содержать все точки отрезка [0,1] Так, например, и для базиса {&,->}, и для базиса {&,V} при каждом р из интервала (0,1) множество значений функций вероятности формул в точке р является всюду плотным на отрезке [0,1]
Устройство множества Wb{p) для фиксированного базиса В может меняться в зависимости от значения р. Так, например, для базиса В — {/},
вьіполняеіся равенство Wy} (2^) = 2^' а ПРИ Р ^ 2^ и Р ^ (^) множество Wy}(p) совпадает с отрезком [0,1].
В диссертации установлены необходимые и достаточные условия выполнения равенства \Ув(р) = [0,1], сформулированные в виде следующей теоремы.
Теорема 31. Пусть задан базис В и число р Є (0,1). Мноэюество Wb{p) совпадает с отрезком [0,1] тогда и только тогда, когда В % L,K,D и 0,1ИЪ(р).
С помощью теоремы 31 проверка равенства Ws(p) = [0,1] сводится к проверке принадлежности точек 0 и 1 множеству Wb{p)- Однако, и эта проверка не всегда легко осуществима. Для выявления базисов, у которых 0,1 Є Wb{p) при всех р Є (0,1), доказано следующее простое достаточное условие
Теорема 32. Пусть базис В таков, что для каоюдой точки q Є (0,1) найдётся функция f Є В такая, что P\{q\j) < q и функция g Є В такая, что Р\(q\g) > q. Тогда при любом р Є (0,1) множество Wb{p) содероісит точки Owl.
Использование іеорем 31 и 32 позволяет выявись базисы, у коюрых функции вероятности формул всюду плотны при всех р Є (0,1). Базисы,
у которых Wb(p) отлично от отрезка [0,1] могут иметь весьма сложное устройство множества Wb(p). Примером такого базиса может служить базис, состоящий из медианы m(x,y,z) = ту V xz V yz. Для этого базиса при произвольном р б (0,1) строится счётное множество неизолированных предельных іочек, при эюм между предельными точками может, вообще говоря, не лежать ни одной точки из множества \Ув(р)-
Автор выражает глубокую признательность своему научному руководителю О М. Касим-Заде за постановку задачи, постоянное внимание к работе, многочисленные плодотворные обсуждения, и огромную моральную поддержку.
Языки и производящие функции
В базисе {&,V} не все формулы заданной сложности являю і ся эквивалентными. Для нахождения величины P\,n{p) этого базиса, рассмотрим сначала величину sn. Легко заметить, чю S\ = 2. Полагая so = 1, из непосредственного рас-смо грения формул сложности п получаем следующее рекуррентное соотношение для sn: n-l 5n = 2 sjfcSn_i_jfc. (1.4) к=0
Для получения величины Pi,n(p) достаточно самого соотношения (1 4), хотя и нетрудно получить, что sn = рї( ") Фактически, величина sn есть число правильных скобочных последовательностей длины п, т е. х( ) (см [6]), умноженное на 2", поскольку каждой бесповторной формуле соответствует правильная скобочная последовательность, у когорой каждой паре скобок приписан один из двух функциональных символов.
Утверждение 1. В базисе {&, V} при любом п имеет место равенство Р\,П(Р)=Р Доказательство. Докажем утверждение индукцией по п. Рассмотрим случай выражений сложности п = 1. Выпишем все выражения сложности 1 &(0,0), &(0,1), &(1,0), &(1,1), V(0,0), V(0,1), V(1,0), V(l,l) Сумма 7г(Ф) по всем выражениям сложности 1 со значением 1 равна !2Ф=ІП(Ф) = Р2 + (2р(1 — р) + Р2) = %Р- Учитывая, чю s\ = 2, имеем Р\,\{р) — Р- Базис индукции доказан.
Докажем шаг индукции. Пусть утверждение верно для всех п т. Рассмотрим п = т Имеем Pl,m(p) = Р(&(ФЬ Ф2) = Ч + Р (ФЬ Ф2) = 1), (1 5) Фі,Ф2 $1,$2 где суммирование в каждом случае ведеіся по всевозможным Фі и Фг таким, что их сложность в сумме равна т — 1. Рассмоірим отдельно первую сумму: m-l Е Р(&(Ф., Фа) = 1) = Е "- 7 = Е Е Е 1г(Ф,)т(Ф,), Фі,Фг Фі=1,Ф2=1 к=0Фі=\Ф2=1 где в последнем случае суммирование ведёгся но выражениям Фі сложности к и выражениям &2 сложности т—1 — к. Преобразуя эту сумму, получаем: Sm к \ф1=1 / Wl / 5т к Из предположения индукции следует, что Р\,к{р) — Pi,m-i-k{p) = р. С учётом соотношения (1.4), рассматриваемая сумма равна: і її Е1\ _p_sJn_r_ 2_ skSm-l-k- о 9 m . m Аналогичными рассуждениями получаем, что вторая сумма в соотношении (1.5) равна (2р(1-р)+р2)/2 Следовательно, Р\,т = \р2+\{2р{1-р)+р2) = р. Предложение доказано.
В рассмотренным примерах явные выражения величины Р\,п{р) для всех п были получены путём непосредственного вычисления. Однако, подобные вычисления практически осуществимы далеко не всегда, поэтому в общем случае рассматривается функция вероятности базиса, т. е. предел lim Р\п{р)- Как будет показано далее, это г предел может быть вычислен без прямого нахождения самих функций Р\,п{р) Языки и производящие функции Положим tn= 7г(Ф). Тогда в силу соотношения (1.2) имеет место Ф=П,Ф=1 равенство Pi,n(p) = tn/sn. Кроме того, обозначим через fn величину 7г(Ф). Тогда величина Ф=п,Ф=0 Pnflip) представляется в виде Рп,о(р) = fn/sn-Введём формальные степенные ряды: T(z) = J tnzn; F(z) = /„ "; S(z) = Y/snzn. п 0 n 0 n Эти сіепенньїе ряды являются производящими функциями последовательностей tn, fn и sn, а именно, воспользовавшись стандартным обозначением (см [6]), можно записать, что [2;г ]Т(г) = tn (аналогично для F(z) и S(z)), т. е. п-й коэффициент степенного ряда совпадает с п-и членом соответствующей последовательности. Подробнее о формальных степенных рядах и производящих функциях см. [б].
Отметим одно полезное свойство производящих функций T(z) и F(z). Пусть базис В является двойственным базису В, т. е. получается из В заменой каждой функции на двойственную Непосредственно из рассмотрения производящих функций для базисов В и В вытекают следующие соотношения для функций вероятности двойственных базисов.
Теорема 1. Пусть В и В — двойственные базисы, а Р\{р) и Р\{р) — соответствующие им функции вероятности. Тогда для любого фиксированного р, 0 р 1, значения Р\(р) и Р{{р) одновременно определены или не определены, и в случае если значения определены, имеет место равенство Pi{p) = 1 - Р{{\ - р).
Для самодвойственных базисов естественным образом получаем
Следствие 1. Пусть В — самодвойственный базис (т е. В = В ) и Р\{р) — соответствующая ему функция вероятности. Тогда для 0 р 1 значения Р\{р) и Р\{1 — р) одновременно определены или не определены, и в случае если оба значения определены, имеет место равенство Р\{р) = l-Pi(l-p).
Чтобы избежать возможных неясностей, уточним, что самодвойственный базис не обязательно состоит из самодвойственных функций. Например, базис {&;, V} — самодвойственный
Непрерывность функции вероятности в граничных точках
Прежде всего отметим, что в граничных точках отрезка [0,1] для нахождения значений Р\{р) нельзя воспользоваться непосредственно теоремой 3, так как в граничных точках может нарушаться условие апериодичносіи системы уравнений (1.12), связывающей производящие функции T(z) и F(z). Для точки р = 0 апериодичность системы зависит от наличия в базисе функций, сохраняющих ноль, а для -ючки р = 1, соответственно, от наличия в базисе функций, сохраняющих единицу.
Рассмотрим подробно возможные варианты поведения функции Р\(р) в точке р = 0. Утверждения, касающиеся поведения функции Р\(р) в точке р = 1 будут получены из соображений двойственности. Для произвольного базиса В выполнено ровно одно из следующих утверждений: 1. Все функции из базиса В сохраняют ноль. 2. В базисе В найдется как функция сохраняющая ноль, так и функция, не сохраняющая ноль. 3. Все функции из базиса В не сохраняют ноль. Рассмотрим каждый из этих случаев отдельно. Случай базиса, состоящего только из функций, сохраняющих ноль, полностью характеризуется следующей очевидной леммой Лемма 7. Пусть В — базис, в котором все функции сохраняют ноль. Тогда значение Р\{0) определено и Р\{0) = 0. Перейдём к рассмотрению второго случая. Лемма 8. Пусть базис В содержит хотя бы одну функцию, не сохраняющую ноль, и хотя бы одну функцию, сохраняющую ноль. Пусть р = 0. Тогда при п 0 выполняется tn ф 0 и fn Ф 0. Доказательство. Докажем утверждение индукцией по п. При п = 1 неравенства t\ 0 и /і 0 вытекают непосредственно из условия леммы. Базис индукции установлен.
Опишем шаг индукции. Пусть утверждение выполнено для п — к — 1. Покажем, что оно выполнено и для п = к. Согласно индуктивному предположению, fk-i ф 0, поэтому найдется выражение Ф сложности к — 1 со значением 0. По условию леммы, в базисе В найдётся функция до, сохраняющую ноль. Рассмотрим выражение до(Ф, 0,..., 0): оно имеет сложность к и значение 0. Следовательно, fk 0
В базисе В также найдется функция д\, не сохраняющая ноль. Тогда выражение і(Ф,0,..., 0) имеет сложность к и значение 1. Следовательно, tk 0 Шаг индукции выполнен. Лемма доказана.
Итак, в случае, когда в базисе присутствуют как функции, сохраняющие ноль, так и функции, не сохраняющие ноль, при р = 0 система уравнений для Т и F обладает свойством апериодичности. В базисе есть как функции сохраняющие, так и функции, не сохраняющие ноль, поэтому базис В не может состоять только из конъюнкций и тождественных нулей. Если базис состоит не только из дизъюнкций и тождественно единичных функций, то система уравнений для Т и F является несводимой. Тогда базис В в точке р = 0 удовлетворяет условиям теоремы 3 и Рі(0) вычисляется по формуле (1.20). В случае базиса, состоящего только из дизъюнкций и тождественно единичных функций формула (1.20) проверяется непосредственно
Перейдём к рассмотрению третьего случая: пусть все функции из базиса В на нулевом наборе равны единице. Далее будем говорить об апериодичности последовательностей {tn} и {/п} подразумевая апериодичность их производящих функций Т и F Докажем следующие леммы, касающиеся свойств последовательностей {tn} и {fn} Прежде всего отметим, что если в последовательности есть два последовательных ненулевых члена и ещё хотя бы один ненулевой член, то последовательность является апериодичной в силу леммы 3.
Лемма 9. Пусть все функции из В не сохраняют ноль и в последовательности {fn} есть по крайней мере два последовательных отличных от нуля члена: fk,fk+i- Тогда в последовательности {tn} такоісе найдутся два последовательных отличных от пуля члена.
Доказательство. Имеем /& ф 0, fk+i ф О, поэтому найдутся выражения Ф& и Фк+і со значением 0, сложности к и к + 1, соответственно. Пусть g есть некоторая функция базиса В. На нулевом наборе функция g равна 1. Выражения #(Фд,, 0,..., 0) и р(Ф +ь 0 . , 0) имеют значение 1 и сложности к + 1 и к + 2, соответственно. Лемма доказана
Лемма 10. Пусть все функции из В не сохраняют ноль и хотя бы одна из них отлична от тождественно единичной функции. Пусть в последовательности {tn} есть по крайней мере два последовательных отличных от нуля члена: tk,tk+i. Тогда в последовательности {fn} такоісе найдутся два последовательных отличных от нуля члена.
Доказательство. Имеем & ф 0, tk+i ф 0, поэтому найдутся выражения Ф и Ф +1 со значением 1, сложности к и /: + 1, соответственно. Пусть g — функция базиса В, отличная от тождественно единичной функции. Тогда найдется набор значений ее переменных а — (а\, ct2, . .) такой что g(a) = 0. При эюм3 а ф 0, так как все функции из В не сохраняют ноль Следовательно, среди компонент набора а найдётся аг = 1.
Заметим, что в данном базисе В можно получить как выражения со значением 0, так и выражения со значением 1: выражение 0 (нулевой сложности) имеет значение 0, а выражение #(0) имеет значение 1. Используя это свойство, для компонент сц с номерами, отличными от г, подберем выражения Ф/ со значениями, равными оц. Рассмотрим выражения 0(ФЬ Ф2 ..., Ф.-1, Ф , Ф.+1, ) и у(Фь Ф2,..., Ф,_і, Фк+1, Ф1+ь ...). 3Через 0 обозначается набор, все компоненты которого нулевые Оба эти выражения имеют значение 0, а их сложности различаются на единицу. Отсюда непосредственно получаем, что в последовательности {/п} есть два ненулевых идущих подряд элемента Лемма доказана.
Лемма 11. Пусть все функции базиса В не сохраняют ноль и хотя бы одна из них отлична от тождественно единичной функции. Тогда в каждой из последовательностей {tn} и {/„} бесконечно много ненулевых членов
Доказательство. Все функции в базисе В не сохраняют ноль, поэюму существует выражение Фі со значением 1. Кроме того, по условию леммы, в базисе В есть функция, отличная от тождественной единицы, а следовательно, существует выражение Фо со значением 0 и сложностью отличной от нуля.
Выражение Фо содержит хотя бы одну константу 0. Подставим вместо нее выражение Фо, в результате чего получим новое выражение со значением 0 большей сложности. Выполняя такую подстановку многократно, получим выражения со значением 0 сколь угодно большой сложности.
Аналогично, подставляя выражение Фо вместо константы 0 в выражении Фі, получаем выражения со значением 1 сколь угодно большой сложности. Лемма доказана.
Из лемм 9-11 следует, что достаточным условием апериодичности последовательностей {tn} и {fn} в случае базиса с хотя бы одной функцией, отличной от тождественной единицы, является наличие хотя бы в одной из последовательностей двух идущих подряд ненулевых членов. Это условие можно сформулировать в терминах свойств базиса В.
Соседними называем двоичные наборы одинаковой длины, которые различаю і ся ровно в одной компоненте. Лемма 12. Пусть базис В, все функции которого не сохраняют ноль, содерэюит функцию, отличную от тождественной единицы, а таксисе функцию д, значения которой на каких-нибудь двух соседних наборах совпадают. Тогда последовательности {tn} и {fn} апериодичны.
Доказательство. Пусть а и а — соседние наборы, различающиеся в г-й компоненте и при этом д(а) = д(& ). Для номеров j, отличных от г, выберем какие-нибудь выражения Ф со значениями а3.
Постоянство функции вероятности однородных базисов
Пусть В — однородный базис с базисным многочленом B(S) и характеристическим многочленом A(T,F), и пусть d3 = ттгтЬг- Функция вероятности базиса В постоянна и равна С, О С 1, при всех р Є (0,1) тогда, и только тогда, когда разности d3 — C образуют геомет-рическую прогрессию со знаменателем г-.
Теорема 17, фактически, означает следующее: для того, чтобы функция вероятности однородного базиса тождественно равнялась постоянной С (0 С 1), необходимо и достаточно, чтобы доля единиц среди значений функций базиса на слоях булева куба „колебалась" около величины С. При этом, если С , то „амплитуда колебаний" будет увеличиваться с увеличением номера слоя; если С , то с увеличением номера слоя „амплитуда" будет уменьшаться. Наконец, в случае С = \ „амплитуда" будет посюянной.
На основании соотношений (3.8) можно сформулировать более простое достаючное условие постоянства функции вероятности. Следующая теорема является непосредственным следствием равенств (3.8).
Следствие 9. Пусть задан базис В = Вг. Пусть коэффициенты характеристического многочлена при всех j удовлетворяют равенствам r for = С. Тогда Pi{p) = С для всехр Є (0,1).
Приведём теперь пример, явно демонстрирующий, что следствие 9 выражает условие достаточное, но не необходимое: построим базис с постоянной функцией вероятности, у которого доли единиц в слоях будут не постоянными, а „колеблющимися".
Пример 8. Положим С — \, а щ2? = d$ = . Тогда, согласно (3.9), Таким образом, доли d3 = r](r, должны представлять из себя последовали телыюсть из чередующихся значений и . Например, для г = 2 можно взять систему функций {/, Ф, &} Проверим, что действительно Р\(р) = \. Характеристический многочлен рассматриваемой системы равен F2 + 4TF + Т2. Следовательно: = тп 2у + 4т 2 7 + 2т w 4 р - 2т + Ър + 4т ш 1-2а + 4т В рассмаїриваемом случае и и сг связаны уравнением 1 = 3-2ил7, из которого вытекает равенство и -1 = бег. Таким образом, РгіР) = 2((7 + Г) 2((7 + г) 1 6(7-2(7 +4т 4((7 +г) 2 Отметим, что в построенном примере доли единиц по слоям „колеблются" около величины 1/2 с „амплитудой" равной 1/6. Из соотношений (3.7) следует
Теорема 18. Пусть задан однородный базис с постоянной функцией вероятности, равной С при всех р (0,1). Тогда С — рациональное число.
Доказательство. Рассмотрим уравнение (3.7) при j = 0. (1 — C)d[) — С + Cd\ = 0. Оно преобразуется к виду C(da + l — di) = do. За исключением случая одновременного выполнения равенств do = 0 и d\ = 1, отсюда вытекает равенство С = d +1_ , что влечёт рациональность числа С.
Если do = 0 и d\ = 1, рассмотрим уравение (3.7) при j = 1: (1 — C)d\ — С + Cdi — 0, откуда С = d _r _d = -- Следовательно, С — рационально. Теорема доказана.
С помощью соотношений (3.9) можно доказать, что объединение двух однородных базисов с одинаковыми постоянными функциями вероятности является базисом с той же функцией вероятности.
Теорема 19. Пусть В и В" — два однородных базиса порядка г и функция вероятности каоїсдого из них постоянна и равна С при всех р Є (0,1), причём константа С Є (0,1) — одна и та же для обоих базисов. Тогда функция вероятности базиса В = В U В" также постоянна и равна С при всех р Є (0,1).
Отметим, что в формулировке теоремы базисы В и В" объединяются как мультимножества: если какому-то элементу В и какому-то элементу В" соответствует одна и та же функция, то в объединении будут присутствовать два элемента, которым соответствует одна и та же функция, т.е. функция входящая двукратно.
Доказательство Пусть а гг и о! п — количество единиц в г-м слое у функций из В и В", соответственно. Пусть d[ = "rL . и d" = TTWFT- ИЗ условия теоремы и равенств (3.9) вытекают соотношения:
Полученное соотношение показывает, что функция вероятности базиса В равна С при всех р Є (0,1). Теорема доказана. Аналогично, с точностью до замены знаков + на —, доказывав і ся Теорема 20. Пусть В — базис порядка г и В С В. Пусть функция вероятности каждого из базисов В и В равна С при всех р Є (0,1). Тогда функция вероятности базиса В\В такэюе постоянна и равна С при всех Р(0,1).
Таким образом, объединение однородных базисов сохраняет свойство тождественного равенства функции вероятности заданной постоянной С.
Перейдем к рассмотрению условий постоянства функции вероятности неоднородных базисов. Установим сначала достаточные условия постоянства, основанные на представлении неоднородного базиса в виде объединения однородных. Далее будет показано, при каких дополнительных ограничениях Э1и достаточные условия являются и необходимыми.
Рассмотрим соотношения (3 12) как равенства нулю многочленов or а При каждом фиксированном j, равенство (3.12) является многочленом от а, содержащим степени а от первой до r-й. Сокращая многочлен на множитель а О, получаем равенство нулю многочлена степени г — 1 в точке и.
Пусть постоянная С является рациональным числом, а число а — алгебраическое, сіепени г. Тогда каждое из соотношений (3.12) представляет собой равенство нулю некоторого многочлена с рациональными коэффициентами степени г — 1 в точке а. Следовательно, все коэффициенты многочленов равны нулю, т.е. для всех k = l,...,rnj = 0,...,r — l выполнены равенства:
Рассмотрим равенства при каждом фиксированном значении к. Заметим, что каждое слагаемое в сумме содержит биномиальный коэффициент (r ), поэтому все слагаемые при г j в действительности равны нулю. Рассмотрим последовательно значения j = О,..., г — 1 и покажем, что из соотношений (3.14) следуют равенства (1 — C)dk% + Cdk%+\ — С = 0 при всех
При j = 0 сумма в равенстве (3.14) вырождается в одно слагаемое, в результате чего равенство принимает вид: ( ) (r )((1-C)dko+Cdki—С) = О, откуда вы і екает: {1-C)dko + Cdki-C = 0. (3.15) При j = 1 в сумме (3.14) два слагаемых, первое из которых равно нулю, в силу соотношения (3.15). Следовательно, второе слагаемое также нулевое, ч іо влечет равенство (1 — C)dk\ + Cdk2 — С = 0. Рассматривая равенства (3.14) при j = 2,3..., г — 1, получаем при каждом к = 1,..., г (1 - C)dh + Cdkl+l-C = 0, г = 0,..., к - 1. Таким образом доказана Теорема 23. Пусть базис В порядка г таков, что его функция вероятности постоянна и равна некоторому рациональному числу С, а число о, соответствующее базису В является алгебраическим, степени г. Тогда каждое из мнооїсеств В для к = 1,..., г является базисом с постоянной функцией вероятности, равной С. Следует отметить, чгю равенство алгебраической степени числа а порядку базиса В является весьма сильным условием. В частности, оно не выполняется для ранее рассмотренных однородных базисов. Однако, теорема 23 легко распространяется на более широкий класс базисов. Рассмотрим базис вида B = BqU Bq+l U ... U Br_i U Вг, (3.16) где q 0, Bq т 0 и Вг ф 0. Тогда уравнение (3.13) принимает вид: г г г Y, \Bk\kak = Y, \Bk\ko-k l + ]Г \Вк\а\ k—q k=q k=q откуда следует, ч іо алгебраическая сіепень числа и не превышает r — q-\-\. Заметим, что для базисов вида (3.16) каждое из равенств (3.12) является многочленом сіепени не выше г — q от а, поэтому выполнена
Теорема 24. Пусть базис В имеет вид 5gUBg+iU.. .l)Br-\\jBr, где q О, Bq Ф и Вг ф. Пусть число а, соответствующее базису В, является алгебраическим, степени r — q+1. Пусть функция вероятности базиса В постоянна и равна некоторому рациональному числу С. Тогда каждое из множеств Bk для k = q,...,r является базисом с постоянной функцией вероятности, равной С.
Теорема 24 описывает более широкий класс базисов с постоянной функцией вероятности, нежели теорема 23, однако, существуют и базисы с по-сюянной функцией вероятности, не удовлетворяющие условиям теоремы 24 Прежде всего, это касается базисов с постоянной иррациональной функцией вероятности (см. раздел 3 3 4). Кроме того, существуют базисы вида (3.16), у которых алгебраическая еіепень числа а строго меньше г — q + 1.
Пример 9. Построим базис В = Bi U В%, имеющий постоянную функцию вероягносіи такой, что функция вероятности для каждого из базисов В и Д} не является постоянной. Пусть ?2 — мультимножество, состоящее из пяти вхождений штриха Шеффера. Тогда, очевидно, функция вероятности базиса Въ непостоянна и, вообще говоря, совпадает с функцией вероятности базиса {/}, см. пример 6. Для построенного множества . имеет место: \B-i\ — 5, а = 5, агі = 10, а22 = 0 Множество Дз составим из булевых функций xyVxzV yz, xyz, xyz V xyz V xyz. Тогда имеет место \Bz\ = 3, азо = 1, азі = 0, азг = 6, а3з = 1. Базисный многочлен базиса В имеет вид bS2 + 353, откуда а — 5/3. Характеристический многочлен базиса В имеет вид А(Т, F) = 5F2 + 10TF + F3 + 6T2F + Т3. По теореме 7 функция вероятности базиса В выражается через г, и; и о следующим образом.
Равномерное приближение непрерывных функций
Исследованные ранее функции вероятности базисов выражали асимптотическую вероятность того, что случайное булево выражение над заданным базисом принимает значение 1. В данной главе рассматриваются вероятностные характеристики бесповторных булевых формул, связанные с обращением в единицу порождаемых ими случайных булевых выражений. Это исследование позволит, во-первых, расширить представления о содержательном смысле функций вероятности базисов, а, во-вторых, установить связь с некогорыми другими вероятностными моделями, упомянутыми во Введении.
Пусть рассматривается вероятностное пространство булевых выражений сложности п над некоторым заданным базисом. Напомним, что согласно определению 7, функция Pi,n(p) равна {Ф} или, в виде вероятно Ф=п,Ф=1 сти события, Р\,п{р) = Р{Ф — !} С помощью формулы полной вероятности функцию Р\,п{р) можно записать в виде: Р\,П{Р) = У2 {Ф = 1Ф порождается Ф}Р{Ф порождается Ф}. Ф=п
Как отмечалось в разделе 1.1, вероятность Т{Ф порождается Ф} равна \/sn. Вероятность Т{Ф = 1Ф порождается Ф} — эю условная вероятность того, что случайное выражение Ф равно единице при условии, что Ф порождается заданной бесповторной формулой Ф. Фактически, эта величина является аналогом функции Р\,п(р) внутри подмножества выражений, порождённых некоторой заданной формулой Ф.
Определение 9. Функцией вероятности бесповторной формулы Ф называется величина Р\(р\Ф) = Т{Ф = 1Ф порождается Ф}
Отметим, что функция вероятности формулы Ф = f(x\,... ,хт), где / — некоторая булева функция, выражается через характеристический многочлен Af базиса {/}, состоящего из одной-единсгвенной функции /: Р1(р\Ф)=А;(р,1-р) С использованием введённого обозначения функция Р\,п(р) записывается в виде: Напомним, что функция вероятности базиса является пределом функций Pi,n(p), поэтому соотношение (5 1), фактически, устанавливает связь между функциями вероятности формул над заданным базисом и функцией вероятности этого базиса.
Бесповгорные формулы также можно рассматривать как один из вариантов „преобразователей вероятности" [31], о которых говорилось во Введе-нии. Каждая бесповторная формула Ф[хі,...,хт] задаёт некоторую булеву функцию /ф(#і,... ,хт). Функции /ф, в свою очередь, однозначно сопоставляется числовая функция /іф(рі, ... ,рт), равная вероятности обращения функции /ф в единицу при случайной независимой подстановке вместо каждой из её переменных хг констант 1 с вероятностью рг и 0 с вероятностью 1 — рг. Функция /іф непосредственно связана с функцией вероятности формулы Ф соотношением Р\{р\Ф) = Ь,ф(р,...,р) и описывает некоторое преобразование вероятностей р\,... ,рт.
Функция /іф, а следовательно и функция вероятности формулы Ф, может быть непосредственно вычислена по заданной формуле Ф с помощью следующего просюго свойства (см [9]), связывающего композицию формул с композицией соответствующих функций /гф
Для рассматриваемых задач наименование переменных в формуле не существенно, поэтому будем считать, что композиция бесповторных формул подразумевает переименование переменных таким образом, что бесповтор-ность формулы не нарушается. Подстановку формул Фі,..., Фт в формулу Ф будем обозначать Ф[Фі, .. ,Фт]- Легко видеть, что функция h для фор АЛ А мулы Ф[ФЬ ..., Фт] имеет вид /ІФ(/ІФІ, ., /ьФт).
Таким образом, вычисление функции вероятности отдельно взяюй бесповторной формулы не представляет особой сложности, однако получение описания множества всевозможных функций вероятности бесиовторных формул над заданным базисом В оказывается существенно более сложной, и, в то же время, более интересной задачей Наиболее продуктивным путём исследования функций вероятности формул над фиксированным базисом оказалось рассмотрение множества значений функций вероятности всевоз можных формул над этим базисом в различных фиксированных точках р отрезка [0,1].
Такое множество совпадает с множеством значений, которое може г быть получено в виде булевых комбинаций независимых бернуллиевских случайных величин, имеющих вероятность обращения в единицу равную р. Это наблюдение устанавливает непосредственную связь рассматриваемой задачи с задачами, изучаемыми в работах Р. М. Колпакова [9] и других авюров [14, 11] Специфика задачи, рассматриваемой в данной диссертации, заключается в комбинировании случайных величин с помощью функций из некоторого базиса (а не с помощью произвольных булевых функций) и в ограничении множества исходных значений вероятности до одного-единсгвенного значения р.
Представляется естественным рассматривать не только те значения, которые получаются в точности как значения функций вероятности формул в точке р, но и те значения, которые могут быть получены приближённо с любой наперёд заданной точностью. Определим множество WB(P) как множество значений функций вероятности бесповторных формул над базисом В в точке р, замкнутое относительно операции предельного перехода, т. е. дополненное всеми своими предельными точками. Именно множество WB{P) является объектом дальнейших исследований.
Начнём рассмотрение с базисов, все функции которых лежат в некоторых специальных классах. Пусть К — множество всех функций, являющихся конъюнкциями переменных или константами, D — множество всех функций, являющихся дизъюнкциями переменных или константами и L — множество всех линейных булевых функций В базисах, целиком лежащих в одном из этих классов, в силу ассоциативности операций, все формулы фиксированной сложности эквивалентны и функция вероятности любой формулы Ф сложности п совпадает с функцией РіуП(р). Легко проверить следующие три утверждения: В каждом случае множество (р) имеет не более одной предельной точки: эго точка 0 для В С К, I для В С D и 1/2 для В С
Как отмечалось выше, функция вероятности любой формулы сложности п в базисе из класса К, D или L совпадает с функцией Р\,п{р) этого базиса Вообще говоря, для базиса, не лежащего в классе К, D или L, ситуация может отличаться: функции вероятности формул существенно изменяются в зависимости от рассматриваемой формулы.
Прежде, чем перейти к изучению устройства множества WB{P) В общем случае, рассмотрим два специальных случая — множество WB(P) при р = О и при р = 1.
Рассмотрим формулу Ф в произвольном фиксированном базисе В и значение её функции вероятности Рі(0Ф). Заметим, что при р = 0 среди вы-ражений, порождаемых формулой Ф, только одно имеет вероятность, отличную от нуля. Это выражение, получающееся подстановкой констант О вместо всех переменных формулы Ф. Значение этого выражения равно О или 1, поэюму значение Рі(0Ф) есть 0 или 1. Фактически, выполняется равенство Л(0Ф) = Ф[0,..., 0]. Аналогично, для любой бесповторной формулы Ф значение Рі(1Ф) рав-ноФ[1,..., 1]. Таким образом, значения Р\ (0 Ф) и Рі(1Ф) могут быть только 0 или 1. Следовательно, для любого базиса В имеет место WB{0) С {0,1} и WB(1) Я {0,1} Далее будем рассматривать множества \в(р) при р Є (0,1).
