13. Понятие бинарного отношения между элементами
одного множества. Способы задания отношений.
Свойства отношений.
Бинарным отношением на множество X называется всякое подмножество декартово произведения множества Х на множество Х.
X = {2,4,6,8}
R: «х не больше у»
R: «х больше или равно (значок) у»
R = {(2,2); (2,4); (2,6); (2,8); (4,4); (4,6); (4,8); (6,6); (6,8); (8,8)}
М
ы
можем построить граф
данного отношения
2. 4.
8 . 6.
Если множество Х числовое, то можно построить график отношения
• • • •
• • •
• •
•
Таким образом, отношение может быть задано разными способами:
Указывают все пары элементов, находящиеся в данном отношении, при этом возможны разные формы:
Перечисляют все пары элементов.
В виде графа.
В виде графика.
Указывают характеристические свойства всех пар элементов (приводим пример из лекции – построение графа)
Свойства отношений.
Отношения могут обладать следующими свойствами:
Свойство рефлексивности. Отношение R на множество Х рефлексивно, если каждый элемент множества Х находится в отношении R с самим собой (приводим пример из лекции).
Свойство антирефлексивности.
Отношение R на множестве Х антирефлексивно , если не один элемент множества Х не находится в отношении R с самим собой. (приводим пример из лекции).
Свойство симметричности.
Отношение R на множестве Х симметрично, если из того что Х находится в отношении R с У следует, что У находится в отношении R c X. (приводим пример из лекции).
Свойство антисимметричности.
Отношение R на множестве Х антисимметрично, если для различных элементов Х и У из того, что Х находится в отношении R с У следует, что У в отношении R c X не находится. (приводим пример из лекции).
Свойство транзитивности.
Отношение R на множестве Х транзитивно, если из того, что элемнт Х находится в отношении R с элементом У, а У находится в отношении с R с элементом Z следует, что Х находится в отношении R с элементом Z. (приводим пример из лекции).
14. Отношение эквивалентности и его связь с разбиением множества на попарно-непересекающиеся подмножества или классы.
Отношением эквивалентности называется отношение, одновременно обладающее свойствами рефлексивности, симметричности, транзитивности. Для отношения эквивалентности выполняется следующее утверждение: если на множестве задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества или классы.
Верно и обратное утверждение: если какое-либо отношение порождает разбиение множества на классы, то это отношение называется отношением эквивалентности.(приводим примеры из лекции).
15. Отношение порядка, его виды.
Отношением порядка называется отношение, обладающее одновременно свойствами антисимметричности и транзитивности (приводим пример из лекции).
Мы видим, что все 3 отношения обладают свойствами антисимметричности и транзитивности, т.е. являются отношением порядка. Отношение порядка бывает строгим, не строгим, линейным и частичным.
Если отношение порядка обладает свойством рефлексивности, то порядок не строгий.
Если свойством антирефлексивности – то строгий.
Если любые 2 элемента находятся в отношении порядка, то порядок линейный.
Если это условие нарушается, то порядок частичный.