Алгебра множин — розділ теорії множин, який визначає закони композиції множин, виходячи з основних властивостей операцій над ними, а також пропонує певну систематичну процедуру для обчислення теоретико-множинних рівнянь та співвідношень.[]
З точки зору абстрактної алгебри алгебра множин — це кільце K підмножин множини R, що містить R.
Властивості операцій на множинах
Бінарні операції об'єднання та перетину множин, задовольняють певним фундаментальним алгебраїчним властивостям. Далі вони наводяться без доведення.
ТВЕРДЖЕННЯ 1: Для будь-яких множин A, B, та C, виконуються такі співвідношення:
- комутативність:
- A ∪B = B ∪A
- A ∩B = B ∩A
- асоціативність:
- (A ∪B) ∪C = A ∪(B ∪C)
- (A ∩B) ∩C = A ∩(B ∩C)
- дистрибутивність операції перетину відносно об'єднання:
- A ∪(B ∩C) = (A ∪B) ∩(A ∪C)
- A ∩(B ∪C) = (A ∩B) ∪(A ∩C)
Як можна спостерігати з наведених співвідношень, з точки зору основних властивостей можна провести певну аналогію між операцією об'єднання множин та операцією множення чисел, операцією перетину множин та операцією додавання чисел. Ця аналогія розвивається в наступному твердженні:
ТВЕРДЖЕННЯ 2: Для будь-якої підмножини A універсальної множини U, справедливі наступні співвідношення:
- властивості нуля
- A ∪Ø = A
- A ∩CA = Ø
- властивості одиниці
- A ∩U = A
- A ∪СA = U
Тут елементи Ø та U є нейтральними елементами відносно операцій ∪ та ∩ відповідно, тобто такими, що не впливають на результат операції, аналогічно тому, як в звичайній алгебрі дійсних чисел такими елементами на операціях множення та складання є 1 та 0 відповідно. Але, на відміну від звичайного множення та складання, в алгебрі операцій перетину та об'єднання множин не існує зворотного елементу.
Наведені закони складають основу алгебри множин. Всі інші співвідношення можуть бути виведені з них безпосередньо.
Принцип дуальності
Наведені вище співвідношення демонструють цікаву закономірність. Якщо в якомусь з законів провести заміни ∪ на ∩, а також Ø на U, то він залишиться справедливим. Це фундаментальна властивість алгебри множин, яка має назву принципа дуальності.......
Додаткові співвідношення алгебри множин
ТВЕРДЖЕННЯ 3: Для будь-яких підмножин A та B універсальної множини U, справедливі наступні твердження:
- ідемпотентність:
- A ∪A = A
- A ∩A = A
- домінування:
- A ∪U = U
- A ∩Ø = Ø
- поглинання:
- A ∪(A ∩B) = A
- A ∩(A ∪B) = A
ТВЕРДЖЕННЯ 4: Нехай A та B — підмножини універсуму U, тоді:
- правила де Моргана:
- С(A∪B) = CA∩CB
- C(A∩B) = CA∪CB
- CCA = A
- CØ = U
- CU = Ø
ТВЕРДЖЕННЯ 5: Нехай A та B — підмножини універсуму U, тоді:
- однозначність доповнення:
- Якщо A ∪B = U, та A ∩B = Ø тоді B = СA.
Часткова впорядкованість
На множині X можна ввести відношення порядку ⊆, яке задовольняє наступним властивостям:
ТВЕРДЖЕННЯ 6: Якщо A, B та C — деякі множини, то:
- рефлексивність:
- A ⊆ A
- антисиметричність:
- A ⊆ B та B ⊆ A тоді й тільки тоді, якщо A = B
- транзитивність:
- If A ⊆ B та B ⊆ C тоді A ⊆ C
Це твердження говорить про те, що множина X є алгебраїчною структурою, або решіткою, і якщо вона дистрибутивна (що показано в твердженні 1) та для кожного елементу існує його доповнення, то така структура має назву булевої алгебри (таке визначення булевої алгебри не є математично строгим, докладніше дивись в статті Булева алгебра).
ТВЕРДЖЕННЯ 7: Якщо A, B та C — підмножини S, то виконується наступне:
- Ø ⊆ A ⊆ S
- A ⊆ A ∪B
- Якщо A ⊆ C та B ⊆ C то A ∪B ⊆ C
- A ∩B ⊆ A
- Якщо C ⊆ A та C ⊆ B то C ⊆ A ∩B
ТВЕРДЖЕННЯ 8: Для будь-яких множин A та B, наступні твердження еквівалентні:
- A ⊆ B
- A ∩B = A
- A ∪B = B
- A − B = Ø
- BC ⊆ AC
Алгебра доповнень
ТВЕРДЖЕННЯ 9: Для універсальної множини U та підмножин A, B, та C з U, справедливе наступне:
- C − (A ∩B) = (C − A) ∪(C − B)
- C − (A ∪B) = (C − A) ∩(C − B)
- C − (B − A) = (A ∩C) ∪(C − B)
- (B − A) ∩C = (B ∩C) − A = B ∩(C − A)
- (B − A) ∪C = (B ∪C) − (A − C)
- A − A = Ø
- Ø − A = Ø
- A − Ø = A
- B − A = AC ∩B
- (B − A)C = A ∪BC
- U − A = AC
- A − U = Ø
Див. також
Література
- Енциклопедія кібернетики, т. 1, с. 70.
- Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teoretiko mnozhinni operaciyi A displaystyle overline A dopovnennya A B displaystyle A cup B ob yednannya A B displaystyle A cap B peretin A B displaystyle A setminus B riznicya A B displaystyle A triangle B simetrichna riznicya A B displaystyle A times B dekartiv dobutok Algebra mnozhin rozdil teoriyi mnozhin yakij viznachaye zakoni kompoziciyi mnozhin vihodyachi z osnovnih vlastivostej operacij nad nimi a takozh proponuye pevnu sistematichnu proceduru dlya obchislennya teoretiko mnozhinnih rivnyan ta spivvidnoshen dzherelo Z tochki zoru abstraktnoyi algebri algebra mnozhin ce kilce K pidmnozhin mnozhini R sho mistit R Vlastivosti operacij na mnozhinahBinarni operaciyi ob yednannya ta peretinu mnozhin zadovolnyayut pevnim fundamentalnim algebrayichnim vlastivostyam Dali voni navodyatsya bez dovedennya TVERDZhENNYa 1 Dlya bud yakih mnozhin A B ta C vikonuyutsya taki spivvidnoshennya komutativnist A B B A A B B A dd asociativnist A B C A B C A B C A B C dd distributivnist operaciyi peretinu vidnosno ob yednannya A B C A B A C A B C A B A C dd Yak mozhna sposterigati z navedenih spivvidnoshen z tochki zoru osnovnih vlastivostej mozhna provesti pevnu analogiyu mizh operaciyeyu ob yednannya mnozhin ta operaciyeyu mnozhennya chisel operaciyeyu peretinu mnozhin ta operaciyeyu dodavannya chisel Cya analogiya rozvivayetsya v nastupnomu tverdzhenni TVERDZhENNYa 2 Dlya bud yakoyi pidmnozhini A universalnoyi mnozhini U spravedlivi nastupni spivvidnoshennya vlastivosti nulya A O A A CA O dd vlastivosti odinici A U A A SA U dd Tut elementi O ta U ye nejtralnimi elementami vidnosno operacij ta vidpovidno tobto takimi sho ne vplivayut na rezultat operaciyi analogichno tomu yak v zvichajnij algebri dijsnih chisel takimi elementami na operaciyah mnozhennya ta skladannya ye 1 ta 0 vidpovidno Ale na vidminu vid zvichajnogo mnozhennya ta skladannya v algebri operacij peretinu ta ob yednannya mnozhin ne isnuye zvorotnogo elementu Navedeni zakoni skladayut osnovu algebri mnozhin Vsi inshi spivvidnoshennya mozhut buti vivedeni z nih bezposeredno Princip dualnostiNavedeni vishe spivvidnoshennya demonstruyut cikavu zakonomirnist Yaksho v yakomus z zakoniv provesti zamini na a takozh O na U to vin zalishitsya spravedlivim Ce fundamentalna vlastivist algebri mnozhin yaka maye nazvu principa dualnosti Dodatkovi spivvidnoshennya algebri mnozhinTVERDZhENNYa 3 Dlya bud yakih pidmnozhin A ta B universalnoyi mnozhini U spravedlivi nastupni tverdzhennya idempotentnist A A A A A A dd dominuvannya A U U A O O dd poglinannya A A B A A A B A dd TVERDZhENNYa 4 Nehaj A ta B pidmnozhini universumu U todi pravila de Morgana S A B CA CB C A B CA CB CCA A CO U CU O dd TVERDZhENNYa 5 Nehaj A ta B pidmnozhini universumu U todi odnoznachnist dopovnennya Yaksho A B U ta A B O todi B SA dd Chastkova vporyadkovanistNa mnozhini X mozhna vvesti vidnoshennya poryadku yake zadovolnyaye nastupnim vlastivostyam TVERDZhENNYa 6 Yaksho A B ta C deyaki mnozhini to refleksivnist A A dd antisimetrichnist A B ta B A todi j tilki todi yaksho A B dd tranzitivnist If A B ta B C todi A C dd Ce tverdzhennya govorit pro te sho mnozhina X ye algebrayichnoyu strukturoyu abo reshitkoyu i yaksho vona distributivna sho pokazano v tverdzhenni 1 ta dlya kozhnogo elementu isnuye jogo dopovnennya to taka struktura maye nazvu bulevoyi algebri take viznachennya bulevoyi algebri ne ye matematichno strogim dokladnishe divis v statti Buleva algebra TVERDZhENNYa 7 Yaksho A B ta C pidmnozhini S to vikonuyetsya nastupne O A S A A B Yaksho A C ta B C to A B C A B A Yaksho C A ta C B to C A B dd TVERDZhENNYa 8 Dlya bud yakih mnozhin A ta B nastupni tverdzhennya ekvivalentni A B A B A A B B A B O BC ACAlgebra dopovnenTVERDZhENNYa 9 Dlya universalnoyi mnozhini U ta pidmnozhin A B ta C z U spravedlive nastupne C A B C A C B C A B C A C B C B A A C C B B A C B C A B C A B A C B C A C A A O O A O A O A B A AC B B A C A BC U A AC A U ODiv takozhSigma algebra Teoriya mnozhinLiteraturaEnciklopediya kibernetiki t 1 s 70 Kuratovskij K Mostovskij A Teoriya mnozhestv Set Theory Teoria mnogosci M Mir 1970 416 s ros