N–местным отношением или n – местным предикатом Р на множествах A 1, A 2,¼, An, называется любое подмножество декартова произведения A 1´ A 2´¼´ An. При 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, и множество пр А Р ⇋ пр1 Р называют областью определения Р. Для всех y из пр В Р ={ y Î B: $ x Î A и (x, y)Î Р } Í B, говорят, что y является значением, принимаемым отношением Р, и множество пр В Р ⇋ пр2 Р называют областью значений Р.
|
|
Если пр1 Р = А, то отношение Р называют всюду определённым.
Если отношение всюду определено и при этом пр2 Р = B, то имеет смысл понятие обратного отношения.
Отношение Р -1, элементами которого являются пары (y, x) такие, что (x, y)Î Р называется обратным к Р, т.о. Р -1 = {(y, x): (x, y) Î Р }.
Пусть Р Í А ´ В и R Í В ´ С – бинарные отношения. Композицией отношений R и Р называется отношение R ∘ Р ={(x, z): $ y Î B и (x, y)Î Р и (y, z)Î R }. При этом область значений отношения Р является областью определения отношения R, т.е. пр2 Р = пр1 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), удовлетворяющая данному условию, может вообще не существовать.)