Проблемы полноты и выразимости в пространствах дискретных функций тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Парватов, Николай Георгиевич

• Парватов, Николай Георгиевич
• доктор физико-математических наук
• 2011

Оглавление диссертации доктор физико-математических наук Парватов, Николай Георгиевич

Введение

1 Нижние и верхние окрестности

1.1 Нижние окрестности и теорема о финитарности.

1.2 Предупорядоченные пространства.

1.3 Сильно предупорядоченные пространства.

1.4 Примеры сильно предупорядоченных пространств.

1.5 Соответствия и замыкания Галуа.

1.6 Примеры. Соответствия Галуа для функций многозначной логики

1.7 Соответствие Галуа для переключательных функций.

1.8 Итоги первой главы.

2 Клоны с мажоритарной функцией и их обобщения

2.1 И-описания и лемма Б. А. Ромова о доопределении.

2.2 Клоны с мажоритарной функцией.

2.3 Клоны с ¿-подклонами.

2.4 (с, сО-Клоны.

2.5 Предикатная характеризация (с, с?)-клонов.

2.6 (с, г)-Разложения (с, (¿)-клонов.

2.7 Итоги второй главы.

3 Квазимонотонные функции на полурешётке

3.1 Полурешётки и полурешёточные функции

3.2 Основные клоны полурешёточных функций.

3.3 Точечные функции.

3.4 Пример. Дважды монотонные функции.

3.5 Дизъюнктивные формы троичных функций

3.6 Обобщённые дизъюнктивные формы.

3.7 Итоги третьей главы.ИЗ

4 Проблема полноты в слабо центральном клоне

4.1 Предельные предикаты.

4.2 Расширенные и-описания и теорема о выделении.

4.3 Слабо центральные предикаты и клоны.

4.4 Слабо центральные клоны, определяемые системами множеств.

4.5 Теорема о полноте в клоне квазимонотонных функций.

4.6 Мощностные оценки.

4.7 Итоги четвёртой главы

5 Проблемы полноты для трёхзначных квазимонотонных функций

5.1 Теорема о выразимости минимальных точечных функций

5.2 Теорема о полноте в классе монотонных функций.

5.3 Аналог теоремы Слупецкого для квазимонотонных функций

5.4 Теорема о полноте в классе квазимонотонных функций.

5.5 Итоги пятой главы.

Введение диссертации (часть автореферата) на тему «Проблемы полноты и выразимости в пространствах дискретных функций»

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

Начало активному изучению дискретных функций и их пространств положено работами Э. Поста, К. Шеннона, С. В. Яблонского, А. В. Кузнецова, О. Б. Лупанова и других исследователей. К настоящему времени теория дискретных функций получила серьёзное развитие, в результате которого были выделены (и продолжают выделяться) для исследования основные классы функциональных пространств (такие, как клоны, наследственные и инвариантные классы и прочие) и сформированы различные направления исследований. В том числе были сформулированы и стали классическими изучаемые в диссертации проблемы полноты и выразимости, проблемы эффективного задания замкнутых классов и их конечной порождаемости, поиска форм представления функций.

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

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

Проблемы полноты и выразимости решены в ряде случаев. В пространствах булевых функций с замыканием относительно суперпозиции они решены в работе Э. Поста [114]. В пространстве функций к-значной логики проблема полноты решена в работах С. В. Яблонского [57] (при к = 3) и И. Розенберга [117] (при произвольном к), отдельные результаты получены в работах [29,19, 20]. В пространстве частичных функций к-значной логики проблема полноты решена в работах Фрейвалда [53] (при к = 2), Б. А. Ро-мова [46] (при к = 3), Ло Чжукая [26] (при произвольном к) и независимо в [47, 84, 85, 86]. В связи с полурешёточной моделью, предложенной в работах Г. П. Агибалова [3, 5, 65] для описания асинхронных дискретных управляющих систем, возникает необходимость решения указанных проблем в различных классах квазимотонных функций на полурешётках. В диссертации проблемы полноты и выразимости решены в некоторых таких классах, найдены различные условия максимальности подклона в клоне, позволяющие выделять максимальные подконы при решении проблем полноты в различных клонах.

Проблема конечной порождаемости состоит в выявлении условий, при которых заданный класс пространства имеет конечное порождающее множество. Актуальность этой проблемы для клонов связана с результатами Ю. И. Янова и А. А. Мучника [64] о существовании клонов без конечного порождающего множества и с результатами Э. Поста [114] о конечной порождаемости клонов булевых функций. В связи с этим в работах С. С. Мар-ченкова [30], Д. Лау [99], Г. Тардёша [123], Деметровича с соавторами [78] и О. С. Дудаковой [18] были выделены некоторые семейства конечно порождаемых клонов. В диссертации описан ряд новых таких семейств, предложены методы функционального разложения в них.

Более общая проблема эффективного задания связана с разработкой и обоснованием методов эффективного задания замкнутых классов при помощи конечных порождающих множеств в произвольных пространствах, конечных запрещающих множеств в предупорядоченных пространствах, конечных описаний в пространствах с замыканием Галуа и иных. Отметим в связи с этим работы Д. Гейгера [83] и В. Г. Боднарчука с соавторами [8], где построена теория Галуа для клонов, работу С. В. Яблонского [62], где охарактеризованы клоны, задаваемые предикатами и конечными запрещающими множествами; указанные результаты обобщены для клонов многоосновных алгебр Р. Пёше-лем и Л. А. Калужниным [ИЗ], для наследственных систем Н. Пиппенджером [110] и О. Экиным с соавторами [81], для перестановочно замкнутых классов J1. Хеллерстайн [90]. В диссертации получено дальнейшее обобщение этих результатов для 5-замкнутых классов дискретных функций, к числу которых относятся клоны, наследственные классы, а также классы функций, вычисляемых переключательными схемами.

Проблема форм представления связана с созданием методов и нахождением условий для представления дискретных функций формулами в различных базисах и обусловлена, как правило, недостаточностью известных форм представления функций (дизъюнктивными, конъюнктивными и алгебраическими нормальными формами и их Анзначными аналогами) для решения ряда задач. Отметим в связи с этим работы С. С. Марченкова [31, 33] и А. Б.Уголь-никова [52], где исследованы ¿(¿-разложения функций многозначной логики в замкнутых классах, обобщающие разложения булевых функций из работы Г. П. Гаврилова [13]. В диссертации вводятся (с, г)-разложения, близкие при с = 0ис = гк чистым и смешанным ¿¿-разложениям; выделяется семейство клонов, допускающих (с, г)-разложения своих функций; устанавливаются условия представления квазимонотонных функций формулами различного вида.

Пространства сами по себе, а не только их конкретные реализации, являются объектом ряда исследований. Так, в работах Г. Биркгофа и О. Фринка [67] охарактеризованы финитарные пространства, в работах О. Ope [109] и

Ц. Эверетта [80] введены и изучены пространства с замыканием Галуа, а в работе А. В. Кузнецова [24] сформулированы условия существования конечной критериальной системы в пространстве. В развитие этого в диссертации изучаются условия существования конечных нижних окрестностей в различных пространствах (произвольных, предупорядоченных и с замыканием Галуа) у заданных или произвольных конечно порождаемых классов; вводятся и изучаются сильно предупорядоченные пространства, к числу которых, как показывается, принадлежит ряд известных функциональных пространств.

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

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

1. Установлены условия, при которых в различных пространствах заданные или произвольные конечно порождаемые классы имеют конечные нижние окрестности; условия при которых замкнутые классы допускают эффективные в приложениях способы задания — конечными запрещающими множествами в предупорядоченных пространствах и конечными описаниями в пространствах с замыканием Галуа. Введены в рассмотрение сильно преду-порядоченные пространства. Доказано, что в финитарных таких пространствах конечно порождаемые подмножества имеют конечные нижние окрестности, классы которых обладают конечными запрещающими множествами. Установлена сильная предупорядоченность ряда функциональных и логических пространств, в том числе пространства переключательных функций с «^-замыканием. Построена теория Галуа для переключательных функций с 5-замыканием, описывающая его как замыкание Галуа.

2. Исследованы проблемы эффективного задания клонов и их конечной порождаемости. Выделено новое семейство конечно порождаемых клонов — включающих конечно порождаемый А- или произвольный (с, с?)-подклон при натуральном с. Построены примеры и предложены конструкции таких клонов. Клоны с (с, (¿)-подклонами охарактеризованы свойствами инвариантных предикатов. Установлена возможность (с, г)-разложений клона над (с, ^-под-клоном (где с — натуральное или оо), известная ранее лишь при с = 0. Найдены предикатные и-описания ряда клонов, в том числе клонов квазимонотонных и слабо существенных квазимонотонных функций, а также монотонных частей этих клонов. Поставлена задача выделения максимальных клонов в множествах точечных и минимальных точечных функций на полурешётке, построены примеры таких клонов на полурешётке интервалов решётки. Явно описаны классы троичных функций, вычисляемых в каноническом базисе формулами различного вида. Предложен метод формульного представления минимальных точечных функций на дистрибутивной точечной полурешётке в базисах, содержащих все одноместные минимальные точечные функции и некоторый набор специальных двухместных функций.

3. Установлен ряд условий максимальности подклона в клоне, при помощи которых проблема полноты решена в ряде случаев. В том числе, доказаны необходимые и достаточные условия максимальности произвольных и слабо центральных подклонов, заданных расширенными и-описаниями. На основе этого в слабо центральном клоне, задаваемом наследственной системой множеств, явно описаны все максимальные подклоны, включающие все слабо существенные функции. Тем самым, в частности, решены проблемы полноты при суперпозиции со слабо существенными функциями в клона-х квазимонотонных функций на полурешётке и в (предполных) клонах, описываемых центральными симметричными и одновременно вполне рефлексивными предикатами, отличными от диагоналей. Найдена асимптотика мощности построенной критериальной системы в случае полурешётки всех непустых подмножеств /¿-элементного множества. В случае трёхэлементной полурешётки решены проблемы: выразимости множества минимальных точечных функций в клоне монотонных функций, полноты в клонах монотонных и квазимонотонных функций.

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

Методы исследований. В диссертации используются математический аппарат и методы дискретной математики и универсальной алгебры.

Достоверность полученных результатов. Все полученные в диссертации результаты имеют строгое математическое доказательство. Частными случаями ряда доказанных теорем являются некоторые известные теоремы.

Практическая и теоретическая ценность. Теоретическая ценность полученных в диссертации результатов обусловлена возможностью их использования в научных исследованиях при изучении различных пространств дискретных функций. Так, на основании полученных результатов проблема выразимости конечно порождаемого множества в сильно предупорядочен-ном финитарном пространстве сводится к выделению замкнутых классов, определяемых запретами из известного конечного множества. Построенная в диссертации теория Галуа для ¿"-замыкания открывает затруднённую ранее возможность решения проблемы выразимости конечно порождаемого класса в пространстве дискретных функций, вычисляемых переключательными схемами в различных базисах: эта проблема может быть решена теперь на основе выделения конечной системы классов, описываемых парами предикатов. Конечная порождаемость ряда клонов может быть установлена путём выявления в них конечно порождаемых й- или произвольных (с, ¿¿)-подклонов при натуральном с; в таких клонах задача синтеза может быть решена на основе (с, г)-разложений. При решении проблемы полноты в произвольном клоне выделение максимальных подклонов может быть выполнено с использованием доказанных в диссертации теорем о выделении. В том числе решение проблемы полноты в произвольном клоне В при суперпозиции с функциями любого его слабо центрального подклона сводится к нахождению ^-простых предикатов.

Практическая ценность полученных результатов обусловлена возможностью их использования на различных этапах проектирования дискретных управляющих систем различного типа. Так, метод (с, г)-разложений можно использовать для решении задач синтеза управляющих систем, описываемых функциями из (с, с?)-клона. В частности, этот метод можно использовать для синтеза дискретных управляющих систем с заданным динамическим поведением, описывая их при помощи полурешёточной модели, предложенной Г. П. Агибаловым. На основе той же модели для синтеза управляющих систем указанного вида можно использовать предложенные в диссертации методы формульного представления квазимонотонных функций. Конструктивный характер доказательства теорем о полноте и выразимости функций на трёхэлементной полурешётке также даёт методы синтеза в произвольных базисах для комбинационных схем с двоичными статическими состояниями и заданным динамическим поведением. При этом на различных этапах реше- ) ния задачи синтеза проектируемое устройство описывается квазимонотонной, монотонной или минимальной точечной функцией, а синтез ведётся в квазимонотонном, монотонном или минимальном точечном базисе.

Работа выполнена в соответствии с планами НИР Томского государственного университета по единому заказ-наряду и по ФЦП «Интеграция», по ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009— 2013 гг. (г/к. №П1010).

Апробация работы. Результаты работы докладывались на Международной конференции «Дискретный анализ и исследование операций» (Новосибирск, 2004), на XIII Международной конференции «Проблемы теоретической кибернетики» (Москва, МГУ, 2002), на VII и IX Международных семинарах «Дискретная математика и её приложения» (Москва, МГУ, 2007), на XV и XVII Международных семинарах «Синтез и сложность управляющих систем» (2004, 2008), на I - VI, VIII и X Сибирских научных школах-семинарах с международным участием «Компьютерная безопасность и криптография»

2002-2007, 2009, 2011), на научных и учебных семинарах кафедры защиты информации и криптографии Томского государственного университета.

Публикации. Материалы диссертации изложены в 25 научных изданиях, из которых 12 включены в список научных изданий, рекомендованных ВАК для опубликования результатов диссертаций.

Структура диссертации. Диссертация состоит из введения, пяти глав, заключения и списка использованных источников, включающего 166 источников. Её объём — 192 страницы.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Парватов, Николай Георгиевич

Заключение

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

В первой главе выявлены условия, при которых в различных пространствах выполняются аналоги обобщённой теоремы А. В. Кузнецова о полноте [59, 62, 63] и конечно порождаемые классы имеют конечные нижние окрестности, а также условия при которых замкнутые классы допускают эффективные в приложениях способы задания — конечными запрещающими множествами в предупорядоченных пространствах и конечными описаниями в пространствах с замыканием Галуа. Получены следующие результаты.

Установлены необходимые и достаточные условия существования конечных нижних окрестностей у конечно порождаемых классов произвольного пространства (теоремы 1.1 и 1.2) и пространства с замыканием Галуа (теорема 1.5). Рассмотрены возможности применения этих условий к различным функциональным пространствам.

Введены в рассмотрение сильно предупорядоченные пространства. Доказано (теоремы 1.3 и 1.4), что в сильно предупорядоченном финитарном пространстве: 1) всякое конечно порождаемое подмножество имеет конечную нижнюю окрестность, классы которой обладают конечными запрещащими множествами; 2) классы с конечными верхними окрестностями имеют конечные запрещающие множества.

Установлена сильная предупорядоченность относительно подстановки переменных пространства Ре функций многозначной логики с замыканием относительно суперпозиции (следствие 1.4), пространства Пе предикатов с замыканием относительно операций подстановки переменных, проектирования и конъюнкции (следствие 1.5), а также пространства Рс,е переключательных функций с 5-замыканием (следствие 1.6). Последнее введённо в результате обобщения ряда известных замыканий и представляет самостоятельный интерес, так как ^-замкнутыми классам являются классы дискретных функций, вычисляемых переключательными схемами в произвольных базисах.

Построена теория Галуа (теоремы 1.7 и 1.8) для пространств переключательных функций с ^-замыканием, описывающая его как замыкание Галуа. Таким образом найдено единое обобщение ряда различных теорий Галуа (построенных Гейгером и Боднарчуком с соавторами для клонов, Харнау для замкнутых классов многозначных функций, Пиппенджером для наследственных классов, Коуцейро и автором для классов дискретных функций, замкнутых подстановками функций из клонов), содержащее их в качестве частных случаев и имеющее собственные приложения в теории переключательных схем.

Перечисленные результаты позволяют получить в качестве следствий известные теоремы о функциональной полноте и предикатно описываемых клонах из [59, 62, 63] и их аналоги для 5-замкнутых классов, неизвестные ранее. Последнее обстоятельство предоставляют возможность, ранее затруднённую, решения проблем полноты и выразимости в пространствах дискретных функций, вычисляемых переключательными схемами. Именно, в силу полученных результатов проблема выразимости для конечно порождаемого класса таких функций имеет решение в виде конечной нижней окрестности, классы которой имеют конечные запрещающие множества и одноэлементные описания.

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

На основе обобщения теоремы К. А. Бейкера и А. Ф. Пиксли из [66] (полученного в теоремах 2.1 и 2.2) рядом равносильных определений введено понятие ¿-подклона в клоне. Доказано, что клон с конечно порождаемым ¿-подклоном конечно порождаемый (теорема 2.3). Рассмотрены примеры клонов с ¿¿-подклонами, нередкие уже среди булевых функций.

На основе анализа примеров введено понятие (с, с/)-клона. Установлена конечная порождаемость (с, с/)-клона при натуральных с (теорема 2.4). (с, Клоны охарактеризованы свойствами инвариантных предикатов (теорема 2.5) Введено понятие (с, г)-разложения для функций и клонов, при с = 0ис = г близкое к известным понятиям из [33] чистого и смешанного ¿¿-разложений. Установлена возможность (с, г)-разложений клона над (с, б?)-подклоном, известная ранее лишь в случае с = 0.

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

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

В связи с проблемами синтеза асинхронных дискретных управляющих систем сформулирована задача описания замкнутых классов в множествах точечных и минимальных точечных функций, а также максимальных таких классов. Доказано, что в каждом из указанных двух множеств всякий замкнутый класс расширяется до некоторого максимального по включению, множество которых конечно (теорема 3.5, следствие 3.4). Построены примеры максимальных таких классов на полурешётке интервалов решётки. Именно, показано, что дважды монотонные функции составляют максимальные подк-лоны в множествах точечных и минимальных точечных функций (следствие 3.7) на полурешётке интервалов решётки.

Явно описаны классы троичных функций, вычисляемых дизъюнктивными формами (теоремы 3.6, 3.7 и 3.8) и произвольными формулами в каноническом базисе (следствие 3.10). Установлено, что класс минимальных точечных функций на дистрибутивной точечной полурешётке порождается двухместными функциями (теоремы 3.9 и 3.10). В качестве доказательства этого предложен метод формульного представления минимальных точечных функций на дистрибутивной точечной полурешётке в бинарных базисах, содержащих все одноместные минимальные точечные функции и некоторый набор специальных двухместных функций.

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

Введены в рассмотрение Р-предельные (по проектированию, отождествлению, симметризации и сужению) предикаты, описывающие для клона В клоны некоторой его критериальной системы, причём конечной для конечно порождаемого клона В (теорема 4.1). Доказаны необходимые и достаточные условия максимальности подклона, заданного расширенным и-описанием (теорема 4.2). Установлена максимальность подклона, описываемого Р-прос-тым предикатом (теорема 4.3). Использование этих теорем для выделения максимальных подклонов проиллюстрировано рядом примеров. В том числе установлена Р^-простота ряда предикатов, а также Р-простота предиката ^ для клона Р, совпадающего с клоном квазимонотонных или слабо существенных квазимонотонных функций, откуда следует максимальность монотонной части в каждом из этих клонов. Сформулирована теорема 4.4 о выделении максимальных слабо центральных подклонов.

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

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

В пятой главе установлен ряд критериев полноты и выразимости для квазимонотонных функций на трёхэлементной полурешётке.

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

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

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

Случай трёхэлементной полурешётки, исследованный в этой главе (и отчасти в предыдущей), представляет особый интерес для приложений, так как функциями на ней описываются динамические состояния дискретных асинхронных управляющих систем с двоичными статическими состояниями. А постановки рассматриваемых проблем полноты и выразимости возникают в силу полурешёточной модели [5] на различных этапах проектирования таких систем.

Список литературы диссертационного исследования доктор физико-математических наук Парватов, Николай Георгиевич, 2011 год

1. Агибалов Г. П., Оранов А. М. Лекции по теории автоматов. Томск: Изд-во ТГУ, 1983. 185 с.

2. Агибалов Г. П., Бузанов В. А., Липский В. Б.,Румянцев Б. Ф. Логическое проектирование переключательных автоматов. Томск: Изд-во Том. ун-та, 1983. 154 с.

3. Агибалов Г. П. Функциональные системы на полурешётках // Алгоритмы решения задач дискретной математики. Вып. 2. Томск: Томск: Изд-во ТГУ. 1987. С. 3-39.

4. Агибалов Г. П. Квазимонотонные функции и их минимизация // Кибернетика. 1989. №2. С. 111-113.

5. Агибалов Г. П. Дискретные автоматы на полурешётках. Томск: Изд-во ТГУ. 1993. 227 с.

6. Алексеев В. Б. Ступенчатые билинейные алгоритмы и распознавание полноты в /г-значных логиках // Известия высших учебных заведений. 1988. №7. С. 19-27.

7. Богомолов A.M., Салий В.И. Алгебраические основы теории дискретных систем. М.: Наука. Физматлит. 1997. 368 с.

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

9. Биркгоф Г. Теория решёток. М.: Наука, 1984. 568 с.

10. Блохина Г. Н. О предикатном описании классов Поста // Дискретный анализ. 1970. В. 16. С. 16-29.

11. Буевич В. А. Вариант доказательства критерия полноты для функций Анзначной логики // Дискретная математика. 1996. Т. 8. В. 4. С. 1-36.

12. Вороненко А. А. О методе разложения для распознавания принадлежности инвариантным классам // Дискретная математика. 2002. Т. 14.1. B. 4. С. 110-116.

13. Гаврилов Г.П. Индуктивные представления булевых функций и конечная порождаемость классов Поста // Алгебра и логика. 1984. Т. 23. № 1.1. C. 3-26.

14. Гаврилов Г.П. Функциональные системы дискретной математики. Изд-во МГУ. 1985.

15. Гретцер Г. Общая теория решеток. М.:Мир. 1982. 452 с.

16. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. Перевод с английского Е. В.Левнера и М.А. Фрумкина под ред. А.А.Фридмана. М.:Мир. 1982. 416с.

17. Дистель Р. Теория графов. Новосибирск: Изд-во Ин-та математики. 2002. 336 с.

18. Захарова Е. Ю. Критерии полноты систем функций из Рк / / Проблемы кибернетики. 1967. В. 18. С. 5-10.

19. Захарова Е. Ю., Кудрявцев В. В., Яблонский С. В. О предполных классах в Ахзначных логиках // Доклады Академии Наук СССР. 1969. Т. 186. №3. С. 509-512.

20. Колмогоров А. Н., Драгалин А. Г. Математическая логика. М.: КомКни-га. 2006. 240 с.

21. Кострикин А. И. Введение в алгебру. Часть III. Основные структуры алгебры. М.: Физико-математическая литература. 2001. 272 с.1. Г '

22. Кон П. Универсальная алгебра. М.: Мир. 1968. 351 с.

23. Кузнецов А. В. Структуры с замыканием и критерии функциональной полноты // Успехи матем. наук. 1961. Т. 16. №2 (98). С. 201-202.

24. Курош А. Г. Лекции по общей алгебре. СПб.: Лань. 2005.

25. Ло Чжукай. Теория полноты для частичных функций многозначной логики // Кибернетический сборник. М.:Мир. 1988. В. 25. С.142-161.

26. Мальцев А. И. Итеративные алгебры Поста. Новосибирск: Изд-во НГУ. 1976.

27. Мальцев А. И. Алгебраические системы. Новосибирск: Изд-во НГУ. 1970. 392 с.

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

29. Марченков С. С. К существованию конечных базисов в замкнутых классах булевых функций // Алгебра и логика. 1984. Т. 23. В. 1 С. 88-99.

30. Марченков С. С. О равномерном ¿¿-разложении булевых функций // Дискретная математика. 1990. Т. 2. В.З. С. 29-41.

31. Марченков С. С., Угольников А. Б. Замкнутые классы булевых функций. М.: Изд-во ИПМ АН СССР. 1990.

32. Марченков С. С. Об ¿¿-разложениях класса Р\ над предполными классами // Дискретная математика. 1993. Т. 5. В. 2. С. 98-110.

33. Марченков С. С. Предполнота замкнутых классов в Р}~\ предикатный подход. // Математические вопросы кибернетики. 1996. В. 6. С. 117-132.

34. Марченков С. С. Инварианты классов Поста // Фундаментальная и прикладная математика. 1998. Т. 4. В. 4. С. 1385-1404.

35. Марченков С. С. Замкнутые классы булевых функций. М.: Физматлит. 2000. 128 с.i l

36. Панкратова И. А. Реализация функций на полурешётках переключательными схемами // Прикладная дискретная математика. 2009. №2. С. 50-55.

37. Перязев Н. А. Слабоповторные булевы функции в бинарном базисе // Дискретная математика и информатика. В. 4. Иркутск: Изд-во Иркутского государственного университета. 1998. 12 С.

38. Перязев Н. А., Шаранхаев И. К. Критерии бесповторности булевых функций в предэлементарных базисах ранга 2 // Дискретная математика. 2005. Т. 17. В. 2. С. 127-138.

39. Риге Ж. Бинарные отношения, замыкания, соответствия Галуа // Кибернетический сборник. 1963. В. 7. С. 129-185.

40. Ромов Б. А. Алгоритм решения проблемы полноты в классе векторных функциональных систем // Математические модели сложных систем. Киев: ИК АН УССР. 1973. С. 151-155.

41. Ромов Б. А. О решётке подалгебр прямых произведений алгебр Поста конечной степени // Математические модели сложных систем. Киев: ИК АН УССР. 1973. С. 156-168.

42. Ромов Б. А. О полноте на квадрате функций алгебры логики и в системе Рк х Pt // Кибернетика. 1987. №4. С. 9-14.

43. Ромов Б. А. О продолжении не всюду определённых функций многозначной логики // Кибернетика. 1987. №3. С. 27-34.

44. Ромов Б. А. Об одной серии максимальных подалгебр прямых произведений алгебр конечнозначных логик // Кибернетика. 1989. №4. С. 11-16.

45. Ромов Б.А. О максимальных подалгебрах алгебры частичных функций многозначной логики // Кибернетика. 1980. В. 1. С. 28-36.

46. Ромов Б.А. О проблеме полноты в алгебре частичных функций многозначной логики // Кибернетика. 1990. В. 1. С. 102-106.

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

48. Стеценко В. А. О предплохих базисах в Р2 // Математические вопросы кибернетики. В. 4. М.:Физматлит. 1992 С. 139 -177.

49. Тайманов В. А. О функциональных системах А:-значной логики с операциями программного типа // Доклады Академии Наук СССР. 1983. Т. 286. №6. С. 1307-1310.

50. Угольников А. Б. О замкнутых классах Поста //Известия вузов. Математика. 1988. №7. С. 79-88.

51. Угольников А. Б. Глубина формул в некоторых классах Ахзначной логики // Вестник МГУ. Серия 1. Математика, механика. 1991. №4. С. 44-47.

52. Фрейвалд Р. Критерии полноты для частичных функций алгебры логики и многозначных логик // Доклады Академии Наук СССР. 1966. Т. 167. №6. С. 1249-1250.

53. Шеннон К. Синтез двухполюсных переключательных схем. Работы по теории информации и кибернетике. Изд-во иностранной литературы. 1963. С. 59-105.

54. Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств. М.: Наука. 1980. 400 с.

55. Шоломов JI. А. Элементы теории недоопределённой информации // Прикладная дискретная математика. Приложение. 2004. № 2. С. 18-42.

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

57. Яблонский С. В. О классах функций алгебры логики, допускающих простую схемную реализацию // Успехи математических наук. 1957. Т. 12. №6(78). С. 189-196.

58. Яблонский C.B. Функциональные построения в /г-значной логике // Труды математического института им. В.А.Стеклова. 1958. Т. 51. С. 5142.

59. Яблонский С. В. О невозможности элиминации перебора всех функций из Р2 при решении некоторых задач теории схем // Доклады Академии Наук СССР. 1959. Т. 124. №1. С. 44-47.

60. Яблонский С. В. Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М.гНаука, 1966.

61. Яблонский С. В. О строении верхней окрестности для предикатно-описуемых классов в Рк- // Доклады Академии Наук СССР. 1974. Т. 218. № 2. С. 302-307.

62. Яблонский С. В. Введение в дискретную математику. М.: Наука. 1986.

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

64. Agibalov G. P. Functional systems on semilattices // R. G. Bukharaev, О. B. Lupanov (Eds.). Fundamentals of Computation Theory. Berlin: Springer Verlag, 1987. P. 5-9.

65. Baker K.A., Pixley A.F. Polynomial interpolation and Chinese remainder theorem for algebraic systems // Math. Zeiteschr. 1975. V.143. № 2. P. 165174.

66. Birkhoff G., Frink O. Representations of lattices by sets // Transactions on american mathematical society. 1948. V. 64. P. 299-316.

67. Bixby R.E. On Reid's characterization of the ternary matroids //J. Combin. Theory Ser. B. 1979. V. 26. P. 174-204.

68. Bulatov A., Krokhin A., Jeavons P. Constraint satisfaction problems and finite algebras // Lecture Notes in Computer Science. 2000. V. 1853. P. 272282.

69. Couceiro M., Foldes S. On Affine Constraints satisfied by Boolean functions // Rutcor Research Report 3-2003. Rutgers University. Доступно по адресу http://rutcor.rutgers.edu/pub/rrr/reports2003.

70. Couceiro M. Galois connections for generalized functions and relational constraints // Contributions to General Algebra. 2004. V. 16. P. 35-54.

71. Couceiro M., Foldes S. Definability of Boolean function classes by linear equations over GF(2) // Discrete Appl. Math. 2004. V. 142. P. 29-34.

72. Couceiro M., Foldes S. On closed sets of relational constraints and classes of functions closed under variable substitution // Algebra Universalis. 2005. V. 54. P. 149-165.

73. M. Couceiro, S. Foldes. Constraints, functional equations, definability of function classes, and functions of Boolean variables // Acta Cybernetica. 2007. V. 18. P. 61-75.

74. M. Couceiro, S. Foldes. Function classes and relational constraints stable under compositions with clones // Discussiones Math., General Algebra and Applications. 2009. V. 29. P. 109-121.

75. Creignou N., Vollmer H. Boolean constraint satisfaction problems: When does post's lattice help? // Lecture Notes in Computer Science. 2008. V. 5250. P. 3-37.

76. Demetrovics J., Hannak L., Ronyai L. Near unanimity functions and partial orderings // Proc. 14 ISMVL, Manitoba. 1984. P. 52-56.

77. Demetrovics J., Hannak L., R6nyai L. On algebraic properties of monotone clones // Order. 1986. V.3. P. 219-225

78. Demetrovics J., Ronyai L. Algebraic properties of crowns and fences // Order. 1989. №6. P. 91-100.

79. Everett C. J. Closure operators and Galois theory in lattices // Transactions on american mathematical society. 1944. V. 55. P. 514-525.

80. Ekin O., Folders S., Hammer P.L., Hellerstein L. Equational characterization of Boolean function classes // Discrete Math. 2000. V.211. P. 27-51.

81. Geelen J., Gerards A.M.H., Whittle G. The excluded minors for GF 4-representable matroids // J. Combin. Theory Ser. B. 2000. V. 79. P. 247299.

82. Geiger D. Closed systems of functions and predicates // Pacific journal of mathematics. 1968. V. 27. № 1. P. 95-100.

83. Haddad L. Maximal partial clones determined by quasi-diagonal relations // Elektronische Informations Verarbeitung und Kybernetik. 1988. V. 24 (7-8) P. 355-366.

84. Haddad L., Rosenberg I. G. Maximal partial clones determined by the areflexive relations // Discrete Appl. Math. 1989. V.24 (1-3). P. 133-143.

85. Haddad L., Rosenberg I.G. Completeness theory for finite partial algebras // Algebra Univers. 1992. V.29(3). P. 378-401.

86. Harnau W. Ein verallgemeinter Relationenbegriff für die Algebren der mehrwertigen Logik. Teil I (Grundlagen). // Rostocker Math. Kolloq. 1985. B. 28. S. 5-17.

87. Harnau W. Ein verallgemeinter Relationenbegriff für die Algebren der mehrwertigen Logik. Teil II (R.elationenpaare). // Rostocker Math. Kolloq. 1987. B.31. S. 11-20.

88. Harnau W. Ein verallgemeinter R,elationenbegriff für die Algebren der mehrwertigen Logik. Teil III (Beweis). // Rostocker Math. Kolloq. 1987. B. 32. S. 15-24.

89. Hellerstein L. On generalized constraints and certificates // Discrete Mathematics. 2001. V.226. P. 211-232.

90. Jeavons P. G., Cohen D. A., Gyssens M. Closure properties of constraints // Journal of ACM. 1997. V.44. P. 527-548.

91. Jeavons P. G. On the algebraic structure of conbinatorial problems // Theoretical computer science. 1998. V. 200. P. 185-204.

92. Jeavons P, Cohen D, Pearson J. Constraints and Universal Algebra // Annals of Mathematics and Artificial Intelligence. 1998. V. 24. P. 51-67.

93. Jeavons P. G., Cohen D. A., Cooper M.C. Constraints, consistency and closure // Artifical Intelligence. 1998. V. 101. P. 251-265.

94. Jonsson P., Nordh G. Introduction to the maximum solution problem // Lecture Notes in Computer Science. 2008. V. 5250. P. 255-282.

95. Krasner M. Une generalisation de la notion de corps //J. Math. Pures Appl. 1938. V. 17. P. 367-385.

96. Krasner M. Abstract Galois theory and endotheory I,II // Acta Sci. Math. 1986. V. 50. P. 253-286; 1988. V.52. P. 231-255.

97. Ladkin P. В., Maddux R. D. On binary constraint problems // Journal of ACM. 1994. V. 41. P. 435-469.

98. Lau. D. Uber partielle Funktionenalgebren // Rostoc. math. Kolloq. 1988. B.33. S. 23-48.

99. Lau. D. Function algebras on finite sets. A basic course on many-valued logic and clone theory. Springer Monographs in Mathematics. Berlin: Springer, 2006. 668 p.

100. Lehman A. Matroids and ports // Notices Amer. math. soc. 1976. V. 12. P. 356-360.

101. Lehtonen E. Order-theoretical analysis of subfunction relations between Boolean functions // manuscript. 2005. Статья доступна в интернете по электронному адресу http://math.tut.fi/algebra/.

102. Lehtonen Е. Descending chains and antichains of the unary, linear, and monotone subfuction relations // Order. 2006. V.23. P. 129-142.

103. Lehtonen E. Closed classes of functions, generalized constraints and clusters. // Algebra Universalis. 2010. V.63. P. 203-234.

104. Mackworth A. K. Consistency in networks of relations // Artifical Intellegence. 1977. V.8. P. 99-118.

105. Montanari U. Networks of constraints: Fundamrntal properties and applications to picture processing // Information Science. 1974. V. 7. P. 95132.

106. Nordh G., Jonsson P. An Algebraic Approach to the Complexity of Propositional Circumscription //In LICS, pages 367-376. IEEE Computer Society, 2004.

107. Nordh G., Zanuttini B. Frozen boolean partial co-clones //In Multiple-Valued Logic, 39th IEEE International Symposium on, pages 120-125, 2009.

108. Ore O. Galois Connections // Transactions on american mathematical society. 1944. V. 55. P. 493-513.

109. Pippenger N. Galois theory for minors of finite functions // Discrete Mathematics. 2002. V. 254. P. 405-419.

110. Pöshel R. Postshe Algebren von Funktionen über einer Familie endlicher Menge. // Z. Math. Logik Grundlagen Math. 1973. V. 19. P. 37-74.

111. Pöshel R. Concrete represetation of algebraic structures and general Galois theory. In: H. Kautschitsch, W. B. Müller, W. Nöbauer (eds)Contributions to General Algebra (Proc. Klagenfurt Conf., 1978) Verlag Johannes Heyen. Klagenfurt. 1979. P. 249-272.

112. Pöshel R., Kaluznin L. A. Funktionen- und Relationenalgebren. Berlin: WEB Deutscher Verlag der Wissenschaften. 1979.

113. Post E. L. Two-valued iterative systems of mathematial logic // Annals of Math. Studies. Princeton Univ. Press. 1941. V.5.

114. Romov B. A. The completeness theory for the product of finite partial algebras // Discrete Mathematics. 2004. V.274. P. 241-264.

115. Romov B. A. The completeness problem in partial hiperclones // Discrete Mathematics. 2006. V. 306. P. 1405-1414.

116. Rosenberg J. Uber die funktionale Vollständigkeit in den mehrwertigen Logiken // CSAV Rada Math. Pfir. Ved. Praha. 1970. B.80. №4. S.3-93.

117. Szabo L. Concrete representation of related structures of universal algebras // I. Acta Sci. Math. 1978. V.40. P. 175-184.1231 Tardos G. A not finitely generated maximal clone of monotone operations // Order. 1986. №3. P.211-218

118. Tutte W.T. A homotopy theorem for matroids // I,II Trans. Amer. Math. Soc. 1958. V.88. P. 144-174.

119. Zverovich. I. E. Characterization of Closed Classes of Boolean Functions in terms of forbidden subfunction and Post classes // Discrete Applied Mathematics. 2005. V. 149. P. 200-218.

120. ОСНОВНЫЕ ПУБЛИКАЦИИ АВТОРА

121. Парватов Н.Г. К синтезу формул, реализующих и представляющих квазимонотонные и монотонные функции на полурешётках подмножеств конечного множества // Вестник Томского государственного университета. 2000. В. 271. С. 111-115.

122. Агибалов Г.П., Парватов Н.Г. О полноте систем монотонных функций для реализации квазимонотонных функций на конечных полурешётках // Дискретный анализ и исследование операций. Серия 1. 2002. Т. 9. №4. С. 5-22.

123. Парватов Н.Г. Функциональная полнота в замкнутых классах квазимонотонных и монотонных трёхзначных функций на полурешётке // Дискретный анализ и исследование операций. Серия 1. 2003., Т. 10. № 1. С. 61-78.

124. Парватов Н.Г. Замечания о конечной порождаемости замкнутых классов многозначных функций // Дискретный анализ и исследование операций. Серия 1. 2004. Т.П. №3. С.32-47.

125. Парватов Н.Г. Теорема о функциональной полноте в классе квазимонотонных функций на конечной полурешётке // Дискретный анализ и исследование операций. Серия 1. 2006. Т. 13. №3. С. 62-82.

126. Парватов Н.Г. Наследственные системы дискретных функций // Дискретный анализ и исследование операций. Серия 2. 2007. Т. 14. №2. С. 76-91.

127. Парватов Н.Г. Клоны с мажоритарной функцией и их обобщения // Дискретный анализ и исследование операций. 2010. Т. 17. №3. С. 46-60.

128. Парватов Н.Г. Проблемы выразимости в решётке с замыканием // Дискретная математика. 2010. Т. 22. В. 4. С. 83-103.

129. Парватов Н.Г. О выделении максимальных подклонов // Прикладная дискретная математика. 2011. №1. С. 14-25.

130. Парватов Н.Г. Проблема нижних окрестностей в пространствах с замыканием и теорема о финитарности // Известия высших учебных заведений. Математика. 2011. №2. С. 65-70.

131. Парватов Н.Г. О нахождении максимальных подклонов слабо центрального клона // Дискретный анализ и исследование операций. 2011. Т. 18. №5. С. 80-97.1.í

132. Парватов Н.Г. Конструкция максимального клона точечных функций на полурешётке интервалов // Прикладная дискретная математика. 2011. №4. С. 5-11.

133. Парватов Н.Г. О формах представления монотонных и квазимонотонных функций на трёхэлементной полурешётке // Материалы IX Меж

134. Парватов Н.Г. О некоторых свойствах операции замыкания, связанных с проблемами выразимости // Вестник Томского государственного университета. Управление, вычислительная техника и информатика 2008. №3. С. 119-124.

135. Парватов Н.Г. Проблемы полноты и выразимости дискретных функций // Прикладная дискретная математика. 2009. №2. С. 56-78.

136. Парватов Н.Г. Нижние и верхние окрестности в множестве с замыканием // Прикладная дискретная математика. 2009. №3. С. 5-14.

137. Парватов Н.Г. Об инвариантах некоторых классов квазимонотонных функций на полурешётке // Прикладная дискретная математика. 2009. №4. С. 21-28.

138. Парватов Н.Г. Соответствие Галуа для замкнутых классов дискретных функций // Прикладная дискретная математика. 2010. №2. С. 10-16.

139. Парватов Н.Г. Точечные и сильно точечные функции на полурешётке // Прикладная дискретная математика. 2010. № 3. С. 22-40.1. ПРОЧИЕ ПУБЛИКАЦИИ АВТОРА

140. Парватов Н.Г. О полноте систем функций на конечных полурешётках // Международная конференция «Дискретный анализ и исследование операций». Материалы конференции (Новосибирск, 2000 год). Новосибирск: Изд-во института математики. 2000. С. 66.

141. Парватов Н.Г. О полных системах операций для синтеза комбинационных схем с заданным динамическим поведением // Труды городской конференции по приборостроению (Томск, 2001 год). Томск: Изд-во ТГ-ПУ. 2001. С. 57-58.

142. Парватов Н.Г. О полноте в классах монотонных и квазимонотонных функций на конечной полурешётке // Труды городской конференции по приборостроению (Томск, 2001 год). Томск: Изд-во ТГПУ. 2001. С. 5556.

143. Парватов Н.Г. Наследственные функциональные системы // Вестник Томского государственного университета. Материалы международных, всероссийских и региональных научных конференций, симпозиумов, школ, проводимых в ТГУ. Приложение. 2006. № 17. С. 53-57.

144. Парватов Н.Г. Конспект лекций по теории групп. Изд-во Томского государственного университета. 122 с.

145. Парватов Н. Г. Совершенные схемы разделения секрета // Прикладная дискретная математика. 2008. №2. С. 50-57.

146. Парватов Н.Г. Слабоцентральные клоны и проблема полноты в них // Прикладная дискретная математика. Приложение К2 4. 2011. С. 14-16.