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

• Автор: Подолько, Дмитрий Константинович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 113 с. : ил.

Оглавление
Введение
1 Основные определения
1.1 Двоичные представления
1.2 Двоичные перестановки
1.3 Операция двоичной суперпозиции
1.4 Эквивалентность 5'-замыкания и /3-замыкания
1.5 Критерий полноты/3-замкнутых классов
2 Классы функций из Рк|
2.1 Счетность семейства /3-замкнутых классов
2.2 Описание /3-замкнутых классов
3 Классы функций из Рц
3.1 Континуальность семейства/3-замкнутых классов
3.2 Конечные семейства /3-замкнутых классов
3.2.1 Классы с булевым замыканием в и
3.2.2 Классы с булевым замыканием в Б или К
3.2.3 Классы с булевым замыканием в Ь
3.2.4 Классы с булевым замыканием Р2, Т0, Т1, Т03, Д или /?
3.2.5 Классы с булевым замыканием О
3.2.6 Классы с булевым замыканием в М или Т0
3.2.7 Множества С(к, к) и С(к. 3)
3.3 Семейство классов с булевым замыканием 0м, /т >
3.4 Полная классификация
3.5 Случай с тремя фиксированными значениями
3.6 Подход к описанию классов
4 Классы функций из Рк |

4.1 Обобщение результатов из Рк|
4.2 Некоторые конечные семейства классов
4.3 Семейство классов с булевым замыканием О
4.3.1 Случай к =
4.3.2 Случай к = 2т, т >
4.4 Полная классификация
5 Все функции А-значной логики
5.1 Обобщение результатов из Рд.|
5.2 Классификация семейств /3-замкнутых классов
Литература

Введение
Настоящая работа относится к одному из основных направлении дискретной математики и математической кибернетики — теории функциональных систем [27, УЗ, 80]. Функциональная система представляет собой пару (51; ’ф), где 21 является некоторым множеством функций, а гф — некоторым отображением множества всех подмножеств системы 21 в себя. Функциональные системы, как правило, имеют содержательную связь с реальными кибернетическими моделями управляющих систем. К числу важнейших задач теории функциональных систем можно отнести задачи о полноте, о выразимости одних функций через другие, о структуре замкнутых классов, о тождественных преобразованиях и т.д. Результаты, получаемые при исследовании функциональных систем, позволяют разрабатывать новые подходы для решения других задач дискретной математики и математической кибернетики. Поэтому С. В. Яблонский утверждал [89], что роль функциональных систем в дискретной математике можно сравнить с ролью математического анализа в непрерывной математике.
Одним из центральных направлений в теории функциональных систем является изучение систем {1\ ф), где ! — множество функций А-значной логики, к > 2, а <р — некоторый оператор на множестве всех подмножеств Т. В качестве операторов у часто рассматриваются операторы, являющиеся операторами замыкания, т.е. обладающие тремя свойствами (см., например, [21 ]): А С <р(А) (экстенсивность), (р(А) С <р(В) при А С. В (монотонность) и ф{(р(А)) = <р(А) (идемпотентность).
Основными типами задач, возникающих при исследовании функций /с-значной логики являются задачи выразимости и полноты (см., например, обзор [79]). К первому из данных типов относятся задачи определения по множеству А и произвольной функции из Рк принадлежности этой функции множеству <р{А). Задачи второго типа для заданных множеств !•' и А из Рк направлены на исследование вопроса порождаемое множеством Р всех функций из А, т.е. выполнения условия <р(Р) = А. При этом важное место занимают задачи исследования классов на наличие конечных порождающих систем, а также задачи о существовании базиса, то есть порождающей системы, при удалении любой функции из которой эта система уже перестает быть порождающей. Также важным направлением при изучении функций А-значной логики является исследование свойств семейства классов {<^(Л) | А С Рк}. К этой проблематике можно отнести задачи определения мощности такого семейства классов, его структуры, свойств его элементов и т.д.
Доказательство. Все случаи рассматриваются аналогично, поэтому изучим только идин из них. Пусть 1 ^ и(В(Л)). Предположим, что найдется число г, 1 < г < т, такое, что р, &д; = 1. Так как (р, (/) £ 1пс1(.Д), то найдется функция Р из Л, для которой верно равенство Т>(Р) = {р, д}. Обозначим ее двоичное представление через {/ц ... ,/т)- Так как р, = 1 и д, = 1, то булева функция /, на некоторых наборах принимает значение 1. Предполо-жсм, что она также принимает значение 0. Тогда функция Р принимает значения р, д, а также значение г, у которого в двоичном представлении г-я компонента равна нулю, что неверно. Поэтому функция /, равна константе 1, и тогда 1 £ Ь(Р) С В (Л), что противоречит условиям рассматримаемого случая. Значит, рг &дг = 0 для всех г = 1, ... , т. Лемма доказана. ■
Теорема 2.3. Пусть I С {(р, д) | р, д £ р < д}, а В — замкнутый класс булевых функций. Тогда существует не более одного /3-замкнутого класса А функций из Рц2, такого, что В(А) — В и 1пс1(Д) = I. Необходимые и достаточные условия существования такого /З-замкнутого класса в зависимости от основания класса В задаются следующими ограничениями на множество I:
1) и {В) = {0,1,х,х}: /<2> / 0« <ДУ<2>) С (1{1М);
2) 11 (В) = {ж, х}: Iф 0 и р + д = к — 1 для всех (р, д) £ I;
3) и (В) = {0,1, ж}.- [^ ф 0, с/(у(2)) С й(/В)) и р < д для всех (р, д) £ I;
4) и (В) = {0, х}: Д2) ф- 0, /В) = {(0,0)} и р = 0 для всех (р. д) £ I;
5) и(В) = (1, ж}.- /И ^ 0, /(В = {(& _ к — 1)} и д = к — 1 для всех (р, д) £ I;
6) С/(В) = {.г}: I = {(0, к — 1)};
7) и (В) = {0,1}.- В2'! = 0, ф 0, /В) ф {(0, 0)} м ф {(к. - 1 ,к- 1)};
8) 1/(В) = {0}: I = {(0,0)};
9) и (В) = {1}: I = {(к — 1,к — 1)}.
Доказательство. Пусть существует Д-замкнутый класс А функций из Рц2, для которого верны равенства ВАЛ) = В и 1псЗ(Л.) = I. Единственность такого класса следует из утверждения леммы 2.8. Докажем необходимость указанных в утверждении теоремы соотношений для множества I в зависимости от основания класса В.