Примеры бинарных отношений. Бинарные отношения, функции, порядок

1. Рефлексивность:

2. Слабая рефлексивность:

3. Сильная рефлексивность:

4. Антирефлексивность:

5. Слабая антирефлексивность:

6. Сильная антирефлексивность:

7. Симметричность:

8. Антисимметричность:

9. Асимметричность:

10. Сильная линейность:

11. Слабая линейность:

12. Транзитивность:

Рефлексивность, свойство бинарных (двуместных, двучленных) отношений, выражающее выполнимость их для пар объектов с совпадающими членами (так сказать, между объектом и его "зеркальным отражением"): отношение R называется рефлексивным, если для любого объекта х из области его определения выполняется xRx. Типичные и наиболее важные примеры рефлексивных отношений: отношения типа равенства (тождества, эквивалентности, подобия и т.п.: любой предмет равен самому себе) и отношения нестрогого порядка (любой предмет не меньше и не больше самого себя). Интуитивные представления о "равенстве" (эквивалентности, подобии и т.п.), очевидным образом наделяющие его свойствами симметричности и транзитивности, "вынуждают" и свойство Р., поскольку последнее свойство следует из первых двух. Поэтому многие употребительные в математике отношения, по определению Р. не обладающие, оказывается естественным доопределить таким образом, чтобы они становились рефлексивными, например, считать, что каждая прямая или плоскость параллельна самой себе, и т.п.

Глава 1. Элементы теории множеств

1.1 Множества

Наиболее простая структура данных, используемая в математике, имеет место в случае, когда между отдельными изолированными данными отсутствуют какие-либо взаимосвязи. Совокупность таких данных представляет собой множество . Понятие множества является неопределяемым понятием. Множество не обладает внутренней структурой. Множество можно представить себе как совокупность элементов, обладающих некоторым общим свойством. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:

Должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности.

Должно существовать правило, позволяющее отличать элементы друг от друга. (Это, в частности, означает, что множество не может содержать двух одинаковых элементов).

Множества обычно обозначаются заглавными латинскими буквами. Если элемент

Если каждый элемент множества

Подмножество

Используя понятие множества можно построить более сложные и содержательные объекты.

1.2 Операции над множествами

Основными операциями над множествами являются объединение , пересечение и разность .

Определение 1 . Объединением

Определение 2 . Пересечением двух множеств называется новое множество

Определение 3 . Разностью двух множеств называется новое множество

Если класс объектов, на которых определяются различные множества обозначить

1.3 Декартово произведение множеств

Одним из способов конструирования новых объектов из уже имеющихся множеств является декартово произведение множеств .

Определение 4 . Декартовым (прямым) произведением множеств

Определение 5 . Степенью декартового произведения

Замечание. Если все множества

1.4 Отношение

Определение 6 . Подмножество

Определение 7 . Мощность множества кортежей, входящих в отношение

Замечание. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц . Сам термин "реляционное представление данных", впервые введенный Коддом , происходит от термина relation , понимаемом именно в смысле этого определения.

Т. к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых , все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей { (1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000) } можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.

В противоположность этому рассмотрим множество { (1), (1,2), (1, 2,3) }, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в

Понятие отношения на множестве

Чтобы определить общее понятие бинарного отношения на множестве, поступим так же, как и в случае с соответствиями,

т.е. рассмотрим сначала конкретный пример. Пусть на множестве X = {2, 4, 6, 8} задано отношение «меньше». Это означает, что для любых двух чисел из множества X можно сказать, какое из них меньше: 2 < 4, 2 < 6, 2 < 8, 4 < 6, 4 < 8, 6 < 8. Полученные неравенства можно записать иначе, в виде упорядоченных пар: (2, 4), (2, 6), (2, 8), (4, 6), (4, 8), (6, 8). Но все эти пары есть элементы декартова произведения X х X, поэтому об отношении «меньше», заданном на множестве X, можно сказать, что оно является подмножеством множества X х X.

Вообще бинарные отношения на множестве X определяют следующим способом:

Определение. Бинарным отношением на множестве X называется всякое подмножество декартова произведения X х X.

Так как в дальнейшем мы будем рассматривать только бинарные отношения, то слово «бинарные», как правило, будем опускать.

Условимся отношения обозначать буквами R, S, Т, Р и др.

