Как задать отношение с помощью графа

⇐ Предыдущая57585960616263646566Следующая ⇒

Чтобы определить общее понятие бинарного отношения на множестве, поступим так же, как и в случае с соответствиями, т.е. рассмотрим сначала конкретный пример. Пусть на множестве 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 называется всякое подмножество декартова произведения Х ´ Х.

Так как в дальнейшем мы будем рассматривать только бинарные отношения, то слово «бинарные», как правило, будем опускать. Условимся отношения обозначать буквами R, S, Т, Р и др. Если R - отношения на множестве X, то, согласно определению, R Ì X X. С другой стороны, если задано некоторое подмножество множества X х X, то оно определяет на множестве X некоторое отношение R.

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

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

Построим, например, граф отношений «меньше», заданного на множестве X = {2, 4, 6, 8}. Для этого элементы множества X изобразим


точками (их называют вершинами графа), а отношение «меньше» - стрелкой (рис. 93).

На том же множестве X можно рассмотреть другое отношение - «кратно». Граф этого отношения будет в каждой вершине иметь петлю (стрелку, начало и конец которой совпадают), так как каждое число кратно самому себе (рис. 94). Отношение можно задать при помощи предложения с двумя переменными. Так, например, заданы рассмотренные выше отношения «меньше» и «кратно», причем использована краткая форма предложений «число х меньше числа у» и «число х кратно числу у». Некоторые такие предложения можно записывать, используя символы. Например, отношения «меньше» и «кратно» можно было задать в таком виде: «х < у», «ху». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или х-у = 3). Для отношения R, заданного на множестве X, всегда можно задать отношение R-1, ему обратное, - оно определяется так же, как соответствие, обратное данному. Например, если R - отношение «x меньше у», то обратным ему будет отношение «у больше х».

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

Упражнения

1. Приведите примеры отношений, существующих между:

а) натуральными числами;

б) прямыми на плоскости;

в) треугольниками;

г) множествами.

2. На множестве X = {0, 3, 6, 9, 12, 15, 18} задано отношение R. Перечислите пары чисел, связанных этим отношением и постройтеего граф, если:

а) R - «х больше у в 3 раза»;

б) R-«х больше у на 3».

3. Запишите в виде равенства предложение:

а) Число х меньше у на 2.

б) Число х меньше у в 2 раза.

4. Задает ли на множестве X = {2, 4, 6, 8} какое-либо отношение следующее множество упорядоченных пар:

а) {(2, 2), (4, 4), (6, 6), (8, 8)}; б) {(4, 2), (6, 4), (8, 6), (2, 1)}?

5. На множестве X = {2, 4, 6, 8} рассматриваются отношения «х = у», «х⋮y» и «х больше у на 2». Какое из приведенных ниже подмножеств множества Х ´ Х задает данные отношения:

а) {(4, 2), (6, 2), (8, 2), (6, 4), (8, 4), (8, 6), (2, 2), (4, 4), (6, 6), (8, 8)};

б) {(4, 2), (6, 4), (8, 6)};

в) {(2, 2), (4, 4), (6, 6), (8, 8)}.

6. Отношение «х ≥ у» рассматривается на множестве X. Каким будет его график на координатной плоскости, если:

а) Х= {2,4,6,8};

б) Х- множество натуральных чисел;

в) Х- множество действительных чисел?

7. На множестве отрезков (рис. 95) задано.

отношение Р: «отрезок х длиннее отрезка у».

Постройте граф этого отношения и задайте

различными способами отношение, обратное

данному.

8. Отношение 5 на множестве действительных чисел задано при помощи графика (рис. 96). Постройте график отношения, обратного данному.

9. Семья Волковых состоит из отца Михаила Петровича, матери Веры Ивановны и детей: Толи, Кати, Андрея и Оли. Между членами семьи существуют различные отношения родства: «быть матерью»; «быть дочерью»; «быть братом» и другие. Постройте графы указанных отношений и назовите другие, которые существуют между членами семьи Волковых. Есть ли среди них взаимно обратные?

10.На рисунке 97 дан граф отношения «быть братом» на множестве детей, живущих в одном доме (дети обозначены точками А, Б, В, Г, Д,

             
Е, Ж, 3). Кто из их является девочкой, а кто мальчиком?

 

11. Решите арифметическим методом задачу, предварительно выделив все отношения, которые в ней рассматриваются:

