Материал: discrete_mathematics

Ні. Доведення виконаємо методом від супротивного, тобто припустимо, що такі множини 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

У першому випадку A – довільна множина, а B = . Обґрунтуємо це твердження методом від супротивного, тобто припустимо, що множина B непорожня та існує елемент x B. Якщо одночасно x A, то за означенням симетричної різниці множин матимемо, що x A B, тобто A B ≠ A, що суперечить умові задачі. Якщо ж припустити, що x B, але x A, то за означенням симетричної різниці множин матимемо, що x A B. Отже, і цього разу задана рівність A B = A не виконується. Таким чином, припущення, що B ≠ , суперечить умові задачі, тобто має місце рівність B = .

Розв'язання другої задачі таке: A – довільна множина, а B = E (або В = ). Знову застосуємо метод від супротивного й припустимо, що множина В непорожня та існує елемент x В. Якщо

чить умові задачі. Якщо ж припустити, що x В, але x A (або x А), то отримаємо x A B, тобто й цього разу задана в умові

рівність не виконується. Отже, припустивши, що B ≠ E, дійшли суперечності, тобто має місце рівність B = E. ◄

2. За допомогою діаграм Венна та методу логічних таблиць перевірити такі теоретико-множинні рівності:

(а) A ∩ (B C) = (A ∩ B) (A ∩ C);

(б) (A ∩ B) A = (A B) ∩ A = A;

(в) A \ (B C) = (A \ B) ∩ (A \ C);

(г) (A B) \ C = (A \ C) (B \ C); (д) A ∩ (B C) = (A ∩ B) (A ∩ C); (е) A B = (A B) \ (A ∩ B).

3. Навести приклад множин A та B, які спростовують рівність

(A B) \ B = A.

102

Сформулювати й довести необхідні й достатні умови для виконання цієї рівності.

5. Нехай A та B – довільні множини. Довести, що співвідношення, розміщені в одному рядку, рівносильні між собою, тобто з істинності одного з них випливає істинністьусіх інших.

(а) A B, В А, A B = B, A ∩ B = A, A \ B = ; (б) A B, А B = E, A ∩ В = ;

(в) A ∩ B = , A В, B А;

(г) A B = E, А B, В A.

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

(а) якщо A C = B C, то A = B;

(б) якщо A ∩ C = B ∩ C, то A = B;

(в) якщо A B = A C, то B = C;

(г) якщо A C = B C і A ∩ C = B ∩ C, то A = B; (д) якщо A \ C = B \ C і C \ A = C \ B, то A = B;

(е) якщо A \ C = B \ C і A ∩ C = B ∩ C, то A = B.

7. Довести, що:

(а) A B C A C і B C;

(б) A B ∩ C A B і A C;

(в) (A ∩ B) C = A ∩ (B C) C A; (г) A B C A ∩ В C;

(д) (A \ B) B = A B A;

(е) A \ B = A A ∩ B = .

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

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

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

103

10.Довести тотожність (A ∩ B) A = (A B) ∩ A = A.

11.Сформулювати та довести необхідні й достатні умови для множин A та B, щоб виконувалася рівність

β(A) β(B) = β(A B).

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

2.4. Декартів (прямий) добуток множин

Декартовим (прямим) добутком множин A та B (позначають

A × B) називають множину всіх пар (a, b), у яких перша компонента належить множині A (a A), а друга – множині B (b B), тобто

A × B = {(a, b) | a A та b B }, або (a, b) A × B a A b B.

Декартів добуток можна природно узагальнити для довільної скінченної сукупності множин. Якщо A1, A2, …, An – множини, то їхнім декартовим добутком називається множина

D = {(a1, a2, …, an) | a1 A1, a2 A2, …, an An},

яка складається зі всіх наборів (a1, a2, …, an), у кожному з яких i-й

член, що називається i-ю координатою, або i-м компонентом

набору, належить множині Ai, i = 1, 2, …, n. Декартів добуток по-

значають A1× A2× … × An.

Щоб відрізняти набір (a1, a2, …, an) від множини, що складається зелементів a1, a2, …, an, його записують не у фігурних, а в круглих дужках і називають кортежем, вектором або впорядкованим

набором.

Довжиноюкортежу називають кількість його координат. Два кортежі (a1, a2, …, an) і (b1, b2, …, bn) однакової довжини

вважають рівними тоді й тільки тоді, коли рівні відповідні їхні координати, тобто ai = bi, i = 1, 2, …, n.

Отже, кортежі (a, b, c) і (a, c, b) різні, у той час як множини {a, b, c} і {a, c, b} рівні між собою.

Декартів добуток множини A на себе n разів, тобто множину

A × A × … × A, називають n-м декартовим (прямим) степенем

множини A та позначають An.

104

Вважають, що A0 = (n = 0) і A1 = A (n = 1). Приклад 2.16. 1. Якщо A = {a, b} і B = {b, c, d}, то

A × B = {(a, b), (a, c), (a, d), (b, b), (b, c), (b, d)}, A2 = {(a, a), (a, b), (b, a), (b, b)}.

2.Якщо R – множина дійсних чисел, або множина точок координатної прямої, то R2 – це множина пар (a, b), де a, b R, або множина точок координатної площини.

Координатне зображення точок площини вперше запропонував французький математик і філософ Рене Декарт, тому введена тео- ретико-множинна операція й називається декартовим добутком.

3.Скінченну множину A, елементами якої є символи (літери, цифри, спеціальні знаки тощо), називають алфавітом. Елементи

декартового степеня An називають словами довжиною n в алфавіті A. Множина

A* = {e} A A2 A3 … = {e} Аі

i N

– це множина всіх слів у алфавіті A; тут e – порожнє слово

(слово довжиною 0), яке не містить жодного символу алфавіту A. Порожнє слово позначають також через ε.

Замість запису слів з An у вигляді кортежів (a1, a2, …, an) частіше використовують традиційну форму їх запису у вигляді послідовності символів a1a2…an, aj A, j = 1, 2, …, n. Наприклад, 010111, 011, 0010, 100 – слова в алфавіті B = {0, 1},

67–35, 98))*–)+1, (4*50+12)/27 – слова в алфавіті

C = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, –, *, /, (, )}. ◄

Операція декартового добутку неасоціативна й некомутативна, тобто множини

(A × B) × C, A × (B × C) і A × B × C,

а також множини

A × B і B × A

не рівні між собою. (Зауважимо, що в математиці множини (A × B) × C і A × (B × C) іноді ототожнюють з A × B × C, вважаючи, що кортежі ((a, b), c), (a, (b, c)) і (a, b, c) збігаються.)

Приклад 2.17.

1. Навести приклад множин A та B таких, що A × B ≠ B × A. Для яких множин виконується рівність?

105