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

• Автор: Тарасова, Ольга Сергеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 112 с.

ф Оглавление

1. Определения, свойства, вспомогательные утверждения

2. Операция перестановки типа I

с множеством нулевых угловых наборов

2.1. Замкнутые классы вД

2.2. Замкнутые классы в /г и Рз

2.3. Ослабленная операция перестановки

3. Операция перестановки типа I

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

3.1. Ослабленная операция перестановки

3.1.1. Замкнутые классы трехзначной логики

3.1.2. Примеры континуальных семейств .
3.2. Замкнутые классы в Рк
3.3. Замкнутые классы в Р2 и Р3
4. Ослабленная операция перестановки типа II
4.1. Примеры континуальных семейств
4.2. Функции вида
4.3. .Р-функции
4.4. Основные утверждения
Литература

Настоящая работа относится к теории функциональных систем — одного из основных разделов дискретной математики. В ней рассматривается задача об изучении свойств замкнутых классов функций А-значной логики.
Э. Пост описал все замкнутые (относительно операции суперпозиции) классы булевых функций и показал, что каждый замкнутый класс имеет конечный базис, а множество всех таких классов счетно [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], где в частности установлено, что множество классов в данной классификации конечно, хотя и зависит от А сверхэкспоненциальным образом.
Понятия параметрической выразимости и параметрического замыкания введены A.B. Кузнецовым в работе [6]. В этой же работе получены критерий параметрической выразимости в А-значной логике для всех А ^ 2 и конечное описание параметрически замкнутых классов булевых функций. Конечность множества параметрически замкнутых классов при А = 3 показана в работе А. Ф. Данильченко [5], а при А > 3 в работе С. Барриса, Р. Уилларда [29]. Кроме того в [5] построены все предполные классы в Р).
В работе Ю.В. Голункова [4] изучаются вопросы полноты функциональнопредикатных систем с операциями замыкания программного типа (см. также [1]). В работах В.А. Тайманова [21, 22] и В.Д. Соловьева [20] исследуется семейство функциональных систем /г-значной логики (к ^ 2) с операциями программного типа. Каждая операция программного типа определяется своим множеством предикатов. В работах [21, 22] показано, что в зависимости от свойств указанных множеств предикатов мощность множества замкнутых классов может быть конечной, счетной или равняться мощности континуума. В случае конечного множества замкнутых классов приведено его полное описание, в случае счетного множества замкнутых классов показано, что каждый класс обладает конечным базисом, в случае континуального множества замкнутых классов представлены примеры классов со счетным базисом и классов без базиса, причем эти примеры совпадают с соответствующими примерами из [27, 28]. В [20] рассматриваются примеры конечных описаний множества замкнутых классов для некоторых операций программного типа.
Следует также отметить подход, состоящий в разбиении множества замкнутых классов /г-значной логики на классы эквивалентности, которые формируются на основе свойств входящих в них функций. Такой подход рассматривался Нгуеном Ван Хоа в работах [17-19].
Из сказанного выше вытекает, что все перечисленные примеры операции замыкания, за исключением некоторых операций замыкания программного типа, приводят к конечному множеству замкнутых классов в Р* при к ^ 3. В связи с этим, представляется важным изучение таких усилений операции суперпозиции, которые, с одной стороны, не являются столь сильными, чтобы давать конечное множество замкнутых классов, а с другой стороны позволяют достаточно просто находить результат применения этих операций к функциям. К числу таких усилений операции суперпозиции можно отнести добавление к ней операции перестановки.
В настоящей работе исследуются классы /г-значной логики, к ^ 2, замкнутые относительно операций суперпозиции и перестановки с множеством угловых наборов. То есть в каждом классе, замкнутом относительно этих операций вместе с каждой функцией содержатся и все функции получающиеся из исходной в результате применения к ней операции перестановки. Операция перестановки использует геометрическое представление функций и поэтому имеет достаточно простой способ вычисления по функции всех ее образов. Эта операция вводится при помощи понятия слоя. В работе изучается несколько модификаций операции перестановки.
Сначала рассматривается операция перестановки, при определении которой слой (слой типа I) задается как множество всех наборов одинаковой длины, содержащих фиксированное количество элементов равных 0,1, — 1. В результате применения этой операции к произвольной функции /(х1,... ,хп), на наборах внутри каждого слоя происходит перестановка значений данной функции, определяемая по следующему правилу. Для каждого слоя выбирается перестановка чисел от 1 до п и для каждого набора слоя новое значение функции / на нем совпадает с исходным значением функции / на наборе, получающимся из данного соответствующей перестановкой его компонент. В работе показано (см. главу 2), что в этом случае множество классов в Г. замкнутых относительно операций суперпозиции и перестановки, является конечным при всех к > 2. Таким образом, данная операция перестановки является слишком сильной. В связи с этим изучается ослабление этой операции за счет введения следующего ограничения. Операцию перестановки разрешается применять только к тем функциям, которые существенно зависят от всех своих переменных. Показано (см. главу 2), что при к = 2 мощность множества замкнутых классов конечна, а при к ^ 3 равна мощности континуума.
Далее в работе вводится понятие слоя относительно углового набора (т.е. набора, все компоненты которого принадлежат множеству (ОД — 1}), и изучается (ослабленЕсли й, /ї Є £Н, то в качестве функции ф можно взять функцию /'. Пусть выполняется по крайней мере одно из соотношений й ^ 91, р ^ 91.
Построим функцию грі(хі,... ,хт1) из ©(/), существенно зависящую от ті переменных, 2 р т4 р q, такую, что существуют наборы йц, Ді из И1, удовлетворяющие равенству {V'i(âi), фіфі)} = D{f)D(f(E3U3)), и выполняется одно из следующих условий: a) mi = 2, Ь) 2 < mx < g и выполнено по крайней мере одно из двух условий: &і(йі) Ф fci(/3i);_&0(âi) > ЬоФі) и М“і) < Ь2фі), с) тг __= q, й 6 91, /3 £ 91,
Й1 = й, 6i(Â) = М/3), 6у(А) = *г(/3) + 1, d)_mi = g, й ф. 91, р Є 91, 6і(йі) = &і(й), 60(йі) = b0(â) + 1, fi = /§, e) ті = q, â f* Зі, /§ & 91, 6і(«і) = 5j(ü), b0(âL) = b0(à) + 1, ЬіШ = Ьіф),Ь2ф1) = Ь20) + 1.
Согласно лемме 3.1.16 класс <{f'}>w содержит функцию і совпадает с /', если її = q, à ф 91, то y?i(/3) = f'(P) и существует набор й', удовлетворяющий соотношениям q>i(â') = /'(й), бі(й') = 6і(й), bo(à') = b0(â) + 1.
Если її = 2, то, очевидно, в качестве функции фі(хі,х2) можно взять функцию <Рі(хі,х2), а в качестве наборов йі, р можно взять произвольные наборы из t/f, удовлетворяющие равенству {ipi(âi),q>i(l3i)} = D(f)D(f(E3U3)).
Пусть 2 < її < q. Тогда в силу леммы 3.1.17 класс < {w содержит функцию ip2(xi,... ,xi2) из ©(/), существенно зависящая от 12 переменных,
2 ^ 12 Р h, такую, что существуют наборы â[, р[ из U32, удовлетворяющие равенству {q>2{â'i), tp2(j3j)} = D(f)D(f(E3U3)) и по крайней мере одному из двух условий: bi(â[) ф Ьіф'і) ba(à'i) > Ьйф[) и b2(â[) < Ь2ф[). Поэтому в качестве функции 1pl(xi xmi) можно ВЗЯТЬ функцию Пусть її = q. Если /З Є £Н, то й ф 51. Тогда в качестве функции ф[х хті) можно взять функцию q>i(xi хя), где mi = її, йі = й', /Зі = /3. Пусть р ф У. Если й € 91, то положим й" = й. Если à gî 91, то положим й" = й'. Согласно лемме 3.1.16 класс <{q>i }>w содержит функцию <рз(хі,... ,хф из ©(/), существенно зависящую от 13 переменных, 2 р l3 р q, такую, что если l3 = q, то i(â") и существует набор Р' из Щ, удовлетворяющий соотношениям <рзф') = ipi(P), bi(p') = Ьіф), Ь2ф') = Ь2ф) +1. Если /3 = 2, то в качестве функции Фі(хі,х2) можно взять функцию <Рз(хі, х2), а в качестве наборов йь рх можно взять произвольные наборы из Щ, удовлетворяющие равенству {ірзфі),ірзфі)} = D(i(E%U3)). Пусть 2 < l3 < q. Тогда в силу леммы 3.1.17 класс <{ч>з)>\г содержит функцию щ{хі,.. ■ ,Хц) из ©(/), существенно зависящую от /4 переменных, 2 р 14 р 13, такую, что существуют наборы й", р" из и‘< , удовлетворяющие равенству {д>4(й"),щф")} = D(f)D(f (E3U3 )) и по крайней мере одному из двух условий: &і(й") ф Ь4ф"); bu(à") > Ь0(р") и b2(à") < Ъ2ф"). Поэтому В качестве функции фі(хі,. . . ,Хті) МОЖНО ВЗЯТЬ функцию tp4(xi, . . . ,Хц), где тщ = U, Й! = й", Pi = р'{. Если Із = g, то в качестве функции фі(х4 xmi) можно ВЗЯТЬ функцию у>з(хі, . . . ,Х[3), где 7771 = h, Йі = Й", Pl = Р'.
Таким образом, мы построили функцию фі(хи наборы йі, pi. Если 772-1 = 2, ТО В качестве функции h МОЖНО ВЗЯТЬ функцию фі. Пусть 7771 > 2. Применяя к функции фі и наборам üi, Pi преобразования аналогичные тем, которые были произведены с функцией / и наборами й, р, и т.д. за конечное число шагов получим функцию, которую МОЖНО ВЗЯТЬ В качестве функции ф(х 1, ... ,хт).
Если 777 = 2, ТО В качестве функции h МОЖНО ВЗЯТЬ функцию ф. Если 777 > 2, то пользуясь замечанием 3.4 нетрудно показать, что класс
< {Ф} >{0">} содержит функцию ф2{х1,Х2,Х3) из ©(/) такую, что выполняется по крайней мере одно из равенств {^2(1;0,ОХ^гСППО)} = D(f)D(f(E3U3)), {ф2(1,1,2),ф2(1,2,2)} = D(f)D{f{ESUS)), Ш 1,0,0), ^2(1,1,2)} = D(f)D(f(E^)),