Отношения и функции

Отношение является фундаментальным понятием дискретной математики, которое используют для обозначения связи между объектами или понятиями. Например, отношение включения элемента во множество, отношение включения подмножества во множество, отношение параллельности и перпендикулярности прямых, отношение равенства чисел и множеств. Общим для всех отношений является то, что они ставят в соответствие друг другу объекты из разных или одного и того же множества. В общем случае отношение можно определить как некоторое утверждение, относительно которого можно определить, является ли оно истинным или ложным. В дискретной математике такое утверждение называется предикатом. Например, предикат x>y может быть истинным или ложным в зависимости от того, какие значения примут входящие в него переменные x и y. Понятие предиката непосредственно вытекает из понятия отношения. Если предикат устанавливает какое- либо соответствие между двумя объектами, то эту пару объектов можно рассматривать как элемент декартова произведения двух множеств, элементами которых и являются эти объекты. В силу последнего обстоятельства объекты, входящие в пары, могут принимать различные сочетания значений. При некоторых из них предикат будет истинным, при других ложным. Подмножество декартова произведения двух множеств, для каждого из элементов которого данный предикат будет истинным, называется двуместным (бинарным) отношением между элементами двух множеств.

В общем случае n - местным отношением между элементами множеств А₁, A₂,..., A_n называется любое подмножество декартова произведения этих множеств. Соответственно бинарное отношение - это любое подмножество декартова произведения двух множеств (возможно, одного и того же множества). При n =1 отношение называется одноместным или унарным и обозначает просто свойство на множестве. Например, r={x | х положительное целое число} задает множество положительных целых чисел.

Как и любое множество, отношения обозначают прописными буквами латинского алфавита. Однако, иногда бывает удобнее использовать для обозначения отношений строчные буквы латинского или греческого алфавита. Будем обозначать n - местное отношение между элементами множеств А₁, А₂,..., А _n как r⁽ⁿ⁾ Í А₁´А₂´...´А_n.

Наиболее часто встречаются бинарные отношения вида r Í А´В или r Í А². В последнем случае множества А называется несущим множеством, на котором задано отношение r. С каждым бинарным отношением связывают два множества: область определения dom r и область значений rng r, которые определяются как проекции отношения r на первую и вторую координаты соответственно, т.е. dom r ={x| $y: (x,y) Î r}, rng r={x | $у:)(у,х) Î r}. Очевидно, каждое бинарное отношение задано на множестве (dom r È rng r).

Для обозначения бинарных отношений r Î А² часто используют следующие записи:

· хrу, читается "х находится в отношении r с у";

· (х,у) Î r, читается "элемент (х,у) принадлежит отношению r";

· у = r(х).

Отношение является множеством, следовательно, к нему применимы любые операции, определенные для множеств. Кроме того, для отношений определены также следующие операции:

· обратное отношение r^-1, которое определяется как r^-1={(x,y) | (y,x) Îr}. Например, для отношения хrу Û х ³ у, заданного на множестве А={1,2,3}, r = {(1,1), (2,1), (2,2), (3,1), (3,2), (3,3)} обратное отношение получится простой перестановкой элементов в каждой паре в отношении r. r^-1 = {(1,1), (1,2), (2,2), (1,3), (2,3), (3,3)};

· дополнение отношения `r, которое определяется как дополнение r до универсального отношения: `r = {(x,y) | (x,y) Î А²\ r;

· композиция отношений r·g, которая определяется следующим образом

r·g = {(x,y)| $z: (x,z) Î r, (z,y) Î g}.

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

1. Задание отношения перечислением элементов.

2. Графиком отношения.

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

4. Графом отношения.

5. Фактор - множеством, в котором перечисляются окрестности каждого из элементов несущего множества.

Рассмотрим различные способы на примере отношения хrу Û x > y, x,y Î {1, 2, 3, 4, 5}.

1. Перечислением элементов: r = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (5,4)}. Это множество называется также графиком отношения.

2. Графиком отношения, т.е. указанием всех точек плоскости, в которых указанное отношение истинно. Для изображения графика отношения введем декартовы координаты, примем, что ось абсцисс - это ось х, а ось ординат - это ось у. Точки, находящиеся в пересечениях всех горизонталей и вертикалей, проведенных через точки координатных осей, изображающие элементы несущего множества, дадут "универсум", т.е. множество, мощность которого равна в данном случае 25. В этом множестве выделим точки, принадлежащие отношению, Рис.2.

Рисунок 2. Изображение отношения с помощью графика

3. Изображение отношения с использованием координатных осей и стрелок очевидно из

Рис. 3, a, b.

Рисунок 3. Изображение отношения стрелками.

4. Изображение отношения с помощью графа. Множество элементов несущего множества используется в качестве имен вершин графа отношения. Ребрами ориентированного графа являются элементы отношения, Рис. 4.

Рисунок 4. Изображение отношения с помощью графа.

5. При изображении отношения с помощью фактор -множества каждому элементу несущего множества сопоставляется его окрестность, определенная следующим образом:

О_r(v_i)={v_j | (v_i,v_j) Î А, где А - несущее множество. Фактор - множество записывается в виде заключенной в квадратные скобки последовательности элементов несущего множества, под каждым из которых указывается его окрестность. В рассматриваемом случае

.

Для любого множества А определим тождественное отношение I_A, которое называется также диагональю А, и универсальное отношение 1 следующим образом:

I_A = {(xx)| x ÎА}. 1 = А². Так как Æ Í А², то Æ является отношением на А и называется пустым отношением.