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

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

Оглавление
Введение

1 Определения и вспомогательные утверждения

1.1 Определения и обозначения

1.2 Связь между двумя мерами сложности формул

1.3 Некоторые оценки сложности булевых функций

1.4 Некоторые свойства функций из Рзд

1.5 Простейшие методы синтеза

1.6 Порождающие системы максимальных классов

2 Сложность псевдолинейных функций

2.1 Псевдолинейные функции и их свойства

2.2 Классы и2,г П £, £2,г и С,
2.3 Класс С.
2.3.1 Свойства минимальных формул
2.3.2 Нижняя оценка для функции Шеннона
2.3.3 Верхняя оценка для функции Шеннона
2.3.4 Верхняя оценка сложности произвольной функции
2.3.5 Нижняя оценка сложности произвольной функции
3 Сложность функций из максимальных классов
3.1 Представление функций из максимальных классов
3.1.1 Специальное разбиение множества Е
3.1.2 Верхняя оценка мощности разбиения
3.1.3 Представление функций из множества
3.2 Верхние оценки для функций Шеннона
3.3 Нижние оценки для функций Шеннона
3.4 Асимптотически точные формулы для функций Шеннона
4 Глубина формул, реализующих функции из Р12
4.1 Классы, проекция которых содержит функцию 8р или 5*
4.2 Классы, проекция которых совпадает с Б или Бщ
4.3 Классы, проекция которых совпадает с классом БМ
Литература

