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

N–местным отношением или n–местным предикатом Р на множествах A₁,A₂,¼,A_n, называется любое подмножество декартова произведения A₁´A₂´¼´A_n. При n=2 отношение называется бинарным. Бинарные отношения чаще рассматриваются, как отношения между элементами одного и того же множества. Пусть это множество М, тогда Р Í M´M={(х,у): х,уÎM}.

То, что два элемента х и у находятся в отношении Р,записывается так: (х,у)ÎР или хРу или х~у(Р) – читается: «х находится с у в отношении Р». В некоторых случаях может использоваться также запись вида: y=Р(x), и соответствующая терминология: y является образом x относительно Р и x является прообразом y относительно Р. Если Р Í А´В, то множество всех образов элементов xÎA называют образом множества А в множестве В и обозначают Р(А)={yÎB: $xÎA и y=Р(x)}. Множество всех прообразов элементов yÎB называют прообразом множества В в множестве А и обозначают Р^‑1(В)={xÎA: $yÎB и y=Р(x)}.

Пусть Р Í А´В – бинарное отношение.Для всех x из пр_А Р={xÎA: $yÎB и (x,y)ÎР} Í A говорят, что отношение Р определено для x, и множество пр_А Р ⇋ пр₁ Р называют областью определения Р. Для всех y из пр_В Р={yÎB: $xÎA и (x,y)ÎР} Í B, говорят, что y является значением, принимаемым отношением Р, и множество пр_В Р ⇋ пр₂ Р называют областью значений Р.

Если пр₁Р = А, то отношение Р называют всюду определённым.

Если отношение всюду определено и при этом пр₂Р = B, то имеет смысл понятие обратного отношения.

Отношение Р^-1, элементами которого являются пары (y,x) такие, что (x,y)ÎР называется обратным к Р, т.о. Р^-1 = {(y,x): (x,y) Î Р}.

Пусть Р Í А´В и R Í В´С – бинарные отношения. Композицией отношений R и Р называется отношение R∘Р={(x,z): $yÎB и (x,y)ÎР и (y,z)ÎR}. При этом область значений отношения Р является областью определения отношения R, т.е. пр₂Р = пр₁R. Иными словами, под композицией понимают последовательное применение двух отношений: сначала отношения Р к элементам множества А, а затем отношения R к значениям Р.

Свойства композиции:

Пусть Т Í D´A, Р Í А´В и R Í В´С – бинарные отношения. Тогда

1) (R∘Р)^-1= Р^‑1∘R^‑1

2) (R∘Р) ∘T = R∘ (Р∘T)

3) (R∘Р)(A) = R(Р(A))

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

Бинарное отношение РÍМ´М называется рефлексивным, если любой элемент множества М находится в этом отношении с самим собой, т.е. "aÎM Þ a~a(Р).

Отношение Р называется транзитивным, если "a, b, с Î M, для которых a~b(Р) и b~с(Р), обязательно следует, что a~с(Р).

Отношение Р называется симметричным, если из a~b(Р) всегда Þ b~a(Р);

Отношение Р называется антисимметричным, если одновременное выполнение a~b(Р) и b~a(Р) возможно только в случае, когда a=b. (Заметим, что пара (a,b), удовлетворяющая данному условию, может вообще не существовать.)