Чашкин А.В. Булевы функции и преобразования - МГТУ им. Баумана, 158 с.
Методические указания для студентов Московского Государственного Технического Университета им. Н.Э. Баумана (Факультет ИУ)
Оглавление
1. Булевы функции ...........3
1.1. Булев куб .............3
1.2. Булевы функции ..........8
1.3. Формулы. Реализация булевых функций формулами ...........14
1.4. Специальные представления функций ............21
1.5. Замкнутые классы булевых функций ............27
1.6. Критерий полноты ..............29
2. Линейные булевы пространства 33
2.1. Линейные булевы пространства.............33
2.2. Линейные операторы ...............37
2.3. Матрицы....................40
2.4. Определители ................43
3. Линейные булевы пространства и булевы функции 47
3.1. Системы линейных булевых уравнений ......................47
3.2. Вычисление коэффициентов АНФ..........................55
3.3. Линейное хеширование................................58
3.4. Линейные коды ....................................63
3.5. Коды Рида-Малера ..................................65
4. Сложность вычисления булевых функций 71
4.1. Схемы из функциональных элементов .......................71
4.2. Булевы функции трех переменных. Построение схем ..............77
4.3. Преобразования схем.................................81
4.4. Булевы функции трех переменных. Нижние оценки сложности.........84
4.5. Сложность функций, зависящих от большого числа аргументов ........88
5. Специальные булевы функции и операторы 94
5.1. Вычисление суммы и разности двух целых чисел.................94
5.2. Вычисление суммы нескольких целых чисел ...................99
5.3. Умножение целых чисел ...............................103
5.4. Сортировка.......................................107
5.5. Сложность вычисления коэффициентов АНФ...................110
5.6. Вычисление преобразования Фурье.........................111
6. Асимптотические методы построения схем 115
6.1. Вычисление дизъюнкции п функций........................115
6.2. Вычисление систем дизъюнкций. Широкие системы...............117
6.3. Вычисление систем дизъюнкций. Узкие системы.................123
6.4. Вычисление всех элементарных конъюнкций...................126
6.5. Асимптотически минимальный метод .......................128
7. Средняя сложность булевых функций 133
7.1. Неветвящиеся программы..............................133
7.2. Функции трех переменных .............................137
7.3. Симметрические функции..............................138
7.4. Асимптотические методы построения программ.................143
7.5. Сложность и средняя сложность функций.....................146
Литература 153
Предметный указатель 155
