.

Відношення. Властивості відношень (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
610 6134
Скачать документ

Реферат на тему:

Відношення. Властивості відношень

Підмножина R декартового степеня Mn деякої множини M називається
n-місним або n-арним відношенням на множині M. Кажуть, що елементи
a1,a2,…,an(M знаходяться у відношенні R, якщо (a1,a2,…,an)(R.

При n=1 відношення R(M називають одномісним або унарним. Таке відношення
часто називають також ознакою або характеристичною властивістю елементів
множини M. Кажуть, що елемент a( M має ознаку R, якщо a(R і R(M.
Наприклад, ознаки “непарність” і “кратність 7” виділяють із множини N
натуральних чисел унарні відношення R( = {2k-1 | k(N } і
R(( = {7k | k(N }, відповідно.

Найбільш популярними в математиці є двомісні або бінарні відношення, на
вивченні властивостей яких ми зупинимось детальніше. Далі скрізь під
словом “відношення” розумітимемо бінарне відношення. Якщо елементи a,b(M
знаходяться у відношенні R (тобто (a,b)(R), то це часто записують у
вигляді aRb. Зауважимо, що бінарні відношення іноді розглядають, як
окремий випадок відповідностей, а саме – як відповідності між однаковими
множинами.

Приклад 1.13. Наведемо приклади бінарних відношень на різних множинах.

1. Відношення на множині N натуральних чисел:

R1 – відношення “менше або дорівнює”, тоді 4R19, 5R15, 1R1m для
будь-якого m(N ;

R2 – відношення “ділиться на”, тоді 4R23, 49R27, mR21 для будь-якого m(N
;

R3 – відношення “є взаємно простими”, тоді 15R38, 366R3121, 1001R3612;

R4 – відношення “складаються з однакових цифр”, тоді 127R4721, 230R 4
302, 3231R 43213311.

2. Відношення на множині точок координатної площини R2:

), (0,0)R 5 (0,0) ;

R6 – відношення “симетричні відносно осі ординат”, тоді (1,7)R6(-1,7) і
взагалі (a,b)R6(-a,b) для будь-яких a,b(R ;

R7 – відношення “менше або дорівнює”. Вважаємо, що (a,b)R7(c,d), якщо a
( c і b ( d. Зокрема, (1,7)R7(20,14), (-12,4)R7(0,17).

3. Відношення на множині студентів даного вузу:

R8 – відношення “є однокурсником”,

R9 – відношення “є молодшим за віком від”.

Для задання відношень можна користуватись тими ж способами, що і при
заданні множин. Наприклад, якщо множина M скінченна, то довільне
відношення R на M можна задати списком пар елементів, які знаходяться у
відношенні R.

Зручним способом задання бінарного відношення R на скінченній множині M
= {a1,a2,…,an} є задання за допомогою так званої матриці бінарного
відношення. Це квадратна матриця C порядку n, в якій елемент cij, що
стоїть на перетині i-го рядка і j-го стовпчика, визначається так

( 1, якщо aiRaj,

cij = (

( 0, в противному разі.

Приклад 1.14. Для скінченної множини M = {2,7,36,63,180} матриці
наведених вище відношень R1, R2, R3 мають такий вигляд

Рис.1.5.

Відношення можна задавати також за допомогою графіків і діаграм. Графік
відношення означається й будується так само, як і графік відповідності.
Поняття діаграми (або графа) відношення також можна означити аналогічно
до відповідності. Однак частіше діаграма (або граф) відношення R на
скінченній множині M={a1,a2,…,an} означається таким чином. Поставимо у
взаємно однозначну відповідність елементам множини M деякі точки
площини. З точки ai до точки aj проводимо напрямлену лінію (стрілку) у
вигляді відрізка або кривої тоді і тільки тоді, коли aiRaj. Зокрема,
якщо aiRai, то відповідна стрілка, що веде з ai в ai, називається
петлею.

Оскільки відношення на M є підмножинами множини M 2, то для них означeні
всі відомі теоретико-множинні операції. Наприклад, перетином відношень
“більше або дорівнює” і “менше або дорівнює” є відношення “дорівнює”,
об’єднанням відношень “менше” і “більше” є відношення “не дорівнює”,
доповненням відношення “ділиться на” є відношення “не ділиться на” тощо.

Аналогічно відповідностям для відношень можна означити поняття
оберненого відношення і композиції відношень.

Відношення R-1 називається оберненим до відношення R, якщо bR-1a тоді і
тільки тоді, коли aRb. Очевидно, що (R-1)-1=R. Наприклад, для відношення
“більше або дорівнює” оберненим є відношення “менше або дорівнює”, для
відношення “ділиться на” – відношення “є дільником”.

Композицією відношень R1 і R2 на множині M (позначається R1(R2 )
називається відношення R на M таке, що aRb тоді і тільки тоді, коли
існує елемент c(M, для якого виконується aR1c і cR2b. Наприклад,
композицією відношень R1 – “є сином” і R2 – “є братом” на множині
чоловіків є відношення R1(R2 – “є небожем”.

Наведемо список важливих властивостей, за якими класифікують відношення.

Нехай R – деяке відношення на множині M.

а). Відношення R називається рефлексивним, якщо для всіх a(M має місце
aRa.

Очевидно, що відношення R1,R2,R4,R5,R7 – рефлексивні.

б). Відношення R називається антирефлексивним (іррефлексивним), якщо для
жодного a(M не виконується aRa.

Відношення “більше”, “менше”, “є сином” антирефлексивні. В той же час,
відношення R6 не є ні рефлексивним, ні антирефлексивним.

Всі елементи головної діагоналі матриці C для рефлексивного відношення
на скінченній множині M дорівнюють 1, а для антирефлексивного відношення
дорівнюють 0.

в). Відношення R називається симетричним, якщо для всіх a,b(M таких, що
aRb маємо bRa.

г). Відношення R називається антисиметричним, якщо для всіх a,b(M таких,
що aRb і bRa маємо a = b.

Наприклад, відношення R3,R4,R5,R6,R8 – симетричні, а відношення R1,R2,R7
– антисиметричні.

Неважко переконатись, що відношення R симетричне тоді і тільки тоді,
коли R=R-1.

д). Відношення R називається транзитивним, якщо зі співвідношень aRb і
bRc випливає aRc.

Наприклад, відношення R1,R2,R4,R5,R7,R8,R9 – транзитивні, а відношення
R3,R6 – не транзитивні.

Неважко переконатись, що відношення R транзитивне тоді і тільки тоді,
коли R(R(R.

Зауважимо, якщо відношення R має будь-яку з перерахованих вище
властивостей, то обернене відношення R-1 також має ту саму властивість.
Таким чином, операція обернення зберігає всі п’ять властивостей
відношень.

Для довільного відношення R означимо нову операцію. Відношення R*
називається транзитивним замиканням відношення R на M, якщо aR*b, a,b(M,
тоді і тільки тоді, коли у множині M існує послідовність елементів
a1,a2,…,an така, що a1 = a, an = b і a1Ra2, a2Ra3,…,an-1Ran.

Наприклад, нехай M – це множина точок на площині і aRb, a,b(M, якщо
точки a і b з’єднані відрізком. Тоді cR*d, c,d(M, якщо існує ламана
лінія, яка з’єднує точки c і d.

Можна довести, що відношення R транзитивне тоді і тільки тоді, коли
R*=R.

Деякі відношення займають особливе місце в математиці. Розглянемо ці
відношення окремо.

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Ответить

Курсовые, Дипломы, Рефераты на заказ в кратчайшие сроки
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020