НГА України Кафедра СА і У Основи дискретної математика Навчальний посібник 27

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

Кафедра системного аналізу і управління

СЛЄСАРЄВ В.В.

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

НАВЧАЛЬНИЙ ПОСІБНИК

для студентів спеціальностей

7.080401, 7.080403 і 7.080203

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

2001

ЗМІСТ

Стор.

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

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

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

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

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

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

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

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

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

Задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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