О сравнении базисов при реализации булевых функций формулами

Результаты диссертации относятся к математической теории синтеза и сложности управляющих систем [20, 4]. Предметом исследования являются формулы в полных конечных булевых базисах [21, 2]. В диссертации изучается зависимость сложности булевых функций в классе формул от функционального базиса [3, 7].

О. Б. Лупанов показал [2, 4], что сложность почти всех булевых функций асимптотически не зависит от базиса. В то же время, существует последовательность булевых функций, сложность которой в одном базисе по порядку больше, нежели в другом базисе. Например, сложность последовательности линейных функций х1ф. фхп в базисе {&, V, -1, (c)} равна п. В то же время, как показала Б. А. Субботовская [11], сложность этой последовательности в базисе {&, V, -1} по порядку не меньше, чем п3/2.

В связи с результатом Б. А. Субботовской [11], О. Б. Лупанов предложил ввести следующее отношение предшествования на множестве базисов, характеризующее сложность отдельных последовательностей функций: базис Б! предшествует базису Б2, если существуют такие действительные константы С и И, что для любой булевой функции / выполнено неравенство ¿-^(/Х СЪБг (/) + В, где £б (/) — сложность функции / в базисе Б. Отношение предшествования естественно порождает отношения эквивалентности, строгого предшествования, несравнимости и непосредственного предшествования на множестве базисов.

Отношение предшествования впервые было введено и исследовано в работе Б. А. Субботовской [12]. О. Б. Лупанов дал (см. [12]) следующий признак выполнимости отношения предшествования для произвольных базисов Б! и Б2: если все функции из базиса Б2 бесповторно выразимы [12] в базисе Б19 то базис Б! предшествует базису Б2. С помощью этого признака О. Б. Лупанов показал (см. [12]), что любой базис предшествует базису Б0, Б0 = {&, V, ->}, т. е. базис Б0 является максимальным.

Б. А. Субботовская привела [12] пример базиса, строго предшествующего базису Б0. Исходя из результатов работы [11], она показала, что базис Б0 и {ф} строго предшествует базису Б0. Б. А. Субботовская дала [12] критерий эквивалентности произвольного базиса Б базису Б0. Она показала, что базис Б эквивалентен базису Б0 тогда и только тогда, когда все функции из базиса Б бесповторно выразимы в базисе Б0. Тем самым Б. А. Субботовская описала класс базисов, строго предшествующих базису Б0.

Далее, Б. А. Мучник (Субботовская) для произвольных базисов Б! и Б2 показала [5], что базис Б! предшествует базису Б2 тогда и только тогда, когда сложность одной конкретной последовательности функций /1? /2,. (определяемой базисами Б! и Б2) в базисе Б2 по порядку не меньше ее сложности в базисе Б^ Тем самым Б. А. Мучник свела задачу сравнения двух произвольных базисов к сравнению сложностей одной бесконечной последовательности булевых функций в этих базисах. Вопрос о существовании алгоритма сравнения произвольных базисов остался открытым.

Следующий результат также принадлежит Б. А. Мучник. Она рассмотрела [6] сложность линейных функций в «нелинейных» [6] базисах. Б. А. Мучник показала [6], что сложность линейной функции ж, ф. ф х&bdquoв произвольном «нелинейном» базисе по порядку не меньше, чем п1 + с, где с — действительная положительная константа, зависящая только от базиса. Тем самым было показано, что если Б — произвольный «нелинейный» базис, а Б' — произвольный «линейный» базис, то базис Б' не предшествует базису Б, и базис Б строго предшествует базису Б и Б'.

Примером «нелинейного» базиса является базис Ъ0и{ху/ ххУ V уг}, примером линейного базиса — базис Б0 и {ф}. В силу результатов работы [6], базис Б0 и {ф, ху V хх V yz} строго предшествует базису Б0 и {ху V хх V ух}. Последний базис, в силу результатов работы [12], строго предшествует базису Б0. Таким образом, используя результаты Б. А. Мучник [6, 12], можно построить последовательность из трех базисов, каждый следующий из которых строго предшествует предыдущему. Вопрос о существовании последовательности большей длины, удовлетворяющей этому условию, остался открытым.

Исследование задачи сравнения полных базисов продолжил В. А. Стеценко. Он рассмотрел [10] класс предмаксимальных базисов, т. е. базисов, непосредственно предшествующих максимальному базису Б0. В. А. Стеценко показал, что каждый предмак-симальный базис эквивалентен базису вида Б0 и {/}, где / — 5-функция [10]. Он также полностью описал [10] множество функций. Тем самым В. А. Стеценко дал необходимое условие того, что данный базис является предмаксимальным. Вопрос о существовании предмаксимальных базисов остался открытым.

Ряд результатов получил Н. А. Перязев. В частности, он распространил [8] результат Б. А. Мучник [6] на класс «монолинейных» базисов [8], показав тем самым, что никакой «немонолинейный» базис не предшествует никакому «монолинейному» базису. Затем он получил [9] результат, аналогичный результату В. А. Стеценко [10], классифицировав все функции, «слабоповторные» [9] в базисе, состоящем из всех двуместных функций.

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

В диссертации получены следующие результаты. Автор доказал [13, 14, 17], что существует бесконечная последовательность базисов, каждый следующий член которой строго предшествует предыдущему. Примером такой последовательности является последовательность Р2(2), Р2(3),.где Р2(п) — множество всех п-местных булевых функций. Из данного результата следует, что не существует минимального базиса, т. е. такого базиса, который предшествует любому базису.

Далее, автор доказал [16, 17, 18] существование предмакси-мальных базисов. Как было показано в [16], базис Б предмаксима-лен тогда и только тогда, когда Б эквивалентен базису вида Б0и{/}, где / — 5-функция. Таким образом, необходимое условие, данное В. А. Стеценко, является также достаточным. На основании списка 5-функций, данного В. А. Стеценко, автор классифицировал [16] все предмаксимальные базисы с точностью до эквивалентности. Автор также доказал [16] существование бесконечного множества попарно несравнимых булевых базисов. Примером такого множества является множество {Б0 и {/}: / € Т}, где Т — множество представителей всех классов 5-функций по отношению обобщенной однотипности [10].

Наконец, автор доказал [17, 19] следующий критерий сравнения произвольных базисов Б! и Б2: базис Б! предшествует базису Б2 тогда и только тогда, когда все функции из базиса Б2 бесповторно выразимы в базисе Б^ Тем самым, достаточный признак сравнения базисов, данный О. Б. Лупановым (см. [12]), является также необходимым. Автор ввел понятие ядра базиса [19]. Ядро базиса является конечным множеством функций, эффективно вычислимым исходя из базиса. Автор доказал, что для произвольных базисов Б1 и Б2 справедлив следующий критерий: базис Б} предшествует базису Б2 тогда и только тогда, когда ядро базиса Б2 является подмножеством ядра базиса Б^ Тем самым автор доказал [19] алгоритмическую разрешимость задачи сравнения произвольных базисов. Используя понятие ядра базиса, автор дал [19] следующий критерий непосредственного предшествования одного базиса другому: базис Б} непосредственно предшествует базису Б2 тогда и только тогда, когда ядро базиса Б2 является строгим подмножеством ядра базиса Б! и отличается от него ровно на одну функцию.