Введение
Данная диссертация относится к теории синтеза и сложности управляющих систем — одному из основных разделов дискретной математики и математической кибернетики. В ней рассматривается задача о сложности реализации функций многозначной логики формулами над конечными системами.
Задача синтеза и сложности управляющих систем [69, 30, 34, 103] в общем случае формулируется следующим образом. Дан набор G базисных элементов некоторого типа (например, функциональные элементы или формулы), каждому из которых приписано некоторое положительное число — вес элемента. С помощью этих элементов по заданным правилам строятся более сложные объекты —■ схемы. Каждой схеме S ставится в соответствие некоторая функция / и число L(S), равное сумме весов всех входящих в нее элементов; при этом говорят, что функция / реализуется схемой S со сложностью L(S). Сложностью функции / называется величина La{f) = mmL(S), где минимум берется по всем схемам S над G, реализующим функцию /. Для каждой функции / требуется найти минимальную схему S над G, реализующую / (то есть такую^ схему Формулы и схемы из функциональных элементов (называемые далее схемами), реализующие дискретные функции, являются одними из основных модельных классов управляющих систем. Множество _Рj, всех функций /с-значной логики, к ^ 2, является важным примером класса дискретных функций, представляющим большой интерес как с теоретической, так и с прикладной точек зрения. Одной из наиболее изученных классификаций функций /с-значной логики являются классы функций, замкнутые относительно операции суперпозиции (см., например, [68, 71, 8, 35]). В связи с этим возникает задача о реализации функций fc-значной логики из замкнутых классов формулами (или схемами) над конечными системами. В этой задаче можно выделить два направления исследований: синтез схем и формул в полных базисах и синтез схем и формул в неполных базисах.
Приведем сначала некоторые результаты, полученные в этих направлениях для функций алгебры логики. В задаче о сложности реализации булевых функций основополагающие результаты были получены О. Б. Лупановым, предложившим асимптотически оптимальные методы синтеза для ряда классов управляющих систем [25-34].

В частности, для произвольного полного конечного базиса £7 булевых функций он показал [26, 27] справедливость следующих соотношений1:
^ФЭ(Р2(п))~р^,

гдеЬ«'э(Р2(п))и1§(Р2( п)) — функции Шеннона при реализации функций схемами и формулами соответственно, а р — константа2, однозначно определяемая по базису С. Оценки высокой степени точности для функций Шеннона при реализации булевых функций формулами и схемами в полных базисах получены в работах С. А. Ложкина [19, 20, 22, 23].
Задача о поведении функций Шеннона для множества всех булевых функций тесно связана с задачей о поведении функций Шеннона, соответствующих замкнутым классам булевых функций при реализации функций схемами и формулами в полных конечных базисах. Полное описание множества всех замкнутых классов булевых функций получено Э. Л. Постом [98, 99] (см. также [85, 72, 59, 102, 91, 38, 39, 92, 05]). Он показал, что это множество счетно, причем каждый замкнутый класс имеет конечный базис. В ряде работ [67, 70, 50, 48, 40,14, 15, 82] изучалась задача о сложности реализации монотонных булевых функций (множество всех таких функций обозначается через М). Асимптотически точные формулы для функций Шеннона при реализации функций из класса М схемами в произвольных полных конечных базисах приведены в работах [52] и [97] (эти формулы получены на основе методов кодирования монотонных функций из работ [83] и [84] соответственно). При реализации функций схемами для каждого замкнутого класса булевых функций, не содержащегося в множестве3 Ь и К и Л, и любого полного конечного базиса А. Б. Угольниковым [55, 60) получена асимптотически точная формула для соответствующей функции Шеннона. При реализации функций формулами для всех замкнутых классов булевых функций, не содержащихся в множестве4 5 и Ь и К и £>, и для любого конечного полного базиса асимптотически точные формулы для соответствующих функций Шеннона получены А. Е. Андреевым [1, 2, 4].
Следует отметить, что упомянутые выше методы синтеза схем и формул существенным образом используют полноту базисов. Поэтому задача о синтезе схем и формул в неполных базисах требует разработки других методов синтеза. Отметим некоторые результаты, полученные в задаче о сложности реализации булевых функций из замкнутых классов схемами и формулами в неполных базисах. При реализации функций схемами для замкнутых классов функций, сохраняющих константы, и любых конечных систем, порождающих эти классы, асимптотически точные формулы для соответствующих функций Шеннона были получены Э.И. Нечипоруком [41, 42).
13десь и далее всякий раз, когда речь идет об асимптотических оценках, подразумевается, чго эти оценки имеют место при га —* оо.
“Константа р называется минимальным приведенным весом элементов базиса.
3Через Ь, К и О обозначаются множества всех линейных функций, конъюнкций и дизъюнкций соответственно.
4 Через 5 обозначается множество всех самодвойственных функций.

Перейдем к изучению классов £2,п 1 ^ г ^ оо. Опишем некоторые свойства минимальных формул над системой Эг, г ^ 2.
Пусть /(х,..,хп) е г: Ф — минимальная формула, реализующая функцию / над системой 53Г1 Т — дерево, соответствующее формуле Ф. В силу минимальности формулы Ф ни одна подформула формулы Ф не может иметь вид г/г(£ь .... Ег), где хотя бы одна из подформул Е1, ...,ЕГ отлична от символа переменной (в противном случае подформула цг(ЕцЕг) реализует функцию тождественный ноль и Ф не является минимальной). Поэтому можно считать, что любая подформула формулы Ф имеет один из двух видов: либо А(Е,П), где Е,П — формулы над Эг, либо иг(хг1, ...,3цг), где 1 ^ н ^ ... ^ гг ^ п. Пусть V — вершина дерева Т, не являющаяся висячей. Обозначим через /„ фуНКЦИЮ, реализуемую ПОдформуЛОЙ, соответствующей ВерШИНе V. ПуСТЬ VI — висячая вершина дерева Т. Обозначим через уш символ из множества Хп и {1}, приписанный вершине ад.
Лемма 2.2.1. Пусть Ф — минимальная формула над системой Х)г. Тогда формула Ф реализует функцию
^^11(2/111) + ^ ' /у
шел veB
Доказательство проведем индукцией по глубине формулы Ф. Перечислим минимальные формулы глубины 1, реализующие функции из класса £2: 1(^)> А(з:1;а:2), —,2пг), где 1 ^ гх ^ ... < гГ < п, Ш[,12 6 X. Легко видеть, что для каждой из них утверждение леммы выполняется. Пусть теперь утверждение леммы справедливо для всех минимальных формул глубины не более /, / > 1. Пусть Ф — минимальная формула, П(Ф) = I + 1. Так как формула Ф минимальна, то она не может иметь вид цг(Ег, ...,ЕГ), где хотя бы одна из подформул £1,...,ЕГ отлична от символа переменной. Так как В(Ф) ^ 2, то формула Ф не может иметь вид г/Дян, где
1 < ц ^ ... ^ гг < п. Следовательно, формула Ф имеет вид А(Е,...,П), где Е,П — минимальные формулы над Так как Е и П являются минимальными формулами, то к ним применимо предположение индукции, из которого утверждение леммы следует тривиальным образом. Лемма доказана.
Обозначим через Ат множество висячих вершин дерева Т, таких, что единственной смежной с ней вершине соответствует подформула вида А(Е, П). Обозначим через Вт множество вершин дерева Т, которым соответствует подформула вида пДЕц £г).
Лемма 2.2.2. Пусть Ф — минимальная формула над системой реализующая функцию /, аТ — соответствующее ей дерево. Тогда выполняются неравенства
АТ>Ш + Н,, ВТ^К}.
Доказательство. Докажем неравенство АТ > |,Д[ + Hj- Пусть, от противного, Ит[ < 1-^/1 + Н}. Тогда найдется символ у € Хп и {1}, который не приписан ни одной из висячих вершин множества А, и такой, что Д(у) 6 3/ и Я/. Так как символ у не приписан ни одной из висячих вершин множества А, то в силу лемм 2.2.1 и 2.1.