Аннотация:
Рассматриваются бинарные отношения в $n$-мерном
пространстве, являющиеся порядковыми, т.е. зависящими для каждой
пары точек
пространства лишь от соотношений ($>$, $<$, $=$) одноименных
компонент. Они могут быть представлены булевыми функциями от покомпонентных
соотношений. Исследуются на NP-трудность и полиномиальность
по представляющим булевым функциям задачи
распознавания отношения на транзитивность, ацикличность, полноту и др.
Получено решение этих задач для всех основных свойств отношений при задании
представляющих функций посредством дизъюнктивных и конъюнктивных нормальных
форм.
Табл. 1, ил. 1, библиогр. 6.