Материал: discrete_mathematics

Як зазначалось, рівність двох множин A = B має місце тоді й тільки тоді, коли одночасно виконуються два включення:

A B і B A.

Для доведення теоретико-множинного включення однієї множини в іншу слід розглянути довільний елемент першої множини і шляхом коректних міркувань обґрунтувати, що цей елемент належить також другій із цих множин.

Побудуємо такий ланцюжок логічних міркувань (за кожним знаком або записано відповідне пояснення):

x A B – за означенням доповнення множини;

←(x A B) – за означенням об'єднання множин;

←((x A) (x B)) – за законом де Моргана, див. п. 1.3;

←(x A) ← (x B) – заозначеннямдоповненнямножини;

x А x В – заозначеннямперетинумножин x А ∩ В.

Усі кроки описаних вище міркувань були рівносильними. Це

означає, що із твердження х A B випливає x A ∩ B, і навпаки. Отже, обґрунтовано обидва включення:

A B A ∩ B і A ∩ B A B . ◄

Аналогічно можна довести всі інші наведені теоретикомножинні тотожності.

Ці тотожності дають змогу спрощувати різні складні вирази над множинами.

Приклад 2.13. Послідовно застосовуючи тотожності із (2.1) і (2.2), маємо:

(A ∩ B ∩ C ∩ D ) ( А ∩ C) ( В ∩ C) (C ∩ D) =

=(A ∩ B ∩ C ∩ D ) (( А В D) ∩ C) =

=((A ∩ B ∩ D ) ( A ∩ B ∩ D )) ∩ C = E ∩ C = C. ◄

Ще одним методом доведення теоретико-множинних співвідношень (рівностей або включень) є метод логічних таблиць.

Значення твердження, що об'єкт є елементом множини M (тобто x M), позначатимемо символом 1. В іншому разі, якщо x M, писатимемо 0.

Приклад 2.14.

1. Доведемо методом логічних таблиць теоретико-множинну рівність A \ (B C) = (A \ В ) (A \ C).

97

За допомогою індексів занумеруємо порядок виконання операцій у лівій та правій частинах, як це було зроблено у прик-

ладах 1.5 та 1.6. Матимемо A \2 (B 1 C) = (A \1 В ) 3 (A \2 C).

Як і раніше, запис (k) у таблиці позначатиме результат операції з номером k.

Будуємо відповідні логічні таблиці:

x A \ (B C), тобто x не є елементом множини в лівій частині. За тих самих умов у правій частині матимемо послідовно:

x A \ В та x A \ C).

Повний збіг значень в останніх (виділених) стовпцях таблиць, що відповідають лівій і правій частинам даної теоретикомножинної рівності, свідчить, що ця рівність справджується.

2. Для доведення теоретико-множинного включення (напр., M1 M2) за допомогою методу логічних таблиць аналогічно попередньому прикладу будуємо логічні таблиці для множин M1 та M2. Включення справджується, якщо в будь-якому рядку цих двох таблиць імплікація значення, що відповідає множині M1, і значення, що відповідає M2, є істинною (тобто твердження

x((x M1) → (x M2)) – істинне).

98

Побудуємо відповідні логічні таблиці для доведення такого теоретико-множинного включення: A \ (B C) (A \ B) (A \ C).

Маємо A \2 (B 1 C) (A \1 B) 3 (A \2 C).

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

Аналіз отриманих логічних таблиць свідчить також, що в наведеному співвідношенні знак включення не можна замінити на знак рівності. Наприклад, для випадку (x A) (x B) (x C) (відповідний рядок таблиці – (1,0,1)) такий об'єкт x є елементом правої множини, однак він не належить лівій множині. ◄

3. Перевірити (довести чи спростувати) правильність такого твердження:

(а) якщо A ∩ B С і A C B, то A С;

(б) A ∩ B C тоді й тільки тоді, коли A B C; (в) якщо A ∩ B C, то A C і B C.

(а) Позначимо елементарні твердження x A, x B та x C через a, b, c, відповідно. Тоді перевірка правильності сформульованого твердження зводиться до з'ясування коректності такого логіч-

ного висновку: (a b) → (← c), (a c) → b A a → (← c).

Тобто слід визначити, чи є тавтологією формула

((a b) → (← c)) ((a c) → b) → (a → (← c)).

Побудовою таблиці істинності або методом відшукання контрприкладу переконуємось, що остання формула є тавтологією. Отже, твердження правильне.

(б) Використаємо ті самі елементарні твердження, що й у попередньому пункті. Відповідна до наведеного твердження формула

99

((a b) → c)) ~ (a → (← b c))

є тавтологією, що свідчить про його правильність.

(в) Аналогічно попереднім пунктам запишемо відповідну наслідковість

a b → c (a → b) (b → c).

Неважко переконатись, що ця наслідковість не виконується. Наприклад, для елемента x такого, що x A, x B та x C, засновок a b → c буде істинним, ависновок (a → b) (b → c) – хибним. ◄

Приклад 2.15.

1. Навести приклад множин A та B, які спростовують рівність (A \ B) B = A. Сформулювати та довести необхідні й достатні умови для виконання цієї рівності.

Наприклад, A = {1, 2}, B = {2, 3}. Тоді (A \ B) B = {1, 2, 3} ≠ A.

Доведемо, що (A \ B) B = A тоді й тільки тоді, коли B A. Нехай (A \ B) B = A. Розглянемо довільний елемент x B. З вивідностей у п. 1.4 маємо: x B (x A \ B x B) (за означенням об'єднання множин) x (A \ B) B. Отже, за умовою x A

й виконується включення B A.

Припустимо, що B A. Для встановлення рівності

(A \ B) B = A

доведемо такі два включення: (A \ B) B A та A (A \ B) B. x (A \ B) B – за означенням об'єднання множин;

(x (A \ B) x B) – за означенням різниці множин; ((x A x B) x B) – див. п. 1.4 і припущення B A; (x A x A) –

Навпаки, нехай x A (див. п. 1.4) (x A (x B x B)) –

дистрибутивність кон'юнкції щодо диз'юнкції, див. п. 1.3); ((x A x B) (x A x B)) – див. п. 1.4;

(x B x A \ B) – за означенням об'єднання та властивістю

комутативності об'єднання множин x (A \ B) B.

Отже, необхідні й достатні умови для виконання рівності (A \ B) B = A доведено.

2. Чи існують множини A, B і C, для яких одночасно виконуються такі співвідношення?

A ∩ B ≠ , A ∩ C = , (A ∩ B) \ C = .

100

Ні. Доведення виконаємо методом від супротивного, тобто припустимо, що такі множини A, B і C існують. Тоді з умови A ∩ B ≠ випливає, що існує елемент x A ∩ B, тобто x A та x B. З другої умови отримаємо x C. Отже, x (A ∩ B) \ C, що суперечить останній умові. Отримана суперечність спростовує припущення про існування таких множин.

3. Довести, що A ∩ B C тоді й тільки тоді, коли A В C. Нехай A ∩ B C і x A – див. п. 1.4;

(x A (x B x B)) –

диз'юнкції, див. п. 1.3;

((x A x B) (x A x B)) – означення перетину й допов нення множин і наслідковість із п. 1.4;

(x A ∩ B x В) – припущення задачі й означення об'єд

нання множин x В C.

Отже, доведено, що A В C.

Навпаки, нехай A В C. Маємо x A ∩ B – означенняперетину множин; x A x B – припущення задачі;

(x В C x B) – означення об'єднання множин;

(x В x C) x B – дистрибутивність кон'юнкції щодо диз'юнкції;

(x В x B) (x C x B) – означеннядоповненнямножини; (← (x B) x B) (x C x B) – властивість заперечення,

див. п. 1.3;

0 (x C x B) – властивості елементів 0 і 1, див. п. 1.3; С x B – наслідковість із п. 1.4 x C.

Таким чином, доведено включення A ∩ B C.

Наведене твердження можна довести також за допомогою методів математичної логіки, обґрунтувавши рівносильність формул

((x A x B) → x C) і (x A → (← x B x C))

або (що те саме) тотожну істинність виразу

((x A x B) → x C) ~ (x A → (← x B x C)).

4. Що можна сказати про множини A та B, якщо?

101