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

Числові вирази. Значення числового виразу

Під числовим виразом розуміють запис чисел та операцій над ними, в якому за попередньою домовленістю відомий порядок виконання операцій над ними. Кожне число є також числовим виразом. Числа виразу називаються його компонентами.
Якщо в числивому виразі виконати всі зазначені операції, то одержане число називається його значенням. Якщо числовий вираз є числом, то це число і називається його значенням. Залежно від значень числові вирази поділяються на додатні, від’ємні і нульові, записується це так: А > 0, А < 0, А = 0. Числові вирази не завжди мають значення в тій числовій множині, з якої беруть їх компоненти. 14. Відношення еквівалентності Відношення R на множині M називається відношенням еквівалентності (або

просто еквівалентністю), якщо воно рефлексивне, симетричне і

транзитивне.

Враховуючи важливість відношення еквівалентності, дамо розгорнуте

означення цього поняття. Таким чином, відношення R на множині M є

відношенням еквівалентності або евівалентністю, якщо

1. aRa для всіх a(M (рефлексивність);

2. Якщо aRb, то bRa для a,b(M (симетричність);

3. Якщо aRb і bRc, то aRc для a,b,c(M (транзитивність). Еквівалентністю є відношення подібності на множині всіх трикутників.

15. розміщення з повторенням

Розмiщення з повтореннями — це сполуки, якi мають такi характернi ознаки:

1. Порядок розташування елементiв у сполуцi має значення.

2. Елементи у сполуках можуть бути задiянi вiд нуля до m разiв: 0 ≤ k_i ≤ m, де

§ m — кiлькiсть мiсць у кожнiй сполуцi вибраної групи;

§ k_i — кiлькiсть мiсць у сполуцi для будь-якого елемента, що задiяний для її складання.

Кiлькiсть розмiщень з повтореннями обчислюють за формулою: Ã_n^m = n^m, де n — кiлькiсть елементiв, що претендують на мiсця у сполуках.

§ рефлексивним, якщо IÍR, тобто, іншими словами, воно завжди виконується між елементом і ним самим ("aÎA, aRa). Як приклад такого відношення можна навести відношення нестрогої нерівності на множині натуральних або дійсних чисел.

Матриця рефлексивного відношення характеризується тим, що всі елементи її головної діагоналі – одиниці. Граф рефлексивного відношення – тим, що петлі є у всіх вершинах.

§ антирефлексивним (іррефлексивним), якщо RÇI=Æ, тобто якщо співвідношення aiRaj виконується, то ai¹aj. Це, наприклад, відношення строгої нерівності на множинах натуральних або дійсних чисел, відношення “бути старшим” у множині людей.

Матриця антирефлексивного відношення характеризується тим, що всі елементи її головної діагоналі – нулі. Граф антирефлексивного відношення не має жодної петлі.

§ симетричним, якщо R = R-1, тобто при виконанні співвідношення aiRaj виконується співвідношення ajRai. Як приклад такого відношення можна навести відстань між двома точками на площині, відношення “бути братом” на множині людей.

Симетричність відношення спричиняє також симетричність матриці. Також для такого відношення вершини графа можуть бути пов’язані тільки парами протилежно спрямованих дуг (тобто ребрами).

§ асиметричним, якщо RÇR-1=Æ, тобто із двох співвідношень aiRaj та ajRai щонайменше одне не виконується. Як приклад такого відношення можна навести відношення “бути батьком” у множині людей, відношення строго включення в множині всіх підмножин деякого універсуму. Очевидно, якщо відношення асиметричне, то воно й антирефлексивне.

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

§ антисиметричним, якщо RÇR-1ÍI, тобто обидва співвідношення aiRaj та ajRai одночасно виконуються тоді й тільки тоді, коли aj=ai. Як приклад можна навести нестрогу нерівність.

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

§ транзитивним, якщо R°RÍR, тобто з виконання співвідношень aiRaj та ajRak випливає виконання співвідношення aiRak. Як приклад можна навести відношення “бути дільником” на множині цілих чисел, “бути старшим” на множині людей.

Матриця транзитивного відношення характеризується тим, що коли rij=1 й rjk=1, то rik=1, причому наявність одиничних елементів на головній діагоналі не порушує транзитивність матриці. Граф транзитивного відношення характеризується тим, що коли через деяку сукупність вершин графа проходить шлях, то існують дуги, які з’єднують будь-яку пару вершин з цією сукупністю в напрямку шляху. Як правило, на графі транзитивного відношення зображують тільки цей шлях, а зумовлені транзитивністю дуги опускають. Такий граф називають графом редукції (або кістяковим графом).

Означення 2.10. Нехай R – бінарне відношення на множині А. Рефлексивним замкненнямR є найменше рефлексивне відношення на А, що містить R як підмножину. Симетричне замкнення R є найменше симетричне відношення на А, що містить R як підмножину. Транзитивне замкненняR є найменше транзитивне відношення на А, яке містить R як підмножину.

Дата добавления: 2014-12-16