Критерии сравнения базисов, доказанные в [19], позволяют выявить некоторые факты о структуре отношения предшествования на множестве базисов. Например, можно показать, что каждый базис предшествует лишь конечному числу классов эквивалентности базисов. Таким образом, не существует бесконечной последовательности базисов, каждый член которой строго предшествует следующему. Далее, для каждого базиса существует бесконечное число попарно не эквивалентных базисов, непосредственно ему предшествующих. Наконец, если рассмотреть две произвольные цепи базисов, у которых совпадают начала и концы, и в которых каждый следующий член строго предшествует предыдущему, то длины этих цепей совпадут. Последний факт позволяет все базисы распределить по ярусам. На нулевом ярусе находится класс эквивалентности базиса Б0, на первом ярусе — классы эквивалентности предмаксималь-ных базисов, на втором ярусе — классы эквивалентности базисов, непосредственно предшествующих предмаксимальным и т. д.

Основным результатом диссертации является критерий сравнения произвольных базисов (см. основную теорему в § 9 главы IV). С помощью этого критерия доказаны все остальные вышеописанные результаты о сравнении базисов, полученные автором (см. теоремы 3−13 в § 10 главы IV). Основная теорема опирается на нижние оценки сложности индивидуальных последовательностей функций в различных базисах (см. основную лемму в § 7 и теоремы 1, 2 в § 8 главы III). Результаты главы III, в свою очередь, опираются на результаты глав I и II. Результаты глав I и II носят вспомогательный характер.

