Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике: Учеб. пособие. — 3-е изд., перераб. — М., 2005. - 416 с.
В пособие включены задачи и упражнения по конечнозначным логикам (в том числе по алгебре логики), по теории автоматов, теории алгоритмов, теории графов и сетей, теории кодирования, комбинаторике, минимизации булевых функций и синтезу схем и формул, реализующих булевы функции. Имеются задачи, предназначенные для первоначальной проработки и освоения методов дискретной математики, а также задачи для углубленного изучения предмета.
Для студентов и преподавателей университетов и технических вузов, в которых изучается дискретная математика.
ОГЛАВЛЕНИЕ
Предисловие к третьему изданию ...................................... 6
Предисловие ко второму изданию ...................................... 7
Глава I
Способы задания и простейшие свойства функций алгебры логики
§ 1. Функции алгебры логики и способы их задания. Операция суперпозиции ............................................................ 9
1. Основные понятия и факты, связанные с булевым кубом и булевыми функциями (9). 2. Элементы булева куба. Первичные представления о булевых функциях (15). 3. Формулы. Реализация булевых функций формулами (23). 4. Двойственные функции. Принцип двойственности (31). 5. Фиктивные и существенные переменные. Отождествление переменных у булевых функций (33).
§ 2. Специальные представления булевых функций .................... 39
1. Разложения булевых функций по переменным. Совершенные дизъюнктивная и конъюнктивная нормальные формы (39). 2. Дизъюнктивные и конъюнктивные нормальные формы (47). 3. Полиномы Жегалкина (52).
Глава II
Замкнутые классы и полнота систем функций алгебры логики
§ 1. Понятия функциональной замкнутости и полноты ................................60
§ 2. Класс самодвойственных функций ................................................................64
§ 3. Класс линейных функций ..................................................................................68
§ 4. Классы функций, сохраняющих константы ..............................................72
§ 5. Класс монотонных функций ..............................................................................75
§ 6. Полнота и замкнутые классы ..........................................................................81
Глава III. k-значные логики
§ 1. Представление функций k-значных логик формулами ............. 88
1. Элементарные функции k-значных логик и соотношения между ними (88). 2. Разложение функций k-значных логик в первую и вторую формы (91).
§ 2. Замкнутые классы и полнота в k-значных логиках............... 92
1. Некоторые замкнутые классы k-значных логик. Представление функций из Pk полиномами по модулю к (92). 2. Исследование систем функций k-значной логики на полноту (97).
Глава IV
Ограниченно-детерминированные функции
§ 1. Отображения последовательностей ............................... 102
1. Основные понятия и факты, связанные с заданием детерминированных функций (102). 2. Типовые примеры (105). 3. Выявление свойства детерминированности функции. Эквивалентность детерминированных функций. Остаточные функции (111). 4. Выявление свойства ограниченной детерминированности функции. Порожденные и автономные функции. Строение классов эквивалентности. Мощности некоторых множеств отображений (119).
§ 2. Диаграммы, таблицы, канонические уравнения, схемы........... 126
1. Диаграммы Мура, канонические таблицы и канонические уравнения (126). 2. Операции над детерминированными функциями (145). 3. Реализация ограниченно-детерминированных функций схемами (159). 4. Замкнутые классы и полнота в множествах детерминированных и ограниченно-детерминированных функций (171).
Глава V Элементы теории алгоритмов
§ 1. Машины Тьюринга и операции над ними. Функции, вычислимые
на машинах Тьюринга ........................................... 178
1. Простейшие свойства машин Тьюринга (178). 2. Операции над машинами Тьюринга (186). 3. Вычислимые функции (190).
§ 2. Классы вычислимых и рекурсивных функций ................... 195
1. Операции суперпозиции, примитивной рекурсии и минимизации (195). 2. Некоторые специальные свойства рекурсивных функций (201).
Глава VI Графы и сети
§ 1. Основные понятия теории графов ................................ 203
1. Простейшие свойства графов. Изоморфизм графов (203). 2. Ориентированные графы (210).
§ 2. Планарность и раскраска графов ................................. 215
§ 3. Деревья и сети.................................................... 219
1. Корневые деревья (219). 2. Двухполюсные сети (223).
Глава VII Элементы теории кодирования
§ 1. Алфавитное кодирование. Критерий однозначности кодирования . 230
§ 2. Коды с минимальной избыточностью ..............................235
§ 3. Самокорректирующиеся коды......................................241
1. Расстояние Хэмминга, шары, сферы и циклы в п-мерном кубе (241). 2. Коды, обнаруживающие и исправляющие ошибки (244).
§ 4. Линейные коды .................................................... 249
Глава VIII Элементы комбинаторики
§ 1. Перестановки и сочетания. Свойства биномиальных коэффициентов ............................................................ 253
§ 2. Формула включений и исключений ................................ 262
§ 3. Возвратные последовательности, производящие функции, рекуррентные соотношения..............................................265
§ 4. Теория Пойа ....................................................... 273
§ 5. Асимптотические оценки и неравенства ........................... 277
§ 6. Оценки в теории графов и сетей ...................................284
Глава IX Минимизация булевых функций
§ 1. Структура граней n-мерного куба. Покрытия и тесты для таблиц 290
§ 2. Методы построения сокращенной д. н. ф ........................... 296
§ 3. Методы построения тупиковых, минимальных и кратчайших д.н.ф...............................................................301
Глава X
Реализация булевых функций схемами и формулами
§ 1. Схемы из функциональных элементов ............................. 306
§ 2. Контактные схемы и формулы.....................................312
Ответы, указания, решения ......................................... 324
Список литературы.................................................. 412
Предметный указатель .............................................. 414
