ЛАБОРАТОРНА РОБОТА №1. МНОЖИНИ. ОСНОВНІ ПОНЯТТЯ
Мета: Засвоїти основні поняття множин та способи їх задання.
Теоретичні відомості: Множини належать до категорії найзагальніших, основоположних понять математики.
Приклади:
• множина натуральних чисел;
• множина цифр десяткової системи;
• множина цифр двійкової системи;
• множина парних чисел.
Є кілька способів подання множин:
1. Вербальний (словесний) – за допомогою опису характеристичних властивостей, які повинні мати елементи множин. Об’єкти, що утворюють множину, називають її елементами, або членами. Прикладом множини можуть бути: множина сторінок книги (кожна сторінка є елементом цієї множини); множина всіх дійсних чисел, більших від
і менших від 1; множина студентів тощо.2. Список (перелік) усіх елементів у фігурних дужках. Стосовно зазначених вище прикладів маємо:
{1, 2, 3, …};
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
{0, 1};
{2, 4, 6, …};
3. Предикатний (висловлювальний) за допомогою предиката, тобто множина подається у вигляді
або 
, де P(x) є предикатом, набуває значення «істина» для елементів цієї множини. Приклади:{1, 2, 3, 4, …} = {x | x - натуральне число};
{0, 1, 2, 3, 4, …, 9} = {x | x – цифра десяткової системи числення};
{0, 1} = {x|x-цифра двійкової системи}= { x | x2 – x = 0};
{2, 4, 6, …} = { x| x – парне число} = { x |
n 
N(x = 2n)};4. За допомогою породжувальної процедури (алгоритму), що описує спосіб отримання елементів множини із уже існуючих елементів або інших об’єктів, якщо такий спосіб існує. Для зазначених прикладів існують породжувальні процедури. Для перших двох і четвертого це:
а) 1
; б) якщо 
, то 
також є 
;б) 0
; б) якщо 
,то також є 
, доки 
;в)
; б) якщо 
, то 
, також є 
.5. Аналітичний – за допомогою аналітичних виразів, що містять позначки множин та операцій над ними.
Із наведених прикладів випливає, що множини бувають скінченними та нескінченними. Множини називаються скінченними, якщо число їх елементів скінченне, тобто існує натуральне число n, яке є числом елементів множини. Множини називають нескінченними, якщо вони містять нескінченне число елементів.
Порожня множина
У теорії множин використовують поняття порожньої множини. Її позначають
. Множина може взагалі не містити елементів, наприклад:S = {x | x – непарне число, що ділиться на 2} = Ø ;
;Для позначення цього факту вводять поняття порожньої множини. Це дає можливість оперувати будь-якою множиною без попереднього застереження, існує вона чи ні.
Операції над множинами
1. Об’єднання A і B (
) – множина, що складається з усіх елементів множини А та всіх елементів В і не містить жодних інших елементів, тобто 
, де символ «V» позначає логічну операцію диз’юнкції (логічне АБО), рис. 1.1.
Рисунок 1.1 – Об’єднання множин А і В2. Переріз А і В – множина, що складається з тих і тільки тих елементів, які належать одночасно множині А та множині В, тобто
, де символ «
» позначає логічну операцію кон’юнкції (логічне І), рис.1.2.
Рисунок 1.2 – Переріз множин А і В3. Різниця А та В (відносне доповнення) – множина, що складається з тих і тільки тих елементів, які належать множині А і не належать В, тобто
, рис.1.3.
Рисунок 1.3 – Різниця мнoжин А і В4. Диз’юнктивна сума А та В (симетрична різниця) – множина, що складається з усіх елементів А, які не належать множині В, й усіх елементів В, які не належать множині А, та яка не містить ніяких інших елементів, тобто
, де для позначення операції диз’юнктивної суми двох множин використано той самий символ 
, що й для логічної операції додавання за mod2. Очевидно, що 
– отже, остання формула є аналітичним поданням множин, рис.1.4.
Рисунок 1.4 – Дизюктивна сума А та ВУніверсум V
Зручно сукупність допустимих об’єктів зафіксувати явно, та вважати, що множини, які розглядаються, складаються з елементів цієї сукупності. Її називають основною множиною (універсумом) і позначають через V.
Нова операція V – A = Ā (абсолютне доповнення).
Ā – це множина, що містить усі елементи універсуму, за винятком А, рис.1.5.
Рисунок 1.5 – Абсолютне доповненняМножину, елементами якої є всі підмножини множини А, називають множиною підмножин (множиною-степенем) множини А і позначають P(A). Так, для триелементної множини
маємо 
.У разі скінченної множини A, що складається з n елементів, множина підмножин P(A) містить
елементів [1].Завдання до лабораторної роботи
1. Складіть алгоритм та програму, який як вхідні дані одержує дві множини і визначає, чи рівні ці множини, чи є одна з них підмножиною другої.
2. Складіть алгоритм та програму, який як вхідні дані одержує множину і конструює список всіх можливих підмножин даної множини.
3. Складіть алгоритм та програму, яка моделює операції над множинами у графічному режимі:
;
;
−B;
.Контрольні питання
1. Що таке множини? Наведіть приклади різних множин.
2. Як можна визначити множину?
3. У яких випадках можна вважати, що множина
, 
, 
є рівними?4. Що таке скінченна і нескінченна множини?
5. До яких із цих множин належить порожня множина?
6. Для чого використовують порожню множину?
7. Що таке підмножина?
8. Чи завжди будь-яка множина містить порожню множину? Аргументуйте відповідь.
9. Чим відрізняється за значенням строге включення
від включення 
? Аргументуйте відповідь.10. Чим відрізняється поняття включення
від поняття належності 
?11. Як розрізняють елементи множини та її підмножини? Відповідь ілюструйте прикладами.
12. Що таке множина-степінь? Які використовують при цьому позначення?
13. Чи може множина входити до складу своїх елементів?
14. Які є способи задання множини?
15. Що таке універсум?
ЛАБОРАТОРНА РОБОТА №2. ВІДНОШЕННЯ
Мета: Засвоїти основні поняття та властивості відношень
Теоретичні відомості: Відношення означає будь-який зв’язок між предметами або поняттями. Відношення між парами об’єктів називають бінарними (двомісними).
Приклади бінарних відношень:
• відношення належності;
• включення множин;
• рівність дійсних чисел;
• нерівність (натуральних, дійсних чисел);
• бути братом;
• ділитися на будь-яке натуральне число;
• входить до складу якого-небудь колективу.
Для наведених бінарних відношень можна записати відповідні їм співвідношення:
•
•
•
•
•
•
;•
– староста групи 1КН-09.Означення: бінарне відношення А, що діє з множини X у множину Y, називають деяку підмножину X
Y (A⊂ X Y).Отже, бінарне відношення встановлює відповідність елементів множини X елементам множини Y. Елемент X називають першою координатою, а елемент Y – другою координатою впорядкованої пари. Множину перших координат називають областю визначення (лівою областю) відношення А. Множину других координат – областю значень (правою областю) відношення А. У таких випадках вважають, що А є відношенням від X до Y. Його називають також відповідністю й позначають X→Y. Відношення може бути подане за допомогою: фактор-множини (множину всіх перерізів відношення А називають фактор-множиною множини Y за відношенням А і позначають Y/A. Вона повністю визначає відношення А), матриці або графа.
Матричний спосіб ґрунтується на поданні відношення A⊂ X
Y відповідною йому прямокутною таблицею (матрицею), що складається з нулів та одиниць, де стовпці – перші координати, а рядки – другі, причому на перетині i-го стовпця і j-го рядка буде 1, якщо виконується співвідношення 
, або 0 – якщо воно не виконується, рис.2.1.| |  |  |  |  |
   | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | |
| 1 | 0 | 1 | 0 | |
| Рисунок 2.1 – Матриця відношення | ||||
Матриця повного відношення – це квадратна матриця, яка складається лише з 1; матриця тотожного (діагонального) відношення – це квадратна матриця, яка складається з 0 та 1 по головній діагоналі; матриця порожнього відношення – це квадратна матриця. Що складається лише з 0.
Відношення також можна зобразити за допомогою орієнтованого графа. Його вершини відповідають елементам множини X та Y, а дуга спрямована від вершини
до 
, означає, що співвідношення виконується, рис.2.2.
Рисунок 2.2 – Види графів відношеньОскільки відношення – це множини над ними можуть виконуватися всі теоретико-множинні операції. Крім того, виділяють специфічні для відношень операції: обернення (симетризація) і композиція.
Відношення симетричне (обернене) деякому відношенню A⊂ X
Y, позначають як 
, воно є підмножиною множини Y X, утвореною тими парами 
, для яких 
.Композиція відношень - нехай дано три множини X, Y, Z і два відношення A⊂ X
Y, та В⊂ Y Z. Композиція відношень А та В є відношенням С, що складається з усіх тих пар 
, для яких існує таке 
, що 
й 
. Позначаємо композицію відношень символом 
. Тоді:
.Властивості відношень
Нехай А бінарне відношення у множині X (
). Тоді відношення А є:• рефлексивним, якщо
, тобто воно завжди виконується між елементом іним самим (
). Як приклад такого відношення можна навести відношення нестрогої нерівності (
) на N, Z та R;• антирефлексивним, якщо
. Тобто якщо співвідношення 
виконується, то 
. Це приклад відношення строгої нерівності на N, Z та R, відношення «бути старшим» у множині людей;• симетричним якщо
, тобто у разі виконання співвідношення виконується співвідношення 
. Як приклад відношення можна навести відстань між двома точками на площині, відношення «бути братом» у множині чоловіків;• асиметричним, якщо
, тобто з двох співвідношень і щонайменше одне не виконується. Як приклад такого відношення можна навести відношення «бути батьком» у множині людей, відношення строгого включення в множину всіх підмножин деякого універсуму. Очевидно, якщо відношення асиметричне, то воно й анти рефлексивне;• антисиметричним, якщо
, тобто обидва співвідношення та одночасно виконуються тоді й тільки тоді, коли 
. Як приклад можна навести нестрогу нерівність ( ) на N, Z та R;• транзитивним, якщо
, тобто з виконанням співвідношень й 
виливає співвідношення 
. Як приклад можна навести відношення «бути дільником» у Z, «бути старшим» у множині людей [1].