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

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

Парватов Николай Георгиевич

ПРОБЛЕМЫ ПОЛНОТЫ И ВЫРАЗИМОСТИ В ПРОСТРАНСТВАХ ДИСКРЕТНЫХ ФУНКЦИЙ

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

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

1 2 [ ир 2012

КРАСНОЯРСК - 2012

005012350

Работа выполнена на кафедре защиты информации и криптографии ФГБОУ ВПО «Национальный исследовательский Томский государственный

университет»

Научный консультант:

доктор технических наук, профессор Агибалов Геннадий Петрович

Официальные оппоненты:

доктор физико-математических наук, профессор Вороненко Андрей Анатольевич;

доктор физико-математических наук, профессор Перязев Николай Алексеевич; доктор физико-математических наук, профессор Шоломов Лев Абрамович

Ведущая организация:

ФГБОУ ВПО «Саратовский государственный университет имени Н. Г. Чернышевского»

Защита состоится 23 марта 2012 г. в 14.00 часов на заседании диссертационного совета ДМ 212.099.18 при Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. Киренского, 26, корпус Ж, ауд. УЛК-115.

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета (г. Красноярск, ул. Киренского, 26).

Автореферат разослан « $ » февраля 2012 г.

Учёный секретарь диссертационного совета

К. А. Кириллов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

жсство нс включено ни в один из классов системы.

Проблемы полноты и выразимости решены в пространствах булевых функций с замыканием относительно суперпозиции в работе Э. Поста, в пространстве функций /г-значной логики - в работах С. В. Яблонского, И. Розенбсрга и других, в пространствах частичных таких функций — в работах Р. Фрейвалда, Б. А. Ромова, Ло Чжукая и других. В связи с полурешёточной моделью, предложенной в работах Г. П. Агибалова для описания асинхронных дискретных управляющих систем, возникает необходимость решения указанных проблем в различных классах квазимотонпых функций па полурешетках. В диссертации проблемы полноты и выразимости решены в некоторых таких классах, найдены различные условия максимальности подклона в клоне, позволяющие выделять максимальные подкопы при решении проблем полноты в различных клонах.

Проблема конечной порождаемости состоит в выявлении условий, при которых заданный класс пространства имеет конечное порождающее множество. Актуальность этой проблемы для клонов связана с результатами Ю. И. Янова и А. А. Мучника о существовании клопов без конечного порождающего множества и с результатами Э. Поста о конечной порождаемое™ клонов булевых функций. В связи с этим в работах С. С. Марчепкова, Д. Лау, Г. Тардсша, Дсметровича с соавторами и О. С. Дудаковой были выделены некоторые семейства конечно порождаемых клонов. В диссертации описан ряд новых таких семейств, предложены методы функционального разложения в них.

Более общая проблема эффективного задания связана с разработкой и обоснованием методов эффективного задания замкнутых классов при помощи конечных порождающих множеств в произвольных пространствах, конечных запрещающих множеств в нредупорядочеппых пространствах, конечных описаний в пространствах с замыканием Галуа и иных. Так, в работах Д. Гейгера и В. Г. Бодпарчука с соавторами построена теория Галуа для клонов, в работе С. В. Яблонского охарактеризованы клопы, задаваемые предикатами и конечными запрещающими множествами; эти результаты обобщены для клонов многоосновных алгебр Р. Пёшелем и Л. А. Калужниным, для наследственных систем Н. Пипненджером и О. Экиным с соавторами, для перестановочно замкнутых классов Л. Хеллерстайн. В диссертации получено дальнейшее обобщение этих результатов для ¿'-замкнутых классов, к числу которых относятся клоны, наследственные классы, а также классы дискретных функций, вычисляемых переключательными схемами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Работа выполнена в соответствии с планами НИР Томского государственного университета по единому заказ-наряду и по ФЦП «Интеграция», по ФЦП «Научные и научно-педагогические кадры инновационной России» на 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 страницы.

СОДЕРЖАНИЕ РАБОТЫ

Первая глава называется «Нижние и верхние окрестности». В ней установлены условия, при которых в различных пространствах - произвольных, предупо-рядоченных и с замыканием Галуа, произвольные или заданные конечно порождаемые классы имеют конечные нижние окрестности с эффективно определяемыми классами (посредством конечных запрещающих множеств в предунорядоченных пространствах и конечных описаний в пространствах с замыканием Галуа). Введены сильно нредуиорядоченные пространства. Рассмотрены приложения найденных условий к различным функциональным и логическим пространствам, в том числе к пространствам дискретных функций с 5-замыканием, введённым для описания классов функций, вычисляемых переключательными схемами. Построена теория Галуа для ¿"-замыкания. Рассмотрим эти результаты подробнее.

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

Теорема 1.1 характеризует пространство с конечными нижними окрестностями для всех конечно порождаемых подмножеств как финитарное с конечной системой 5(Л) для всякого конечного подмножества А, где А) — система максимальных замкнутых подмножеств среди не включающих А.

Подмножество А С Р называется компактным (слабо компактным) в пространстве (Р,'), если всякая непустая направленная вверх система (соответственно цепь) С подмножеств множества Р, такая, что А С (иС)', содержит в качестве элемента множество В, такое, что А С В'.

Теорема 1.2 характеризует подмножества А с конечными нижними окрестностями в произвольном пространстве как компактные (равносильно слабо компактные) с конечной системой <5>(Л).

Далее изучаются нредуиорядоченные пространства.

Пусть в множестве Р определено предупорядочение <. Тройка (Р/, <) называется предупорядочеппым пространством, если для любых элементов х и у из Р выполняется импликация

(я < у) =>({!}' С {у}').

Подмножество А С Р называется наследственным, если вместе с любым своим элементом Ь оно содержит всякий элемент а из Р, такой, что а < Ь. Пусть

X С Р. Наименьшее по включению наследственное множество среди включающих X обозначается Наибольшее по включению наследственное множество среди не пересекающихся с X обозначается Р\Х> и множество X для него называется запрещающим. В приложениях задание наследственных и замкнутых классов конечными запрещающими множествами является эффективным.

Предупорядоченное пространство называется сильно предупорядочетшм, если множество Р является объединением направленной вверх системы N конечных подмножеств и существует функция а : ЛГ М, такая, что для любых множеств В\ € А/", В? = ot(Bi) и X С Р выполняется включение

X'nBiQ (Х< П В2у.

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

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

Верхней окрестностью множества X в пространстве называется система И замкнутых классов, не включённых в Х\ если всякий не включённый в X' замкнутый класс пространства можно сузить до класса из И.

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

Следствия 1.4 - 1.6 устанавливают сильную нредупорядоченность относительно подстановки переменных трёх функциональных пространств — пространства Ре функций / : Еп —> Е с замыканием относительно операций суперпозиции, пространства П^ предикатов р : Еп —> {И,Л} с замыканием относительно операций конъюнкции, проектирования и подстановки переменных, а также пространства Рс,е функций / : Е" —> С с 5-замыканием (где Е и С — фиксированные конечные множества, а п принимает целые положительные значения). Рассмотрим подробнее последней результат.

Пусть заданы клоны L С Рс, R С РЕ и множества О С Рс\е, U С Ре,с-Положим 5 = (L,0, R,U). Множество М функций из Рс,е называется S-замкнутым, если

О с М, LMR С М, MUM С М.

При этом под «произведением» XY произвольных множеств X и Y функций из соответствующих классов Рр,с и Рс,е понимается множество всех функций

/(д[(х),... ,дп(х)), где / — п-местпая функция из X, д\,...,д„ — т-мсстныс функции из У, через х обозначен набор переменных х\,...,хт, а числа пит принимают произвольные натуральные значения.

Будем обозначать через < предупорядочеиие в множестве Р^.е относительно подстановки переменных, при котором для функций и и V), зависящих соответственно от п и т переменных, неравенство V < и» означает, что

у(х ь ... ,хп) = ... ,£;т) для некоторых ц,... ,гт из {1,... , п}.

Имеет место

Следствие 1.6. В множестве Рс,е Б-замыкание и предупорядочеиие относительно подстановки переменных сильно согласованы посредством системы N и отображения а, где А/" состоит из множеств при целых положительных п и а(Р^п)Е) = Р™ для т =

Здесть Р^р — множество функций из Рс,е от п или менее переменных.

Установлено

Следствие 1.7. Конечно порождаемый Э-замкнутый класс имеет конечную нижнюю окрестность, классы которой обладают конечными запрещающими множествами.

Введённое 5-замыкание обобщает ряд известных замыканий и представляет самостоятельный интерес, так как ¿"-замкнутыми классами являются классы функций, вычисляемых переключательными схемами.

Далее изучаются пространства с замыканием Галуа.

Пусть заданы непересекающиеся множества Р и Т и соответствие Галуа между системами их подмножеств, то есть для любого подмножества X С Р {и любого X С Т) определено подмножество Х+ С Т (соответственно Х+ С Р), причём

X С X СУ ^ Х+ ЭУ+ и X СУ Х++ С У++

если X и У С Р или X и У С Т. Соответствие Галуа может быть определено отношением а С Р х Т, таким, что для любых х € Р и у е Т:

(х, у) е а & х 6 {у}+ 6 {х}+.

В каждом из множеств Р и Т оказывается определённым замыкание ++, называемое замыканием Галуа. Пусть также в каждом из множеств определено предупорядочеиие <, согласованное с замыканием Галуа в нём.

Множество X называется описанием Галуа-замкнутого класса Х^. Галуа-замк-нутый класс, обладающий конечным описанием, называется конечно описуемым.

Теорема 1.5. Пусть в преду порядочен1) юм пространстве (Т,++, <]) всякий Галуа-замкнутый класс с одноэлементным описанием обладает конечным запрещающим множеством. Тогда для любого Галу а-замкнуто го класса этого преду-порядоченного пространства наличие конечного запрещающего множества равносильно наличию конечного описания и равносильно наличию конечной верхней окрестности. В тех же условиях для любого Галуа-замкнутого класса пространства (Р,++ ) наличие конечного порождающего множества равносильно наличию конечной нижней окрестности.

Теорема 1.6 характеризует пространства с замыканием Галуа и с конечными нижними окрестностями для всех конечно порождаемых классов следующим условием: при некотором предупорядочении двойственного пространства классы с одноэлементными описаниями имеют конечные запрещающие множества.

Далее в работе построена теория Галуа для 5-замыкания.

Это сделано на основе обобщения классического соответствия Галуа pol£ — invs, определяемого отношением сохранения функцией из Ре предиката из Пв и изученного Гейгером и Боднарчуком с соавторами, а также соответствия Галуа polc Е— invc,£, определяемого отношением сохранения функцией из Рс,е 2-предиката из ПС,Е и изученного Пшшенджером.

Сделаем необходимые определения. Пара предикатов р и q одинаковой арности из соответствующих множеств Пс и Пд называется 2-предикатом соответствующей арности. Множество всех 2-нредикатов обозначается через Пс,е- Говорят, что функция / из Рс,е от п переменных сохраняет m-арный 2-предикат (р, q) из Пс,е (либо сохраняет предикат q из Пе, если Е = С и р = q), если для любых наборов Xi,..., Хп, удовлетворяющих предикату q, набор /И(Х 1, ..., Хп), полученный последовательным вычислением значений функции / от строк матрицы (Xf,..., Х%), удовлетворяет предикату р.

Через ро1сЯ(У) (соответственно через ро1с(У)) обозначается множество всех функций из Рс,е (из Pc), сохраняющих все 2-предикаты из множества Y С Пс,е (предикаты из множества Y С Пс)- Через invc,jj(X) (соответственно через invc(A')) обозначается множество всех 2-предикатов из Пс,е (предикатов из множества Пс), сохраняемых всеми функциями из множества X С Рс,е (из X С Рс). Положим

Пс,я = (invc(L)xinvE(fi))ninvc,£(0)ninv^(C/) и inv^(y) = П^вП1Пус,£(У),

где через invgjl(i7) обозначено множество 2-предикатов {q,p), полученных перестановкой компонент в 2-предикатах (р, q) из класса inve,c{U). Рассмотрим соот-

ветствие Галуа ро]С£; - шу^, определяемое отношением сохранения функцией из Рс,е 2-прсднката из Галуа-замкнутые классы функций описывает

Теорема 1.7. Для любого множества N 2-предикатов из множество является Б-замкиутым классом функций из Рс,е- Для любого Б-замкнутого класса М С РСЕ имеет место равенство М = ро1с£(1пУр£(М)).

Имеет место

Следствие 1.8. Конечно порождаемый Б-замкнутый класс имеет конечную нижнюю окрестность, классы которой имеют одноэлементные описания. Наличие конечного описания для Б-замкнутого класса равносильно существованию для него конечного запрещающего множества и равносильно наличию конечной верх71ей окрестности.

Галуа-замкнутые классы 2-предикатов характеризует

Теорема 1.8. Для произвольного множества М функций из Рс,е множество шУс,е{М) является Я-замкнутым классом 2-предикатов. Для любого Б-замк-иутого класса N 2-предикатов верно: N = 1ПУ^£(ро1СЕ(Лг)).

В этой теореме множество 2-предикатов из класса включающее все 2-ди-агонали, называется Б-замкпутым, если оно содержит конъюнкцию любых двух своих 2-ирсдикатов, вместе с любым своим 2-прсдикатом содержит все его проекции и все 2-предикаты, получаемые из него подстановкой переменных, а также вместе с любым своим т-местным 2-прсдикатом (р, д) содержит всякий т-местный 2-предикат (р\ д') из такой, что р 2 р' и д С <?'.

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

Результаты первой главы позволяют получить в качестве следствий известные теоремы о функциональной полноте и предикатно описываемых клонах и их аналоги для ¿'-замкнутых классов. Последнее обстоятельство предоставляет возможность, ранее затруднённую, решения проблем полноты и выразимости в пространствах дискретных функций, вычисляемых переключательными схемами. Именно, в силу следствий 1.7 и 1.8 проблема выразимости конечно порождаемого множества таких функций имеет решение в виде конечной нижней окрестности, классы которой имеют конечные запрещающие множества и описания.

Результаты первой главы получены в следующих работах автора: теоремы 1.1 и 1.2 — в [10], теоремы 1.3 - 1.6 — в [8], следствия 1.4 - 1.6 — в [8, 22], теоремы 1.7 и 1.8 — в [24] на основе [6]. Предварительные результаты получены в [19, 20, 21].

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

Через роГ^К) обозначается множество частичных функций вида / : Еп —> £'и{*}, сохраняющих все предикаты из множества У С Пд. Для клона К, такого, что шуе(АТ) = тУвро^К), множество У называется и-описаиием. И-огшсания клонов играют существенную роль при выявлении свойств конечной порождаемо-сти (что показано во второй главе) и при решении проблем полноты (это показано в четвёртой главе).

В первом разделе приводится лемма Б. А. Ромова о доопределении, используемая для нахождения и-описаний. Далее приводится теорема Бейкера и Пиксли, характеризующая клоны с мажоритарными функциями, а также уточняющая её

Теорема 2.1, необходимая для последующего обобщения.

Дальнейшим обобщением является

Теорема 2.2. Пусть М\ и М2 — клопы функций из Ре, такие, что М\ С М?. Пусть также N1 = тУв(Л/1), N2 = ту^Мг) и (I ^ 1. Следующие условия равносильны:

(1) имеет место равенство = ту^

(2) имеет место включение N1 Стувро^АЪиП^);

