2. Бінарні відношення. Способи Їх задання та властивості, необхідні для аналізу задач прийняття рішень.

Бінарним відношенням R на множині називається довільна підмножина R декартового добутку (декартовим добутком двох множин A і B називається множина пар елементів , де , ). Якщо пара елементів x і y знаходиться у бінарному відношенні R, то будемо позначати цей факт як або xRy. Якщо потрібно вказати множину , на якій задано бінарне відношення R, то будемо писати або .

Крім безпосереднього задання всіх пар, для котрих виконується відношення R, існує три основних способи задання відношень: матрицею, графом, перетинами.

Нехай множина містить n елементів: . Тоді матриця бінарного відношення A(R) задається елементами , : , якщо ; , якщо не виконується . З іншого боку, якщо задана матриця A розміром з нулів і одиниць та вибрано нумерацію елементів множини , що складається з n елементів, то тим самим на задається деяке відношення R=R(A) таке, що , виконано тоді і лише тоді, коли .

Задання бінарного відношення R графом здійснюється наступним чином. Елементам скінченої множини (при деякій нумерації) ставиться у взаємно-однозначну відповідність вершини графа G. Проведемо дугу від вершини до вершини тоді і лише тоді, коли виконується (при i=j дуга перетворюється у петлю при вершині ).

Якщо задано довільний граф G з n вершинами і вибрано нумерацію на множині , то тим самим на задається деяке відношення таке, що виконується тоді і лише тоді, коли у графі G є дуга . Граф є геометричним представленням відношення аналогічно тому, як графік є геометричним представленням функції. Геометрична мова корисна, якщо граф достатньо простий. Навпаки, вивчати й описувати складні графи з великою кількістю вершин часто зручно у термінах відношень.

Універсальним способом задання відношень (зокрема, на нескінченних областях) є задання за допомогою перетинів.Верхнім перетином називається множина елементів таких, що : . Аналогічно задається нижній перетин: .

Приведемо основні властивості бінарних відношень, що необхідні для аналізу задач прийняття рішень.

Рефлексивність. Відношення R називається рефлексивним, якщо для x, xRx, іншими словами: , де E – діагональне відношення. У матриці A(R) рефлексивного відношення на головній діагоналі стоять одиниці; у графі G(R) при кожній вершині мається петля; , для .

Антирефлексивність. Відношення R називається антирефлексивним, якщо з xRy випливає , іншими словами: . У матриці A(R) антирефлексивного відношення на головній діагоналі стоять нулі; у графі G(R) відсутні петлі; , для .

Симетричність. Відношення R називається симетричним, якщо з xRy випливає yRx, іншими словами: . Матриця A(R) симетричного відношення R симетрична ( для i,j); у графі G(R) разом з кожною дугою входить і дуга ; для .

Асиметричність. Відношення R називається асиметричним, якщо з xRy випливає , іншими словами: . У матриці A(R) асиметричного відношення для i,j; граф G(R) не може мати одночасно дуг і ; для і , .

Антисиметричність. Відношення R називається антисиметричним, якщо з xRy і yRx випливає x=y або . У матриці A(R) антисиметричного відношення для , ; граф G(R) не може містити одночасно дуги і при ; для і , , .

Транзитивність. Відношення R називається транзитивним, якщо з xRz і zRy випливає xRy або . У матриці A(R) транзитивного відношення для i, k ; у графі G(R) існує дуга , якщо існує шлях з x в y; для і .