Властивості операцій над множинами

Теорема 1. Для будь-яких підмножин А, В, С універсальної множини U наведені нижче рівності є тотожностями (вираз А ' слід розуміти як U \ А):

1) А È(В È С)=(А È В)È С, 1') А Ç(В Ç С)=(А Ç В)Ç С,

2) А È В = В È А, 2') А Ç В = В Ç А,

3) А È(В Ç С)=(А È В)Ç(А È С), 3') А Ç(В È С)=(А Ç В)È(А Ç С),

4) А ÈÆ= А, 4') А Ç U = А,

5) А È А '= U, 5') А Ç А '=Æ.

Довести тотожності можна використовуючи означення рівності множин, тобто показавши для кожної з даних рівностей, що множина ліворуч від знака «=» включається у множину праворуч від знака «=» й навпаки. Доведемо таким способом тотожність 3. Спочатку доведемо, що

А È(В Ç С)Í(А È В)Ç(А È С). (*)

Нехай х Î А È(В Ç С). Тоді, згідно з визначенням операції об’єднання множин, х Î А або х Î В Ç С. Розглянемо два випадки: х Î А та х Î В Ç С. Якщо в кожному з них ми покажемо, що х Î(А È В)Ç(А È С), то твердження (*) буде доведено. Отже, перший випадок: х Î А. З визначення операції об’єднання множин випливає, що коли деякий об’єкт є елементом деякої множини Х, то він є елементом множини Х È Y, де Y – довільна множина. Таким чином, з х Î А випливає: х Î А È В та х Î А È С. Згідно з визначенням операції перетину множин це означає, що х Î(А È В)Ç(А È С). Розглянемо другий випадок: х Î В Ç С. З визначення операції Ç випливає, що х Î В та х Î С. Але тоді та х Î АÈВ та х Î А È С. Згідно з визначенням операції перетину множин це означає, що х Î(А È В)Ç(А È С).Отже, твердження (*) доведено.

Тепер доведемо, що

(А È В)Ç(А È С)Í А È(В Ç С) (**)

Нехай х Î(А È В)Ç(А È С). Згідно з визначенням операції перетину множин маємо: х Î(А È В) та х Î(А È С). Використовуючи визначення операції об’єднання множин, маємо: х Î А або х Î В, а разом з тим х Î А або х Î С. Отже, можливі такі випадки: а) х Î А, б) х Î А й х Î С, в) х Î В й х Î А, г) х Î В й х Î С. У випадках а), б) та в), оскільки х Î А, то х належить й множині, що є об’єднанням множини А з довільною множиною, отже, х Î А È(В Ç С). У випадку г) можна зробити висновок, що х Î В Ç С, але тоді х Î А È(В Ç С). Таким чином, у кожному з випадків а), б), в), г) ми показали, що х Î А È(В Ç С), отже, включення (**) доведено й тим самим завершено доведення тотожності 3.

Інші наведені вище тотожності теж можна довести виходячи з визначення рівності множин.

Тотожності 1 та 1' називаються законами асоціативності, відповідно, для операцій об’єднання та перетину множин, тотожності 2 та 2' – законами комутативності для цих операцій, тотожності 3 та 3' – законами дистрибутивності для цих операцій.

Відповідно до закону асоціативності (тотожність 1), дві множини, котрі можна утворити за допомогою операції об’єднання з множин А, В й С, узятих у певному порядку, рівні. Домовимося позначати таку єдину множину через А È В È С. Закон асоціативності стверджує, що порядок розміщення дужок у цьому виразі не є суттєвим. Можна узагальнити цей результат, тобто показати, що усі множини, які можна побудувати із заданих множин А ₁, А ₂,…, А_n, узятих у зазначеному порядку, є рівними. Множину, яка утворюється таким способом з А ₁, А ₂,…, А_n, позначатимемо через А ₁È А ₂È…È А_n. Відповідне узагальнення можна зробити й для операції перетину. Такі загальні закони асоціативності дають змогу установити загальні закони комутативності: якщо 1',2',…, n ' – це числа 1,2,…, n, узяті у довільному порядку, то

