О глубине и сложности формул в предполных классах k-значной логики

• Автор: Сафин, Ринат Фатехович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 82 с.

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

1.1. Основные определения и обозначения

1.2. Основные свойства систем функций

1.3. Вспомогательные утверждения

1.3.1. Метод преобразования формул

1.3.2. Основные следствия

1.3.3. Преобразование 5-формул

2. Классы типов ЬиР

2.1. Классы линейных функций

2.2. Классы самодвойственных функций

3. Классы типов Е, В и О

3.1. Классы функций сохраняющих разбиения
3.2. Классы типа В
3.3. Классы монотонных функций
4. Классы типа С
Ф 4.1. Классы типа
4.2. Равномерные порождающие системы в классах типа С* при к
4.2.1. Порождающие системы
4.2.2. Равномерность подсистем
4.2.3. Существование равномерных порождающих систем
4.3. Классы типа Сг
4.3.1. Классы типа и С?7. Т-максимальные функции
4.3.2. Равномерность порождающих систем в классах типа Сг
5. Доказательство основных теорем
Литература

Данная работа относится к математической теории синтеза управляющих систем. В ней рассматривается задача о реализации формулами функций из предполных классов Ахшачпой логики.
Одной из основных задач математической кибернетики является построение и изучение модельных классов управляющих систем с точки зрения сложности. Класс формул, реализующих функции /с-значной логики, к ^ 2, является одним из основных модельных классов управляющих систем. В качестве наиболее естественных мер сложности формул выступают число переменных, входящих в формулу, и глубина. Число переменных, называемое также сложностью формулы, характеризует “стоимость”, а глубина - время работы, при условии что различные вычисления можно производить параллельно. Для каждой функции требуется построить такую формулу, которая реализует эту функцию, и является наилучшей относительно выбранной меры сложности. Имеется простой метод для нахождения таких оптимальных формул, основанный на переборе всех формул данной сложности. Однако этот метод практически не применим, поскольку требует для своей реализации большого числа шагов. Поэтому возникает задача о разработке таких методов синтеза, которые позволяют строить для всех функций из заданного множества относительно хорошие формулы, и при этом существенно проще перебора всех формул.
Для множества всех булевых функций асимптотически оптимальные методы синтеза формул в полных базисах (а также ряда других важных классов управляющих систем) были разработаны О.Б. Лупановым [7-13] (см. также [6, 45]). Оценки глубины формул в полных базисах были получены в работах [4, 5) (см. также |18|). Из результатов О. Б. Лупанова, в частности, следует, что большинство функций алгебры логики допускает лишь очень сложную реализацию. Поэтому, с одной стороны, представляет интерес выделение классов функций, допускающих более простую реализацию, и разработка методов синтеза оптимальных формул для функций из этих классов. С другой стороны, представляется важным для различных естественных классификаций функций £-значной логики иметь оценки глубины и сложности формул, реализующих функции из соответствующих классов. Одной из наиболее известных и лучше всего изученных с функциональной точки зрения классификаций булевых функций является описание Э. Поста [40, 41] множества всех замкнутых относительно операции суперпозиции классов функций (см. также [14, 16, 22, 27, 37|). Обзор результатов, полученных для формул над конечными системами, реализующих функции из классов Поста содержится в [23]. При к > 3 к настоящему времени изучены только некоторые семейства замкнутых классов в Р*,, в частности, предполные классы функций, все семейства которых описаны в работах И. Розенберга [46, 47] (см. также [2, 15, 26, 29]). Таким образом, возникает задача о реализации функций из замкнутых классов &-значной логики формулами над конечными системами, имеющими наименьшую сложность или глубину. При этом при реализации функций из некоторого замкнутого класса &-значной логики представляется естественным рассматривать формулы в базисах состоящих из функций принадлежащих этому же классу.
Как правило, при разработке вычислительных устройств возникает необходимость минимизировать сложности формул одновременно но нескольким параметрам, например, по числу элементов и времени работы. Поэтому представляет интерес получение соотношений между глубиной и сложностью формул, реализующих заданные функции.
Конечную систему функций 21 из Рь к ^ 2, будем называть равномерной, если существуют такие константы с и ф зависящие только от системы 21, что для всех функций / из [21] выполнено неравенство
ВД)<с1оё2Ра(/) + ф (1)
где Ра(/) и Ая(/) соответственно минимальные сложность и глубина, с которыми можно реализовать функцию / формулами над системой 21. Все необходимые определения приведены в главе 1.
В. М. Храпченко показал (см. |28[), что любая полная в Р2 конечная система функций равномерна. Аналогичный результат был получен Ф. Спирой [48], (см. также [42]). Похожую задачу о времени вычисления арифметических выражений с использованием нескольких процессоров рассматривали Р. Брент, Д. Кук и К. Маруяма [32] и Р. Бреит [33, 34], применившие метод преобразования формул для арифметических выражений аналогичный предложенному В. М. Храпченко и Ф. Спирой. Поскольку пижняя оценка для Ра(/) аналогичная (1) (с другими константами) получается тривиально, оценка (1) является наилучшей по порядку. Задача о получении оценок для константы с в соотношении (1) для различных полных систем булевых функций рассматривалась в работах [24, 25, 35, 39, 43, 49]. Использованный в работах [28, 48] метод позволяет по произвольной формуле построить эквивалентную ей формулу логарифмической глубины от сложности исходной формулы. При этом сложность формулы увеличивается. Путем модификации метода преобразования формул в некоторых случаях можно добиться чтобы увеличение сложности было незначительным (см. [31, 36]). Отметим, что методы преобразования формул, приведенные в работах [28, 48| легко переносятся на случай полных систем функций 1г-значной логики при к ^ 3. Однако они существенно используют полноту систем.
Для полных монотонных систем булевых функций равномерность была доказана И. Вегенером [51] (см. также [52]). Равномерность произвольных конечных систем булевых функций была доказана А. Б. Угольниковым [20, 21], им также приведены примеры неравномерных систем функций в Рь при к ^ 3 (см. также [44]). Поскольку, как уже было отмечено выше, методы приведенные в работах (28, 48] позволяют устанавливать равномерность полных систем функций в Р/с при любом к ^ 3, возникает вопрос О равномерности неполных систем функций в Р/с. Л. И. Ахметовой [1] был анонсирован результат о том, что любая конечная система функций в Р3, порождающая предполный класс, является равномерной. В данной работе изучается равномерность конечных порождающих систем для предполных классов й-значной логики.
Пусть к ^ 2. Множество (0,1 к — 1} будем обозначать через Е^. Класс функций, сохраняющих отношение р, будем обозначать через Ар (определения см. в главе 1). Будем пользоваться обозначениями из (29], согласно которым в Р^ имеются следующие семейства предполных классов:
1) классы самодвойственных функций классы типа Р;
2) классы линейных функций — классы типа Ь;
3) классы функций, сохраняющих разбиения множества Е— классы типа Е;
4) классы функций, сохраняющих сильно гомоморфные прообразы /ьадических элементарных отношений, — классы типа В;
5) классы монотонных функций — классы типа О;
6) классы функций, сохраняющих центральные отношения, — классы типа С.
Если р — отношение частичного порядка на Е*, такое, что для любых двух элементов а и Ь из Е/с существуют зир(а, Ъ) и тДаД) относительно частичного порядка р, то