Если R - отношения на множестве X, то, согласно определению, R X х X. С другой стороны, если задано некоторое подмножество множества X х X, то оно определяет на множестве X некоторое отношение R.

Утверждение о том, что элементы х и у находятся в отношении R, можно записывать так: (х, у) R или x R y. Последняя запись читается: «Элемент х находится в отношении R с элементом у».

Отношения задают так же, как соответствия. Отношение можно задать, перечислив пары элементов множества X, находящиеся в этом отношении. Формы представления таких пар могут быть различными - они аналогичны формам задания соответствий. Отличия касаются задания отношений при помощи графа.

Построим, например, граф отношений «меньше», заданного на множестве Х= (2, 4, 6, 8}. Для этого элементы множества X изобразим точками (их называют вершинами графа), а отношение «меньше» - стрелкой (рис. 1).

На том же множестве X можно рассмотреть другое отношение - «кратно». Граф этого отношения будет в каждой вершине иметь петлю (стрелку, начало и конец которой совпадают), так как каждое число кратно самому себе (рис. 2).

Отношение можно задать при помощи предложения с двумя переменными. Так, например, заданы рассмотренные выше отношения «меньше» и «кратно», причем использована краткая форма предложений «число х меньше числа у» и «число х кратно числу у». Некоторые такие предложения можно записывать, используя символы. Например, отношения «меньше» и «кратно» можно было задать в таком виде: «х<у», «х у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или х – у = 3).

Для отношения R, заданного на множестве X, всегда можно задать отношение R -1 , ему обратное, - оно определяется так же, как соответствие, обратное данному. Например, если R - отношение «х меньше у», то обратным ему будет отношение «у больше х».

Понятием отношения, обратного данному, часто пользуются при начальном обучении математике. Например, чтобы предупредить ошибку в выборе действия, с помощью которого решается задача: «У Пети 7 карандашей, что на 2 меньше, чем у Бори. Сколько карандашей у Бори?» - ее переформулируют: «У Пети 7 карандашей, а у Бори на 2 больше. Сколько карандашей у Бори?» Видим, что переформулировка свелась к замене отношения «меньше на 2» обратным ему отношением «больше на 2».

Свойства отношений

Мы установили, что бинарное отношение на множестве X представляет собой множество упорядоченных пар элементов, принадлежащих декартову произведению ХхХ. Это математическая сущность всякого отношения. Но, как и любые другие понятия, отношения обладают свойствами. Их удалось выделить, изучая различные конкретные отношения. Свойств достаточно много, в нашем курсе мы будем изучать только некоторые. Рассмотрим на множестве отрезков, представленных на рис. 3, отношения перпендикулярности, равенства и «длиннее». Построим графы этих отношений (рис. 4) и будем их сравнивать.

Видим, что граф отношения равенства отличается от двух других наличием петель в каждой его вершине. Эти петли - результат того, что отношение равенства отрезков обладает свойством: любой отрезок равен самому себе. Говорят, что отношение равенства обладает свойством рефлексивности или просто, что оно рефлексивно .

Определение. Отношение R на множестве X называется рефлексивным, если о каждом элементе множества X можно сказать, что он находится в отношении R с самим собой.

R рефлексивно на Х <=> xRx для любого х X

Если отношение R рефлексивно на множестве X, то в каждой вершине графа данного отношения имеется петля. Справедливо и обратное утверждение: граф, каждая вершина которого имеет петлю, задает отношения, обладающие свойством рефлексивности.

Примеры рефлексивных отношений:

Отношение «кратно» на множестве натуральных чисел (каждое натуральное число кратно самому себе);

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

Существуют отношения, которые свойством рефлексивности на обладают. Таким, например, является отношение перпендикулярности на множестве отрезков: нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе. Поэтому на графе отношения перпендикулярности (рис. 4) нет ни одной петли. Не обладает свойством рефлексивности и отношение «длиннее» для отрезков.

Обратим теперь внимание на графы отношений перпендикулярности и равенства отрезков. Они «похожи» тем, что если есть одна стрелка, соединяющая пару элементов, то обязательно есть и другая, соединяющая те же элементы, но идущая в противоположном направлении. Эта особенность графа отражает те свойства, которыми обладают отношения параллельности и равенства отрезков:

Если один отрезок перпендикулярен другому отрезку, то этот «другой» перпендикулярен первому;

Если один отрезок равен другому отрезку, то этот «другой» равен первому.

Про отношения перпендикулярности и равенства отрезков говорят, что они обладают свойством симметричности или, просто симметричны.

Определение. Отношение R на множестве X называется симметричным, если выполняется условие: из того, что элемент х находится в отношении R с элементом у, следует, что и элемент у находится в отношении R с элементом х.

Используя символы, это отношение можно записать в таком виде:

R симметрично на X <=> (xRy => yRx)

Граф симметричного отношения обладает особенностью: вместе с каждой стрелкой, идущей от х к у, граф содержит и стрелку, идущую от у к х. Справедливо и обратное утверждение. Граф, содержащий вместе с каждой стрелкой, идущей от х к у, и стрелку, идущую от у к х, является графом симметричного отношения.

В дополнение к рассмотренным двум примерам симметричных отношений присоединим еще такие:

Отношение параллельности на множестве прямых (если прямая х параллельна прямой у, то и прямая у параллельна прямой х);

Отношение подобия треугольников (если треугольник F подобен треугольнику Р, то треугольник Р подобен треугольнику F).

Существуют отношения, которые свойством симметричности не обладают. Таким, например, является отношение «длиннее» на множестве отрезков. Действительно, если отрезок х длиннее отрезка у, то отрезок у не может быть длиннее отрезка х. Про отношения «длиннее» говорят, что оно обладает свойством антисимметричности или просто антисимметрично.

Определение. Отношение R на множестве X называется антисимметричным, если для различных элементов х и у из множества X выполнено условие: из того, что х находится в отношении R с элементом у, следует, что элемент у в отношении R с элементом х не находится .

антисимметрично на X <=> (xRy и х≠у => )

Граф антисимметричного отношения обладает особенностью: если две вершины графа соединены стрелкой, то эта стрелка только одна. Справедливо и обратное утверждение: граф, вершины которого соединены только одной стрелкой, есть граф антисимметричного отношения.

Кроме отношения «длиннее» на множестве отрезков свойством антисимметричности, например, обладают:

Отношение «больше» для чисел (если х больше у, то у не может быть больше х);

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

Существуют отношения, не обладающие ни свойством симметричности, ни свойством антисимметричности. Рассмотрим, например, отношение «быть сестрой» на множестве детей одной семьи. Пусть в семье трое детей: Катя, Маша и Толя. Тогда граф отношения «быть сестрой» будет таким, как на рисунке 5. Он показывает, что данное отношение не обладает ни свойством симметричности, ни свойством антисимметричности.

Обратим внимание еще раз на одну особенность графа отношения «длиннее» (рис. 4). На нем можно заметить: если стрелки проведены от е к а и от а к с , то есть стрелка от е к с ; если стрелки приведены от е к b и от b к с , то есть стрелка и от е к с и т.д. Эта особенность графа отражает важное свойство отношения «длиннее»: если первый отрезок длиннее второго, а второй - длиннее третьего, то первый - длиннее третьего. Говорят, что это отношение обладает свойством транзитивности или просто транзитивно.

Определение. Отношение R на множестве X называется транзитивным, если выполняется условие: из того, что элемент х находится в отношении R с элементом у и элемент у находится в отношении R с элементом z, следует, что элемент х находится в отношении R с элементом z.

Используя символы, это определение можно записать в таком виде:

R транзитивно на X <=> (xRy и yRz => xRz)

Граф транзитивного отношения с каждой парой стрелок, идущих от х к у и у к z , содержит стрелку, идущую от х к z . Справедливо и обратное утверждение.

Кроме отношения «длиннее» на множестве отрезков свойством транзитивности обладает отношение равенства: если отрезок х равен отрезку у и отрезок у равен отрезку z , то отрезок х равен отрезку z . Это свойство отражено и на графе отношения равенства (рис. 4)

Существуют отношения, которые свойством транзитивности не обладают. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку d, а отрезок d перпендикулярен отрезку b, то отрезки а и b не перпендикулярны!

Рассмотрим еще одно свойство отношений, которое называют свойством связанности, а отношение, обладающее им, называют связанным.

