Алгебра множин

Алгебра множин — розділ теорії множин, який визначає закони композиції множин, виходячи з основних властивостей операцій над ними, а також пропонує певну систематичну процедуру для обчислення теоретико-множинних рівнянь та співвідношень.^{[джерело?]}

З точки зору абстрактної алгебри алгебра множин — це кільце 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 ∩C_A = Ø

властивості одиниці

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) = C_A∩C_B
C_(A∩B) = C_A∪C_B
CC_A = A
C_Ø = U
C_U = Ø

ТВЕРДЖЕННЯ 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 = Ø
B^C ⊆ A^C

Алгебра доповнень ред.

ТВЕРДЖЕННЯ 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 = A^C ∩B
(B − A)^C = A ∪B^C
U − A = A^C
A − U = Ø

Див. також ред.

Література ред.

Енциклопедія кібернетики, т. 1, с. 70.