Содержание к диссертации
Введение
1. Определения, свойства, вспомогательные утверждения 8
2. Операция перестановки типа I с множеством нулевых угловых наборов 19
2.1. Замкнутые классы в Р* 19
2.2. Замкнутые классы в Р2 и Р3 24
2.3. Ослабленная операция перестановки 29
3. Операция перестановки типа I с произвольным множеством угловых наборов 30
3.1. Ослабленная операция перестановки 30
3.1.1. Замкнутые классы трехзначной логики 30
3.1.2. Примеры континуальных семейств 78
3.2. Замкнутые классы в Р* 80
3.3. Замкнутые классы в Р2 и Р3 81
4. Ослабленная операция перестановки типа II 98
4.1. Примеры континуальных семейств 98
4.2. Функции вида Ffi 98
4.3. Р-функции 102
4.4. Основные утверждения 108
Литература 110
- Замкнутые классы в Р2 и Р3
- Замкнутые классы трехзначной логики
- Замкнутые классы в Р2 и Р3
- Функции вида Ffi
Введение к работе
Настоящая работа относится к теории функциональных систем — одного из основных разделов дискретной математики. В ней рассматривается задача об изучении свойств замкнутых классов функций А>значной логики.
Э. Пост описал все замкнутые (относительно операции суперпозиции) классы булевых функций и показал, что каждый замкнутый класс имеет конечный базис, а множество всех таких классов счетно [31, 32]. Описание множества замкнутых классов булевых функций содержится также в [8, 9, 23, 24, 30]. Многозначные логики во многом похожи на двухзначную логику и в них сохраняется ряд результатов, имеющих место в двухзначной логике. Среди таких результатов можно отметить решения проблемы функциональной полноты и задачи описания предполных классов (см. [2, 7, 10, 25, 26, 33-35]). В тоже время имеют место и существенные различия. К их числу относятся примеры Ю. И. Янова о существовании замкнутых классов в Р* (множестве всех функций &-значной логики), не имеющих базиса, и А. А. Мучника о существовании замкнутых классов в Рк со счетным базисом для всякого А; ^ 3 (см. [27, 28]). Из этих результатов, в частности, следует континуальность множества замкнутых классов в Рк при к ^ 3, что делает труднообозримой структуру данного множества.
Поскольку при к ^ 3 проведение в fc-значной логике исследований по изучению множества замкнутых классов наталкивается на значительные трудности, многие авторы стали рассматривать задачу изучения классов,.полученных в результате применения более сильных операций замыкания, которые позволяли бы получить множество замкнутых классов счетной или конечной мощности. В работах [1, 4-6, 11-16, 20-22, 29] приведены классификации и свойства классов функций А;-значной логики, к ^ 2, замкнутых относительно операций, являющихся усилениями операции суперпозиции. При этом в работах [11-16] изучается операция З'-замыкания, в работах [5, 6, 29] — операция параметрического замыкания, в работах [1, 4, 20-22] — операции замыкания программного типа.
Идея операции ^-замыкания, где наряду с операцией суперпозицией разрешается применять операцию перехода к двойственным функциям относительно фиксированной группы подстановок, т.е. /^-замкнутый класс вместе с каждой функцией содержит двойственную относительно указанной группы подстановок функцию, высказывалась несколькими авторами. В настоящее время существуют две версии построения S-классификации множества функций /г-значной логики (к ^ 3), представленные в работах С. С. Марченкова [11-13] и Нгуен Ван Хоа [14-16], где в частности установлено, что множество классов в данной классификации конечно, хотя и зависит от А; сверхэкспоненциальным образом.
Понятия параметрической выразимости и параметрического замыкания введены А. В. Кузнецовым в работе [6]. В этой же работе получены критерий параметрической выразимости в А;-значной логике для всех к ^ 2 и конечное описание параметрически замкнутых классов булевых функций. Конечность множества параметрически замкнутых классов при к = 3 показана в работе А. Ф. Данильченко [5], а при к > 3 в работе С. Барриса, Р. Уилларда [29]. Кроме того в [5] построены все предполные классы в Рз-
В работе Ю.В. Голункова [4] изучаются вопросы полноты функционально-предикатных систем с операциями замыкания программного типа (см. также [1]). В работах В.А. Тайманова [21, 22] и В.Д. Соловьева [20] исследуется семейство функци-
ональных систем Ахзначной логики (к ^ 2) с операциями программного типа. Каждая операция программного типа определяется своим множеством предикатов. В работах [21, 22] показано, что в зависимости от свойств указанных множеств предикатов мощность множества замкнутых классов может быть конечной, счетной или равняться мощности континуума. В случае конечного множества замкнутых классов приведено его полное описание, в случае счетного множества замкнутых классов показано, что каждый класс обладает конечным базисом, в случае континуального множества замкнутых классов представлены примеры классов со счетным базисом и классов без базиса, причем эти примеры совпадают с соответствующими примерами из [27, 28]. В [20] рассматриваются примеры конечных описаний множества замкнутых классов для некоторых операций программного типа.
Следует также отметить подход, состоящий в разбиении множества замкнутых классов /с-значной логики на классы эквивалентности, которые формируются на основе свойств входящих в них функций. Такой подход рассматривался Нгуеном Ван Хоа в работах [17-19].
Из сказанного выше вытекает, что все перечисленные примеры операции замыкания, за исключением некоторых операций замыкания программного типа, приводят к конечному множеству замкнутых классов в Pk при к ^ 3. В связи с этим, представляется важным изучение таких усилений операции суперпозиции, которые, с одной стороны, не являются столь сильными, чтобы давать конечное множество замкнутых классов, а с другой стороны позволяют достаточно просто находить результат применения этих операций к функциям. К числу таких усилений операции суперпозиции можно отнести добавление к ней операции перестановки.
В настоящей работе исследуются классы &-значной логики, к ^ 2, замкнутые относительно операций суперпозиции и перестановки с множеством угловых наборов. То есть в каждом классе, замкнутом относительно этих операций вместе с каждой функцией содержатся и все функции получающиеся из исходной в результате применения к ней операции перестановки. Операция перестановки использует геометрическое представление функций и поэтому имеет достаточно простой способ вычисления по функции всех ее образов. Эта операция вводится при помощи понятия слоя. В работе изучается несколько модификаций операции перестановки.
Сначала рассматривается операция перестановки, при определении которой слой (слой типа I) задается как множество всех наборов одинаковой длины, содержащих фиксированное количество элементов равных 0,1,...,А; — 1. В результате применения этой операции к произвольной функции f(xi,..., хп), на наборах внутри каждого слоя происходит перестановка значений данной функции, определяемая по следующему правилу. Для каждого слоя выбирается перестановка чисел от 1 до и и для каждого набора слоя новое значение функции / на нем совпадает с исходным значением функции / на наборе, получающимся из данного соответствующей перестановкой его компонент. В работе показано (см. главу 2), что в этом случае множество классов в Pk, замкнутых относительно операций суперпозиции и перестановки, является конечным при всех к ^ 2. Таким образом, данная операция перестановки является слишком сильной. В связи с этим изучается ослабление этой операции за счет введения следующего ограничения. Операцию перестановки разрешается применять только к тем функциям, которые существенно зависят от всех своих переменных. Показано (см. главу 2), что при к = 2 мощность множества замкнутых классов конечна, а при к ^ 3 равна мощности континуума.
Далее в работе вводится понятие слоя относительно углового набора (т.е. набора, все компоненты которого принадлежат множеству {0,к — 1}), и изучается (ослаблен-
ная) операция перестановки для этого нового определения слоя. При этом рассматриваемое ранее понятие слоя в новых терминах — слой относительно нулевого углового набора. Установлено (см. главу 3), что при к = 3 для любых множеств угловых наборов, удовлетворяющих определенным условиям (такие множества называются правильными, см. стр. 9), множество замкнутых классов счетно, а при к ^ 5 для произвольных множеств угловых наборов множество замкнутых классов является континуальным.
Кроме того, в работе рассматривается разбиение всех наборов на такие подмножества (слои типа II), которые содержат все наборы, находящиеся на фиксированном расстоянии от заданного углового набора. Изучается (ослабленная) операция перестановки с указанными понятием слоя при произвольных перестановках значений функций на наборах внутри каждого такого слоя. Отметим, что каждый слой типа II представляется в виде объединения некоторых слоев типа I. Показано (см. главу 4), что при всех к ^ 3 для любого множества угловых наборов определенного вида (см. стр. 9) множество замкнутых классов А;-значной логики является счетным.
Дадим более точные определения понятия слоя и операции перестановки.
Положим Ек = {0,1,..., к — 1}, Е% = Ек х ... х Ек, к ^ 2, п ^ 1. Набор (аь..., ап) из Е% называется угловым, если схі Є {О, к — 1}, г = 1,... ,п. Слой определяется двумя способами.
I. Наборы (5i,...,Sn), (7ь--ч7п) принадлежат одному слою типа I относительно углового набора (а\, ...,ап) тогда и только тогда, когда наборы (|«5г — а\\,..., \5п—ап\), (І7і — аі|,..., І7я — &п\) содержат одинаковое число элементов, равных 0,1,..., к — 1.
П. Наборы (5\,...,5п), (7г,..,7п) принадлежат одному слою типа II относительно углового набора (аі,...,ап) тогда и только тогда, когда суммы элементов наборов
(1*1 - «її, . \бп - «пі). (І7і - «ill і І7п - <хп\) совпадают.
Заметим, что для произвольного углового набора а = (ац,..., ап) любой слой типа I относительно а содержится в некотором слое типа II относительно а, при этом каждый слой типа II относительно а представляется в виде объединения слоев типа I относительно а. Вначале дадим общее определение операции перестановки в независимости от конкретного определения слоя, пользуясь лишь тем свойством, что любое разбиение на слои является разбиением множества на непересекающиеся подмножества. Пусть у нас фиксированы функция f{x\,... ,хп) из Рк, угловой набор и разбиение множества Е% на слои относительно этого углового набора. Тогда в результате действия на функцию f(x\,..., хп) операции перестановки с данным угловым набором и разбиением на слои можно получить функцию
Операцию перестановки, которую разрешается применять только к функциям существенно зависящим от всех переменных, будем называть ослабленной операцией
перестановки.
Дадим краткое описание содержания глав диссертации.
В главе 1 приведены основные определения, свойства и вспомогательные утверждения.
В главе 2 рассматривается операция перестановки типа I с множеством угловых наборов О = {(0), (0,0),...}. В параграфах 2.1, 2.2 доказывается (Теорема 2.1.1), что любой класс в Pfc, А; ^ 2, замкнутый относительно операции суперпозиции и такой операции перестановки, порождается функциями от А; переменных. Отсюда вытекает следствие (Следствие 2.1.2) о конечности множества всех таких классов. В теоремах 2.2.1, 2.2.2 приводится полное описание замкнутых классов в Р2 и Рз. В параграфе 2.3 операцию перестановки разрешается применять только к функциям существенно зависящим от всех переменных, т.е. рассматривается ослабленная операция перестановки. Показывается, что в этом случае в Р2 число замкнутых классов конечно (Теорема 2.3.1), а в Pk при А; ^ 3 остается справедливым пример класса со счетным базисом из [27, 28], и, следовательно, множество замкнутых классов имеет мощность континуума (Теорема 2.3.2).
В главе 3 рассматривается операция перестановки типа I с произвольным множеством угловых наборов. При этом в параграфе 3.1 изучается ослабленная операция перестановки, а в параграфах 3.2, 3.3 операцию перестановки разрешается применять к произвольным функциям А;-значной логики.
В параграфе 3.1.1 исследуются классы трехзначной логики, замкнутые относительно операций суперпозиции и перестановки. Вначале доказывается, что существует множество Л С Р3, которое при любом выборе множества угловых наборов замкнуто относительно операций суперпозиции и перестановки, а множество всех его подмножеств, замкнутых относительно этих операций, счетно (Теорема 3.1.1). Затем вводится понятие правильного множества угловых наборов, т. е. произвольного множества угловых наборов, содержащего подмножество вида {Їт5п\п ^ 2}, где % Є {0,2}п\{0",2П}, 5п Є {0П, 2П} для всех п ^ 2. Устанавливается, что для любого правильного множества угловых наборов произвольный замкнутый класс 21 С Р3 представим в виде объединения двух классов: замыкания множества всех трехместных функций из 21 и пересечения Г2 П 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.3.1-3.3.4). Поскольку операция перестановки типа II сильнее операции перестановки типа I, указанное выше утверждение о конечности множества классов, замкнутых относительно операций суперпозиции и перестановки с произвольным бесконечным множеством угловых наборов, при А; ^ 2 выполняется и для операции перестановки типа П.
В главе 4 рассматривается ослабленная операция перестановки типа II с произвольным множеством угловых наборов. Для произвольного подмножества множества угловых наборов О U О, где О = {(к — 1), (к — 1, к — 1),...}, в Pk при к ^ 3 справедливы примеры классов со счетным базисом из [27, 28], и, следовательно, множество замкнутых классов имеет мощность континуума (Теорема 4.1.1). Заметим, что данное утверждение о континуальности множества замкнутых классов для множества угловых наборов О U О при к ^ 3 справедливо и для операции перестановки типа I, поскольку операция перестановки типа II является более сильной операцией.
Далее в главе 4 вводится понятие m-регулярного множества угловых наборов, т. е. произвольного множества угловых наборов, содержащего подмножество вида {I72,...,7т}, где 5 Є {О2, (к-1)2}, 7п Є {0, к- 1}П\{0П, (*~ 1)п} Для всех п = 2,..., т. В параграфах 4.2-4.4 устанавливается, что для любого /^-регулярного множества угловых наборов множество классов в Pk, к ^ 3, замкнутых относительно операций суперпозиции и перестановки, является счетным. Доказательство этого факта проводится в три этапа. В параграфе 4.2 изучается множество F функций /г-значной логики специального вида. Показывается, что F содержит некоторое подмножество Fq, которое при любом выборе множества угловых наборов замкнуто относительно операций суперпозиции и перестановки, а множество всех подмножеств F0, замкнутых относительно этих операций, счетно (Теорема 4.2.1). В лемме 4.2.3 представлено полное описание замкнутых подмножеств множества Fq. Кроме того, в параграфе 4.2 доказывается, что множество, состоящее из замыканий подмножеств множества Fi = F\F0 относительно операций суперпозиции и перестановки с произвольным множеством угловых наборов конечно, при этом указан способ построения конечных порождающих систем для каждого из этих замыканий (Теорема 4.2.2). В параграфе 4.3 исследуются свойства функций из множества Pk\F (такие функции называются F-функциями). Доказывается, что замыкание произвольной существенной ^-функции f(xi,...,xn) относительно операций суперпозиции и перестановки с произвольным /^-регулярным множеством угловых наборов совпадает с множеством всех функций, принимающих значения из множества значений функции / (Теорема 4.3.1). В параграфе 4.4 из теорем 4.2.1, 4.2.2, 4.3.1 выводится основной результат главы 4 о счетности множества классов в Pk, к ^ 3, замкнутых относительно операций суперпозиции и перестановки с произвольным /^-регулярным множеством угловых наборов (Теорема 4.4.1), а также описание указанных классов (Следствия 4.4.1, 4.4.2).
В диссертации принята следующая нумерация теорем, лемм, следствия, утверждений и замечаний. Теоремы нумеруются тройками чисел, где первое число — номер главы, второе — номер параграфа, третье — номер теоремы внутри параграфа. Леммы и следствия нумеруются аналогичным образом. Утверждения (замечания) имеют двойную нумерацию: первое число — номер главы, второе — номер утверждения (замечания) внутри главы.
Основные результаты диссертации опубликованы в работах [36-40].
Замкнутые классы в Р2 и Р3
Вначале докажем общую лемму для Рк, к 2, которую в дальнейшем будем использовать при изучении свойств классов в / и Р3. Лемма 2.2.1. Пусть f(xi,...,хт), fi(xi,...,xtl),..., fr(xi,...,xtr) — произвольные функции из Pk, k 2, т 1, U 1, г = 1,...,г, г 1, 21 = {/,/ь-..,/г} о, д(х\,..., xk) — произвольная функция из Рк, такая, что для любого набора (ati,..., ak) из Ek выполняется соотношение где Тогда Є 21. Доказательство. Пусть /, /і,,/» 7, 21 удовлетворяют условиям леммы. Выберем среди чисел i,...,„ наибольшее и обозначим его через t. Пусть .,xti) добавлением несущественных переменных xti+i,... ,xt. Положим di(xi,.. .,xk) = (xSi,...,Xgi) для всех і = 1,..., А; , п = k + klr, J = J, где J = (2n — l)m. Рассмотрим функцию (а;і,.. .,хт,хт+і,.. .,Xj), получающуюся ИЗ f(Xi,.. .,Хт) добавлением несущественных Переменных Xm+i,...,Xj. Применим к функции р операцию перестановки с угловым набором 0J и набором перестановок а. За исключением перестановок, действующих на слоях, содержащих наборы а(а) = (аг,...,аг,а2,...,а.2, ,5 ь ,dk, fi{di{a)),...,ipi{di{a)): для любого а = (ai,...,ak) из Е%, все остальные перестановки из а тождественные. Для каждого a = (ot\,..., ак) из Е% перестановка, действующая на слое, содержащем набор а(а), переводит его в набор_(/?i,..., fim, ), где / Є Y(a\,..., а ; /і,..., /г) при г = 1,..., т, д(а) = f(@i, An)» f Є Е т. Такие перестановки на слое существуют, поскольку согласно лемме 2.1.1 все наборы вида (хъ , Хг Х2, , Хг, Хп, , Хп) 771 2т71 2п-1771 для различных (хі, , Хп) из Е% принадлежат разным слоям. Рассмотрим функцию Теорема 2.2.1. Множество классов в Р2, замкнутых относительно операций суперпозиции и перестановки типа I с множеством угловых наборов О = {(0), (0,0),...}, исчерпывается следующим списком: Р2, То, 7\, TQDTI, С, Ci, Со. Доказательство. Пусть 21 С Р2 и 21 = 21 е . Тогда класс 21 замкнут относительно операции суперпозиции. Все классы в Р2, замкнутые относительно операции суперпозиции, описаны, например, в [23]. Если 21 не содержит функций отличных от констант, то 21 — один из классов С, Со, Сі. Если же 21 содержит функции отличные от констант, то тогда классу 21 принадлежит функция х и согласно лемме 2.2.1 и теореме 2.1.1 класс То П Ті содержится в 21. В силу свойств операции перестановки справедливы следующие равенства Т0 о= Т0, Ті о= Ть ТоПТ1 с»= Т0 ПТі. Отсюда, поскольку [21] = 21 и То П Ті С 21, получаем, что 21 в данном случае совпадает с одним из классов Р2, То, Ті, То П Ті. Тем самым теорема доказана. Рассмотрим замкнутые классы в Р$. Из определения операции перестановки вытекает справедливость следующей леммы. Лемма 2.2.2. Пусть i, j Є Е3, і ф j, т Є {і, j}. Классы Tij, ТІ, Nmtij, Gij, С, Ctj, СІ замкнуты относительно операций суперпозиции и перестановки с множеством угловых наборов О. Лемма 2.2.3. Пусть 21 ф 0, 21 С Ръ, 21 = 21 0, 0,1,2 Є 21, f(xu...,xn) -произвольная функция из 21. Тогда 21 содержит все функции от трех переменных, принимающие значения из множества D(f). Справедливость леммы следует из леммы 2.2.1.
Лемма 2.2.4. Пусть 21 ф 0, 21 С Тц, 21 = 21 р, i,j Є Е3, i,j Є 21, f(xu...,xn) -произвольная функция из 21, g(xi,x2,x3) — произвольная функция из Р3, удовлетворяющая равенствам D(g) = D(f), D(g({i, j}3)) — D(f({i, j}n)). Тогда g Є 21. Справедливость леммы следует из леммы 2.2.1. Доказательство. Пусть 21, / удовлетворяют условиям леммы, и пусть і = 0, j = 1, А; = 2. 1. Так как 21 С Г0, 21 Тоь 21 g Т02, то 21 содержит функции рг Є Т0\Т0і и 1 Є То\7о2. Из определения функций (рі, грі следует, что классу [0, рі, фі] принадлежат функции щ(х) и vi{x) такие, что щ{1) = 2, г і(2) = 1. Тогда согласно лемме 2.2.1 класс {0,ui,v\,f} o содержит множество функций {д{х\,Х2,х3) Є То D(g) = D(f)}. 2. Из условия следует, что 21 содержит функцию гр2 Є {То П Тоі)\7о2. Из определения функции ір2 получаем, что классу [0, 2] принадлежит функция v2 (х) такая, что г 2(2) = 1. Тогда по лемме 2.2.1 класс {0, V2,f} o содержит множество {д(хих2,х3) Є Го П Т011 ОД = (/), D(g({0,1}3)) = D(/({0,1}"))}. 3. Согласно лемме 2.2.1 класс {0, /} с содержит множество Для любого другого набора (i,j,k), удовлетворяющего условию {i,j, k} = Е3, доказательство аналогично. Тем самым лемма доказана. Лемма 2.2.6. Пусть 21 ф 0, 21 С Р3, 21 = 21 с?, 0,1,2 21. Тогда Доказательство. Пусть 21 удовлетворяет условиям леммы. 1. Предположим, что 21 содержит функции /р. Т7, /rfc Tfc. Без ограничения общности можно считать, что /7 ., /rfc функции одной переменной. Отсюда получаем /гДО = /TJ(J ) = г, /rfc(0 = М (к) = г и /г,(/г (я)) = » , что противоречит условию. 2. Если 21 С Тк, то утверждение очевидно. Пусть 21 содержит функцию /тк(х) Т . Покажем, что тогда 21 С Т ПТІП TJ. Предположим, что 21 g Тг, г Є {i,j}. Пусть, для определенности, г = j. Тогда 21 содержит функцию JTJ{X) ф. Tj и, следовательно, /TJ(J) = і- Отсюда, согласно лемме получаем, что класс (/r,, /тк} о = 21 содержит константу г, что противоречит условию. 3. Из условия следует, что 21 принадлежат функции /г01 (х, у) Тої, /тц(х, у) . Ti2, /т02(х у) - ТОЇ- Предположим, что 21 содержит функции /гг(х) . Тт, /т,(х) - Т», г ф S, r,s Є Е3. Для определенности возьмем г = 1, s = 2. Возможны два случая. В первом случае /гДі) = /г2(2). Тогда /гДі) = /г2(2) = 0 и по лемме 2.2.1 класс {/т1,/г2} о содержит константу /тДО), что противоречит условию. Во втором случае /тДі) ф /т2(2). Тогда не ограничивая общности можно считать, что /ТІ(1) = 2. Согласно лемме 2.2.1 класс {/т2,/т1} е содержит функцию h(x) такую, что h(l) = /i(2) = /т2(2). Если /т2(2) = 0, то по лемме 2.2.1 класс {h} o содержит константу Л(0). Если /г2(2) = 1, то [h, /тц/гіг] содержит функцию д(х) такую, что д(1) = д(2) = 0. Тогда по лемме 2.2.1 класс {д} о содержит константу #(0), что противоречит условию. Тем самым лемма доказана. Доказательство. Пусть 21 удовлетворяет условиям леммы. a. Поскольку различных классов: 1. Классы, содержащие константы 0, 1, 2.
Замкнутые классы трехзначной логики
В настоящем параграфе для обозначения классов То, Ті в Р2 будем использовать символы TQ , Т соответственно. Введем следующие обозначения классов в Р3: 0\ — класс всех функций, которые принимают значение 1 на всех наборах имеющих хотя бы один элемент равным 1, и функций получающихся из данных добавлением несущественных переменных; R\ — класс всех функций из 7\ С\Т02, принимающих значение 1 только на наборе, состоящем из 1, и функций получающихся из данных добавлением несущественных переменных; SDti — класс всех функций, принимающих не более одного раза значение і, и функций получающихся из данных добавлением несущественных переменных, г Є Е3. Положим Xj(x) = Y(x) = Z?j(x) = y-(x) = j, {i,j} = {0,2}. Определим следующие множества функций: Х = {Х \п = 0,1,...}, Y = множества содержат также функции, получающиеся из данных путем переименования (без отождествления) переменных и добавления фиктивных переменных. Теорема 3.1.1. Пусть W — произвольное множество угловых наборов из Q$. Тогда ft = l w и мощность множества всех подмножеств ft, замкнутых относительно операций суперпозиции и перестановки с множеством угловых наборов W, счетная. Доказательство. Положим А\ = {XQ2} W, А28 = {YQ2} w, А = {%} w, Ai= {02} w, B\ = {X2Q} W,.B2S = {Y2%} W, Bl = {Z2Q} W, B\ = {Cs20} w, s = 1,2, Нетрудно показать, что для всех s 1, {i,j} — {0,2} классы [{Ху-}], [{ і }] [{ "}] [{ }]) [{ у}] совпадают (с точностью до переименования переменных и добавления фиктивных переменных) с множествами функций {Х ,Хф ... ,Х .,}, \Xij,Х , — , Л , Yij, — , ijj, x ijt ij-, і ij\i lAy» iji і t ij)- \Ziji tji iji Xij} соответственно. Пусть — множество, содержащее все наборы из Е$ с фиксированным числом единиц q, 1 q $С п, и только их. Тогда для любого углового набора (QJI, ... ,ап) справедливо следующее утверждение. Множество совпадает с объединением некоторых множеств, каждое из которых образует один слой относительно («і,..., ап). Поэтому, применяя к любой функции из ft операцию перестановки с множеством угловых наборов W, можем получить лишь саму эту функцию. Следователь-но, А\ = [{ &}], A = [{Y&}}, АІ = [{ЗД, В? U В? U [{Х }}, Л? U В? U {Xij} w= A? U В U [{Xij}]. Аналогично можно показать, что {А02, X20} w= [{А02}] U [{А2о}]-
Отсюда получаем, что ft = ft jy, и произвольное подмножество 21 множества ft, замкнутое относительно операций суперпозиции и перестановки с множеством угловых наборов W, содержит множество Yij (соответственно Zij, Cij), {i,j} = {0,2}, тогда и только тогда, когда для любого п 1 найдется число е(п) п, такое, что Y (соответственно Z„- , „ ) принадлежит 21, а множество Х , {i,j} = {0,2}, принадлежит 21 в том и только в том случае, когда для любого п 1 найдется число е{п) п, такое, что по крайней мере одна из функций Х п , Yij содержится в 21. Таким образом, множество всех подмножеств множества ft, замкнутых относительно операций суперпозиции и перестановки с множеством угловых наборов W, исчерпывается следующим не более чем счетным множеством классов, элементы которого разделим на две группы. 1. Классы, получающиеся в результате объединения конечного числа (не более семи) классов, перечисленных в предыдущем пункте. Указанное множество классов является счетным, так как содержит счетное под множество попарно различных классов А\, А\,..., А\, Теорема доказана. Теорема 3.1.2. Пусть W — произвольное правильное множество угловых наборов из Qz, 21 — произвольное множество функций из Рз такое, что 21 = 21 и/. Тогда 21 = д U «В, где = 21П П, В = 3L(3) W. Доказательство теоремы 3.1.2 будет приведено ниже. Из теорем 3.1.1 и 3.1.2 получаем основной результат данного параграфа. Теорема 3.1.3. Пусть W — произвольное правильное множество угловых наборов из Qz- Тогда мощность множества классов в Рз, замкнутых относительно операций суперпозиции и перестановки с множеством угловых наборов W, счетная. Докажем теорему 3.1.2. Для этого нам потребуются следующие утверждения. Замечание 3.2. В силу свойства 2 операции перестановки (см. главу 1) везде далее будем считать, что любое правильное множество угловых наборов W наряду с любым своим набором (а\,..., ап), п 2, также содержит наборы (as(i), , Xs{n)), (2 — «3(1)1..., 2 — as(n)) для всех перестановок s чисел 1,..., п. Отсюда, в частности, следует, что W содержит множества Q\, Ql, V3. Лемма 3.1.1. Пусть W— произвольное правильное множество угловых наборов из Qz, f{x\,x2) — существенная функция из Рз, а, /3 — произвольные наборы из множества {(0,1), (1,0), (1,2), (2,1)}. Тогда класс {f} w содержит функцию Доказательство. Если f(a) = /(/З), то утверждение очевидно. Пусть /(d) ф f((3). Если а и Р принадлежат одному слою относительно хотя бы одного набора из Q\, то утверждение очевидно. В противном случае, существует г, і Є {1,2}, такое, что оч — &% — 1- Без ограничения общности можно считать, что і = 1. Пусть р(хі,х2) Є Рз, 6, 7 Є Е%. Обозначим через ips (xi,x2) следующую функцию Обозначим через /0, /ь /2, /з, о, hu h2, h3, следующие функции: fo(xi,x2) — f(xux2), fi(xx,x2) = /o,1),(1f ( i. ), /2(xux2) = Атт)(хих2), /з(хг,х2) = f l)M{xux2), hj(xi,x2) = fj ( 1, 2) для j = 0,1,2,3. Из определения функции /3 следует, что g(xi,x2) = /з(хі,х2). Нетрудно показать, что если функция fj, 0 j 2, существенная, то функции fj+i, hj+i принадлежат классу {fj} w- Аналогично, если функция hji 0 J 2, существенная, то функции /,+ь Л_,+і принадлежат классу {/&,} и/. Рассмотрим функцию /. Возможны следующие случаи. 1. (/({0,2}2) 2. Если ограничение функции f(x\,X2) на множество {0,2}2 является существенной функцией, то все функции /о, /і, /г, /з являются существенными и, следовательно, функция д принадлежит классу {/} w- Если ограничение функции f(xi,X2) на множество {0,2}2 не является существенной функцией, то /(О,0) ф /(2,2). Поэтому для любого j = 0,1,2,3 хотя бы одна из функций fj, hj является существенной. Следовательно, согласно вышеуказанному замечанию получаем, что д E {f} w 2. D(/({0,2}2) = 1. 2.1. -D(/) = 3. Тогда существует набор из / Тогда все функции /0, /і, /г, /з являются существенными и, следовательно, согласно вышеуказанному замечанию функция д принадлежит классу {f} w 2.2. .D(/) = 2. Если /(0,0) = /(1,1), то все функции /о, /і, /г, /з являются существенными, и, следовательно, д E {f} w- Пусть /(0,0) ф /(1,1). Если функция / на множестве С/2 принимает одно из своих значений только один раз, то все функции /о, /і, /г, /з являются существенными, и, следовательно, д {/} цл- Пусть функция / на множестве Щ принимает каждое из своих значений по два раза. Возможны следующие случаи. 2.2.1. / Є Go2- Тогда / Є N0,o2 U - 2,02- Исходя из соображений двойственности достаточно доказать лемму для случая, когда / Є iV0i02- Так как /(0,0) ф /(1,1), то /(1,1) = 2. Возьмем функцию Vifab ) = f(xi,f(xux2)). Тогда -фх Є 02 0,02, -01 (1,0) ф 01(1,2), V i(0,1) = -0i(2,1). Следовательно, ф\ на множестве Щ принимает одно из своих значений только один раз. Поэтому согласно предыдущим случаям получаем, что класс {ipi} w содержит функцию 2( 1, 2) такую, что г(1,0) = 2, 2(1,2) — 0. Рассмотрим
Замкнутые классы в Р2 и Р3
Лемма 3.3.1. Пусть f(xi,...,хт), fi(xi,...,xtl),..., fr(xi,...,Хъ) — произвольные функции из Pk, k 2, га 1, U 1, г = 1,...,r, r 1, W — произвольное бесконечное множество угловых наборов из Qk, 21 = {/, /і, , /r} w 7(яь xk) произвольная функция из Рк, такая, что для любого набора («i, ...,) из Е\ выполняется соотношение Следствие 3.3.1. Пусть f(xi,...,xm) — произвольная функция из Рк, к 2, га 1, W — произвольное бесконечное множество угловых наборов из Qk, g(xi,... ,хк) — произвольная функция из Рк, такая, что для любого набора (а\,... ,ак) из Ек выполняется соотношение Рассмотрим замкнутые классы в Pi. Теорема 3.3.1. Пусть W — произвольное бесконечное множество угловых наборов из Q2. Множество классов в Pi, замкнутых относительно операций суперпозиции и перестановки с множеством угловых наборов W, исчерпывается следующим списком: Доказательство. Пусть 21 С Р2 и 21 = 2l vf. Если W С V2, то утверждение теоремы вытекает из следствия 3.2.2 и теоремы 2.2.1. Если W % V2, то множество W содержит угловой набор a = (a,..., с т), га 2, не принадлежащий V2. В силу свойства 2 операции перестановки (см. главу 1) можно считать, что набор а удовлетворяет равенствам «і = 0, а2 = 1. В силу следствия 3.2.1 и теоремы 2.2.1 получаем, что либо класс 21 совпадает с одним из классов С, Со, Сі, либо То П Ті С 21. Пусть То П Ті С 21. Тогда классу 21 принадлежит функция f[x\,... ,хт), получающуюся из Х\ добавлением несущественных переменных х2,...,хт. Согласно свойству 1 операции перестановки (см. главу 1) класс {/} {а} содержит функцию g(x\,.. .,хт) такую, что р(1,..., 1) = /(О,0,1,..., 1), #(0,..., 0) = /(1,1,0,..., 0). Тогда функция д(х,...,х) = х. Следовательно, согласно лемме 3.3.1 получаем ТоПТі у = Р2- Поэтому, в силу соотношения ТоПТі С 21, имеем 21 = Р2. Тем самым теорема доказана. Рассмотрим замкнутые классы в Рз. Из определения операции перестановки вытекает справедливость следующей лемм. Лемма 3.3.3. Пусть a = (cti,...,am) — произвольный угловой набор из Q- Wz, т 2, у — произвольный элемент из Ез, i,j — произвольные элементы из {0,2}, такие, что {i,j} = {0,2}, f(x\,..., хп) — произвольная функция из Рз, принимающая значение у хотя бы на одном наборе из множества {j, 1}п, п 1. Тогда класс {/} « содержит функцию д(х\,.. .,хт), принимающую значение у хотя бы на одном наборе из множества {г, 1}т, причем выполняется равенство д(г,..., г) = f(j,. ,.,j). Доказательство. Пусть а, у, i, j, f удовлетворяют условию леммы. Пусть і = О, j = 2 (случай г = 2, j = 0 доказывается аналогично). Класс [{/}] содержит функцию h(xi,x2), такую, что h принимает значение у по крайней мере на одном из наборов (2,2), (1,2), (1,1) и h(2,2) = /(2,...,2). В силу свойства 2 операции перестановки (см. главу 1) можно считать, что набор а удовлетворяет равенствам «і = 0, «2 = 2.
Рассмотрим функцию p(xi,... ,хт), получающуюся из h(xi, X2) добавлением несущественных переменных х3,..., хт. Согласно свойства 1 операции перестановки (см. главу 1) класс { } d содержит функцию g(xi,... ,хт), такую, что 0(0,0,0,...,0) = у (2,2,0,...,0), $(0,1,0,...,0) = (1,2,0,...,0). Тогда g(xi,...,xm) принимает значение у хотя бы на одном наборе из {0,1}т, и 0(0,...,0) = (2,2,0...,0)=/(2,...,2). Тем самым лемма доказана. Лемма 3.3.4. Пусть W С Q3, W % V3. Тогда 1) TQi w= Ti2 W= Tu W = T2 W=z NQfii w= N2,\2 W= Рз/ 2) классы Т02, ТІ, iVo,o2» №,02 СОЇ, G\2, GQ2, С, СОЇ, Cn, C02, Co, C\, C2 замкнуты относительно операций суперпозиции и перестановки с множеством угловых наборов W; 3) Nlfil w= Nhl2 w=Tl. Доказательство. 1) Покажем, что T0i w= РЗ- Аналогичные равенства для классов Ті, Т\2, Т0, Т2 доказываются похожим образом. Через f(x) обозначим функцию из T0i, удовлетворяющую равенству /(2) = 2. Согласно лемме 3.3.3 класс {f} w содержит функцию h(x) такую, что /г(0) = 2. А так как {/, 0,1} С Тої, то класс TQI W содержит все константы 0, 1, 2. В силу леммы 3.3.1 класс {х, 0, 1,2} W содержит все функции от трех переменных из Р3- Поэтому, согласно теореме 3.2.1, имеем {х, 0,1,2} w=z Рз, и, поскольку х Є Тої, получаем Тоі іу= Рз Покажем, что N0fli w= Рз- Через д(х) обозначим функцию из N0,oi, удовлетворяющую равенству д(2) = 2, через ф{х\,Х2) обозначим функцию из iV0ioi, удовлетворяющую равенству гр(0,2) = 1- Согласно лемме 3.3.3 класс {g} w содержит функцию р(х) такую, что (р(0) = 2. А так как {д,ф,0} С iVo.oi, то класс N0i0i w содержит все константы 0, 1, 2. В силу леммы 3.3.1 класс {х, 0,1,2} w содержит все функции от трех переменных из Рз- Поэтому, согласно теореме 2, имеем {х, 0,1,2} іу= Рз, и, поскольку х Є Notoi, получаем /Vo,oi w= Рз- Равенство N2,i2 w= Рз доказывается аналогично. 2) В силу замечания 1.1 получаем, что в результате применения операции перестановки с произвольным угловым набором а из Q3 к произвольной функции f(xi,...,xn) из Рз не меняется множество ее значений на множествах {0,2}п, {1п}, Щ. Поэтому, согласно определению классов Т02, Ть iVo)02, N2,02, С0і, Сі2, С02, С, С0і, Сі2, С02, С0, Сі, Сг, данные классы замкнуты относительно операций суперпозиции и перестановки с множеством угловых наборов W. 3) Для данного случая утверждение леммы доказывается аналогично пункту 1. Лемма 3.3.5. Пусть W С V3 U {(0,2)(2,0)}. Тогда Nlfil П Nhl2 w= Nlfil П 7V1)12 Доказательство. Пусть W удовлетворяет условию леммы. В силу свойств операции перестановки для доказательства леммы достаточно показать, что -/Уі,оіПІ\Г1)12 Узи{(о,2)(2,о)}= -N1,01 nNlyl2. Так как по лемме 2.2.2 Nl 0i V3= Nlfil, N\t\2 v3= А ідг, то класс iV1)0i П -/Vi,i2 замкнут относительно операции суперпозиции и перестановки с множеством угловых наборов V3. Любая двуместная функ ция из Nifii П -/Vi,i2 может принимать значение отличное от 1 только на наборах (0,2), (2,0). Поэтому JVi,oin7Vi,i2 {(o,2)(2,o)}= 1,01 П Л і,і2, и, следовательно, N\fil П Л д2 у3и{(0,2)(2,0)}= - 1,01 П Л 1Д2 Положим Г = {IifrTbNifrNj&Gij \i,j Є Е3, і ф j}, A = {Tij,Ti \ i,j Є E3, і ф j], Є = {ТЙ ГІ,ЛГМ1,ЛГМІ Є {0,2}, ЄІ = {NijuN TiuTi}, і = 0,2. Отметим следующие очевидные свойства классов из Г. Пусть г, j, к попарно различные элементы множества Е3. Тогда выполняются следующие равенства
Функции вида Ffi
Теорема 4.1.1. Пусть W С {(0), (0,0),.. .}U{(A;-1), (Jfc-1, k-1),...}, к 3. Тогда мощность множества классов в Pk, замкнутых относительно операций суперпозиции и перестановки типа II с множеством угловых наборов W, равна мощности континуума. Доказательство следует из существования класса 21 = {/2,/3, ,/І, --} w со счетным базисом {/2, /з,. , /І, } (см. [27, 28]), где { к — 2 при хі = ... = Xj-i = Xj+l = ... = ХІ = к — 1, Xj = к — 2, j = 1,..., г; 0 в остальных случаях, Поскольку согласно определению операция перестановки типа II является более сильной чем операция перестановки типа I, то из следствия 3.2.3 вытекает следующее утверждение. Следствие 4.1.1. Пусть W С {(0), (0,0),...} U {(к - 1), (А; - 1, к - 1),...}, к 3. Тогда мощность множества классов в Pk, замкнутых относительно операций суперпозиции и перестановки типа I с множеством угловых наборов W, равна мощности континуума. 4.2. Функции вида FQ Введем следующие обозначения: i% = {(«і,..., ап) Є Е% \ а\+.. .+ап = I (mod 2)}, / = 0,1, п 1; Fn(x х ) = { ЄСЛИ (Хи Хп) Є Еы ij\ її---» п) j в противном случае, при г, j Є Ek, п 1; F/ — множество всех функций, получающихся из функций множества {F-j(xi,...,xn) (i,j) Е\ьп 1} переименованием (без отождествления) переменных и добавлением фиктивных переменных, / = 0,1; F = F U Fi; Рассмотрим некоторые свойства функций из множества F. i). Fffix, ...,x)=i, F%-\x,..., х) = Ft)(x) для всех п 1. ii). Пусть s(x) — произвольная перестановка чисел 1,...,п, п 1. Тогда множество D(f\) значений функции /і целиком содержится в одном из множеств Ек0 или Ек1; г Є Ек0, если D(fi) С Е\0, и г Є Ек1, если D(fi) С Е\х. Тогда Лемма 4.2.1. Пусть f(x\,... ,хп) — произвольная функция из F, существенно зависящая от п переменных, п 1, a = ( 2i,..., ап) — произвольный угловой набор из Qk д(хіі УХП) произвольная функция, получающаяся из f применением операции перестановки с угловым набором а. Тогда g(x\,..., хп) = f(x\,..., хп). Доказательство. Данная лемма непосредственно следует из того факта, что для любого углового набора а из Qk, п 1, каждое из множеств Ек0, Ек1 совпадает с объединением некоторых слоев относительно а. Справедливость последнего вытекает из определения слоя, согласно которому два произвольных набора ( Si,. ., Sn) (71,...,7п) принадлежат одному слою относительно а в том и только том случае, когда выполняется равенство \5i — ai\ + ... + \5п — е п = І7і - "її + + І7п — otn\. Рассмотрим множество FQ. Введем следующие обозначения: Фу = {i,F ,..., ,...}, % = {І, ,..., g?,...}, Нц = { ,..., у-\...}, Ф = {г, 4,... , д}, % = { ,/ ,.. ., ), -1 = (4,..., -1}. Ц = Ц = {І}, (i,j) Є ElQ, п 1. Обозначим через Фу, Фу, Яу, Ф, Ф2]\ Hfj1 1, Ф?-, Фу. множества Я„- , Ф„-, Фу- соотвественно переименованием (без отождествления) переменных и добавлением фиктивных переменных, (z,j) Є Ек0, п 1. Лемма 4.2.2. Для функций из FQ справедливы следующие равенства: [{?%}} = Щ, если п 1, г", j Є &,; [(4"}] = S U ЯГ [{4П-1}] = Ф?Г2 U Я -1, если п 1, г, і Є і&; [(4 0] = [{Ц}}] U [ML если гг 1 и ли& г, j, Z Є &,, либо г, j, І Є Elkl. [{4, и}] = Ф U Ф Г1 U [{И}], если п 1 и ли5о г, j Є 0, и Є Elkl, либо г, j , и Є 0. Доказательство. Если i,j Є Е1 , то [{4}] = ІІ-
Действительно, поскольку 4(4( )) = ij ( ) = то из свойств О» и0 следует, что справедливо включение Фу С [{4}]- В силу свойств i)-v) получаем искомые равенства. Пусть і J Є E\v Тогда [(4"}] = Ф2; U Я »"1, [{4""1}] = Я2""1 U Ф -а. Действи-тельно, так как в силу свойства і) и равенства F FMx)) = j выполняются соотношения і Є [(4n}] J е [{Fijn 1}], то согласно свойству Ш) имеем Ф2]1 U Н 1 С [{i »}], Я2"-1 U ф2!1-2 с [(4П_1}]- СИЛУ свойств i)-v) получаем Пусть либо г, j, / є E\Q, либо г, j, І Є Ек1. Поскольку согласно предыдущим случаям классу [{i "}] принадлежит одна из констант г или j, и [{Fj"}] С Фу U Ф (см. выше), то по свойству v) выполняется равенство [{i ",0] = [(- }] U [Ml Пусть либо г, j Є Ек0, и Є Ек1, либо г, j Є Ек1, и Є E\Q. Так как г, j Є [{ ",м}], [{ 7}] фу и фл то согласно свойствам i)-v) имеем [{Ffi, и}] = Ф?- U Ф-1 U [{«}]. Тем самым лемма доказана. Следствие 4.2.1. Пусть А — произвольное множество угловых наборов из Qk, к 2. Тогда F0 A= F0. Доказательство. Согласно предыдущей лемме и свойству v) класс [F0] совпадает с множеством (J I (J [{FJj} U Ек] U \J [{Ffi} U Ек] J, которое также в силу преды дущей леммы содержится в F0. Таким образом, [F0] = FQ. Отсюда, согласно лемме 4.2.1, получаем F0 A F0. Тем самым следствие доказано. Лемма 4.2.3. Пусть А — произвольное множество угловых наборов из Qk, к 2. Тогда множество классов в FQ, замкнутых относительно операций суперпозиции и перестановки с 2. Классы, являющиеся конечными объединениями классов из пункта 1, если все входящие в указанные объединения функции принимают значения только из одного множества E\Q или Ек1. 3. Классы, получающиеся из конечных объединений классов Фу U Ф , Ф„- U Ф Г1, Фу-, где г ф j, (i,j) .Ef0, п 1, содержащих как функции со значениями из E\Q, так и функции со значениями из E\v Доказательство. Согласно лемме 4.2.1 для любого подмножества F множества FQ выполняется равенство F A=1 [F1]. Поэтому для доказательства леммы достаточно показать, что множество классов в FQ, замкнутых относительно операции суперпозиции, исчерпывается указанным в условии леммы списком классов. В силу леммы 4.2.2 и свойств i)-v) все классы из условия леммы являются замкнутыми относительно операции суперпозиции. Пусть % С Fo, 21 = [21]. Положим 21у = 2ІПФу. В силу справедливости соотношений FQ = [FQ], FQ = \J Ф U (J Фу класс 21 можно представить в виде объединения следующих множеств 21 = U 2ly- U U 21у. Покажем, что 21 совпадает с одним из классов из условия леммы. Заметим, что согласно лемме 4.2.2 и свойствам i)-v) замыкание любого конечного объединения классов из пункта 1 условия леммы совпадает с одним из классов из пунктов 2, 3 условия леммы. Поэтому для доказательства этого факта достаточно проверить, что для любых различных г и j из Ек, имеющих одинаковую четность, множество 21у содержится в некотором конечном объединении классов из пункта 1 условия леммы, а это объединение в свою очередь содержится в 21. Рассмотрим произвольное непустое множество 21у. Возможны следующие случаи. Пусть i,j Є Ек0. Так как 21у не пусто, то в силу равенств F (F Jx)) = F JO) = і и свойства і) множество 21у содержит константу г. Если множество 21у П Фу бесконечно, то по свойству Ш) имеем 21у = Фу. В противном случае, либо 21у = Ф?., либо существует п 1 такое, что Ffi Є 2ly, Fjj . 21у для всех I п. Тогда также согласно свойству Ш) получаем, что 21у = Ф?. Пусть i,j Є E\v Поскольку 2Ц,- не пусто, то в силу равенств i .(i (:r)) = F l) = j и свойства і) множество 21у содержит хотя бы одну из констант i,j. Если оба множества 21у П Фу-, 21у ПЯу бесконечны, то по свойству ш) имеем 21 - = Фу- С Фу- и Ф_ С 21. Если множество 21у П Фу бесконечно, множество 21у П Ну конечно, то согласно свойству Ш) множество 21у совпадает с одним из множеств Фу- U Я2--1 (I 1), Фу, а класс 21 содержит один из классов (Фу U Я ) U (Яг2?-1 U Ф2 -2), Фу U Я соответственно. Если, наоборот, множество 21у П Фу конечно, множество 21у Г) Яу бесконечно, то в силу свойства Ш) множество 21у совпадает с одним из множеств Яу U Ф. (I 1), Яу U Фу, Щ, а класс 21