Определение. Отношение R на множестве X называется связанным, если для любых элементов х и у из множества X выполняется условие: из того, что х и у различны, следует, что либо х находится в отношении R с элементом у, либо элемент у находится в отношении R с элементом х.

Используя символы, это определение можно записать в таком виде:

R связанно на множестве X <=> (х≠у xRy или yRx)

Например, свойством связанности обладают отношения «больше» для натуральных чисел: для любых различных чисел х и у можно утверждать, что либо х> у, либо у > х.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

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

Выделенные свойства позволяют анализировать различные отношения с общих позиций - наличия (или отсутствия) у них тех или иных свойств.

Так, если суммировать все сказанное об отношении равенства, заданном на множестве отрезков (рис. 4), то получается, что оно рефлексивно, симметрично и транзитивно. Отношение «длиннее» на том же множестве отрезков антисимметрично и транзитивно, а отношение перпендикулярности-симметрично, но оно не обладает свойствами рефлексивности и транзитивности. Все эти отношения на заданном множестве

отрезков связанными не являются.

Задача 1. Сформулировать свойства отношения R, заданного при помощи графа (рис. 6).

Решение. Отношение R- антисимметрично, так как вершины графа соединяются только одной стрелкой.

Отношение R - транзитивно, так как с парой стрелок, идущих от b к а и от а к с , на графе есть стрелка, идущая от b к с .

Отношение R - связанно, так как любые две вершины соединены стрелкой.

Отношение R свойством рефлексивности не обладает, так как на графе есть вершины, в которых петли нет.

Задача 2. Сформулировать свойства отношения «больше в 2 раза», заданного на множестве натуральных чисел.

Решение. «Больше в 2 раза» - это краткая форма отношения «число х больше числа у в 2 раза». Это отношение антисимметрично, так как выполняется условие: из того, что число х больше числа у в 2 раза, следует, что число у не больше числа х в 2 раза.

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

Заданное отношение не транзитивно, так как из того, что число х больше числа у на 2, а число у больше числа z на 2, следует, что число х не может быть больше числа z на 2.

Это отношение на множестве натуральных чисел свойством связанности не обладает, так как существуют пары таких чисел х и у, что ни число не больше числа у в два раза, ни число у не больше х в 2 раза. Например, это числа 7 и 3,5 и 8 и др.

Основы дискретной математики.

Понятие множества. Отношение между множествами.

Множество – совокупность объектов, обладающих определенным свойством, объединенных в единое целое.

Объекты, составляющие множество называются элементами множества. Для того чтобы некоторую совокупность объектов можно было называть множеством должны выполняться следующие условия:

· Должно существовать правило, по которому моно определить принадлежит ли элемент к данной совокупности.

· Должно существовать правило, по которому элементы можно отличить друг от друга.

Множества обозначаются заглавными буквами, а его элементы маленькими. Способы задания множеств:

· Перечисление элементов множества. - для конечных множеств.

· Указание характеристического свойства .

Пустым множеством – называется множество, не содержащее ни одного элемента (Ø).

Два множества называются равными, если они состоят из одних и тех же элементов. , A=B

Множество B называется подмножеством множества А ( , тогда и только тогда когда все элементы множества B принадлежат множеству A .

Например: , B =>

Свойство:

Примечание: обычно рассматривают подмножество одного и того е множества, которое называется универсальным (u). Универсальное множество содержит все элементы.

Операции над множествами.

2.Пересечением 2-х множеств называется новое множество, состоящее из элементов, одновременно принадлежат и первому и второму множеству.

Н-р: , ,

Свойство: операции объединения и пересечения.

· Коммутативность.

· Ассоциативность. ;

· Дистрибутивный. ;

Бинарные отношения и их свойства.

Пусть А и В это множества производной природы, рассмотрим упорядоченную пару элементов (а, в) а ϵ А, в ϵ В можно рассматривать упорядоченные «энки».

(а 1 , а 2 , а 3 ,…а n) , где а 1 ϵ А 1 ; а 2 ϵ А 2 ; …; а n ϵ А n ;

Декартовым (прямым) произведением множеств А 1 , А 2 , …, А n , называется мн-во, которое состоит из упорядоченных n k вида .

Н-р: М = {1,2,3}

М× М= М 2 = {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.

Подмножества декартова произведения называется отношением степени n или энарным отношением. Если n =2, то рассматривают бинарные отношения. При чем говорят, что а 1 , а 2 находятся в бинарном отношении R , когда а 1 R а 2.

Бинарным отношением на множестве M называется подмножество прямого произведения множества n самого на себя.

М× М= М 2 = {(a, b )| a, b ϵ M } в предыдущем примере отношение меньше на множестве М порождает следующее множество: {(1,2);(1,3); (2,3)}

Бинарные отношения обладают различными свойствами в том числе:

· Рефлексивность: .

· Антирефлексивность (иррефлексивность): .

· Симметричность: .

· Антисимметричность: .

· Транзитивность: .

· Асимметричность: .

Виды отношений.

· Отношение эквивалентности;

· Отношение порядка.

v Рефлексивное транзитивное отношение называется отношением квазипорядка.

v Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.

v Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.

v Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.

Связанные определения

Свойства отношений

Бинарные отношения могут обладать различными свойствами, такими как

Виды отношений

• Рефлексивное транзитивное отношение называется отношением квазипорядка.
• Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности .
• Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка .
• Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка .
• Полное антисимметричное (для любых x, y выполняется xRy или yRx) транзитивное отношение называется отношением линейного порядка.
• Антирефлексивное асимметричное отношение называется отношением доминирования.

Виды двухместных отношений

• Обратное отношение [уточнить ] (отношение, обратное к R) - это двухместное отношение, состоящее из пар элементов (у, х), полученных перестановкой пар элементов (х, у) данного отношения R. Обозначается: R −1 . Для данного отношения и обратного ему верно равенство: (R −1) −1 = R.
• Взаимо-обратные отношения (взаимообратные отношения) - отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого - областью значений другого.
• Рефлексивное отношение - двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого х этого множества элемент х на­ходится в отношении R к самому себе, то есть для любого элемента х этого множества имеет место xRx. Примеры рефлексивных отношений: равенство , одновременность , сходство.
• Антирефлексивное отношение (Иррефлексивное отношение, отметим, что также как антисимметричность не совпадает с несимметричностью иррефлексивность не совпадает с нерефлексивностью.) - двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого элемента х этого множества неверно, что оно находится в отношении R к самому себе (неверно, что xRx), то есть возможен случай, что элемент множества не находится в отно­шении R к самому себе. Примеры нерефлексвных отношений: «заботиться о», «развлекать», «нервировать».
• Транзитивное отношение - двухместное отношение R, оп­ределенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz следует xRz (xRy&yRzxRz). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
• Нетранзитивное отношение [уточнить ] - двухместное отношение R, оп­ределенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz ((xRy&yRzxRz)). Пример нетранзитивного отношения: «x отец y»
• Симметричное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых элементов х и у этого множества из того, что х находится к у в отношении R (xRy), следует, что и у находится в том же отношении к х (уRx). Примером симметричных отношений могут быть равенство (=), отношение эквивалентности , подобия , одновременности, некоторые отношения родства (например, отношение братства).
• Антисимметричное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy и xR −1 y следует х = у (то есть R и R −1 выполняются одновременно лишь для равных между собой членов).
• Асимметричное отношение [уточнить ] - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy следует yRx. Пример: отношение «больше» (>) и «меньше» (<).
• Отношение эквивалентности (отношение тождества [уточнить ] , отношение типа равенства) - двухместное отношение R между предметами х и у в предметной области D, удовлетворяющее следующим аксиомам (условиям): Таким образом, отношение типа равенства является одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, обмениваемость товаров на рынке, подобие , одновременность . Пример отношения, которое удовлетворяет аксиоме (3), но не удовлетворяет аксиомам (1) и (2): «больше».
• Отношения порядка - отношения, обладающие только некоторыми из трёх свойств отношения эквивалентности. В частности, отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует «нестрогий» порядок. Отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») - «строгий» порядок.
• Функция - двухместное отношение R , определенное на некотором мно­жестве, отличающееся тем, что каждому значению x отно­шения xRy y . Пример: «y отец x ». Свойство функциональности отно­шения R записывается в виде аксиомы: (xRy и xRz )→(y ≡z ). Поскольку каждому значению x в выражениях xRy и xRz соответствует одно и то же значение, то y и z совпадут, окажутся одними и теми же. Функциональное отношение однозначно, поскольку каждому значению x отношения xRy соответствует лишь одно-единственное значение y , но не наоборот.
• Биекция (одно-однозначное отношение) - двухместное отношение R , определенное на некотором мно­жестве, отличающееся тем, что в нём каждому значению х соответствует единственное значение у , и каждому значению у соответствует единственное значение х . Одно-однозначное отношение является частным случаем однозначного отношения.
• Связанное отношение - это двухместное отношение R , определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов х и у из этого множества, одно из них находится в отношении R к другому (то есть выполнено одно из двух соотношений: xRy или yRx ). Пример: отношение «меньше» (<).

Операции над отношениями

Так как отношения, заданные на фиксированной паре множеств , , суть подмножества множества , то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных ,

Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.

Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрого порядка, а их пересечение пусто.

Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом.

Если , то обратным отношением называется отношение , определённое на паре , и состоящее из тех пар , для которых . Например, .

Пусть теперь , . Произведением отношений , называется отношение такое, что

Если , и , то произведение отношений не определено. Если же отношения рассматривать определённые на каком-то множестве , то такой ситуации не возникает.

Например, рассмотрим отношение строгого порядка определённого на множестве натуральных чисел. Несложно заметить, что

Бинарные отношения и называются перестановочными, если . Несложно заметить, что для любого бинарного отношения , определённого на , , где символом обозначено равенство, определённое на . Однако равенство не всегда справедливо.

Имеют место следующие тождества:

Отметим, что аналоги последних двух тождеств для не имеют места.

Некоторые свойства отношения можно определить, используя операции над отношениями:

См. также

Литература

• А. И. Мальцев. Алгебраические системы. - М .: Наука, 1970.

Wikimedia Foundation . 2010 .

Смотреть что такое "Бинарное отношение" в других словарях:

Бинарное отношение - . Иначе: двуместное или двойственное. «Бинарным отношением на множестве X» называется подмножество упорядоченных пар элементов из X. Примерами Б.о. являются равенство (=), неравенства (< или >), отношение включения A Ì B.… … Экономико-математический словарь

бинарное отношение - Иначе: двуместное или двойственное. «Бинарным отношением на множестве X» называется подмножество упорядоченных пар элементов из X. Примерами Б.о. являются равенство (=), неравенства (), отношение включения A ? B. В широком смысле слова… … Справочник технического переводчика

Двуместный предикат на заданном множестве. Под Б. о. иногда понимают подмножество множества упорядоченных пар (а, 6) элементов заданного множества А. Б. о. частный случай отношения. Пусть. Если, то говорят, что элемент находится в бинарном… … Математическая энциклопедия

В логике то, что в отличие от свойства характеризует не отдельный предмет, а пару, тройку и т.д. предметов. Традиционная логика не рассматривала О.; в современной логике О. пропозициональная функция от двух или большего числа переменных. Бинарным … Философская энциклопедия

отношение - ОТНОШЕНИЕ множество упорядоченных п ок индивидов (где п > 1), т.е. двоек, троек и т.д. Число п называется «местностью», или «арностью», О. и, соответственно, говорят о n местном (п арном) О. Так, например, двуместное О. называют… … Энциклопедия эпистемологии и философии науки

В теории потребления это формальное описание способности потребителя сравнивать (упорядочивать по желательности) разные наборы товаров (потребительские наборы). Чтобы описать отношение предпочтения, не обязательно измерять желательность… … Википедия

У этого термина существуют и другие значения, см. Отношение. Отношение математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Отношения обычно классифицируются по количеству связываемых объектов … Википедия

У этого термина существуют и другие значения, см. Отношение. Отношение в логике первого порядка двух и более аргументный предикат (многоместный предикат), двух и более предикатное свойство. Знак отношения: R.[уточнить] В терминах отношений… … Википедия

У этого термина существуют и другие значения, см. Эквивалентность. Отношение эквивалентности () на множестве это бинарное отношение, для которого выполнены следующие условия: Рефлексивность: для любого в, Симметричность: если … Википедия

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Бинарное отношение на мно … Википедия

Лекция 3.

п.3. Отношения на множествах. Свойства бинарных отношений.

3.1. Бинарные отношения .

Когда говорят о родстве двух людей, например, Сергей и Анна, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Сергей, Анна) отличается от других упорядоченных пар людей тем, что между Сергеем и Анной есть некое родство (кузина, отец и т. д.).

