В.В. Слєсарєв

Основи дискретної математики

Затверджено до видавництва науково-методичною радою

Академії як навчальний посібник для студентів

напрямку підготовки "Комп'ютерні науки" спеціальності 7.080401

та 7.080403 і напрямку підготовки "Прикладна математика"

спеціальності 7.080203

(протокол № 7 від 17.07.2001 р.)

Дніпропетровськ

НГА України

2001

УДК

ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ: Навч. посібник / В.В.Слєсарєв. -

Дніпропетровськ: Національна гірнича академія України, 2001.- 98 с.

Викладено основні розділи дискретної математики, пов'язані с теорією множин, теорією графів, кінцевими автоматами, алгеброю логіки, комбінаторикою та формальними системами. Наведено варіанти задач для закріплення знань.

Рецензенти: В.В.Ткачов, д-р техн. наук, кафедра автоматизації виробничих

процесів НГА України

Л.С. Коряшкіна, канд.фіз-мат. наук, кафедра Національного технічного університету "КПІ" України

 Національна гірнича академія України, 2001

 В.В.Слєсарєв, 2001

ЗМІСТ

Вступ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Розділ 1. Основи теорії множин . . . . . . . . . . . . . . . . . . . . . . . 6

1.1. Основні визначення . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2. Операції з множинами . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3. Розбивка множин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4. Декартов добуток множин . . . . . . . . . . . . . . . . . . . . . . . . .12

1.5. Відношення . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.6. Властивості відношень . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.7. Відповідність, відображення і функції . . . . . . . . . . . . . . 17

Задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Розділ 2. Основи теорії графів . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.1. Основні положення . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.. Неорієнтовані графи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3. Ізоморфізм графів. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4. Відношення порядку і відношення еквівалентності

на графі. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.5. Характеристики графів. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.6. Эйлерові графи і гамільтонові цикли . . . . . . . . . . . . . . . . 31

2.7. Розрахунок мережного графіка . . . . . . . . . . . . . . . . . . . . . . 32

2.8. Оптимізація на мережах . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

Розділ 3. Основи теорії кінцевих автоматів . . . . . . . . . . . . . . . . 44

3.1. Логічні функції . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.2. Приклади логічних функцій . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.3. Зв'язок логічних функцій і функціональних схем . . . . . . . 46

3.4 Канонічне представлення логічних функцій . . . . . . . . . . . . 48

3.5. Задача мінімізації логічних функцій . . . . . . . . . . . . . . . . . . 50

3.6. Основні поняття теорії кінцевих автоматів . . . . . . . . . . . . . 53

3.7. Абстрактна і структурна теорія кінцевих автоматів . . . . . . 55

3.8. Співставлення кінцевих автоматів. . . . . . . . . . . . . . . . . . . . . 58

3.9. Синхронні мережі з автоматів. . . . . . . . . . . . . . . . . . . . . . . . .59

3.10. Приклад синтезу кінцевого автомата . . . . . . . . . . . . . . . . . 61

3.11. Програмна реалізація логічних функцій і автоматів. . . . . . 66

Задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Розділ 4. Математична логіка і формальні системи. . . . . . . . . 70

4.1. Вступ у формальні системи . . . . . . . . . . . . . . . . . . . . . . . . . . 70