О сложности реализации функций многозначной логики формулами специального вида

Оглавление
Введение 4
1 Определения и вспомогательные утверждения 11
1.1 Основные определения и обозначения............................ 11
1.2 Некоторые замкнутые классы.................................... 14
1.3 Бинарные операции с правым сокращением........................ 16
2 Булевы функции 20
2.1 Эквивалентные преобразования а-формул ........................ 20
2.2 Верхние оценки функций Шеннона................................ 23
2.3 Реализация монотонных функций................................. 26
2.4 Реализация немонотонных функций............................... 27
3 Двоично представимые функции трехзначной логики 33
3.1 Критерий двоичной представимости функции ............... 33
3.2 Частичная эквивалентность многочленов......................... 35
3.3 Сопоставление многочленов формулам ........................... 41
3.4 Верхние оценки функции Шеннона для класса двоично
представимых функций.......................................... 46
3.5 Нижние оценки функции Шеннона для класса двоично
представимых функций.......................................... 51
3.6 Верхние оценки глубины для произвольной функции............... 54
4 Функции многозначной логики 62
4.1 Функции ИЗ Рк,2 .............................................. 62
2
4.2 Верхние оценки глубины для произвольной функции Список литературы
3
Введение
Данная работа относится к математической теории синтеза и сложности управляющих систем — одному из основных разделов дискретной математики и математической кибернетики. В ней рассматривается задача о реализации функций многозначной логики формулами специального вида над конечными базисами.
Одной из основных задач математической кибернетики является построение и изучение модельных классов управляющих систем с точки зрения их сложности. В общем случае эта задача, может быть сформулирована следующим образом. Рассматривается набор базисных элементов, из которых по некоторым правилам строятся более сложные объекты — управляющие системы (например, схемы из функциональных элементов, контактные схемы, формулы). Заданы правила, позволяющие каждой системе сопоставить реализуемую ей функцию. Кроме того, каждой системе сопоставлено положительное число (сложность), которое характеризует ее стоимость. Рассматриваемая задача состоит в построении по заданной функции такой управляющей системы, которая реализует эту функцию и является оптимальной относительно выбранной меры сложности; при этом сложность построенной системы называется сложностью этой функции. Для заданного множества функций исследуется также поведение функции Шеннона, которая характеризует сложность реализации в рассматриваемом классе управляющих систем самой сложной функции, принадлежащей этому множеству и зависящей от фиксированного числа перменных.
Пусть к > 2. Положим £* = {0,1,...,А; - 1}. Обозначим через
Рк множество всех функций А-значной логики. Формулы над конечными
4
базисами, реализующие функции из Р*, — один из основных модельных классов управляющих систем. Основными мерами сложности формул являются число символов переменных, входящих в формулу, и глубина; число символов переменных характеризует “стоимость”, а глубина — время вычисления реализуемой функции. Для каждой конечной системы 21 С Р* через [21} обозначим множество функций, реализуемых нетривиальными формулами над системой 21. Пусть F € [21]. Функцию Шеннона по сложности (числу символов переменных) для множества F обозначим мере:? Р«д(Р(п)), а функцию Шеннона по глубине — через £>а(Р(гс)). Если F = [21], то функции Шеннона L^(F(n)) и
(F(n)) будем обозначать также через L%{n) и Аа(п) соответственно.
Асимптотически оптимальные методы синтеза для основных модельных классов управляющих систем были разработаны О. Б. Лупановьтм (14, 15, 20, 21, 22, 23, 24, 25]. В частности, он показал [16, 17], что для любого полного в Р* конечного базиса 21 имеет место асимптотическое равенство
т ( \
Ра (гг) — р- ,
log 2п
где р — константа, зависящая от системы 21 (минимальный приведенный вес элементов базиса).
Наряду с задачей о поведении функции Шеннона для класса Рз, рассматривается также задача о поведении функции Шеннона для различных подмножеств этого множества. Одной из наиболее известных и хорошо изученных с функциональной точки зрения классификаций булевых функций является описание семейства всех замкнутых относительно операции суперпозиции классов функций, полученное Э. Постом [46, 47]. Он показал, что это семейство является счетным, и что для каждого замкнутого класса существует конечная порождающая система. Изложение этих результатов содержится также в [40, 32, 26, 44, 27, 45, 35].
При исследовании задачи синтеза формул в конечных базисах, реализующих функции из замкнутых классов Поста, рассматриваются две отдельные задачи — синтез в полных базисах и синтез в неполных базисах. Для каждого полного конечного базиса и каждого замкнутого класса булевых функций, не
5
содержащегося полностью ни в одном из классов1 5, Ь, К, Г>, асимптотически точные формулы для соответствующих функций Шеннона были получены А. Е. Андреевым [3, 4]. Для некоторых замкнутых классов и любых конечных систем, порождающих эти классы, асимптотически точные формулы для соответствующих функций Шеннона получены А. Б. Угольниковым |28, 29]. Он показал также [30, 31], что для произвольной конечной системы булевых функций функции Шеннона по глубине и сложности имеют соответственно линейный и экспоненциальный порядок роста относительно числа переменных.
Таким образом, в задаче о сложности реализации булевых функций получен ряд существенных результатов. Получение аналогичных результатов для функций к-значной логики (к > 3) сопряжено со значительными трудностями, которые связаны с континуальностью семейства замкнутых классов [42] (см. также [41]) и отсутствием описания семейства всех конечнопорожденых замкнутых классов2. Вместе с тем, для некоторых полных в Р* базисов асимптотически точные формулы для соответствующих функций Шеннона были получены в работах Ю. В. Захаровой [11], С. Б. Гашкова [б], С.А. Ложкина [13]. Задачу о реализации формулами функций из класса3 Рзд исследовал Д.А. Дагаев [8, 9, 10]. Он получил оценки и асимптотически точные формулы для функций Шеннона, соответствующих некоторым замкнутым классам. В то же время при исследовании задачи синтеза формул в неполных базисах приведены примеры последовательностей функций многозначной логики, сложность которых имеет сверхэкспоненциальный порядок роста относительно числа переменных [31, 33, 34, 1,2]. Эти результаты говорят о принципиальных отличиях многозначных логик от двузначной логики с точки зрения теории сложности.
Одно из важных направлений исследований в задачах синтеза формул над конечными базисами состоит в исследовании реализации функций формулами
1 Здесь 5 — класс всех самодвойственых функций, Ь — класс всех линейных функций, К — класс всех конъюнкций, О — класс всех дизъюнкций.
’^К настоящему времени получено описание лишь отдельных семейств замкнутых классов функций многозначной логики (см., например, работы [38, 39, 48, 49]).
3ЗдеСЬ Р)с,2 — класс всех функций к-зиачной логики, принимающих значения 0 и 1, к > 3.
6