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


Второе издание — 1992 г.
Для студентов и преподавателей университетов и технических вузов, в которых изучается дискретная математика.
ОГЛАВЛЕНИЕ
Предисловие к третьему изданию ……………………………….. 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
§ 6. Полнота и замкнутые классы …………………………………..81
Глава III. k-значные логики
§ 1. Представление функций k-значных логик формулами …………. 88
1. Элементарные функции k-значных логик и соотношения между ними (88). 2. Разложение функций k-значных логик в первую и вторую формы (91).
§ 2. Замкнутые классы и полнота в k-значных логиках…………… 92
1. Некоторые замкнутые классы 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



Читать онлайн
скачать бесплатно


Теги:
сборник задач по дискретной математике, Гаврилов дискретная математика, Гаврилов сборник задач, задачник по дискретной математике

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