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

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

Оглавление
Введение

1 Определения и основные свойства операции расширенной суперпозиции

1.1 Основные определения и обозначения

1.2 Операция расширенной суперпозиции

1.3 Свойства операции расширенной суперпозиции

2 Критерий выразимости функций в терминах расширенной суперпозиции

2.1 Формулировка и доказательство критерия выразимости

2.2 Критерии согласованности

3 Критерий универсальной разложимости классов булевых функций

3.1 Вспомогательные утверждения

3.2 Формулировка и доказательство критерия универсальной
разложимости
4 Г-пополнения замкнутых классов булевых функций
4.1 Вспомогательные определения
4.2 Базовые Г-пополнения классов Б, Ги и 5Г
4.3 Базовые Г-пополпения класса Мщ
4.4 Базовые Г-пополнения класса Тц
4.5 Базовые Г-пополнепия классов вида От
4.6 Базовые Г-пополнения класса К$
4.7 Базовые Г-пополнения класса Б
4.8 Теорема о множестве базовых Г-пополнений
4.9 Теорема о множестве Г-пополнений
4.10 Отличие некоторых Г-пополнений от замкнутых классов
5 Вопросы полноты для Гг и предполных классов булевых функций
5.1 Вспомогательные утверждения
5.2 Полнота в классе Гг
5.3 Полнота в классе Т
5.4 Полнота в классе Г
5.5 Полнота в классе М
5.6 Полнота в классе Ь
Список литературы
Введение
Диссертация относится к математической теории функциональных систем — одному из основных разделов дискретной математики и математической кибернетики. В ней рассматривается задача о реализации булевых функций формулами специального вида. Вводится понятие операции расширенной суперпозиции. Исследуются вопросы выразимости и полноты в терминах рассматриваемой операции.
В теории функциональных систем важное место занимают задачи классификации функций в соответствии с различными свойствами этих функций. Исследование свойств функций позволяет объединить эти функции в отдельные классы и зачастую помогает получить более полное понимание структуры функциональных множеств и на основе полученной классификации выделить некоторый более общий подход, применимый к другим задачам теории дискретных функций. Описание и изучение множеств функций, замкнутых относительно операции суперпозиции, является одним из наиболее известных подходов к решению задач классификационного характера. Классическим результатом в этой области является описание множества всех классов булевых функций, замкнутых относительно операции суперпозиции. Это описание было получено Э. Постом [46,47] в 1920 году. Как показал Пост, мощность множества классов булевых функций, замкнутых относительно операции суперпозиции, является счетной. Ю. И. Янов и
А. А. Мучник [43] установили, что в /с-значной логике при к > 3 существуют примеры замкнутых классов, не имеющих базиса, а также классов со счетным базисом. Отсюда, в частности, следует, что множество всех замкнутых классов /о-значной логики при к > 3 имеет континуальную мощность, что значительно затрудняет исследование.

Следствие 2.2.21 Для любого инвариантного класса Я выполнено равенство
[Дн]^ = [5]^ П [То]/г П [Т^р.
Утверждение 2.2.22 Пусть Я С Еп, п > 1, а г(х 1,...,хп) — частичная функция, определенная па мноо/сестве Л. Функция г является согласованной с классом БМ тогда и только тогда, когда она является согласованной с классами М, О2 и I2.
Доказательство. Пусть частичная функция г является согласованной с классами М, О2 и I2, и выполняются соответствующие условия согласованности. Построим доопределение функции г в классе БМ. Рассмотрим множество доопределяющих функций частичной функции г. Обозначим это множество через Д. Очевидно, что Д ф 0. Пусть 7 — набор длины п, такой, что существует набор а Е Я, такой, что 7 > а, г (а) = 1. Множество всех таких наборов обозначим через Гр Заметим, что это множество может быть пустым. Рассмотрим подмножество Яг множества Я*, содержащее все функции ф(х,... ,хп) Е Яр удовлетворяющих следующему условию: для любого набора 7 Е Г1 выполняется соотношение /(7) = 1. В силу согласованности функции г с классом М, для любых двух наборов а,р е Я, таких, что а > /3, для произвольной функции /(ад,... ,хп) Е Я] выполняется соотношение /(5) > /(/5). Следовательно, Яг ф 0. Пусть 7 — набор длины п, такой, что существует набор а Е Я, такой, что 7 <5, /(5) = 0. Множество всех таких наборов обозначим через Го- Рассмотрим подмножество множества Яг, содержащее все функции /(яд,..., хп) Е Яг, удовлетворяющих следующему условию: для любого набора 7 6 Го выполняется соотношение /(7) = 0. Обозначим это множество через Я3. Аналогично доказывается, что Я3 ф 0. Несложно видеть, что Я Е ГоиГр ГоПД = 0.
Докажем, что в множестве Го нет двух противоположных наборов. Предположим противное. Пусть существует такой набор 7 6 Го, что
7 € Го- Согласно определению множества Го существуют такие наборы а,Р Е Я, что 5 > 7, (5 > 7, г(й) = г((3) — 0. Несложно видеть, что поскольку наборы 7 и 7 не имеют общей нулевой компоненты, то и наборы а и (3 не имеют общей нулевой компоненты. Следовательно, функция г не