В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A ´B ) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S ´K можно выделить большое подмножество упорядоченных пар (s , k ), обладающих свойством: студент s слушает курс k . Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.

Для строгого математического описания любых связей между элементами двух множеств введем понятие бинарного отношения.

Определение 3.1. Бинарным (или двухместным ) отношением r между множествами A и B называется произвольное подмножество A ´B , т. е.

В частности, если A= B (то есть rÍA 2), то говорят, что r есть отношение на множестве A.

Элементы a и b называются компонентами (или координатами ) отношения r.

Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит : r, t, j, s, w и т. д.

Определение 3.2. Областью определения D r={a | $ b , что a rb } (левая часть). Областью значений бинарного отношения r называется множество R r={b | $ a , что a rb } (правая часть).

Пример 3. 1. Пусть даны два множества A ={1; 3; 5; 7} и B ={2; 4; 6}. Отношение зададим следующим образом t={(x ; y )ÎA ´B | x+ y =9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере D t={3; 5; 7} и R t= B ={2; 4; 6}.

Пример 3. 2. Отношение равенства на множестве действительных чисел есть множество r={(x ; y ) | x и y – действительные числа и x равно y }. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, D r= R r.

Пример 3. 3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j={(x ; y )ÎA ´B | y – цена x } – отношение множеств A и B .

Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t={(x ; y )ÎA ´B | x+ y =9}, а потом записано в виде t={(3; 6), (5;4), (7;2)}. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.

Способы задания отношений:

1) с помощью подходящего предиката;

2) множество упорядоченных пар;

3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом , точки же, изображающие элементы множеств, принято называть вершинами графа .

4) в виде матрицы: пусть A ={a 1, a 2, …, an } и B ={b 1, b 2, …, bm }, r – отношение на A ´B . Матричным представлением r называется матрица M =[mij ] размера n ´m , определенная соотношениями

.

Кстати, матричное представление является представлением отношения в компьютере.

Пример 3. 4. Пусть даны два множества A ={1; 3; 5; 7}и B ={2; 4; 6}. Отношение задано следующим образом t={(x ; y ) | x+ y =9}. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.

Решение. 1) t={(3; 6), (5; 4), (7; 2)} - есть задание отношения как множества упорядоченных пар;

2) соответствующий ориентированный граф показан на рисунке.

https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,

Пример 3. 5 . Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M :

,

где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.

Рассмотрим информационный обмен между устройствами mi и mj , которые находятся в отношении r, если из устройства mi поступает информация в устройство mj .

Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:

Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:

Матричное представление этого бинарного отношения имеет вид:

. ,

Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.

Введем обобщенное понятие отношения.

Определение 3.3. n-местное (n -арное ) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей )

rÍA 1´…´An ={(a 1, …, an )| a 1ÎA 1Ù … Ùan ÎAn }

Многоместные отношения удобно задавать с помощью реляционных таблиц . Такое задание соответствует перечислению множества n -к отношения r. Реляционные таблицы широко используются в компьютерной практике в реляционных базах данных . Заметим, что реляционные таблицы нашли применение в повседневной практике. Всевозможные производственные, финансовые, научные и другие отчеты часто имеют форму реляционных таблиц.

Слово «реляционная » происходит от латинского слова relation , которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).

Определение 3.4. Пусть rÍA ´B есть отношение на A ´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A ´B , которое определяется следующим образом:

r-1={(b , a ) | (a , b )Îr}.

Определение 3.5. Пусть r ÍA ´B есть отношение на A ´B, а s ÍB ´C – отношение на B ´C. Композицией отношений s и r называется отношение t ÍA ´C ,которое определяется следующим образом:

t=s◦r= {(a , c )| $ b Î B, что (a , b )Îr и (b , c )Îs}.

Пример 3. 6 . Пусть , и C ={, !, d, à}. И пусть отношение r на A ´B и отношение s на B ´C заданы в виде:

r={(1, x ), (1, y ), (3, x )};

s={(x ,), (x , !), (y , d), (y , à)}.

Найти r-1 и s◦r, r◦s.

Решение. 1) По определению r-1={(x , 1), (y , 1), (x , 3)};

