Критерий полноты и замкнутые классы мультифункций в полном частичном ультраклоне ранга 2 тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Бадмаев Сергей Александрович

• Бадмаев Сергей Александрович
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Бадмаев Сергей Александрович

функций

Глава 2. Замкнутые классы мультифункций в полном частичном ультраклоне ранга

§ 3. Минимальные частичные ультраклоны ранга

§ 4. Частичные ультраклоны К\ — К\2

Глава 3. Критерий полноты и максимальность классов К —

К \2

§ 5. Примеры полных множеств мультифункций

§ 6. Вспомогательные леммы

§ 7. Критерий полноты

Заключение

Список литературы

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

Введение

Теория функциональных систем занимает одно из главных положений в дискретной математике [3, 8, 21]. Конечнозначные функциональные системы наряду с теорией графов являются универсальным аппаратом описания конечных моделей в дискретной математике и математической кибернетике. Неслучайно C.B. Яблонский приравнивал роль функциональных систем в дискретной математике к роли математического анализа в непрерывной математике [41].

Наиболее часто рассматриваются функциональные системы, в которых функции определены на множестве Ek = {0,1,... ,k — 1} и принимают значения из этого множества. Такие функции принято назы-

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

k

ннй представляют исследования, связанные с подмножествами функций вместе с операцией суперпозиции. Традиционными задачами здесь являются получение эффективных критериев полноты и описание решетки замкнутых классов функций. Первые результаты в этом направлении были получены американским математиком Э. Постом [58, 59], который полностью описал решетку замкнутых классов булевых функций, что позволило установить ее счетность и решить проблему полноты. Позднее в [40] результаты Поста были изложены на функциональном языке, что позволило представить их в более доступной форме.

Результаты, полученные в двузначной логике, способствовали дальнейшему развитию исследований теории функций k-зпачпой логики. При этом выделяются два направления: первое связано с увеличением мощности основного множества, второе - с рассмотрением функций, которые определены не на всех наборах. Исследования по первому направлению получили развитие несколько раньше. В 1939 году Е. Слупец-кий предложил критерий полноты множества функций k-значной логики, которое содержит все унарные функции [68]. В дальнейшем C.B. Яблонский решил задачу о полноте для функций трехзначной логики, описав все предполные классы [38]. В 1956 году A.B. Кузнецов сообщил о конечности числа предполных классов для функций k-значной логики при любом k [9], различные семейства предполных классов получены в работах [12, 16, 39]. Окончательное решение проблемы полноты k

го века начинает развиваться другое направление, связанное с изучением функций, заданных не на всех наборах. Не всюду определенные функции удобно рассматривать как отображения из декартовой степени Ek в множество всех подмножеств причем одноэлементные подмножества отождествляются с элементами Ek, а остальные подмножества понимаются как неопределенности. Очевидно, что операция суперпозиции в обычном смысле для работы с этими функциями не подходит. Существует несколько способов расширения операции суперпозиции, каждый из которых позволяет находить значения суперпозиции на наборах с неопределенностями и, тем самым, порождает определенное подмножество функций 2k-3na4Hoft логики. В зависимости от вида и числа неопределенностей, а также измененной операции суперпозиции их называют частичными, недоопределенными, доопределяемыми, гиперфункциями, мультифункциями. Такие функции возникают при изучении многозначных логик, решении функциональных уравнений, моделировании схем с неисправностями [13, 22, 23, 30]. Естественно, что и для них также

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

Диссертация состоит из введения, трех глав, разбитых на 7 параграфов, заключения и списка литературы.

Во введении дается обоснование актуальности темы исследований.

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

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

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

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

По результатам, изложенным в диссертации, опубликованы 13 научных работ, отражающих основное содержание диссертации, в том числе

5 публикаций [71] - [75] в журналах из списка рецензируемых изданий, рекомендованного ВАК.

Совместные работы выполнены в неразделимом соавторстве. Конфликт интересов с соавтором отсутствует.

Результаты диссертации были представлены на семинаре «Актуальные вопросы вещественного и функционального анализа» (Улан-Удэ, 2014), XII Международном семинаре «Дискретная математика и ее приложения» имени академика О.Б. Лупанова (Москва, 2016), 5-ой российской школе-семинаре «Синтаксис и семантика логических систем» (Улан-Удэ, 2017), международной научной конференции «Мальцевские чтения» (Новосибирск, 2017), X Международной научной конференции «Дискретные модели в теории управляющих систем» (Москва, 2018), научном семинаре кафедры теоретической кибернетики Казанского федерального университета, а также неоднократно докладывались на семинарах Бурятского государственного университета и Иркутского государственного университета.

Исследования по теме диссертации выполнялись в рамках грантов РФФИ №18-31-00020 и Бурятского государственного университета.

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

Глава 1. Основные понятия и результаты

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

§ 1. Основные понятия и терминология

Параграф посвящен используемым в диссертации основным понятиям и обозначениям.

Пусть Еь = {0,1,... ,к — 1}. Для любого натурального п через обозначим п-ю декартову степень множества Е&. Элементами множества ЕП являются всевозможные упорядоченные наборы (ах,..., ап), которые называют к-ичными наборами, где а^ € Е при 1 < г < п. Набор (ах,..., ап) будем обозначать через а. Число п называют длиной набора и обозначают через |а|. Набор, состоящий только из нулей, называем ну-

0

1

кк функция, у которой как переменные, так и сама функция, принимают значения из множества Е^. Таким образом, если ](хх,..., хп) - функция к-зпачпой логики от п переменных, то / отображает множество Е~П в множество Е&. Функцию к-зпачпой логики от п переменных называют так-

п к п

функций на Еь обозначаем через также будем использовать обозначение Рь = и рП. Двузначные функции называются также булевыми

п>0

функциями или функциями алгебры логики.

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

пк

логики, имеет длину кп.

Переменная х» п-местной функции /(х1,...,хп) € называется фиктивной (несущественной), если для любыха1,... , 1, а»+1,...,ап из Ек выполняется равенство

](ах,... ,а»— 1,0,а»+1,... ,ап) = • • • = /(«1,..., а»—1, к — 1,а»+1,... ,ап).

В противном случае переменная х» называется существенной.

Для любого натурального п и любого г, 1 < г < п, обозначим через еП(х1,..., х»,..., хп) функцию к-значной логики, значения которой совпадают со значениями переменной х», т.е. у этой функции единственной существенной переменной является переменная х». Функции еп называются проекциями или селекторными функциями. Функцию е1 называют

х

Если для функций /(х1,..., хп) и д(х5+1,..., хп) при всех возможных значениях переменных х5+1,... , хп справедливо равенство

/(«1,..., а, х8+1,..., хп) = д(х8+1,..., хп),

то говорят, что функция д получена из функции ] подстановкой констант а1,..., вместо перемеиных х1,..., х8.

Если для функций f (х1,..., хп) и д(х, х5+1,... , хп) при всех возможных значениях переменных х5+1,..., хп справедливы равенства

/(0,..., 0, х8+1,..., хп) = д(0, х8+1,..., хп);

](к — 1,..., к — 1, х8+1,..., хп) = д(к — 1, х8+ь ..., хп),

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

Рассмотрим функцию /(х1,...,хп) € Р& с фиктивными переменными х1,..., х5 и функцию д (х5+1,...,хп) € Р&, получающуюся из ] подстановкой констант а1,..., а8 вместо первых в переменных. Так как переменные у функции ] фиктивные, то результат подстановки будет

один и тот же для любых а1,..., а8. Поэтому полагаем, что д(х8+1,..., хп) = I(0,..., 0, х5+1,..., хп).

Будем говорить, что функция д получена из функции I удалением фиктивных переменных х1,..., х5, а функция / получена из функции д добавлением фиктивных переменных х1,..., х5.

Каждое из трех определений выше очевидным образом распространяется на случай произвольных переменных х»1,..., х»8.

к

ривать их с точностью до существенных переменных.

Если I(х1,..., хп) - п-местная функция к-значной логики, то остаточными функциями (подфункциями) от функции / по переменной х» называются (п—1)-местпые функции, обозначаемые и определяемые следующим образом:

(т1 , . . . , Тп—1) = / (т1, . . . , , ^ ^ . . . , тп—1)

для любого (т1,... ,тп—1) € Е^1. Если а» = 0, то остаточная функция называется нулевой остаточной, если а» = 1, то единичной остаточной.

Суперпозицией с внешней функцией f (х1,... ,хп) € Р& и внутренними функциями /1(х1,..., хт),... , /п(х1,..., хт) € Р& называется выражение

I(/1(хЬ . . . ,хт), . . . ,/п(хЬ . . . ,хт)),

которое определяет функцию д(х1,...,хт) € Р& следующим образом:

для любого набора (а1,..., ат) € Е^ значений перемеиных х1,..., хт

д

д(аъ... , ат ) = I (/1(а1,... , ат ),... ,1п(а1,... ,ат)).

Так как для любого г € {1,..., п} значение 1»(а1,..., ат) принадлежит

Е&, то это определение является корректным и позволяет однозначно

д

функций 1,11,..., 1п.

Замыканием множества функций к-значной логики К называется

к

КК

обозначается через [К]. Множество функций к-значной логики К называется замкнутым (замкнутым классом), если К = [К].

Говорят, что множество В полно в замкнутом множестве К, если [В] = К. При К = Рь говорят просто, что В - полное множество. Е к

к

держащее все селекторные функции.

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

функций.

КЕ

К 'на Еь такого, что К с К 'с Рь.

Наряду с понятием максимального клона используется совпадающее

К

К=Р

/ € К выполняется

[К и {/}] = РА. к

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

Е Е

отображение / : Еп ^ Еь и {0}. Обозначим множество всех частичных функций к-значной логики через Р*.

Суперпозиция частичных функций

I (I (хх,... , хт ), . . . ,/п(хх, . . . ,хт))

определяет некоторую частичную функцию $(хх,..., хт) следующим образом: если (ах,..., ат) € Е™, то

0^и /г(ах,... ,ат) = 0 для некоторого г;

#(ах,..., ат) = <

