О пересечениях и объединениях предполных классов многозначной логики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики

Нагорный Александр Степанович

О ПЕРЕСЕЧЕНИЯХ И ОБЪЕДИНЕНИЯХ ПРЕДПОЛНЫХ КЛАССОВ МНОГОЗНАЧНОЙ ЛОГИКИ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи

Москва - 2013

005060082

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Научные руководители: доктор физико-математических наук

профессор Вороненко Андрей Анатольевич

Официальные оппоненты: доктор физико-математических наук

профессор Дьяконов Александр Геннадьевич

Защита диссертации состоится 7 июня 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. (495) 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru.

Автореферат разослан « (о » мая 2013 г. Ученый секретарь

диссертационного совета В.А. Костенко

доктор физико-математических наук профессор Марченков Сергей Серафимович

кандидат физико-математических наук доцент Дайняк Александр Борисович

Ведущая организация: Московский энергетический институт

(Национальный исследовательский университет)

к.т.н., ведущий научный сотрудник

Общая характеристика работы

Актуальность темы. Функции многозначной логики — один из основных модельных объектов дискретной математики, широко используемых для описания разнообразных дискретных систем. Интерес к функциям многозначной логики обусловлен как достаточно широкими выразительными возможностями данных функций, так и возможностью применять к функциям комбинаторно-логические приемы и методы различного рода. В частности, эти методы позволяют получать многочисленные разложения и представления функций через „элементарные" функции.

Современная проблематика теории функций многозначной логики весьма разнообразна. Здесь ставятся и решаются задачи метрического, перечислительного, композиционного, сложностного, классификационного и ряда других типов. Особое место в этом ряду занимают задачи классификационного характера. В самом деле, прежде чем проводить систематическое исследование множества функций многозначной логики, необходимо провести хотя бы приблизительное структурирование (классифицирование) этого множества, разбить его на подмножества (классы), которые отвечали бы свойствам, характерным для выбранного направления исследований.

Среди различных подходов к классифицированию множества функций многозначной логики исторически первым явился подход, основанный на термальной (формульной) выразимости функций. Этот подход содержался в пионерских работах Э. Поста [21, 22], в которых была построена полная классификация множества булевых функций. Сейчас этот подход связывают с операторами замыкания на множестве функций многозначной логики (у Поста — оператор суперпозиции) и классификациями, состоящими из замкнутых (относительно выбранного оператора замыкания) классов.

Классификации множеств Рк функций £-значной логики, основанные на операторе суперпозиции, являются самыми известными и самыми изученными. Однако, в отличие от случая булевых функций, при любом к ^ 3 соответствующая классификация множества Рк оказывается континуальной [15]. Здесь трудно ожидать таких исчерпывающих результатов, которые получены Э. Постом для множества Р%. Поэтому исследованию подвергаются наиболее значимые фрагменты решетки (по вложению) замкнутых классов в Рк'. максимальные элементы решетки (предполные в Рк классы), субмаксимальные элементы, атомы решетки, начальные сегменты и интервалы решетки, определяемые хорошо изученными классами, и т.д.

Пусть Ьк обозначает решетку замкнутых классов в Рк-

Случай к = 3 вызывал и вызывает наибольший интерес у исследователей, поскольку это наименьшее значение к, при котором Lk имеет континуальную мощность. В качестве примера укажем, что для решетки Ьз

• все 18 максимальных элементов были найдены C.B. Яблонским [13],

• все 169 субмаксимальных элементов были найдены Д. Лау [19],

• все 84 минимальных элемента были построены Б. Чаканем [16],

• все элементы решетки Ьз, содержащие множество всех трехзначных функций одной переменной, описаны Г. А. Бурле [4],

• все 144 дискриминаторных класса в Рз были получены С.С. Марчен-ковым [И],

• все замкнутые классы линейных функций в Рк при любом простом к (и, в частности, в Рз) были описаны Я. Деметровичем и Я. Бадь-инским [17], однако в этом направлении имеется гораздо более общий результат: в Рз существует лишь конечное число замкнутых классов, содержащих существенную линейную функцию; все эти классы фактически описаны в работе С.С. Марченкова [10].

К строению решетки Ьз также имеют отношение работы [2, 12, 6, 3, 5]. Особо отметим относительно недавно появившуюся монографию [20], в которой можно найти подробное изложение целого ряда новейших результатов о строении решетки L3, а также некоторых фрагментов решетки L& для произвольных значений

Самыми важными в вопросах классификации (а также в вопросах полноты) представляются максимальные (предполные) классы. Согласно хорошо известной теореме A.B. Кузнецова [7], при любом к > 2 число предполных классов в Рк конечно.

Как уже говорилось выше, все предполные классы в Рг были описаны Э. Постом, отдельные семейства предполных классов в Рк при к ^ 3 были найдены C.B. Яблонским [13, 14], Полное описание предполных классов в Рк (в терминах сохранения некоторых предикатов) было получено И. Ро-зенбергом [23, 24].

Нам понадобятся несколько определений.

Множество всех функций из Рк от п переменных обозначим через Р£. Говорят, что функция f & Р^ сохраняет предикат р{хi,x2,... ,хт), если

iu^DbetM Щ &Â Марты№*СРМР],/\О [sj

uJfofUMU UCCAêdoëai&WMU- 0

для любых п наборов

(ац,.. .,атi),..., (ain,... удовлетворяющих предикату р, набор

(/(оц, • • • ,ain)i • • • ./(«ml, • ■ •

также удовлетворяет предикату р.

Для любого предиката р множество всех функций, сохраняющих предикат р, является замкнутым классом [1]. Отметим также, что из теоремы Розенберга [23, 24] следует, что при любом к > 2 все предполные классы fc-значной логики являются предикатно описуемыми. В настоящее время, следуя И. Розенбергу, принято разбивать все предполные классы (и соответствующие предикаты) на шесть семейств:

• классы функций, монотонных относительно частичных порядков с наименьшим и наибольшим элементами - классы семейства М,

• классы функций, сохраняющих нетривиальные разбиения множества Ек = {0,1,..., к — 1} - классы семейства U,

• классы функций, сохраняющих центральные предикаты - классы семейства С,

• классы функций, сохраняющих сильно гомоморфные прообразы fr-адических элементарных отношений - классы семейства В.

• классы самодвойственных функций - классы семейства S,

• и классы квазилинейных функций - классы семейства L.

Нам будет удобно выделить в семействе С подсемейство Т классов функций, сохраняющих одноместные центральные предикаты.

Ввиду теоремы A.B. Кузнецова [7] о функциональной полноте всякий замкнутый класс из Рк, отличный от Рк, целиком содержится хотя бы в одном из предполных в Рк классов. Отсюда вытекает, в частности, что определяющие свойства предполных классов — предикаты, задающие предполные классы, — присутствуют во всех остальных замкнутых классах. Этот факт следует также из теории Галуа для алгебр Поста [1, 18], согласно которой любой замкнутый класс можно задать подходящим множеством предикатов (может быть, бесконечным), среди которых обязательно присутствует хотя бы один из предикатов, задающих предполный класс.

Данные результаты, лежащие в основе теории функций многозначной логики, естественным образом приводят к постановке следующей задачи: каковы все те замкнутые классы в Рк, которые определяются только предикатами, задающими предполные в Рк классы? Иными словами, каковы все те замкнутые классы в Рк, которые представляют собой пересечения предполных в Рк классов?

Данные замкнутые классы, которые мы будем назвать основными замкнутыми классами, образуют,каркас" решетки замкнутых классов в Рк, поскольку они определяются только „основными свойствами" класса Рк — свойствами, присутствующими во всех остальных замкнутых классах и отвечающими за решение проблемы полноты в классе Рк.

Таким образом, решение проблемы функциональной полноты в Рк имеет в качестве логического продолжения перечисление и исследование основных замкнутых классов в Рк. В свою очередь, решение этих новых задач открывает возможности для построения обозримых классификаций центральной" части множества Рк, а также позволяет получить ответы на ряд вопросов, связанных с базисами в классе Рк ■

Очевидно, что количество основных замкнутых классов (при фиксированном к) конечно. При к — 2 (случай булевых функций) имеется ровно 5 предполных классов и ровно 14 различных пересечений предполных классов. При к = 3 число предполных классов равно 18, а число различных пересечений предполных классов теоретически может быть близко к 218. Понятно, что даже при небольших значениях к решение задачи построения всех основных замкнутых классов в Рк наталкивается на значительные трудности переборного характера. Вместе с тем анализ случаев к — 2,3 показывает, что одни и те же основные замкнутые классы могут получаться в результате пересечения предполных классов из довольно большого числа наборов таких классов. Возникает задача минимизирования перебора при перечислении основных замкнутых классов. В данной диссертации автором разработан путь решения этой задачи — построение „аксиом вложения", которые имеют вид

Кц П К!а П ... П Ки СКьиКьи...и К], (#)

и тем самым устанавливают связь (включение) пересечений некоторых предполных классов АГ,т и объединений некоторых (других) предполных классов К]п.

Помимо классификации множеств функций, замкнутых относительно операции суперпозиции, определенный интерес представляет задача „ин-

дивидуальной классификации" функций £-значной логики, т.е. задача получения множества F(fc) всех возможных распределений таких функций по предполным в Р^ классам (т.н. характеристических строк функций). Для решения этой задачи достаточно предварительно найти все основные замкнутые классы в Рк, а затем для каждого основного класса либо построить пример £-значной функции, лежащей в тех и только в тех пред-полных классах, которые задают этот основной класс, либо предложить (и обосновать) новую аксиому вложения, из которой бы вытекало, что такого примера функции не существует (и, следовательно, данный основной класс не имеет базиса из одной функции).

Наконец, для решения ряда задач (в частности, для ответа на вопрос, существует ли функция с заданным распределением по предполным классам) полезно иметь множество всех тупиковых (т.е. неупрощаемых) аксиом вложения, а еще лучше — иметь его некоторое базисное подмножество (т.е. минимальное множество аксиом вложения, их которого логически выводятся все остальные аксиомы вложения). В этом случае вместо того, чтобы вести поиск нужной строки в множестве Р(к), мы можем просто проверить, удовлетворяет ли данное распределение по предполным классам всем аксиомам из базисного множества аксиом.

Цель работы. Диссертационная работа преследует следующие цели:

• изучить структуру замкнутых (относительно операции суперпозиции) классов функций многозначной логики на предмет получения некоторых универсальных (справедливых для всех к ^ 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 работ [25]—[35], в том числе две работы [29, 32] в рецензируемых изданиях, включенных в перечень ВАК РФ. Все работы опубликованы без соавторов.

Структура и объем работы. Диссертация состоит из введения, трех глав, за которыми следуют пять приложений и список литературы, содержащий 52 наименования, включая публикации диссертанта. Общий объем работы составляет 162 страницы.

Краткое содержание работы

Введение содержит краткие сведения по истории вопроса и обоснование актуальности темы исследования. В нем также сформулирована цель диссертации, описана структура диссертации и перечислены основные полученные результаты.

Первая глава диссертации посвящена исследованию пересечений и объединений предполных классов fc-значной логики для произвольного к ^ 2 и является самой объемной. В первом параграфе приводятся основные определения и обозначения, используемые в диссертационной работе. В частности, в нем приводится предикатное описание всех шести семейств предполных классов fc-значной логики.

Аксиому вложения вида (*) назовем тупиковой, если после удаления любого Kim из левой части или Kjn из правой части она перестает быть аксиомой (т.е. соответствующее вложение становится ложным). Из конечности числа предполных в Рк классов (при любом заданном fc > 2) следует конечность множества всех тупиковых аксиом вложения в Рк ■ Две аксиомы вложения вида (*) назовем двойственными, если найдется такая перестановка 7Г на Ек, которая переводит одну аксиому вложения в другую.

Подмножество А множества всех тупиковых аксиом вложения назовем полной системой аксиом, если все остальные аксиомы вложения логически следуют из аксиом этого подмножества, и неприводимой системой аксиом,

если никакая аксиома из А логически не следует из всех остальных аксиом из А. Неприводимую полную систему аксиом вложения будем называть базисной системой аксиом.

Тупиковую аксиому вложения вида (*) назовем ядровой, если она логически не следует из всех остальных аксиом вложения, т.е. система всех остальных тупиковых аксиом вложения не является полной. Очевидно, все ядровые аксиомы содержатся в любой базисной системе аксиом вложения.

Если, наоборот, ни одна базисная система аксиом не содержит некоторую тупиковую аксиому вложения, то такую аксиому назовем регулярной.

Во втором параграфе вводится еще несколько дополнительных понятий и доказывается ряд вспомогательных утверждений (оформленных в виде И лемм и трех следствий из них) о некоторых свойствах ограниченных частичных порядков и об условиях, накладывающих ограничения на множество значений /с-значной функции на подмножествах множества

Пусть Im{f) есть множество значений функции / € Рк на множестве Ек, К = Рк \ К для любого К С Рк и Сд есть минимальный по числу наборов двухместный центральный предикат с центром Д.

Следующая лемма играет важную роль.

Лемма 1.9. Пусть к ^ 3, s ^ 2 и для каждого i = 1,2,..., s подмножество Ai множества Ek удовлетворяет условию 1 ^ [Д*| < к — 2.

S _

Для того чтобы для любой функции / б П Сд( выполнялось Im{f) = Ek,

<=i

необходимо и достаточно, чтобы нашлось подмножество {Д^Д^-чД.,} множества {Ai, Д2,..., Д5} такое, что

U (Ek \ Д ij = Ek и при всех j = 1,2,..., t справедливо |Дг-.| — к- 2.

3=1

В третьем параграфе для произвольного к ^ 2 мы формулируем и доказываем, опираясь на факты и леммы из предыдущего параграфа, ряд универсальных свойств предполных классов fc-значной логики (28 утверждений и восемь следствий из них). Ббльшая часть этих свойств представляет собой некоторые аксиомы вида (*).

Для произвольного 0 ф Е С Ек обозначим через Те множество функций из Рк, сохраняющих множество Е.

Утверждение 1.16. Пусть к ^ 3. Для любых непустых множеств Д и Е, удовлетворяющих условиям АПЕ = 0 и АиЕ с Ек, справедливо вложение Сд П Те С Тдив-

Для произвольного нетривиального разбиения £> = {^,¿2, ■ • • ,£«} множества Ек обозначим через класс всех /с-значных функций, сохраняющих разбиение Б.

Утверждение 1.18. Пусть к ^ 3. Тогда для любого нетривиального разбиения Б — {Г, Д, Е} множества Ек выполнено

Мг,хе П Сд П Тге £ ¡^г,дие П С/риД,я-Здесь Мг,а,е обозначает произвольный класс функций, монотонных относительно любого линейного порядка на Ек, согласно которому 7 -< 6 -< е при всех 7 6 Г, 5 6 Д, е е Е.

Пусть В — класс Слупецкого (класс всех функций из Рк, которые имеют не более одной существенной переменной или принимают менее к значений).

Утверждение 1.26. Пусть к ^ 3, Ь ^ 2 и пусть множества

г

Дх, Дг,..., ДьЯ Ек таковы, что и (£*\Д*) = Ек и при всех г — 1,2,..., Ь

«=1

справедливо |Д;| = к — 2. Тогда

Сх.2.....^ПВС (и^ иТо,*-х.

Отдельный, четвертый параграф первой главы посвящен исследованию некоторых предполных классов монотонных /с-значных функций, а именно классов функций, монотонных относительно линейных порядков на Ек (подсемейство Мк), и классов функций, монотонных относительно частичных порядков на Ек, имеющих наименьший и наибольший элементы, и таких, что остальные элементы в них попарно несравнимы (подсемейство Мк). Здесь формулируются и доказываются восемь теорем о том, в каких случаях пересечение таких классов минимально (т.е. содержит лишь константы из Ек и селекторные функции) и в каких случаях все функции в этом пересечении монотонны относительно некоторого линейного порядка на множестве Ек ■

Приведем формулировки двух утверждений из этого параграфа:

Утверждение 1.34. При всех к > 6 а) при 2 ^ р < для любых классов К\, К2,..., Кр е М* верно

и

кем*

Ь) при р> найдутся классы КЪК2, ...,Кр£Мк такие, что

П^с п К

з-1 кем*

Утверждение 1.35. При всех к ^ 6

a) в случае 2 < р < существуют р попарно различных классов

v

К и К2,...,Кр€Мк таких, что П 2 и К;

з=1 кем1

b) в случае (^г*) + 1 ^ V ^ (*) ^ любых р попарно различных классов

р ___

К\, К2, ...,Кре Мк выполняется р| Kj С р) К.

3=1 кем*

Данные результаты могут быть использованы для оптимизации алгоритмов поиска указанных выше пересечений классов &-значных функций для фиксированных значений к, а также для получения нижних и верхних оценок для числа попарно различных пересечений (такого вида) классов й-значных функций при растущем к.

Также отметим, что утверждения 1.34 и 1.35 являются примерами „пороговых" свойств предполных классов /с-значной логики — при увеличении количества р пересекаемых классов всего на единицу свойства результата резко изменяются.

В пятом параграфе речь идет о решетке основных замкнутых классов в й-значной логике и об одном из методов ее построения.

Наконец, в шестом параграфе первой главы для произвольного к ^ 2 подробно описаны три алгоритма:

— алгоритм построения множества Р(к) всех попарно различных характеристических строк для &-значных функций;

— алгоритм поиска всех тупиковых аксиом вложения в &-значной логике;

— алгоритм поиска всех (в том числе минимальных) базисных систем аксиом вложения в /г-значной логике.

Первый параграф второй главы носит иллюстративный характер и решает проблемы построения решетки основных замкнутых классов, получения множества возможных распределений функций по предполным классам и поиска всех базисных систем аксиом вложения для двузначного случая.

Его основные результаты помещены в формулировку теоремы 2.1 и в приложение А и фактически являются следствиями известных результатов Э. Поста [21, 22].

Второй параграф начинается с предикатного описания всех 18 пред-полных классов трехзначной логики. Далее доказывается утверждение 2.2, содержащее 30 свойств — аксиом вложения пересечений предпол-ных классов трехзначной логики в некоторый другой предполный класс. Все указанные аксиомы являются тупиковыми, причем ббльшая часть из них является прямым следствием утверждений, доказанных в первой главе. Остальные свойства являются специфическими для предполных классов именно трехзначной логики, поэтому доказываются отдельно. Отметим, что при доказательстве активно используется распределение одноместных функций из Р3 по предполным классам, полученное C.B. Яблонским [14].

Опираясь на доказанные в утверждении 2.2 свойства, с помощью компьютерной программы мы получили множество всех основных замкнутых классов трехзначной логики (теорема 2.2 и приложение В).

В третьем параграфе доказывается утверждение 2.3, состоящее из 11 аксиом вложения некоторых предполных классов трехзначной логики или их пересечений в объединение двух или более (других) предполных классов. Эти аксиомы, вместе с аксиомами из утверждения 2.2, позволяют найти все варианты распределения трехзначных функций по предполным классам (теорема 2.3), а также решить некоторые задачи, связанные с базисами в (замечание 2.1).

Четвертый параграф открывается теоремой 2.4, дающей список всех тупиковых аксиом вложения в трехзначной логике (таблица D.1). В этой таблице таблице также выделены все ядровые и все регулярные аксиомы.

В конце параграфа приводится пример базисной системы из 123 аксиом вложения (теорема 2.5), почти все аксиомы которой (116 из 123) состоят из трех или четырех классов.

Данная базисная система аксиом позволяет ответить на вопрос, существует ли трехзначная функция с заданным распределением по предполным классам, проверив справедливость всех аксиом системы, что значительно проще, чем вести поиск характеристического вектора данной функции в множестве F(3), состоящем из 406 строк длины 18.

Третья глава посвящена исследованию пересечений и объединений предполных в Р4 классов и изучению связей между ними.

В начале первого параграфа приводится описание всех 82 предпол-ных классов функций четырехзначной логики с помощью предикатов. Затем формулируются вспомогательные факты 4 и 5, имеющие дело с четырехзначными функциями, выпускающими одно или два значения.

Основным результатом параграфа является теорема 3.1, в формулировке которой фигурируют 83 свойства, из которых „раскрытием скобок" можно получить более трех тысяч тупиковых аксиом вложения в четырехзначной логике. Все они суть следствия универсальных свойств, доказанных в первой главе диссертации.

Еще большее число аксиом вложения получено автором с помощью компьютерных программ. В частности, найдены все пересечения предполных классов, содержащих все константы из Ек, в некоторый класс из семейства М или из семейства и. Некоторые из них перечислены во втором и в третьем параграфе, соответственно.

Данные результаты позволили построить некоторые обозримые фрагменты решетки Ь\ основных замкнутых классов в Р4 (теоремы 3.3 и 3.4 из второго параграфа и теоремы 3.6-3.8 из третьего параграфа), которая в этом случае содержит конечное, но очень большое число вершин.

Второй и третий параграфы третьей главы имеют также по одному техническому утверждению, посвященному перечислению всех неприводимых (т.е. неупрощаемых) пересечений предполных классов из семейства М (теорема 3.2) и из семейства и (теорема 3.5), содержащих только все константы из £4 и все селекторные функции (такие пересечения мы называем тривиальными). Список неприводимых тривиальных пересечений крайне полезен при поиске (в частности, при компьютерном поиске) тупиковых аксиом, поскольку он позволяет существенно уменьшить количество логических слагаемых при раскрытии скобок в КНФ функции покрытия.

В последнем, четвертом параграфе третьей главы указаны точные значения количеств неприводимых тривиальных пересечений, состоящих из тг классов (п = 2,3,..., 8), для всех предполных в Р4 классов, содержащих все константы (таблица 7).

Завершает диссертацию заключение, в котором подводится итог проведенным исследованиям и формулируются возможности приложений полученных результатов, а также высказываются мысли о дальнейшем развитии идей и методов, предложенных автором.

Диссертационная работа содержит пять приложений. Приложение А содержит диаграмму Хассе решетки основных замкнутых классов алгебры

логики. В приложении В перечислены элементы полурешетки пересечений в Рз, вместе с примерами множеств функций, задающих эти элементы. Приложение С содержит примеры функций для строк множества F(3) (теорема 2.3). В приложении D перечислены все тупиковые попарно не двойственные аксиомы вложения в Р$. В соответствующей таблице для каждой такой аксиомы указано количество двойственных аксиом, а также выделено множество ядровых и регулярных аксиом вложения. Наконец, приложение Е содержит 6 диаграмм Хассе для различных фрагментов решетки L\ основных замкнутых классов в Р4 (теоремы 3.3, 3.4, 3.6-3.8).

СПИСОК ЛИТЕРАТУРЫ

1. Боднарчук В. Г., Калужнин В. А., Котов В. Н., Ромов Б. А. Теория Га-луа для алгебр Поста I-II// Кибернетика. 1969. № 3. С. 1-10, № 5. С. 1-9.

2. Булатов А. А. Конечные подрешетки в решетке клонов // Алгебра и логика. 1994. Т. 33, № 5. С. 514-549.

3. Булатов А. А. Подрешетки решетки клонов функций на трехэлементном множестве, I // Алгебра и логика. 1999. Т. 38, № 1. С. 3-23; II, там же. 1999. Т. 38, № 3. С. 269-295.

4. Бурле Г. А. Классы fc-значных логик, содержащие все функции одной переменной // Дискретный анализ. 1967. JV» 10. С. 3-7.

5. Жук Д. Н. Решетка замкнутых классов самодвойственных функций трехзначной логики // М.: Издательство Московского университета. 2011. 109 с.

6. Крохин А. А. Моноидальные интервалы в решетках клонов // Алгебра и логика. 1995. Т. 34, № 5. С. 288-310.

7. Кузнецов A.B. О проблемах тождества и функциональной полноты для алгебраических систем // Труды 3-го Всесоюзного матем. съезда. Т. 2. М.: Изд-во АН СССР. 1956. С. 145-146.

8. Ло Чжу-Кай Предполные классы, определяемые fc-арными отношениями в fc-значной логике - Asta Sei. natur. Univ. Jilinesis, N 3. 1964.

9. Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках // Проблемы кибернетики. 1960. 3. С. 49-60.

10. Марченков С. С. О замкнутых классах в Р*, содержащих однородные функции // Препринт ИПМ АН СССР. 1984. № 35. С. 1-28.

11. Марченков С. С. Дискриминаторные классы трехзначной логики // Матем. вопросы кибернетики. Вып. 12. М.: Наука. 2003. С. 15-26.

12. Сафин К. Jl. Идеалы итеративных алгебр // Сибир. матем. журнал. 1995. Т. 36, № 6. С. 1384-1391.

13. Яблонский С. В. О функциональной полноте в трехзначном исчислении // ДАН СССР. 1954. 95. № 6. С. 1153-1156.

14. Яблонский С. В. Функциональные построения в fc-значной логике // Тр. МИАН СССР им. В. А. Стеклова. 1958. 51. С. 5-142.

15. Янов Ю.И., Мучник A.A. О существовании fc-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР. 1959. 127. № 1. С. 44-46.

16. Csäkäny В. AU minimal clones on three-element set // Acta Cybernet. 1983. V. 6, N. 3. P. 227-238.

17. Demetrovics J., Bagynski J. The lattice of linear classes in prime-valued logics // Discrete Mathematics. Banach Center Publications. Warsaw, 1982. V. 7. P. 105-123.

18. Geiger D. Closed systems of functions and predicates // Pacific journal of mathematics. 1968. V. 27. N. 1. P. 95—100.

19. Lau D. Submaximalle Klassen von Рз // Electron. Informationsverarb. und Kybemet. 1982. В. 18, N. 4-5. S. 227-243.

20. Lau D. Function Algebras on Finite Sets. A Basic Course on Many-Valued Logic and Clone Theory // Springer-Verlag Berlin Heidelberg. 2006. 670 p.

21. Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43. N. 4. P. 163-185.

22. Post E. L. Two-valued iterative systems of mathematical logic. N. J.: Princeton Univ. Press, 1941.

23. Rosenberg I. G. La structure des fonctions de plusieurs variables sur un ensemble fini // C.R. Acad. Sei. Paris. Ser. A.B. 1965. 260. P. 38173819.

24. Rosenberg I. G. Über die funktionale Vollständigkeit in den mehrwertigen Logiken // Rozpravy Ceskoslovenske Akad. Vöd. N. 80. Praha: Rada Math. Prir. Ved., 1970. P. 3-93.

Публикации автора по теме диссертации

25. Нагорный A.C. О мощности базисов трехзначной логики // Научная конференция „Тихоновские чтения 2010", тезисы докладов (Москва, 2529 октября 2010 г.). М.: Изд-во МАКС Пресс, 2010, С. 9.

26. Нагорный А. С. О свойствах предполных классов в трехзначной логике //XI Межвузовский научно-практический семинар „Комбинаторные конфигурации и их применения" (Кировоград, 15-16 апреля 2011 г.), Материалы. Кировоград: Изд-во Кировоградского национального технического университета, 2011, С. 117-122.

27. Нагорный А. С. О свойствах теоретико-множественных операций над предполными классами трехзначной логики // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.). Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. С. 336-340.

28. Нагорный А. С. О критериальной таблице в Р3 // Научная конференция „Ломоносовские чтения", тезисы докладов (Москва, 14-23 ноября 2011 г.). М.: Изд-во МАКС Пресс, 2011, С. 27-29.

29. Нагорный A.C. О свойствах предполных классов в Р3 // Известия высших учебных заведений. Поволжский регион. Физ.-мат. науки. Пенза: Изд-во Пензенского государственного университета, 2012, №2 (22), С. 16-24.

30. Нагорный А. С. О функциях четырехзначной логики, монотонных относительно линейных порядков // Материалы XIII Межвузовского научно-практического семинара „Комбинаторные конфигурации и их применения", (Кировоград, 13-14 апреля 2012 г.). Кировоград: Изд-во Кировоградского национального технического университета, С. 107109.

31. Нагорный A.C. О пересечениях классов монотонных функций многозначной логики // XI международный семинар „Дискретная математика и ее приложения", (Москва, 18-23 июня 2012 г.). М.: Изд-во механико-математического ф-та МГУ, С. 207-209.

32. Нагорный А. С. О распределении трехзначных функций по предпол-ным классам // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2012. № 3, С. 45-52.

33. Нагорный А. С. О некоторых пересечениях предполных классов многозначной логики, вложенных в классы Со и Сод.....к-з // Материалы

Международного научного семинара „Дискретная математика и ее применение в экономико-математическом моделировании и информационных технологиях" (Запорожье, 11-13 октября 2012 г.). С. 51-52;

34. Нагорный А. С. О некоторых пересечениях предполных классов многозначной логики // Научная конференция „Тихоновские чтения", тезисы докладов (Москва, 29-31 октября 2012 г.). М.: Изд-во МАКС Пресс, С. 46-47.

35. Нагорный A.C. О линейной монотонности некоторых пересечений предполных классов многозначной логики // Материалы XV Международного научно-практического семинара „Комбинаторные конфигурации и их применения", (Кировоград, 12-13 апреля 2013 г.). Кировоград: ПП „Ексклюзив-Систем", С. 75-78.

Напечатано с готового оригинал-макета

Подписано в печать 30.04.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 80 экз. Заказ 126.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

На правах рукописи

04201357780 УДК 519.716.5

НАГОРНЫЙ АЛЕКСАНДР СТЕПАНОВИЧ

О ПЕРЕСЕЧЕНИЯХ И ОБЪЕДИНЕНИЯХ ПРЕДПОЛНЫХ КЛАССОВ МНОГОЗНАЧНОЙ ЛОГИКИ

Специальность 01.01.09 - дискретная математика и математическая кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научные руководители: доктор физ.-мат. наук профессор А.А.Вороненко, доктор физ.-мат. наук профессор С.С.Марченков

МОСКВА - 2013

Содержание

Введение 4

1 Некоторые свойства предполных классов многозначной логики 20

1.1 Основные понятия ...................................................21

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

1.3 Утверждения о пересечениях и объединениях предполных классов 39

1.4 Свойства пересечений предполных классов монотонных функций . .57

1.5 Полурешетка пересечений предполных классов .....................79

1.6 Системы аксиом вложения ..........................................80

2 Построение решетки основных замкнутых классов

в трехзначной логике 84

2.1 Свойства предполных классов двузначной логики ..................85

2.2 Полурешетка пересечений предполных классов в ?з ...............90

2.3 Распределение трехзначных функций по предполным классам .....97

2.4 Множество всех тупиковых аксиом вложения в Рз ................101

3 Некоторые свойства предполных классов четырехзначной логики 104

3.1 Следствия из универсальных свойств ..............................108

3.2 Фрагменты решетки Ь\ для классов монотонных функций .......112

3.3 Фрагменты решетки Ь\ для классов функций, сохраняющих разбиения ..........................................................121

3.4 О количестве неприводимых тривиальных пересечений ...........126

Заключение 128

Приложение А. Решетка основных замкнутых классов алгебры

логики .................................................130

Приложение В. Элементы полурешетки пересечений в .............131

Приложение С. Примеры функций для строк множества -Р(З) ........141

Приложение О. Аксиомы вложения в трехзначной логике.............144

Приложение Е. Фрагменты решетки основных замкнутых классов в 154 Список литературы 158

Введение

Актуальность проблемы. Функции многозначной логики — один из основных модельных объектов дискретной математики, широко используемых для описания разнообразных дискретных систем. Интерес к функциям многозначной логики обусловлен как достаточно широкими выразительными возможностями данных функций, так и возможностью применять к функциям комбинаторно-логические приемы и методы различного рода. В частности, эти методы позволяют получать многочисленные разложения и представления функций через „элементарные" функции.

Современная проблематика теории функций многозначной логики весьма разнообразна. Здесь ставятся и решаются задачи метрического, перечислительного, композиционного, сложностного, классификационного и ряда других типов. Особое место в этом ряду занимают задачи классификационного характера. В самом деле, прежде чем проводить систематическое исследование множества функций многозначной логики, необходимо провести хотя бы приблизительное структурирование (классифицирование) этого множества, разбить его на подмножества (классы), которые отвечали бы свойствам, характерным для выбранного направления исследований.

Среди различных подходов к классифицированию множества функций многозначной логики исторически первым явился подход, основанный на термальной (формульной) выразимости функций. Этот подход содержался в пионерских работах Э. Поста [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) относительно некоторого „сильного" оператора замыкания. Так, довольно проработанной является 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], согласно которой любой замкнутый класс можно задать подходящим множеством предикатов

(может быть, бесконечным), среди которых обязательно присутствует хотя бы один из предикатов, задающих предполный класс.

Данные результаты, лежащие в основе теории функций многозначной логики, естественным образом приводят к постановке следующей задачи: каковы все те замкнутые классы в Рк, которые определяются только предикатами, задающими предполные в классы? Иными словами, каковы все те замкнутые классы в Р^, которые представляют собой пересечения предпол-ных в Рк классов?

Данные замкнутые классы, которые мы будем назвать основными замкнутыми классами, образуют „каркас" решетки замкнутых классов в поскольку они определяются только „основными свойствами" класса Р\ — свойствами, присутствующими во всех остальных замкнутых классах и отвечающими за решение проблемы полноты в классе .

Таким образом, решение проблемы функциональной полноты в Р^ имеет в качестве логического продолжения перечисление и исследование основных замкнутых классов в Д. В свою очередь, решение этих новых задач открывает возможности для построения обозримых классификаций „центральной" части множества Р^, а также позволяет получить ответы на ряд вопросов, связанных с базисами в классе Р^.

Очевидно, что количество основных замкнутых классов (при фиксированном к) конечно. При к = 2 (случай булевых функций) имеется ровно 5 предполных классов и ровно 14 различных пересечений предполных классов. При к = 3 число предполных классов равно 18, а число различных пересечений предполных классов теоретически может быть близко к 218. Понятно, что даже при небольших значениях к решение задачи построения всех основных замкнутых классов в Р^ наталкивается на значительные трудности переборного характера. Вместе с тем анализ случаев к — 2.3 показывает, что одни и те же основные замкнутые классы могут получаться в результате пересечения предполных классов из довольно большого числа наборов таких

классов. Возникает задача минимизирования перебора при перечислении основных замкнутых классов. В данной диссертации автором разработан путь решения этой задачи — построение „аксиом вложения", которые имеют вид

и тем самым устанавливают связь (включение) пересечений некоторых пред-полных классов и объединений некоторых (других) предполных классов.

Фактически, каждая аксиома вида (*) означает, что всякий основной класс, полностью содержащийся в каждом из предполных классов К^, К¿2, ..., К{з, должен также содержаться и в объединении предполных классов Кп' > ■ ■ • > К31 ■ Данное обстоятельство и приводит к сокращению перебора.

Помимо классификации множеств функций, замкнутых относительно операции суперпозиции, определенный интерес представляет задача „индивидуальной классификации" функций /с-значной логики, т.е. задача получения множества Р{к) всех возможных распределений таких функций по предпол-ным в Р/г классам. Для решения этой задачи достаточно предварительно найти все основные замкнутые классы в Р^, а затем для каждого основного класса либо построить пример /с-значной функции, лежащей в тех и только в тех предполных классах, которые задают этот основной класс, либо предложить (и обосновать) новую аксиому вложения, из которой бы следовало, что такого примера функции не существует (и, следовательно, данный основной класс не имеет базиса из одной функции).

Наконец, для решения ряда задач (в частности, для ответа на вопрос, существует ли функция с заданным распределением по предполным классам) полезно иметь множество всех тупиковых (т.е. неупрощаемых) аксиом вложения, а еще лучше — иметь его некоторое базисное подмножество (т.е. минимальное множество аксиом вложения, их которого логически выводятся все остальные аксиомы вложения). В этом случае вместо того, чтобы вести поиск нужной строки в множестве (заметим, что это множество может

быть слишком большим по мощности, а может быть и вовсе еще не построен-

ным), мы можем просто проверить, удовлетворяет ли данное распределение по предполным классам всем аксиомам из базисного множества аксиом. При этом выигрыш достигается не только за счет того, что в записи каждой аксиомы участвуют далеко не все предполные классы (чаще всего их там от 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] в рецензируемых изданиях, включенных в перечень ВАК РФ. Все работы