У підручнику в логічній послідовності викладено основні поняття та методи дискретної математики. Окрім таких розділів, як теорія множин і математична логіка, теорія графів, основи теорії кодування, теорія булевих функцій, теорія алгоритмів та формальних мов, які традиційно входять до базового курсу дисципліни, розглянуто також основи теорії складності обчислень та деякі застосування дискретної математики у штучному інтелекті. За змістом та обсягом підручник відповідає навчальним планам дисципліни "Дискретна математика" для студентів базових напрямів "Комп'ютерні науки", "Комп'ютеризовані системи, автоматика та управління", "Комп'ютерна інженерія" та "Прикладна математика". Стислий зміст Передмова 7 Розділ 1. Основи: логіка та методи доведення, множини 9 Розділ 2. Комбінаторний аналіз 48 Розділ 3. Теорія графів 88 Розділ 4. Дерева та їх застосування 150 Розділ 5. Відношення 185 Розділ 6. Основи теорії кодування 215 Розділ 7. Булеві функції 235 Розділ 8. Мови, граматики й автомати 276 Розділ 9. Основи теорії алгоритмів 312 Розділ 10. Комбінаторні задачі та складність обчислень 330 Термінологічний словник 355 Література 361 Алфавітний покажчик 363 Зміст Передмова 7 Розділ 1. Основи: логіка та методи доведення, множини 9 1.1. Логіка висловлювань 9 1.2. Закони логіки висловлювань 15 1.3. Нормальні форми логіки висловлювань 17 1.4. Логіка першого ступеня 19 1.5. Закони пасіки першого ступеня 23 1.6. Випереджена нормальна форма 25 1.7. Логічне виведення в логіці висловлювань 26 1.8. Застосування правил виведення в логіці висловлювань 28 1.9. Метод резолюцій 30 1.10. Правила виведення в численні предикатів 32 1.11. Методи доведення теорем 34 1.12. Множина. Кортеж. Декартів добуток 35 1.13. Операції над множинами. Доведення рівностей з множинами 37 1.14. Комп'ютерне подання множин 39 Контрольні запитання та завдання 40 Комп'ютерні проекти 47 Розділ 2. Комбінаторний аналіз 48 2.1. Основні правила комбінаторного аналізу. Розміщення та сполучення 48 2.2. Обчислення кількості розміщень і сполучень 50 2.3. Перестановки 51 2.4. Біном Ньютона 53 2.5. Поліноміальна теорема 55 2.6. Задача про цілочислові розв'язки 56 2.7. Числа Стірлінга другого роду та числа Белла 56 2.8. Генерування перестановок 57 2.9. Генерування сполучень 59 2.10. Генерування розбиттів множини 61 2.11. Рекурентні рівняння 62 2.12. Розв'язування рекурентних рівнянь 63 2.13. Принцип коробок Діріхле 68 2.14. Принцип включення-виключення 69 2.15. Принцип включення-виключення в альтернативній формі 70 2.16. Твірні функції 71 Контрольні запитання та завдання 82 Комп'ютерні проекти 87 Розділ 3. Теорія графів 88 3.1. Основні означення та властивості 88 3.2. Деякі спеціальні класи простих графів 94 3.3. Способи подання графів 95 3.4. Шляхи та цикли. Зв'язність 100 3.5. Ізоморфізм графів 105 3.6. Ейлерів цикл у графі 108 3.7. Гамільтонів цикл у графі 111 3.8. Зважені графи й алгоритми пошуку найкоротших шляхів 113 3.9. Обхід графів 120 3.10. Пленарні графи 124 3.11. Розфарбовування графів 126 3.12. Незалежні множини вершин. Кліки 130 3.13. Паросполучення в графах. Теорема Холла 132 3.14. Найбільше паросполучення у дводольних графах 134 Контрольні запитання та завдання 138 Комп'ютерні проекти 148 Розділ 4. Дерева та їх застосування 150 4.1. Основні означення та властивості 150 4.2. Рекурсія. Обхід дерев. Префіксна та постфіксна форми запису виразів 154 4.3. Бінарне дерево пошуку 160 4.4. Дерево прийняття рішень 163 4.5. Бектрекінг (пошук із поверненнями)... 170 4.6. Каркаси (з'єднувальні дерева) 175 Контрольні запитання та завдання 177 Комп'ютерні проекти 182 Розділ 5. Відношення 185 5.1. Відношення та їх властивості 185 5.2. Відношення еквівалентності 188 5.3. Відношення часткового порядку 190 5.4. Топологічне сортування 192 5.5. Операції над відношеннями 195 5.6. Замикання відношень 197 5.7. Бази даних і відношення 202 Контрольні запитання та завдання 204 Комп'ютерні проекти 213 Розділ 6. Основи теорії кодування 215 6.1. Алфавітне й рівномірне кодування 215 6.2. Достатні умови однозначності декодування. Властивості роздільних кодів 216 6.3. Оптимальне кодування 220 6.4. Коди, стійкі до перешкод. Коди Хеммінга 226 Контрольні запитання та завдання 232 Комп'ютерні проекти 234 Розділ 7. Булеві функції 235 7.1. Означення булевої функції. Реалізація функцій формулами 235 7.2. Алгебри булевих функцій 240 7.3. Спеціальні форми подання булевих функцій 243 7.4. Повнота й замкненість 250 7.5. Мінімізація булевих функцій 257 7.6. Реалізація булевих функцій схемами з функціональних елементів 267 Контрольні запитання та завдання 272 Комп'ютерні проекти 275 Розділ 8. Мови, граматики й автомати 276 8.1. Мови 276 8.2. Формальні породжувальні граматики 278 8.3. Типи граматик (ієрархія Хомскі) 281 8.4. Дерева виведення 283 8.5. Форми Бекуса-Наура 284 8.6. Скінченні автомати з виходом 285 8.7. Скінченні автомати без виходу 289 8.8. Подання мов 294 Контрольні запитання та завдання 303 Комп'ютерні проекти 310 Розділ 9. Основи теорії алгоритмів 312 9.1. Основні вимоги до алгоритмів 312 9.2. Машини Тьюрінга 314 9.3. Обчислення числових функцій на машинах Тьюрінга 319 9.4. Теза Тьюрінга. Приклади алгоритмічно нерозв'язних проблем 320 9.5. Рекурсивні функції 323 9.6. Теза Чорча. Зв'язок рекурсивних функцій із машинами Тьюрінга 327 Контрольні запитання та завдання 328 Комп'ютерний проект 329 Розділ 10. Комбінаторні задачі та складність обчислень 330 10.1. Масові задачі, алгоритми та складність 330 10.2. Задачі розпізнавання, мови та кодування 334 10.3. Детерміновані машини Тьюрінга та клас Р 336 10.4. Недетерміновані машини Тьюрінга та клас NP 338 10.5. Поліноміальна звідність і NР-повні задачі 341 10.6. Теорема Кука 344 10.7. Приклади NР-повних задач. Доведення NР-повноти 349 Контрольні запитання та завдання 354 Термінологічний словник 355 Література 361 Алфавітний покажчик 3