Введение к работе
Актуальность темы исследований. Теория функциональных систем образует одно из главных направлении исследований в математике. Конечнозначные функциональные системы наряду с теорией графов являются универсальным аппаратом описания конечных моделей в дискретной математике и математической кибернетике. Изучение таких систем связано с именами целого ряда выдающихся математиков, среди них Дж. Буль, Г. Фреге, А. Пирс, М. Шеффер, П.С. Порецкий, Е. Пост, И.И. Жегалкин, А.И. Мальцев, К. Шеннон, В.М. Глушков, А.В. Кузнецов, СВ. Яблонский, О.Б. Лупанов.
Особая роль в теории конечнозначных функциональных систем отводится булевым функциям. Возникновение булевых функций было связано с исследованиями по математической логике. Затем они приобрели фундаментальное значение для оснований математики, однако долго оставались практически невостребованными в части математических приложений. Только открытие в середине XX века приложений к техническим проблемам стимулировало внимание к теории булевых функций.
В работах К. Шеннона и В.И. Шестакова была впервые продемонстрирована плодотворность идеи применения аппарата теории булевых функций к проблемам синтеза релейно-контактных схем.
Невозможно представить человеческую деятельность без компьютерной техники, развитие которой существенно зависит от уровня разработки математических моделей дискретных преобразователей информации. Функционирование самых сложных современных компьютеров поддается описанию средствами теории булевых функций. На сегодняшний день общепризнана роль булевых функций как аппарата для изучения дискретных преобразователей информации.
Для современного уровня развития цивилизации характерным является переработка громадного, быстро растущего объема информации, которая вывела на ведущее место математические модели, описывающие обработку, хранение, передачу, тестирование информации. В связи с этим теория булевых функций нашла применение не только в логических системах, синтезе, диагностике и контроле различного рода схем, но и в теории кодирования, в теории конечных автоматов, в теории игр, в языках программирования и даже при математическом моделировании природных процессов.
В теории булевых функций, как и в любой другой функциональной системе, одним из основных способов задания функций является задание их с помощью суперпозиции выделенных базисных функций. Такие задания принято называть формульными, а суперпозиции — формулами в заданном базисе1.
В 20-40-х годах Э. Посту удалось описать все порожденные с помощью суперпозиции классы булевых функций — замкнутые классы функций2. Оригинальное детальное изложение этого результата было весьма сложно и занимало большой объем. В дальнейшем доказательство результата Э. Поста было упрощено3.
Для теории булевых функций актуальным является представление функций формулами специального вида. Хорошо известны разложение Шеннона, двойственное к нему, разложение, получаемое из разложения Шеннона заменой дизъюнкции на сложение по модулю два, разложение Акерса, а также канонические формы: совершенные дизъюнктивная и конъюнктивная нормальные формы, совершенная полиномиальная нормальная форма, поляризованные полиномы Же-галкина.
Интерес к полиномиальным разложениям связан с техническими приложениями. При логическом проектировании дискретных устройств одним из основных этапов является представление булевых функций различными формулами над заданным базисом4. До настоящего времени в составе элементного базиса преобладали элементы, реализующие функции конъюнкцию, дизъюнкцию и отрицание. В результате достижений интегральной технологии последнего десятилетия получили распространения также серии микросхем, содержащих в своем составе элементы "сложение по модулю 2". Необходимо отметить, что использование таких элементов тесно связано
'Яблонский СВ. Функциональные построения в k-значной логике// Труды математ. института им В.А.Стеклова.- 1958.- Т 51.- С. 2-142.
2Post E.L. Introduction to a general theory of elementary propositions//Amer. J. Math- 1921.- V.43, No 4.- P. 163-185; Post E.L. Two-valued iterative systema of mathematical logic// Annals of Math. Studies.- 1941.- No 5.
3Яблонский СВ., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста.- М: Наука, 1966.- 120 с; Марченков С.С, Угольников А.Б. Замкнутые классы булевых функций.- М: Ин-т лрикл математики АН, 1990.-147 с.
4Глушков В.М., Капитонова Ю.В., Летичевский А.А. Автоматизация проектирования вычислительных машин.- Киев: Наукова думка, 1975.- 231 с.
со сложностью устройств, особенно это относится к программируемым логическим матрицам, структура которых напрямую моделирует представление булевых функций нормальными формами. Теоретические исследования показывают, что применение полиномиальных форм при логическом проектировании ведет к более компактному размещению логических схем на элементной базе5.
Для технических приложений, особенно в части синтеза настраиваемых модулей для управляющих логических устройств, имеют большое значение рассматриваемые в диссертации бесповторные представления булевых функций. Актуальность исследований слабоповторных функций для теории булевых функций вытекает из их связи с понятием неразделимости, а также с изучением сложности представлений булевых функций в различных базисах6.
Получение нижних оценок сложности конкретных функций является трудной и до настоящего времени недостаточно разработанной проблемой теории булевых функций. Из результатов по оценке сложности формульных представлений отметим, полученное О.Б. Лупановым7 асимптотическое выражение для функции Шеннона, используемой для оценки сложности.
Цель исследований. При формульном задании булевых функций возникает необходимость во введении специальных ограничений, например, заранее задается вид формул или ограничивается их сложность. В связи с этими ограничениями возникают следующие фундаментальные проблемы:
1. Характеризация функций, представимых формулами над задан-
ными базисами или формулами специально заданного вида, без привлечения понятия суперпозиции.
2. Нахождение множества функций R или формул специально за
данного вида Ф таких, что любые булевы функции из некоторого
множества К представляются формулами над R или формулами
вида Ф, при этом, если такая формула для функции в определен
ном смысле единственна, то такие формулы называются канони-
5Sasao Т., Besslich P. On the complexity of mod-2 sum PLA's// IEEE Trans, on Comput- 1990.-V. 39, No 2.- P. 262-266.
6Субботовская Б.А. О сравнении базисов при реализации функций алгебры логики формулами// ДАН СССР.- 1963.- Т. 149, Н 4.- С. 784-787.
7Лупанов О.Б. О сложности реализаций функций алгебры логики формулами// Проблемы кибернетики. Вып. 3. гиз, 1963.- С. 61-80.
ческими формами для класса К.
3. Разработка алгоритмов для нахождения представлений функций
формулами, существование которых определяется решением проблем 1 и 2.
4. Оценка сложности найденных формульных представлений, исходя
из определенных критериев сложности формул. Целью диссертации является исследование перечисленных выше проблем:
для представлений булевых функций в виде бесповторных формул над бинарными функциями (формул, в запись которых каждая переменная входит не более одного раза);
для булевых функций, у которых любая нетривиальная остаточная функция (т.е. полученная подстановкой констант) представляется бесповторной формулой над бинарными функциями, а сами функции такого представления не имеют;
для представлений булевых функций в виде многоместной суммы по модулю два специальным образом определенных слагаемых;
для представления линейных функций формулами в различных базисах.
Методы исследований. В диссертации используются методы теории булевых функций, комбинаторики и линейной алгебры. В ряде случаев проводился компьютерный эксперимент с использованием автоматизированной системы вычислений в теории булевых функций.
Научная новизна. Для перечисленных представлений по отмеченным выше проблемам получены следующие результаты.
По первой проблеме:
описан в терминах остаточных функций класс булевых функций бесповторных в бинарном базисе;.
описан в терминах обобщенной однотипности класс булевых функций слабоповторных в бинарном базисе.
По второй проблеме:
— найден широкий класс полиномиальных разложений, включаю
щий, в частности, все другие известные полиномиальные разло
жения.
По третьей проблеме:
— получен непереборный алгоритм для нахождения бесповторных
представлений булевых функций в бинарном базисе, по сложности
сравнимый с заданием булевых функций в векторной форме;
— найдены формулы вычисления коэффициентов введенных полино
миальных разложений и полиномиальных канонических форм без
использования операции нахождения обратной матрицы.
По четвертой проблеме:
получено точное значение функции Шеннона для некоторых классов полиномиальных представлений булевых функций;
разработан новый метод получения нелинейных нижних оценок сложности представления булевых функций формулами в базисах, называемых немонолинейными, и, как следствие этого метода, получено описание всех базисов, в которых линейные функции имеют линейную оценку сложности.
Все основные результаты диссертации являются новыми.
Теоретическая п практическая ценность.
Полученные в диссертации результаты имеют теоретическое значение для теории булевых функций, а также практическое применение для решения прикладных задач синтеза логических схем. Разработанные под руководством диссертанта компьютерные программы по алгоритму бесповторной реализации булевых функций и по вычислению коэффициентов разложения полиномиальных форм использовались в научных исследованиях по теории булевых функций, а также для общей системы синтеза конечных автоматов на программируемых логических матрицах.
Результаты, полученные в диссертации, могут быть использованы при чтении курса лекций по дискретной математике и специальных курсов по теории булевых функций.
Апробация работы. По результатам исследований, изложенных в диссертации, были сделаны доклады в ведущих научных центрах: Московском государственном университете (механико-математический факультет и факультет вычислительной математики и кибернетики), Институте математики СО РАН (г. Новосибирск), Институте кибернетики им. В.М. Глушкова (г. Киев), Иркутском государственном университете, а также на следующих международных конференциях, семинарах, школах-семинарах: по проблемам теоретической кибернетики (Саратов, 1993; Ульяновск, 1996); "Сложность и синтез управляющих систем" (Минск, 1993; Н.Новгород, 1994; Минск, 1995); по дискретной математике и ее приложениям (Москва, 1993); "Дискретные модели в теории управляющих си-
стем"(Москва, 1993); по прикладной логике (Новосибирск, 1992; Иркутск, 1995); по математической логике (Казань, 1992); по алгебре (Красноярск, 1993); 1000 заседании семинара "Алгебра и логика" (Новосибирск, 1994); "Нестандартные логики и логические аспекты информатики"(Канадзава / Япония, 1994); "Нестандартные логики и логика в программировании" (Иркутск, 1995); по приложениям разложения Рида-Маллера в синтезе схем, (Оксфорд / Великобритания, 1997); "Мапьцевские чтения"(Новосибирск, 1997). На некоторых из приведенных конференций были сделаны пленарные доклады.
Публикации. Результаты диссертации опубликованы в работах [1-27].
Структура и объем работы. Диссертационная работа изложена на 173 страницах и состоит из введения, четырех глав, разбитых на 11 параграфов, заключения и списка литературы, содержащего 111 наименований, включая работы диссертанта.