[ I(/1(ах,... ,ат),...,/п(а1,... ,ат)), иначе.

Следующим шагом стало исследование гиперфункций и мультифунк-ций на Е^.

Пусть Е - множество мех подмножеств Е&, в том чиеле 0. Отображение вида / : Еп ^ Е \ {0} называется п-местной гиперфункцией на Еь, а отображение вида / : Е^ ^ Е - п-местной мультифункцией на Е&.

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

I (/х (хх,... , хт ), . . . ,/п(хх, . . . ,хт))

задает некоторую гиперфункцию #(хх,... , хт), если для любого набора (ах,..., ат) € Ет значение гиперфункции $(хх,..., хт) вычисляется по одному из двух правил:

для суперпозиции 1-го вида:

0(аь... ,ат) = и I (&ъ...,&т);

Ь»€/г(а 1,...,а„)

для суперпозиции 2-го вида:

( П I (&Ъ...,Ьт), если П I (Ьх,...,Ьт) = 0;

^(ах, . . . , ат) = < .

I и I (ьъ ..., Ьт), иначе.

V Ьг€/г(а1,...,а„)

Суперпозиция мультифупкций

I (Л (хх,...

, хт ), . . . ,/n(Xl, . . . ,хт))

д(х1, . . . , хт)

(а1,..., ат) € Ет значение мультифункции д(х1,..., хт) вычисляется по одному из двух правил:

для суперпозиции 1-го вида:

{0, если 1»(а1,... ,ат) = 0 для некоторого г; и I(Ь1 ,...,Ьп), иначе;

Ьг€/г(а1,...,ат)

для суперпозиции 2-го вида:

0, если 1»(а1,... ,ат) = 0 для некоторого г;

п I(Ь1 ,...,Ьп), если ПI(&1,...А) = 0;

Ьг€/г(а1,...,ат)

У I(Ь1,..., Ьп), иначе.

^ Ьг€/г(а1,...,ат)

д(«1,... ,ат) = <

г

ся п-местная гиперфункция (мультифупкция) еп такая, что для любых а1,..., ап из Е^ верно

еп(аь... ,ап) = {а»}.

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

к

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

Далее дадим определения гиперклона, мулы иклони, ультраклона и частичного ультраклона на Е&.

Гиперклоном на множестве Е^ называется любое множество гипер-

функций, содержащее все гиперпроекции и замкнутое относительно операции суперпозиции 1-го вида.

Мультиклоном на множестве Ek называется любое множество муль-тифункций, содержащее все мультипроекции и замкнутое относительно операции суперпозиции 1-го вида.

Ультраклоном па множестве Ek называется любое множество гиперфункций, содержащее все гиперпроекции и замкнутое относительно операции суперпозиции 2-го вида.

Частичным ультраклоном на множестве Ek называется множество мультифункций, содержащее все мультипроекции и замкнутое относительно операции суперпозиции 2-го вида.

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

Пусть Rs - s-местный предикат, заданный на множестве F. Будем говорить, что мультифункция f (xi,..., xn), определенная на множестве F, сохраняет предикат Rs, если для любых наборов

(aii,... ,asi),..., (ain,... ,asn), принадлежащих предикату Rs, набор

(f (an,..., ain),..., f (asi,..., aSn))

принадлежит Rs.

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

Для упрощения записи используется кодировка: 0 ^ *, {0} ^ 0, {1} ^ 1, {0,1} ^ —, тогда F = {*, 0,1, -}.

E2

рез P2—5 а частичный ультраклон, состоящий из всех мультифункций на

Е2 через Р2*.

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

Пусть предикаты Я и Я', определенные на Р, заданы матрицами М и М 'размерное ти п х т. Предикаты Я и Я' будем называть двойственными, если для любых ау € М и в«^ € М', где г € {1,...,п}, ^ € {1,..., т}, выполняются следующие условия: если ау = 0, то ву = 1; если ау = 1 то = 0; если ау = *, то = * если ау = —, то = —•

Функцию из Р2* будем задавать ее значениями на двоичных наборах, причем вектор значений функции будем записывать в виде строки или столбца, а двоичные наборы будем считать заданными в соответствии с натуральным порядком. Например, I = (0 * — 1) означает, что I(00) = 0, I(01) = *, I(10) = —, I(11) = 1. Также рассматриваются нульместные функции, которые будем называть константными и обозначать 0 1 * и (—), а также (00) (11) (**), (—).

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

выражение I(д(х1, х2), ^(х1, х2)) = (—1 — 1) будем кратко записывать

I (д(х1,х2 ),й(хьх2)) = (—1).

Для набора (а1,..., ап) € (Р\ {*})п набор (в1,..., вп) € {0,1}п, где в» — а» для всех г € {1,..., п}, называется уточнением.

§ 2. Замкнутые классы функций k-значной логики и мультифункций

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

Для систем функций двузначной логики с операцией суперпозиции основные результаты в этом направлении связаны с американским математиком Э. Постом, который описал решетку замкнутых классов и показал, что каждый замкнутый класс имеет конечный базис, а множество всех таких классов счетно [58, 59]. В нашей стране данные результаты в более простой форме были представлены в работе [40], а также С.С. Марченковым в [19] и A.B. Угольниковым в [32]. Отметим результаты А. И. Мальцева [14, 15], предложившего алгебраический подход.

Для функций k-зпачпой логики при k > 3 критерий функциональной полноты предложил Е. Слупецкий [68]. C.B. Яблонский [37, 38] решил задачу о функциональной полноте в множестве функций трехзначной логики и описал все 18 предполных классов. Конечность числа пред-

k

вым [9]. Некоторые типы предполных классов были получены C.B. Яблонским [39], В.В. Мартынюком [16], Ло Джукаем [12]. Описание всех предполных классов функций из Pk было завершено И. Розенбергом [62, 63]. Отметим также работу Ю.И. Янова, A.A. Мучника [42], в которой было доказано, что в Pk существуют замкнутые классы со счетным базисом, а также замкнутые классы, не имеющие базиса. Следствием этого результата является континуальная мощность множества замкнутых классов функций k-значной логики при k > 3.

Для описания замкнутых классов часто используется предикатный подход. Первые работы связаны с именем М.И. Краснера [52, 53]. Также одним из первых предикатный подход для описания замкнутых классов предложил A.B. Кузнецов [10, 11]. Предикатный подход оказался настолько эффективным, что стал одним из основных (см., например, [20], [64], [50]).

Среди замкнутых классов функций k-зпачпой логики выделяются, так называемые клоны - классы, содержащие все проекции [69]. Работы многих исследователей посвящены описанию различных фрагментов решетки клопов функций k-зпачпой логики, а также исследованию различных свойств клонов, среди которых отметим [2, 4, 5, 17, 18, 28, 45, 65, 69] и монографию D. Lau [51].

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

ЕП ^ Ek u 0,

где Ek = {0,1,..., k — 1}. Множество всех частичных функций k-зпачпой логики обозначается через P^-

Суперпозиция частичных функций

f (fi(xi,... , xm ), . . . ,fn(Xi, . . . ,Xm))

определяет некоторую частичную функцию g(xi,..., xm) следующим образом: если (ai,..., am) £ Em, то

. 0, если fi(ai,... ,am) = 0 для некоторого i; g(ai,..., am) =

f (fi(ai,.. .,0m),..., fn(öi,... ,öm)), иначе.

Работа [70] китайского математика Ван Сянхао - одна из первых по частичным функциям, в ней описаны все максимальные замкнутые классы в Р2* и Рз? н0 эти результаты долгое время были неизвестны математическому сообществу. Позднее Р.В. Фрейвалдом [33] получено

описание предполных классов в P2*, а D. Lau [49] и Б.А. Ромовым [29] описаны максимальные замкнутые классы в P3*. Окончательно решение проблемы функциональной полноты путем описания всех предполных классов в р* независимо друг от друга получили Ло Джукай [12] и L. Haddad, I.G. Rosenberg [48]. Все минимальные частичные клоны описаны в [43, 44]. Также отметим, что решетка клонов в р* даже при k = 2 континуальна [1].

Следующий шаг был сделан к исследованию гиперфункций - функций вида f : ЕП ^ 2Ek \ {0} и мультпфункций - f : E^ ^ 2Ek. Суперпозиция гиперфункций

f (fi (xi,. . . , xm ), . . . ,fn(Xi, . . . ,Xm))

для любого набора (а1,... , am) £ Em определяется одним из двух способов:

g(ai,..., flm) = U f (bi,...,bn);

0i£/i(a1,.";am)

Г П f(bi,...,bm), если nf(bi,...,bm) = 0;

n(n n \ _ J bi£/i(«1,...,«„)

I U f (bi,... , bm), иначе.

V bi£/i(aI,...,a„)

Для того, чтобы суперпозиция мультифункций

f (fi (xi,...

j xm ), . . . ,fn(xi, . . . ,Xm))

задавала некоторую мультифункцию g(xi,... , xm) обычно используется два способа определения суперпозиции:

для суперпозиции 1-го вида: если (ai,..., am) £ Em, то

{0, если fi(ai,... ,am) = 0 для некоторого i; IJ f(bi,...,bn), иначе;

bi£/i(a i,...,am)

для суперпозиции 2-го вида: если (ai,..., am) £ Em, то

#(аь ... ,ат) = <

0, если !г(ах,... ,ат) = 0 для некоторого г; П I(Ьх,...,Ьп), если ПI(Ьх,...,Ьп) = 0;

Ьг€/г(аЬ".;ат)

У I(Ьх,..., Ьп), иначе.

^ Ьг€/г(а 1,...,ат)

Из определений суперпозиций 1-го и 2-го видов следует, что множество всех мультифункций на Еь является подмножеством 2ь-значных функций, которые однозначно определяются своими значениями на множестве Еь. Нетрудно видеть, что данное подмножество не замкнуто относительно стандартной суперпозиции 2ь-значных функций, а суперпозиции 1-го и 2-го видов позволяют сохранить свойство замкнутости. Заметим, что если I, !х,..., I являются функциями к-зпачпой логики, то суперпозиции 1-го и 2-го видов работают в точности как стандартная суперпозиция функций к-зпачпой логики.

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

Все минимальные гиперклоны на двухэлементном множестве и муль-тиклоны на двухэлементном множестве описаны в [56]. Автором совместно с И.К. Шаранхаевым получено описание всех минимальных ультраклонов в Р2- и частичных ультраклонов в Р| в следующих утверждениях.

Теорема 1 ([71]) Существует ровно 8 минимальных ультраклонов на Е2

Теорема 2 ([71]) Существует ровно 12 минимальных частичных уль-Е2

Наиболее важные результаты при рассмотрении замкнутых классов

функций связаны с получением эффективных критериев полноты. Критерий полноты системы гиперфункций на двухэлементном множестве с суперпозицией 1-го вида сформулировал и доказал В.В. Тарасов в [31]. В работах [24, 25] В.И. Пантелеев получил описание всех максимальных мультиклонов ранга 2 и ультраклонов ранга 2, тем самым решив проблему полноты.

Решение задачи о полноте произвольной системы мультифункций в полном частичном ультраклоне ранга 2 решена автором в данной диссертации. Проведем обзор данных результатов.

Введем в рассмотрение следующие множества функций, содержащие все проекции:

1) К - множество, состоящее из всех функций, принимающих па пулевом наборе либо значение 0, либо значепне *.

2) К2 - множество, состоящее из всех функций, принимающих па единичном наборе либо значение 1, либо значе пне *.

3) - множество, состоящее из всех функций / для которых выполняется одно из двух условий:

• /(0) = ши / (1) = *;

• /(0) = 0 и /(1) = 1.

4) К4 - множество, состоящее из всех функций / таких, что на любом двоичном наборе а выполняется одно из трех условий:

• /(а) = /(а) = —

• /(а) = /(а) = *;

• /(а) = /(а), где/(а) е {0,1}.

5) К5 - множество, состоящее из всех функций / таких, что на лю-

а

• /(а) = ши /(а) = *;

• I(а) = I(а), где!(а) е {0,1}.

6) Ко = Р2— и {*}.

7) Кт = Р2*.

8) - множество всех функций I, одновременно удовлетворяющих трем условиям:

• если I(а), I(/3), I(7) е {0,1}, то

/а\ Г/0\ /0\ /0\ Д\

0

I

в

е

0 0

1

1 0

1 1

где а = (ах,..., ап), в = (в,..., вп), 7 = (7х,..., 7п) - двоичные наборы такие, что (а^7») е {(000), (001), (010), (111)} для любого г е {1,... ,п};

• если существует двоичный набор а такой, что I(а) = —, то для любого двоичного набора /3 верно I (/3) = 1;

• пусть двоичные наборы а = (ах,..., ап), в3 = (въ..., вп) такие, что а» < А Для всех г е {1,..., п}, тогда, если I(а) = *, то I(в3) = *.

9) Кд - множество всех функций I, одновременно удовлетворяющих трем условиям:

• если I(а), I(/3), I(7) е {0,1}, то

/а\ Г/0\ /ах /1\ /1\

I в е | 0 , 1 , 0 , 1

\7/ 1\0/ V1/ V/ V/

где а = (ах,..., ап), в = (А,..., вп), 7 = (7х,..., 7п) - двоичные наборы такие, что (а^7») е {(000), (011), (101), (111)} для любого г е {1,... ,п};

• если существует двоичный набор а такой, что I(а) = —, то для любого двоичного набора в верн о I (в) = 0;

• пусть двоичные наборы а = (а^..., ап), /3 = (въ..., вп) такие, что а < А Для всех я ^ {1,... , п} тогда, если /(/3) = *, то ](а) = *.

10) К10 - множество всех функций, сохраняющих предикат /00001111- а\

Я10 =

где (а, в, 7,^ _ всевозмож-

7

0 0 1 1 1 1 0 0 - в 0 10 110 10 - 7 \0 1101001 - ^

ные столбцы, в которых а, в, 7,^ ^ {0,1, —, *} одновременно удовлетворяют двум условиям:

• в любом столбце среди а, в, 7, ^ как минимум два принимают значение *;

• в любом столбце (авт^Д если среди а, в, 7, ^ встречается 0 или 1, то все они неравны

11) К11 - множество всех функций, сохраняющих предикат

/0 00110 0 - - 01 -****** Яп = 001010 - 0 - *** 01 - * * * *

\0 1 0 0 1 - 0 0 -****** 01 - */

12) К12 - множество всех функций, сохраняющих предикат

/001111 1 - - 01 Я12 = 010111 - 1 - *** 01 - **** \0 1101 - 1 1 - 01 - */

Теорема I ([27]) Классы К1 и К2 являются частичными ультраклонами ранга 2.

Теорема 3 ([74]) Каждый из классов К3 - К7 является частичным ультраклоном ранга 2.

Теорема 4 ([74]) Классы К8 и Кд являются частичными ультраклонами ранга 2.

Список литературы диссертационного исследования кандидат наук Бадмаев Сергей Александрович, 2019 год

Список литературы

[1] Алексеев, В. Б. О некоторых замкнутых классах в частичной двузначной логике / В. Б. Алексеев, А. А. Вороненко // Дискретная математика. — 1994. Т. 0. Вып. 4. — С. 58-79.

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

[3] Гаврилов, Г. П. Функциональные системы дискретной математики / Г. П. Гаврилов. — М.: Изд-во МГУ, 1985. — 39 с.

[4] Дудакова, О. С. О конечной порожденности предполных классов монотонных функций многозначной логики / О. С. Дудакова. // Мат. вопр. кибернетики. — М.: Физматлит, 2006. — № 17. — С. 13 104.

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

[6] Зубков, О. В. Некоторые замкнутые классы унарнопорожденных ультрафункций / О. В. Зубков // Известия Иркутского гос. университета. Серия Математика. — 2015. — Т. 12. — С. 35-48.

