yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Тема №2. Теория Отношений.

Дискретная математика

Тема №2. Теория Отношений.

План

 

2.1Отношения .........................................

2.2. Свойства бинарных отношений .......................

2.3. Операции с бинарными отношениями ..................

2.1.Подмножество R c M^n называется n-местным (n-арным) отношением на несущем множестве M.  Множество М является несущим для отношений любой арности, которые на нем построены. Говорят, что элементы вектора (a1,a2,a3,...,an) находятся в отношении R , если  этот вектор принадлежит множеству R.  Для n=1 отношение называют унарным (по сути, такое отношение выделяет  из  множества  М  подмножество R по признаку); для n=2 - бинарным (т.е. отношением  между двумя элементами множества М) и т.д.

Отношение - то же множество, элементами которого являются  векторы размерности n или, при другой записи, цепочки длины n,  составленные в алфавите М и отобранные в соответствии с отношением R

 

Пример: Построим бинарное отношение R, которое определим словами как "в латинском алфавите встречается раньше" на несущем  множестве M={a,b,c,d}.  Примерами элементов отношения R  могут  быть векторы (a,c), (c,d)... или цепочки ac, cd, bd..., такие, в которых на первом месте стоит буква, встречающаяся в латинском  алфавите раньше по сравнению с буквой, стоящей на втором месте.

Отношение R является подмножеством множества M^2:

M^2 = {aa, ab, ac,...,cc}, из которого элементы отбираются в соответствии со следующей процедурой  R={xy ¦ x "меньше" y}.

R={ab,ac,ad,bc,bd,cd}

Отношения любой арности можно задать одним из способов задания множеств (перечисление элементов, порождающая процедура, характе ристические признаки).  Кроме этого бинарные отношения можно  задавать:

а) с помощью матрицы смежности - квадратной матрицы, столбцы и строки которой обозначены элементами несущего множества,  а  элементы имеют следующие значения:

--                        i\j¦ a ¦ b ¦ c ¦ d ¦

¦ 1, если ai R aj          --+---+---+---+---+

Cij = ¦                          a ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦

¦ 0 ,в противном случае    --+---+---+---+---+

L-                         b ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦

--+---+---+---+---+

(строки-i, столбцы - j )           c ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦

--+---+---+---+---+

d ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦

--+---+---+---+----

На рисунке представлена матрица для отношения R из предыдущего примера.

 

б) с помощью ориентированного графа - элементы несущего множества М изображаются на плоскости в виде вершин графа (точки с  обозначением рядом элементов несущего множества), а затем вершины, пары которых входят в множество R, соединяются с помощью  стрелок(дуг) (начинается стрелка в первом элементе пары,  заканчивается  -  вовтором); число таких стрелок равно числу элементов в множестве R.

Для каждого бинарного отношения R можно построить обратное отношение R^(-1) (читается: R в степени минус один), поменяв местами в каждом элементе R проекции векторов.

 

 

 

 

9