У навчальному посібнику в логічний послідовності викладено основні поняття дискретної математики згідно галузевого стандарту вищої освіти України по комп'ютерним і другим наукам. Теоретичний матеріал книги проілюстровано значною кількістю вправ і задач для набуття читачем практичного досвіду. За змістом та обсягом навчальний посібник відповідає навчальним планам дисципліни "Дискретна математика" для студентів різних спеціальностей вищих навчальних закладів, які вивчають дану дисципліну, аспірантів і спеціалістів, які використовують відповідні математичні і комп'ютерні методи, а також окремі розділи навчального посібника можуть бути використані відповідними технічними навчальними закладами і коледжами. ЗМІСТ Передмова..........................................................................................................8 Розділ 1. ТЕОРІЯ МНОЖИН..........................................................................10 1.1. Поняття множини.....................................................................................10 1.2. Способи задання множин........................................................................12 1.3. Операції над множинами....................................................................13 1.4. Алгебра множин.......................................................................................17 Контрольні запитання...............................................................................19 Задачі для самостійного розв'язування.....................................................20 Коментарі ......................................................................................................21 Розділ 2. ТЕОРІЯ ВІДНОШЕНЬ...................................................................22 2.1. Основні визначеня...................................................................................22 2.2. Бінарні відношення............................................................................23 2.3. Способи задання бінарних відношень...............................................24 2.4. Операції над бінарними відношеннями ..............................................27 2.5. Властивості бінарних відношень............................................................28 2.6. Композиція бінарних відношень .........................................................31 2.7. Функціональні відношення................................................................33 Контрольні запитання....................................................................................36 Задачі для самостійного розв'язування.........................................................37 Коментарі .................................................................................................... 39 Розділ 3. ЕЛЕМЕНТИ ТЕОРІЇ ЧИСЕЛ........................................................40 3.1. Найбільший спільний дільник...............................................................40 3.2. Найменше спільне кратне ...............................................................42 3.3. Непереривні дроби ..............................................................................43 3.4. Загальні визначення порівняння чисел.................................................48 3.5. Порівняння чисел і його властивості................................................48 3.6. Повна і приведена система вирахувань................................................51 3.7. Теореми Ейлера і Ферма.........................................................................53 3.8. Порівняння з одним невідомим..............................................................54 Контрольні запитання .................................................................................58 Задачі для самостійного розв'язування .....................................................58 Коментарі........................................................................................................59 Розділ 4. КОМБІНАТОРИКА............................................................................60 4.1. Основні правила комбінаторики................................................................60 4.2. Перестановки і розміщення без повторень................................................61 4.3. Розміщення і перестановки з повтореннями.............................................62 4.4. Сполучення...................................................................................................64 4.5. Метод включення-виключення............................................................66 4.6. Метод рекурентних співвідношень........................................................68 Контрольні запитання.........................................................................................69 Задачі для самостійного розв'язування.............................................................69 Коментарі.............................................................................................................70 Розділ 5. АЛГЕБРАЇЧНІ СТРУКТУРИ.............................................................71 5.1. Загальні визначення......................................................................................71 5.2. Найпростіші алгебраїчні структури............................................................75 5.3. Кільця і поля..................................................................................................77 5.4. Решітки ................................................................................................78 Контрольні запитання .......................................................................................81 Задачі для самостійного розв'язування...............................................................82 Коментарі..............................................................................................................82 Розділ 6. ЛОГІКА БУЛЯІ ЖЕГАЛКІНА............................................................83 6.1. Основні визначення логіки Буля..................................................................83 6.2. Способи задання логічних функцій.............................................................84 6.3. Елементарні логічні функції.........................................................................89 6.4. Основні закони алгебри логіки.....................................................................90 6.5. Перетворення логічних функцій...................................................................91 6.6. Властивості логічних функцій......................................................................93 6.7. Суперпозиція логічних функцій...................................................................95 6.8. Диз'юнктивне розкладання логічних функцій............................................95 6.9. Кон'юнктивне розкладання логічних функцій............................................99 6.10. Нормальні форми зображення логічних функцій................................103 6.11. Основні визначення логіки Жегалкіна ..................................................108 6.12. Закони алгебри Жегалкіна .......................................................................109 6.13. Поліном Жегалкіна.....................................................................................111 6.14. Методи побудови полінома Жегалкіна....................................................112 6.15. Дослідження логічних функцій ........................................................114 6.16. Мінімізація логічних функцій..................................................................122 Контрольні запитання...................................................................................138 Задачі для самостійного розв'язування.............................................................140 Коментарі.............................................................................................................143 Розділ 7. МАТЕМАТИЧНА ЛОГІКА...............................................................144 7.1. Основні визначення......................................................................................144 7.2. Висловлювання і логічні зв'язки ..............................................................145 7.3. Умовні і еквівалентні висловлювання........................................................149 7.4. Інтерпретація формул логіки висловлювань.............................................152 7.5. Дедуктивні висновки у логіці висловлювань............................................155 7.6. Побудова доведень у логіці висловлювань .............................................158 7.7. Логіка предикатів і квантори.......................................................................167 7.8. Формули логіки предикатів і їх рівносильність.....................................173 7.9. Закони і тотожності логіки предикатів......................................................177 7.10. Випереджені нормальні форми................................................................180 7.11. Побудова доведень у логіці предикатів...............................................182 Контрольні запитання.........................................................................................185 Задачі для самостійного розв'язування.............................................................186 Коментарі ..........................................................................................................190 Розділ 8. НЕЧІТКА ЛОГІКА........................................................................191 8.1. Основні визначення . . .................................................................................191 8.2. Основні характеристики логіки нечітких множин.................................193 8.3. Методи побудови функцій належності нечітких множин.......................194 8.4. Операції над нечіткими множинами..........................................................195 8.5. Властивості операцій над нечіткими множинами.....................................199 8.6. Поняття нечіткої і лінгвістичної змінної...................................................199 8.7. Нечіткі вислови і нечіткі моделі систем....................................................201 Контрольні запитання.........................................................................................205 Задачі для самостійного розв'язування.............................................................205 Коментарі ..........................................................................................................206 Розділ 9. ТЕОРІЯ ГРАФІВ ..............................................................................207 9.1. Основні терміни і визначення.....................................................................207 9.2. Способи задання графів...............................................................................211 9.3. Підграфи і ізоморфізм графів ..................................................................215 9.4. Маршрути, ланцюги та цикли.....................................................................218 9.5. Метричні характеристики графів .............................................................220 9.6. Вилучення ребра і вершини ......................................................................221 9.7. Введення ребра в граф і вершини в ребро.................................................222 9.8. Злиття і розщепленняя вершин та стягування ребра ..............................224 9.9. Об'єднання, перетин та добуток графів.....................................................225 9.10. Кільцева сума, різниця та доповнення графів ......................................227 9.11. Різновиди графів і їх властивості..............................................................229 9.12. Дослідження графів за допомогою матриць............................................239 Контрольні запитання ......................................................................................245 Задачі для самостійного розв'язування.............................................................246 Коментарі.............................................................................................................248 Розділ 10. АЛГОРИТМИ НА ГРАФАХ............................................................249 10.1. Алгоритм Дейкстри для пошуку найкоротших шляхів..........................249 10.2. Алгоритм Прима для побудови мереж мінімальної довжини...............253 10.3. Алгоритм Флойда - Уоршолла для пошуку найкоротших шляхів між усіма парами вершин.........................................................................................257 10.4. Алгоритм Форда - Фалкерсона для пошуку максимального потоку....261 10.5. Алгоритм пошуку заданого потоку мінімальної вартості.....................268 Контрольні запитання ......................................................................................271 Задачі для самостійного розв'язування.............................................................272 Коментарі.............................................................................................................274 Розділ 11. ДЕРЕВА.............................................................................................275 11.1. Визначення і властивості звичайних дерев..............................................275 11.2. Визначення і властивості орієнтованих дерев........................................278 Контрольні запитання .....................................................................................280 Задачі для самостійного розв'язування.............................................................280 Коментарі.............................................................................................................181 Розділ 12. ОСНОВИ ТЕОРІЇ КОДУВАННЯ.....................................................282 12.1. Алфавітне й рівномірне кодування ........................................................282 12.2. Оптимальне кодування ...........................................................................283 12.3. Завадостійке кодування.............................................................................289 12.4. Шифрування ............................................................................................292 12.5. Стиснення інформації................................................................................299 Контрольні запитання.........................................................................................309 Задачі для самостійного розв'язування.........................................................309 Коментарі.............................................................................................................310 Розділ 13. ТЕОРІЯ АВТОМАТІВ...............................................................311 13.1. Основні визначення...................................................................................311 13.2. Автомати Мілі, Мура, С-автомати...........................................................313 13.3. Способи задання автоматів..................................................................315 13.4. Перетворення автоматів Мура в автомати Мілі.....................................319 13.5. Перетворення автоматів Мілі в автомати Мура.....................................320 13.6. Ізоморфізм автоматів ..............................................................................325 13.7. Еквівалентність автоматів.........................................................................326 13.8.. Мінімізація автоматів...............................................................................328 13.9. Канонічний метод структурного синтезу автоматів...............................332 13.10. Графічний метод структурного синтезу автоматів...............................335 Контрольні запитання.........................................................................................338 Задачі для самостійного розв'язування.............................................................339 Коментарі ..........................................................................................................341 Література............................................................................................................342