Симетрична різниця множин

Матеріал з Вікіпедії — вільної енциклопедії.

В математиці та теорії множин, симетричною різницею двох множин є така множина елементів, які містяться в одній з цих двох множин, але не в обох.

Симетрична різниця множин A та B позначається як AΔB.

Наприклад, симетрична різниця множин {1,2,3} та {3,4} є {1,2,4}. Симетрична різниця множини усіх студентів та усіх особ жіночої статі, містить множину усіх студентів-чоловіків та усіх жінок, які не є студентами.

Між симетричною різницею та об'єднанням множин такий зв'язок:

A Δ B = (A − B) ∪(B − A)

Зв'язок з операцією перетину множин такий:

A Δ B = (A ∪B) − (A ∩B)

Мовою математичної логіки:

A Δ B = { x : (x ∈A) ⊕ (x ∈B) }.

Тут ⊕ -- логічна функція заперечення тотожності.

Симетрична різниця є комутативною та асоціативною:

A Δ B = B Δ A

(A Δ B) Δ C = A Δ (B Δ C)

Порожня множина є нейтральним елементом, і кожна множина є зворотним елементом до самої себе відносно цієї операції:

A Δ Ø = A

A Δ A = Ø

Перетин множин є дистрибутивним відносно симетричної різниці:

A ∩(B Δ C) = (A ∩B) Δ (A ∩C)

В булевій алгебрі симетрична різниця може бути визначеною наступним чином:

x Δ y = (x ∨ y) ∧ ¬(x ∧ y) = (x ∧ ¬y) ∨ (y ∧ ¬x)