Супрун В.П. Основы теории БУЛЕВЫХ ФУНКЦИЙ

Основы теории булевых функций 2017. 208 с.

Онлайн-книга

Аннотация

Учебное пособие предназначено студентам младших курсов высших учебных учреждений математического (или технического) профиля для начального изучения одного из наиболее важных и сложных разделов дискретной математики --- теории булевых функций.

Основная область применения теории булевых функций --- разработка методов, алгоритмов и программных средств синтеза (проектирования) цифровых устройств на элементах заданного логического базиса. Кроме того,... (Подробнее)

Содержание

Содержание				5
От автора				10
Глава 1. Булевы функции. Способы задания				12
1. Одномерная таблица истинности				13
2. Число булевых функций n переменных				14
3. Двумерные таблицы истинности				15
4. Элементарные булевы функции				17
5. Характеристическое множество булевой функции				19
6. Задачи для самостоятельного решения				21
Глава 2. Формулы и основные равносильности				25
1. Тавтологии				27
2. Основные логические равносильности				29
3. Дизъюнктивное и конъюнктивное разложения				31
4. Задачи для самостоятельного решения				34
Глава 3. Нормальные формы булевых функций				37
1. Постановка задачи минимизации				37
2. Дизъюнктивные нормальные формы				38
3. Понятие импликанты				41
4. Конъюнктивные нормальные формы				42
5. Полиномиальные нормальные формы				44
6. Задача минимизации булевых функций в классе ДНФ				46
7. Задачи для самостоятельного решения				47
Глава 4. Кратчайшее покрытие булевых матриц				49
1. Постановка задачи				49
2. Задача о переводчиках				51
3. Методы поиска кратчайшего покрытия булевых матриц				52
4. Ядро булевой матрицы				56
5. Задачи для самостоятельного решения				57
Глава 5. Метод минимизации Квайна				59
1. Описание метода				59
2. Задачи для самостоятельного решения				62
Глава 6. Метод минимизации Квайна—Мак-Класки				65
1. Модификация метода				65
2. Пример применения модификации				66
3. Задачи для самостоятельного решения				68
Глава 7. Другие методы минимизации				69
1. Метод Блейка—Порецкого				69
2. Дизъюнктивный критерий поглощения				71
3. Примеры применения дизъюнктивного критерия поглощения				73
4. Метод минимизации Нельсона				75
5. Задачи для самостоятельного решения				76
Глава 8. Полиномы Жегалкина				79
1. Монотонно поляризованные полиномы				79
2. Общий вид полинома Жегалкина				81
3. Классические методы построения полиномов Жегалкина				82
4. Оригинальные методы построения полиномов Жегалкина				85
5. Задачи для самостоятельного решения				89
Глава 9. Полиномы Рида—Маллера				93
1. Основные понятия и определения				93
2. Обобщение метода преобразования СДНФ				94
3. Модификация метода преобразования СДНФ				95
4. Метод неопределенных коэффициентов				97
5. Метод деления таблицы истинности пополам				98
6. Кратчайшие полиномы Рида—Маллера				100
7. Метод минимизации булевых функций в классе полиномов Рида—Маллера				101
8. Пример применения метода минимизации				102
9. Функция Шеннона для оценки сложности полиномов Рида—Маллера				103
10. Примеры сложных булевых функций				104
11. Минимальные полиномы Рида—Маллера				105
12. Задачи для самостоятельного решения				108
Глава 10. Арифметические полиномы				110
1. Основные понятия и примеры				110
2. Общий вид арифметического полинома				112
3. Методы арифметического разложения булевых функций				113
4. Свойства арифметических полиномов				118
5. Задачи для самостоятельного решения				119
Глава 11. Симметрические булевы функции				122
1. Свойства симметрических булевых функций				122
2. Дизъюнктивное разложение симметрических булевых функций				125
3. Число симметрических булевых функций				126
4. Суперпозиция симметрических булевых функций				126
5. Примеры симметрических булевых функций				128
6. Задачи для самостоятельного решения				130
Глава 12. Полиномиальное разложение симметрических булевых функций				134
1. Основные понятия и определения				134
2. Метод треугольника и его модификации				135
3. Задачи для самостоятельного решения				139
Глава 13. Существенные и фиктивные переменные				142
1. Определение, свойства булевых переменных				142
2. Нахождение фиктивных переменных				144
3. Введение фиктивных переменных				146
4. Задачи для самостоятельного решения				146
Глава 14. Булево дифференцирование				148
1. Определение булевой производной				148
2. Свойства булевых производных				150
3. Булевы производные высших порядков				152
4. Примеры вычисления булевых производных				155
5. Задачи для самостоятельного решения				156
Глава 15. Основные замкнутые классы				158
1. Свойства замыкания				158
2. Булевы функции, сохраняющие константу 0				160
3. Булевы функции, сохраняющие константу 1				160
4. Самодвойственные булевы функции				161
5. Линейные булевы функции				163
6. Задачи для самостоятельного решения				165
Глава 16. Монотонные булевы функции				168
1. Свойства монотонных булевых функций				168
2. Критерии монотонности булевых функций				170
3. Разложение монотонных булевых функций				171
4. Нижние единицы монотонных булевых функций				175
5. Дуализация монотонных булевых функций				176
6. Оценки числа монотонных булевых функций				178
7. Предполные классы булевых функций				180
8. Задачи для самостоятельного решения				181
Глава 17. Полнота системы булевых функций				183
1. Проблема функциональной полноты				183
2. Критерий функциональной полноты				184
3. Таблица Поста				187
4. Минимальные базисы				189
5. Выделение минимальных базисов				190
6. Задачи для самостоятельного решения				192
Глава 18. Булевы функции шефферовского типа				195
1. Число шефферовских булевых функций				195
2. Симметрические булевы функции шефферовского типа				197
3. Задачи для самостоятельного решения				198
Рекомендуемая литература				200

Об авторе

Супрун Валерий Павлович

Кандидат технических наук, доцент механико-математического факультета Белорусского государственного университета. Область научных интересов — дискретная математика и вычислительная техника. Автор около 350 изобретений в области автоматики и вычислительной техники. Награжден золотой медалью и дипломом Всемирной организации интеллектуальной собственности (ВОИС) как "Лучший изобретатель Беларуси 2006 года". Заслуженный работник Белорусского государственного университета.

Автор 80 научных статей по дискретной математике, а также учебных пособий "Математика для старшеклассников: Задачи повышенной сложности" (URSS), "Математика для старшеклассников: Нестандартные методы решения задач" (URSS), "Математика для старшеклассников: Методы решения и доказательства неравенств" (URSS), "Математика для старшеклассников: Дополнительные разделы школьной программы" (URSS), "Математика для старшеклассников: Нестандартные методы решения уравнений повышенной сложности" (URSS), "Основы теории булевых функций" (URSS), "Основы математической логики" (URSS). Многие книги автора были переведены и выходили в URSS также на испанском языке.