Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
🚀 Вийди на новий рівень крипто-торгівлі!
Easy Trade Bot — автоматизуй свій прибуток уже зараз!
Ми пропонуємо перелік перевірених прибуткових стратегій на такі пари як BTC, DOT, TRX, AAVE, ETH, LINK та інші. Ви можете підключити автоматичну торгівлю на своєму акаунті Binance або отримувати торгові рекомендації на email у режимі реального часу. Також можемо створити бота для обраної вами монети.
Всі результати торгів ботів доступні для перегляду у зручних таблицях на головній сторінці. Швидко, динамічно та прозоро!
Множини
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2025
Тип роботи:
Інші
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Множини
2.1. Основні поняття теорії множин
Поняття множини належить до категорії найзагальніших, основоположних понять математики. Відповісти на питання «Що таке множина?» не так просто, як це здається на перший погляд. У повсякденному житті та практичній діяльності часто доводиться говорити про деякі сукупності різних об’єктів: предметів, понять, чисел, символів тощо. Наприклад, сукупність сторінок у книзі, сукупність книг у бібліотеці, сукупність об’єктів, які складають основні фонди підприємства, сукупність характерних рис приватного підприємства, сукупність об’єктів і суб’єктів господарської діяльності, сукупність законодавчих актів, які регулюють економічні відносини.
На підставі інтуїтивних уявлень про будь-які подібні чітко визначені сукупності об’єктів сформувалося математичне поняття множини як об’єднання об’єктів у єдине ціле. Саме такої точки зору дотримувався засновник теорії множин німецький математик Георг Кантор. Група математиків, які працювали під псевдонімом Н.Бурбаки, стверджувала: «Множина утворюється з елементів, що мають певні властивості і знаходяться у певних відношеннях між собою чи з елементами інших множин».
Математичне поняття множини пов’язане з абстракцією, яку називатимемо абстракцією множини. Суть її полягає в тому, що всі існуючі властивості і зв’язки предметів не розглядаються, відокремлюються лише одна або кілька властивостей або зв’язків, які виражають належність цих предметів до деякої множини. Якщо ми розглянемо множину співробітників планово-економічного відділу деякої організації, то елементами цієї множини є конкретні люди, які працюють в цьому відділі. Всі властивості цих людей ігноруються за виключенням однієї властивості – бути співробітником планово-економічного відділу. Об’єкти, що утворюють множину, називаються її елементами, або членами. Множина є визначеною, коли можна встановити, чи є будь-який об’єкт її елементом або ні. Наприклад, якщо ми розглядаємо множину студентів групи 1ЕК1, то всі властивості (молодих людей, які складають групу 1ЕК1) і зв’язки з іншими множинами ігноруються, відокремлюється лише зв’язок з групою 1ЕК1, тобто властивість бути саме студентом саме групи 1ЕК1.
Якщо ми розглянемо множину студентів, яка знаходиться кожного вівторка весняного семестру на другій навчальній парі, в аудиторії 402 третього корпусу ХДТУ, то виявиться, що цю множину складають ті самі студенти групи 1ЕК1, що і тільки що розглянуту множину. Хоча для елементів цієї множини основним є зв’язок з певною аудиторією в певний час. Але в цій аудиторії в цей час знаходяться саме студенти групи 1ЕК1, хоча зараз не важливо, що це студенти групи 1ЕК1, важливим є лише те, що ці студенти знаходяться саме в даній аудиторії в даний час, тобто відокремлюється зв’язок саме з аудиторією в даний час. Іншими словами одні й ті самі об’єкти можуть одночасно бути елементами різних множин.
Для позначення конкретних множин використовують великі літери /,/,/,... або великі літери з індексами /, / і т. д. Для позначення елементів множин загалом застосовують малі літери /, /, /, ... або малі літери з індексами /, / і т.д.
Для позначення того, що / є елементом множини / (тобто / належить /), будемо застосовувати запис /, а запис / означатиме, що елемент / не належить множині /. Записом / користуються як скороченням для запису /. Символ / називається символом належності.
Приклад 2.1. Наведемо ще кілька прикладів множин:
Множина натуральних чисел, які є меншими за 15. Позначимо її /;
Множина цифр десяткової системи. Позначимо її /;
Множина цифр двійкової системи. Позначимо її /;
Множина парних чисел. Позначимо її /;
Множина видів навчальних занять студентів. Позначимо її /.
Таким чином, ми дійшли проблеми задання множин. При цьому наведені вище приклади множин задають описи характеристичних властивостей, які повинні мати їхні елементи.
2.1.1. Способи подання множин
Є кілька способів подання множин.
1. Вербальний (словесний) за допомогою опису властивостей, які повинні мати елементи множин.
2. Список (перелік) усіх елементів у фігурних дужках.
Приклад 2.2. Стосовно зазначених вище прикладів маємо:
/;
/;
/;
/.
/, де
/ – лекції;
/ – лабораторні роботи;
/ – практичні заняття;
/ – індивідуальна робота;
/ – самостійна робота.
3. Предикатний (висловлювальний, породжувальний) за допомогою предиката, тобто множина задається у вигляді / або /, де / набуває значення «істина» для елементів множини.
Приклад 2.3. Приклади предикатів:
/ – натуральне число, яке менше за 15};
/ – цифра десяткової системи};
/ – цифра двійкової системи/;
/ – парне число/;
/ – від навчальних занять студентів}.
4. За допомогою породжувальної процедури, яка описує спосіб отримання елементів множини із вже існуючих або інших об’єктів, якщо такий спосіб існує. Елементами множини є всі об’єкти, які можуть бути створені за допомогою цієї процедури. Частіше за все породжуючи процедура задається рекурсивними правилами.
Приклад 2.4. Задамо породжуючі процедури для раніше наведених прикладів:
для множини /:
а) /; б) якщо /, то / теж /, поки /;
для множини /:
а) /; б) якщо /, то теж /, поки /;
для множини B:
а) /; б) якщо /, то / теж /, поки /;
для множини /:
а) /; б) якщо /, то / теж /;
для множини / породжуючої процедури не існує, тому що не зрозуміло яким чином можна отримати наступний елемент із вже існуючих.
5. Аналітичний (за допомогою формул). Про цей спосіб далі.
Із наведених прикладів випливає, що множини бувають скінченими та нескінченними. Множини називають скінченими, якщо число їх елементів скінчене, тобто існує натуральне число /, яке є числом елементів множини. Множини називають нескінченними, якщо вони містять /нескінченне число елементів.
Введені вище поняття теорії множин з успіхом можуть бути використані в основах аналізу, алгебрі, математичній логіці, економіці, та ін. Однак при більш строгому розгляді такі інтуїтивні уявлення можуть виявитися незадовільними. Недосконалість інтуїтивних уявлень про множини, їх недостатність ілюструється, наприклад, відомим парадоксом Б.Рассела, який формулюється таким чином. Розглянемо множину / всіх таких множин /, що / не є елементом /. Тоді, якщо / не є елементом /, то за означенням / також є елементом /. З іншого боку, якщо / є елементом /, то / – одна з тих множин /, які не є елементами самих себе, тобто / не є елементом /. У будь-якому випадку / є елементом / й / не є елементом /. Парадокс Рассела частіше за все формулюють у вигляді запитання: “Чи голить себе цирульник, який голить тих, хто не голиться сам?”, на яке не існує відповіді.
Цей парадокс свідчить про те, що теорія множин, яка широко використовується в її інтуїтивному, «наївному» викладі, є суперечливою. Формалізація теорії множин, пов’язана, зокрема, з усуненням парадоксів, сприяла розвитку не тільки методів теорії множин, а й математичної логіки.
Приклад 2.5. Наведемо приклади інших множин:
За колишньою марксистською класифікацією функціональною основою розвитку людського суспільства є матеріальне виробництво, яке як множина, позначимо її /, складається з трьох елементів, які теж є множинами: /, де
/ – множина робочих ресурсів,
/ – множина предметів праці,
/ – множина засобів праці.
В свою чергу / множина, яка називається множиною продуктивних сил.
Множина / засобів виробництва складається з двох елементів: / – множини предметів праці і / – множини засобів праці:
/.
За ринковою класифікацією, яка панує зараз, множина економічних ресурсів /, тобто ресурсів, які використовуються для виробництва товарів і послуг, складається з двох елементів:
/, де
/ – множина матеріальних ресурсів,
/ – множина людських ресурсів.
2.1.2. Порожня множина
У теорії множин використовується поняття порожньої множини. Позначається вона символом .
Множина може взагалі не містити елементів, наприклад
/ – непарне число, що ділиться на /;
/.
Для позначення цього факту вводиться поняття порожньої множини.
Це поняття відіграє дуже важливу роль при заданні множин за допомогою опису. Так, без поняття порожньої множини не можна говорити про множину відмінників групи спеціальності “Економічна кібернетика” або про множину дійсних коренів квадратного рівняння, не пересвідчившись заздалегідь, чи є взагалі в студентській групі відмінники або чи має задане рівняння дійсні корені. Поняття порожньої множини дає змогу оперувати множиною відмінників групи, не піклуючись про те, чи є відмінники в групі, яка розглядається. Теж саме стосується й множини дійсних коренів квадратного рівняння. Порожню множину умовно будемо відносити до скінченних множин. Можна довести, що порожня множина єдина.
Таким чином, уведення порожньої множини дає можливість оперувати будь-якою множиною без попереднього застереження, існує вона чи ні.
2.1.3. Операції над множинами
Розглянемо дві множини А та В і введемо кілька операцій над ними. Для графічної ілюстрації будемо використовувати кола Ейлера. Для зображення множини на площині креслять замкнену лінію із заштрихованою внутрішньою областю (найчастіше – це коло, звідси й назва відповідного інструмента, що широко застосовується в теорії множин).
Зазначимо, що в подальшому викладі використовуватимемо символи вже відомих нам логічних операцій кон’юнкції «/» диз’юнкції «/» імплікації «/», еквіваленції «/» для формалізованого запису означень і теорем.
Означення 2.1. Об’єднання / і / (/) – множина, що складається з усіх елементів множини /, всіх елементів множини / і не містить ніяких інших елементів (рис.2.1), тобто
/,
де символ «/» позначає логічну операцію диз’юнкції (логічне «або»), тобто, згадуючи операцію „диз’юнкція”, елемент / належить множині / тоді і тільки тоді, коли або
1. / істинне і / хибне, або
2. / істинне і / хибне, або
3. / істинне і / істинне.
/
Рис.2.1
Означення 2.2. Переріз / і / – множина, що складається з тих і тільки тих елементів, які належать одночасно множині / та множині / (рис.2.2), тобто
/,
де символ «/» позначає логічну операцію кон’юнкції (логічне «і»), тобто згадуючи операцію „кон’юнкція”, елемент / тоді і тільки тоді, коли / і / істинні одночасно.
/
Рис.2.2
Означення 2.3. Різниця / і / (відносне доповнення) – множина, що складається з тих і тільки тих елементів, які належать множині / й не належать / (рис.2.3), тобто
/.
Тобто, елемент / тоді і тільки тоді, коли / істинне і / хибне одночасно.
/
Рис.2.3
Означення 2.4. Диз’юнктивна сума / і / (симетрична різниця) – множина, що складається з усіх елементів /, які не належать множині /, й усіх елементів /, які не належать множині /, та яка не містить ніяких інших елементів (рис.2.4), тобто
/.
Тобто, елемент / тоді і тільки тоді, коли або
1. / істинне і / хибне одночасно, або
2. / істинне і / хибне одночасно.
/
Рис.2.4
Очевидно, що
/.
2.1.4. Універсум /
Звичайно, вже в контексті деякої задачі, в якій виникає конкретна множина, явно або неявно обмежується сукупність об’єктів, що є допустимими (натуральні числа – серед цілих або дійсних залежно від контексту, студенти – серед студентів факультету, університету, або серед всіх студентів України, або світу залежно від контексту).
Зручно сукупність допустимих об’єктів зафіксувати явно, як деяку множину та вважати, що множини, які розглядаються, складаються з елементів цієї множини. Її називають основною множиною (універсумом) і позначають /.
Наприклад, універсумом / для множин, які виникають в деякій арифметичній задачі, є числа (залежно від контексту натуральні, цілі, дійсні або комплексні). Універсумом / для множин деякої задачі, що стосується зоології, є множина тварин (залежно від контексту це множина всіх тварин або ссавців, або птахів і т.д.).
Приклад 2.6. Якщо в задачі мова іде про студентів, то універсумом / може бути множина всіх студентів деякої групи, або факультету, або деякого університету, або всіх ВНЗ України, або всього світу. Наприклад, якщо в задачі підраховується успішність деякого окремого студента групи 1ЕК, то в якості / достатньо обрати множину студентів цієї групи, якщо складається порівняльна таблиця успішності студентів першого курсу КНЕУ або ХДТУ, то в якості універсуму / достатньо розглядати множину всіх студентів першого курсу даних навчальних закладів.
Будь-яку множину розглядатимемо у зв’язку з універсумом, який на колах Ейлера асоціюватимемо з прямокутником на площині, всередині якого зображатимемо множини, як ми робили, починаючи з рис.2.1.
Нова операція / – (абсолютне доповнення /) – це множина, що містить усі елементи універсуму, за винятком елементів / (рис.2.5).
/
Приклад 2.7. Якщо розглядати в якості універсуму / множину співробітників деякої фірми та означити літерами:
/ – множину менеджерів цієї фірми;
/ – множину співробітників за віком більш 30 років;
/ – множину співробітників за віком більш 40 років;
/ – множину співробітників, які мають стаж роботи більш за 5 років.
Визначимо зміст множин:
1) / – множина співробітників фірми, які не є менеджерами;
2) / – множина співробітників фірми, яким за віком не більше 30 років;
3) / – множина менеджерів фірми, яким за віком більш 30 років;
4) / – множина співробітників фірми за віком не більш 30 років, які мають стаж роботи не більш 5 років;
5) / – множина співробітників фірми за віком більш 30 років, які мають стаж роботи не більш 5 років.
2.1.5. Підмножина. Рівність множин.
Означення 2.5. Множина / називається підмножиною множини /, якщо кожен елемент / є елементом /.
Для позначення цього факту вводиться знак «/» – символ включення (або «/»); іншими словами, /.
Якщо необхідно підкреслити, що множина / містить також інші елементи, крім елементів множини В, то використовують символ строгого включення: /. Зв’язок між символами / і / задається виразом /. Загалом будемо використовувати символ «/».
Говорять, що множина / є істинною (або власною, від слова «власне») підмножиною /, якщо / і / на відміну від неістинних (або невласних) підмножин та / будь-якої множини /.
Приклад 2.8. Стосовно вищенаведеного приклада підмножинами множини U співробітників деякої фірми є множини /, /, /, /, /, /, /, /, /. Крім того можна розглядати, що
/ – множина співробітників фірми, яким за віком більш 40 років, є підмножиною множини співробітників за віком більш 30 років.
/, / – множина співробітників фірми за віком не більш 30 років, які мають стаж роботи не більш 5 років, є підмножиною множини співробітників фірми, яким за віком не більш 30, й одночасно є підмножиною множини співробітників фірми, які мають стаж роботи не більш 5 років.
Підкреслимо, що всі наведені приклади підмножин є прикладами істинних підмножин.
Порожня множина не містить елементів. Отже, додаючи до множини / порожню множину, ми фактично нічого не додаємо. Тому завжди можна вважати, що будь-яка множина / містить порожню множину як підмножину.
Приклад 2.9. Нехай / – людська істота} і / – людська істота жіночої статі}; тоді зрозуміло, що /, а / – істинна підмножина /.
Треба бути уважним, щоб розрізняти елементи множини та підмножини цієї множини. Наприклад, коли пишуть / це означає, що елемент / є членом множини, що складається з трьох елементів: /, / і /. Коли ж пишуть /, це означає, що множина, що складається з одного елемента /, є підмножиною множини, яка складається з трьох елементів: /, /, /.
Таким чином, якщо Розов А.Ю. є студентом групи 1ЕК, то це означає, що цей студент є елементом множини / студентів групи 1ЕК. Якщо це єдиний студент цієї групи, який склав зимову сесію на “відмінно”, то студент Розов А.Ю., є єдиним елементом множини / студентів-відмінників групи 1ЕК за результатами зимової сесії, при чому /.
Означення 2.6. Дві множини рівні, якщо вони складаються з одних і тих самих елементів:
/.
Наприклад, /.
Справджується таке твердження: / тоді і тільки тоді, коли /.
Можна довести таке твердження: включення множин транзитивне, тобто справджується така рівність:
якщо /, то /.
2.1.6. Множина підмножин
Слід розуміти, що елементи множини самі можуть бути деякими множинами. Наприклад, книга з множини книг у шафі може розглядатися як множина сторінок. Потрібно звернути увагу на те, що йдеться про елементи множини, а не про підмножини (ніяка сукупність сторінок не може розглядатися як підмножина множини книг).
Множина / груп факультету складається із груп, тобто елементом множини / є група, як неподільне ціле, в той самий час кожна група є множиною студентів, але окремий студент не є елементом множини / груп факультету.
Означення 2.7. Множину, елементами якої є всі підмножини множини /, називають множиною підмножин (множиною-степенем) множини / і позначають /.
Приклад 2.10. Для триелементної множини / маємо
/.
У разі кінцевої множини /, що складається з n елементів, множина підмножин / містить / елементів. Слід підкреслити відмінності між відношенням належності (/) і відношенням включення (/). Як уже зазначалося, множина / може бути своєю підмножиною (/), але вона не може входити до складу своїх елементів (/). Навіть у разі одноелементних підмножин потрібно відрізняти множину / та її єдиний елемент а (дивись приклад). Відношення включення має властивість транзитивності, відношення належності цієї властивості не має. Тобто, із того, що / не витікає, що /, як здається на перший погляд.
Приклад 2.11. Розглянемо такі множини /, /. Дійсно /, але /.
2.2 Алгебра множин
2.2.1. Закони алгебри множин
Операції над множинами, як і операції над логічними змінними, мають деякі властивості. Останні виражаються сукупністю тотожностей незалежно від конкретного вмісту множин, що входять у них, і є підмножинами деякого універсуму /. Ми вже знаємо, що множина об’єктів разом з операціями утворюють алгебру. Множина всіх множин разом з операціями об’єднання, перерізу і абсолютного доповнення утворюють алгебру, яка називається алгеброю множин. Її основні властивості або закони алгебри множин наведені нижче.
1. Комутативні закони
а) /;
б) /.
2. Асоціативні закони
а) /;
б) /.
3. Дистрибутивні закони
а) /;
б) /.
Властивості та /
4 а) /;
4 б) /.
5 а) /;
5 б) /.
6 а) /;
6 б) /.
7 а) /;
7 б) /.
Закон ідемпотентності (самопоглинання)
8 а) /;
8 б) /.
Закон поглинання
9 а) /;
9 б) /.
Теорема де Моргана
10 а) /;
10 б) /.
Властивості доповнення, різниці та рівності
11) /;
14) /;
12) /;
15) /;
13) /;
16) /.
Можна довести, що:
1) Якщо /, то /;
2) / тоді і тільки тоді / тоді і тільки тоді / тоді і тільки тоді /;
3) /.
2.2.2 Методи доведення тотожностей алгебри множин
Основний метод доведення тотожності в алгебрі множин ґрунтується на застосуванні означення рівності множин і твердження про рівність множин. Такий зручний інструмент, як кола Ейлера може бути використаний для доведення тотожностей алгебри множин тільки після певної формалізації. Ми її не робитимемо, тому використовуватимемо кола Ейлера як ілюстративний інструмент.
Доведемо, наприклад, тотожність 3а) /, використовуючи твердження про рівність множин. Але спочатку проілюструємо її справжність за допомогою кіл Ейлера. Для цього треба представити на колах Ейлера множину з лівої частини тотожності / і множину з правої частини тотожності / і упевнитися в їхній рівності.
Для зображення лівої частини тотожності спочатку закреслюємо штрихом одного напрямку /, потім штрихом іншого напрямку закреслюємо /. Результатом є область, що закреслена (рис.2.7).
/
Рис.2.7
Для зображення правої частини тотожності спочатку закреслимо штрихом одного напрямку область /, штрихом іншого напрямку область /. Результатом / буде область подвійного закреслення (рис.2.8).
/
Рис.2.8
Очевидно, що обидві області співпадають (збігаються).
Приклад 2.12. Спочатку доведемо тотожність 3а) / /, використовуючи твердження про рівність множин.
Доведемо, що /. Для цього візьмемо будь-яке /, тоді за означенням операцій «/» і «/», / /. За законом дистрибутивності диз’юнкції відносно кон’юнкції маємо, що /, тобто / або /, що і було потрібно довести.
Доведемо, що /. Для цього візьмемо будь-яке /. Звідси / або / /, тобто /, що і було потрібно довести.
Згідно з твердженням про рівність множин 3а) / /.
Доведемо, що / за означенням рівності множин. Для цього знову візьмемо будь-яке /, тоді за означенням операцій «/» і «/», це еквівалентне тому, що /. Це в свою чергу за законом дистрибутивності диз’юнкції відносно кон’юнкції еквівалентне тому, що /, тобто / або /. Таким чином ми довели, що
/
тобто /.
За означенням рівності двох множин це означає, що / /.
Доведемо ту саму тотожність алгебраїчним способом. Нагадаємо, що при цьому ми маємо використовувати основні властивості (тотожності) алгебри множин (2а або 2б) причому, якщо ми доводитимемо деяку тотожність (2а або 2б), то всі інші вважатимемо доведеними.
Адже, треба довести /
Почнемо з правої частини
/
ми отримали ліву частину. Тотожність доведено.
Будь-яка теорема алгебри множин виводиться з тотожностей 2а) і 2б),тобто методом алгебраїчних перетворень.
Приклад 2.13. Доведемо властивість 8а) /, послідовно використовуючи властивості 4б), 5а), 3а), 5б), 4а).
/.
2.2.3. Узагальнення операцій над множинами, розбиття множини, декартів добуток множин.
Із властивостей комутативності й асоціативності операцій об’єднання випливає, що об’єднання кількох множин можна виконати, послідовно об’єднуючи їх, причому порядок входження множин не впливає на результат, наприклад /. Отже, об’єднання сукупності множин можна подати співвідношенням
/.
Аналогічно на / множин узагальнюється операція перерізу:
/.
Використовуючи узагальнення операцій об’єднання та перерізу на n множин, можна узагальнити також інші співвідношення, наприклад закон де Моргана, який в узагальненому вигляді має вигляд
/ і /.
Означення 2.8. Сукупність множин / називається розбиттям множини /, якщо об’єднання всіх цих множин співпадає з множиною /, тобто
1. /
переріз будь-яких двох різних множин / і / є порожньою множиною, тобто
2. /
Приклад 2.14. Наведемо приклади розбиття множин:
Нехай /, тоді сукупність множин / і / є розбиттям множини /, тому що /, а /.
Нехай / – множина співробітників деякої фірми. Розбиттям цієї множини є сукупність двох множин – множини чоловіків та жінок, які є співробітниками фірми.
Нехай / – множина студентів факультету. Сукупність множин /, де / – множина студентів /-ї групи факультету, є розбиттям множини /.
Введемо ще одну операцію над множинами.
Означення 2.9. Прямим (або декартовим) добутком множин / і / називається множина всіх упорядкованих пар елементів /, з яких перший належить множині /, а другий – множині / (позначається /):
/
Порядок входження пар може бути будь-яким, але розташування елементів у кожній парі визначається порядком множин, що перемножуються. Тому /, тобто прямий добуток властивості комутативності не має.
Приклад 2.15. Наведемо приклади декартового добутку:
Якщо /, /, тоді
/,
/.
Якщо є множина прізвищ /Стеценко, Чуйко, Козак} і є множина посад /старший менеджер, менеджер} філії деякої фірми.
Тоді декартів добуток /(Стеценко, старший менеджер), (Стеценко, менеджер), (Чуйко, старший менеджер), (Чуйко, менеджер), (Козак, старший менеджер), (Козак, менеджер)} є множиною всіх можливих варіантів розподілу прізвищ співробітників за всіма посадами даної філії.
Декартів добуток /(Старший менеджер, Стеценко), (Старший менеджер, Чуйко), (Старший менеджер, Козак), (Менеджер, Стеценко), (Менеджер, Чуйко), (Менеджер, Козак)} є множиною всіх можливих варіантів розподілу посад даної філії за всіма прізвищами (особами).
Зрозуміло, що в загальному вигляді для двох множин / і / виконується /.
Операція прямого добутку множин узагальнюється на будь-яку їх кількість і записується у вигляді
/
причому елементом прямого добутку / множин є впорядкована послідовність із / елементів (/), яка називається ще кортежем або вектором завдовжки /, а також впорядкованою /-кою.
Властивості асоціативності для прямого добутку також не виконуються, але виконується властивість дистрибутивності відносно об’єднання, перерізу і відносного доповнення (різниці):
/;
/;
/.
Якщо як співмножник декартового добутку /-множин використовується одна множина /, то це записується так:
/.
Операція декартового добутку відрізняється від операцій, введених раніше, тим, що елементи добутку множин суттєво відрізняються від елементів співмножників і є об’єктами іншої природи. Наприклад, якщо / – множина дійсних чисел, то декартовий добуток / – множина всіх точок площини.
2.2.4. Кола Ейлера як інструмент графічного зображення в теорії множин
Розглянемо інструмент ілюстрації в теорії множин, кола Ейлера, для графічного зображення всіх операцій перерізу з трьома множинами / (рис.2.9).
1) /
2) /
3) /
4) /
5) /
6) /
7) /
8) /
/
/
/
/
1)
2)
3)
4)
/
/
/
/
5)
6)
7)
8)
Рис.2.9.
Тут зображені всі варіанти розбиття площини універсуму /, якщо в операціях задіяні три множини. Ці варіанти можна використовувати для графічного зображення будь яких операцій з трьома множинами. Їхній алгебраїчний вираз можна використовувати для алгебраїчного запису результату операції з множинами. Наведемо приклади.
Приклад 2.16. На колах Ейлера зображено результат операцій з множинами. Виходячи з зображення навести результат в алгебраїчному вигляді.
1. /
/
Рис.2.10.
/.
Ми використали поняття розбиття універсуму. Але для алгебраїчного вигляду можна знайти і інші варіанти. Наприклад,
/ і т.д.
2. /
/
Рис.2.11.
/
3. /
/
Рис.2.12.
/
Як ви вже мабуть побачили, що аналогічно формулам алгебри логіки формули алгебри множин теж мають кілька різних варіантів. Ці варіанти відрізняються операціями і кількістю множин, що входять у формулу. Причому вираз, в який входять об’єднання перерізів всіх множин не тільки не є самим коротким, а навпаки є найдовшим. Чи не нагадує він ДДНФ для логічної функції? Якщо ви згадаєте означення ДДНФ, то побачите повну аналогію. Для логічних функцій побудова ДДНФ була першим етапом алгоритмів скорочення формул. В теорії множин це питання не стоїть так гостро. Значно більше значення має проблема доведення тотожностей.
2.3 Нечіткі множини та лінгвістичні змінні
2.3.1 Загальні відомості та означення
Класична математика є дуже потужним апаратом для розв’язання науково-технічних задач. Але не всі сфери людської діяльності допускають достатню ступінь формалізації для використання цього апарату. Людина постійно приймає рішення в соціальних процесах, опис яких характеризується неповнотою, нечіткістю та невизначеністю. Зокрема це стосується процесів соціально-економічної сфери. Основною діючою фігурою в цій сфері є людина-фахівець, яка мислить і оперує частіше за все нечіткими, нематематичними категоріями, наприклад, “у світі ще з кінця XIX сторіччя потреби практики різко посилювали увагу до інструментальних, практичних аспектів аналітичної економії, до питань функціонування ринкової економіки”.
Теорія нечітких множин дає змогу до певної міри формалізувати процеси і явища соціальної, економічної сфери та інших сфер.
Нечіткі множини широко використовуються в різних застосуваннях штучного інтелекту, теорії розпізнавання образів, теорії прийняття рішень тощо. Якщо до твердження «логічно кажучи, можна вивести майже всю сучасну математику з єдиного джерела – теорії множин» додати концепцію нечіткості, то це відкриє шлях до «подвоєння» математики: доповнюючи звичайну множину нечіткою (розпливчастою), можна кожному об’єкту в математиці поставити у відповідність його нечіткий (розпливчастий) аналог.
Означення 2.10. Нехай є множина /, елементи якої позначаються через /. Тоді нечіткою множиною / в множині / є сукупність упорядкованих пар /, де / а / – ступінь належності елемента / до нечіткої множини /, тобто кожному елементу з множини / ставиться у відповідність число / з деякої множини чисел /, де / називається простором належності. Коли / містить тільки дві точки 0 та 1, множина / не є нечіткою, тому що, кожному елементу /, який не належить нечіткій множині /, відповідає ступінь належності /, кожному елементу /, який не належить нечіткій множині /, відповідає ступінь належності /.
У теорії звичайних множин введено поняття характеристичного числа
/
Тобто характеристичне число / для всіх елементів / множини / (/)
Таким чином, ступінь належності в цьому випадку, повністю збігається з характеристичним числом. Тобто можна сказати, що якщо /, то елемент / абсолютно (на 100%) належить множині /, якщо /, то елемент абсолютно (на 100%) не належить множині /. В цьому випадку / теж є звичайною (чіткою) множиною, яка є підмножиною множини /, тобто деякі елементи множин / належать множині /, а деякі не належать. При цьому множина / містить два елемента: 1 і 0.
В випадку з нечіткими множинами може бути й не 100-відсоткова належність елементів множини / до множини /. Тому у подальшому вважатимемо, що / є відрізком [0, 1], причому 0 й 1 є відповідно нижчим і вищим ступенями належності. Основне припущення полягає в тому, що нечітка множина / може бути точно визначена зіставленням кожному об’єкту х числа, яке знаходиться в діапазоні від 0 до 1 і відображає ступінь його належності /.
У теорії нечітких множин так само, як і в теорії чітких множин, широко використовується поняття універсальної множини. При цьому універсальною множиною / нечіткої множини / називається область визначення функції належності /.
Нечітка множина /, /, визначається математично як сукупність упорядкованих пар, складених з елементів / універсальної множини /і відповідних ступенів належності / або безпосередньо у вигляді функції
/.
У науковій літературі можливі такі записи нечітких множин:
/;
/;
/,
або у вигляді табл.2.1.
Таблиця 2.1
х
/
/
/
/
/
/
/
/
0,2
0,6
0,3
0,8
1
0
0
Приклад 2.17. Щоб детальніше пояснити поняття нечіткої підмножини, розглянемо такий приклад. Передбачимо, що деяка множина / складається з дев’яти елементів /,
/.
Отже, нечітка підмножина /: не містить / і /; у невеликій мірі містить /, /; містить / трохи більше, ніж / і /; у значно більшій мірі містить / і /, не повністю містить / і /. Таким чином, можна створити математичну структуру, що дає змогу оперувати елементами.
Як приклад можна розглядати множину /, де кожен елемент / позначає зріст людини у сантиметрах, а саме /, /, /, /, /, /, /, /, /. А множина / описує таке нечітке поняття, як «бути дуже високою за зрістом людиною».
Наведемо означення поняття нечіткої підмножини, введеного засновником теорії нечітких множин Л. Заде [3]: «Нечітка підмножина / універсальної множини / характеризується функцією належності /, що ставить у відповідність кожному елементу / число / із множини [0,1] і характеризує міру належності елемента / підмножині /».
Означення 2.11. Множина, що містить єдиний елемент, називається синглетоном.
Синглетон може визначатися як серед чітких, так і серед нечітких множин.
Означення 2.12. Носієм нечіткої множини / називається множина / таких точок в /, для яких функція / – додатна.
Для вище приведеного прикладу 2.17 /.
Означення 2.13. Висотою нечіткої множини / називається величина /.
Для вище приведеного прикладу /.
Означення 2.14. Точкою переходу нечіткої множини / називається такий елемент множини /, ступінь належності якого множині / дорівнює 0,5.
Для вище приведеного прикладу точка переходу – це елемент /.
2.3.2. Теоретико-множинні операції з нечіткими операціями.
Так само як для чітких множин можна визначити включення і рівність нечітких множин, а також операції об'єднання, перетинання, доповнення, і т.д. над нечіткими множинами, тільки робиться це за допомогою функції належності.
Нагадаємо, що ступінь належності / є числами із множини /, яка звичайно розглядається як відрізок /. Введемо деякі операції з ступінями належності, які за позначенням співпадають з операціями алгебри логіки, але в теорії нечітких множин мають інші значення.
Означення 2.15. Нехай є два ступеню належності / і /. Тоді
/, /;
/, /.
Тобто нечітка кон’юнкція двох чисел / і / дорівнює мінімальному з цих двох чисел, а нечітка диз’юнкція дорівнює максимальному з цих двох чисел. Нечітка імплікація визначається більш складно за допомогою нечіткої кон’юнкції, а нечітка еквівалентність за допомогою нечіткої імплікації і кон’юнкції.
Нехай задані нечіткі підмножини /, / множини /.
/, /, /.
Означення 2.16. Об'єднанням нечітких множин / є нечітка множина /, /, ступінь належності елементів до якої визначається як /.
На рис.2.13 наведений результат виконання операції об’єднання двох нечітких множин, для яких множина / неперервно розподілена на відрізку /.
/
/
Рис.2.13
Рис.2.14
Означення 2.17. Перетином двох нечітких множин / називається нечітка множина /, /, функція приналежності елементів до якого визначається як /.
На рис.2.14 наведений результат виконання операції перерізу двох нечітких множин, для яких множина / неперервно розподілена на відрізку /.
Тобто / - це нечітка множина, така, що / і /.
Означення 2.18. Доповненням нечіткої множини / називається нечітка множина /, /, таке, що /, /.
/
Рис.2.15
Приклад 2.18. Розглянемо нечітку множину /, чисел, набагато більших нуля. Доповненням до цієї множини буде множина /, чисел, набагато менших нуля.
Означення 2.19. Різницею нечітких множин називається множина /, /, ступінь належності елементів до якої визначається як / (див. рис.2.15).
Означення 2.20. Симетричною різницею / називається множина /, де /.
Приклад 2.19. Нехай є дві нечіткі множини. Найдемо результати виконання визначених операцій:
/, /;
/;
/;
/;
/;
/.
Означення 2.21. Множиною рівня / нечіткої множини / в /, називається множина у звичному вигляді, складена з елементів /, ступені приналежності яких нечіткій множині / більші або рівні /.
/.
Нечіткі лінгвістичні змінні. Подальшим узагальненням поняття нечіткої множини є поняття лінгвістичної змінної.
Означення 2.22. Лінгвістичною змінною називається кортеж
де / – назва (ім’я) змінної; / (або просто /) – базова множина змінної /, тобто множина назв лінгвістичних значень змінної / зі значеннями з універсальної множини /; / – універсальна множина; / – синтаксичне правило (що має форму граматики), яке породжує назву / значень змінної /; / – семантичне правило, що ставить у відповідність кожній нечіткій змінній / її значення /, тобто нечітку підмножину / універсальної множини /.
Конкретна назва /, породжена синтаксичним правилом, називається термом. Терм, що складається з одного або кількох слів, які завжди фігурують разом, називають атомарним. Терм, що складається з одного або більше атомарних термів, називається складним.
Пояснимо поняття лінгвістичної змінної на конкретному прикладі.
Приклад 2.19. Нехай експерту треба оцінити вартість випуску продукції за допомогою понять «мала», «середня» і «висока». Максимальна вартість продукції становить 5000 грн. Для формалізації цього опису використовуємо поняття лінгвістичної змінної
/,
де / – вартість (назва змінної); / – базова терм-множина, що складається з множини назв лінгвістичних значень змінної /; тут /; / – універсальна множина, тут від 0 до 5000 грн.; / – процедура перебору елементів множини / (мала, середня, висока); / – процедура експертного опиту.
На рис.2.16. показано функції належності відповідних нечітких змінних /, /, /.
Існує кілька основних аспектів поняття лінгвістичної змінної, які потребують уточнення. По-перше, важливо зрозуміти, що поняття функції належності відмінне від поняття ймовірності. Так, висловлення про те, що значення функції належності «середня вартість» дорівнює 0,5, не має ніякого відношення до ймовірності того, що значення змінної «вартість» дорівнює 2500 грн.
Правильна інтерпретація значення функції належності, яке дорівнює 0,5, полягає в тому, що воно є лише суб’єктивною мірою того, наскільки вартість суми 2500 грн. відповідає в поданні суб’єкта слову «середня». Математичні операції, які застосовуються до значень функції належності, відмінні від операцій, що застосовуються до значень ймовірностей, хоча між ними існує деяка аналогія.
По-друге, лінгвістична змінна має структуру в тому значенні, що вона пов’язана двома правилами:
- синтаксичним – визначає спосіб породження лінгвістичних значень, які належать терму – множині цієї змінної;
- семантичним – визначає спосіб обчислення значень лінгвістичної змінної.
/
Рис.2.16
Зазначимо у зв’язку з цим, що типове значення лінгвістичної змінної, наприклад «не дуже мала вартість» і «не дуже висока вартість», включає те, що можна було б назвати первинними термами, наприклад «мала» та «середня», значення яких суб’єктивне і залежить від контексту. Передбачається, що значення таких термів визначено заздалегідь.
Дамо означення понять «синтаксичне» та «семантичне» правила.
Синтаксичне правило (процедура) – опис процесу утворення нових, осмислених для певної задачі управління, значень лінгвістичної змінної, виходячи з її терму – множини.
Семантичне правило (процедура) – процес, що дає змогу перетворити кожне нове значення лінгвістичної змінної, яка утворюється синтаксичною процедурою, на нечітку змінну, тобто приписати йому деяку семантику формуванням відповідної нечіткої множини.
2.3.3. Включення і рівність нечітких множин
Означення 2.23. Нехай задані нечіткі підмножини /, / множини /. Ступінь включення /, нечіткої множини / в нечітку множину / визначається по формулі /, де /, / ступені належності елемента / до множин / і /.
Якщо /, то / нечітко включається в множину / й позначається /. Якщо /, то / нечітко не включається в множину / й позначається /. Це поняття є узагальненням поняття включення для чітких множин. Дійсно, нехай / и / - чіткі множини й /, звідси випливає /. Якщо ж /, то /.
Приклад 2.20. Нехай задано множину /, і в неї дві нечіткі множини / і / /, тоді:
/
Аналогічно можна обчислити /, звідки випливає /, але /.
Означення 2.24. Ступінь рівності двох нечітких підмножин /, / множини /визначається як /, де /.
Якщо /, то множини нечітко рівні /. Якщо /, то множини нечітко не рівні /. Якщо /, то множини взаємно індиферентні /.
Поняття нечіткої рівності й нерівності, індиферентності є узагальненням понять рівності й нерівності для чітких множин. Дійсно, нехай / й / – чіткі множини, тоді у випадку /, /, якщо ж / и /.
Приклад 2.21. Нехай задано множину / і в неї дві нечіткі множини / і / / знайдемо ступінь рівності множин / і /:
/
звідки випливає /.
Означення 2.25. Нечітка множина / дорівнює нечіткій множині /.
/, якщо /.
Неважко помітити, якщо виконується рівність множин /, то ці множини є й нечітко рівними /.
Відношення
3.1. Основні поняття та властивості відношень
3.1.1. Основні означення.
Ми вже знаємо, що за Н. Бурбакі елементи множини можуть знаходитися в деяких відношеннях між собою або з елементами інших множин, але означення відношення не давалося. Загалом відношення означає який-небудь зв'язок між предметами або поняттями. Унарні (одномісні) відношення віддзеркалюють наявність деякої певної властивості (ознаки) у елементів множини (наприклад, «бути фахівцем» в множині співробітників фірми). У цьому випадку всі елементи / з цієї множини /, які мають цю властивість (ознаку) /, утворюють деяку підмножину множини /, яке називається унарним відношенням /, тобто /. Відношення між парами об'єктів називаються бінарними (двомісними). Звичайно відношення записується у вигляді співвідношень /, де / – відношення, яке встановлює зв'язок між елементом / і елементом /.
Приклад 3.1. Приклади бінарних відношень:
1. входити до складу деякого колективу;
2. відношення належності;
3. включення множин;
4. працювати в одній фірмі;
5. нерівність чисел;
6. бути братом;
7. ділитися на яке-небудь натуральне число.
Для наведених відношень запишемо відповідні їм співвідношення:
1. Розов – староста групи 1ЕК;
2.·Коцар і Степаненко вчаться в одній групі;
3.· /;
4. Резнік і Тимошенко працюють в одній фірмі;
5. /;
6. Богдан брат Віктора;
7. 6 ділиться на 3.
Бінарне відношення повністю визначається множиною всіх пар елементів /, для яких воно справджується. Тому будь-яке бінарне відношення можна розглядати як множину впорядкованих пар /, тобто можна дати таке строго математичне означення бінарного відношення.
Означення 3.1. Бінарним відношенням /, що діє з множини / у множину /, називається деяка підмножина декартова добутку множин /і / /, тобто /.
Приклад 3.2. Нехай множина /Стеценко, Чуйко, Козак}, є деякою множиною прізвищ, а множина /старший менеджер, менеджер} є множиною посад філії деякої фірми. Декартів добуток / містить 6 впорядкованих пар. Це пари /(Стеценко, старший менеджер), (Стеценко, менеджер), (Чуйко, старший менеджер), (Чуйко, менеджер), (Козак, старший менеджер), (Козак, менеджер)}. Розглянемо бінарне відношення /, де /(Чуйко, старший менеджер), (Стеценко, менеджер), (Козак, менеджер)}. Це відношення встановлює відповідність прізвищ осіб посадам, які вони займають у філії фірми, тобто є відношенням „займати посаду”.
Бінарне відношення встановлює відповідність елементів множини / елементам множини /. Зрозуміло, що співвідношення / можна записати у вигляді /, де /. Наприклад, Чуйко займає посаду старшого менеджера еквівалентно (Чуйко, старший менеджер) / „займати посаду”, / еквівалентно / (але не можна записати /). Елемент / називають першою координатою, а елемент / – другою координатою впорядкованої пари /. Множина перших координат називається областю визначення (лівою областю) відношення / і позначається /.
Множина других координат називається областю значень (правою областю) відношення / і позначається /. Якщо /, /, тоді /, /. У таких випадках кажуть, що / є відношенням від / до /, що воно ставить у відповідність елементам множини / елементи множини /, тому таке відношення (див. рис.3.1) називають також відповідністю та позначають /. Якщо /, то будь-яке відношення /: / є підмножиною / і називається відношенням в /. Тобто в цьому випадку відношення / ставить у відповідність елементу множини / елемент множини / (рис.3.2).
/
Рис.3.1
/
Рис.3.2
Якщо /, то кажуть, що відношення / задано на /.
Приклад 3.3. Надано дві множини /, /.
Нехай / – відношення «бути дільником» від / до /. Тоді / /. Відношення / – « = » від / до /: /; відношення / – «>» від / до /: /. /, /, /, /, /, /.
Відокремлюють такі випадки відношень в /:
1. Повне (універсальне) відношення /, яке справджується для будь-якої пари / елементів з /, тобто /. Наприклад, / – відношення «вчитися в одній групі» у множині /, де / – множина студентів групи 1ЕК.
2. Тотожне (діагональне) відношення /, що виконується тільки між елементом і ним самим. Наприклад, рівність на множині дійсних чисел.
3. Порожнє відношення, якому не задовольняє жодна пара елементів з /, тобто /. Наприклад, / – відношення «бути братом» у множині /, де / – множина жінок.
Повне і порожнє відношення можна визначити і для випадку відношень від / до /. Повним відношенням буде /, яке справджується для будь якої пари /, де /.
Порожнім відношенням є відношення, якому не задовольняє жодна пара елементів /, де /.
Означення 3.2. Розглянемо відношення /. Нехай елемент /. Перерізом відношення / за елементом / називається множина елементів / з /, для яких пара /.
Множину всіх перерізів відношення / називають фактором-множиною множини / за відношенням / і позначають /. Вона повністю визначає відношення /.
Приклад 3.4. /, /. Відношення
/, /.
Випишемо перерізи за всіма елементами множини / у такому вигляді:
Таблиця 3.1
/
/
/
/
/
/
/
/
/
/
Об'єднання множин другого рядка утворять фактор-множину /.
3.1.2. Подання бінарних відношень за допомогою матриці.
З означення бінарного відношення зрозуміло, що воно, як будь-яка множина, може бути подане вербальним способом, переліком, предикатним або аналітичним способом. Але є способи подання бінарних відношень, властиві тільки для них. З попереднього зрозуміло, що відношення може бути подане за допомогою фактора-множини. Розглянемо ще два способи подання скінченого бінарного відношення: за допомогою матриці й графа.
Матричний спосіб ґрунтується на поданні відношення / відповідною йому прямокутною таблицею (матрицею), що складається з нулів та одиниць, де стовпці – перші координати, а рядки – другі, причому на перетині /-го стовпця і /-го рядка буде 1, якщо виконується співвідношення /, або 0 – якщо воно не виконується.
Повне і порожнє відношення можна визначити і для випадку відношення від / до /. Повним відношення буде D=X*Y, для будь-якої пари (X,Y), де /, /.
Порожнім відношенням є відношення якому не задовольняє жодна пара елементів (X,Y), де /, /.
Приклад 3.5. Для наведеного у попередньому прикладі відношення матриця має такий вигляд:
Таблиця 3.2
/
/
/
/
/
/
1
1
0
0
0
/
0
1
0
0
1
/
0
0
1
0
1
/
0
1
1
1
1
Розглянемо матриці для окремих випадків відношень в Х. Матриця повного відношення – це квадратна матриця, що складається лише з одиниць; матриця тотожного (діагонального) відношення – це квадратна матриця, яка складається з нулів та одиниць на головній діагоналі; матриця порожнього відношення – це квадратна матриця, що складається лише з нулів.
1. Об’єднання відношень / і /:
/.
2. Переріз відношень / і /:
/.
3. Різниця відношень / і /:
/.
4. Диз’юнктивна сума відношень / і /:
/.
5. Доповнення відношення /:
/.
Крім того, виділяються специфічні для відношень операції: обернення (симетризація) і композиція.
Приклад 3.8. Нехай відношення «бути матір’ю дочки» визначене на деякій множині жінок /{(Оксана, Наталя), (Олена, Надія), (Олена, Ольга), (Катерина, Галина)}. Відношення / «бути матір’ю сина» задано парами Q2 = {(Оксана, Олег), (Олена, Андрій), (Катерина, Сергій)}.
Відношення / є відношенням «бути матір’ю», пари цього відношення визначають всіх матерів, які мають дочок або синів.
Відношення /, тобто не є змістовним.
Відношення /, /.
Відношення /.
Означення 3.3. Відношення, симетричне (обернене) деякому відношенню /, є підмножиною множини /, утвореною тими парами /, для яких /. Відношення симетричне до / позначається /.
Із попереднього зрозуміло, що перехід від / до / здійснюється взаємною перестановкою координат кожної впорядкованої пари. Наприклад, відношення / – « /дільник /» має обернене до нього / – « /кратне /». Для наведеного вище у прикладі 3.3 відношення / обернене відношення /.
Відношення, обернене відношенню / – це відношення /{(Наталя, Оксана), (Надія, Олена), (Ольга, Олена), (Галина, Катерина)} – «бути дочкою».
Відношення, обернене відношенню / – це відношення «бути сином», яке складається з пар /{(Олег, Оксана), (Андрій, Олена), (Сергій, Катерина)}.
Слід зазначити, що при переході від / до / область визначення стає областю значень і навпаки. Матриця / – це транспонована матриця відношення /. Граф оберненого відношення / утворюється із графа відношення / заміною всіх дуг на протилежні.
3.1.3. Композиція відношень.
Нехай надано три множини /, /, /та два відношення /, /.
Означення 3.4. Композицією відношень / і / є відношення /, що складається з усіх тих пар /, для яких існує таке /, що / й /. Будемо позначати композицію відношень символом o, а саме
/.
Схематично утворення композиції наведено на рис.3.8.
/
Рис.3.8
Можна легко показати, що переріз відношення / за / збігається з перерізом відношення / за підмножиною /, тобто /.
Приклад 3.9. Розглянемо композицію відношення / з прикладу 3.4, а саме / з відношенням /. Це / / /. Візьмемо переріз відношення / за /: /. З іншого боку, маємо /.
Приклад 3.10. Розглянемо композицію відношення /, яке діє з множини /{Оксана, Олена, Катерина} в множину /{(Наталя, Надія, Ольга, Галина)} з відношенням «бути матір’ю дочки» /{(Наталя, Зоряна), (Наталя, Сніжана), (Надія, Юлія), (Ольга, Богдана), (Ольга, Світлана), (Галина, Олена)}, яке діє з множини / в множину /{(Зоряна, Сніжана, Юлія, Богдана, Світлана, Алла)}. Це відношення /{(Оксана, Зоряна), (Оксана, Сніжана), (Олена, Юлія), (Олена, Богдана), (Олена, Світлана), (Катерина, Алла)}, яке є відношенням «бути бабусею онучки» і діє з множини / в множину /.
Приклад 3.11. Розглянемо композицію відношення / з відношенням «бути матір’ю сина» /{(Надія, Олексій), (Галина, Богдан)}, яке діє з множини / в множину /{Олексій, Богдан}. Це відношення /{(Олена, Олексій), (Катерина, Богдан)}, яке є відношенням «бути бабусею онука». Візьмемо перерізи відношення / за всіма елементами множини /:
/ (Оксана) = {Зоряна, Сніжана} – перелічені онучки Оксани;
/ (Олена) = {Юлія, Богдана} – онучки Олени;
/ (Катерина) = {Алла} – онучка Катерини.
Фактор-множина / – це множина {Зоряна, Сніжана, Юлія, Богдана, Алла} – множина онучок всіх жінок з множини /.
Візьмемо перерізи відношення / за всіма елементами множини /:
/ (Оксана) = {Олексій};
/ (Олена) = {Богдан};
/ (Катерина) = /.
Фактор-множина / – це множина {Олексій, Богдан} – множина онуків всіх жінок з множини /.
Щодо властивостей композиції можна зазначити таке:
1. /, тобто не виконується закон комутативності;
2. /, тобто виконується закон асоціативності;
3. /.
Перші дві властивості очевидні, третю проілюструємо на наведеному прикладі відношень / і /.
Приклад 3.12. Відношення /{(Зоряна, Оксана), (Сніжана, Оксана), (Юлія, Олена), (Богдана, Олена), (Світлана, Олена), (Алла, Катерина)}, яке є відношенням «бути онучкою бабусі» діє з множини / в множину /.
Відношення / ми вже знаходили. Це /{(Наталя, Оксана), (Надія, Олена), (Ольга, Олена), (Галина, Катерина)} і воно діє з множини / в множину /.
Знайдемо обернене відношення до /.
/{(Зоряна, Наталя), (Сніжана, Наталя), (Юлія, Надія), (Богдана, Ольга), (Світлана, Ольга), (Алла, Галина)} і це відношення діє з множини / в множину /.
Знайдемо композицію відношень /{(Зоряна, Оксана), (Сніжана, Оксана), (Юлія, Олена), (Богдана, Олена), (Світлана, Олена), (Алла, Катерина)}. Як ви бачите, відношення / і відношення / збігаються.
3.1.4. Подання композиції відношень матрицями.
Твердження 3.1. Матриця композиції відношень / утворюється як добуток матриць відношень / й / з подальшою заміною відмінних від нуля елементів одиницями.
Справді, елемент / матриці композиції знайдемо як суму добутків відповідних елементів матриць / та / (відповідно до правила множення матриць):
/.
Очевидно, така сума відмінна від нуля тоді й тільки тоді, коли хоча б один доданок відмінний від нуля, тобто дорівнює одиниці:
/.
Якщо у виразі / не один, а кілька одиничних доданків, то кожен з них відповідає одному й тому самому співвідношенню /, через що їх сума має бути замінена одиницею.
Приклад 3.13. Для композиції відношень / та / із прикладу 3.9 матриця утворюється так:
/.
Побудуємо матрицю композиції / для прикладу 3.10.
/.
Пропонуємо читачеві самостійно впевнитися, що отримана матриця повністю відповідає відношенню / з прикладу 3.10.
3.1.5. Властивості відношень.
Нехай / – бінарне відношення у множині / ( /).
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора