![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Завдання множин здійснюється трьома основними способами:
1. Приклад: Перерахування всіх елементів, що входять у множину.
Приклад. А={а1, а2, а3 }, B={1, 2, b, c}, C={аі}1 3
2. Завданням характеристичної властивості, що виділяє елементи даної множини серед елементів, що зазначені іншим множинам.
Приклад. N={n|nÎZ і n>0}, М={mÎM|m=n2 і nÎN}
3. Описом процедури, що породжує, із зазначенням множин, що пробігають параметри цієї процедури.
Приклад. М={n2|nÎN}, C ={8х1+14х2+32х3|х1, х2, х3ÎZ}.
З визначення рівності множин і способів завдання їх випливає, що порядок елементів у множинах несуттєвий.
Для інтерпретації множин і операцій над ними використовуються геометричні фігури - кола Ейлера і діаграми Венна (рис. 1.1.).
Рис. 1.1. Кола Ейлера
1.2. Операції над множинами. Формули. Тотожності
Нові множини породжуються в результаті застосування операцій до існуючих множин.
Об'єднанням множин М1 і М2 називається множина М1ÈM2={m|mÎM1 чи mÎM2}.
Перетином множин М1 і М2 називається множина М1ÇM2={m|mÎM1 і mÎM2}.
Множини М1 і М2 називаються диз'юнктними, якщо М1 ÇM2=Æ.
Різниця множин М1 і М2 - це множина М1\М2={m|mÎM1 і mÏM2}.
Симетричною різницею множин М1 і М2 називається множина
М1-М2= {m|mÎM1\M2 чи mÎМ2\М1}.
Якщо М1ÍM2, то різниця М2\М1 називається доповненням
множини М1 у множині М2. Зокрема, ` М = U\M - доповнення множини М в універсумі чи просто доповнення множини М. Інше позначення доповнення множини - ùМ.
Приклад. A={1,2, 3, 4}; B={3, 4 5}; З ={1, 3}; AÈB={1, 2, 3, 4, 5}; AÇB={3, 4}; A\З ={2, 4}; A\B={1, 2}; B\A={5}; A-B={1,2,5}.
Теорема. Будь-які дві множини А і В можуть знаходитися в одному з п'яти станів: 1)А=В; 2)АÌВ; 3)АÉВ; 4)АÇВ=Æ; 5)А\В ¹Æ і В\А¹Æ і АÇВ¹Æ
Завдання нових множин за допомогою ідентифікаторів, операцій і дужок, тобто завдання за допомогою формул називається аналітичним.
Для операцій над множинами справедливі закони (тотожності):
1. AÈB=BÈA; AÇB=BÇA; комутативність
2. AÈ(BÈЗ)=(AÈB)ÈЗ; AÇ(BÇЗ)=(AÇB)ÇC; асоціативність
3. AÈ(BÇC)=(AÈB)Ç(AÈC); AÇ(BÈC)=(AÇB)È(AÇC);
дистрибутивність
4. AÈÆ=A; AÈU=U;
AÇÆ=Æ; AÇU=A;
`Æ=U; `U=Æ; властивості границь
5. AÈ`A=U; AÇ`A=Æ; доповнення
6. AÈA=A; AÇA=A; ідемпотентність
7. AÈ(AÇB)=A; AÇ(AÈB)=A; поглинання
8. AÈ(`AÇB)=AÈB; AÇ(`AÈB)=AÇB;
(AÇC)È(BÇ`C)=(AÇC)È(BÇ`C)È(AÇB);
(AÈC)Ç(BÈ`C)=(AÈC)Ç(BÈ`C)Ç(AÈB) Блейка-Порецького
9. (AÇB)È(`AÇB)=B; (AÈB)Ç(`AÈB)=B склеювання
10. ù(AÇB)=`AÈ`B; ù(AÈB)=`AÇ`B; деМоргана
11. Якщо АÈB=U і AÇB=Æ то A=`B
12. ù ùA=A; інволютивність
13. A\B=AÇ`B
14. A-B=B-A; комутативність
15. A-(B-C)=(A-B)-C; асоціативність
16. A-Æ=Æ-A=A; A-U=U-А=`A; властивості границь
17. AÍB, якщо і тільки якщо АÈB=B і AÇB=A і AÇ`B=Æ
18. A=B, якщо і тільки якщо A-B=.
1.3. Доведеннятотожностей. Булева алгебра множин
Для доведення тотожностей використовується універсальний метод, в основу якого покладене визначення рівності (еквівалентності) двох множин. Кожне з доведень складається з послідовності тверджень вигляду “якщо Р, то Q”, записується як “PÞQ” і що читаються як “з R випливає Q”. Отже, якщо існує послідовність тверджень Р, Р1, Р2, Р3,..., Рn, Q така, що з Р випливає Р1, з Р1 випливає Р2,…з Рn випливає Q, то існує доведення, що “з Р випливає Q”, тобто RÞQ.
Приклад. D=AÇ(BÈС) = (AÇB)È(AÇС)=E
а) Доведемо, що DÍE. Якщо dÎD, то dÎA і dÎ(BÈC), чи отже, (dÎA і dÎB), чи (dÎA і dÎC). Це значить, що dÎAÇB чи dÎAÇC), тобто dÎ(AÇB)È(AÇC), що записується як dÎE. Тобто, DÍE.
б) Доведемо, що ЕÍD. Якщо еÎE то еÎ((AÇB) чи (AÇС)), отже еÎA і еÎB) чи еÎA і еÎC. Це значить, що еÎA і еÎ(BÈC) тобто еÎD. Тобто, ЕÍD. Отже, D=Е.
Для доведення тотожностей можуть бути використані доведені раніше тотожності.
Приклад. AÈ(AÇB)=A; AÈ(AÇB) = (AÇU)È(AÇB) = AÇ(UÈB) =
= AÇU = A.
Для кожної множини М, булеан У(М) замкнутий щодо операцій È,Ç,\,-,ù, тобто для всяких М1, М2ÎB(M) множини, одержувані в результаті виконання операцій М1ÈM2, M1ÇM2, M1\M2, M2\M1,, M1-M2, `M1,`M2 є елементами булеана В(М).
Булеан B(М) разом з (булевими) операціями на ньому утворюють так звану (булеву) алгебру множин. Кожна підмножина M’ булеана В(М) замкнута відносно (булевих) операцій, містить як множини, що є підмножинами кожної множини з M’, так і множини, що містять як підмножини кожну множину з M’. Таким чином, M’ з (булевими) операціями також виявляється (булевою) алгеброю.
1.4. Узагальнення операцій. Подвійність
Завдякі властивості асоціативності об'єднання, Перетин і симетрична різниця довільних сімей множин можуть бути записані без пріоритетних дужок.
1. М1ÈM2ȼÈМn=È{Мі|1£ і £ n}={m| існує і, де 1£і£n, таке, що mÎMі}.
2. М1ÇM2ǼÇMn=Ç{Mі|1£ і £ n}={m| для кожного і., де 1£ і£n, виконане mÎMі}.
3. М1-M2-¼-Mn=-{Mі|1 £ і £ n }={m| існує і єдино і, де 1£і£n, таке, що mÎMі}.
Ці визначення узагальнюються на випадок, коли множини Мі задані як елементи деякої сім'ї множин М и потрібно виконання деякої додаткової умови В:
È{Mі|MіÎM і Мі задовольняє умову В}.
Приклад. È{Mі|MіÎB(Z) і MіÇN0=Æ} - множина усіх від'ємних цілих чисел.
Замість È{Mі|іÎN} використовується запис ÈMі. Аналогічно - для ¢¢Ç¢¢ і ¢¢-¢¢.
Перші вісім тотожностей представлені парами подвійних (дуальних) співвідношень, одне з яких виходить заміною в іншому символів “È” на “Ç” і “Ç” на “È”, а також Æ на U і U на Æ. Відповідні пари символів È, Ç і Æ, U називаються подвійними (дуальними).
Принцип подвійності: При заміні в будь-якій теоремі (тотожності, формулі) вхідних у неї символів дуальними одержимо новий вираз, що також є теоремою (тотожністю, формулою).
Тотожності 9, 11 не змінюються при заміні символів дуальними і називаються самоподвійними. Принцип подвійності поширюється на “\”, -, а також на вираження, що включають знаки “Ì” і ”É”, які при переході до дуальних виражень заміняються на знаки відповідно “É” і “Ì”.
Різні вираження алгебри множин можна спрощувати чи перетворювати до зручного вигляду за допомогою тотожних перетворень, тобто послідовності застосувань відповідних властивостей (тотожностей) операцій над множинами.
Контрольні запитання
1. Що є множина, фактор-множина, порожня множина і універсум?
2. Які способи завдання множин існують?
3. Які операції діють над множинами?
4. Як можуть співвідноситися дві множини?
5. Які тотожності для операцій над множинами існують?
6. Які способи доведення тотожностей існують?
7. Для яких операцій можливе узагальнення і яке саме?
8. У чому полягає принцип подвійності?
Спісок літератури:
Дата публикования: 2014-11-18; Прочитано: 1619 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!