Міністерство освіти і науки,
МОЛОДІ ТА СПОРТУ УКРАЇНИ
ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ
УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ
КОНСПЕКТ ЛЕКЦІЙ
з дисципліни
«ДИСКРЕТНА МАТЕМАТИКА»
Харків 2012
МІНІСТЕРСТВО ОСВІТИ І НАУКИ,
МОЛОДІ ТА СПОРТУ УКРАЇНИ
ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ
УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ
КОНСПЕКТ ЛЕКЦІЙ
з дисципліни «ДИСКРЕТНА МАТЕМАТИКА»
для студентів денної форми навчання напряму
“Комп’ютерна інженерія”
ЗАТВЕРДЖЕНО
кафедрою АПОТ.
Протокол № 4 від 24.11.2011
Харків 2012
Конспект лекцій з дисципліни “Дискретна математика” для студентів денної форми навчання напряму “Комп’ютерна інженерія” / Упоряд.: В.І. Хаханов, С.В. Чумаченко – Харків: ХНУРЕ, 2012. – 96 с.
Упорядники: в.І. Хаханов,
С.В. Чумаченко
Рецензент: є.І. Литвинова, д-р техн. Наук, проф. Каф. Апот хнуре
ЗМІСТ
Вступ 5
1 Основні поняття теорії множин 6
1.1 Відношення приналежності й включення 6
1.2 Способи завдання множин 7
1.3 Алгебра множин Кантора 8
1.4 Закони й тотожності алгебри множин 9
1.5 Контрольні запитання 10
2 Відповідності. Функції. Відображення 11
2.1 Поняття впорядкованої пари й вектора 11
2.2 Декартів (прямий) добуток множин 12
2.3 Відповідності 13
2.4 Функції. Відображення 16
2.5 Контрольні запитання 17
3 Відношення. Алгебра відношень 18
3.1 Поняття відношення 18
3.2 Операції над відношеннями 18
3.3 Алгебра відношень 20
3.4 Контрольні запитання 22
4 Бінарні відношення 23
4.1 Способи завдання бінарних відношень 23
4.2 Властивості бінарних відношень 25
4.3 Бінарне відношення еквівалентності 27
4.4 Контрольні запитання 31
5 Бінарне відношення порядку 31
5.1 Упорядковані множини й бінарне відношення порядку 31
5.2 Типи порядку (лінійний, частковий, передпорядок) 31
5.3 Контрольні запитання 35
6 Структури. Алгебраїчні системи. Ізоморфізм 36
6.1 Структура 36
6.2 Дедекиндові (модулярні) структури 38
6.3 Дистрибутивні структури 39
6.4 Ізоморфізм множин 39
6.5 Контрольні запитання 40
7 Висновки до розділу «Теорія множин» 41
8 Позначення до розділу «Теорія множин» 41
9 Основні поняття булевої алгебри 43
9.1 Логічні операції й логічні функції 43
9.2 Закони й тотожності булевої алгебри 47
9.3 Доведення законів булевої алгебри 47
9.4 Контрольні запитання 48
10 Диз’юнктивні й кон’юнктивні нормальні форми (ДНФ і КНФ).
Досконалі ДНФ і КНФ (ДДНФ і ДКНФ) 49
10.1 ДНФ і КНФ 49
10.2 ДДНФ і ДКНФ 50
10.3 Складність зображення булевих функцій 52
10.4 Теорема Шенона про розкладання булевих функцій 53
10.5 Контрольні запитання 53
11 Елементи логічних схем. Булеві функції від двох змінних 54
11.1 Фізичний зміст логічних функцій І, АБО, НІ та їх схемотехнічне
зображення 54
11.2 Таблиця аналітичного й схемотехнічного зображення булевих
функцій від двох змінних 57
11.3 Властивості й аналітичні зображення елементарних булевих
функцій від двох змінних 59
11.4 Приклади розв’язання практичних завдань 60
11.5 Контрольні запитання й завдання 61
12 Способи зображення булевих функцій 62
12.1 Табличний спосіб зображення булевих функцій 62
12.2 Числовий спосіб зображення булевих функцій 62
12.3 Аналітична форма запису булевих функцій 63
12.4 Геометрична інтерпретація булевих функцій 63
12.5 Кубічна форма зображення булевих функцій 65
12.6 Схемотехничне зображення 66
12.7 Контрольні запитання й завдання 66
13 Системи функцій алгебри логіки. Функціональна повнота 67
13.1 Класи булевих функцій 67
13.2 Повнота функцій алгебри логіки 72
13.3 Контрольні запитання 73
14 Булеві похідні 73
14.1 Булеві похідні першого порядку 74
14.2 Фізичний зміст булевої похідної першого порядку 75
14.3 Змішана похідна k-го порядку 75
14.4 Булеві похідні k-го порядку 77
14.5 Контрольні запитання 78
15 Мінімізація булевих функцій. Методи Квайна й Квайна-Мак-Класки 78
15.1 Основні положення методу Квайна 79
15.2 Мінімізація булевих функцій за методом Квайна-Мак-Класки 79
15.3 Контрольні запитання 83
16 Мінімізація булевих функцій: метод невизначених коефіцієнтів 83
16.1 Основні припущення 83
16.2 Алгоритм знаходження невизначених коефіцієнтів 85
16.3 Контрольні запитання 86
17 Мінімізація булевих функцій: метод карт Карно 87
17.1 Основні положення 87
17.2 Спрощений стандарт карт Карно 89
17.3 Мінімізація за картами Карно 90
17.4. Контрольні запитання 91
18 Висновки до розділу «Булева алгебра» 92
19 Позначення до розділу «Булева алгебра» 92
Перелік посилань 95
ВСТУП
Конспект лекцій з дисципліни «Дискретна математика» розроблено на підставі робочої програми відповідно до освітньо-професійної підготовки фахівців освітньо-кваліфікаційного рівня бакалавр за напрямом “Комп’ютерна інженерія”.
Мета навчальної дисципліни – формування у студентів базових знань в області дискретної математики, необхідних для освоєння методів аналізу й синтезу апаратних і програмних засобів цифрових обчислювальних систем і мереж різного призначення.
У результаті вивчення дисципліни студенти повинні:
знати математичний апарат дискретної математики – множини і відношення, операції над ними, формальні правила подання, мінімізації і реалізації логічних функцій, основні формули теорії множин та булевої алгебри у частині іхнього застосування;
уміти формулювати і вирішувати практичні задачі синтезу й аналізу цифрових дискретних об’єктів на основі вибору найбільш раціонального математичного апарата дискретної математики з метою її оптимального рішення.