[7] Казимиров, А. С. Классификация и перечисление базисов клона всех гиперфункций ранга 2 / А. С. Казимиров, В. И. Пантелеев, Л. В. Токарева // Известия Иркутского гос. университета. Серия Математика. - 2014. - Т. 7. - С. 61-78.

[8] Кудрявцев, В. Б. Функциональные системы / В. Б. Кудрявцев. — М.: Изд-во МГУ, 1982. - 159 с.

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

[10] Кузнецов, А. В. Алгебра логики и ее обобщения / А. В. Кузнецов // Яновская С. А. Математическая логика и основания математики. Математика в СССР за сорок лет, т. 1. — М.: Физматгиз, 1959. — С. 13-120.

[11] Кузнецов, А. В. Структуры с замыканием и критерии функциональной полноты / А. В. Кузнецов // Успехи математ. наук. — 1961. — Т 1б _ №2 (98). _ С. 201-202.

[12] Ло Джукай, Теория полноты для частичных функций многозначной логики / Ло Джукай // Кибернетический сборник. Новая серия. — Вып. 25. - М.: Мир, 1988. - С. 142-157.

[13] Ложкин, С. А. О синтезе формул и схем из не всюду определенных функциональных элементов / С. А. Ложкин // Материалы VI международной конференции «Дискретные модели в теории управляющих систем». — М.: Изд-во ВМиК МГУ, 2004. — С. 44-47.

[14] Мальцев, А. И. Итеративные алгебры и многообразия Поста / А. И. Мальцев // Алгебра и логика. — 1966. — Т. 5. — № 2. — С. 5-24.

[15] Мальцев, А. И. Итеративные алгебры Поста / А. И. Мальцев. — Новосибирск: Изд-во НГУ, 1976. — 100 с.

[16] Мартынюк, В. В. Исследование некоторых классов в многозначных логиках / В. В. Мартынюк // Проблемы кибернетики. — Вып. 3. — М.: Физматгиз, 1960. — С. 49-60.

[17] Марченков, С. С. О замкнутых классах самодвойственных функций в Р3 / С. С. Марченков, Я. Деметрович, Л. Ханнак // Методы дискретного анализа в решении комбинаторных задач. — 1980. — Вып. 34. - С. 38-73.

[18] Марченков, С. С. О замкнутых классах самодвойственных функций многозначной логики / С. С. Марченков // Проблемы кибернетики. - Вып. 40. - М.: Наука, 1983. - С. 261-266.

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

[20] Марченков, С. С. Предполнота замкнутых классов в Р^: предикатный подход / С. С. Марченков // Математические вопросы кибернетики. — Вып. 6. — М.: Наука, 1996. — С. 117 132.

[21] Марченков, С. С. Функциональные системы с операцией суперпозиции/ С. С. Марченков. — М.: Физматлит, 2004. — 104 с.

[22] Пантелеев, В. И. Логика предикатов при обобщенной интерпретации переменных / В. И. Пантелеев, Н. А. Перязев // Вестник Бурятского университета. — 2005. — Серия 13. — Вып. 2. — С. 39-44.

[23] Пантелеев, В. И. Недоопределенные булевы функции и булевы уравнения / В. И. Пантелеев, Н. А. Перязев // Труды VII Международной конференции «Дискретные модели в теории управляющих систем- М: МАКС Пресс, 2006. - С. 262-265.

[24] Пантелеев, В. И. Критерий полноты для доопределяемых булевых функций / В. И. Пантелеев // Вестник Самарского гос. университета. Естественнонауч. серия. — 2009. — № 2 (68). — С. 60-79.

[25] Пантелеев, В. И. Критерий полноты для недоопределенных частичных булевых функций / В. И. Пантелеев // Вестник Новосибирского гос. университета. Серия: Математика, механика, информатика. — 2009. Т. 9. № 3. - С. 95-114.

[26] Пантелеев, В. И. О некоторых интервалах в решетке частичных ультрафункций / В. И. Пантелеев, С. Ю. Халтанова // Известия Иркутского гос. университета. Серия Математика. — 2010. — Т. 3, Л" 4. - С. 80-87.

[27] Пантелеев, В. И. О двух максимальных мультиклонах и частичных ультраклонах / В. И. Пантелеев // Известия Иркутского гос. университета. Серия Математика. — 2012. — Т. 5, № 4. — С. 46-53.

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

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

[30] Сапоженко, А. А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах / А. А. Сапоженко, С. А. Ложкин // Микроэлектроника. — 1983. — Т. 12. — Вып. 1. — С. 42-47.

[31] Тарасов, В. В. Критерий полноты для не всюду определенных функций алгебры логики / В. В. Тарасов // Проблемы кибернетики. — Вып. 30. - М.: Наука, 1975. - С. 319-325.

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

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

[34] Халбашкеева, Т. Ю. О некоторых частичных ультраклонах / Т. Ю. Халбашкеева // Материалы 4-й Российской школы-семинара «Синтаксис и семантика логических систем» (Улан-Удэ, 14-19 августа 2012). — Иркутск: Изд-во ФГБОУ ВПО «Восточно-Сибирская государственная академия образования», 2012. — С. 129-131.

