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

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