Введение
1 Определения и основные свойства операции расширенной суперпозиции 12
1.1 Основные определения и обозначения 12
1.2 Операция расширенной суперпозиции 15
1.3 Свойства операции расширенной суперпозиции 17
2 Критерий выразимости функций в терминах расширенной суперпозиции 21
2.1 Формулировка и доказательство критерия выразимости . 21
2.2 Критерии согласованности 24
3 Критерий универсальной разложимости классов булевых функций 36
3.1 Вспомогательные утверждения 36
3.2 Формулировка и доказательство критерия универсальной разложимости 42
4 P-пополнения замкнутых классов булевых функций 45
4.1 Вспомогательные определения 47
4.2 Базовые P-пополнения классов L, U01 и SU 48
4.3 Базовые P-пополнения класса M01 52
4.4 Базовые P-пополнения класса T0 56
4.5 Базовые P-пополнения классов вида Om 57
4.6 Базовые P-пополнения класса K01 63
4.7 Базовые P-пополнения класса S 67
4.8 Теорема о множестве базовых P-пополнений 69
4.9 Теорема о множестве P-пополнений 70
4.10 Отличие некоторых P-пополнений от замкнутых классов 81
5 Вопросы полноты для P2 и предполных классов булевых функций 84
5.1 Вспомогательные утверждения 84
5.2 Полнота в классе P2 89
5.3 Полнота в классе T1 94
5.4 Полнота в классе S 100
5.5 Полнота в классе M 108
5.6 Полнота в классе L 111
Список литературы
