6. Свойства и виды бинарных отношений

Будем использовать следующие символы, заимствованные из математической логики: дизъюнкция (читается "ИЛИ"), конъюнкция (читается "И"), импликация (читается "ВЛЕЧЕТ", или "ЕСЛИ…ТО"), эквивалентность (читается "ЭКВИВАЛЕНТНО", или "ТОГДА И ТОЛЬКО ТОГДА"), отрицание (читается "НЕ", или "НЕВЕРНО, ЧТО"), квантор всеобщности (читается "ВСЕ"), квантор существования (читается "СУЩЕСТВУЕТ").

Отношение называется всюду определенным слева (справа), если левая (правая) проекция графика совпадает с множеством ( ), что записывается в виде или (определенность всюду слева) и в виде или (определенность всюду справа).

Отношение не всюду определенное слева (справа) характеризуется тем, что соответственно левая (правая) проекция является собственным подмножеством ( ) - ( ), или ( ).

Отношение, однозначное слева (справа) определяется тем, что каждое левое сечение (правое сечение ) содержит только один элемент или пустое. Это записывается в виде ( ).

Многозначность слева (справа) возникает тогда, когда хотя бы одно левое (правое) сечение содержит более одного элемента.

Однозначное слева отношение называется функциональным отношением. Если функциональное отношение является всюду определенным слева, то оно называется функцией, определенной на , со значениями в и представляется тройкой , где - график функции, т.е. множество пар , удовлетворяющих закону, устанавливаемому функцией .

Вместо понятия функции вводится понятие отображения из в и соответствующее ему форма записи: .

7. Операции над бинарными отношениями

Так как графики бинарных отношений являются множествами, то над ними можно производить обычные операции над множествами: объединения, пересечения, взятия разности и симметричной разности, взятия декартова произведения.

В отличие от обычных множеств для бинарных отношений вводятся также операции инверсии и композиции.

Инверсией бинарного отношения называется операция построения обратного к отношения , график которого удовлетворяет условию . Инверсия функции производится по общим правилам построения обратного отношения.

Композицией бинарных отношений и называется отношение , график которого удовлетворяет условию .

Т.о., композиция бинарных отношений определена только в том случае, если они заданы на множествах, одно из которых является общим для обоих отношений.

Композиции нескольких взаимосвязанных отображений удобно представлять посредством диаграмм.

Например, диаграмма отображений , , имеет вид:

8) Специальные свойства бинарных отношений, заданных на одном множестве

Бинарное отношение , для которого имеет место , записывается в виде , имеет график и называется бинарным отношением, заданным на множестве .

Бинарные отношения, заданные на одном множестве, помимо общих свойств бинарных отношений (всюду определенное – не всюду определенное, однозначное – многозначное) могут обладать другими, специфическими для данной конструкции свойствами.

Пусть произвольные элементы множества , тогда эти дополнительные свойства формально представляются так:

рефлексивность - ,

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

симметричность - ,

антисимметричность -

транзитивность - ,

полнота -

Запись можно интерпретировать как непосредственную связь между элементами и .

В более общем случае связь осуществляется не непосредственно, а через промежуточные элементы, т.е. существует цепочка

, , … , ,

где , , … , - произвольные элементы множества .

Тогда говорят о транзитивном замыкании и записывают .

Элементы и удовлетворяют транзитивному замыканию , если они удовлетворяют хотя бы одному из следующих отношений:

- отношению (непосредственная связь ),

- композиции двух одинаковых отношений (связь через один элемент ),

- … ,

- композиции одинаковых отношений (связь через элементов ).

С учетом введенного понятия транзитивного замыкания может быть дано формализованное представление следующих дополнительных свойств:

ацикличность - ,

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

Ацикличность обладает свойствами антирефлексивности и антисимметричности.

Антитранзитивность обладает свойствами ацикличности.