2) Используя определение композиции двух отношений, получаем

s◦r={(1,), (1, !), (1, d), (1, à), (3,), (3, !)},

поскольку из (1, x )Îr и (x ,)Îs следует (1,)Îs◦r;

из (1, x )Îr и (x , !)Îs следует (1, !)Îs◦r;

из (1, y )Îr и (y , d)Îs следует (1, d)Îs◦r;

из (3, x )Îr и (x , !)Îs следует (3, !)Îs◦r.

Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:

2) ;

3) - ассоциативность композиции.

Доказательство. Свойство 1 очевидно.

Докажем свойство 2. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементов. Пусть (a ; b ) Î (s◦r)-1 Û (b ; a ) Î s◦r Û $ c такое, что (b ; c ) Î r и (c ; a ) Î s Û $ c такое, что (c ; b ) Î r-1 и (a ; c ) Î s-1 Û (a ; b ) Î r -1◦s -1.

Свойство 3 доказать самостоятельно.

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

Рассмотрим специальные свойства бинарных отношений на множестве A .

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

1. Отношение r на A ´A называется рефлексивным , если (a ,a ) принадлежит r для всех a из A .

2. Отношение r называется антирефлексивным , если из (a ,b )Îr следует a ¹b .

3. Отношение r симметрично , если для a и b , принадлежащих A , из (a ,b )Îr следует, что (b ,a )Îr.

4. Отношение r называется антисимметричным , если для a и b из A , из принадлежности (a ,b ) и (b ,a ) отношению r следует, что a =b .

5. Отношение r транзитивно , если для a , b и c из A из того, что (a ,b )Îr и (b ,c )Îr, следует, что (a ,c )Îr.

Пример 3. 7. Пусть A ={1; 2; 3; 4; 5; 6}. На этом множестве задано отношение rÍA 2, которое имеет вид: r={(1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)}. Какими свойствами обладает данное отношение?

Решение. 1) Это отношение рефлексивно, так как для каждого a ÎA , (a ; a )Îr.

2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.

3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:

4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.

5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.

Как по матрице представления

определить свойства бинарного отношения

1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.

.

2. Антирефлексивность: на главной диагонали все нули.

3. Симметричность: если .

4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.

.

Операция «*» выполняется по следующему правилу: , где , .

5. Транзитивность: если . Операция «◦» выполняется по обычному правилу умножения, при этом надо учитывать: .

3.3 Отношение эквивалентности. Отношение частичного порядка.

Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве (одинаковости) двух элементов множества.

Определение 3.6. Отношение r на A есть отношение эквивалентности , если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности a rb часто обозначается: a ~ b .

Пример 3. 8 . Отношение равенства на множестве целых чисел есть отношение эквивалентности.

Пример 3. 9 . Отношение «одного роста» есть отношение эквивалентности на множестве людей X .

Пример 3. 1 0 . Пусть ¢ - множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (m Î¥) и запишем , если равны остатки этих чисел от деления их на m , т. е. разность (x -y ) делится на m .

Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:

это отношение рефлексивно, т. к. для "x ΢ имеем x -x =0, и, следовательно, оно делится на m ;

это отношение симметрично, т. к. если (x -y ) делится на m , то и (y -x ) тоже делится на m ;

это отношение транзитивно, т. к. если (x -y ) делится на m , то для некоторого целого t 1 имеем https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, отсюда , т. е. (x -z ) делится на m .

Определение 3.7. Отношение r на A есть отношение частичного порядка , если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.

Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях считать, что один элемент множества превосходит другой.

Пример 3. 11 . Отношение x £y на множестве действительных чисел есть отношение частичного порядка. ,

Пример 3. 1 2 . Во множестве подмножеств некоторого универсального множества U отношение A ÍB есть отношение частичного порядка.

Пример 3. 1 3 . Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.

Прообразом отношения частичного порядка является интуитивное понятие отношения предпочтения (предшествования). Отношение предпочтения выделяет класс задач, которые можно объединить, как задача о проблеме выбора наилучшего объекта .

Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве A и определить наилучшие объекты.

Отношение предпочтения P , которое можно определить как «aPb , a , b ÎA Û объект a не менее предпочтителен, чем объект b » является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a , то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.

Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование , т. е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.

Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.