График, граф и матрица отношения.

График:	Граф: соединить стрелками, если xRy
Матрица отношения:  1 если xRy, 0 если нет.

 

Отношение предшествования:

Можно перечислить все пары элементов, находящихся в данном отношении: .

График, граф и матрица отношения.

 

Отношение делимости: .  

.

График, граф и матрица отношения.

 

. .

. .

 

ЛЕКЦИЯ 3.

 

Свойства отношений.

Рефлексивность и антирефлексивность.

Рефлексивно: Если для любого , верно .

Антирефлексивно: Если для любого  , .

Примеры. Отношение  рефлексивно, < антирефлексивно. 

Отношение может быть ни рефлексивным, ни антирефлексивным: . , , 

 

 

Симметричность, несимметричность и антисимметричность.

Симметрично: Если из  следует .

Несимметрично: Если из  следует .

Антисимметрично: Если из  и  следует

 

В терминах матрицы отношения:

Симм:  матрица симметрична.

Несимм: . Несимметрична, на диаг 0.

Антисимм:    (т.е. только на диагонали). Пары  элементов при i,j и j,i могут быть 0,0 и 1,0 

 

Комментарий. Антисимметрическая матрица, где  и по диагонали 0, не имеет отношения к этим понятиям:, здесь -1 не присутствует,

 

Примеры.    Симметрично: отношение делимости: .

Несимметрично: < Антисимметрично: .  

 

Транзитивность.

Если из  и  следует .

 

Пример не транзитивного отношения

, , .  

Отношение эквивалентности, отношение порядка.  

Отношение эквивалентности называется отношение, обладающее свойствами 1) рефлексивности 2) симметричности 3) транзитивности.

 

Пример – отношение делимости в Z., (x-y делится на k)

Рефлексивно: х-х = 0 делится на k,  

Симм: x-y то и y-x делится,

Транз: x-y, y-z то x-z тоже делится на k.

(Непересекающиеся классы вычетов, рассматривали в 1 семестре).

 

Отношением порядка, или частичным порядком, на множестве M называется бинарное отношение,  удовлетворяющее следующим условиям:

1. Рефлексивность:   :   

2. Антисимметричность:   :  и . 

3. Транзитивность:   :  и

 

Примечание. Если отношение обладает свойствами антирефлексивности, несимметричности и транзитивности, то называется отношением строгого порядка.

 

Множество M, на котором задано отношение частичного порядка, называется частично упорядоченным.

Пример. Множество натуральных чисел N относительно делимости –

частично упорядоченное множество с отношением нестрогого порядка (k делится на k). Не для всякой пары чисел можно утверждать, что одно делится на другое.

 

Пример.  Множество всех подмножеств относительно включения одно в другое.

Подмножества могут быть частично пересекающимися или вовсе не пересекающимися, то есть не всякие 2 из них сравнимы.

Рассмотрим множество всех подмножеств для множества из 3 элементов.

Диаграмма Хассе

Перерыв

Рассмотрим множество всех подмножеств для множества из 4 элементов. Цветом выделены те подмножества, которые сравнимы с множеством, состоящим только из одной «1». Но кстати, и не все из них сравнимы между собой.   

Очевидно, что не всякая пара подмножеств сравнима по включению. Например, (1,2,4) и (3,4) несравнимы.