МІНІСТЕРСТВО ОСВIТИ УКРАЇНИ
ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНIЧНИЙ УНIВЕРСИТЕТ
КАФЕДРА «КОМП’ЮТЕРНОЇ ІНЖЕНЕРІЇ»
Методичні вказівки до виконання лабораторних робіт
з дисципліни
"ДИСКРЕТНА МАТЕМАТИКА"
для студентів спеціальностей
7.091501: "Комп'ютерні системи та мережі"
7.091502: ”Системне програмування”
Затверджено
на засіданні кафедри КІ
Протокол № 1 від
30.08.2010
Рекомендовано до видання
методичною комісією
спеціальностей 7.091501 і 7.091502
Протокол № від
Донецьк
УДК 518.551071
Методичні вказівки до виконання лабораторних робіт за курсом “Основи дискретної математики“, частина I ((для студентів очної, заочної та очно – заочної форми навчання). Уклали: А.Ю. Іванов, О.Ю. Чередникова. – Донецьк: ДонНТУ, 2010 - 56 с.
В курсі дискретної математики студенти повинні опанувати значний обсяг математичних фактів та способів їх застосування.
Основні знання, що їх повинні набути студенти, стосуються таких розділів: основи математичної логіки, комбінаторний аналіз, теорія графів, основи теорії кодування. З кожного розділу розглядаються можливі застосування, в основному до проблем прикладної математики та інформатики. В усіх розділах приділяється значна увага побудові алгоритмів для розв'язування задач дискретної математики. Поняття, факти, алгоритми, що вивчаються у курсі "Дискретна математика" використовуються у курсах "ЕОМ та програмування", "Теорія ймовірностей", "Методи оптимізації", "Дослідження операцій", а також у багатьох спеціальних курсах.
Укладачі: А.Ю. Іванов, ст. викл., О.Ю. Чередникова, ас.
Рецензенти: В.О. Краснокутський., к.т.н., доц
Ю.В. Ладиженський., к.т.н., доц.
Лабораторна робота №1
Тема роботи:Множина.
Мета роботи: Вивчення способів завдання множин. Набуття практичних навичок у виконанні операцій над множинами та перевірці основних співвідношень алгебри множин.
Теоретичні відомості
Множина – це сукупність об'єктів, що розглядається як одне ціле. Поняття множини береться за основне, тобто не зводиться до інших понять. Об'єкти, складові множини, називаються його елементами. Основне відношення між елементом а і множиною A, що містить його, позначається так: а є елемент множини A; або а належить A, або A містить а. Якщо а не є елементом множини A, то пишуть: а не входить в A, A не містить а.
Способи задання множини:
а)
Перерахуванням її елементів:
б) Характеристичним предикатом. Наприклад:
-
до множини
входять тільки ті
,
що мають властивість
.
в) Породжуючою процедурою:
Для представлення у ЕОМ кінцевої множини S і підмножини можна використовувати послідовні і зв'язані списки . Маються три основних засоби зробити це.
Послідовне представлення. Множина S з k елементів може являти собою неупорядкований k-елементний список {s1, s2, s3, ...,sk}. Тому з множиною можна працювати, як з вектором A з k компонент A[ 1:k], де компоненти - елементи S чи посилання на них. При цьому пошук елемента множини простіше, якщо сполучити порядок списку з порядком S, тобто вважати набір компонентів А упорядкованим, наприклад, по зростанню.
Зв'язане представлення. Для зберігання інформації про елементи множини можна використовувати 2-зв'язкові (двонаправлені) лінійні списки, записи яких зв'язані за допомогою пари покажчиків, записаних в адресних полях записів списку. Структура 2-зв'язного списку показана на рис.1.1.
Рисунок 1.1. Структура зберігання інформації о множині за допомогою 2-звязного списку
Для кожного запису у полі prev міститься адреса попереднього запису, у полі - next - адреса наступного запису, а data позначає інформаційне поле. Для доступу до списку можуть бути використані адреси початкової (start), кінцевої (end) і поточної (this) записів списку. Індикатори початкового і кінцевого записів є нульові (NULL), як і значення адресних полів start і end, відповідно.
Обробка списку будується на основі процедур модифікації і перегляду. Процедури модифікації повинні забезпечувати вставки і виключення записів списку. Часткою процедур вставки і виключення є процедури додати і видалити початковий чи кінцевий запис списку. Рис. 1.2 ілюструє процедуру вставки нового запису Z після запису Y.
Рисунок 1.2 – Структурна схема вставки елемента у множину
Процедури перегляду списку повинні забезпечувати зсув покажчика поточного запису (this) на необхідне число позицій у напрямку початку чи кінця списку, як показано на рис. 1.3.
Рисунок 1.3 – Структурна схема зсуву покажчика поточного запису множини
Окремим випадком зсуву покажчика поточного запису є перехід до початкового чи кінцевого записів списку, що дозволяє ініціалізувати покажчики start і end після модифікацій на початку і кінці списку.
Основні операції над множинами
о
б'єднання
().
Множина елементів, які належать хоча
б одному з двох множин (або А, або В, або
А та В).
x
A
B
п
еретинання
().
Множина елементів, які належать одночасно
двом множинам
x
A
B 
різниця. Множина елементів, які належать одній множині та не належать іншій.
x
A - B 
симетрична різниця (ознака
)
Множина елементів, які належать або
різниці між А та В, або різниці між В та
А.
x
A
B
Для виконання роботи треба знати співвідношення між операціями над множинами: ( Ø – пуста множина, U – універсальна множина)
1. А А .
2. Якщо А В і В А А = В .
3. Якщо А В і В С А С .
4. Ø А .
5. А U .
6. А + В = В + А - комутативність.
7. АВ = ВА - комутативність.
8. А + (В + С) = (А + В) + С асоціативність.
9. А(ВС) = (АВ)С асоціативність.
10. АА = А .
11. А (В + С) = АВ + АС дистрибутивність 1 закон.
12. А + ВС = (А + В)(А + С) дистрибутивність 2 закон.
13. А + Ø = А для пустого елементу.
14. А А = А .
15. А + U = U одиниця.
16. А Ø = Ø.
17.
А
В
А + В = В, АВ = А,
.
18.
А +
= U .
19.
А
=Ø .
20. А U=A
21.
=
U .
22.
=Ø.
23.
= А.
24
теорема де Моргана
Парадокс Расселу. Розглянемо всі множини, не включаючи самих себе. Розглянемо множину всіх таких множин. Тоді: якщо вона не включає себе, то вона включає себе.