Гаврилов Г. П., Сапоженко А. А.
Задачи и упражнения по дискретной математике

В пособие включены задачи и упражнения по конечнозначным логикам (в том числе по алгебре логики), по теории автоматов, теории алгоритмов, теории графов и сетей, теории кодирования, комбинаторике, минимизации булевых функций и синтезу схем и формул, реализующих булевы функции. Имеются задачи, предназначенные для первоначальной проработки и осво- освоения методов дискретной математики, а также задачи для углубленного изучения предмета.
Для студентов и преподавателей университетов и технических вузов, в которых изучается дискретная математика.

Предисловие к третьему изданию	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-значных логик. Представление функций из P_k полиномами по модулю k (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. Расстояние Хэмминга, шары, сферы и циклы в n-мерном кубе (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

скачать (DjVu, 3372 Кб)

:: назад к литературе ::

Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике

ОГЛАВЛЕНИЕ

Гаврилов Г. П., Сапоженко А. А.
Задачи и упражнения по дискретной математике