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

Теорема 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'. Як і раніше, ми дотримувалися домовленостей щодо законів кому-тативності та асоціативності.