Бинарные отношения

Последовательность длины п, члены которой суть а1, .... аn, будем обозначать через {а1, .... аn}. Последовательность {а1, а2} длины два будем называть упорядоченной парой. Декартово (прямое) произведение множеств А и В определяется как множество всевозможных пар {а, b}, где , т.е.

AB {<a,b>|aA&bB}

Таким образом, декартовым произведением множеств Мa и Мь, называется множество М вида .

Угловыми скобками < > обозначается последовательность, т. е. множество, в котором зафиксирован порядок элементов, т.е кортеж.

Кортежем длины n, составленным из элементов множеств X1, X2, …, Xn, называется конечная последовательность .

Если отношение устанавливается между двумя множествами, то Прямым (декартовым) произведением множеств А и В, обозначаемым АВ, называется множество упорядоченных пар, такое, что первая координата каждой пары — элемент А, а вторая координата — элемент В, т.е. АВ = {<a,b>| аА и bВ}.

В целях наглядного представления декартовых произведений удобно использовать язык геометрии. Для этого множества X, Y представляются осями координат. Элементы хX, уY — соответственно абсциссами и ординатами. Само произведение ХY — точками плоскости ХОY. В качестве примера на рис. 1 показано декартово произведение множеств Х = {1, 2, 3}, Y = {1, 2}.

 

 

рис. 4.1

 

 

Бинарное отношение RXY может отражать разный смысл.

 

Пример. Значениями множества Хможно закодировать названия книжных издательств, а элементами множества Y — всех фирм некоторого региона, которые занимаются продажей этих книг. Тогда отношению RXY можно придать смысл множества заключенных договоров между издательствами и торгующими фирмами. Пусть Х={1, 2, 3}, Y={1, 2} рассматриваются как три издательства и два магазина, продающие книги. Тогда отношение R = {<1,1>, <2,2>, <3,2>} означает, что издательство 1 заключило договор с магазином 1, издательство 2 — с магазином 2, издательство 3 — с этим же магазином 2.

 

Пример. Пусть А = {1,2}, В = {а,b,с}.

Тогда АВ = {<1,а>, <1,b>, <1,с>, <2,а>, <2,b>, <2,с>}. Декартово произведение АВ = {<а,1>, <b,2>, <с,1>, <а,2>, <b,2>, <с,2>}. Декартово произведение АА = {<1,1>, <1,2>, <2,1>, <2,2>} называется декартовым квадратом множества А.

 

Пример. Если множество А включает т различных элементов, а множество В — пэлементов, то произведения множеств АВ и ВА имеет т п элементов. Пусть А = {1}, а В ={1,2,3}. Тогда АВ ={< 1, 1 >, <1,2>, <1, 3 >}. Если А = 0, а В = {1, 2, 3}. Тогда АВ=ВА=0.

Пример 2. Всё множество координат всех клеток шахматной доски можно записать декартовым произведением вида {a,b,c,d,e,f,g,h} {1,2,3,4,5,6,7,8} = {‹a,1›, ..., ‹a,b›, ‹b,1›, ..., ‹b,b›, ..., ‹h,8› }

 

Любое непустое подмножество R декартова произведения ХY множеств X,Y называетсябинарным отношением между Х и Y. Записывается это так: RХY, или так: хRу, или так: <х,у>R. Слово «бинарный» происходит от английского binary, что в переводе означает «двойной». Любое непустое подмножество ХY является бинарным отношением на X. В частности, множество ХX называется универсальным отношением на X.

Пусть А и В два конечных множества. Напомним, что декартово произведение множеств А и В это множество АВ, состоящее из всех упорядоченных пар <а, b>, где а A, b B.

Бинарным отношением между элементами множеств А и В называется любое подмножество R. множества АВ,т.е. R АВ.

Под бинарным отношением (с левой областью А и правой областью В) подразумевается произвольное подмножество . Если А = В, то будем говорить о бинарном отношении на множестве А. Вместо часто пишут a R b.