О классах функций k-значной логики, замкнутых относительно операций суперпозиции и перестановки

Оглавление
Введение 3
1. Определения, свойства, вспомогательные утверждения 8
2. Операция перестановки типа I
с множеством нулевых угловых наборов 19
2.1. Замкнутые классы в Рк.......................................... 19
2.2. Замкнутые классы в Р2 и Р2......................................24
2.3. Ослабленная операция перестановки...................................29
3. Операция перестановки типа I ...............
с произвольным множеством угловых наборов 30
3.1. Ослабленная операция перестановки...................................30
3.1.1. Замкнутые классы трехзначной логики...........................30
3.1.2. Примеры континуальных семейств . . . . '..................78
3.2. Замкнутые классы в Рк...............................................80
3.3. Замкнутые классы в Р2 и Рз.........................................81
4. Ослабленная операция перестановки типа II 98
4.1. Примеры континуальных семейств .....................................98
4.2. Функции вида .......................................................98
4.3. .Г-функции.........................................................102
4.4. Основные утверждения...............................................108
Л итература 110
5
Введение
Настоящая работа относится к теории функциональных систем — одного из основных разделов дискретной математики. В ней рассматривается задача об изучении свойств замкнутых классов функций к-значной логики.
Э. Пост описал все замкнутые (относительно операции суперпозиции) классы булевых функций и показал, что каждый замкнутый класс имеет конечный базис, а множество всех таких классов счетно (31, 32). Описание множества замкнутых классов булевых функций содержится также в [8, 9, 23, 24, 30]. Многозначные логики во многом похожи на двухзначную логику и в них сохраняется ряд результатов, имеющих место в двухзначной логике. Среди таких результатов можно отметить решения проблемы функциональной полноты и задачи описания предполных классов (см. |2, 7, 10, 25, 26, 33-35]). В тоже время имеют место и существенные различия. К их числу относятся примеры Ю. И. Янова о существовании замкнутых классов в Рк (множестве всех функций ^-значной логики), не имеющих базиса, и А. А. Мучника о существовании замкнутых классов в Рк со счетным базисом для всякого к ^ 3 (см. ]27, 28]). Из этих результатов, в частности, следует континуальность множества замкнутых классов в Рк при к ^ 3, что делает труднообозримой структуру данного множества.
Поскольку при к > 3 проведение в Ахзначной логике исследований по изучению множества замкнутых классов наталкивается на значительные трудности, многие авторы стали рассматривать задачу изучения классов, полученных, в результате применения более сильных операций замыкания, которые позволяли бы получить множество замкнутых классов счетной или конечной мощности. В работах [1, 4-6, 11-16, 20-22, 29] приведены классификации и свойства классов функций Л-значной логики, к ^ 2, замкнутых относительно операций, являющихся усилениями операции суперпозиции. При этом в работах [11-16] изучается операция 5-замыкания, в работах [5, 6, 29] — операция параметрического замыкания, в работах |1, 4, 20-22] — операции замыкания программного типа.
Идея операции 5-замыкания, где наряду с операцией суперпозицией разрешается применять операцию перехода к двойственным функциям относительно фиксированной группы подстановок, т.е. 5-замкнутый класс вместе с каждой функцией содержит двойственную относительно указанной группы подстановок функцию, высказывалась несколькими авторами. В настоящее время существуют две версии построения 5-классификации множества функций /г-значной логики (к ^ 3), представленные в работах С. С. Марчснкова (11-13) и Нгуен Ван Хоа (14 —16], где в частности з'станов-лено, что множество классов в данной классификации конечно, хотя и зависит от к сверхэкспоненциальным образом.
Понятия параметрической выразимости и параметрического замыкания введены А. В. Кузнецовым в работе [6]. В этой же работе получены критерий параметрической выразимости в /.-значной логике для всех к ^ 2 и конечное описание параметрически замкнутых классов булевых функций. Конечность множества параметрически замкнутых классов при к = 3 показана в работе А. Ф. Данильченко [5], а при к > 3 в работе С. Барриса, Р. Уилларда |29|. Кроме того в [5] построены все предполные классы в Р3.
В работе Ю.В. Голункова |4] изучаются вопросы полноты функциональнопредикатных систем с операциями замыкания программного типа (см. также |1|). В работах В.А. Тайманова [21, 22] и В.Д. Соловьева (20] исследуется семейство функци-
опальных систем Л-значной логики (к ^ 2) с операциями программного типа. Каждая операция программного типа определяется споим множеством предикатов. В работах [21, 22[ показано, что в зависимости от свойств указанных множеств предикатов мощность множества замкнутых классов может быть конечной, счетной или равняться мощности континуума. В случае конечного множества замкнутых классов приведено его полное описание, в случае счетного множества замкнутых классов показано, что каждый класс обладает конечным базисом, в случае континуального множества замкнутых классов представлены примеры классов со счетным базисом и классов без базиса, причем эти примеры совпадают с соответствующими примерами из [27, 28). В [20[ рассматриваются примеры конечных описаний множества замкнутых классов для некоторых операций программного типа.
Следует также отметить подход, состоящий в разбиении множества замкнутых классов /с-значной логики на классы эквивалентности, которые формируются на основе свойств входящих в них функций. Такой подход рассматривался Нгуеном Ван Хоа в работах [17-19|.
Из сказанного выше вытекает, что все перечисленные примеры операции замыкания, за исключением некоторых операций замыкания программного типа, приводят к конечному множеству замкнутых классов в Р* ПРИ к ^ 3. В связи с этим, представляется важным изучение таких усилений операции суперпозиции, которые, с одной стороны, не являются столь сильными, чтобы давать конечное множество замкнутых классов, а с другой стороны позволяют достаточно просто находить результат применения этих операций к функциям. К числу таких усилений операции суперпозиции можно отнести добавление к ней операции перестановки.
В настоящей работе исследуются классы &-значной логики, к ^ 2, замкнутые относительно операций суперпозиции и перестановки с множеством угловых наборов. То есть в каждом классе, замкнутом относительно этих операций вместе с каждой функцией содержатся и все функции получающиеся из исходной в результате применения к ней операции перестановки. Операция перестановки использует геометрическое представление функций и поэтому имеет достаточно простой способ вычисления по функции всех ее образов. Эта операция вводится при помощи понятия слоя. В работе изучается несколько модификаций операции перестановки.
Сначала рассматривается операция перестановки, при определении которой слой (слой типа I) задается как множество всех наборов одинаковой длины, содержащих фиксированное количество элементов равных 0,1,...,к — 1. В результате применения этой операции к произвольной функции /(хь... ,х„), на наборах внутри каждого слоя происходит перестановка значений данной функции, определяемая но следующему правилу. Для каждого слоя выбирается перестановка чисел от 1 до п и для каждого набора слоя новое значение функции / на нем совпадает с исходным значением функции / на наборе, получающимся из данного соответствующей перестановкой его компонент. В работе показано (см. главу 2), что в этом случае множество классов в /*, замкнутых относительно операций суперпозиции и перестановки, является конечным при всех к ^ 2. Таким образом, данная операция перестановки является слишком сильной. В связи с этим изучается ослабление этой операции за счет введения следующего ограничения. Операцию перестановки разрешается применять только к тем функциям, которые существенно зависят от всех своих переменных. Показано (см. главу 2), что при к = 2 мощность множества замкнутых классов конечна, а при к ^ 3 равна мощности континуума.
Далее в работе вводится понятие слоя относительно углового набора (т.е. набора, все компоненты которого принадлежат множеству {ОД- — 1}), и изучается (ослаблен-
ная) операция перестановки для этого нового определения слоя. При этом рассматриваемое ранее понятие слоя в новых терминах — слой относительно нулевого углового набора. Установлено (см. главу 3), что при к = 3 для любых множеств угловых наборов, удовлетворяющих определенным условиям (такие множества называются правильными, см. стр. 9), множество замкнутых классов счетно, а при к ^ 5 для произвольных множеств угловых наборов множество замкнутых классов является континуальным.
Кроме того, в работе рассматривается разбиение всех наборов на такие подмножества (слои типа II), которые содержат все наборы, находящиеся на фиксированном расстоянии от заданного углового набора. Изучается (ослабленная) операция перестановки с указанными понятием слоя при произвольных перестановках значений функций на наборах внутри каждого такого слоя. Отметим, что каждый слой типа II представляется в виде объединения некоторых слоев типа I. Показано (см. главу 4), что при всех к ^ 3 для любого множества угловых наборов определенного вида (см. стр. 9) множество замкнутых классов &-значной логики является счетным.
Дадим более точные определения понятия слоя и операции перестановки.
Положим Ек = {0,1,..., А: — 1}, ££ = Ек х ... х Ек, к ^ 2, п > 1. Набор (аь...,ап) из Е£ называется угловым, если а* € {0, к — 1}, г = 1,..., п. Слой определяется двумя способами.
I. Наборы (<5г,...,<5п), (7ь...,7п) принадлежат одному слою типа I относительно углового набора (вц,..., а„) тогда и только тогда, когда наборы (|<51 —ос\ |,..., |<5П-а„|), (|71 — аД,..., |7„ — ап|) содержат одинаковое число элементов, равных 0,1,..., к — 1.
И. Наборы (#1,..., <5П), (71,..., 7п) принадлежат одному слою типа II относительно углового набора (с*х,...,а„) тогда и только тогда, когда суммы элементов наборов (]6у - оД,..., |<5„ - а„|), (|71 -01|,..-,|7п-«п|) совпадают.
Заметим, что для произвольного углового набора а = (с*1,...,а„) любой слой тина I относительно а содержится в некотором слое типа II относительно а, при этом каждый слой типа II относительно а представляется в виде объединения слоев типа I относительно а. Вначале дадим общее определение операции перестановки в независимости от конкретного определения слоя, пользуясь лишь тем свойством, что любое разбиение на слои является разбиением множества Е% на непересекающиеся подмножества. Пусть у нас фиксированы функция /(«Рь...,£я) из Рк, угловой набор и разбиение множества ЕЦ на слои относительно этого углового набора. Тогда в результате действия на функцию /(ху,.. .,хп) операции перестановки с данным угловым набором и разбиением на слои можно получить функцию <р(х\,... ,£„) ИЗ Рк в том и только том случае, когда для каждого слоя q можно выбрать такое взаимно однозначное отображение ая наборов слоя q на себя, что функция <р(х1}хп) будет совпадать с функцией /(ая(ху,... ,хп)) на всех наборах этого слоя. Назовем операцией перестановки типа I и операцией перестановки типа II такие операции перестановки, дхя которых слой есть слой типа I и слой типа II соотвественно, причем в определении операции подстановки для случая операции перестановки типа I допускаются только такие взаимно однозначные отображения наборов слоя, в результате действия которых происходит перестановка компонент наборов этого слоя, а в определении операции перестановки для случая операции перестановки типа II взаимно однозначные отображения наборов слоя произвольны. В силу указанного выше свойства вложения слоев тина I в слои типа II и отсутствия ограничения на взаимно однозначные отображения, операция перестановки типа II является более сильной, чем операция перестановки типа I.
Операцию перестановки, которую разрешается применять только к функциям существенно зависящим от всех переменных, будем называть ослабленной операцией
перестановки.
Дадим краткое описание содержания глав диссертации.
В главе 1 приведены основные определения, свойства и вспомогательные утверждения.
В главе 2 рассматривается операция перестановки типа I с множеством угловых наборов О = {(0),(0,0),...}. В параграфах 2.1, 2.2 доказывается (Теорема 2.1.1), что любой класс в Р*, к ^ 2, замкнутый относительно операции суперпозиции и такой операции перестановки, порождается функциями от к переменных. Отсюда вытекает следствие (Следствие 2.1.2) о конечности множества всех таких классов. В теоремах 2.2.1, 2.2.2 приводится полное описание замкнутых классов в Р2 и Р3. В параграфе 2.3 операцию перестановки разрешается применять только к функциям существенно зависящим от всех переменных, т.е. рассматривается ослабленная операция иереста-новки. Показывается, что в этом случае в Р2 число замкнутых классов конечно (Теорема 2.3.1), а в Рк при к ^ 3 остается справедливым пример класса со счетным базисом из [27, 28), и, следовательно, множество замкнутых классов имеет мощность континуума (Теорема 2.3.2).
В главе 3 рассматривается операция перестановки типа I с произвольным множеством угловых наборов. При этом в параграфе 3.1 изучается ослабленная операция перестановки, а в параграфах 3.2, 3.3 операцию перестановки разрешается применять к произвольным функциям АхзначноЙ логики.
В параграф 3.1.1 исследуются классы трехзначной логики, замкнутые относительно операций суперпозиции и перестановки. Вначале доказывается, что существует множество П С Р3, которое при любом выборе множества угловых наборов замкнуто относительно операций суперпозиции и перестановки, а множество всех его подмножеств, замкнутых относительно этих операций, счетно (Теорема 3.1.1). Затем вводится понятие правильного множества угловых наборов, т. е. произвольного множества угловых наборов, содержащего подмножество вида {7п,<5п|гс ^ 2}, где уп € {0,2},*\{0'\2П}, £» € {0П,2П} для всех п ^ 2. Устанавливается, что для любого правильного множества угловых наборов произвольный замкнутый класс 21 С Р3 представим в виде объединения двух классов: замыкания множества всех трехместных функций из 21 и пересечения ПП21 (Теорема 3.1.2). Из теорем 3.1.1, 3.1.2 выводится основной результат параграфа 3.1.1 о счетности множества классов в Р3, замкнутых относительно операций суперпозиции и перестановки с произвольным правильным множеством угловых наборов (Теорема 3.1.3). В параграфе 3.1.2 доказывается (Теорема 3.1.4), что для произвольных множеств угловых наборов классы А:-значной логики, замкнутые относительно операций суперпозиции и перестановки, образуют континуальное множество при А; ^ 5.
В параграфах 3.2, 3.3 обобщаются результаты параграфов 2.1, 2.2 на случай операции перестановки с произвольным множеством угловых наборов, которую разрешается применять ко всем функциям Ахзначной логики. Показывается, что в Р* при А: ^ 2 любой класс, замкнутый относительно операций суперпозиции и перестановки с произвольным бесконечным множеством угловых наборов, порождается функциями от к переменных (Теорема 3.2.1), а множество всех таких классов конечно (Следствие 3.2.3). Кроме того, дзя указанного множества угловых наборов приводится полное описание замкнутых классов в Р2 и Рз (Теоремы 3.3.1-3.3.4). Поскольку операция перестановки типа II сильнее операции перестановки типа I, указанное выше утверждение о конечности множества классов, замкнутых относительно операций суперпозиции и перестановки с произвольным бесконечным множеством угловых наборов, при к ^ 2 выполняется и для операции перестановки типа II.
В главе 4 рассматривается ослабленная операция перестановки типа II с произвольным множеством угловых наборов. Для произвольного подмножества множества угловых наборов О и О, где О = {(А; — 1), (к — 1, к — 1),...}, в Р* при к ^ 3 справедливы примеры классов со счетным базисом из |27, 28|, и, следовательно, множество замкнутых классов имеет мощность континуума (Теорема 4.1.1). Заметим, что данное утверждение о континуальности множества замкнутых классов для множества угловых наборов ОиО при к ^ 3 справедливо и для операции перестановки типа I, поскольку операция перестановки типа II является более сильной операцией.
Далее в главе 4 вводится понятие т-регулярного множества угловых наборов, т. е. произвольного множества угловых наборов, содержащего подмножество вида {^72,.--.7т},гдс 6е {О2, (Аг — I)2}, 7„ € {0,£-1}п\{0п, {к-1)”} для всех п = 2,...,т. В параграфах 4.2-4.4 устанавливается, что для любого А*-регулярного множества угловых наборов множество классов в Рку к ^ 3, замкнутых относительно операций суперпозиции и перестановки, является счетным. Доказательство этого факта проводится в три этапа. В параграфе 4.2 изучается множество Р функций &-значной логики специального вида. Показывается, что Р содержит некоторое подмножество Ро, которое при любом выборе множества угловых наборов замкнуто относительно операций суперпозиции и перестановки, а множество всех подмножеств /'о, замкнутых относительно этих операций, счетно (Теорема 4.2.1). В лемме 4.2.3 представлено полное описание замкнутых подмножеств множества Ро. Кроме того, в параграфе 4.2 доказывается, что множество, состоящее из замыканий подмножеств множества Р| = Р\Р0 относительно операций суперпозиции и перестановки с произвольным множеством угловых наборов конечно, при этом указан способ построения конечных порождающих систем для каждого из этих замыканий (Теорема 4.2.2). В параграфе 4.3 исследуются свойства функций из множества Рк\Р (такие функции называются Р-функциями). Доказывается, что замыкание произвольной существенной Р-функции /(х\у...,хп) относительно операций суперпозиции и перестановки с произвольным А:*-регулярным множеством угловых наборов совпадает с множеством всех функций, принимающих значения из множества значений функции / (Теорема 4.3.1). В параграфе 4.4 из теорем 4.2.1, 4.2.2, 4.3.1 выводится основной результат главы 4 о счетности множества классов в Р*, А: ^ 3, замкнутых относительно операций суперпозиции и перестановки с произвольным А:*-регулярным множеством угловых наборов (Теорема 4.4.1), а также описание указанных классов (Следствия 4.4.1, 4.4.2).
В диссертации принята следующая нумерация теорем, лемм, следствия, утверждений и замечаний. Теоремы нумеруются тройками чисел, где первое число — номер главы, второе — номер параграфа, третье — номер теоремы внутри параграфа. Леммы и следствия нумеруются аналогичным образом. Утверждения (замечания) имеют двойную нумерацию: первое число — номер главы, второе — номер утверждения (замечания) внутри главы.
Основные результаты диссертации опубликованы в работах [36-40).
7
Глава 1
Определения, свойства, вспомогательные утверждения
Пусть Рк — множество всех функций Ахзначной логики, Ек = {0,1,...,к — 1}, Ап = А х ... х А — п-ая декартова степень произвольного множества А, к ^ 2, п ^ 1. Сначала дадим общее определение операции перестановки, в котором под слоем понимается некото|юе произвольное подмножество множества Е£, а разбиение на слои множества ££ есть произвольное разбиение на подмножества множества Е£ с двумя ограничениями: объединение всех слоев разбиения есть множество пересечение любых двух различных слоев разбиения есть пустое множество.
Определение. Пусть /(ад,...,хп) — произвольная функция из Рк, п ^ 1, к ^ 2; Я = {Их,...,Нп} — разбиение на слои множества /?£, где Я — число слоев, 71} — слой множества ££, j = 1,..., Л; <т; — взаимно однозначное отображение ножества всех наборов слоя Н] на себя, э = 1,..., Я, о = (<7ь..., ад). Будем говорить, что функция .. ,х„) получена из /(х\,..., х„) при помощи операции перестановки, если для любого набора 6 = (&х,..-,6п), принадлежащего слою 71}, ] — 1,...,/2, выполняется соотношение /«-й) = !(°т-
Везде далее мы будем пользоваться только двумя частными определениями операции перестановки. Для их задания нам потребуются определения углового набора и два частных определения слоя. Положим а" = (а,. , а) для всех а из Ек, п ^ 1.
п
Определение. Набор («1,..., огп) из Ек будем называть угловым набором, если а, принадлежит множеству {0, Л—1} для всех г = 1,..., п. Обозначим через С?* множество всех угловых наборов из Е%, (Зк = и О — 1Д {0"}, V* = и {0П, (к — 1)п}.
1 1 п^1
Определепие. Назовем (*0, *1, • • •, й-|)-м слоем типа I относительно углового набора 0П множество наборов из ££, каждый из которых содержит ^ элементов, равных ^ = 0,1,...- 1,1о + *1 + ... + гк-1 = п, п ^ 1.
Определение. Будем говорить, что множество наборов А С Ек, п ^ 1, А; ^ 2, составляет один слой типа I относительно угловою набора (аь..., с*п) из ф", если существует такой слой В типа I относительно углового набора 0", что набор (р\,..., рп) из Е£ принадлежит А тогда и только тогда, когда набор (\@\ — от),..., |/?„ — оп|) принадлежит В.
Замечание 1.1. Легко видеть, что для любого углового набора с* = (аь ..., а„) из
справедливы следующие утверждения. Любой слой типа I относительно а, содержащий наборы из множества {0,2}п, целиком содержится в этом множестве, а множество {1”} само является слоем типа I относительно а.
Обозначим через Я\ = Я\(п,к) число слоев типа I относительно углового набора 0П в Е%. Нетрудно показать, что число слоев типа I относительно любою угловою набора из (]% равно Я\ и Я\ = Для каждого угловою набора а из занумеруем слои
относительно а числами 0,1,..., Ях — 1 в некотором порядке.
Определение. Пусть /(х— функция из Рк, « = (ai,...,с*п) — угловой набор из Q£, aj ~ перестановка чисел 1,...,п, j = 0,...,Лі — 1, а — п ^ 1, ft ^ 2.
Будем говорить, ЧТО функция f°(x 1,. . ., Х„) получена ИЗ функции f(xI,..., х„) при помощи операции перестановки типа I с угловым набором а и набором перестановок а, если для любого набора (<5lt..., 6п), принадлежащего j-му слою типа I относительно d, j = 0,...,/?і — 1, выполняется соотношение = /(7ь• • • >7п), где
І7* “ «*1 = 1^(0 ~ <Ч(і)I Л-151 всех * = 1.• • ■ »я.
Будем говорить, что функция <?(хь... ,хп) получена из функции /(хi,...,xn) при помощи операции перестановки типа I с угловым набором а, если существует набор а = (оо,, (7щ-і) перестановок чисел 1,..., п такой, что д получается из / при помощи операции перестановки типа I с угловым набором а и набором перестановок а.
Определение. Назовем j-м слоем типа II относительно углового набора 0П множество наборов из ££, сумма элементов которых равна j, 0 ^ j ^ п(к — 1), п ^ 1, к ^ 2.
Определение. Будем говорить, что множество наборов Л С ££, ті ^ 1, к ^ 2, составляет один слой типа II относительно углового набора («|,... ,ап) из если существует такой слой В типа II относительно углового набора 0П, что набор (Д,..., /?п) из Е% принадлежит Л тогда и только тогда, когда набор (|/?i — 031,..., |/3„ — а„|) принадлежит В.
Обозначим через /?ц = Ru(n,k) число слоев типа II относительно углового набора О" в Е%. Легко видеть, что число слоев типа II относительно любого углового набора из равно Rn и Яц = п(к — 1) +1. Обозначим через 5ц{j, d) множество всех взаимно однозначных отображений множества всех наборов j-го слоя типа II относительно углового набора а из Qk на себя.
Определение. Пусть У(х|, • • •,хп) — функция из Рк, n ^ 1, к ^ 2,
а = («і,...,<*„) —угловой набор из Q£, oj — отображение из 5ц(у,a), j = 0,...,Я» — I,
О = (<70,...,<7дп_і).
Будем говорить, ЧТО функция /°{х 1,...,Х„) получена из /(Х|,...,ХП) при помощи операции перестановки типа II с угловым набором а и набором отображений <7, если для любого набора 8 = (8i,... ,6п), принадлежащею j-му слою типа II относительно d, j = 0..,Яц — 1, выполняется соотношение f°(8) = /{о3[8)).
Будем говорить, что функция д(хi,...,xn) получена из /(xi,...,xn) при помощи операции перестановки типа II с угловым набором а, если существует набор отображений (7 — (<70,...,<7я„-і)> Oj € 5n(jf, a), j = 0,..., Яц — 1, такой, что д получается из / при помощи операции перестановки типа II с угловым набором а и набором отображений о.
Определение. Пусть /(хь...,хп), д(хь...,хп) — функции из Ль, п ^ 1, к ^ 2, W — некоторое подмножество (конечное или бесконечное) множества угловых наборов Qk. Будем говорить, что функция д получена из / при помощи операции перестановки типа I (типа II) с множеством угловых наборов W, если существует набор а = (ori,...,an) из W такой, что функция д получается из функции / при помощи операции перестановки типа I (типа II) с угловым набором а.
Определение. Пусть '21 — некоторое подмножество функций из Рк, к ^ 2, W — некоторое подмножество (конечное ИЛИ бесконечное) множества угловых наборов Qk.