Утверждение 4.2.17. Пусть /(ад х$, г) - функция из II и ОТ, ‘/’(Уь • ■ • 1У<нг) ~ функция из А Аа, В ВЧ — формулы над и и ЯЛ, е которые не входит переменная г, Ь(В,) ^ У, г = 1 д. Тогда существуют р, 1 =% Р йг Я + 8, функция ■ ■ ■ ,уР,г) из $ и формулы В[,... ,В'р над II и ОТ, в
которые не входит переменная г, такие, что
ДАЬ ..., А„ <р(Въ. ..,ВЧ,г)) Л ^(Б; Б;, г),
и верны неравенства Б(Бг') < N + 53 Т(А3), г = 1,... ,р.

Доказательство. По утверждению 4.2.16 либо
/(ад, <р(гц, ..., уя, г)) Ч ч>(/(хи..., х„ ух) /(жь • ■ ■, ха, уд), г),
либо функция /(ад х8,1р(у1 уя, г)) принадлежит множеству 5.
В первом случае положим р = д, у> = <р, В[ = /{Ах А,, Б,:), г = 1, ...,д.
Легко видеть, ЧТО выполнены соотношения Ь(В[) = Ь(Вг) + 53 В{А3) ^ N + 53 -ЦА;')'
7=1 7
г = 1 р.
Во втором случае положим р = д + в, <рг = /{х х„<р{ух уч,г)), В[ = Ах, г = Б'+, = Б;, г = 1д. Легко видеть, что выполнены соотношения
Б(Б') = Б(А<) «: Е £(А). * = 1, ■ • •, 8. Б(В,'+3) < У, г = 1,... ,р. ш

Утверждение 4.2.18. Пусть Ф{х,г) — формула над и и ОТ, причем переменная г имеет только одно вхождение в формулу Ф. Тогда существуют такие г 1? 1, формулы ФДж) Фг(£) над Б и ОТ и функция <р{ух,... ,уг,г) из множества 5, что
Ф(г,г) ч <р(Ф1(г) ФГ(г),г)
«ед<ЦФ),* = 1 г.
Доказательство. Поскольку все функции входящие в формулу Ф симметрические, формула Ф(х, г) эквивалентна формуле Ф'(х, г) над БиОТ той же глубины и сложности, имеющей вид
Ф'(х,г) = ПА /г(Л; Л7,Л‘ Л^ Л1 Л^,г),
где /Дад,... ,хщ, г) /г (яд,... ,хПг,г) — функции из множества Б и ОТ, А{ — формулы над и и ОТ, в которые не входит переменная г, г = 1 г, / = 1 щ.
Покажем, что для каждого / = 1 г — 1 существует формула Ф3(х, г) над Б и ОТ такая, что Ф’(х,г) Ч ФДж, г), имеющая вид
Ф3(х, г) = П/,(А,. • •, А»1 А) Л"ББ(Бь ...,Вя,х)),
где ф £ 5, БДт) — такие формулы над Б и ОТ, в которые не входит переменная г, что
Г П
г = 1,... ,д.
г=J[+1
Для / = г — 1 формула Ф' уже имеет требуемый вид
ФГ_,(х, г) = Ф'(х, г) = П/ь...,/г_1(А1 А?1 А^ь ..., • • •, АА *))■