Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


Ѕинарные отношени€




Ѕинарные отношени€ служат простым и удобным аппаратом дл€ весьма широкого круга задач. язык бинарных и n- арных отношений используетс€ во многих прикладных (дл€ математики) област€х, например, таких как математическа€ лингвистика, математическа€ биологи€, математическа€ теори€ баз данных. Ўирокое использование €зыка бинарных отношений легко объ€сн€етс€ - геометрический аспект теории бинарных отношений есть попросту теори€ графов.

¬ведем необходимые определени€.

ќпределение 1.1. ƒекартовым произведением множеств X и Y называетс€ множество X x Y всех упор€доченных пар (x, y) таких, что x X, y Y.

ќпределение 1.2. —оответствием между множествами X и Y (или соответствием из X в Y) называетс€ любое подмножество декартова произведени€ X x Y. ≈сли множества X и Y совпадают, то соответствие между множествами X и Y называют также бинарным отношением на множестве X.

ѕример 1.1. ѕусть X = { a, b, c, d }, Y = { 1, 2, 3, 4, 5 }. “огда множество кортежей a={(a, 1), (b, 2), (c, 3), (d, 4)} €вл€ютс€ соответствием из X в Y.

ќтметим, что обычно соответстви€ задаютс€ не путем указани€ подмножества a декартова произведени€ X x Y, а путем указани€ свойства пар (x, y), принадлежащих этому подмножеству

a. Ќапример, отношение a= {(4, 4), (3, 3), (2, 2), (4, 2)} на множестве X = { 4, 3, 2 } можно определить как свойство "ƒелитс€" на этом подмножестве целых чисел.

’орошо известными примерами отношений из школьного курса математики €вл€ютс€:

Ј на множестве целых чисел Z отношени€ "делитс€", "делит", "равно", "больше", "меньше", "взаимно просты";

Ј на множестве пр€мых пространства отношени€ "параллельны", "взаимно перпендикул€рны", "скрещиваютс€", "пересекаютс€", "совпадают";

Ј на множестве окружностей плоскости "пересекаютс€", "касаютс€", "концентричны".

‘акт принадлежности кортежа (x, y) соответствию a, часто обозначают с помощью так называемой инфиксной формы записи: x a y. “ипичными примерами таких записей из курса математики €вл€ютс€: x > y, a = b, 8 4, m || l, a b и т. п.

ќтношени€ могут задаватьс€ формулами:

Ј формулы

y = x2 +5x - 6 или

задают бинарные отношени€ на множестве действительных чисел;

Ј формула

x + y = любовь,

задает бинарное отношение на множестве людей. Ётому отношению принадлежит люба€ пара людей, между которыми существует любовь.

«адание отношений в виде формул достаточно широко распространено. ќб этом свидетельствуют многочисленные надписи на деревь€х заборах или стенах домов типа:

"¬ас€ + “ан€ = любовь",

увековечивающие принадлежность конкретной пары (¬ас€, “ан€) отношению "любовь".

–ассмотрим еще три формы представлени€ бинарных отношений: матричное представление и два графических представлени€. ¬ качестве носител€ отношени€ дл€ иллюстрирующих примеров будем использовать множество X = { a, b, c, d, e }.

¬начале рассмотрим метод, восход€щий к аналитической геометрии. Ќачертим пару взаимно перпендикул€рных осей (OX - горизонтальна€ ось, а OY - вертикальна€ ось) и на каждой отметим точки, представл€ющие элементы множества X (рис. 1).

–ис. 1.  оординатна€ сетка

—чита€ метки a, b, c, d, e координатами точек на горизонтальной и вертикальной ос€х, отметим на плоскости точки с координатами (x, y) такими, что (x, y). Ќа рисунке 2 изображено множество точек, соответствующее отношению a= {(a, b), (a, c), (b, d), (c, e), (e, b), (e, e)}.

–ис. 2. Ѕинарное отношение a

ƒругой широко распространенный способ представлени€ отношений основан на использовании ориентированных графов. ѕри таком представлении элементы множества X изображаютс€ вершинами графа (точками плоскости), а элементы (x, y) отношени€ a дугами (стрелками), соедин€ющими первую компоненту x отношени€ со второй компонентой y. √раф бинарного отношени€ a изображен на рисунке 3.

–ис. 3. √раф бинарного отношени€

ƒл€ бинарных отношений, определенных на конечных множествах, часто используетс€ матричный способ задани€. ѕусть на некотором конечном множестве X задано отношение a. ”пор€дочим каким-либо образом элементы множества X = { x1, x2,..., xn } и определим матрицу отношени€ A = [ aij ] следующим образом:

“аким образом, матрица отношени€ a, представленного графом на рисунке 3, имеет вид

„асто матрицу отношени€ называют булевой, чтобы подчеркнуть, что ее элементами €вл€ютс€ только нули и единицы.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-05-06; ћы поможем в написании ваших работ!; просмотров: 638 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќадо любить жизнь больше, чем смысл жизни. © ‘едор ƒостоевский
==> читать все изречени€...

2107 - | 1841 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.011 с.