[35] Халбашкеева, Т. Ю. Некоторые максимальные частичные ультраклоны ранга 2 / Т. Ю. Халбашкеева // Материалы 50-й между-

народной научной студенческой конференции «Студент и научно-технический прогресс». — Новосибирск, 2012. — С. 20.

[36] Халтанова, С. Ю. О двух изоморфных интервалах в решетке ультраклонов ранга 2 / С. Ю. Халтанова // Известия Иркутского гос. университета. Серия Математика. — 2014. — Т. 7. — С. 133-140.

[37] Яблонский, С. В. Вопросы функциональной полноты в k-значном исчислении: дне. канд. физ.-мат. наук / С. В. Яблонский. — 1953.

[38] Яблонский, С. В. О функциональной полноте в трехзначном исчислении / С. В. Яблонский // Докл. АН СССР. — 1954. — Т. 95. — № 6.

- С. 1153-1156.

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

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

[41] Яблонский, С. В. Введение в дискретную математику: Учеб. пособие для вузов / С. В. Яблонский; под ред. В. А. Садовничего. — 3-е изд., стер. — М.: Высш. шк., 2001. — 384 с.

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

[43] Borner, F. Minimal Partial Clones / F. Borner, L. Haddad, R. Poschel // Bulletin of the Austral. Math. Soc. — 1991. — Vol. 44. — No 3.

— P. 4G5-415.

[44] Borner, F. A Note on Minimal Partial Clones / F. Borner, L. Haddad, R. Poschel // Proceedings of 21th IEEE International Symposium on Multiple-Valued Logic (ISMVL). — 1991. — P. 262-267.

[45] Csâkâny, B. All Minimal Clones on the Three-Element Set / B. Csâkâny // Acta cybernetica. — 1983. — No. 6. — P. 227-238.

[46] DoroslovaCki, R. One interval in the lattice of partial hyperclones / R. DoroslovaCki, J. Pantovic, G. Vojvodic // Chechoslovak Mathematical Journal. — 2005. — No 55 (130). — P. 719-724.

[47] Drescher, Th. Multiclones and relations / Th. Drescher, R. Pöschel // Multiple-Valued Logic. — 2001. — No 7. — P. 313-337.

[48] Haddad, L. Completeness theory for finite partial algebras / L. Had-dad, I. G. Rosenberg // Algebra Universalis. — 1992. — Vol. 29. — No. 3. — P. 378-401.

[49] Lau, D. Eigenschaften gewisser abgeschlossener Klassen in Postschen Algebren / D. Lau. Dissertation A, WPU Rostock. — 1977.

[50] Lau, D. Submaximale Klassen von P3 / D. Lau // J. Inf. Process. Cybern. — 1982. EIK 18, 4/5. — P. 227-243.

[51] Lau, D. Function algebras on finite sets. A basic course on many-valued logic and clone theory / D. Lau. — Berlin: Springer-Verlag, 2006. — 668 p.

[52] Krasner, M. Remarque au sujet de "Une generalisation de la notion de corps" / M. Krasner // Journ. de Math. — 1938. — P. 367-385.

[53] Krasner, M. Generalisation abstraite de la theorie de Galois / M. Krasner // Colloques internationaux du Centre National R. S. Algebre et theorie des nombres. — Paris. — 1949. — V. 24. — P. 163-165.

[54] Machida, H. Hyperclones on a two-element set / H. Machida // Multiple-Valued Logic. An International Journal. — 2002. — No. 8(4). — P. 495-501.

[55] Machida, H. On maximal hyperclones on {0,1} - a new approach / H. Machida, J. Pantovic // Proceedings of 38th IEEE International Symposium on Multiple-Valued Logic (ISMVL). — 2008. — P. 32-37.

[56] Pantovic, J. Minimal partial hyperclones on a two-element set / J. Pantovic. G. Vojvodic // Proceedings of 34th IEEE International Symposium on Multiple-Valued Logic (ISMVL). — 2004. — P. 115119.

[57] Pantovic, J. On the partial hyperclone lattice / J. Pantovic. G. Vojvodic // Proceedings of 35th IEEE International Symposium on Multiple-Valued Logic (ISMVL). — 2005. — P. 96-100.

[58] Post, E. L. Introduction to a general theory of elementary propositions / E. L. Post // Amer. J. Math. — 1921. — V. 43. —No 4. — P. 163185.

[59] Post, E. L. Two - valued iterative systema of mathematical logic / E. L. Post // Annals of Math. Studies. — 1941. —No 5.

[60] Romov, B. A. Hyperclones on a finite set / B. A. Romov // Multiple-Valued Logic. An International Journal. — 1998. — No. 3(2). — P. 285-300.

[61] Romov, B. A. Partial hyperclones on a finite set / B. A. Romov // Proceedings of 32th IEEE International Symposium on Multiple-Valued Logic (ISMVL). — 2002. — P. 17-22.

[62] Rosenberg, I. G. La structure des fonctions de plusieurs variables sur un ensemble fini / I. G. Rosenberg // C. R. Acad. Sci. Paris. Ser. A. B. — 1965. — V. 260. — P. 3817-3819.

