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

Суперпозиция бинарных отношений

Свойства суперпозиций бинарных отношений

Цели занятия: изучить понятие отношения на множестве как его некоторые подмножества; научиться осуществлять операции над отношениями; понять принцип суперпозиции отношений.

Роль и место лекции

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

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

1. Отношения на множествах

Определение 1.

Отношение – это один из способов задания взаимосвязей между элементами множеств. Они бывают унарные, бинарные и в общем случае n -арные.

Определение 2.

Унарные (одноместные) отношения на множестве – это наличие какого-то определенного признака R (свойства и т. п.) у элементов a некоторого множества M. Унарное отношение образует некоторое подмножество на множестве, в котором они введены, т. е. .

23

ПРИМЕР 1.

Множество животных одного вида являются подмножеством множества рода животных и т. д. Так {грызуны} {млекопитающие} подмножество задано отношением «класс»

Определение 3.

Соответствие – это способ задания взаимосвязей, взаимодействий между элементами множества (наряду с отношениями). Частными случаями соответствия являются функции, операции, преобразования и др.

Определение  4.

Два множества называются эквивалентными, если для любого элемента а множества А найдется такой элемент b множества В, что .

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

Определение 5.

Бинарное (двухместное) отношение на множестве – это наличие каких-либо взаимосвязей R, которыми характеризуются пары элементов на некотором множестве M. Тогда все пары  элементов из М, между которыми имеет место данное отношение R, образуют подмножество пар из множества всех возможных пар элементов , т. е. , при этом .

Определение  6.

Сокращенное определение. Говорят, что на множестве M задано бинарное отношение , если в M× M выделено некоторое подмножество .

Другими словами, бинарное отношение на множестве M – это подмножество в M× M. Утверждение, что элемент a состоит в отношении  с элементом b, означает, что пара , или

 .                 (1)

ПРИМЕР  2.

1. Отношение делимости в N. Число n состоит в этом отношении с числом m, если n делится на m {(1, 1), (3, 6), (3, 9)…}:. Подмножество R в N², определяющее отношение делимости, имеет вид: R = {(n, m) : : n = km}.

2. Отношение " " в R. Число x состоит в этом отношении с числом y, если x y {(1, 2); (3, 3); (2, 12)…}. Соответствующее подмножество в R² определяется следующим образом: R = {(x, y) : x y}.

3. Отношение равенства в R. Числа x и y состоят в этом отношении, если они равны {(1, 1), (3, 3)…}: R = {(x, y) : x=y}.

4. Отношение {семейной пары} на множестве {люди}.

Определение  7.

Бинарное отношение , заданное на множестве M называется:

- рефлексивным, если a a для a M,

- симметричным, если a b  b a,

- антисимметричным, если (a b) и (b a)  a = b,

- транзитивным, если (a b) и (b с)  a c.

ПРИМЕР 3.

24

1. Отношение " ", заданное на множестве R, является рефлексивным, однако отношение " < ", заданное на том же самом множестве R, не рефлексивно. Докажем второе утверждение. Бинарное отношение " < " это:

" < " =R = {(x, y) : x< y},

означающее, что произвольный элемент  должен удовлетворять неравенству a < a, а это неправда. Следовательно, произвольный элемент a не состоит сам с собой в отношении " < ", и рефлексивности нет. Множество {животные одного вида} рефлексивно.

2. Определим на множестве R следующее бинарное отношение: элементы связаны бинарным отношением , если равны их целые части [x]=[y]. Докажем, что определенное таким образом бинарное отношение  обладает свойством симметричности. Действительно, имеет место следующее соотношение

[x] = [y]  [y] = [x].

Определение  8.

Бинарное отношение , заданное на множестве M, называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно (см. определение 4).

25

ПРИМЕР 4.

Пусть на множестве M={1, 2, 3} задано бинарное отношение ={(1, 2); (2, 1); (1, 1); (2, 2); (3, 3)}. Доказать, что заданное таким образом бинарное отношение  является отношением эквивалентности. Нужно показать, что бинарное отношение  обладает свойствами рефлексивности, симметричности и транзитивности.

