Введение к работе
Актуальность темы исследований. В математике естественным способом задания функций является представление при помощи суперпозиции выделенных функций, часто называемых базисными. Такие представления в теории булевых функций называют термами или формулами. Возросший интерес к изучению представлений булевых функций термами объясняется тем, что булевы функции являются наиболее эффективным аппаратом для синтеза схем, применяемых в электроннике.
При исследовании термальных представлений булевых функций естественно возникают две основных проблемы:
определить, существует ли представление заданной функции в виде терма над некоторым базисным множеством функций;
в том случае если такое представление существует, найти наилучший, в определенном смысле, терм, представляющий данную функцию.
Решение первой проблемы принадлежит Э.Посту1. На постановку второй проблемы повлияло то, что булевы функции являются общепризнанной моделью для проектирования электронных схем. В связи с этим, имеется большой практический интерес к нахождению термальных представлений булевых функций, имеющих наименьшую сложность. Эта проблема еще далека от окончательного решения. С одной стороны, широко известен результат О.Б. Лупанова2, который получил асимптотическое выражение для оценки сложности представлений булевых функций термами над различными полными базисами. Им доказано, что почти все булевы функции имеют сложность j-.
Однако, СВ. Яблонский3 показал, что не существует эффективного метода задания последовательностей самых сложных булевых функций. Более того, все известные до сих пор последовательности
'Post 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.
2Лупанов О.Б. Асимптотическая оценка сложности управляющих систем.-М.: Из-во МГУ, 1984.- 137 с.
3Яблонский СВ. Об алгоритмических трудностях синтеза минимальных контактных схем //Сб.Проблемы кибернетики. Вып.2.- М.:Фиэматгиз, 1959.- С.75-122.
булевых функций имеют лишь полиномиальные оценки сложности. Таким образом, проблема минимизации для конкретных функций не имеет до сих пор удовлетворительного решения.
Бесповторные булевы функции, то есть функции, для которых существует представление в виде терма, в котором каждая переменная встречается один раз, имеют особое значение, как функции наименьшей сложности. Понятие бесповторности для булевых функций часто возникает в связи с исследованиями вопросов сложности представлений булевых функций термами.
Хотя количество бесповторных булевых функций существенно меньше, чем остальных функций, они имеют большое практическое значение. Большинство функций, применяющихся при разработке микропроцессоров, являюется бесповторными в базисе, состоящем из конъюнкции, дизъюнкции и отрицания4. В связи с этим существует потребность в получении эффективных алгоритмов, позволяющих определить, является ли данная функция бесповторной, и, в случае успеха, найти ее реализацию в виде терма.
Важность изучения бесповторных функций подтверждается и работой В.А. Кузнецова5 о том, что бесповторное представление для булевой функции является, в некотором смысле, единственным, поэтому при рассмотрении многих вопросов, изучение всех булевых функций сводится к изучению неразделимых функций, то есть функций, не допускающих бесповторной декомпозиции на функции меньшей размерности.
Слабоповторные булевы функции являются, в некотором смысле, наименьшими из повторных функций. Как следует из результата Н.А. Перязева6 о том, что всякая слабоповторная функция является неразделимой, добавление к базису слабоповторной функции позволяет, с одной стороны, расширить его в смысле увеличения возможностей по реализации булевых функций термами, а с другой стороны, сделать это расширение минимальным, что позволяет исследовать
4Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Настраиваемые модули для управляющих логических устройств.- Ленинград: Энергоиздат, 1981.- 166 с.
'Кузнецов А.В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики// Труды математ. института им. В.А.Стеклова.-1958.-Т. 51.- С. 186-225.
6Перязев Н.А. Сложность представлений булевых функций формулами в не-монолинейных базисах// Иркутский ун-тет. Серия: Дискретная математика и информатика. Вып. 2.- Иркутск, 19Э5. - 15 с.
базисы по сложности термальных представлений .
Изучение слабоповторных булевых функций в различных базисах позволяет создать классификацию неразделимых булевых функций, которая может быть использована как в теоретических, так и в практических целях.
Цели исследований:
изучение свойств бесповторных и слабоповторных булевых функций в различных базисах;
разработка критериев бесповторностн для различных базисов;
получение полного описания слабоповторных булевых функций в некоторых сериях базисов.
Методы исследований. Использовались методы теории булевых функций и комбинаторики.
Научная новизна. Исследование свойств бесповторных и слабоповторных функций в произвольных базисах позволило разработать подход к получению критериев бесповторностн булевых функций в произвольных базисах, при помощи которого получен новый критерий бесповторностн для полного бинарного базиса. При исследовании слабоповторных булевых функций изучалось множество функций, которые становятся слабоповторными при расширении базиса. Получен критерий, позволяющий определить конечность или счет-ность этого множества. Получено полное описание слабоповторных булевых функций в двух сериях базисов. Все результаты диссертации являются новыми.
Теоретическая и практическая ценность. Полученные в диссертации результаты имеют значение для теории булевых функций и могут найти практическое применение в задачах синтеза дискретных преобразователей информации. Полученные результаты могут применяться при исследовании проблем сложности представлений булевых функций термами.
Субботовская Б.Л. О сравнении базисов при реализации функций алгебры логики формулами// ДАН СССР.- 1963.- Т. 149, № 4.- С. 784-787. Черухин Д.Ю. Алгоритм сравнения булевых базисов// Материалы двенадцатой международной конференции по проблемам теоретической кибернетики. - Нижний Новгород. -1999. - С. 249.
Апробация работы. Результаты диссертации были представлены на Сибирской конференции по исследованию операций (Новосибирск, 1998), Второй международной конференции "Мальцевские чтения" (Новосибирск, 1998), Двенадцатой международной конференции по проблемам теоретической кибернетики (Нижний Новгород 1999), Международной конференции по математической логике, посвященной 90 - летию со дня рождения А.И. Мальцева (Новосибирск 1999), конференции "Алгебра, логика и кибернетика", посвященной памяти А.И. Кокорина (Иркутск 1999), семинаре Института динамики систем и теории управления СОР АН, а также многократно докладывались на семинарах Иркутского государственного университета.
По теме диссертации имеется 7 публикаций [1] - [7].
Структура и объем работы. Диссертационная работа изложена на 115 страницах и состоит из введения, трех глав, разбитых на 7 параграфов, заключения и списка литературы, содержащего 57 наименований, включая работы диссертанта.