Марченков С. С. Булевы функции.— М., 2002.— 68 с.
Брошюра знакомит читателя с булевыми функциями — одним из важнейших классов дискретных функций. В ней излагаются основные понятия
теории булевых функций, доказывается критерий функциональной полноты и рассматриваются вопросы сложности реализации булевых функций.
Брошюра предназначена для школьников старших классов и студентов первых курсов.
ОГЛАВЛЕНИЕ
Предисловие.....................................................................3
Глава I
ЭЛЕМЕНТАРНЫЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ
§ 1. Табличное задание булевых функций........................................................5
§ 2. Некоторые элементарные булевы функции..............................................7
§ 3. Существенные и фиктивные переменные ................................................9
§ 4. представление булевых функций формулами........................................12
§ 5. Эквивалентность формул..............................................................................15
§ 6. Замыкание. Замкнутые классы ..................................................................18
§ 7. Разложение булевой функции но переменной..........................................21
§ 8. Двойственность. Принцип двойственности..............................................23
§ 9. Полиномы Жегалкина..................................................................................26
Глава II ЗАМКНУТЫЕ КЛАССЫ И ПОЛНОТА
§1. Класс самодвойственных функций............................................................30
§ 2. Класс линейных функций............................................................................31
§ 3. Класс монотонных функций........................................................................34
§ 4. Критерий полноты..........................................................................................38
§ 5. Замкнутые классы, содержащие константы............................................40
Глава IIІ
СЛОЖНОСТЬ РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ
§ 1. Минимизация ДНФ........................................................................................45
§ 2. Схемы из функциональных элементов......................................................52
§ 3. Выполнимость КНФ......................................................................................61
Ответы, решения, указания................................................................................65