1. Необходимо проверить, что для любого элемента a из множества M пара (a, a) принадлежит бинарному отношению . Здесь a = 1, 2, 3 и из определения  видно, что пары (1, 1), (2, 2), (3, 3) принадлежат бинарному отношению .

2. Выполнение условия  видно прямо из определения бинарного отношения .

3. Должно выполняться свойство: .

Действительно: ,   и т. д.

3. Операции над бинарными отношениями

Мы уже знаем, что бинарные отношения являются множествами, и, следовательно, можно говорить о равенстве бинарных отношений и о включении одного бинарного отношения в другое: . На бинарные отношения, заданные на некотором множестве переносятся общие операции над множествами. Пусть  и   – бинарные отношения, заданные на множестве A. Тогда:

- – бинарное отношение в A, пересечение отношений  и ;

- – бинарное отношение в A, объединение отношений  и ;

- – бинарное отношение в A, разность отношений  и ;

- – бинарное отношение в A, дополнение к бинарному отношению  в A, т. е. .

ПРИМЕР 5.

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

тогда между ними имеют место следующие отношения включения: ; ; ; . Последнее бинарное отношение является отношением равенства в Z и т.д.

В биологии отношение на множестве {ареал} может определять подмножество {вид животных}.

4. Суперпозиция бинарных отношений

Определение 9.

26

Суперпозицией (композицией) двух бинарных отношений  и называется бинарное отношение (будем обозначать его как ), определенное следующим образом:  когда в множестве A найдется хотя бы один элемент b, такой, что  и .

Определение 10.

Множество называется связным, если на этом множестве можно определить суперпозицию любых подмножеств.

ПРИМЕР 6.

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

1. = = . Действительно, поскольку , , то ; обратно, если , , то ;

2. = . Рассмотрим произвольную пару , возможны два случая a) ; b) . Рассмотрим случай a) , . В случае b) , . Итак, мы показали, что   и, следовательно, ;

3. .                      

Замечание!!!

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

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

Поскольку  и , получаем, что пара . Теперь надо показать, что пара . Перепишем бинарное отношение  как . Следовательно, , причем для любого n, откуда получаем, что пара , ибо в противном случае , что невозможно. Однако легко показать, что

27

;  =  = .

Здесь E_M – бинарное отношение равенства в множестве M.

5. Свойства суперпозиций бинарных отношений

1. Свойство объединения. Пусть во множестве A заданы бинарные отношения   и , I. Здесь I - конечный или бесконечный набор индексов. Тогда

,  .        (2)

Заметим, что в вышеприведенных соотношениях значки нельзя заменить на .

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

Пусть  и .

2. Свойство ассоциативности. Для любых бинарных отношений , заданных на некотором множестве A, справедливо равенство:

.                         (3)

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

Пусть пара  и . Это означает, что  и и . Итак, мы доказали, что если , то из этого следует, что . Обратное включение доказывается аналогично.

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

3) Суперпозиция обратных отношений.

Определение 11.

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

ПРИМЕР 7.

Пусть на множестве A={0, 1, 2, 3} задано бинарное отношение ={(0, 1); (2, 3); (1, 3)}, тогда = {(1, 0); (3, 2); (3, 1)}.

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

,  .               (4)

Заключение

28

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

- отношение на множестве есть множество;

- бинарные отношения могут быть заданы на декартовом произведении множеств;

- отношения могут быть рефлексивными, симметричными, антисимметричными и транзитивными;

- над отношениями можно делать такие же операции, как и над множествами;

- суперпозиция определяет новое связное множество;

- операция суперпозиции не коммутативна.

Литература

1. Яблонский Я. В. Введение в дискретную математику. – М.: Высшая школа, 2001. - 384 с.

2. Москинова Г.И. «Дискретная математика». – М.: Логос, 2002. – 240 с.

3. Ильин В.А., Позняк Э.Г. «Л инейная алгебра». – М.: Физматлит, 2001.

4. Самсонов Б.Б. и др. «Компьютерная математика». – Ростов-на-Дону: Феникс, 2002. – 512 с.

29

Лекция 4

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

Поделиться: