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

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

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

На правах рукописи УДК 519.714

РГБ ОД

Черухин Дмитрий Юрьевич

2 1 МАЙ 2008

О СРАВНЕНИИ БАЗИСОВ ПРИ РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ ФОРМУЛАМИ

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА —2000

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

Научный руководитель

доктор физико-математических наук, член-корреспондент РАН, профессор О. Б. Лупанов.

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

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

Ведущая организация — Институт математики

Сибирского отделения РАН.

Защита диссертации состоится 16 июня 2000 г. в 16 час. 15 мин. на заседании диссертационного совета Д.053.05.05 при Московском государственном университете им. М. В. Ломоносова по адресу: 119899, ГСП, Москва, Воробьевы горы, МГУ, механико-математический факультет, аудитория 14-08.

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

Автореферат разослан 16 мая 2000 г.

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

профессор В. Н. Чубариков.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В связи с этим результатом Б. А. Субботовской, О. Б. Лупанов в начале 60-х годов поставил задачу сравнения базисов в следующем виде. Пусть Б, и Б2 — произвольные базисы. Скажем, что базис Б, предшествует базису Б2, если существуют такие константы С и £>, что для любой булевой функции / выполнено неравенство ЬБ (/)< С-О (здесь Ьъ(/) — сложность функции / в базисе Б, т. е. наименьшая из сложностей формул в базисе Б, реализующих функцию /; сложностью формулы называется число вхождений в нее символов переменных). Отношение предшествования задает частичный порядок на множестве базисов и естественным образом определяет

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

2 Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1979. — 272 с.

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

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

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

производные отношения: строгого предшествования, эквивалентности, несравнимости и непосредственного предшествования.

Отметим основные результаты предшественников, относящиеся к сравнению полных конечных булевых базисов. О. Б. Лупанов дал признак сравнения произвольных базисов и на его основании показал, что базис Б0 = {&, V, -1} является наибольшим, т. е. любой базис ему предшествует. Б. А. Субботовская построила пример неэквивалентных базисов; доказала критерий эквивалентности произвольного базиса базису Б06; дала неалгоритмический критерий сравнения произвольных базисов7; для некоторых базисов Б (в том числе, неэквивалентных базису Б0) доказала, что базис Б и {ф} строго предшествует базису Б8.

В. А. Стеценко классифицировал все 5-функции (функции, «слабоповторные» в базисе Б0) и дал необходимое условие того, что произвольный базис является предмаксимальным (т. е. непосредственно предшествует базису Б0)9. Н. А. Перязев показал, что никакой «немонолинейный» базис не предшествует никакому ♦монолинейному» базису10; классифицировал все функции, «слабоповторные» в базисе, состоящем из всех двуместных функций 11;

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

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

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

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

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

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

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

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

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

Методы исследования. В диссертации использованы разработанные автором методы получения нижних оценок сложности индивидуальных последовательностей функций, основанные на идее «забивания переменных», впервые использованной Б. А. Субботовской 12.

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

1) доказана алгоритмическая разрешимость задачи сравнения базисов; дан алгоритмический критерий сравнения базисов;

2) доказано существование бесконечного множества попарно неэквивалентных базисов; доказано существование бесконечной строго убывающей цепи базисов; доказано отсутствие минимальных базисов; доказано отсутствие бесконечных строго возрастающих цепей базисов;

3) доказано существование предмаксимальных базисов; получена классификация с точностью до эквивалентности предмаксимальных базисов;

4) доказано существование несравнимых базисов; доказано существование бесконечного множества попарно несравнимых базисов; для каждого базиса доказано существование бесконечного множества попарно не эквивалентных базисов, непосредственно ему предшествующих.

Теоретическая и практическая ценность. Диссертация носит теоретический характер. Полученные результаты могут быть полезны специалистам по дискретной математике и математической кибернетике, работающим в МГУ, Институте прикладной математики РАН, НИИ Прикладной

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

