Міністерство освіти і науки, молоді та спорту України

Запорізький електротехнічний коледж

Запорізького національного технічного університету

ЗАТВЕРДЖЕНО

Протокол засідання ПЦК “Розробка програмного забезпечення”

від ___________________ № _____

Голова ПЦК _________ Н.В. Бабенко

ДИСКРЕТНА МАТЕМАТИКА

Збірник методичних вказівок

до практичних робіт для спеціальності

«Розробка програмного забезпечення»

Викладач Н.В. Бабенко

2011

Передмова

Методичні вказівки для виконання практичних робіт з предмета “Дискретна математика“ містять указівки до виконання практичних робіт №№ 1-15.

Структура методичних указівок наступна:

1. Тема роботи

2. Мета роботи

3. Завдання до роботи

4. Опис виконання завдання

Звіт з виконання практичної роботи виконується на аркушах формату А4 і повинен містити наступні пункти:

1. Тема роботи

2. Мета роботи

3. Завдання до роботи

4. Результати виконання роботи

5. Висновок

Зміст

Практична робота 1 Елементи теорії множин	4
Практична робота 2 Еквівалентні перетворення формул	10
Практична робота 3 Побудова ДНФ, КНФ	15
Практична робота 4 Побудова ДДНФ, ДКНФ	18
Практична робота 5 Елементи комбінаторного аналізу	21
Практична робота 6 Основні поняття алгебри висловлювань Пропозиціональні зв’язки та форми	26
Практична робота 7 Таблиці істинності для складних висловлювань	27
Практична робота 8 Формули предикатів. Формалізація запису стверджень за допомогою кванторів. Логічна еквівалентність формул.	29
Практична робота 9 Звичайні графи. Основні поняття і визначення	30
Практична робота 10 Пошук найкоротшого шляху	32
Практична робота 11 Знаходження основних чисел графа	34
Практична робота 12 Побудова остова дерева графа	36
Практична робота 13 Знаходження символу дерева та відновлення дерева по символу	37
Практична робота 14 Побудова остова дерева мінімальної ваги за алгоритмами Краскала та Пріма	38
Практична робота 15 Побудова дерева та коду Хаффмана	40

Практична робота №1

1 Тема

Елементи теорії множин.

2 Мета

Закріпити основні поняття теорії множин.

3 Порядок виконання роботи

3.1 Виконати завдання відповідно варіанту:

Завдання 1

Визначити чи виконується рівність аналітично та графічно.

Завдання 2

Дані множини А, В, С, D:

1. Зобразити на діаграмі Ейлера-В’єнна дану множину ;

2. Описати множину (див. малюнок) за допомогою дій над множинами.

Завдання 3

Нехай R – множина дійсних, а Z – множина цілих чисел. Які геометричні фігури зображують відношення ?

Завдання 4

Визначити, яке з відношень є функціональним на множині R. У випадку, якщо співвідношення не є функціональним, на R, то вказати (якщо можливо) множину, на якій воно є функціональним.

4. Відповіді до приведених завдань

5 Висновок

Зразок виконання нульового варіанту

Завдання 1

Графічне рішення:

=

Відповідь: Рівність виконується

Завдання 2

1. 

2. 

Завдання 3

а)

б)

Завдання 4

Це відношення функціональне, тому що одному із Pr₁ відповідає єдине значення із Pr₂.