[63] Rosenberg, I. G. Uber die funktionale Vollstandigkeit in den mehrwertigen Logiken / I. G. Rosenberg. Roz pravy Ceskoslovenske Akad. Ved. Rada Mat. Prirod. Ved. — 1970. — No 80(4). — S. 3-93.

[64] Rosenberg, I. G. Completeness properties of multi-valued logic algebras / I. G. Rosenberg // Computer science and multivalued logic: Theory and Applications, second edition, D.C. Rine, ed., Amsterdam: North-Holland, 1984. — P. 144-186.

[65] Rosenberg, I. G. Minimal clones I: The five types / I. G. Rosenberg // Lectures in Universal Algebra (L. Szabo, A. Szendrei eds.), Colloq. Math. Soc. J. Bolyai 43, North Holland, 1986. — P. 405-427.

[66] Rosenberg, I. G. An algebraic approach to hyperalgebras / I. G. Rosenberg // Proceedings of 26th IEEE International Symposium on Multiple-Valued Logic (ISMVL). — 1996. — P. 203-207.

[67] Rosenberg, I. G. Multiple-valued hyperstructures / I. G. Rosenberg // Proceedings of 28th IEEE International Symposium on Multiple-Valued Logic (ISMVL). — 1998. — P. 326-333.

[68] Slupeski, J. Kryterium petnosci wielowartosciowych systemow logiki zdan / J. Slupeski. Comptes rendus des seances de la Societe des Sciences et des Lettres de Varsovie. Cl. III, 32, 1939, 102-109.

A criterion of fullness of many-valued systems of propositional logic // Studua Logica, 30. — 1972. — P. 153-157.)

[69] Szendrei, A. Clones in universal algebra / A. Szendrei. — Montreal: Les presses de l'universite de Montreal, 1986.

[70] Wang Xianghao, Structure theory of total and partial functions defined in a finite set / Wang Xianghao // Acta Sci. Natur. Univ. Jiliensis. — 1963. — V. 2. — P. 295-316.

Работы автора по теме диссертации

[71] Бадмаев, С. А. Минимальные частичные ультраклоны на двухэлементном множестве / С. А. Бадмаев, И. К. Шаранхаев // Известия Иркутского государственного университета. Серия Математика. — 2014. Т. 9. С. 3-9.

[72] Бадмаев, С. А. О максимальных клонах частичных ультрафункций на двухэлементном множестве / С. А. Бадмаев, И. К. Шаранхаев //

Известия Иркутского государственного университета. Серия Математика. - 2016. - Т. 16. - С. 3-18.

[73] Бадмаев, С. А. Об одном максимальном клоне частичных ультрафункций на двухэлементном множестве / С. А. Бадмаев // Журнал СФУ. Серия Математика и физика. — 2017. — Т. 10. — Вып. 2 С. 140-145.

[74] Бадмаев, С. А. О некоторых максимальных частичных ультраклонах на двухэлементном множестве / С. А. Бадмаев // Известия Иркутского государственного университета. Серия Математика. — 2017. - Т. 21. - С. 3-18.

[75] Бадмаев, С. А. Критерий полноты множества мультифункций в полном частичном ультраклоне ранга 2 / С. А. Бадмаев // Сиб. электрон. матем. изв. — 2018. Т. 15 С. 450-474.

[76] Бадмаев, С. А. О полных множествах частичных ультрафункций на двухэлементном множестве / С. А. Бадмаев // Вестник Бурятского гос. университета. Математика, информатика. — 2015. — №3. — С. 61-67.

[77] Бадмаев, С. А. О минимальных клонах частичных ультрафункций на двухэлементном множестве / С. А. Бадмаев, И. К. Шаранхаев // Материалы семинара «Актуальные вопросы вещественного и функционального анализа». — Улан-Удэ, 2014. — С. 16-17.

[78] Бадмаев, С. А. О некоторых минимальных ультраклонах / С. А. Бадмаев, И. К. Шаранхаев // Материалы XVII Международной конференции «Проблемы теоретической кибернетики». — Казань: Отечество, 2014. - С. 33-34.

[79] Бадмаев, С. А. Критерий полноты для частичных ультрафункций / С. А. Бадмаев // Тезисы докладов международной конференции «Мальцевские чтения». — Новосибирск, 2016. — С. 172.

[80] Бадмаев, С. А. О максимальных клонах частичных ультрафункций / С. А. Бадмаев, И. К. Шаранхаев // Материалы XII Международного семинара «Дискретная математика и ее приложения». — М.: Изд-во мех.-мат. факультета МГУ, 2016. — С. 185-187.

[81] Бадмаев, С. А. О двух максимальных частичных ультраклонах / С. А. Бадмаев // Материалы 5-ой российской школы-семинара «Синтаксис и семантика логических систем» — Улан-Удэ: Изд-во Бурятского гос. университета, 2017. — С. 14-17.

[82] Бадмаев, С. А. Об одном критерии полноты множества мул ьтифуикни и / С. А. Бадмаев, И. К. Шаранхаев // Тезисы докладов международной конференции «Мальцевские чтения». — Новосибирск, 2017. - С. 139-140.

[83] Бадмаев, С. А. Критерий полноты множества мультифункций в полном частичном ультраклоне ранга 2 / С. А. Бадмаев // Труды X Международной конференции «Дискретные модели в теории управляющих систем». — Москва, 2018. — С. 43-46.