математики и кибернетики при Нижегородском гос. университете, Институте математики Сибирского отделения РАН.

Апробация. Результаты диссертации докладывались на ХН-й Международной конференции «Проблемы теоретической кибернетики» (Н. Новгород, 1999), на 1-й (Москва, 1997), Н-й (Н. Новгород, 1998) и Ш-й (Новосибирск, 1999) Научных молодежных школах по дискретной математике и ее приложениям, Х1Х-Й (1997), ХХ-й (1998) и ХХ1-Й (1999) Конференциях молодых ученых механико-математического факультета МГУ, на семинаре «Математические вопросы кибернетики» в МГУ под руководством чл.-корр. РАН С. В. Яблонского (1998) и чл.-корр. РАН О. Б. Лупанова (1999), и на семинаре «Синтез управляющих систем» в МГУ под руководством чл.-корр. РАН О. Б. Лупанова (1998).

Публикация. Основные результаты диссертации опубликованы в работах [1-7].

Структура и объем диссертации. Диссертация изложена на 90 страницах, состоит из введения, четырех глав и списка литературы. Список литературы включает 21 источник.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе введены и исследованы функции, для которых в последующих главах получена нижняя оценка сложности. Первая глава состоит из параграфов 1-3.

В § 1 содержатся основные понятия, используемые в диссертации. Приведем некоторые из них. Базисом будем называть произвольную конечную полную систему булевых функций. Примерами базисов являются Б0 = {&, V,-1} и Р2(п) = {/: {0, 1}п->{0,1}}. Определим по индукции множество формул (в базисе Б).

Базис индукции. Пусть / — п-местная функция, / € Б. Тогда

выражение f(x^,____хп) при п^ 1 [символ / при п = 0] является формулой

в Б.

Индуктивный переход. Пусть / — п-местная функция, п ^ 1, / € Б, каждое из выражений является либо ранее построенной

