Введение к работе
Актуальность темы. Понятие функции в силу своей фундаментальности занимает одно из самых важных положений в математике. Математические модели, описанные на языке функций, находят широкое применение в различных областях человеческой деятельности. В последнее время интенсивно развивающейся областью теории функций является класс дискретных функций, так как аппарат таких функций используется при проектировании вычислительных устройств, кодировании информации, передаче данных, в диагностике и контроле схем, в теории конечных автоматов, в теории игр, в языках программирования, при математическом моделировании природных процессов и др.
В рамках дискретных функций одним из важнейших понятий является понятие функциональной системы — пары (Р, Q), где Р — множество функций, Q — множество операторов заданных на Р. Изучение функциональных систем связано с именами целого ряда выдающихся математиков. Среди них Дж. Буль, Г. Фреге, А. Пирс, М. Шеффер, П.С. Порецкий, Е. Пост, К. Шеннон, И.И. Жегалкин, А.И. Мальцев, В.М. Глушков, А.В. Кузнецов, СВ. Яблонский, О.Б. Лупанов.
Одной из распространенных функциональных систем является система, в которой элементами первого множества являются функции, определенные на множестве {0,1,..., к — 1} и принимающие значения из этого же множества, а в качестве оператора используется суперпозиция. Такие функции возникают как в самой теории функций, так и в многозначной логике (поэтому их часто называют функциями к-значной логики), в которой требуется для описания некоторых явлений употреблять высказывания, принимающие более двух значений.
Рассматривая функции к-значной логики можно выделить три направления исследований. Первое направление связано с логическими исчислениями, второе с подмножествами функций, а третье с суперпозициями, удовлетворяющими некоторым свойствам.
По первому направлению актуальны вопросы связанные с использованием функциональных систем в многозначных логиках. Исследуются различные семантики конечнозначных логик и строятся адекватные им логические исчисления. Одной из важных задач в этом направлении является построение многозначных логик при обобщенной интерпретации переменных языка первого порядка.
В рамках второго направления основным объектом исследований являются подмножества вместе с операцией суперпозиции и соответствующие им понятия:
замыкания — множества функций, пред ставимых суперпозициями над заданным подмножеством;
замкнутого класса — множества функций, совпадающего со своим замыканием;
клона — замкнутого класса содержащего все проекции (селекторные функции);
полного в замкнутом классе множества функций — множества функций, замыкание которого совпадает с рассматриваемым замкнутым классом.
Наиболее важные достижения здесь относятся к построению и анализу порождающих множеств, проблеме эффективных критериев полноты и описанию решетки замкнутых классов1.
Среди всех работ в этом направлении выделим работы Э. Поста2 и И. Розенберга3.
В вышеперечисленных проблемах основным в паре подмножество-суперпозиция является второй элемент, но не менее интересной, а в последнее время и интенсивно развивающейся, является задача изучения некоторого специального подмножества функций /г-значной логики. В этом случае приходится изменять операцию суперпозиции так, чтобы она не выводила за пределы рассматриваемого подмножества и относительно соответствующим образом измененной операции суперпозиции ставить те же вопросы — замыкания, полноты и т.д.
Среди всех возможных подмножеств выделим подмножества функций 2т-значной логики, которые однозначно определяются по своим значениям на наборах, построенных из элементов множества {0,1,..., т — 1}. Такие подмножества, с одной стороны, возникают при изучении многозначных логик, решении уравнений над функциями, в технических системах, где рассматриваются схемы с неисправностями из некоторого возможного множества, а с другой стороны, являются есте-
Яблонский С. В. Функциональные построения в fc-значной логике // Труды матем. ин-та им. В. А. Стеклова. 1958. Т. 51. С. 2—142.
2Post Е. L. Two-valued iterative systems of mathematical logic. Annals of Math. Studies. Princeton: Univ. Press. 1941. Vol. 5. 122 p.
3Rosenberg I. G. fiber die Verschiedenheit maximaler Klassen in P^ // Rev. Roumaine Math. Pures Appl. 1969. 14. P. 431-438.
ственным развитием теории функций /г-значной логики, в которой наряду со всюду определенными функциями рассматриваются и функции, определенные не на всех наборах и неопределенности могут быть различных видов. Один из путей исследований здесь связан с тем, что неопределенности понимаются как некоторые подмножества множества {0,1,..., к — 1}. Естественно, что такие функции можно назвать обобщениями функций /г-значной логики и, в зависимости от числа и вида неопределенностей, а также измененной суперпозиции, их называют частичными, недоопределенными, доопределяемыми, гипер-, мульти-, ультрафункциями4.
Для третьего направления исследований — изучение суперпозиций специального вида — можно выделить следующие фундаментальные проблемы:
описание при фиксированном к класса функций представимых суперпозициями специального вида.
указание тех значений к, при которых любую функцию /г-значной логики можно представить суперпозициями заданного вида.
разработка простых алгоритмов для нахождения представлений функций суперпозициями специального вида, существование которых определяется решением двух вышеприведенных проблем.
оценка сложности представлений, исходя из определенных критериев сложности.
Одним из ответов на этот вопрос является возможность представления булевых функций дизъюнктивными и конъюнктивными нормальными формами и их аналоги для произвольного к > 2. Для к = 2 наиболее общая постановка задачи рассматривалась О. Б. Лупановым5.
Особый интерес при представлении функций специальными формами вызывают представления, использующие в качестве внешней функции суперпозиции многоместное сложение по модулю к, которые мы бу-Ло Джукай. Теория полноты для частичных функций многозначной логики // Кибернетический сборник. Новая серия. Вып. 25. М.: Мир, 1988. С. 142—157. Тарасов В. В. Критерий полноты для не всюду определенных функций алгебры логики // Проблемы кибернетики. Вып. 30. М.: Наука, 1975. С. 319—325. Алексеев В. Б., Вороненко А. А. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика. 1994. Т. 6. Вып. 4. С. 58—79. Rosenberg I. G. Multiple-valued hyperstructures // Proceedings of 28th ISMVL (May 27-29 1998). IEEE, 1998. P. 326-333.
Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципы локального кодирования // Проблемы кибернетики. 1965. № 4. С. 31—110.
дем называть полиномиальными формами. Многие известные полиномиальные представления булевых функций удалось описать с использованием операторного подхода6.
Естественной является задача распространения этих результатов на произвольные функций /г-значной логики.
Цели работы:
описать логические системы, как область возникновения обобщений функций /г-значной логики;
исследовать вопросы связанные с полными множествами и специальными представлениями частичных гиперфункций и ультрафункций;
перенести операторный подход, развитый для специальных представлений булевых функций на функции /г-значной логики и в рамках этого подхода описать известные полиномиальные представления булевых функций с точки зрения полиномиальных представлений функций /г-значной логики.
Основные результаты и научная новизна. Автору лично принадлежат следующие основные научные результаты (в том числе и из совместных работ):
- построены исчисления табличного типа для семантики языка пре
дикатов с обобщенной интерпретацией переменных и доказаны теоре
мы полноты и корректности;
- найдены некоторые специальные представления частичных ги
перфункций и полные множества, что позволило дать описание всех
максимальных частичных гиперклонов на 2-х элементном множестве
и доказать в терминах предполных классов критерий функциональ
ной полноты. Тем самым решена проблема, являющаяся объединением
известных задач СВ. Яблонского о полноте для частичных и недоопре-
деленных булевых функций;
^Избранные вопросы теории булевых функций: Монография / А. С. Балюк, С. Ф. Винокуров, А. И. Гайдуков и др. / под ред. С. Ф. Винокурова, Н. А. Пе-рязева. М.: Физматлит, 2001. 192 с.
- как аналог частичных гиперфункций и обобщение функций
k-значной логики определены ультрафункции и найдены для них неко
торые полные множества, что позволило доказать критерий полноты
для ультрафункций на 2-х элементном множестве;
найдены необходимые и достаточные условия существования полиномиальных представлений частного вида;
найдены общие условия существования полиномиальных представлений функций /г-значной логики, в которых слагаемые являются операторными образами фиксированной функции (системы функций), и для некоторых таких представлений найдены формулы вычисления коэффициентов без использования операции нахождения обратной матрицы.
В диссертацию включены следующие совместные результаты:
введена новая гиперзначная семантика при обобщенной интерпретации переменных языка предикатов (совместно с Н.А. Перязевым);
предложен операторный подход к специальным представлениям функций k-значной логики, который позволил классифицировать известные операторы (совместно с Н.А. Перязевым);
на основе операторного подхода найдены необходимые и достаточные условия существования полиномиальных представлений булевых функций в которых слагаемые являются бинарными термами (совместно с ученицей А.С. Зинченко);
найдена нижняя оценка сложности для одного класса операторных полиномиальных представлений функций k-значной логики (совместно с А.С. Зинченко).
Основные результаты диссертации являются новыми. Конфликт интересов с соавторами отсутствует.
Теоретическая и практическая ценность. Полученные результаты имеют теоретическое значение и могут найти применение в исследованиях по теории функциональных систем. Результаты могут быть использованы при проектировании дискретных преобразователей информации и при работе с неполными и противоречивыми описаниями состояний.
Методы исследований. В диссертационой работе широко используются понятия и методы теории дискретных функций (в частности по-
нятие сохранения предиката функцией), математической логики, универсальной алгебры, линейной алгебры.
Апробация работы. Результаты диссертации докладывались на: школе-семинаре по дискретной математике и ее приложениям (Москва, 1993); 4-й Международной конференции по прикладной логике (Иркутск, 1995); Международной конференции «Логика и приложения» (Новосибирск, 2000); 12-й Байкальской международной конференции «Методы оптимизации и их приложения» (Иркутск, 2001); Международной конференции «Компьютерные науки и информационные технологии» (Саратов, 2002); X, XIII, XIV и XV Международной конференции «Проблемы теоретической кибернетики» (Саратов, 1993; Казань, 2002; Пенза, 2005; Казань, 2008); Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, 2003); Международной конференции «Алгебра, логика и кибернетика» (Иркутск, 2004); VI и VIII Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 2004; 2009); Российской школе-семинаре «Синтаксис и семантика логических систем» (Иркутск, 2006; Владивосток, 2008); Международном российско-китайском семинаре «Алгебра и логика» (Иркутск, 2007); Шестых Смирновских чтениях по логике (Москва, 2009).
Исследования по теме диссертации выполнялись в рамках грантов РФФИ (00-01-00556 «Вопросы существования, нахождения и сложности представления булевых функций полиномиальными формами», 007-01-00240 «Недоопределенные частичные булевы функции»).
Публикации. По теме диссертации опубликовано 30 научных работ, отражающих основное содержание диссертации, в том числе семь работ в журналах, рекомендованных ВАК РФ [2, 6, 17, 18, 21, 22, 27] и одна коллективная монография [8].
Структура и объем работы. Диссертация изложена на 215 страницах и состоит из введения, четырех глав, заключения и списка литературы, содержащего 181 наименование, включая работы диссертанта.
