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

• Автор: Михайлович, Анна Витальевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 111 с. : ил.

Оглавление
Введение
1 Основные определения и вспомогательные утверждения
1.1 Определения и обозначения
1.2 Вспомогательные утверждения
2 Классы, порожденные функциями из множества КБ1
2.1 Критерии базируемости и конечной норожденности
2.2 Замыкание относительно отождествления переменных
3 Классы, порожденные функциями из множества МБз
3.1 Критерии базируемости и конечной порожденности
3.2 Изображение монотонных функций на плоскости
3.3 Критерии базируемости и конечной порожденности в терминах свойств
множества точек на плоскости
4 Классы, порожденные функциями со специальными свойствами
4.1 Критерий базируемости для множеств, обладающих свойствами (*) и (**)
4.2 Примеры множеств, обладающих свойствами (*) и (**)
4.2.1 Классы, порожденные функциями из множества КЯ"1.
4.2.2 Классы, порожденные симметрическими функциями с
согласованными типами
4.2.3 Классы, порожденные функциями из множества
4.2.4 Классы, порожденные функциями из множества МЭ..
Литература

Введение
В данной работе изучаются свойства замкнутых классов функций многозначной логики. Рассматривается задача о существовании базисов для некоторых семейств замкнутых классов.
Э. JI. Пост [134,135] описал все замкнутые (относительно операции суперпозиции) классы булевых функций и показал, что множество замкнутых классов1 в Р2 счетно, при этом каждый такой класс имеет конечный базис (см. также [136]). Описание классов Поста можно найти также в работах [33,42,62,63,67,104,119,124,132,139]. Предикатное описание классов Поста дано в [4] (см. также [33,42,124]). Алгебраический подход к понятиям суперпозиции и замкнутого класса предложен А. И. Мальцевым [24,28].
Многозначные логики во многом похожи на двузначную логику. В них сохраняются многие результаты, имеющие место в двузначной логике. Можно, например, отметить решения проблемы функциональной полноты [21, 22, 25, 65, 66,146,147,151) и задачи описания предполных классов [16,29,66,126-129,137,140,141]. В то же время имеются существенные различия между' Р2 и Р* при к > 3. К их числу относятся примеры Ю. И. Янова о существовании замкнутых классов в Р*,, не имеющих базиса, и А. А. Мучника о существовании замкнутых классов в Р^ со счетным базисом [71] (к > 3). Из этих результатов следует, что мощность семейства замкнутых классов в Рд, при каждом к > 3 континуальна. Это делает труднообозримой структуру данного множества.
Поскольку при к > 3 изучение замкнутых классов Ä-значной логики наталкивается на значительные трудности, то, с одной стороны, многие авторы стали рассматривать задачу изучения классов, замкнутых относительно более сильных операций замыкания, которые позволили бы получить множество замкнутых классов конечной или счетной мощности (см., например, [1,8,9,23,34,36,38,51-54,56-61,76]). С другой стороны, изучались отдельные семейства замкнутых классов функций /г-зыачной логики, содержащих конечное, счетное или континуальное множество подклассов. К настоящему времени получено описание свойств некоторых семейств замкнутых классов2 в Рд.. Отметим некоторые из этих результатов.
Наиболее хорошо изучены свойства предполных3 классов функций fc-значной логики. Конечность числа предполных классов в Рк установил A.B. Кузнецов [44]. Все предполные классы функций трехзначной логики описал С. В. Яблонский [65,66]. Отдельные семейства предполных классов в Рд, найдены в работах [2,13,14,29,66,126-129]. Полное описание всех предполных классов в Рд. при всех к > 3 было дано И. Розенбергом [140,141] (см. также [5,15,35,69,124,137]). Асимптотически точная формула для числа 7Г(к) всех предполных классов в Рд, найдена в [15]. Конечная порожденноеть всех
1 Через Рд, обозначается множество всех функций /с-значнон логики, к > 2.
2 Обзор результатов, полученных в этом направлении, можно найти, например, в [124,133].
3 Предполные классы в Рд, называются также максимальными.

