Оглавление
Введение
1 Определения и вспомогательные утверждения
1.1 Определения и обозначения
1.2 Связь между двумя мерами сложности формул.
1.3 Некоторые оценки сложности булевых функций
1.4 Некоторые свойства функций из 12.
1.5 Простейшие методы синтеза.
1.6 Порождающие системы максимальных классов
2 Сложность псевдолинейных функций
2.1 Псевдолинейные функции и их свойства
2.2 Классы Я П , С, г и С
2.3 Класс С2 .
2.3.1 Свойства минимальных формул.
2.3.2 Нижняя оценка для функции Шеннона.
2.3.3 Верхняя оценка для функции Шеннона
2.3.4 Верхняя оценка сложности произвольной функции.
2.3.5 Нижняя оценка сложности произвольной функции
3 Сложность функций из максимальных классов
3.1 Представление функции из максимальных классов.
3.1.1 Специальное разбиение множества Ь .
3.1.2 Верхняя оценка мощности разбиения.
3.1.3 Представление функций из множества Нп.
3.2 Верхние оценки для функций Шеннона
3.3 Нижние оценки для функций Шеннона.
3.4 Асимптотически точные формулы для функций Шеннона.
4 Глубина формул, реализующих функции из Рл
4.1 Классы, проекция которых содержит функцию Лр или 6
4.2 Классы, проекция которых совпадает с или .9о1
4.3 Классы, проекция которых совпадает с классом БМ
Литература
- Київ+380960830922