double arrow

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

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, zR }. При этом область значений отношения Р является областью определения отношения R, т.е. пр2 Р = пр1 R. Иными словами, под композицией понимают последовательное применение двух отношений: сначала отношения Р к элементам множества А, а затем отношения R к значениям Р.

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

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

1) (RР)-1= Р ‑1R ‑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), удовлетворяющая данному условию, может вообще не существовать.)


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: