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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

З точки зору абстрактної алгебри алгебра множин — це кільце K підмножин множини R, що містить R.

Властивості операцій на множинах[ред.ред. код]

Бінарні операції об'єднання та перетину множин, задовольняють певним фундаментальним алгебраїчним властивостям. Далі вони наводяться без доведення.

ТВЕРДЖЕННЯ 1: Для будь-яких множин A, B, та C, виконуються такі співвідношення:

комутативність:
  • AB  =  BA
  • AB  =  BA
асоціативність:
  • (AB) ∪C  =  A ∪(BC)
  • (AB) ∩C  =  A ∩(BC)
дистрибутивність операції перетину відносно об'єднання:
  • A ∪(BC)  =  (AB) ∩(AC)
  • A ∩(BC)  =  (AB) ∪(AC)

Як можна спостерігати з наведених співвідношень, з точки зору основних властивостей можна провести певну аналогію між операцією об'єднання множин та операцією множення чисел, операцією перетину множин та операцією додавання чисел. Ця аналогія розвивається в наступному твердженні:

ТВЕРДЖЕННЯ 2: Для будь-якої підмножини A універсальної множини U, справедливі наступні співвідношення:

  • властивості нуля
  • A ∪Ø  =  A
  • A ∩CA  =  Ø
  • властивості одиниці
  • AU  =  A
  • A ∪СA  =  U

Тут елементи Ø та U є нейтральними елементами відносно операцій ∪ та ∩ відповідно, тобто такими, що не впливають на результат операції, аналогічно тому, як в звичайній алгебрі дійсних чисел такими елементами на операціях множення та складання є 1 та 0 відповідно. Але, на відміну від звичайного множення та складання, в алгебрі операцій перетину та об'єднання множин не існує зворотного елементу.

Наведені закони складають основу алгебри множин. Всі інші співвідношення можуть бути виведені з них безпосередньо.

Принцип дуальності[ред.ред. код]

Наведені вище співвідношення демонструють цікаву закономірність. Якщо в якомусь з законів провести заміни ∪ на ∩, а також Ø на U, то він залишиться справедливим. Це фундаментальна властивість алгебри множин, яка має назву принципа дуальності.......

Додаткові співвідношення алгебри множин[ред.ред. код]

ТВЕРДЖЕННЯ 3: Для будь-яких підмножин A та B універсальної множини U, справедливі наступні твердження:

ідемпотентність:
  • AA  =  A
  • AA  =  A
домінування:
  • AU  =  U
  • A ∩Ø  =  Ø
поглинання:
  • A ∪(AB)  =  A
  • A ∩(AB)  =  A

ТВЕРДЖЕННЯ 4: Нехай A та B — підмножини універсуму U, тоді:

правила де Моргана:
  • С(AB)  =  CA∩CB
  • C(AB)  =  CA∪CB
  • CCA  =  A
  • CØ  =  U
  • CU  =  Ø

ТВЕРДЖЕННЯ 5: Нехай A та B — підмножини універсуму U, тоді:

однозначність доповнення:
  • Якщо AB  =  U, та AB  =  Ø тоді 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 ⊆ AB
  • Якщо A ⊆ C та B ⊆ C то AB ⊆ C
  • AB ⊆ A
  • Якщо C ⊆ A та C ⊆ B то C ⊆ AB

ТВЕРДЖЕННЯ 8: Для будь-яких множин A та B, наступні твердження еквівалентні:

  • A ⊆ B
  • AB  =  A
  • AB  =  B
  • A − B  =  Ø
  • BC ⊆ AC

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

ТВЕРДЖЕННЯ 9: Для універсальної множини U та підмножин A, B, та C з U, справедливе наступне:

  • C − (AB)  =  (C − A) ∪(CB)
  • C − (AB)  =  (C − A) ∩(CB)
  • C − (B − A)  =  (AC) ∪(C − B)
  • (B − A) ∩C  =  (BC) − A  =  B ∩(C − A)
  • (B − A) ∪C  =  (BC) − (A − C)
  • A − A  =  Ø
  • Ø − A  =  Ø
  • A − Ø  =  A
  • B − A  =  ACB
  • (B − A)C  =  ABC
  • U − A  =  AC
  • A − U  =  Ø

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