А ₁È А ₂È…È А_n = А _1'È А _2'È…È А_{n '},

А ₁Ç А ₂Ç…Ç А_n = А _1'Ç А _2'Ç…Ç А_{n '}.

Можна узагальнити й закони дистрибутивності:

А È(В ₁Ç В ₂Ç…Ç В_n)=(А È В ₁)Ç(А È В ₂)Ç…Ç(А È В_n),

А Ç(В ₁È В ₂È…È В_n)=(А Ç В ₁)È(А Ç В ₂)È…È(А Ç В_n).

Зауважимо, що у теоремі 1 властивості операцій над множинами зібрані попарно таким чином, що кожен член будь-якої пари утворюється з іншого члена одночасною заміною È на Ç, Æ на U. Така рівність (або вираз), що утворюється з іншої рівності (або виразу) заміною усіх входжень È на Ç, Ç на È, Æ на U та U на Æ, називається двоїстою (двоїстим) до даної (до даного).

Зазначимо, що коли твердження Q двоїсте до істинного твердження Т, що сформульовано у термінах È, Ç та ', причому для доведення твердження Т досить лише тотожностей 1-5 та 1'-5', то Q також є істинним. Дійсно, вважаючи, що Т складається з посилок (умов) та висновку, припустимо, що доведення твердження Т подано у вигляді послідовності кроків, а поруч з кожним кроком записано його обґрунтування. За припущенням кожне таке обґрунтування є однією з тотожностей 1-5, 1'-5' або умовою твердження Т. Замінимо кожну тотожність (співвідношення), що зустрічається у доведенні та обґрунтуванні, на двоїсту (двоїсте) до неї (до нього). Оскільки тотожність, двоїста до кожної з тотожностей 1-5, 1'-5', також є однією з цих тотожностей, а твердження, двоїсте до посилки твердження Т, є посилкою твердження Q, результат заміни кожного кроку обґрунтування у доведенні твердження Т може служити обґрунтуванням відповідного кроку нової послідовності, яка, таким чином, буде доведенням. Отже, останній рядок нової послідовності є висновком твердження Q, двоїстим до висновку твердження Т.

Теорема 2. Для будь-яких підмножин А й В універсальної множини U наведені нижче рівності є тотожностями (вираз А ' слід розуміти як U \ А):

6) Якщо для усіх А А È В = А, 6') Якщо для усіх А А Ç В = А,

то В =Æ, то В = U,

7) Якщо А È В = U та А Ç В =Æ, то В = А ',

8) (А ')'= А,

9) Æ'= U, 9') U '=Æ,

10) А È А = А, 10') A Ç A = A,

11) A È U = U, 11') A ÇÆ=Æ,

12) A È(A Ç B)= A, 12') A Ç(A È B)= A,

13) (A È B)'= A 'Ç B ', 13') (A Ç B)'= A 'È B '.

Тотожності теореми 2 можна довести виходячи з визначення рівності множин, а також як наслідки тотожностей теореми 1.

Деякі з тотожностей теореми 2 мають спеціальні назви. Так, 10 та 10' – це закони ідемпотентності, 12 та 12' – закони поглинання, 13 та 13' – закони де Моргана.

Теорема 3. Для довільних множин А та В твердження

а) А Í В,

б) А Ç В = А,

в) А È В = В

попарно еквівалентні.

(Зазначимо, що фраза «Твердження R ₁, R ₂,…, R_k попарно еквівалентні» означає, що для будь-яких i та j, i =1,…, k, j =1,…, k, R_i еквівалентне R_j, тобто з R_i випливає R_j, а з R_j випливає R_i.)

Доведення. Достатньо показати, що з а) випливає б), з б) випливає в), а з в) випливає а). Покажемо, що з а) випливає б). Нехай А Í В. Виходячи з означення рівних множин, треба довести, що А Ç В Í А та А Í А Ç В. Оскільки для будь-яких множин А та В А Ç В Í А, то залишається показати, що А Í А Ç В. Нехай х Î А, але тоді х Î В, отже, х Î А Ç В. Таким чином, А Í А Ç В.

Доведемо, що з б) випливає в). Нехай А Ç В = А. Підставивши А Ç В замість А у вираз А È В, а потім послідовно застосувавши закони комутативності (2), дистрибутивності (3), ідемпотентності (10), комутативності (2'), поглинання (12'), маємо:

А È В =(А Ç В)È В = В È(А Ç В)=(В È А)Ç(В È В)=(В È А)Ç В = В Ç(В È А)= В.

Покажемо, що з в) випливає а). Нехай А È В = В. Оскільки А Í А È В, а А È В = В то А Í В.

Тотожності 1-13 та 1'-13' дають змогу спрощувати різні складні вирази, що містять множини. Наведемо приклади.

І. (А Ç В ')'È В = А 'È(В ')'È В = А 'È В È В = А 'È В.

Для спрощення початкового виразу були послідовно застосовані: закон де Моргана (13'), тотожність 8, закон ідемпотентності (10). При перетвореннях ми також дотримувалися домовленості щодо закону асоціативності.

ІІ. (А Ç В Ç С)È(А 'Ç В Ç С)È В 'È С '=((А È А ')Ç В Ç С)È В 'È С '=

=(U Ç В Ç С)È(В Ç С)'=(В Ç С)È(В Ç С)'= U.

У даному випадку послідовно застосовувалися: закон дистрибутивності (3') (до виразу (А Ç В Ç С)È(А 'Ç В Ç С)), тотожності 5, 4' й знов 5. При перетвореннях ми також дотримувалися домовленостей щодо законів асоціативності та комутативності.

ІІІ. (А Ç В Ç С Ç D ')È(A 'Ç C)È(B 'Ç C)È(C Ç D)= (A Ç B Ç C Ç D ')È((A 'È B 'È D)Ç C)=((A Ç B Ç D ')È(A Ç B Ç D ')')Ç C = C.

Тут послідовно застосовано узагальнений закон дистрибутивності (до виразу (A 'Ç C)È(B 'Ç C)È(C Ç D)), закон де Моргана (двічі) з тотожністю 8, тотожності 5 та 4'. Як і раніше, ми дотримувалися домовленостей щодо законів кому-тативності та асоціативності.