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

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

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

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

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

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

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

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

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

Відношення R називається ациклічним, якщо, тобто з xRz1, z1Rz2 ..., zk-1Ry випливає, що .

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

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