1.5. Діаграми Ейлера – Венна

Для наглядної ілюстрації операцій над множинами використовуються так звані діаграми Ейлера – Венна. Ми з ними мали справу тільки-що. На цих діаграмах результат операції подається у вигляді затемненої області, а квадрат – це універсальна множина U.

Рис.3

З цієї діаграми добре видно, що симетрична різниця визначається формулою . Алгебра множин. Закони алгебри множин.

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

Комутативний закон
Асоціативний закон
Дистрибутивний закон
Властивості множин та
Закон ідемпотентності (самопоглинання)
Закон поглинання
Закони де Моргана
Доповнення, різниці та ін.

Основні закони і властивості операцій з множинами

1.6. Декартовий добуток.

Нехай маємо дві множини і . Множина називається декартовим добутком множин і і позначається символом . Якщо множини і скінченні і складаються з і елементів відповідно, то множина – декартовий добуток множин і – складається з пар елементів.

О з н а ч е н н я. Декартовий добуток двох множин – це множина всіх можливих пар елементів множин і .

Декартовий добуток іноді називають прямим добутком, який позначають символом .

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

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

Число елементів множини, як уже говорилось, позначається символом , отже, число елементів декартового добутку дорівнює . Зауважимо, що =  тільки у випадку, коли принаймні один із співмножників є порожня множина. Коротко цю тезу можна записати так: . В подальшому будемо вважати, що, як правило, множини А і В – не порожні..

Окремий інтерес являє той випадок, коли множини рівні, тобто . Оскільки тепер в декартовому добутку будуть елементи однієї й тієї ж множини, то потрібно ввести поняття упорядкованої пари елементів.

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

Так, наприклад, якщо множина , то пари і , а також пари вважаються різними, хоча вони і складені з одних і тих же елементів. Пари, складені з однакових елементів теж вважаються упорядкованими.

О з н а ч е н н я. Декартовим квадратом множини називається множина всіх упорядкованих пар елементів із множини і позначається символом .

Отже, декартовий квадрат деякої множини – це множина, складена з усіх упорядкованих пар елементів множини .

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

Так само можна узагальнити і поняття декартового добутку на випадок довільної сукупності множин.

О з н а ч е н н я. Декартовим добутком множин називається сукупність послідовностей, тобто сукупність упорядкованих –ок елементів вигляду , де , .

Елементи декартового добутку часто називають кортежами. Інакше кажучи, кортежем називають впорядковану послідовність , а кожен його елемент – компонентою кортежу. Кортеж може містити компоненти, що повторюються, але не можна порушувати заданий порядок компонент у кортежі. Наприклад, такі кортежі не рівні: . Для позначення кортежу використовують круглі дужки, а для заміщення його в тексті – символ t, тобто . Впорядковані набори елементів фіксованої довжини називають сумісними кортежами.

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

Наприклад, точку на кресленнях описують в декартовій системі координат так: (x; у; z), де x, у, z – координати точки в тривимірному просторі; в полярній системі координат так: (,, ), де  – радіус-вектор,  – кут нахилу радіус-вектора до осі Оx, а  – кут нахилу радіусу вектора до осі Оy; дату в документах описують так: (<число>,<місяць> ,<рік>). Число компонент кортежу визначає його довжину або ранг: .

П р и к л а д 2.1.

Нехай – множина дійсних чисел. Тоді = {(0,0),(0,1)}, = {(0,0),(1,0)},

= {(0,0,0),(0,0,1),(0,0,2),(0,1,0),(0,1,1),(0,1,2)},

B²={(0;0),(0;1),(1;0),(1;1)}.

Нехай R¹=R – множина точок числової прямої, тоді R² = – множина точок площини XOY, R³ = – множина точок простору XOYZ Звертаємо увагу на те, що декартовий добуток – операція не комутативна. Видно, що . В цьому є певна аналогія з векторним добутком векторів.

П р и к л а д 2.2.

Розглянемо скінченну множину А, елементи якої є символи (букви, цифри, розділові знаки, знаки операцій ). Таку множину будемо називати алфавітом. Елементи декартового степеня (тобто n–ки) – це слова довжини n в алфавіті А. Множину В всіх слів в алфавіті А можна записати у вигляді:

.

Нехай, наприклад, множина складається з десяти елементів . Це – алфавіт з 10- символів. Всякий набір символів з цього алфавіту називається словом відповідної довжини. Наприклад, є слово, але уже не є слово, оскільки елементи і не належать алфавіту. Отже, множина елементів буде словом в заданому алфавіті тоді і тільки тоді, коли всі його елементи належать алфавіту. Коли мова йде про числові множини, то у слові нулі не можуть стояти на першому місці.

Зауважимо, що при запису слів , як правило, не використовують обрамляючи дужки і розділові коми. Запишемо, наприклад, множину всіх слів B довжиною не більше трьох в алфавіті А = {0;1}. Це буде множина слів довжиною 1 або довжиною 2, або довжиною 3, тобто це буде об’єднання цих множин: , де

, .

Тоді

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

1. ;

2. ;

3. ;

4. ;

5. ;

6. .

11