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

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

НОВОКАХОВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ

МЕТОДИЧНІ ВКАЗІВКИ

До проведення практичних занять

з дисципліни “Основи дискретної математики”

для студентів заочного відділення

спеціальності 6.050103 - „Програмна інженерія”

І. ПРОГРАМА НАВЧАЛЬНОЇ ДИСЦИПЛІНИ “ОСНОВИ ДИСКРЕТНОЇ МАТЕМАТИКИ”

Розділ 1. Теорія множин

Поняття множини. Способи задання множин. Порожня множина. Операції над множинами. Властивості множин. Алгебра множин.

Розділ 2. Вступ до математичної логіки

Поняття логічної функції. Алгебра Буля, її закони. Методи мінімізації булевих функцій. Загальна характеристика висловлювань. Логічні операції. Таблиці істинності.

Розділ 3. Комбінаторний аналіз

Комбінаторні схеми. Загальні правила суми та добутку. Комбінаторні схеми: розміщення, розміщення з повтореннями, функціональні відображення. Комбінаторні схеми: сполучення, сполучення з повтореннями. Комбінаторні схеми: розбиття.

Розділ 4. Бінарні відношення

Поняття бінарного відношення. Завдання бінарного відношення з допомогою матриці та графа. Композиція відношень.

Розділ 5. Теорія графів

Основні поняття теорії графів. Цикломатичний базис, цикломатичне число матриці графа. Алгоритм знаходження мінімальних шляхів в навантажених графах. Алгоритм фронту хвилі, алгоритм Форда-Беллмана.

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

Множина – це об’єднання об’єктів в єдине ціле. Множина визначена, коли ми можемо вирішити - будь-який даний об’єкт є її членом чи ні.

Для позначення конкретних множин використовують різні прописні літери A, S, X,… або прописні літери з індексами , і т.і. Для позначення елементів множин в загальному вигляді використовують різні малі літери з індексами , і т.і.

В теорії множин використовується поняття „порожньої множини”. Позначається вона символом Æ.

Розглянемо дві множини та , та введемо декілька операцій над ними. Для графічної ілюстрації будемо використовувати так звані кола Ейлера. Також будемо використовувати знаки логічних операцій: кон’юнкції «», дизъюнкції «», імплікації «», тотожності «».

1. Об’єднання А та В () – це множина, яка містить усі елементи множини А, усі елементи множини В та не включає ніяких інших елементів, тобто

(«» - логічна операція диз’юнкції (логічне «або»)

2. Пересічення А и В – це множина, яка містить ті і тільки ті елементи, які належать одночасно до множини А та до множини В, тобто

де знак «» позначає логічну операцію кон’юнкції (логічне «і»).

3. Різниця А та В (відносне доповнення) – це множина, яка містить ті і тільки ті елементи, які належать А, та не належать В, тобто

4. Диз’юнктивна сума А та В (або симетрична різниця) – це множина, яка містить усі елементи множини А, що не належать В, та всі елементи множини В, що не належать множині А, та не містять ніяких інших елементів, тобто ,

Де - символ операції диз’юнктивної суми двох множин.

Цілком природно, що

Зручно сукупність допустимих об’єктів зафіксувати явним чином та вважати, що множини, які розглядаються, складаються з елементів цієї сукупності. Її називають основною множиною (універсумом) та позначають U. Універсум U арифметикі – числа, універсум U зоології – тварини.

Будь-яку множину будемо розглядати в зв’язку з універсумом, який з допомогою кол Ейлєра будемо асоціювати з прямокутником на площині, всередені якого будемо зображати множини:

Поиск по сайту: