Навчальний посібник призначений для студентів, які вивчають дисципліну «Математична логіка та дискретна математика».
Посібник складається з трьох частин: теорія множин і відношень, елементи математичної логіки та теорія графів. Весь матеріал супроводжується великою кількістю прикладів. Наприкінці кожної частини наведено задачі для самостійного опрацювання.
Навчальний посібник орієнтований на студентів технічних спеціальностей закладів вищої освіти, а саме для тих, хто навчається за спеціальністю 172 «Електронні комунікації та радіотехніка» галузі знань – 17 «Електроніка та телекомунікації».
ЗМІСТ
ВСТУП 6
Частина 1. Теорія множин і відношень 8
1.1. Теорія множин 8
1.1.1. Поняття множини 8
1.1.2. Способи задання множин 9
1.1.3. Відношення між множинами 10
1.1.4. Основні операції над множинами 11
1.2. Відношення 18
1.2.1. Декартовий добуток множин 18
1.2.2. Поняття відношення. Способи задання відношень 20
1.2.3. Способи задання відношень 20
1.2.4. Основні поняття теорії відношень: області визначення, образи, прообрази, обернені та композиційні відношення 22
1.2.5. Властивості бінарних відношень 24
1.2.6. Спеціальні бінарні відношення 27
1.2.7. Відношення порядку 31
1.3. Функції та відображення 33
1.3.1. Основні поняття функції та відображення 33
1.3.2. Класифікація функцій 37
1.3.3. Потужність множин і зліченність 38
1.4. Завдання до частини 1 39
Частина 2. Елементи математичної логіки 47
2.1. Висловлювання 47
2.2. Булеві функції. Основні поняття та означення 53
2.2.1. Способи задання булевих функцій 54
2.2.2. Поняття фіктивної та істотної змінної 55
2.2.3. Булеві функції аргументів 57
2.2.4. Реалізація булевих функцій формулами 60
2.2.5. Принцип двоїстості 66
2.3. Диз’юнктивна та кон'юнктивна нормальні форми 67
2.3.1. Повні системи булевих функцій 67
2.3.2. Означення диз’юнктивної нормальної форми 68
2.3.3. Алгоритм побудови ДНФ 68
2.3.4. Означення кон'юнктивної нормальної форми 69
2.3.5. Алгоритм побудови КНФ. 69
2.3.6. Досконалі диз’юнктивна та кон'юнктивна нормальні форми 70
2.4. Зображення булевої функції поліном Жегалкіна 73
2.5. Мінімізація булевих функцій за допомогою карт Карно (діаграма Вейча) 77
2.6. Завдання до частини 2 81
Частина 3. Теорія графів 88
3.1. Основні поняття теорії графів 88
3.2. Операції над графами 93
3.3. Матричні способи задання графа 94
3.3.1. Задання графа матрицею суміжності 94
3.3.2. Задання графа матрицею інцидентності 96
3.4. Ізоморфізм графів 97
3.5. Маршрути в графі 98
3.6. Зв'язність графа 100
3.7. Приклади з історії теорії графів 103
3.8. Обходи в графах. Ейлерові графи 105
3.9. Зважені графи 106
3.10. Дерева 107
3.11. Мінімальні шляхи в зважених орграфах 108
3.12. Мінімальні остовні дерева зважених графів 114
3.13. Завдання до частини 3 117
ВСТУП
Дискретна математика – це важлива галузь математики, яка вивчає дискретні об'єкти, тобто такі, що мають скінченну або зліченну множину елементів. Ця дисципліна є основою для розуміння багатьох аспектів сучасних інформаційних технологій, комп'ютерних наук, а також таких напрямів, як мережеві технології, телекомунікації та штучний інтелект. Саме тому її вивчення є обов’язковим для студентів технічних спеціальностей, які бажають оволодіти методами аналізу та моделювання систем, що працюють з дискретними даними.
Навчальний посібник "Дискретна математика" розроблений для студентів, які вивчають дисципліну "Математична логіка та дискретна математика". Він охоплює основні теми, необхідні для глибокого розуміння цієї галузі. Матеріал посібника структуровано на три основні частини: теорія множин та відношень, математична логіка і теорія графів. Кожна з цих частин забезпечує поступове ознайомлення з фундаментальними поняттями та методами, які є ключовими для подальшого вивчення комп’ютерних наук.
Перша частина посібника присвячена теорії множин і відношень. Вона є базовою для розуміння багатьох інших розділів математики і комп'ютерних наук. Тут розглядаються основні операції над множинами, відношення між ними, а також функції та їх властивості. Цей розділ також містить практичні завдання для закріплення матеріалу, що допомагає студентам краще зрозуміти його застосування на практиці.
Друга частина зосереджена на елементах математичної логіки. Висловлювання, булеві функції, різні нормальні форми, а також методи мінімізації логічних виразів є необхідними для розуміння принципів роботи комп’ютерів, зокрема схем булевої алгебри. Цей розділ також містить приклади та завдання, що допомагають студентам опанувати техніки аналізу логічних схем та роботи з висловлюваннями.
Третя частина присвячена теорії графів – одному з найпопулярніших і найпотужніших математичних інструментів для моделювання реальних систем. Теорія графів широко використовується в комп'ютерних науках, зокрема для побудови мереж, аналізу маршрутів і алгоритмів пошуку оптимальних шляхів. У посібнику розглядаються основні поняття графів, такі як зв'язність, ізоморфізм, а також спеціальні види графів, такі як дерева та орграфи.
Окрім теоретичного матеріалу, кожен розділ посібника містить велику кількість завдань для самостійної роботи, що сприяє формуванню у студентів практичних навичок розв'язання задач з дискретної математики. Це допомагає не лише закріпити вивчений матеріал, але й розвинути аналітичне мислення, яке є необхідним для майбутніх фахівців у галузі інформаційних технологій.
Цей навчальний посібник покликаний сформувати у студентів цілісне уявлення про дискретну математику як науку, яка лежить в основі багатьох сучасних технологій. Знання, отримані в процесі вивчення цього курсу, стануть важливою частиною підготовки спеціалістів, що працюють з мережами, базами даних, алгоритмами штучного інтелекту та іншими технологіями, які базуються на дискретних структурах.
Дискретна математика. Навчальний посібник / Н.Б. Дахнo , Ю.В. Кравченкo, O.O. Лещенкo, А.С. Дуднік – К. : КНУ імені Тараса Шевченка/ 2025 р.
- Виробник: Каравела
- Модель: навчальний посібник
- Наявність: Є в наявності
-
350 грн.
Дискретна математика. Навчальний посібник / Н.Б. Дахнo, Ю.В. Кравченкo, O.O. Лещенкo, А.С. Дуднік – К. : КНУ імені Тараса Шевченка/