Теорема 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), дві множини, котрі можна утворити за допомогою операції об’єднання з множин А, В й С, узятих у певному порядку, рівні. Домовимося позначати таку єдину множину через АÈВÈС. Закон асоціативності стверджує, що порядок розміщення дужок у цьому виразі не є суттєвим. Можна узагальнити цей результат, тобто показати, що усі множини, які можна побудувати із заданих множин А1,А2,…,Аn, узятих у зазначеному порядку, є рівними. Множину, яка утворюється таким способом з А1,А2,…,Аn, позначатимемо через А1ÈА2È…ÈАn. Відповідне узагальнення можна зробити й для операції перетину. Такі загальні закони асоціативності дають змогу установити загальні закони комутативності: якщо 1',2',…,n' – це числа 1,2,…,n, узяті у довільному порядку, то
А1ÈА2È…ÈАn = А1'ÈА2'È…ÈАn',
А1ÇА2Ç…ÇАn = А1'ÇА2'Ç…ÇАn'.
Можна узагальнити й закони дистрибутивності:
АÈ(В1ÇВ2Ç…ÇВn)=(АÈВ1)Ç(АÈВ2)Ç…Ç(АÈВn),
АÇ(В1ÈВ2È…ÈВn)=(АÇВ1)È(АÇВ2)È…È(АÇВ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. Для довільних множин А та В твердження
а) АÍВ,
б) АÇВ=А,
в) АÈВ=В
попарно еквівалентні.
(Зазначимо, що фраза «Твердження R1,R2,…,Rk попарно еквівалентні» означає, що для будь-яких i та j, i=1,…,k, j=1,…,k, Ri еквівалентне Rj, тобто з Ri випливає Rj, а з Rj випливає Ri.)
Доведення. Достатньо показати, що з а) випливає б), з б) випливає в), а з в) випливає а). Покажемо, що з а) випливає б). Нехай АÍВ. Виходячи з означення рівних множин, треба довести, що АÇВÍА та АÍАÇВ. Оскільки для будь-яких множин А та В АÇВÍА, то залишається показати, що АÍАÇВ. Нехай хÎА, але тоді хÎВ, отже, хÎАÇВ. Таким чином, АÍАÇВ.
Доведемо, що з б) випливає в). Нехай АÇВ=А. Підставивши АÇВ замість А у вираз АÈВ, а потім послідовно застосувавши закони комутативності (2), дистрибутивності (3), ідемпотентності (10), комутативності (2'), поглинання (12'), маємо:
Покажемо, що з в) випливає а). Нехай АÈВ=В. Оскільки АÍАÈВ, а АÈВ=В то АÍВ.
Тотожності 1-13 та 1'-13' дають змогу спрощувати різні складні вирази, що містять множини. Наведемо приклади.
І. (АÇВ')'ÈВ=А'È(В')'ÈВ=А'ÈВÈВ=А'ÈВ.
Для спрощення початкового виразу були послідовно застосовані: закон де Моргана (13'), тотожність 8, закон ідемпотентності (10). При перетвореннях ми також дотримувалися домовленості щодо закону асоціативності.
ІІ. (АÇВÇС)È(А'ÇВÇС)ÈВ'ÈС'=((АÈА')ÇВÇС)ÈВ'ÈС'=
=(UÇВÇС)È(ВÇС)'=(ВÇС)È(ВÇС)'=U.
У даному випадку послідовно застосовувалися: закон дистрибутивності (3') (до виразу (АÇВÇС)È(А'ÇВÇС)), тотожності 5, 4' й знов 5. При перетвореннях ми також дотримувалися домовленостей щодо законів асоціативності та комутативності.
Тут послідовно застосовано узагальнений закон дистрибутивності (до виразу (A'ÇC)È(B'ÇC)È(CÇD)), закон де Моргана (двічі) з тотожністю 8, тотожності 5 та 4'. Як і раніше, ми дотримувалися домовленостей щодо законів кому-тативності та асоціативності.
