Page 15 - 4570

14

декартовим квадратом множини А. Аналогічно, декартовим добутком n
множин А 1, . . ., А n (позначають A 1 . . . А n) називають множину всіх таких
кортежів (а 1, . . ., а n) довжиною n, що а 1  А 1, . . ., а n  А n. Частковий випадок
n
А. . . А позначають як А і називають n-м степенем множини А.
Приклад 1.18. Нехай А = {1, 2}, В = {а, b, с]. Тоді
АВ = {(1, а), (1, b), (1, с), (2, а), (2, b), (2, с)},
ВА = {(а, 1), (а, 2), (b, 1), (b, 2), (с, 1), (с, 2)}.
Зрозуміло, що загалом АВ ≠ ВА.
Для скінченних множин потужність (кількість елементів) декартового
добутку дорівнює добутку потужностей цих множин: |АВ| = |А| |В|.
Кортеж – це впорядкований набір елементів. Це не означення кортежу, бо
не пояснено, що таке впорядкований набір. Вважатимемо поняття «кортеж»
(вектор, рядок, ланцюжок), як і поняття множини, первісним, неозначуваним.
Елементи, що утворюють кортеж, називають його компонентами. Компоненти
нумерують, кількість компонент називають довжиною (розмірністю) кортежу.
Нескінченні кортежі не розглядатимемо.
На відміну від елементів множини, компоненти кортежу можуть
повторюватись. Кортеж записують у круглих дужках, наприклад (а, b, с, a, d) –
кортеж довжиною 5. Іноді дужки і навіть коми не пишуть, наприклад 011001.
Кортежі довжиною 2 часто називають парами, довжиною 3 – трійками,
довжиною n – n-ками («енками»).
Два кортежі рівні, якщо вони мають однакову довжину та відповідні їх
компоненти рівні. Інакше кажучи, кортежі (a 1, . . ., а n) і (b 1, . . ., b m) рівні, якщо n
= m та a 1 = b 1, а 2 = b 2, . . ., а n = b m.

3. Принцип двоїстості та комп’ютерне подання множин

Рівність алгебри множин, отримана з іншої рівності через заміну всіх
входжень  на ,  на ,  на U і U на , називається двоїстою
(дуальною) відносно вихідної рівності.
Для будь-якого істинного твердження, що формулюється за допомогою
знаків операцій  та ,  та U, двоїсте відносно нього речення також є
істинним. Це речення виражає принцип двоїстості алгебри множин.
З цього принципу випливає, що якщо є деяке твердження із знаками
операцій  та ,  та U, то відповідне йому твердження зі штрихом на
підставі двоїстості випливає з цього ж самого твердження. Це означає, що нема
потреби доводити, наприклад, рівність A B  A  B , якщо доведена рівність

A B  A  B .
У комп’ютері можна подавати множини різними способами. Один зі
способів – зберігати невпорядковані елементи множини. Проте в такому разі
операції з множинами займатимуть багато часу через те, що потрібно щоразу
переглядати елементи. Тому розглянемо інші способи.
Одним із найпоширеніших і найпростіших способів – подання множин за
допомогою бітових рядків. Упорядкуємо довільним способом елементи