p>
Внутрішні області, обмежені жирними лініями, збігаються. Можна простежити, що операції над множинами по їх об'єднанню або перетинанню володіють також коммутативностью і асоціативністю.
Відносини множин. Види відносин та їх властивості
Елементи множини, як правило, знаходяться в будь-якому відношенні один щодо одного. Ці відносини можна задати у вигляді неповних речень - предикатів, наприклад, В«менше, ніж ...В», В«більше, ніж ...В», В«еквівалентноВ», В«конгруентноВ» і т. п.
Той факт, що певний елемент знаходиться в якому-небудь відношенні до елемента того ж безлічі x j , математично записують як XiRxj , де R - символ відносини.
Ставлення з двох елементів безлічі X називають бінарним. Бінарні відносини множин X і Y представляють собою деяке безліч впорядкованих пар (х, у), освічених декартовим твором X х Y . У випадку можна говорити не тільки про безліч впорядкованих пар, а й про безліч впорядкованих трійок, четвірок елементів і т. д., тобто про парних стосунках, одержуваних у результаті декартова твори , де п - розмірність n -рядків.
Розглянемо основні види відносин - відносини еквівалентності, порядку та домінування.
Деякі елементи множин можна вважати еквівалентними в тому випадку, коли будь-який з цих елементів за певних умов можна замінити іншим, тобто дані елементи знаходяться ось-носінні еквівалентності. Прикладами відносин еквівалентності є відносини паралельності на безлічі прямих небудь площині; подоби на безлічі трикутників; приналежності до однієї функціональної групі мікросхем або до одного класу типорозмірів і т. д.
Термін В«Ставлення еквівалентностіВ» будемо застосовувати при виконанні таких умов:
1) кожен елемент еквівалентний самому собі;
2) вислів, що два елементи є еквівалентними, не вимагає уточнення того, який з елементів розглядається першим, а який другим;
3) два елемента, еквівалентні третьому, еквівалентні між собою.
Введемо для позначення еквівалентності символ ~, тоді розглянуті умови можна записати наступним чином:
1) х ~ Х (рефлективність);
2) х ~ Уу ~ х (симетричність);
3) х ~ У і у ~ z х ~ z (транзитивність). p> Отже, ставлення R називають відношенням еквівалентності, якщо воно рефлексивно, симетрично і транзитивній.
Нехай деякого елементу х X еквівалентно деякий підмножина елементів А X , тоді це підмножина утворює клас еквівалентності, еквівалентний х. Очевидно, що всі елементи одного і того ж класу еквівалентності еквівалентні між собою (властивість транзитивності). Тоді всякий елемент хХ може знаходитися в одному і тільки одному класі еквівалентності, тобто в цьому випадку безліч X розбивається на деяку непересічне підмножина класів еквівалентності , де J - деяке безліч індексів. p> Таким чином, кожному відношенню еквівалентності на безлічі X відповідає деякий розбиття безлічі X на класи.
Часто стикаються з відносинами, які визначають деякий порядок розташування елементів множини. Наприклад, у процесі автоматизованого конструювання потрібно вводити безліч одних вихідних даних раніше або пізніше, ніж безліч інших. При цьому може виявитися, що елементи одного безлічі більше або менше елементів іншого і т. д. У всіх цих випадках можна розташувати елементи множини X або групи елементів в деякому порядку (наприклад, у вигляді спадної або зростаючою послідовності), тобто ввести відношення порядку на множині X.
Розрізняють відносини строгого порядку, для яких застосовують символи і відносини не суворого порядку, де використовують символи. Ці відносини характеризуються такими властивостями:
для відносини строгого порядку:
х < X - помилково (антирефлексивне);
х <У, а У <х - взаємовиключаються (несиметричність);
x <у і у < x x < z - (транзитивність);
для відносини не суворого порядку:
х X - істинно (рефлексивність);
ху і ух х = у - (антисиметричність);
х у і у z x у z - (транзитивність) .
Безліч X називають впорядкованим, якщо будь-які два елементи х і у цієї множини можна порівняти, тобто якщо для них виконується одна з умов: х < у, х = у, у < х.
Впорядковане безліч називають кортежем. У загальному випадку кортеж - це послідовність елементів, тобто сукупність елементів, в якій кожен елемент займає цілком певне місце. Елементи впорядкованої множи...
