Отношения. Свойства отношений.

Функция

Рассмотрим некоторое отображение f:ХY. Это отображение называют функцией, если оно одно­значно, т. е. если для любых пар (х₁y₁)f и (х₂y₂)f изx₂= x₁ следует y₂= y₁.

На рис. 1.5, а приведен пример отображения, явля­ющегося функцией. Отображение на рис. 1.5, б функцией не является.

Из определения отображения и из приведенных ранее примеров следует, что элементами множеств Х и Y мо­гут быть объекты любой природы. Однако в задачах компьютерных сетей большой интерес представляют отображения, которые являются однозначными и множество значений которых представляет собой множество вещественных чи­сел R. Однозначное отображение f, определенное выше, называют функцией с вещественными значениями, если .

а) б)

Рис. 1.5. Иллюстрация к понятию функции

Понятие функции является чрезвычайно широким, и изучению отдельных классов функций посвящены многие математические дисциплины (алгебра, тригонометрия и т.п.). Мы рассмотрим только некоторые общие наибо­лее фундаментальные свойства функции, не касаясь свойств конкретных классов.

Значение у в любой из пар (х, y)f называют функ­цией от данного х и записывают в виде y=f(x). Такая запись позволяет вести следующее формальное определе­ние функции:

f={(x, y)=f(x)}. (1.19)

Таким образом, символ f используют при определении Функции в двух смыслах:

f является множеством, элементами которого будут пары (х, y), участвующие в соответствии;

f (x) является обозначением для уУ, соответствую­щего данному хХ.

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

Пусть отображение (X, Г) является отношением. Рас­смотрим элемент уГх. Будем говорить, что элемент у находится в отношении Г к элементу х, и запишем это в виде

уГх. (1.20)

Используя для отображения, заданного на одном множестве, соотношение (X, Г), получаем, что отношение есть пара множеств (X, Г), в которой ГХ². Поскольку элементами множества X² являются упорядоченные пары, то можно сказать, что отношение есть множество упорядоченных пар. Так как каждая пара связывает между собой только два элемента множества X², то такое отношение называют бинарным.

Можно ввести более общее понятие отношения, называя отноше­нием пару множества (X, Г), где ГХ ⁿ. Элементами множества Х ⁿ являются упорядоченные n-ки, что позволяет назвать данное отноше­ние n-арным. В частности, множество упорядоченных троек может быть названо тернарным отношением. В дальнейшем, не оговаривая этого особо под термином «отношение» будем иметь в виду бинарное отно­шение.

Отношения делятся на различные виды в зависимости от того, обладают или не обладают они некоторыми свой­ствами. Рассмотрим шесть основных свойств отношений. При описании этих свойств будем считать, что х, у и z — любые элементы из множества X.

Рефлексивность: хГх истинно; антирефлексивность: хГх ложно; симметричность: хГууГх; антисимметрич­ность: хГу и уГхх=у; несимметричность: если хГу ис­тинно, то уГх ложно; транзитивность: хГу и yГzxГz.

Воспользовавшись описанными свойствами, рассмотрим некоторые важные виды отношений.