Актуальность проблемы. Функции многозначной логики — один из основных модельных объектов дискретной математики, широко используемых для описания разнообразных дискретных систем. Интерес к функциям многозначной логики обусловлен как достаточно широкими выразительными возможностями данных функций, так и возможностью применять к функциям комбинаторно-логические приемы и методы различного рода. В частности, эти методы позволяют получать многочисленные разложения и представления функций через &bdquo-элементарные" функции.
Современная проблематика теории функций многозначной логики весьма разнообразна. Здесь ставятся и решаются задачи метрического, перечислительного, композиционного, сложностного, классификационного и ряда других типов. Особое место в этом ряду занимают задачи классификационного характера. В самом деле, прежде чем проводить систематическое исследование множества функций многозначной логики, необходимо провести хотя бы приблизительное структурирование (классифицирование) этого множества, разбить его на подмножества (классы), которые отвечали бы свойствам, характерным для выбранного направления исследований.
Среди различных подходов к классифицированию множества функций многозначной логики исторически первым явился подход, основанный на термальной (формульной) выразимости функций. Этот подход содержался в пионерских работах Э. Поста [36, 37], в которых была построена полная классификация множества булевых функций. Сейчас этот подход связывают с операторами замыкания на множестве функций многозначной логики (у Поста — оператор суперпозиции) и классификациями, состоящими из замкнутых (относительно выбранного оператора замыкания) классов.
Классификации множеств Р^ функций /с-значной логики, основанные на операторе суперпозиции, являются самыми известными и самыми изученными. Однако, в отличие от случая булевых функций, при любом к ^ 3 соответствующая классификация множества оказывается континуальной [28]. Здесь трудно ожидать таких исчерпывающих результатов, которые получены Э. Постом для множества /V Поэтому исследованию подвергаются наиболее значимые фрагменты решетки (по вложению) замкнутых классов в Р^: максимальные элементы решетки (предполные в Р^ классы), субмаксимальные элементы, атомы решетки, начальные сегменты и интервалы решетки, определяемые хорошо изученными классами, и т. д.
Пусть Ьь обозначает решетку замкнутых классов в Р&-• Для простоты будем предполагать, что элементами решетки Ьд. являются клоны (замкнутые классы, содержащие все селекторные функции).
Ясно, что случай к = 3 вызывал и вызывает наибольший интерес у исследователей, поскольку это наименьшее значение /с, при котором Ь&имеет континуальную мощность. В качестве примера укажем, что для решетки Ьз.
• все 18 максимальных элементов были найдены С. В. Яблонским [24],.
• все 169 субмаксимальных элементов были найдены Д. Лау [32],.
• все 84 минимальных элемента были построены Б. Чаканем [29],.
• все элементы решетки ¿-з, содержащие множество всех трехзначных функций одной переменной, описаны Г. А. Бурле [5],.
• все 144 дискриминаторных класса в Рз были получены С. С. Марчен-ковым [19],.
• все замкнутые классы линейных функций в Р^ при любом простом к (и, в частности, в Рз) были описаны Я. Деметровичем и Я. Бадьинским [30], однако в этом направлении имеется гораздо более общий результат: в Рз существует лишь конечное число замкнутых классов, содержащих существенную линейную функциювсе эти классы фактически описаны в работе С. С. Марченкова [15].
Довольно распространенной является задача, когда требуется определить все замкнутые классы, которые содержат конкретную (в некотором смысле важную) функцию. Так, в работе С. С. Марченкова [17] охарактеризованы все замкнутые классы в, которые включают дуальный дискриминатор с[ {(1(х, х. г) — х и с1(х, у, г) = г при х ф у). К сожалению, в Р3 таких классов будет несколько сотен. А вот для тернарного дискриминатора р (р (х, х, г) = 2 и р (х, у, г) = х при х ^ у) все 144 соответствующих дискриминаторных класса трехзначных функций описаны в работе [19].
С. С. Марченковым получены еще два результата этого типа. Доказано [15], что в Р3 имеется счетное число замкнутых классов, содержащих однородную функцию ¿-з г) = х, если ху у, г попарно различны и.
1з (х, у, г) — г в противном случае). Все они имеют конечные базисы по суперпозиции. Наконец, в работе [16] охарактеризованы все (их конечное число при любом к) замкнутые классы, которые содержат переключательную однородную функцию й (¿-(х, х, у) ~ в (х, у, х) = х, х) = у и ¿-(ж, у, г) = х в остальных случаях).
Иногда часть замкнутых классов определяется тем, что они образуют классификацию (например, множества Р3) относительно некоторого &bdquo-сильного" оператора замыкания. Так, довольно проработанной является 5″ -клас-сификация, которая при к = 3 дает 48 классов [20, 18].
К строению решетки также имеют отношение работы [3, 21, 10, 4, 7]. Особо отметим относительно недавно появившуюся монографию [33], в которой можно найти подробное изложение целого ряда новейших результатов о строении решетки, а также некоторых фрагментов решетки Ь&для произвольных значений к ^ 3.
Самыми важными в вопросах классификации (а также в вопросах полноты) представляются максимальные (предполные) классы. Согласно хорошо известной теореме А. В. Кузнецова [11] при любом к ^ 2 число пред-полных классов в Рк конечно. Усилиями ряда математиков (С. В. Яблонский [24, 25], А. В. Кузнецов [11], В. В. Мартынюк [14], Ло Чжу-Кай [13], И. Розенберг [38, 39] и другие) при любом к ^ 2 все предполные классы в Р/с были найдены и охарактеризованы в терминах сохранения некоторых предикатов.
В настоящее время, следуя И. Розенбергу [38, 39], принято разбивать все предполные классы (и соответствующие предикаты) на шесть семейств (см. также книгу [27]):
• классы функций, монотонных относительно частичных порядков с наименьшим и наибольшим элементами — классы семейства М,.
• классы функций, сохраняющих нетривиальные разбиения множества Ек = {0,1,., к — 1} - классы семейства и,.
• классы функций, сохраняющих центральные отношения — классы семейства С,.
• классы функций, сохраняющих сильно гомоморфные прообразы /г-ади-ческих элементарных отношений — классы семейства В.
• классы самодвойственных функций — классы семейства Э,.
• и классы квазилинейных функций — классы семейства Ь.
Нам будет удобно выделить в семействе С подсемейство Т классов функций, сохраняющих одноместные центральные отношения.
Ввиду теоремы А. В. Кузнецова [11] о функциональной полноте всякий замкнутый класс из Р}~, отличный от Р^, целиком содержится хотя бы в одном из предполных в Р&классов. Отсюда вытекает, в частности, что определяющие свойства предполных классов — предикаты, задающие предполные классы, — присутствуют во всех остальных замкнутых классах. Этот факт следует также из теории Галуа для алгебр Поста [2, 31], согласно которой любой замкнутый класс можно задать подходящим множеством предикатов может быть, бесконечным), среди которых обязательно присутствует хотя бы один из предикатов, задающих предполный класс.
Данные результаты, лежащие в основе теории функций многозначной логики, естественным образом приводят к постановке следующей задачи: каковы все те замкнутые классы в Рк, которые определяются только предикатами, задающими предполные в классы? Иными словами, каковы все те замкнутые классы в Р^, которые представляют собой пересечения предпол-ных в Рк классов?
Данные замкнутые классы, которые мы будем назвать основными замкнутыми классами, образуют &bdquo-каркас" решетки замкнутых классов в поскольку они определяются только &bdquo-основными свойствами" класса Р — свойствами, присутствующими во всех остальных замкнутых классах и отвечающими за решение проблемы полноты в классе .
Таким образом, решение проблемы функциональной полноты в Р^ имеет в качестве логического продолжения перечисление и исследование основных замкнутых классов в Д. В свою очередь, решение этих новых задач открывает возможности для построения обозримых классификаций &bdquo-центральной" части множества Р^, а также позволяет получить ответы на ряд вопросов, связанных с базисами в классе Р^.
Очевидно, что количество основных замкнутых классов (при фиксированном к) конечно. При к = 2 (случай булевых функций) имеется ровно 5 предполных классов и ровно 14 различных пересечений предполных классов. При к = 3 число предполных классов равно 18, а число различных пересечений предполных классов теоретически может быть близко к 218. Понятно, что даже при небольших значениях к решение задачи построения всех основных замкнутых классов в Р^ наталкивается на значительные трудности переборного характера. Вместе с тем анализ случаев к — 2.3 показывает, что одни и те же основные замкнутые классы могут получаться в результате пересечения предполных классов из довольно большого числа наборов таких классов. Возникает задача минимизирования перебора при перечислении основных замкнутых классов. В данной диссертации автором разработан путь решения этой задачи — построение &bdquo-аксиом вложения", которые имеют вид и тем самым устанавливают связь (включение) пересечений некоторых пред-полных классов и объединений некоторых (других) предполных классов.
Фактически, каждая аксиома вида (*) означает, что всякий основной класс, полностью содержащийся в каждом из предполных классов К^, К¿-2, ., К{з, должен также содержаться и в объединении предполных классов Кп' > ¦ ¦ • > К31 ¦ Данное обстоятельство и приводит к сокращению перебора.
Помимо классификации множеств функций, замкнутых относительно операции суперпозиции, определенный интерес представляет задача &bdquo-индивидуальной классификации" функций /с-значной логики, т. е. задача получения множества Р{к) всех возможных распределений таких функций по предпол-ным в Р/г классам. Для решения этой задачи достаточно предварительно найти все основные замкнутые классы в Р^, а затем для каждого основного класса либо построить пример /с-значной функции, лежащей в тех и только в тех предполных классах, которые задают этот основной класс, либо предложить (и обосновать) новую аксиому вложения, из которой бы следовало, что такого примера функции не существует (и, следовательно, данный основной класс не имеет базиса из одной функции).
Наконец, для решения ряда задач (в частности, для ответа на вопрос, существует ли функция с заданным распределением по предполным классам) полезно иметь множество всех тупиковых (т.е. неупрощаемых) аксиом вложения, а еще лучше — иметь его некоторое базисное подмножество (т.е. минимальное множество аксиом вложения, их которого логически выводятся все остальные аксиомы вложения). В этом случае вместо того, чтобы вести поиск нужной строки в множестве (заметим, что это множество может быть слишком большим по мощности, а может быть и вовсе еще не построенным), мы можем просто проверить, удовлетворяет ли данное распределение по предполным классам всем аксиомам из базисного множества аксиом. При этом выигрыш достигается не только за счет того, что в записи каждой аксиомы участвуют далеко не все предполные классы (чаще всего их там от 3 до 5 штук), но и благодаря тому, что количество аксиом в базисном множестве может быть существенно меньше, чем количество строк в множестве Р{к) (см. вторую главу).
Цель работы. Данная диссертационная работа преследует следующие цели:
• изучить структуру замкнутых (относительно операции суперпозиции) классов функций многозначной логики на предмет получения некоторых универсальных (справедливых для всех к ^ 2) свойств вида (*) для пересечений и объединений предполных в Р&классов;
• используя указанные в предыдущем пункте свойства, в трехзначной логике решить задачу поиска всех основных замкнутых классов, а также связанные с ней задачу индивидуальной классификации функций по предполным классам и задачу поиска всех тупиковых аксиом вложенияа в четырехзначной логике построить фрагменты решетки основных замкнутых классов.
Основные результаты работы и научная новизна. Все основные результаты диссертации являются новыми. Укажем наиболее существенные из них.
1. Доказаны 48 утверждений и следствий из них, представляющих собой универсальные (справедливые для всех к ^ 2) свойства пересечений и объединений предполных классов к-значной логики (первая глава);
2. В трехзначной логике: найдены все 1505 основных замкнутых (относительно операции суперпозиции) классов и описан алгоритм построения решетки по вложению, которую они образуют (см. теорему 2.2 из второй главы и приложение В) — получены все 406 вариантов распределения функций по предполным классам (см. теорему 2.3 из второй главы) — найдены все 3602 тупиковые аксиомы вложения, среди которых выделены все 58 ядровых и все 319 регулярных аксиом. Указана также одна из базисных систем аксиом (см. теоремы 2.4 и 2.5 из второй главы и приложение Б);
3. В четырехзначной логике построены фрагменты решетки всех основных замкнутых классов для пересечений предполных классов из семейств М и и (см. теоремы из третьей главы и приложение Е).
Личный вклад автора. Все выносимые на защиту результаты диссертации принадлежат лично автору. Все работы автора по теме диссертации написаны без соавторов.
Методы исследований. В диссертации используются методы и аппарат дискретной математики и математической кибернетики, в частности, комбинаторно-логические методы, а также методы универсальной алгебры.
Теоретическая и практическая ценность. Полученные результаты имеют в основном теоретическое значение и могут найти применение в научных исследованиях по теории функциональных систем.
Апробация работы. На основе результатов, представленных в диссертационной работе, автором были сделаны доклады на следующих научных конференциях и семинарах: Научные конференции «Тихоновские чтения» (Москва, 2010;2012);
Научные конференции «Ломоносовские чтения» (Москва, Севастополь, 2011;2013);
XI, XIII и XV Международные научно-практические семинары «Комбинаторные конфигурации и их применения» (Кировоград, 2011;2013);
XVI Международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 20−25 июня 2011 г.);
XI Международный семинар «Дискретная математика и ее приложения» (Москва, 18−23 июня 2012 г.);
Международный научный семинар «Дискретная математика и ее применение в экономико-математическом моделировании и информационных технологиях» (Запорожье, 11−13 октября 2012 г.).
Кроме того, результаты обсуждались на научных семинарах кафедры математической кибернетики факультета ВМК МГУ.
Публикации. По теме диссертации опубликовано 11 работ [42]-[52], в том числе две работы [46, 49] в рецензируемых изданиях, включенных в перечень ВАК РФ. Все работы опубликованы без соавторов.
Структура и объем работы. Диссертация состоит из введения, трех глав, за которыми следуют пять приложений и список литературы, содержащий 52 наименования, включая публикации диссертанта. Общий объем работы — 162 страницы.
Заключение
.
Подведем итог проведенным исследованиям. В диссертационной работе получены следующие основные результаты:
• доказаны 48 утверждений и следствий из них, представляющих собой универсальные (справедливые для всех к ^ 2) свойства пересечений и объединений предполных классов /с-значной логики;
• в трехзначной логике: построена решетка всех 1505 основных замкнутых классовполучены все 406 вариантов распределения функций по предполным классамнайдены все 3602 тупиковые аксиомы вложения, среди которых выделены все 58 ядровых и все 319 регулярных аксиом. Указана также одна из базисных систем аксиом;
• в четырехзначной логике построены фрагменты решетки всех основных замкнутых классов для пересечений предполных классов из семейств М и и.
Решетка основных замкнутых классов в Рз, полученная в данной работе, может служить отправной точкой в различных задачах классификации замкнутых множеств функций трехзначной логики. Варианты распределения трехзначных функций по предполным классам могут быть использованы во всевозможных задачах индивидуальной классификации. Методы решения задач классификации с помощью аксиом, очевидно, могут применяться и давать результаты не только в трехзначной логике, но и в /с-значной — для небольших значений к и для произвольных значений к, а также в случае исследования других функциональных систем, замкнутых относительно некоторого оператора (не обязательно оператора суперпозиции).
Решение задачи индивидуальной классификации четырехзначных функций на основе &bdquo-аксиоматического" подхода и опираясь на вычислительные возможности современных суперкомпьютеров, представляется вполне реальным уже в самой ближайшей перспективе.
Наконец, отметим, что универсальные свойства пересечений и объединений предполных классов £—значной логики (см. первую главу диссертации), в сочетании с методами комбинаторного анализа, возможно, помогут дать ответ на ряд открытых вопросов в в теории функций многозначной логики, в частности, помогут получить оценки для максимальной мощности базиса в .
Автор выражает благодарность А. А. Вороненко и С. С. Марченкову за постоянное внимание к работе.