формулой в Б, либо переменной из множества X = {а;,, а^,...}. Тогда выражение /(Р{,..является формулой в Б.

Подформулой формулы Р называется часть формулы Р, состоящая из подряд идущих символов и являющаяся формулой. Сложностью формулы Г по переменной х, (обозначение: ЬХ(Р)) называется число вхождений в Р переменной х{. Сложностью формулы Р (обозначение: Ь(Р)) называется суммарное число вхождений в символов переменных. Сложностью функции / в базисе Б (обозначение: Ьъ(/)) называется наименьшая из сложностей формул в базисе Б, реализующих функцию /. Обозначим через множество существенных переменных функции /, положим пе5(/) — | У(/)\. Через МБ(/) обозначим отношение ЬБ(/)/ пез(/), если пе5(/)^0.

Скажем, что базис Б, предшествует базису Б2 (обозначение: Б, ^ Бг), если существуют такие числа С и И, что для любой булевой функции / выполнено ЬБ (/) ^ СЬъ (/) + й. Базисы Б, и Б2 эквивалентны (обозначение: Б, ~ Бг), если Б, =^Б2 и Б2 Б,. Базис Б, строго предшествует базису Б2 (обозначение: Б[ чБ2), если Б, =«! Б2 и Б2 =4 Б,. Базисы Б, и Б2 несравнимы, если Б, ^ Б2 и Бг ^ Б,. Базис Б, непосредственно предшествует базису Б2, если Б, -< Б2 и не существует такого базиса Б', что выполнено Б, -< Б' -< Б2. Базис Б называется предмаксимальным, если Б непосредственно предшествует базису Б0.

Формула Р называется бесповторной, если каждая переменная, существенная для функции, ею реализуемой, входит в формулу Р ровно один раз. Скажем, что функция / бесповторно выразима в базисе Б, если существует бесповторная формула в базисе Б, реализующая функцию /. Функция /

называется й-функцией, если / существенно зависит от всех своих переменных, / бесповторно не выразима в базисе Б0, а любая функция, полученная из / подстановкой какой-либо константы вместо некоторой переменной, бесповторно выразима в Б0.

Скажем, что функции / и д от п аргументов обобщенно однотипны, если существует такая перестановка (г,,...,гп) набора (1,...,га) и такие константы с,,.сп, что справедливо тождество:

/(а?„ ..., хп) = 5(х,- © с........ ф с„) Ф ср.

Отношение обобщенной однотипности является эквивалентностью.

Пусть / — функция п аргументов, (г'п..., г'„) — перестановка набора (1,..., п), д — функция к аргументов и 0 ^ к ^ п. Скажем, что множество переменных {х^, ...,а:(} функции / является д-выделимым (или выдели-мым) если существует такая функция Н, что справедливо тождество:

/0*1 > • • х„) = • ■ х^,..

Скажем, что функция / разделима если либо пеэ(/) < п, либо существует такое выделимое множество У переменных функции /, что 2 < |У| < п - 1.

Обозначим через [Б] множество всех функций, полученных из функций базиса Б с помощью подстановки констант вместо некоторых переменных, удаления всех несущественных переменных, замены некоторых переменных их отрицаниями и (возможно) замены функции ее отрицанием. Базис Б называется нормальным, если [Б] = Б. Лексикографически минимальной назовем функцию, набор значений которой лексикографически предшествует наборам значений всех других функций, обобщенно однотипных с ней. Ядром базиса Б (обозначение: Кег(Б)) называется множество всех неразделимых лексикографически минимальных функций, входящих в множество [Б]. Например, Кег(Б0) = {0, х, ху], Кег(£,(2)) = {0, х, ху, х ф у}. Порядком базиса Б (обозначение: пез(Б)) называется наибольшее число существенных переменных у функций из базиса Б.

Подстановкой констант называется произвольное конечное множество пар А = {(а;,., с,),..., (x¡t, ct)}, где х,-,..x¡t — попарно различные переменные, с,,..., ск — константы из множества {0,1}. Подстановку А также обозначим {x¡ = с,,..., х^ = cfc}. Положим V(A) = {а;,-,..х^}, |-A| = fc. Пусть / — булева функция п аргументов, тогда через /|А обозначим функцию п аргументов, для которой выполнено тождество

/\а(Х\1 ■ ■ ^ч) — f(X!> • • •> С1> • • -1 СЫ • • -i Xn)i

где константы с,,..., ct стоят на местах переменных х.,..., x¡^ соответственно. Функция /}А называется подфункцией функции /. Пусть F — формула, тогда через F|A обозначим формулу, полученную из F заменой всех вхождений переменных а;,.,..., x¡ на константы с,,..., ck соответственно.

В § 2 дано определение степеней произвольной функции и доказаны их простейшие свойства. Пусть f — функция п аргументов, m — натуральное число. Индукцией по т определим т-ю степень функции /, которую будем обозначать /(т).

Базис индукции: та = 1. Положим /<•> = /. Индуктивный переход: m ^ 2 и функция /<т-|> уже определена. Если п =0, то положим /(т) =/. Если п ^ 1, то зададим функцию /(т) от пт аргументов формулой

/(/<"-'>(*„ ..• ■.) + «• • • - *.-))•

Функции /(т) рассматривала Б. А. Субботовская |3.

Пусть g — подфункция функции /(т), s — натуральное число, з Ст. Множество переменных V(<7)n{rn.(i-и + и • ••< ^n-.}- 1 называется

s-множеством (функции д); s-множесгво Z называется регулярным, если \Z\ =nJ. Переменная x¿ называется з-регулярной переменной функции д,

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

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

Лемма 1. Пусть / — функция п аргументов, пеБ(/) = п, п ^ 2, т — натуральное число, У С У(/<т)) и

т>(ц-1Г.

Тогда существует такая подфункция д функции /("1), что У(д) СУ и функция, полученная из д удалением несущественных переменных, обобщенно однотипна с /.

Мерой устойчивости функции / (обозначение: и(/)) называется наименьшая из мощностей таких подстановок констант А, что пез(/|у4) = 0.

Лемма 2. Для любой функции / и любого натурального числа т выполнено неравенство

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

Скажем, что функция / забивает функцию д подстановкой констант А, если существует такая переменная что функции /, д и /|л существенно зависят от х{, а функция <;|л не зависит существенно от х¡.

Пусть А,,..., Ар — функции. Обозначим через г>(А,,..., Ар) множество всевозможных наборов функций (А,|в,..Нр\в), где В — подстановка р

констант и У(В)= и Скажем, что функции Л,,..., А независимы

(в совокупности), если

и(А„..., Ар) = и(Л,)х ...xv(hr).

Функция / называется р-универсальной для базиса Б, если пеБ(/) > О и для любых функций А,,..., кр, бесповторно выразимых в Б, множества су-

щественньгх переменных которых по парно не пересекаются и в объединении дают множество V(f), выполнено хотя бы одно из двух:

1) либо функция / забивает какую-то из функций Л,,..., hp некоторой подстановкой констант:

2) либо функции /, hu ..., kp независимы в совокупности.

Утверждение 1. Пусть Б — произвольный базис. Если функция <р бесповторно не выразима в базисе Б, функция h бесповторно выразима в Б и тождественно не равна константе, то

!»<¥>, Л)| >3.

Лемма 3. Пусть Б — произвольный базис, ф — функция к аргументов, бесповторно не выразимая в Б, и nes(^) = к. Тогда функция

является 1-универсалькой для базиса Б.

Лемма 5. Пусть Б — произвольный базис, <р — функция п аргументов, nes(vj)= тг, функция <р является 1-универсальной для базиса Б, u = u(tp), и ^ 2, р — натуральное число и

т(р, <р) = L'og^) pj + U°g„ РJ + 2.

Тогда функция является р-универсальной для базиса Б.

Во второй главе для каждой формулы введен класс ее ¡¿I-подформул; показано, что в подформулах из этого класса возможно производить «забивание переменных»; дана нижняя оценка мощности этого класса подформул исходя из свойств функции, реализуемой объемлющей формулой. Вторая глава состоит из параграфов 4-6.

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

Функция вида х^ Ф... ф х, Ф с называется линейной. Обозначим через фп функцию х, ф ... Ф хп. Базис Б назовем линейным, если функция ®2 бесповторно выразима в базисе Б. Скажем, что функция / линейно зависит от переменной , если

/1(1=0} =/1{х, = 1) © 1-

Формула Р называется приведенной, если выполнены условия:

a) либо Р состоит из одного символа константы, либо ни одна подформула формулы F не реализует константу;

b) каждая функция, входящая в формулу Р, существенно зависит от всех своих аргументов, и либо линейна, либо нелинейно зависит от всех своих аргументов;

c) ни одна подформула <7 формулы Р не содержит вхождений переменных, несущественных для функции, реализуемой формулой (7.

Утверждение 3. Пусть Б — произвольный базис, Р — формула в Б. Тогда существует приведенная формула Р' в базисе [Б], удовлетворяющая следующим свойствам: Р' = Р; Vi Ьх (Р).

Пусть Б — произвольный базис, р = пез(Б). Скажем, что функция / согласована с базисом Б, если выполнены условия:

a) если базис Б линеен, то функция f является р-универсальной для Б;

b) если базис Б нелинеен, то пез(/) > 0 и каждая существенная переменная функции / содержится в некотором фр-выделимом множестве переменных функции /.