предполных классов при к <7 доказана Д. Jlay [108]. Пример предполиого в Рв класса типа1 О (замкнутого класса функций, монотонных относительно частичного порядка специального вида), не имеющего конечной порождающей системы, приведен Г. Тардо-шем [158]. Необходимые и достаточные условия конечной порожденное предполных классов функций в Рк (к > 3), монотонных относительно частично упорядоченных множеств ширины 2, получены в [10-12].
Свойства минимальных классов и минимальных клонов5 в решетке Шк (семействе замкнутых классов функций к-значной логики, упорядоченных по включению) изучались в работах [87-89,100-103,124,125,131,133,138,144,145,152,159]. В [133] приведена формула для числа минимальных классов функций fc-значной логики, к > 3, и дано описание свойств функций, порождающих эти классы (см. также [124]). Все минимальные клоны в Р3 описаны Б. Чаканем [87,88]. В [101,102,133] описаны все минимальные клоны в Рк (к > 3) порядка 1. Розенберг [144] установил конечность множества минимальных клонов в Рк при всех к > 3 и привел классификацию функций, определяющих минимальные клоны в решетке ШД. Отдельные семейства минимальных клонов в Р.^ изучены в [159]; в работе [131] приведены примеры минимальных клонов в Рк, к > 3, порядка t, 1 < t < к.
В работах [6,25,30-32,36-41,47-55,66,146,147,151] изучаются свойства замкнутых классов в Рк, содержащих заданное множество функций одной переменной. Е. Слу-пецкий [151] предложил критерий полноты для систем функций /с-значной логики, содержащих множество6 P/t(l), к > 3. Все замкнутые классы в Рк, содержащие множество P/t(l), перечислены Г. А. Бурле [6]. Яблонский [66] получил критерий полноты для систем функций в Pfc, содержащих множество всех функций из Рк[ 1), принимающих не более к — 1 значения, к > 3. Некоторое усиление этого результата получено
А. И. Мальцевым [25]. Критерии полноты для систем функций из Рк при к > 5, содержащих группу &к всех подстановок на множестве Ек — {0,1,..., к — 1}, получены в [146,147]. Все замкнутые классы в Рк, содержащие заданный предполный в [Р/,.(1)] класс функций, для всех к > 3 описаны в [55]. Описание семейства замкнутых классов в Рк, содержащих группу ©*,, при всех к > 3 получено в [30-32,43,51-53]. Свойства семейств замкнутых классов в Рк, содержащих некоторые подгруппы группы 6к, изучены в работах [37,39-41,47-50,54].
В работах В. Б. Кудрявцева [17-20] изучаются свойства систем функций к-значной логики, состоящих только из функций, принимающих все значения из множества Ек (такие системы называются 5-системами) ; приводятся критерии 5-полноты для рассматриваемых систем функций, устанавливается асимптотическое поведение числа 5-предполных 5-множеств и их типов.
Замкнутые классы функций из множества7 Pkii изучаются в работах [83-86,97-99, 105-107,112,116,117,124]. Рассматривается отображение замкнутых классов из Pkj в замкнутые классы Pi и для каждого класса В С. Pi описывается семейство за-
мкнутых классов из Pkii, состоящих из функций, ограничение которых на множестве определяет функции из класса В. Ряд важных свойств замкнутых классов из Р3 2 изучен в [97-99,112,117]; в частности, для каждого замкнутого класса В булевых функций
4 Будем использовать обозначения семейств предполных классов из книги [69].
5 Клоном называется замкнутый класс, содержащий все селекторные функции.
6 Через Pfc(l) обозначается множество всех функций f(x) из Рк, к > 2.
7 Через Pkj обозначается множество всех функций fc-значной логики, принимающих значения только из множества Ei, 2 < I < к.

Пусть £о > 0. Поскольку (1,%, е2,р, Ц > 0, то справедливы неравенства
6 — <6,1 — и е2 — < е2 — Так как выполняется но крайней мере одно
из неравенств (2.5), то выполняется по крайней мере одно из неравенств 6 — <
или е2 — < 0. Следовательно, хотя бы одна компонента решения (жі, уі, жг, 2/г) от-
рицательна.
Пусть Ь0 < 0. Поскольку е±, 62,р,д > 0, то справедливы неравенства еі + < ег —
— у^у и с/2 + у^уу < е2 — уу^уу. Так как выполняется по крайней мере одно из неравенств (2.6), то выполняется по крайней мере одно из неравенств ег + у^уу < 0 или 62 + у^у < 0. Следовательно, хотя бы одна компонента решения (ац, у1, х2, у2) отрицательна.
Таким образом, решение (х1,уі,х2}у2) = (ег + у^у,<іг - ^, е2 - у^у, 62 + у|^ при Ь0 ф 0 содержит хотя бы одну отрицательную компоненту. Следовательно, (еі, 6, е2, 62) является единственным решением системы (2.4) с компонентами из Ъ+.

Утверждение 2.2.7. Пусть /(жі,..., хп) Є Я, У/ = £(е,6) х £(0,6), е,6,п Є М, е + 26 = п, а Є <0>, сг > 0, числа а,Ь Є N такие, что (а, Ъ) — 1 и | = ст. Тогда функция / содероісится в < Ра > в ттгеш ?.г только в том случае, когда выполняются следующие соотношения:
(1) Ье — а6> 0;
(2) Ье — ад ^ Ьа при всех Ь = 1,..., е.
Доказательство. Необходимость. Пусть ф(х,... ,хп) Є Я, Nf = £(е,6) х £(0,6), е,6,п Є е + 26 = п, а Є <0>, а > 0, числа а,Ь Є N такие, что (а,Ь) = 1 и | = = п. Пусть функция ф(х,... ,хп) содержится в < Яа>. Тогда существует функция 1г(х,хт) Є Яа, такая, что Уд = £(са, сЪ), где с Є т = са + сЬ, /(жі,... ,хп) =
— Ь,(хЪ1,..., хХгп), хг1,..., жгт Є {оц,. . . , Жп}.
По условию функция / является симметрической относительно множества {жі,... ,же-м}- Пусть а = (ац,... ,ап) = (Iе, 2^, 2й), е,д > 0. Очевидно, что
а Є £(е, 6) х £(0,6) = У/. Поэтому /(а) = 1. Так как / Є [Б1], то по утверждению 2.2.4 среди ж,,,..., ж,т встречается каждая из переменных Х,..., же+сг, причем каждая из переменных встречается одинаковое число раз. Пусть каждая из переменных хі, ■.. ,хе+а встречается среди ж,,,...,ж,т ровно р раз, а переменные же+сг+1,... ,хп встречаются с/е-Ы+ъ раз соответственно, де-м+1, • ••,?« 6 й+. Тогда т = (е+сг)р+де+(г+і+..
Поскольку функция / существенно зависит от переменных жс+[(+і,..., хп, то среди Х{1,..., х1т встречается каждая из этих переменных, а значит, дк+а+, ■ ■ ■, дп Є П.
Положим (3 = (ач,..., а,т). Тогда Н((3) — /(5) = 1. Поэтому /З Є Уд = £(са,сЬ). Следовательно, выполняются следующие соотношения:
Щ =са= |(аг1,...,а,т)| == р(аъ ... ,ае+Л) = ре; т - Р = сЬ = т - |(аіг,..., а,т)| = р(е + 6) + де+а+і + ■ ■ ■ + дп~
-р|(аъ...,ае+а)| = рб + де+сі+і + ... + дп-
Таким образом, р = са/е. Поэтому са/е Є N. Кроме того, выполняются равенства Цс+<і+і + ... + дп = сЬ — рб = с(Ъе — а6)/е. Поэтому Ье — а6> 0.