Введение
1 Синтез формул с ограниченной глубиной альтернирования и схем из функциональных элементов ограниченной ширины 30
1.1 Формулы с ограниченной глубиной альтернирования 30
1.1.1 Вспомогательные определения и утверждения 30
1.1.2 Верхняя оценка функции Шеннона 36
1.1.3 Нижняя мощно стная оценка функции Шеннона
1.2 Реализация функций из некоторых классов, связанных с конечными грамматиками, формулами глубины альтернирования 3 47
1.3 Схемы с ограниченной памятью 52
2 Синтез формул в базисах с прямыми и итеративными переменными 60
2.1 Некоторые особенности задачи и порядок функции Шеннона 60
2.2 Сложность формул в базисах, итеративное замыкание которых содержит все монотонные функции 72
2.3 Асимптотические оценки высокой степени точности для некоторых базисов 83
Заключение 99
Литература