(3) для всякой функции /(х\,... ,хп) из М2 существует такая функция т/(хь ..., хп+({+1) в М\, что для любого г, 1 < г < ¿+1, выполняется тождество

/(х) = т{(х, /(ж),..., ¡(х),хп+и ¡(х),..., /(¡г)),

где через х обозначен набор переменных х\,..., хп и переменная находится на (п + г)-м месте функции тп$;

(4) для любого предиката р(хи •••,£() из Ы\, зависящего от1 > й переменных, и любого (равносильно некоторого) подмножества С/ С {1,..., содержащего \и\ > й элементов, найдётся предикат ц(х\,... в N2, такой, что

р(хи.. .,х[)= q{x 1,. . . ,£() А Д .. .,!()■

гег/

В условиях (1) - (4) из теоремы 4.2 клоп Mi С Mi называется d-подклоном клона Л/г, функция лг/ называется специальной для J, переменные xi,..., называются внутренними для функции гтг/. Клопы с d-подклонами представляют интерес в связи с проблемой конечной порождаемое™ в силу следующей теоремы.

Теорема 2.3. Пусть М\ — d-подклон клона функций из Ре- Если клон М1 конечно порождаемый, UAieem порядок щ и степень mi, то клон Mi также конечно порождаемый, его порядок не превосходит max{ni, \E\d — 1}, а степень не превосходит max{mi,d}.

Здесь порядком конечно порождаемого клопа М называется наименьшее натуральное число п, такое, что функции, зависящие не более, чем от п неременных, порождают клон М так, что М = [М^]. Степенью конечно порождаемого клона М называется наименьшее натуральное число ш, такое, в некоторой нижней окрестности клона М всякий клон К описывается некоторым предикатом рк, зависящим не более, чем от т переменных, как К = polе(рк)-

Понятие ейюдклона иллюстрирует

Пример 2.1. В этом примере устанавливается, что 2-подклонами являются монотонные части Ml'1 и Л//00 в клонах Id d-нсразделёпных и неразделённых булевых функций, причём для функции / из /°° специальную функцию mj в Л//00 всегда можно выбрать с не более, чем одной существенной внутренней переменной.

Последнее замечание примера 2.1 получает следующее обобщение.

Для целого неотрицательного числа с и целого положительного числа d ^ 2 клон М1 называется (с,д)-подклоном клона Mi и оба эти клона называются (c,d)-клонами, если клон Mi является d-подклоиом клона Mi и для любой функции / из Мг специальную функцию тоу в клопе М\ можно выбрать с не более чем с существенными внутренними неременными. Выбирая число с из расширенного натурального ряда, пополненного наибольшим элементом оо, всякий d-подклон будем считать (с, (¿)-подклоном при с = оо. В связи с проблемой конечной порождаемое™ клонов представляет интерес

Теорема 2.4. Для любых натуральных cud, где d ^ 2, всякий (с, d)-клон конечно порождаемый. Его порядок не превосходит maxdSC2 — 1,с + d+ 1), а степень не превосходит max(|.E|c+1, d + 2).

Утверждение данной теоремы было известно ранее лишь при с = 0 в части, касающейся конечной порождаемое™.

Далее в работе получена предикатная характеризация (с, й)-клонов.

Будем говорить, что га-местная функция }{х¡,...,х„) из Ре сохранянет по

набору своих переменных Xit,... ,Хіс, где {ii,...,ic} С {1,...,п}, гтг-арный 2-предикат (р, q), если для любых наборов Х\,..., Хп из і?"' верно следующее: всякий раз когда наборы X,,,..., Хіс удовлетворяют предикату q, набор ..., Хп),

полученный последовательным выписыванием значений функции /, вычисленных от строк матрицы (Xf,..., удовлетворяет предикату р.

Набор у из Ет будем называть особым набором т-арного предиката р, если этот набор не удовлетворяет предикату р, но для любого числа і, 1 ^ і ^ т, найдётся удовлетворяющий предикату р набор, отличающийся от набора у только г-й координатой. Если при этом предикат р совпадает с предикатом q, либо получен из него проектированием, возможно неоднократным, то 2-предикат (Ет \ (у},р) будем называть 2-редукцией предиката q (через Е"1\ {у} обозначен тп-ариый предикат, область истинности которого совпадает с одноимённым множеством).

Имеет место

Теорема 2.5. Пусть cud — натуральные числа, такие, что d ^ 2, и Mi — d-подклон клона Mi функций из Ре- Пусть также множество Y предикатов из Пе является и-описанием клона Мі так, что іпуеІМі) = 'pol^(^). Тогда равносильны условия:

(1) клон Mi является (с,д)-подклоном клона Мг;

(2) для любого г > d всякая функция из М2 по некоторому набору своих переменных, содержащему не более с переменных, сохраняет все г-арные 2-редукции предикатов из Y;

(3) для любого г > d всякая частичная функция из Pg, имеющая доопределение в клоне Mi, по некоторому набору своих переменных, содержащему не более с переменных, сохраняет все г-арные 2-редукции предикатов из У.

Далее изучаются (с,г)-разложения (с, с£)-клонов, при с = 0 аналогичные чистым и при с = г близкие к смешанным ^-разложениям, введённым в работах С. С. Марченкова и изучавшимся также в работах А. Б. Уголышкова.

Говорят, что клон Mi (с,г)-разлагается над клоном М\, если для любой функции / из Л/2, зависящей от п ^ г неременных, найдутся / ^ с чисел ¿і,... , г; в множестве {1,... ,п} и функция g в клоне Mi, зависящая от I + Q переменных, такие, что

f{x) = g(x',..., J(xlr),..., f{x\+1),..., /(4),..., f(xrr-%

где через х обозначен набор переменных х\,... ,хп, через х' обозначен набор переменных Хц,...,Хіи через Xj при 1 < г <] < г обозначен набор неременных 2?i,.. .,Xj-i,Xi,Xj+i, ...,хп. Доказана

Теорема 2.6. Для любых натуральных dur, таких, что d ^ 2 и г = |£,|i' +1, и любого с из расширенного натурального ряда всякий клон функций из Ре (с, г)-разлагается над любым своим (с,ё)-подклоиом.

Ранее был известен аналог этой теоремы для чистых ¿¿-разложений и клопов с мажоритарной функцией (что соответствует случаю с = 0 в теореме 2.6).

Результаты второй главы опубликованы в следующих работах автора: теоремы 2.1 - 2.4 - в [4], теоремы 2.5 и 2.6 - в [7].

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

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

Прежде всего, найдены и-описания клона Ml монотонных функций на верхней нолурешётке L (то есть функций, сохраняющих её упорядочение клона Ql квазимонотонных функций (имеющих монотонную миноранту), клона <Е>£ слабо существенных квазимоиотоиных функций (имеющих одноместную монотонную миноранту), а также клопа Фl П Ml слабо существенных монотонных функций.

Пусть

е{т)(хи .. ,,хт) = Зх(х < Х\ Л • • • Ах ^ хт),

е^ ^ , . . . , хгт) =

= £Г(т)(Ж1, . . . ,хт) V £{т){хт+1, ..., х2т) V ... V £(т)(ж(г_1)т+ь • ■ • ,хгт). Теорема 3.1. Имеют место равенства

ту£(д£) = 1ПУьро1Н£(,(Ь))), туЬ{МЬ) = ту^ро^«,^»).

Теорема 3.2. Имеют место равенства

тУ£(Ф£) = ту£ роГ£(£(9(£)Д), еШ'2\ ■■■),

ту£(М£ П Фь) = ро1Ь«,е^г-).!),е(«(£).2)>...).

Теорема 3.1 согласуется с тем, что клоны Мь и <5^ содержат мажоритарную функцию от д(Ь) + 1 переменной и являются конечно порождаемыми (это известно из работ Деметровича), а в соответствии с теоремой 3.2 монотонная часть является 2-нодклоном в клоне <5х, и (1,2)-подклоном в клоне Ф^; в частности, клоны М^ПФ^ и Ф/, являются (1, 2)-клонами и, следовательно, конечно порождаемые. В диссертации монотонная мажоритарная функция и специальные монотонные функции для слабо существенных квазимонотонных функций указаны явно. Сформулированные свойства в том числе открывают возможности для решения задач синтеза в указанных клонах на основе (с, г)-разложения функций. Далее изучаются точечные функции.

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

/(а) = £Да'),

а'

где суммирование ведётся по всем наборам а! из Еп, таким, что а' ^ а. Точечная функция, сохраняющая множество Е, называется минимальной точечной. Классы точечных и минимальных точечных функций обозначаются через Т^ и Ш1п(Т^) соответственно. Устанавливаются некоторые свойства этих классов.

Теорема 3.3 устанавливает, что точечные функции с одинаковым числом переменных образуют полурешетку.

Теорема 3.4 устанавливает критерий точечности, откуда получается

Следствие 3.3, утверждающее о существовании в любом базисе последовательности схем сложности 0(\L\n) и глубины 0(п2) для распознавания точечно-сти заданной вскторно n-местной функции из Pi,

Схему линейной сложности можно получить также методом A.A. Воропенко и методом В. Б. Алексеева.

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

Теорема 3.5. Каждый замкнутый класс точечных функций из Ti включён в некоторый максимальный такой класс; множество последних конечно.

Следствие 3.4. Каждый замкнутый класс минимальных точечных функций из minTi включён в некоторый максимальный такой класс; множество последних конечно.

Построены примеры максимальных клонов в множествах 7/, и min Ti в случае, когда L есть полурешётка интервалов решетки (Е, =<:).

В этом случае элементами нолурешётки L являются интервалы [а, 6] решетки Е, где а и 6 — элементы из Е, такие, что а =4 Ь. При этом в множестве L определены два упорядочения — полурешёточное ^ и решёточное =<:, такие, что

[а, 6] < [с, d] (с а и b 4 d), [а, b} 4 [с, d] <ä> (а с и b d)

для элементов а, Ь,с и d из Е, таких, что а 4 b и с ^ d. Доказано

Следствие 3.7. Пусть (L, — решётка и (L, — полурешётка интервалов решётки (Е, Клопы и polx,(=^, Е) являются максимальными по включению среди включённых в соответствующие классы Ti точечных и minT^ минимальных точечных функций.

Далее рассматриваются проблема форм представления в классе minT^.

Прежде всего, явно описывается класс функций на трёхэлементной полурешёт-кс ¿2 = {0,1, Т} (непустых подмножеств множества Е-i = {0,1}), вычисляемых формулами в каноническом базисе из операций —i, V, А ( — это точечные продолжения па полурешётку Ei одноимённых булевых операций) и дизъюнктивными формами различного вида. Рассматриваемый случай трёхэлементной нолурешётки — принципиально важный, поскольку наборами сё элементов описываются динамические (то есть изменяющиеся и в разной степени определённые) состояния комбинационных схем с двоичными статическими (то есть неизменными и полностью определёнными) состояниями.

Понадобятся некоторые определения. Для набора х = {х\,... ,хп) переменных и набора а = (аі,..., ап) значений из множества {0,1, Т} положим

ха = х*1 Л-- - Лхап",

где хЧ' есть ->Хі,Хі, 1 или ХіЛ-^Хі при соответствующем значении аг, равном 0,1, Т или Для непустого множества А наборов а1,..., ат из множества {0,1,Т}"\ {Т}" формулу

xа' V ... V ж0™

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

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

Теорема 3.6. указывает условия, при которых произвольная функция вычисляется заданной днф, откуда получается

Следствие 3.8. Функция / из множества рої^^,^, {Т}), зависящая от п переменных, тогда и только тогда вычисляется некоторой днф, когда выполняются условия /_1(0) =1 /-1(1) и (1) ф 0.

В частности, всякая отличная от констант 0 и 1 минимальная точечная функция / вычисляется сокращённой днф

хк, где К = тах(/_1(1),

и в отличие от двоичного случая это единственная тупиковая дф для функции /, минимальная как по числу конъюнкций, так и по суммарному числу букв в них.

Далее рассматриваются дф, в которых любая конъюнкция содержит все переменные, причём хотя бы одну дважды — с отрицанием и без него. Такие дф называются далее дф с повторениями.

Теорема 3.7. указывает условия, при которых произвольная функция вычисляется заданной дф с повторениями, откуда получается

Следствие 3.9. Всякая функция /:££—» {0,Т} из класса роІ^Д^, {Т}) вычисляется некоторой дф с повторениями.

Теорема 3.8. указывает условия, при которых произвольная функция вычисляется дф хс, где С С (ЁТ2 \ {Т}") и ({0,1, _1_}п \ {0,1}"), с конъюнкциями двух типов, откуда получается

Следствие 3.10. Имеют место равенства классов:

[У,Л,Н = ро1^«,£:2,{Т}) и [0,1, V, Л, -і] = [тіпТу = роІ£2(<, Еі).

Далее изучается проблема форм представления в классе mini/,, где L — дистрибутивная точечная полурешетка. В частности, на основе предложенного метода формульного представления установлено, что класс minT^ порождается своими двухместными функциями. Рассмотрим подробнее этот результат.

Полурешётка L называется дистрибутив)юй, если таковой является решётка L' = L U {_L}, полученная присоединением наименьшего элемента _L. Полурешст-ка называется точечной, если каждый сё элемент является суммой некоторых минимальных сё элементов. К числу дистрибутивных точечных относится полурешётка Et непустых подмножеств множества = {0,... ,к — 1}. Наборами ее элементов описываются динамические состояния схем с fc-ичными статическими состояниями.

Пусть в дистрибутивной точечной полурешётке L выделено подмножество С С L, включающее все минимальные элементы полурешётки и называемое специальным, а для каждого элемента с из специального множества С задана с-специаль-ная функция — двухместная квазимонотонпая функция *с из Ql со свойствами

1) х *с х = х для всех х из L;

2) х *с (х + с) = (х + с) *с х = х для всех х из L таких, что хс =

В диссертации предлагается рекурсивный метод разложения для формульного представления квазимонотонпых функций из Ql в базисах, содержащих все слабо существенные функции из Ф^ и набор специальных функций *с, с 6 С, а также для представления минимальных точечных функций из min Ti в бинарных базисах, содержащих одноместные функции из min Т^ и набор специальных функций (2)

из min . На основании предложенного метода установлена

Теорема 3.9. Пусть L — дистрибутивная точечная полурешётка. Тогда

Ql = [Ф£и(шт min Тс, С [(minT^j.

Отдельно рассмотрен случай полурешетки Еь непустых подмножеств множества

Теорема 3.10. Пусть L = Ek. Тогда

Ql = [Фl U {V}], minTb С [(minTL)(1) U {V}].

Здесь дизъюнкция есть точечная функция, ограничение которой определено на множестве Ek = m'm(Ek) как Х\ V а;2 = max(:ri,x2).

Результаты третьей главы получены автором в работах [23) (теоремы 3.1 и 3.2), [12] (следствие 3.7) и [25] (остальные теоремы и следствия) на основании результатов более ранней работы [1]. Некоторые предварительные результаты получены в [15, 18, 23].

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

Напомним некоторые определения. Пусть множество А функций из Р^ включает все селекторы. Клоны, включающие множество А С Р^, называются А-кло-иами. Проблема А-полиоты в клоне В, где А С В, состоит в описании всех порождающих А-клоп В подмножеств X С В, порождающих его с использованием операций суперпозиции и функций из множества А так, что В = \ХиА]. Инструментом решения этой проблемы является критериальная для А-клоиа (иначе — А-критериальная для клона) В система. Так называется система 5 А-клонов, собственным образом содержащихся в клоне В, если всякий Л-клон, собственным образом содержащийся в клоне В, можно расширить до некоторого клона из 5. А-критериальная система Б называется безызбыточной, если она не содержит пары сравнимых но включению клонов и совпадает тогда с системой 5(Л, В) всех максимальных А-клонов среди строго содержащихся в В, в остальных случаях лишь включенной в 5. Представляют интерес условия, позволяющие выделять клоны А-критериалыюй системы (по-возможиости конечной и безызбыточной).

Сначала рассмотрен наиболее общий случай А =

Предложено для решения проблемы полноты в клоне В использовать множество А (В) предикатов из Щ, обладающих свойствами В-предельности но проектированию, отождествлению, сужению и симметризации. Это означает, что всякий предикат р из А (В) неинвариаптсн для клона В, а всякий отличный от р предикат, полученный из него проектированием, отождествлением переменных, сужением (— пересечением с некоторым инвариантным для клона В предикатом) или симметризацией (— пересечением с перестановочно эквивалентным предикатом) уже инвариантен для клона В. Доказана

Теорема 4.1. Система клопов ВПро1^(р), где р 6 А (В), является критериальной для клопа В. Эта система конечная, если клоп В конечно порождаемый.

В качестве средства выделения подклонов в клоне, в том числе максимальных при решении проблем полноты, предложено наряду с предикатными описаниями

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

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

Теорема 4.2. Пусть К и В — клопы функций из Р1, такие, что К С В, а множество У предикатов из ШУ£,(К) \ ¡пу£(Б) является расширенным и-описаиием клона К в клоне В. Тогда равносильны условия:

1) клоп К не является максимальным подклоном клона В;

2) включения К С В Г) ро1£($) С В выполняются для некоторого предиката

Я = <?о П «71 П ... П

где предикат до инвариантен для клопа В, а предикаты <71, • • -, (?г перестановочно эквивалентны некоторым предикатам из У.

Использование теоремы 4.2 иллюстрирует

Пример 4.1. Пусть в — подстановка на множестве Ь простого порядка р без неподвижных точек. В примере 4.1 показано, что расширенное и-описание клона ро1ь(78) «-самодвойственных функций из Рь, сохраняющих график 78 подстановки й, составляют предикаты 7,., 1 ^ г ^ р — 1. На основании этого с использованием теоремы 4.2 установлена максимальность в Р^ нодклона ро1£(73), известная ранее из теоремы Розенберга.

Далее выделен частный случай, имеющий многочисленные приложения.

5-предельный по проектированию, симметризации и сужению предикат называется В-простым, если он один составляет и-описание некоторого нодклона в клопе В (тогда расширенное и-описание). Доказана

Теорема 4.3.Пусть предикат р является В-простым. Тогда подклон В Г) ро¡¿(р) является максимальным в В. Также в этом случае для любого В-пре-делъного по проектированию и отождествлению предиката д равенство В П ро1л(р) = В П ро1£(д) означает перестановочную эквивалентность предикатов р и д и, в частности, влечёт В-простоту предиката д.

Использование этой теоремы иллюстрируют

Примеры 4.2 - 4.6. В примерах 4.2 - 4.5 установлено, что Р£-простым является: график подстановки на Ь, разлагающейся в произведение независимых циклов длины 2; предикат нетривиального отношения эквивалентности на Ь\ предикат решёточного порядка; отличный от диагонали центральный, симметричный и вполне рефлексивный предикат. В примере 4.6 установлено, что предикат полурешёточного упорядочения ^ множества Ь является В-простым, если В 6 {С^^, Ф£}, откуда следует максимальность монотонных частей в клонах и Ф^.

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

Элемент с из множества Ь будем называть слабо центральным для гп-местного предикатар из Щ, если замена любой компоненты в любом удовлетворяющем предикату р наборе значением с приводит к набору, удовлетворяющему предикату р. Предикат, для которого элемент с является слабо центральным, назовём с-слабо-цеитральным предикатом. Предикат, для которого некоторый элемент является слабо центральным, сам называется слабо центральным. Доказана

Лемма 4.4. Для произвольного клона К функций из Рследующие условия равносильны:

(1) всякую частичную функцию из Р£, имеющую доопределение в клоне К, можно доопределить до функции из К значением с;

(2) клон К вместе с любой функцией / содержит и всякую функцию д /;

(3) клоп К описывается посредством некоторого множества У с-слабо-цен-тральных предикатов из Щ, такого, что К = ро^(У).

Здесь неравенство д >с / означает, что функция д получается из функции / заменой некоторых её значений значением с.

Клон К, для которого выполняются условия (1) - (3) леммы 4.4, называется слабо центральным или, точнее, с-слабо-цеитралъпым. Иными словами, произвольный клон является с-слабо-центральным, если он включает (наименьший по включению такой) клон ро1£(И^), описываемый множеством всех с-слабо-центральных предикатов и совпадающий в двоичном случае с одним из клонов неразделённых либо разделённых булевых функций. В диссертации установлены некоторые свойства слабо центральных клонов, связанные с конечной иорождае-мостью и нредикатоной описуемостью, рассмотрены примеры.

Пусть А(А,В) — множество инвариантных для А и одновременно В-иредель-ных но проектированию, отождествлению, сужению и симметризации предикатов.

Лемма 4.5 устанавливает В-простоту предикатов из множества Л(Л, В) для слабо центрального клона А. Имеет место

Теорема 4.4. Пусть А и В — с-слабо-центральные клоны, такие, что АС В. Тогда клоны В П д Є А(А,В), составляют безызбыточпую А-крите-

риальную систему для клона В. Для любых предикатов р и д из множества Л(Л, В) равенство клонов ЯПроІ^р) = ВПро1£(<?) равносильно перестановочной эквивалентности предикатов р и д.

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

Пусть є -- система подмножеств множества Ь, обладающая свойствами

(1) (свойство наследственности) если некоторое множество принадлежит системе ё, то и всякая его часть принадлежит г;

(2) (свойство слабой центральности для с) если множество Я принадлежит системе ё, то множество Я и {с} также принадлежит ей.

Говорят, что функция / из Рі, зависящая от п переменных, сохраняет систему ё, если для любого натурального т, любых наборов Х\,...,Хп из Ьт и набора Ха = /И (Л" \,...,Хп) (значений функции /, вычисленных от строк матрицы (Х{,..., множество Хо принадлежит системе є всякий раз, когда множества Х\,... ,Хп принадлежат ей. (Здесь для произвольного набора А = (Лі,..., Ат) через А обозначается множество {/Ц,..., Лт}.) Функции из Рі, сохраняющие систему ё, составляют с-слабо-центральный клоп, обозначаемый через С^^ё).

Функцию / назовём слабо существенной, если для некоторого г, 1 ^ г ^ гг, для любого натурального т и любых наборов Хо,... ,Хп из Ь'п, таких, что Хо = і,..., Хп) множество Х0 принадлежит системе ё всякий раз, когда множество Хі принадлежит ей. Слабо существенные функции из P¿ составляют с-сла-бо-центральный клон, включённый в С}ь(ё) и обозначаемый через Фі(є).

Клоны фі(є) и Фі(є) представляют интерес благодаря своим приложениям. В том числе они совпадают с клонами С^ь квазимонотоиных и Ф^ слабо существенных квазимонотонных функций на нолурешёткс Ь, если в качестве системы ё взять систему всех подмножеств с нижней гранью в полурешётке Ь. Кроме того, показано, что (предиолный но теореме Розенберга) клон функций из Рі, описываемый отличным от диагонали центральным, вполне рефлексивным и симметричным предикатом, совпадает с клоном для некоторой системы ё. Имея ввиду указанные приложения клонов С2ь{ё) и далее будем использовать для них соответствующие обозначения <3х, и Фі,; вместо д(ё) будем писать ц(Ь).

Далее решена проблема ф£-полноты в клоне <2і-

Для набора V = (УЇ,..., Ут) из Ь,п обозначим через II(У) систему всех таких подмножеств и С {1,... ,т}, что множество {У|г Є и} не принадлежит системе

є; через Щ(У) обозначим систему минимальных но включению подмножеств из и(У)\ определим т-местный предикат ру как ру(Х) = и(Х) С и (У).

Будем называть компоненту У} набора У несущественной, если для любого подмножества и С {1,... , то} выполняется равносильность

и и {Я Є и [У) и (У).

Будем называть подобными г-ю и ]-ю компоненты У и У} набора У, если для любого подмножества и С {1,..., т} выполняется равносильность

и и {г} € и {У) О и и {Л Є [/(У).

Будем называть их различными подобными компонентами при іф 3.

Обозначим через Т^ множество всех таких наборов У из Ь'п (при произвольных натуральных т), что выполняются условия:

(1) |Е/о(У)| > і;

(2) набор У не содержит несущественной компоненты;

(3) если в наборе У имеются различные подобные компоненты и набор У получен из набора У удалением любой из них, то |С/0(У)| = 1-

Критерий Ф^-полноты в клоне даёт

Теорема 4.5. Клоны <3£Проору), где У Є Т¿, составляют безызбыточную Ф¿-критериальную систему для клона

Для наборов У = (Уи ... ,Уп) и г = (£ь ..., гт) из Т£ равенство

Яь п рої ¿(ру) = <5І П рої ¿(р2)

имеет место тогда и только тогда, когда п = т и для некоторой подстановки а на множестве чисел 1,... ,п верно, что и (У) = где 2а = (^а(1),...,г„ы)-

Далее получены мощностные оценки построенной безызбыточной Ф^-критери-альпой системы в классе <3г квазимонотонных функций на полурешётке Ь = Ёк (в индексах обозначаемой через к).

Теорема 4.6. При к > 2 имеют место неравенства:

В частности, при к —> оо имеет место асимптотичекое соотношение

Результаты четвертой главы опубликованы в следующих работах автора. Теоремы 4.1 - 4.3 получены в [9], теоремы 4.4 и 4.5 — в [И], теорема 4.6 — в [5] на основании более раннего результата [2). Предварительные результаты получены в [13, 14, 15, 17].

Пятая глава называется «Проблемы полноты для трехзначных квазимонотонных функций». В ней рассматриваются функции из Р2 (здесь и далее в индексах вместо Е2 пишем 2) на трехэлементной полурешётке Е2 = {0,1, Т}, решаются проблемы выразимости множества minT^ в классе М2, проблемы полноты в классах AI2 и Q2-

Через А и В обозначаются классы polg а и polj ß функций из Р2, сохраняющих соответствующие предикаты

а(хих2,хл) = [e(2)(xi,x2) Ve^Ori,^)] Ae(-2)(x2,xi) и ß(xuxi) = (хих2) ф (0,1).

Через Cqj, C\j и Су обозначаются классы polgCfO, Т}),ро1§({1, Т}) и polü({T}).

Критерий выразимости множества min Т2 в классе М2 даёт

Теорема 5.1. Для произвольного множества F функций из М2 тогда и только тогда имеет место включение [F] Э min Т2, когда множество F не включено ни в один из классов А, В, Cqj, Cij и Cj.

Через Сод обозначается класс polg({0,1}) функций из Р2, сохраняющих унарный предикат {0,1}. Критерий полноты в классе М2 даёт

Теорема 5.2. Произвольное множество функций из класса М2 тогда и только тогда является полным в нём, когда оно не включено пи в один из классов А В, Cqj, Cij, Cr и Сод. Пересечения указанных классов с классом М2 образуют шесть предполиых в М2 классов.

Напомним, что в замкнутом классе К функций из Pl нредполный класс, содержащий все одноместные функции из называется классом Слупецкого.

Критерий Q1^ '-полноты в классе Q2 даёт

Теорема 5.3. Пусть F С Q2. Система F U Q?,1' тогда и только тогда полна в классе Q2, когда она не включена в класс А. В частности, единственным классом Слупецкого е классе Q2 является класс Q2 П А.

Критерий полноты в классе Q2 даёт

Теорема 5.4. Произвольное множество квазимонотонных функций из класса Q2 тогда и только тогда является полным в нём, когда оно не включено пи в один из классов А, В, Со,т, Ci,Ti Су, Сод и М2. Пересечения указанных классов с классом Q2 образуют семь предполиых в Q2 классов.

Теоремы 5.1 - 5.2 доказаны конструктивными методами, которые можно использовать в алгоритмах синтеза квазимонотонных, монотонных или минимальных точечных функций в произвольных базисах.

Результаты пятой главы получены в [3] на основе [16].

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

Установлена сильная предупорядоченность относительно подстановки переменных ряда функциональных пространств (следствия 1.4 - 1.6), в том числе пространства переключательных функций с ^-замыканием.

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

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

В связи с проблемой конечной порождаемое™ выделено новое семейство конечно порождаемых клонов — содержащих конечно порождаемый ё,- или произвольный (с, с£)-подклон при натуральном с (теоремы 2.2 - 2.4). Клоны с (с, (¿)-под-

клонами охарактеризованы свойствами инвариантных предикатов (теорема 2.5). Установлена возможность (с, г)-разложсний клона над (с, ¿)-нодклоном, известная ранее лишь в случае с = 0.

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

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

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

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

Для функций на трёхэлементной полурешетке найдены: безызбыточная нижняя окрестность множества минимальных точечных функций в клоне монотонных функций (теорема 5.1), безызбыточные критериальные системы в клонах монотонных (теорема 5.2) и квазимонотонных (теорема 5.4) функций.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[13] Парватов Н.Г. О иолиотс систем монотонных функции для реализации квазимонотонных функций на конечных полурешетках // Новые информационные технологии в исследовании дискретных структур. Доклады третьей Всероссийской конференции с международным участием. (Томск, 2000 год) Научное издание. Томск: ТНЦ СО РАН, «Спектр», 2000. С. 70-74.

[14] Парватов Н.Г. О полноте в классе квазимонотонных функций на конечных полу решётках // Материалы VII Международного семинара «Дискретная математика и ее приложения» (Москва, 2001 г.). Часть I. М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2001. С. 114-117.

[15] Парватов Н.Г. К синтезу комбинационных схем с заданным динамическим поведением из элементов произвольной функционально полной системы // Автоматизация проектирования дискретных систем. Материалы 4-й международной конференции (Минск, 2001 год). Минск: Институт технической кибернетики НАН Беларуси, 2001. Т.2. С. 74-77.

[16] Парватов Н. Г. Функциональная полнота в классах квазимопотонных и монотонных функций на трехэлементной полурешетке // Материалы XIII Международной конференции «Проблемы теоретической кибернетики». Часть I, II. М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002. С. 143-144.

[17] Парватов Н.Г. О функциональной полноте в классе квазимопотонных функций на конечной гюлурешеткс // Материалы XV Международной школы-семинара «Синтез и сложность управляющих систем» (Новосибирск, 18-23 октября 2004 г.). Под редакцией О. В. Лупанова. Новосибирск: Изд-во Института математики, 2004. С. 65-67.

[18] Парватов Н.Г. О формах представления монотонных и квазимопотонных функций на трёхэлементной полурешетке // Материалы IX Международного семинара «Дискретная математика и ее приложения», носвящёшюго 75-летию со дня рождения О. Б. Лупанова (Москва, 18-23 июня 2007 г.). Под редакцией О. М. Касим-Заде. М.: Изд-во механико-математического факультета МГУ, 2007. С. 170-173.

[19] Парватов Н.Г. Проблема выразимости в полной решётке с замыканием // Материалы XVII Международной школы-семинара «Синтез и сложность управляющих систем» (Новосибирск, 27 октября - 1 ноября 2008 г.). Под редакцией О. Б. Лупанова. Новосибирск: Изд-во Института математики, 2008. С. 127-130.

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

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

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

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

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

[25] Парватов Н.Г. Точечные и сильно точечные функции на полурешётке // Прикладная дискретная математика. 2010. №3. С. 22-40.

Подписано к печати 09.02.2012. Формат 60x84/16. Бумага «Снегурочка». Печать XEROX. Усл.печ.л. 1,86. Уч.-изд.л. 1,68 _Заказ 114-12. Тираж 100 экз.__

Томский политехнический университет Система менеджмента качества Томского политехнического университета сертифицирована NATIONAL QUALITY ASSURANCE по стандарту ISO 9001:2008

ИЗДАТЕЛЬСТВОW ТО. 634050, г. Томск, пр. Ленина, 30

Тел./факс: 8(3822)56-38-63, www.lpu.ru

Введение

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] на различных этапах проектирования таких систем.

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.