АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Свойства бинарных отношений

Читайте также:
  1. F. Метод, основанный на использовании свойства монотонности показательной функции .
  2. I. Социально-психологическая сущность неуставных взаимоотношений
  3. II. Свойства векторного произведения
  4. II. Типы отношений между членами синтагмы
  5. III. Психические свойства личности – типичные для данного человека особенности его психики, особенности реализации его психических процессов.
  6. V2: Электрические и магнитные свойства вещества
  7. VI.1. Правовое регулирование брака и семейных отношений
  8. VII. Принятые формы сексуальных отношений
  9. Аддикция отношений
  10. Административно-правовое регулирование отношений в сфере конкуренции и ограничения монополистической деятельности на товарных рынках
  11. Административно-правовые отношения. Особенности административно-правовых отношений.
  12. Административное деление украинских земель в составе империй. Социально-экономический уклад, начало кризиса феодально-крепостнической системы общественных отношений.

 

Бинарное отношение R (RÌA´A=A2), заданное на множестве А называется отношением тождества, если все его элементы (кортежи) имеет вид (а,а), где аÎА и обозначается idA, т.е. . Пары, вида (а,а) называются диагональными, а отношение idA называют диагональным. Вполне понятно, что матрица отношения тождества будет иметь вид единичной матрицы:

Очевидно, что для любого бинарного отношения R, определенного на множестве А, имеет место равенство: *R=R*idA=R.

Бинарное отношение R, заданное на множестве А, называется рефлексивным, если idAÍR, т.е. когда оно включает диагональ.

Примеры:

а. А – множество прямых на плоскости, на котором задано отношение R= «Прямая Х параллельная прямой Y».

Действительно, как известно из элементарной геометрии, две прямые параллельны, если они либо совпадают, либо не имеют ни одной общей точки (нигде не пересекаются). Поскольку прямая Х совпадает сама с собой, то пара (Х,Х) принадлежит данному отношению R, т.е. (Х,Х)Î R.

b. А – множество студентов нашего вуза и на котором задано отношение Р= «студент S ровесник студенту V». Очевидно, что каждый ровесник сам себе, и поэтому (S,S)ÎP.

Бинарное отношение R, заданное на множестве А называется иррефлексивным, если aRa (или (а,а)Î R) не имеет смысла. Или тоже самое можно сформулировать как (а,а)Ï R.

Пример:

а. На числовом множестве D задано отношение R=”<”. Вполне очевидно, что для любых двух чисел х отношение x<x всегда ложно, т.е. все диагональные элементы (х,х) этого отношения на матрице отношений будут равны нулю.

Следует отметить, что иррефлексивные отношения еще называют антиреффлексивным.

Ø Бинарное отношение R, заданное на множестве А называется симметричным, если для пары (а, b) Î А2 из аRb следует bRа (RÍR-1).

Примеры:

а. Прямая А перпендикулярна прямой В в плоскости Z.

b. Студент Х является соседом по парте студента Y.

(Заметим, что приведенные отношения не являются рефлексивными).

Ø Бинарное отношение R, заданное на множестве А называется, антисимметричным, если из и следует, что ().

Пример:

а. Отношение включения для множества, т.е. отношение «множество А является подмножеством множества В». И если А Í В и В ÍА, то из аксиомы объемности следует, что А = В.

Ø Бинарное отношение R, заданное на множестве А называется транзитивным, если для любых a, b, c Î A из aRb и bRc следует aRc (R Í R2).

Примеры:

а. Отношения подобия на множестве треугольников;

в. Отношение «быть ровесником», заданное на множестве студентов;

с. Отношение «быть больше (меньше)», заданное на множестве действительных чисел.

Ø Бинарное отношение R, заданное на множестве А называется отношением эквивалентности (или просто эквивалентностью), если для любых элементов a, b, c Î A выполняются следующие свойства:

- рефлексивность: aRa (idA Í R);

- симметричность: aRb Þ bRa (R Í R-1);

- транзитивность: aRb и bRc Þ aRc (R2 Í R).

Примеры:

а. Отношение равенства “=” на любом множестве является отношением эквивалентности (рефлексивность: а=а; симметричность: a=bÞb=a; транзитивность: (a=b и b=c) Þ a=c).

b. Отношение R={(1, 1), (1, 2), (1, 3), (2, 2), (2, 2), (2, 1), (2, 3), (3, 3), (3, 2), (3, 1)} является отношением эквивалентности, так как оно рефлексивно: "(а){(a, a) Î R}; симметрично: (a, b) R (b, a) ÎR; транзитивно: ((a, b) и (b, c) ÎR Þ (a, c) Î R, где a, b –числа, принимающие значения 1, 2, 3. Например, транзитивность (1, 2) Î R и (2, 3) Î R влечет (1, 3) Î R. Отметим, что в этом примере R=R-1.

с. Отношение “быть на одном курсе” на множестве студентов факультета;

d. Отношение “иметь одинаковый остаток при делении на 3” на множестве

натуральных чисел;

e. Отношение параллельности на множестве прямых плоскости.

d. Отношение подобия на множестве треугольников и т.п.

 

Считается, что термин “отношение эквивалентности” применяется только в случае, если выполняются следующие три условия:

Ø Каждый элемент эквивалентен самому себе;

Ø Высказывание, что два элемента являются эквивалентными, не требует уточнения, какой из элементов рассматривается первым, а какой вторым;

Ø Два элемента, эквивалентные третьему, эквивалентны между собой.

Для обозначения эквивалентности иногда применяют символ ”~”1.

Тогда общее определение отношения эквивалентности получим, записав три вышеприведенные условия в виде следующих соотношений:

а~а (рефлексивность);

а~bÞb~a (симметричность);

а~b и b~c Þa~c (транзитивность).

Отношение эквивалентности, заданное на множестве А, тесно связано с разбиением множества на классы. Эта определяется следующим утверждением:

Лемма: «Всякое отношение эквивалентности, определенное на множестве А, задает разбиение множества на классы».

Доказательство:

Пусть на множестве А задано отношение эквивалентности «~». Выполним следующее построение. Выберем элемент а1ÎА и образуем класс (подмножество А) А1, состоящий из элемента а1 и всех элементов, эквивалентных а1; затем выберем элемент а2ÏА1 и образуем класс А2, состоящий из а2 и всех элементов, эквивалентных а2 и т.д. получится система классов А1, А2….(возможно бесконечная) такая, что любой элемент из А входит в один класс. Вполне очевидно, что полученная система классов обладает свойствами:

Ø Аi=А;

Ø

Ø .

Построенное разбиение, т.е. система классов, называется системой классов эквивалентности по отношению R.

С другой стороны, любое разбиение А на классы определяет некоторое отношение эквивалентности, а именно, отношение “входить в один и тот же класс данного разбиения”, что утверждается следующей леммой:

Лемма: «Всякое разбиение множества А на классы задает на множестве А отношение эквивалентности»

Доказательство:

Пусть a, b Î A и aRb Û a и b лежат в одном классе разбиения. Тогда для любого а Î К aRa, т.е данное отношение рефлексивно.

Пусть К – некоторый класс разбиения, и a, b Î К. Тогда и b, a Î K, т.е. aRb Þ bRa, что доказывает симметричность отношения элементов данного класса.

Из aRb и bRc следует, что a, b, c Î K. Следовательно aRc что доказывает транзитивность отношения элементов данного класса.

Таким образом доказано, что элементы, определяющие класс разбиения, связаны отношением эквивалентности.

Пример. Разбиение множества натуральных чисел N={1, 2, ….} по отношению “иметь общий остаток от деления на 7” состоит из 7 бесконечных (счетных) классов: первый класс –{0, 7, 14, 21,….} (остаток 0), второй класс –{1, 8, 15, 22,…} (остаток 1), третий класс –{2, 9, 16,….} (остаток 2) ……, седьмой класс – {6, 13, 20, 27,….} (остаток 6).

Пример 5. Отношение “проживание в одном доме” в множестве жителей России образует разбиение населения России.

Множество классов эквивалентности множества А образует фактормножество множества А по отношению эквивалентности и обозначается А|~.

Системой представителей некоторого отношения эквивалентности ~ называется множество, содержащее по одному элементу из каждого класса эквивалентности.

Пример. Пусть на плоскости определена декартова система координат и координаты обозначаются через х и у. Будем говорить, что две точки М1 и М2 эквивалентны, если их абсциссы равны: М12Ûх12.

Класс эквивалентности – прямая, параллельная оси ординат. Фактормножества образованы прямыми на плоскости, параллельными оси ординат. Система представителей может определена точками, лежащими на оси абсцисс, т.е. точками с координатами (х, 0), хÎR.

Другими примерами отношения эквивалентности могут служить равенство и подобие фигур, логические утверждения, выражаемые с помощью оборотов “иметь такое же”, “быть таким же”.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)