6. Многоместные отношения. Способы задания бинарных отношений. Композиция отношения. Примеры.

Подмножество n-ой степени множества называется n-местным отношением на этом множестве. R  Aⁿ

СПОСОБЫ ЗАДАНИЯ ОТНОШЕНИЙ.

Поскольку отношение является подмножеством, то для его задания подходят все способы задания множеств. (см выше).

Если отношение задано на конечном множестве, то можно использовать также матричный способ задания:

R=R[i,j]= . (нарисовать матрицу)

Ясно, что единичная матрица Е задает отношение равенства.

Так же к отношениям можно применить все операции с множествами.

Кроме того, отношения могут задать новое отношение, называемое композицией.

R₁R₂=R ={(a,b,c)|(a,b)R₁ и сА и a R₁b R₂c}

Последовательная композиция отношения с самим собой называется степенью отношения. RRR…R=Rⁿ.

Имеем: R⁰=I; R¹=R: ……Rⁿ=RR^n-1.

Если некоторая пара (a,b) принадлежит какой-либо степени отношения R на множестве А мощности n, то эта пара принадлежит и степени R не выше n-1.

R A²& |A|=n  (a,bA) (k|aR^kbk<n)

7. Виды отношений. Ядро отношения. Примеры.

ВИДЫ ОТНОШЕНИЙ: 1-местное - подмножество

2-местное – бинарное отношение

3- местное – тернарное отношение и т. д.

n-местное – n-арное отношение.

Показатель степени множества называется арностью отношения.

Для записи отношения обычно применяется инфиксная запись: aRb

ТИПЫ ОТНОШЕНИЙ:

Обратное отношение R^-1={(a,b)| (b,a)R }

Дополнение отношения R= {(a,b)|(a,b)R}

Тождественное отношение I= {(a,a)|aA}

Универсальное отношение U= {(a,b)|a,bA}

Можно сказать, что (R^-1)^-1=R

Для отношений справедливы операции с множествами, определяющиеся аналогично.

Для любого подмножества А₁ множества А можно определить понятие сужения отношения R на множество А₁. Оно получается удалением из R всех пар, содержащих элементы, не входящие в А₁.

Композиция отношения с обратным называется ядром отношения и обозначается как ker R=RR^-1. Ядро отношения само является отношением на А.

8. Свойства отношений. Примеры. Теорема о свойствах отношений.

СВОЙСТВА ОТНОШЕНИЙ.

1. рефлексивность. Для любого элемента из А выполняется отношение аRа.

(aA) aRa. Главная диагональ такого отношения содержит только единицы.

2. антирефлексивность. Для любого а из А отношение не выполняется.

(aA) not(aRa). Главная диагональ его матрицы содержит только нули.

3. симметричность. Для любой пары отношение либо выполняется в обе стороны, либо вообще не выполняется.

(a,bA) (aRbbRa). Матрица симметрична относительно главной диагонали.

4. антисимметричность. Для любой пары отношение выполняется в обе стороны только в том случае, когда элементы пары равны.

(a,bA) (aRb=bRaa=b)

5. транзитивность. Для любых двух пар (a,b) и (b,c) выполнимость отношения для них говорит о выполнимости отношения для пары (а,с).

(a,b,cA) (aRb&bRcaRc)

6. полнота (линейность). Любые два элемента из множества А вступают в отношение хотя бы в одну сторону.

(a,bA) (a≠baRbbRa).

ПРЕДСТАВЛЕНИЕ ОТНОШЕНИЙ В ЭВМ.

Понятно, что в ЭВМ можно представить только конечные множества. По этой причине задать в ЭВМ можно только отношения, заданные на конечных множествах. Удобнее всего использовать матрицу отношения. О матрицах отношений существует две важные теоремы.

ТЕОРЕМА. Пусть R-бинарное отношение на множестве А, тогда