Лекция 3

Отношение

1. Бинарное отношение на X - любое подмножество прямого произведения r М  X×X.
2. Единичное отношение e_x на X содержит только пары (x,x).
3. Полное отношение U =  X×X.
4. Обратное отношение r ^{- 1} = {(x,y)|(y,x) О r}.
5. Отношение r на X рефлексивно, если для любого x О X пара (x,x) О r.
6. Отношение r на X антирефлексивно, если для любого x О X пара (x,x) П r.
7. Отношение r на X симметрично, если для любой пары (x,y) из условия (x,y) О r следует (y,x) О r.
8. Отношение r на X антисимметрично, если из условия (x,y) О r и (y,x) О r следует x=y.
9. Отношение r на X асимметрично, если для любой пары (x,y) из условия (x,y) О r следует (y,x) П r.
10. Отношение r на X транзитивно, если для любых двух пар (x,y) и (y,z) из условия (x,y) О r и (y,z) О r следует (x,z) О r.
11. Композиция бинарных отношений s и r на X называют отношение
    

    j = r°s = {(x,z)|(x,y) О s,(y,z) О r}
12. Теорема. Отношение r транзитивно тогда и только тогда, когда r°r М r.
13. Отношение r^{^} называют замыканием отношения r на свойство A , если r^{^} обладает свойством A, r М r^{^} и для любого отношенияsсо свойством A , r^{^} М s.
14. Транзитивное замыкание произвольного отношения имеет вид r⁺ = И_{k = 1}^Ґ r^k
15. Рефлексивное транзитивное замыкание отношения имеет вид r⁺ = И_{k = 0}^Ґ r^k
16. Алгоритм Уоршолла транзитивного замыкания. Рассмотрим булеву матрицу M отношения. Если m_ij = 1,i № j, то i-я строку матрицы заменяем поэлементной дизъюнкцией i-й и j-й строк матрицы. Процедуру повторяем до тех пор, пока процесс не установится - матрица перестанет изменяться.
17. Отношение называют отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
18. Множество элементов из X, эквивалентных некоторому элементу x₀ , называется классом эквивалентности элемента x₀ . Обозначения класса эквивалентности [x₀ ].
19. Множество всех классов эквивалентности - фактор-множество.
20. Мощность фактор-множества - индекс разбиения.
21. Любое отношение эквивалентности порождает разбиение.
22. Любое разбиение порождает отношение эквивалентности.
23. Отношение называют предпорядком, если оно рефлексивно и транзитивно.
24. Отношение называют порядком, если оно рефлексивно, антисимметрично и транзитивно.
25. Порядок r называется линейным (или полным), если для любых элементов xry или yrx. В противном случае - частичный порядок.
26. Отношение называют строгим порядком, если оно асимметрично и транзитивно.
27. Элемент y О X накрывает элемент x О X, если x << y и не существует элемента z О X такого, что x << z << y.
28. Любое упорядоченное множество можно представить диаграммой Хассе.
29. Пусть r есть частичный порядок на X. Отношение sна элементах прямого произведения (x,y)s(a,b) называется отношением Парето, если оно выполняется в том и только в том случае, когда xra и yrb.
30. Алфавит - множество символов с отношением линейного порядка.
31. Лексикографический r порядок a₁ << a₂ , где a₁ = x₁₁x₁₂ ...x_1i ..x_1n и a₂ = x₂₁ x₂₂ ...x_2i ..x_2m на алфавите задается одним из двух условий 1) a₁ = bx_1i c,     a₂ = bx_2id, где b,c,d - некоторые слова, возможно пустые, а символы x_1i и x_2i связаны отношением линейного порядка x_1i rx_2i или 2) a₁ = a₂f, где f- некоторое непустое слово.