Основные типы бинарных отношений

Пусть  – бинарное отношение на множестве А, т.е.     AA. Говорят, что 

рефлексивно, если	 a  A a a
симметрично, если	 a, b  A a  b  b  a
транзитивно, если	 a, b, c  A a  b  b  c  a  c
антирефлексивно, если	 a  A
антисимметрично, если	 a, b  A a  b  b  a  a = b
функция, если	 a  D()  ! b  B a  b

Легко понять, что означают эти свойства на языке графов и графиков:

Свойство	Граф	График
рефлексивность	вкаждой вершине а графа есть петля  a	график содержит диагональ D = {(a; a)  AA}:
симметричность	у каждой стрелки в графе есть обратная (если есть a    b, то должна быть и b    a ):	график симметричен относительно диагонали:
транзитивность	л … юбой путь по стрелкам графа можно пройти по одному ребру:	? ? ?
анти- рефлексивность	в графе нет ни одной петли:	на графике нет ни одной точки диагонали:
анти- симметричность	в графе нет замкнутых путей длины два:	любые две симметричные относительно диагонали точки совпадают (и лежат на диагонали):
функция	из каждой вершины графа выходит не более одной стрелки:	любая вертикальная прямая x = a  А пересекает график не более чем в одной точке:

Примеры: 1. Какими свойствами обладает бинарное отношение  со следующим графом ?

Ясно, что  рефлексивно, симметрично, не транзитивно: путь 1    3   2 нельзя пройти по одной стрелке. Оно не антисимметрично и не антирефлексивно. Функцией не является, т.к. из вершин 1  , 2  , 3  выходят более одной стрелки.

2. Какими свойствами обладает отношение  = {(1; 1), (2; 2)}  NN ?

Для удобства можно построить граф для , который наглядно демонстрирует, что  не рефлексивно (например, нет петли у вершины 3 ), симметрично, транзитивно, антисимметрично, но не антирефлексивно. При этом  является функцией.

3. Какими свойствами обладает бинарное отношение , заданное правилом a  b  |a – b| < 1 (a, b  R) ?

Последовательно проверяем все свойства аналитически, т.к. построить граф в данном случае затруднительно.

Рефлексивность: ( a  A a  a)  ( a  R |a – a| < 1) – верно, т.к. 0 < 1. Значит,  рефлексивно.

Симметричность: ( a, b  A a  b  b  a)  ( a, b  R |a–b| < 1   |b – a| < 1) – верно. Значит,  симметрично.

Транзитивность: ( a, b, c  A a  b  b  c  a  c)  ( a, b, c  R |a – b| < 1  |b – c| < 1  |a – c| < 1). Нетрудно понять, что это не верно: например, |0 – 0,5| < 1  |0,5 – 1| < 1, но |0 – 1| = 1  1. Таким образом,  не транзитивно.

Антирефлексивность: ( a  A )  ( a  R |a – a|  1) – не верно, и  не антирефлексивно.

Антисимметричность: ( a, b  A a  b  b  a  a = b)  ( a, b  R |a – b| < 1  |b – a| < 1  a = b) – не верно, т.к. |0 – 0,5| < 1  |0,5 – 0| < 1, но 0,5  0. Итак,  не антисимметрично.

Функциональность: ( a  A  b, c  B a  b  a  c  b = c)  ( a, b, c  R |a – b| < 1  |a – c| < 1  b = c) – не верно (?!). Значит,  – не функция.

Упражнения: 1. Обоснуйте свойства отношения  из примера 3, построив график этого отношения.

2. Какими свойствами обладают бинарные отношения  со следующими графиками:

3. Исследуйте свойства бинарных отношений:

a)  = {(1; 3), (3; 5), (5; 7), …}  NN, б) a  b  a²= b² (a, b  N),

в) a  b  a² = b² (a, b  R), г)  = {(x; y)  NN | |y – x| > 5}.