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

• Автор: Черухин, Дмитрий Юрьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Москва
• Количество страниц: 90 с.

ОГЛАВЛЕНИЕ
Введение
Глава I. Свойства функций специального вида
§ 1. Основные понятия
§ 2. Степени функций
§ 3. Функции, р-универсальные для данного базиса
Глава II. Свойства формул специального вида
§ 4. Техника забивания -формул
§ 5. Ранг функции
§ 6. Оценка количества -подформул
Глава III. Нижние оценки сложности функций
§ 7. Основная лемма
§ 8. Оценка сложности степеней некоторых функций
Глава IV. Сравнение булевых базисов
§ 9. Критерий сравнения произвольных базисов
§ 10. Исследование структуры базисов
Литература

ВВЕДЕНИЕ
Результаты диссертации относятся к математической теории синтеза и сложности управляющих систем [20, 4]. Предметом исследования являются формулы в полных конечных булевых базисах [21, 2]. В диссертации изучается зависимость сложности булевых функций в классе формул от функционального базиса [3, 7].
О. Б. Лупанов показал [2, 4], что сложность почти всех булевых функций асимптотически не зависит от базиса. В то же время, существует последовательность булевых функций, сложность которой в одном базисе по порядку больше, нежели в другом базисе. Например, сложность последовательности линейных функций х1 ф... ф хп в базисе {&, V, -1, ©} равна п. В то же время, как показала Б. А. Субботовская [11], сложность этой последовательности в базисе {&, V, -п} по порядку не меньше, чем п3/2.
В связи с результатом Б. А. Субботовской [11], О. Б. Лупанов предложил ввести следующее отношение предшествования на множестве базисов, характеризующее сложность отдельных последовательностей функций: базис Б! предшествует базису Б2, если существуют такие действительные константы С и £>, что для любой булевой функции / выполнено неравенство ЛБ (/)< СХБа(/) + £>, где АБ(Я — сложность функции / в базисе Б. Отношение предшествования естественно порождает отношения эквивалентности, строгого предшествования, несравнимости и непосредственного предшествования на множестве базисов.
Отношение предшествования впервые было введено и исследовано в работе Б. А. Субботовской [12]. О. Б. Лупанов дал (см. [12]) следующий признак выполнимости отношения предшествования для произвольных базисов Б1 и Б2: если все функции из базиса Б2

бесповторно выразимы [12] в базисе Б1; то базис Б! предшествует базису Б2. С помощью этого признака О. Б. Лупанов показал (см. [12]), что любой базис предшествует базису Б0, Б0 = {&, V, ->}, т. е. базис Б0 является максимальным.
Б. А. Субботовская привела [12] пример базиса, строго предшествующего базису Б0. Исходя из результатов работы [11], она показала, что базис Б0и{®} строго предшествует базису Б0. Б. А. Субботовская дала [12] критерий эквивалентности произвольного базиса Б базису Б0. Она показала, что базис Б эквивалентен базису Б0 тогда и только тогда, когда все функции из базиса Б бесповторно выразимы в базисе Б0. Тем самым Б. А. Субботовская описала класс базисов, строго предшествующих базису Б0.
Далее, Б. А. Мучник (Субботовская) для произвольных базисов 65 и Б2 показала [5], что базис Б! предшествует базису Б2 тогда и только тогда, когда сложность одной конкретной последовательности функций /],/2
Следующий результат также принадлежит Б. А. Мучник. Она рассмотрела [6] сложность линейных функций в «нелинейных» [6] базисах. Б. А. Мучник показала [6], что сложность линейной функции ху ф ... ф хп в произвольном «нелинейном» базисе по порядку не меньше, чем п1 + с, где с — действительная положительная константа, зависящая только от базиса. Тем самым было показано, что если Б — произвольный «нелинейный» базис, а Б' — произвольный «линейный» базис, то базис Б' не предшествует базису Б, и базис Б строго предшествует базису Би Б'.

ГЛАВА II. СВОЙСТВА ФОРМУЛ СПЕЦИАЛЬНОГО ВИДА
§ 4. Техника забивания /-формул.
Пусть / — произвольная функция п аргументов, Б — произвольный базис, х{, 1 г < п, — переменная. Функция / называется линейной, если существуют такие константы а0,
/ = аххх ® .. ф апхп Ф а0.
В противном случае функция / называется нелинейной. Введем функцию фи от п аргументов, задав ее тождеством
Ф~ гг* СТА СТА гр
п “ Ф
Базис Б назовем линейным, если функция ф2 бесповторно выразима в базисе Б. В противном случае базис Б назовем нелинейным. Скажем, что функция f линейно зависит от х{, если
0)3/1,,(31)
Скажем, что функция / нелинейно зависит от ж если жг- е У(/) и тождество (31) не выполнено.
Пусть А1 — произвольная формула. Формула А называется приведенной, если выполнены следующие условия:
a) либо Пс, с €{0,1}, либо ни одна подформула формулы А не реализует константу;
b) внешняя функция каждой подформулы формулы А1 существенно зависит от всех своих аргументов и либо линейна, либо нелинейно зависит от всех своих аргументов;
c) ни одна подформула С формулы А1 не содержит вхождений переменных, несущественных для функции, реализуемой формулой (3.