Пусть Р — формула вида К..., где Л — символ функции, ... ..., Рп — формулы. Формула .Р называется и-формулой, если не существует такой линейной функции Л, что выполнено тождество

Пусть / — функция, т, в — натуральные числа, 5 < т, д — подфункция функции /(т). Далее, пусть все переменные, входящие в Р, существенны

для функции д. Наконец, пусть Ь — целое неотрицательное число. Формула Р называется I'[-формулой (для функции д), если либо Ь(Р)^Ь, либо хотя бы одна переменная, входящая в формулу Р, не является з-регулярной для функции д.

Подформула Л-), I ^г ^ гг, формулы Р называется -центральной, если она не содержит подформул, являющихся -формулами. Формула Р называется ¡±1 -формулой, если все формулы Р„, за исключением,

быть может, одной, являются -центральными. Переменная называется VI -центральной (для формулы Р), если она входит хотя бы в одну и[-центральную подформулу формулы Р.

Скажем, что функция / забивает формулу Р в базисе Б подстановкой констант А, если существует такая формула Р' в базисе Б и такая переменная г. что выполнены условия: г€ У"(/|д); Р'= Р|А; V» £ ),■

ЬЛР')<1ЛП<)•

Лемма 8. Пусть Б — нормальный базис, р =пез(Б), / — функция п аргументов, пеэ(/) = п, / согласована с базисом Б, тп, з — натуральные числа, з < т, д — подфункция функции /(т). Далее, пусть £ = прг, Р — приведенная -формула в базисе Б, все переменные, входящие в Р, существенны для д. Наконец, пусть 2 — множество всех ¡//-центральных переменных формулы Р и все переменные из множества Z являются з-регу-лярными для функции д. Тогда существует такая подстановка констант А, что |А| ^ ¡Я! + пр, все переменные из множества У(А) являются з-регу-лярными для д, и функция д забивает формулу Р в базисе Б подстановкой констант А.