а) На одной полке было в 3 раза больше книг, чем на другой. Когда с первой полки сняли 8 книг, а на другую положили 5 книг, то на второй полке стало на 17 книг меньше, чем на первой. Сколько книг было на каждой полке?

б) На автобазе было на 46 грузовых машин больше, чем автобусов. Сколько грузовых машин было на автобазе, если их было в 3 раза больше, чем автобусов?

 

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

Мы установили, что бинарное отношение на множестве X представляет собой множество упорядоченных пар элементов, принадлежащих декартову произведению X ´ Х. Это математическая сущность всякого отношения. Но, как и любые другие понятия, отношения обладают свойствами. Их удалось выделить, изучая различные конкретные отношения. Свойств достаточно много, в нашем курсе мы будем изучать только некоторые.

Рассмотрим на множестве отрезков, представленных на рис. 98, отношения перпендикулярности, равенства и «длиннее». Построим графы этих отношений (рис. 99) и будем их сравнивать. Видим, что граф отношения равенства отличается от двух других наличием петель в каждой его вершине. Эти петли - результат того, что отношение равенства отрезков обладает свойством: любой отрезок равен самому себе. Говорят, что отношение равенства обладает свойством рефлексивности или просто, что оно рефлексивно.

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-отношение подобия треугольников (если треугольник Р подобен треугольнику Р, то треугольник Р подобен треугольнику сосуществуют отношения, которые свойством симметричности не

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

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

R антисимметрично на

 

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

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

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

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

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

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

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

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

R транзитивно на X <=> (хRу Ù у R z => хRz).

 

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

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

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

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

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

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

К связано на множестве X <=> ( х¹ у => хRу Ú уRх).


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Упражнения

8. Докажите, что отношение R, заданное при помощи графа (рис. 102), рефлексивно, антисимметрично и транзитивно.

9.Докажите, что отношение Т, заданное при помощи графа (рис. 103), симметрично и транзитивно.

10.Сформулируйте условия, при которых отношение свойством рефлексивности не обладает, и докажите, что отношение Т (см. упр. 2) не рефлексивно.

11.Сформулируйте условия, при которых отношение не обладает свойством: а) симметричности; б) антисимметричности; в) транзитивности; г) связанности.

12.Докажите, что отношение Р, граф которого изображен на рисунке 104, не обладает ни свойством симметричности, ни свойством антисимметричности, ни свойством транзитивности.

13.Какими свойствами обладает отношение, граф которого изображен на рисунке 105? Является ли оно рефлексивным? Транзитивным?

14.Какие из следующих утверждений истинны:

а) Отношение «х больше у на 3» антисимметрично на множестве N, так как из того, что х больше у на 3, не следует, что у больше х на 3.

б) Отношение «х больше у на 3» антисимметрично, так как из того, что х больше у на 3, следует, что у не больше х на 3.

в) Отношение «х больше у на 3» антисимметрично, так как из того, что х больше у на 3, следует, что у меньше х на 3.

8. На множестве отрезков задано отношение «короче». Верно ли, что оно антисимметрично и транзитивно? Рефлексивно ли оно?

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

а) «меньше»; б) «меньше на 2»; в) «меньше в 2 раза»?

10. На множестве Х = {а, b, с) задано отношение R = {(а, b), (а, а), (b, b), (с, с), (b, а), (b, с), (с, b)}. Какими свойствами оно обладает?

13.На множестве X - {2, 4, 6, 8, 12} заданы отношения «больше» и «кратно». В чём их сходство и различие?

14.Установите, какое отношение рассматривается в задаче; какие приемы анализа задачи можно использовать:

а) Школьники сделали к карнавалу 15 шапочек для мальчиков, а для девочек в 2 раза больше. Сколько всего карнавальных шапочек они сделали?

б) Второклассники вырезали для елки 26 звездочек, это в 2 раза меньше, чем снежинок. Сколько всего звездочек и снежинок вырезали второклассники?


⇐ Предыдущая57585960616263646566Следующая ⇒


Источник: http://vikidalka.ru/2-79376.html



Рекомендуем посмотреть ещё:


Закрыть ... [X]

Отношение между элементами множеств x и y задано уравнением yx1 - Черника карандашом поэтапно



Как задать отношение с помощью графа Как задать отношение с помощью графа Как задать отношение с помощью графа Как задать отношение с помощью графа Как задать отношение с помощью графа Как задать отношение с помощью графа Как задать отношение с помощью графа Как задать отношение с помощью графа Как задать отношение с помощью графа

Похожие новости