Введение
1 Автоматное замыкание 27
1.1 Основные определения 27
1.2 Автоматное замыкание 29
1.3 Описание автоматно замкнутых классов 30
2 Обобщенные формулы 37
2.1 Определение обобщенных формул 37
2.2 Соотношение между обобщенным и автоматным замыканиями 43
2.3 Свойства обобщенных формул 44
2.4 Реализация функций из класса 01
2.4.1 Пары наборов 54
2.4.2 Отношение частичного порядка на множестве наборов 59
2.4.3 Различные допустимые последовательности 66
2.4.4 Доказательства основных утверждений 73
2.5 Реализация функций из классов 0 и 1 77
3 Универсальные автоматы 82
3.1 Определения и различные постановки задачи 82
3.1.1 Неинициальный автомат 83
3.1.2 Инициальный автомат с многократной подачей наборов 85
3.1.3 Инициальный автомат с однократной подачей наборов 86
3.2 Булев автомат с двумя константными состояниями 87
3.2.1 Свойства автоматов из множества V2() 88
3.2.2 Верхняя оценка числа функций, реализуемых квазиуниверсальным автоматом из V2() 94
3.2.3 Условия квазиуниверсальности автомата из V2() 101
3.3 Булев автомат с тремя константными состояниями 106
3.3.1 Примеры и оценка снизу 107
3.3.2 Оценка сверху, первый случай 113
3.3.3 Оценка сверху, второй случай 123
3.3.4 Условия квазиуниверсальности автомата c тремя константными состояниями 128
3.4 Булев автомат с константными состояниями, 3 164
3.4.1 Свойства автоматов с состояниями 165
3.4.2 Оценка сверху для автоматов из множества V1() 167
3.4.3 Пример автомата с 2 + 2 состояниями, реализующего все булевы функции кроме констант 170
Заключение 173
Литература