В § 5 введено понятие ранга функции и дана нижняя оценка количества 1/-подформул данной формулы через ранг функции, ею реализуемой. Рангом функции / (обозначение: г(/)) называется наименьшее целое число г, для которого существует такая функция ф и такие линейные функции Л,,..Лг, что выполнено тождество

Лемма 9. Пусть к, п — неотрицательные целые числа, в — функция к+п аргументов, nes(fl) = fc+n, (р — произвольная нелинейная функция двух аргументов и

д(х,, ...,хгк + п)= в(у(х„ ..ip(xlk_l, х2к + 1,...,х2к + п). Тогда г (fir) к

Лемма 10. Пусть / — нелинейная функция п аргументов, nes(/) = п, т — натуральное число и д — подфункция функции /(т). Тогда

Пусть G — произвольная формула. Обозначим через u(G) количество f-формул среди подформул формулы G. Через р£(С) обозначим количество ^¿-формул среди подформул формулы G.

Лемма 11. Пусть формула G в базисе Б реализует функцию д. Тогда

В § 6, используя результаты § 5, дана нижняя оценка количества подформул данной формулы.

Пусть G — произвольная формула и Р — произвольное подмножество множества подформул формулы G. Определим подмножество цР множества Р следующим образом: пусть,формула Я, Н€Р, имеет вид Я = h(Hu ... ..., Ht), где h — символ функции и Я,,..., Н, — формулы; тогда Я принадлежит множеству цР в том и только в том случае, когда никакая из формул Я,,..., Н4, за исключением, быть может, одной, не содержит подформул, принадлежащих множеству Р.

Лемма 12. Для любой формулы G и любого подмножества Р множества подформул формулы G справедливо

Лемма 13. Пусть Б — произвольный базис, р = пез(Б), j — нелинейная функция п аргументов, пез(/) = п; т, з, Ь, к— натуральные числа, з ^ т, и

п'^2Ьгпгрк.

Далее, пусть д — подфункция функции }<-т), Д — формула в базисе Б, реализующая функцию д. Наконец, пусть каждая л-регулярная переменная функции д входит в формулу О не больше, чем к раз. Тогда

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

Основная лемма. Пусть Б — нормальный базис порядка р, / — функция п аргументов, пеэ(/) = п, функция / нелинейна, согласована с базисом Б, и = и(/) и и ^ 2. Далее, пусть т, з — натуральные числа, з < т и

и' > 99п6р6(МБ(/<т>))2-

Тогда

Теорема 1. Пусть Б — нормальный базис порядка р, / — функция п аргументов, №&(/) = п, функция / нелинейна, согласована с базисом Б, и = = и(/) и и ^ 2. Тогда для любого натурального т, т ^ п, справедливо

Гле ° = шАлГ 7 = 1+2и«„»-

• Посредством 1{т)>д(т) обозначим следующее условие: для некоторого числа С выполнено Нгп д(т)//(тпС; посредством /(гп)жд(тп.) обо-

т -• ло

значим одновременную выполнимость условий /(т)^.д(т) и 5(т)>;/(т).

Теорема 2. Пусть Б,, Б2 — произвольные базисы и пусть не все функции из базиса Б2 бесповторно выразимы в Б,. Тогда для любого числа е, е>0, существует такая функция /Е, что

где N = пе5(/£(т))-

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

Основная теорема. Пусть Б] и Б2 — произвольные базисы. Тогда равносильны следующие три условия м:

а) базис Б, предшествует базису Б2,

б) все функции из базиса Б2 бесповторно выразимы в Б,,

в) Кег(Б2) С Кег(Б, );

кроме того, равносильны условия г) и д):

г) базис Б, непосредственно предшествует базису Б2,

д) Кег(Б2) С Кег(Б,) и | Кег(Б,)\ Кег(Бг)| = 1.

В § 10 из основной теоремы выведены теоремы 3-13, дающие качественные характеристики структуры отношения предшествования на множестве базисов.

Теорема 3. Для всякого натурального числа п, п ^ 2, базис Р2(п + I) строго предшествует базису Рг(п).

Теорема 4. Существует бесконечная последовательность базисов Б,, Б2,.... в которой каждый базис Б,- + 11 г £ Н, строго предшествует базису Б,.

Теорема 5. Не существует такого базиса Б', который предшествует любому базису.

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

Теорема 6. Произвольный базис Б является предмаксимальным тогда и только тогда, когда Б эквивалентен базису вида Б0и{/}, где f — 5-функция.

Теорема 7. а) Каждый предмаксимальный базис эквивалентен базису вида Б0 и {/}, где / — одна из следующих функций:

• . .. • £„ V Х,Х2 ■...■£„, 2, Х{(Х2 V . . . V хп) V Ж, .. • хп,

п^З, (1)

V щ) V х,а;4,

х1(х3х4 V V з V

б) если / — функция из множества (1), то базис Б0и{/} предмаксима-

лен;

в) если /, и /2 — различные функции их множества (1), то базисы Б0и{/,} и Б0и{/2} неэквивалентны.

Заметим, что множество (1) — это полная система различных представителей классов обобщенной однотипности 5-функций. Множество (1) взято из работы В. А. Стеценко15.

Теорема 8. Существует бесконечное множество попарно неэквивалентных предмаксимальных базисов.

Теорема 9. Существует бесконечное множество попарно несравнимых базисов.

Теорема 10. Каждый базис предшествует лишь конечному числу базисов с точностью до эквивалентности.

Теорема 11. Не существует бесконечной последовательности базисов Б,, Б2,..., в которой каждый базис Б;, г € К, строго предшествует базису

Теорема 12. Для произвольного базиса Б существует бесконечное множество попарно неэквивалентных базисов, непосредственно предшествующих базису Б.

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

Теорема 13. Пусть Б,,..Б„ и Б',,..Б'т — две конечные последовательности базисов; Б, = Б), Бп = Б'т; для любого г. 1 ^ i < п — 1, базис Б1 + 1 непосредственно предшествует базису Б,., и для любого j, 1 ^ j < тп — 1, базис + 1 непосредственно предшествует базису Бу. Тогда п = т.

Пользуясь случаем, автор выражает благодарность научному руководителю чл.-корр. РАН О. Б. Лупанову за неоценимую поддержку на всех этапах подготовки диссертации.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

Введение.

Глава 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, -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], что сложность линейной функции ж, ф . ф х„ в произвольном «нелинейном» базисе по порядку не меньше, чем п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 с.