Отношение
- Бинарное отношение на X - любое подмножество прямого произведения r М X×X.
- Единичное отношение ex на X содержит только пары (x,x).
- Полное отношение U = X×X.
- Обратное отношение r - 1 = {(x,y)|(y,x) О r}.
- Отношение r на X рефлексивно, если для любого x О X пара (x,x) О r.
- Отношение r на X антирефлексивно, если для любого x О X пара (x,x) П r.
- Отношение r на X симметрично, если для любой пары (x,y) из условия (x,y) О r следует (y,x) О r.
- Отношение r на X антисимметрично, если из условия (x,y) О r и
(y,x) О r следует x=y.
- Отношение r на X асимметрично, если для любой пары (x,y) из условия (x,y) О r следует (y,x) П r.
- Отношение r на X транзитивно, если для любых двух пар (x,y) и (y,z) из условия
(x,y) О r и (y,z) О r следует (x,z) О r.
- Композиция бинарных отношений s и r на X называют отношение
j = r°s = {(x,z)|(x,y) О s,(y,z) О r} |
|
- Теорема. Отношение r транзитивно тогда и только тогда, когда r°r М r.
- Отношение r^ называют замыканием отношения r на свойство
A , если r^ обладает свойством A,
r М r^
и для любого отношенияsсо свойством A , r^ М s.
- Транзитивное замыкание произвольного отношения имеет вид r+ = Иk = 1Ґ rk
- Рефлексивное транзитивное замыкание отношения имеет вид
r+ = Иk = 0Ґ rk
- Алгоритм Уоршолла транзитивного замыкания. Рассмотрим булеву матрицу M
отношения. Если mij = 1,i № j, то i-я строку матрицы заменяем
поэлементной дизъюнкцией i-й и j-й строк матрицы. Процедуру повторяем до тех
пор, пока процесс не установится - матрица перестанет изменяться.
- Отношение называют отношением эквивалентности, если оно рефлексивно,
симметрично и транзитивно.
- Множество элементов из X, эквивалентных некоторому элементу x0 ,
называется классом эквивалентности элемента x0 . Обозначения класса
эквивалентности [x0 ].
- Множество всех классов эквивалентности - фактор-множество.
- Мощность фактор-множества - индекс разбиения.
- Любое отношение эквивалентности порождает разбиение.
- Любое разбиение порождает отношение эквивалентности.
- Отношение называют предпорядком, если оно рефлексивно и транзитивно.
- Отношение называют порядком, если оно рефлексивно, антисимметрично и
транзитивно.
- Порядок r называется линейным (или полным), если для любых элементов
xry или yrx. В противном случае - частичный порядок.
- Отношение называют строгим порядком, если оно асимметрично и транзитивно.
- Элемент y О X накрывает элемент x О X, если x << y и не
существует элемента z О X такого, что x << z << y.
- Любое упорядоченное множество можно представить диаграммой Хассе.
- Пусть r есть частичный порядок на X. Отношение sна элементах
прямого произведения (x,y)s(a,b) называется отношением Парето, если
оно выполняется в том и только в том случае, когда xra и yrb.
- Алфавит - множество символов с отношением линейного порядка.
- Лексикографический r порядок a1 << a2 , где a1 = x11x12 ...x1i ..x1n и a2 = x21 x22 ...x2i ..x2m на
алфавите задается одним из двух условий 1) a1 = bx1i c, a2 = bx2id, где b,c,d - некоторые слова, возможно пустые, а символы x1i и x2i
связаны отношением линейного порядка x1i rx2i или 2) a1 = a2f, где f- некоторое непустое слово.
|