Понятие бинарного отношения. Свойства отношений

R називають бінарним відношенням на множині A, Якщо . При цьому замість запису часто використовують запис xRy.

Відношення R називається рефлексивним, якщо для будь-якого .

В матриці рефлексивного відношення на головній діагоналі знаходяться одиниці, тобто матриця така, що a_ij=1 якщо i=j. Граф рефлексивного відношення обов’язково має петлі у вершинах. Для верхнього й нижнього розрізів справедливо , для всіх x Î W.

Відношення R називається антирефлексивним, якщо xRy означає , для .В матриці антирефлексивного відношення на головній діагоналі знаходяться нулі, тобто a_ij=0 якщо i=j. Граф рефлексивного відношення не має петель у вершинах, і верхні та нижні розрізи задовольняють умові , для всіх x Î W.

Відношення R називається симетричним, якщо R<=R^-1 . Матриця симетричного відношення симетрична, тобто a_ij=a_ji для всіх i, j. У графі всі дуги парні. Для розрізів має місце рівність R⁺(x)= R^-(x) для всіх x Î W.

Відношення R називається асиметричним, якщо (тобто з двох виразів x R y та y R x хоча б один не вірний). У матриці симетричного відношення для всіх i, j. Тобто з двох симетричних елементів a_ij і a_ji хоча б один обов’язково дорівнює 0. Зауважимо, що антирефлексивність є обов’язковою умовою асиметричності.

Відношення R називається антисиметричним, якщо x R y та y R x можуть бути вірні одночасно тоді і тільки тоді, коли x = y. Для матриці антисиметричного відношення справедливо , якщо .

Відношення R називається транзитивним, якщо (якщо з та випливає ). Якщо для всіх i, j –­ відношення транзитивне.

Відношення R називається ациклічним, якщо , тобто з xRz₁, z₁Rz₂..., z_k-1Ry випливає, що .

Відношення R називається від’ємно транзитивним, якщо його доповнення транзитивне.

Відношення R називається сильно транзитивним, якщо воно водночас транзитивне та від’ємно транзитивне.