1. Кузнецов А. В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики // Труды МИАН СССР. —1958. —Т. 51. —С. 186−225.

2. Л у п, а н о в О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. — М.: Физматгиз, i960. —С. 61−80.

3. Л у п, а н о в О. Б. О методах получения оценок сложности и вычисления индивидуальных функций Ц Дискретный анализ. Вып. 25. — Новосибирск, ИМ СО АН СССР, 1974. —С. 3−18.

4. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.: Изд-во МГУ, 1984. — 138 с.

5. Мучник Б. А. Об одном критерии сравнимости базисов при реализации функций алгебры логики формулами // Матем.заметки. —1967. —Т. 1, № 5. —С. 515−524.

6. Мучник Б. А. Оценка сложности реализации линейной функции формулами в некоторых базисах // Кибернетика. — 1970. —№ 4. —С. 29−38.

7. Нигматуллин Р. Г. Сложность булевых функций. — М.: Наука, 1991. —240 с.

8. П е р я з е в Н. А. Сложность представлений булевых функций формулами в немонолинейных базисах. — Иркутский университет. Серия: Дискретная математика и информатика. Вып. 2. — Иркутск, 1995. — 15 с.

9. П е р я з е в Н. А. Слабоповторные булевы функции в бинарном базисе. — Иркутский университет. Серия: Дискретная математика и информатика. Вып. 4. — Иркутск, 1998. — 12 с.

10. Стеценко В. А. О предплохих базисах в Р2 // Математические вопросы кибернетики. Вып. 4. — М.: Наука, 1992.— С. 139−177.

11. Субботовская Б. А. О реализации линейных функций формулами в базисе V, &, ~ // Докл. АН СССР. — 1961. — Т. 136, № 3. —С. 553−555.

12. Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами // Докл. АН СССР. — 1963. — Т. 149, № 4. — С. 784−787.

13. Черухин Д. Ю. Об одной бесконечной цепочке улучшающихся булевых базисов. — Препринт механико-математического факультета МГУ. — 1997. — № 7. — 16 с.

14. Черухин Д. Ю. Об одной бесконечной последовательности улучшающихся булевых базисов // Дискретный анализ и исследование операций. —1997. —Т. 4, № 4. — С. 79−95.

15. Черухин Д. Ю. Алгоритм сравнения булевых базисов // Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции. Часть II. / Под ред. О. Б. Лупа-нова.— М.: Изд-во механико-математического ф-та МГУ, 1999.— С. 249.

16. Черухин Д. Ю. О предплохих булевых базисах // Дискретная математика. — 1999.—Т. 11, вып. 2. — С. 118−160.

17. Черухин Д. Ю. О сравнении булевых базисов // Докл. РАН. — 1999. — Т. 367, № 6. — С. 742−743.

18. Черухин Д. Ю. О булевых базисах, непосредственно предшествующих базису {&, V, -|}. // Докл. РАН. — 1999. — Т. 369, № 5. — С. 605−606.

19. Черухин Д. Ю. Алгоритмический критерий сравнения булевых базисов // Математические вопросы кибернетики. Вып. 8. —М.: Наука, 1999. —С. 77−122. 90.

20. Яблонский С. В. Основные понятия кибернетики // Проблемы кибернетики. Вып. 2. —М.: Физматгиз, 1959. — С. 7−38.

21. Яблонский С. В.

Введение

в дискретную математику. — М.: Наука, 1979. — 272 с.