Дискретная математика для инженера. 4-е изд.

В книге изложены основные понятия теории множеств, общей алгебры, логики, теории графов, теории алгоритмов и формальных систем, теории автоматов. По сравнению с изданием 1988г. заново написаны разделы по теории графов и сложности вычислений.Для инженеров, специализирующихся в области автоматизированного управления и проектирования, вычислительной техники, информационных технологий, передачи информации, а также для студентов и аспирантов соответствующих специальностей.Предисловие к третьему изданиюТретье издание книги, выходящее через 15 лет после второго издания, заметно от него отличается и содержанием, и составом авторов. Главы, написанные Г. М. Адельсоном-Вельским, в настоящем издании заменены.Глава 4 «Графы» написана заново и существенно отличается от прежней отбором материала. В частности, в нее включены матричные методы анализа графов, сведения о пространстве циклов и планарных графах. Особое внимание уделено оптимизационным задачам на графах, имеющим широкие приложения.Глава 9 второго издания заменена новым параграфом 5.5 «Вычислительная сложность и NP-трудные задачи», который содержит современное и более компактное изложение теории NP-трудных задач. Кроме того, в главу 5 добавлены краткие сведения о различных моделях абстрактных машин.Глава 10 «Линейное программирование» удалена, поскольку ее предмет не принято относить к дискретной математике.Существенно обновлен список литературы. Как и в первых двух изданиях, этот список не имеет цели отразить историю предмета, приоритеты или дать его полное библиографическое описание. Его задача — указать работы, в которых вопросы, кратко упомянутые в книге, изложены более подробно.Я глубоко благодарен Г. М. Адельсону-Вельскому за нашу совместную работу над первыми версиями книги.Благодарю также Т. А. Таран за обширный список замечаний, поправок и уточнений ко второму изданию книги. О. П. Кузнецов, Москва, октябрь 2003 г.--------------------------------------------------------------------------------------ОглавлениеПредисловие к третьему изданию 3Глава первая. Множества, функции, отношения 41.1. Множества и операции над ними 41.2. Соответствия и функции 151.3. Отношения 27Глава вторая. Элементы общей алгебры 352.1. Операции на множествах и их свойства 352.2. Полугруппы, группы, решетки 41Глава третья. Введение в логику 503.1. Логические функции (функции алгебры логики) 503.2. Булева алгебра 563.3. Полнота и замкнутость 713.4. Язык логики предикатов 82Глава четвертая. Графы 914.1. Основные понятия 914.2. Пути и связность в неориентированных графах 994.3. Пути и связность в ориентированных графах 1074.4. Деревья 1144.5. Пространство циклов 1184.6. Двудольные и планарные графы 1254.7. Раскраски, устойчивость, покрытия 1324.8. Оптимизационные задачи на графах 137Глава пятая. Теория алгоритмов 1515.1. Предварительное обсуждение 1515.2. Машины Тьюринга 1635.3. Рекурсивные функции 1885.4. Вычислимость и разрешимость 2115.5. Вычислительная сложность и NP-трудные задачи 227Глава шестая. Формальные системы 2406.1. Формальные теории (логические исчисления).Исчисление высказываний 2426.2. Исчисление предикатови теории первого порядка 2546.3. Метатеория логических исчислений 2656.4. Абстрактные формальные системы 274Глава седьмая. Языки и грамматики 2917.1. Формальные грамматики и их свойства 2937.2. Операции над языками 3157.3. О семантике формальных языков 324Глава восьмая. Автоматы 3288.1. Основные понятия 3288.2. Распознавание множеств автоматами 3478.3. Сети из автоматов, их анализ и синтез 3668.4. Программная реализациялогических функций и автоматов 383Рекомендуемая литература 388Основная литература 388Дополнительная литература 390Предметный указатель 391