Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Навчальний посібник
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
«ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Я.П. Романчук
ДИСКРЕТНА МАТЕМАТИКА
Конспект лекцій
Розглянутий на засіданні кафедри АСУ
як навчальний посібник для студентів
базового напрямку 050101 «Комп’ютерні науки»
денної та заочної форм навчання (протокол № 1-10/11 від 31 серпня 2010 р.)
Львів − 2010
УДК 519.1+519.6
Я.П. Романчук. Дискретна математика: Конспект лекцій для студентів напряму комп’ютерні науки спеціальності Інформаційні управляючі системи та технології. – Львів: НУЛП, 2010. – 210 с.
У конспекті викладено теорію множин і відношень; алгебру логіки і алгебру логіки висловлень і предикатів, теорію графів, моделі алгоритмів і програм, формальні граматики й мови, основи теорії кодування та шифрування.
Кожен розділ складається з основних визначень, властивостей, операцій і теорем; має значну кількість розв’язаних і ілюстрованих прикладів з об’єктами дискретної природи; містить вправи для аудиторної та самостійної роботи студентів.
Конспект лекцій може бути корисним для студентів інших спеціальностей, які бажають вивчати методи дискретної математики для використання їх у природничих і гуманітарних науках із залученням інформаційних технологій.
Рецензент:
І.М. Дронюк, кандидат фізико-математичних наук, доцент кафедри АСУ.
Відповідальна за випуск:
З.Я. Шпак, кандидат технічних наук, доцент кафедри АСУ.
Лекція 5
7. КОМБІНАТОРИКА
У цьому розділі розв’язуються деякі задачі, пов’язані з розглядом різних комбінацій з елементів кінцевих множин М. Наприклад, якщо взяти 10 різних цифр 0, 1, 2, ... , 9 і утворювати з них комбінації, то будемо одержувати різні числа, наприклад 345, 534, 1036, 5472, 45, 54 і т.п.
Видно, що деякі з таких комбінацій відрізняються тільки порядком цифр (наприклад 345 і 534), інші − вхідними в них цифрами (наприклад 1036 і 5472), треті − розрізняються і порядком і числом цифр (наприклад 345 і 54).
Отримані комбінації задовольняють різним умовам. Залежно від правил їх утворення можна виділити три типи комбінацій: перестановки, розміщення, сполучення. Розглянемо їх окремо.
7.1. Перестановки.
Означення 7.1. Комбінації з n елементів, які відрізняються одна від іншої тільки порядком елементів, називаються перестановками.
Перестановки позначаються символом Рn, де n — число елементів, які входять у кожну перестановку.
Приклад 7.1. Нехай множина М містить три букви А, В, С. Складемо всі можливі комбінації із цих букв: АВС, АСВ, ВСА, CAB, CBA, ВАС (усього 6 комбінацій). Видно, що вони відрізняються одна від іншої тільки порядком розташування букв.
Дійсно, на перше місце в комбінації (перестановці) можна поставити три букви. На друге місце вже можна поставити тільки дві букви із трьох (одна посіла перше місце), а на третьому виявиться тільки одна (та, що залишилася). Виходить, 3 · 2 · 1 = 6 = P3 , але 1 · 2 · 3 = 3! Прийшли до відомого у математиці поняття факторіалу.
Означення 7.2. Добуток всіх натуральних чисел від 1 до n включно називають n-факторіалом і пишуть: n!= 1 · 2 · 3 · ... · (n - 1) · n. Вважають, що 0! = 1 і . Основна властивість факторіалу: (n + 1)! = (n +1) · n!.
Отже, число перестановок обчислюємо за формулою: Рn = n! (7.1)
7.2. Розміщення.
Означення 7.3. Комбінації з n елементів по m елементів, які відрізняються одна від другої або самими елементами або порядком елементів, називаються розміщеннями.
Розміщення позначаються символом , де n − число всіх наявних елементів, m − число елементів у кожній комбінації. Число розміщень можна обчислити за формулою:
, де 0 ≤ m ≤ n; m, nN. (7.2)
Вважають, що .
Приклад 7.2. Нехай множина M містить чотири букви А, В, С, D. Склавши всі комбінації тільки із двох букв, одержимо: АВ, AC, AD, ВА, ВР, BD, СА, СВ, CD, DA, DB, DC.
Видно, що всі отримані комбінації (їх 12) відрізняються або буквами, або їхнім порядком (комбінації ВА і АВ вважаються різними).
За формулою (7.2) , що збігається з результатом наведеного прикладу. Тут кожен рядок відповідає однієї із всіх наявних букв (n=4), а число стовпців відповідає іншим буквам (n-1=3) , усього 4∙3=12 різних комбінацій.
Формулу (7.2) можна записати у факторіальній формі:
. (7.3)
Основні властивості розміщень: 1) ; 2) .
7.3. Сполучення.
Означення 7.4. Сполученнями називаються всі можливі комбінації з n елементів по m, які відрізняються одна від другої принаймні хоча б одним елементом ( m, nN і n m).
У загальному випадку число сполучень із n елементів по m дорівнює числу розміщень із n елементів по m, поділеному на число перестановок із m елементів: . Використовуючи для чисел розміщень і перестановок факторіальні формули і , одержимо формулу для числа сполучень у вигляді: . (7.4)
Основні властивості сполучень: ; .
Приклад 7.3. Множина М утворена з чотирьох букв А, В, С, D. Скласти комбінації з двох букв, що відрізняються одна від другої хоча б одним елементом.
Маємо АВ, AC, AD, ВР, BD, CD. Виходить, що число сполучень з чотирьох елементів по двоє дорівнює 6. Це коротко записується так: .
7.4. Розміщення з повтореннями.
Розміщення з n елементів по k зображують упорядковані комбінації різних елементів множини М, |М|= n. Часто доводиться робити упорядковані комбінації з повтореннями деяких елементів. Наприклад, з множини М = {A, Б} можна зробити вісім комбінацій з трьох елементів: ААА, ААБ, АБА, БАА, БАБ, ББА, АББ, БББ. Тут n = 2, k = 3. Такі упорядковані k-комбінації називають кортежами довжини k. Два кортежі (тобто дві загальні комбінації) вважаються однаковими, якщо вони мають однакову довжину і на місцях з однаковими номерами стоять однакові елементи.
Означення 7.5. Розміщенням із повтореннями з n елементів по k називається кортеж довжини k з n елементів.
Кількість кортежів обчислюється за формулою: . (7.5)
Розглянутий вище приклад обчислюється за формулою (7.5) .
Дійсно, після заповнення першого місця кортежу довжиною k одним із n елементів (що можливо зробити n варіантами) заповнити друге місце кортежу можна знову будь-яким елементом із усієї множини (повторюючи в одному з варіантів елемент, який знаходиться на першому місці), і так далі k разів. За правилом добутку одержимо, що .
Вправи
1. Спростити: а) ; б) .
2. Обчислити: а) 7! – 5!; б) .
3. Скільки різних варіантів хокейної команди можна скласти з 9 нападаючих, 5 захисників і 3 воротарів, якщо до складу команди повинно ввійти 3 нападаючих, 2 захисника і воротар?
4. Із 10 студентів призначають двох чергових. Скількома способами можна це зробити, якщо:
1) один із призначених стає старшим;
2) старших немає?
5. Побудувати різні перестановки по 2 і по 3 елементи множини М = {1,2,3}.
6. У футбольному чемпіонаті беруть участь 15 команд вищої ліги. За умовою, що 2 останні команди її залишають, скільки варіантів завершення чемпіонату?
7. Скільки кортежів довжини 4 можна одержати з елементів множини
М = {1, 2, 3, 4}.
СПИСОК ЛІТЕРАТУРИ
Акимов О.Е. Дискретная математика. Логика, группы, графы. - М.: Лаборатория Базовых Знаний, 2003. – 376 с.
Андерсон Д. А. Дискретная математика и комбинаторика. – М. – С.- Пб. – К.: Издательский дом «Вильямс», 2003.– 958 с.
Бондаренко М.Ф., Білоус Н.В., Руткас А.Г. Комп’ютерна дискретна математика. – Харків: «Компанія СМІТ», 2004. – 480 с.
Донской В.И. Дискретная математика. - Симферополь: Сонат, 2000– 360с.
Капітонова Ю.В., Кривий С.Л., Летичевський О.А. Основи дискретної математики. – К.:Наукова думка, 2002. – 578 с.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергия, 1980. – 344 с.
Коваленко Л.Б., Станішевський С.О. Дискретна математика: Навч. посіб. для студентів економічних, менеджерських та електротехнічних спеціальностей вищих навчальних закл. – Харків: ХНАМГ, 2006. – 192 с.
Тевяшев А.В., Гусарова И.Г. Основы дискретной математики в примерах и задачах. - Харьков: ХНУРЭ, 2003. – 272 с.
Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979. –384 с.
Уилсон Р. Введение в теорию графов. – М.: Мир, 1977. – 205 с.
Сенчуков В.Ф. Основи дискретної математики [Текст] : навч. посіб. / В.Ф. Сенчуков, Т. В. Денисова. – Х. : ІНЖЕК, 2009. – 320 с.
Нікольський Ю.В. Дискретна математика [Текст] : підручник / Ю.ºВ.ºНікольський, В. В. Пасічник, Ю. М. Щербина. – Львів: Магнолія 2006, 2009. – 432 с.
Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб: Изд-во «Лань», 1999. – 288 с.
ЗМІСТ
ВСТУП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .
3
1. ТЕОРІЯ МНОЖИН . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.1. Поняття множини . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2. Операції над множинами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.3. Діаграми Венна . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2. ВІДНОШЕННЯ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.1. Основні Означення . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.2. Властивості бінарних відношень. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.3. Операції над бінарними відношеннями. . . . . . . . . . . . . . . . . . . . . . . . .
33
2.4. Правила побудови матриць відношень. . . . . . . . . . . . . . . . . . . . . . . . . .
39
2.5. Функції. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
3. ЛОГІКА ВИСЛОВЛЕНЬ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
3.1. Основні Означення. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
3.2. Істинностна функція. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
3.3. Еквівалентні висловлення. Тавтології. . . . . . . . . . . . . . . . . . . . . . . . . . .
64
3.4. Основні схеми побудови логічно правильних міркувань.
Логічний наслідок. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
4. АЛГЕБРА ЛОГІКИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
4.1. Логічні функції. Основні Означення. . . . . . . . . . . . . . . . . . . . . . . . . . .
80
4.2. Булева алгебра. Зроблені нормальні форми . . . . . . . . . . . . . . . . . . . . .
86
4.3. Еквівалентні перетворення. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
4.4. Двоїстість булевих функцій. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
4.5. Функціонально повні системи. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
4.6. Похідна від булевої функції. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
101
4.7. Комутаційні схеми. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
104
5. ЛОГІКА ПРЕДИКАТІВ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
111
5.1. Основні Означення. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
111
5.2. Квантори. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
114
5.3. Операції над предикатами і кванторами
Еквівалентні співвідношення. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .
118
5.4. Логічна інтерпретація формул логіки предикатів. . . . . . .. . . . . . . . . . .
123
5.5. Префіксна нормальна форма. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
129
6. ГРАФИ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
133
6.1. Основні Означення. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
133
6.2. Способи завдання графів. . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
141
6.3. Зв’язність графа. Маршрути, шляхи, ланцюги, цикли. . .. . . . . . . . . . .
150
6.4. Метрика на графах. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
157
6.5. Ейлерів цикл. Ейлерів граф. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . .
161
6.6. Шляхи і цикли Гамільтона. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
166
6.7. Планарні графи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
170
6.8. Дерева і ліс. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
174
7. КОМБІНАТОРИКА. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
181
7.1. Перестановки. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
181
7.2. Розміщення. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
182
7.3. Сполучення. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
182
7.4. Розміщення з повтореннями. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
183
ЛІТЕРАТУРА. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
185
ПРЕДМЕТНИЙ ПОКАЖЧИК. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
186
ПРЕДМЕТНИЙ ПОКАЖЧИК
А
Алгебра логіки 80-111
− множин 7
Антирефлексивне відношення 25
Антисиметричне відношення 25
Антитранзитивне відношення 26
Асиметричне відношення 25
Асоціативність 11
Б
Бінарні відношення 14
− операції 8
Булеан 6
Булева алгебра 86
В
Відношення 14
− бінарне 15
− еквівалентне 26
− симетричне 25
− рефлексивне 25
− транзитивне 26
Висловлення 52, 56
− просте 52
− складне 52
− еквівалентне 64
Властивості тотожності 11
− доповнення 11
Г
Граф 133-180
− вершини 133
− степінь 135
− грань 170
− діаметр 158
− доповнення 135
− каркас (скелет) 137
− радіус 158
− ребра 133
− переріз (розріз) 152
− суміжні вершини 133
− ребра 133
− точка зчленування 152
− центр 157
− ейлерів 161
− гамільтонів 166
− дуги 134
− скінченний 134
− неорієнтований 134
− орієнтований 134
− плоский 170
− повний 135
− порожній 134
− зв’язний 151
− ланцюг 150
Д
Двоїстість 93-95
Декартів добуток 14
Дерево 174
− висота 177
− корінь 176
− листя 176
− нащадок вершини 178
− ребра 175
− рівень вершини 177
− кореневе 177
− неорієнтоване 174
− орієнтоване 175
Діаграми Венна 10
Диз’юнктивна нормальна форма
(ДНФ) 91
Диз’юнкція 55
Додавання за модулем два 53
Доповнення множини 8, 34
Е
Еквіваленції 66
Елементарна диз’юнкція 92
− кон’юнкція 91
Еквівалентні перетворення 90-93
Елементи множини 4
З
Задання булевої функції 87
− − − таблицею істинності 55
Задання множин 4-5
− − визначено властивістю 4
− − переліченням елементів 4
− − рекурсивне 4
Задача комівояжера 169
Закони алгебри множин 10, 11
− логіки Буля 84
Змінна фіктивна 81
Значення істинності висловлення 52
Досконала диз’юктивна нормальна форма (ДДНФ) 87
− кон’юктивна − − (ДКНФ) 88
І
Ідемпотентність 10
Ізоморфізм графів 138
Імплікація 66
Інверсія 82
Інцидентність ребер і вершин
графа 133
Істиннісне значення висловлення 52
К
Квантор загальності 114
− існування 144
Комбінаторика 181
Композиція відношень 34
Комутаційні схеми 104-108
Кон’юктивна нормальна
форма (КНФ) 92
Кон’юнкція 55
Кортеж 183
Л
Ланцюг простий 150
Ліс 175
Логіка висловлень 52-79
− предикатів 111-132
Логічний наслідок 69
М
Маршрут 150
− довжина 150
− замкнений (циклічний) 151
− неорієнтований 151
− орієнтований 153
Матриця інцидентності 141
− бінарних відношень 16
− відстаней 159
− суміжності 142
Множина 4-13
− зчисленна (скінченна) 5
− континуальна (нескінченна) 5
− порожня 5
Н
Набір булевий 80
Нескоротна система
булевих функцій 82
О
Область значень відношення 14
− Означення відношення 15
Обернена імплікація 66
Обернене відношення 34
(ПНФ) 129
Принцип двоїстості 93
Псевдограф 134
Р
Різниця множин 8
Розміщення 182
Рефлексивне замикання 36
С
Символічна логіка 52-53
Символ предметних змінних 111
− індивідуальний 111
− предикатний 111
− функціональний 111
Симетрична різниця 8
Список бінарних відношень 16
Сполучення 183
Стрілка Пірса 82
Суперпозиція булевої функції 83
Т
Таблиця істинності 55
Тавтології 65
Теорема Ейлера 162
− Куратовського 173
− про диз’юнктивне, кон’юнктивне розкладання булевої функції 87
− Черча 124
Тотожне відношення 26
Обчислення висловлень 70-73
− предикатів 118
Об’єднання множин 7, 33
Операції над бінарними
відношеннями 33-39
Орграф 134
П
Парадокс логічний 58
Перестановки 181
Перетинання множин 8, 33
Петля 134
Підграф 137
Підмножина 5
Правила побудови матриць
відношень 39-42
Порядок предиката 111
Правило введення квантора
загальності 114
− − − існування 114
− перейменування вільних змінних 118
− − зв’язаних змінних 118
Похідна від булевої функції 101-103
Правила висновку 70-73
Правильне міркування 69
Предикат 111
Предметна область 111
Предметні константи 113
− змінні 111
Префіксна нормальна форма
Тотожно істинна формула
(тавтологія) 123
− хибна формула (суперечлива, нездійсненна) 124
Транзитивне змикання 35
У
Унарні операції 8
Упорядкована пара 14
Ф
Функціонально повні системи 96-100
Функція 46-51
− ін’єктивна 47
− взаємооднозначна 47
− двоїста 93
− істинностна 62
− логічна 80
− обернена 48
− самодвоїста 94
− що зберігає 0 80
− що зберігає 1 80
Ц
Цикл гамільтонів 166
− простий 154
− ейлерів 161
Ш
Шлях гамільтонів 166
− простий 150
Штрих Шиффера 82
19.02.2013 18:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора