1.7. Отношения и их представление

Пусть задано некоторое множество объектов А = {a₁,a₂,…a_N}. Множество всех пар вида (a_i , а_j), где a_iA, a_iA образуют декартово произведение А х А. Любое подмножество Р  A х А декартова произведения называется бинарным отношением на множестве А. Отношения задаются в виде матрицы P(N х N), в которой строки и столбцы соответствуют объектам из А. Если пара (a_i , а_j) P, то элемент p_ij= 1, в противном случае - 0.

Рассмотрим основные типы наиболее распространенных бинарных отношений.

Рефлексивность. Отношение P рефлексивно, если пары (a_i , а_i)P, i =1,..N

Антирефлексивность. Отношение Р антирефлексивно, если пары (a_i , а_i)P, i= 1,...N.

Симметричность. Отношение Р симметрично, если одновременно (a_i , а_j)P и (a_j , а_i)P .

Асимметричность. Отношение Р асимметрично, если (a_i,а_j) P только когда (a_j , а_i) P.

Антисимметричность. Р антисимметрично, если из (a_i , а_j) P и (a_j , а_i) P следует a_i=а_j.

Транзитивность. P транзитивно, если из (a_i , а_j)P и (a_j , а_k)P следует (a_i , а_k) P .

Связность (линейность). Отношение Р связно, если для любых a_iA и a_iA выполнено

(a_i , а_j) P или (a_j , а_i)P или эти условия выполнены одновременно.

Эквививалентность. Отношение Р называется эквивалентностью, если оно рефлексивно, симметрично и транзитивно. Эквивалентность выражает неразличимость объектов из одного класса. Пусть А = {a₁,a₂,a₃,a₄,a₅}. Если a₁= a₂ и a₃= a₄ = a₅ , то есть объекты a₁ и a₂ не различаются, и a₃ ,a₄ ,a₅ также не различаются, то матрица эквивалентности

имеет вид:

1 1 0 0 0

P_э =0 0 1 1 1

0 0 1 1 1

Отношение можно также представить в виде графа. Тогда отношение эквивалентности можно представить в виде неориентированного графа (Рис. 1.9).

1 2 3 4 5

Рис. 1.9. Граф эквивалентности.

Толерантность. Отношение Р называется толерантностью, если оно рефлексивно и симметрично. Толерантность выражает свойство похожести. Если a₁ a₂ , a₂  a₃ , a₄ a₅ ,то матрица толерантности и граф выглядят как на Рис. 1.10.

1 1 0 0 0

1 1 1 0 0

P_т=0 1 1 0 0

0 0 0 1 1

1 2 3 4 5

Рис. 1.10. Отношение и граф толерантности.

Линейный порядок. Отношение Р называется линейным порядком, если оно рефлексивно, антисимметрично, транзитивно и связно. Для линейного порядка применяются также и другие названия: линейный квазипорядок, ранжирование. Данное отношение говорит о частичном упорядочении объектов из А, когда классы неразличимых объектов упорядочены. Если неразличимых объектов нет, то есть все классы эквивалентности одноэлементны, то отношение Р является антирефлексивным, а порядок или ранжирование называется строгим. Пусть A₁={a₁}, A₂={a₂}, A₃={a₃,a₄} и A₄={a₅} - классы эквивалентности. Следовательно, a₃=a₄ и классы A_i упорядочены A₁ A₂A₃A₄ то есть A₁ предшествует A₂ и т.д. Тогда матрица линейного порядка имеет вид: