Дискретная математика: Учебное пособие. Часть I - Основания дискретной математики, страница 6

Отображение, заданное между элементами одного множества Х, называют отношением. Между математическими объектами такими отношениями могут быть {=, ¹, ³, >, <, £}, а между “нематематическими” объектами {“x принадлежит y”, “x часть y”, “x смежный y”, “x  родственник y”, “x родитель y”, “x находится рядом с y”,..}.

          Например, “2=2”, “3>2”, “факультет ФАПУ часть университета КГТУ”, “судно <имя> находится рядом с причалом <номер>” и т.п.

Очевидно, что каждое отношение r=(xi, xj) или r=(x1, x2,..,xn) есть кортеж, а их множество есть подмножество X2 или Xn, т.е.

R={(xi, xj)| xi, xjÎX}ÍX2 или R={(x1, x2,..,xn)| xiÎX}ÍXn.

Если n=1, то отношение называют унарным или одноместным. Такое отношение r(x) равносильно заданию предиката Р(х) на области определения для формирования подмножества, удовлетворяющего заданному условию.

Если n=2, то отношение называют бинарным или двухместным. Такое отношение позволяет сравнивать по заданному предикату P(xi, xj) элементы множества X.

Если n=n, то отношение называют n- арным или n-местным.

Бинарные отношения между элементами множества X удобно описывать матрицами (ХÄХ), строки и столбцы которых есть элементы множества, а на пересечении i-ой строки и  j-го столбца ставят знак “1”, если задано отношение

 r(i, j) между i-м и j-м элементами и “0” в противном случае, т.е.

                                        1, если (xi,xj)ÎR;

                              rij=    

0, если (xi,xj)ÏR.

Например, таблица на с.15 представляет также отношение r2(xi, xj) для предиката Р2(x1, x2):- ”xi и xj имеют общий делитель”.

Отношения также удобно представлять в операторной форме:

r: X®X или r: Xn-1®X.

Каждому отношению r может быть найдено обратное r-1.

r-1: X¬X или r-1: X ¬(X1ÄX2Ä..ÄXn-1).

В этом случае R-1={(x, x)|xÎX}ÍX2 или R-1={(x, x1, x2,..xn-1)| xiÎX}ÍXn.

Анализ отношений позволяет выделить характерные свойства.

Бинарное отношение рефликсивно, если для каждого хiÎХ имеем r(xi; xi)=1. Такими отношениями являются “..=..”, “..быть похожим..”, “..быть изоморфным..”, “..быть эквивалентным..” и т.п. При матричном описании такого отношения на главной диагонали матрицы будут только “1”, т.е. r(xi, xi)=1.

Бинарное отношение антирефлексивно, если для каждого хiÎХ имеем

r(xi, xi)=0. Такими отношениями являются “..>.. ”, “..<..”, “быть родителем” и т.п..

При матричном описании такого отношения на главной диагонали матрицы будут только “0”, т.е. r(xi, xi)=0.

Бинарное отношение симметрично, если для любой пары (xi, xj)ÎR имеем r(xi, xi)=r(xj, xi)=1. Такими отношениями являются “..¹..”, “..быть похожим..”, “..быть эквивалентным..”, “..быть родственником..” и т.п.. При матричном задании такого отношения будет симметричное расположение “1” относительно главной диагонали, т.е. r(xi, xi)=r-1(xj, xi).

Бинарное отношение антисимметрично, если для любой пары (xi, xj) при i¹j имеем r(xi, xi)¹r(xj, xi), а при i=j имеем r(xi, xi)=1. Такими отношениями являются “..³..”, “..£..” и т.п.. При матричном задании такого отношения это означает несимметричное расположение “1” относительно главной диагонали и наличие “1” на главной диагонали.

Бинарное отношение асимметрично, если для любой пары (xi, xj) при i¹j имеем r(xi, xi)¹r(xj, xi), а при i=j имеем r(xi, xi)=0.. Такими отношениями являются “..>..”, “..<..”, “быть родителем” и т.п. При матричном задании такого отношения это означает несимметричное расположение “1” относительно главной диагонали и наличие “0” на главной диагонали.

Бинарное отношение транзитивно, если для любых элементов xi, xj, xkÎХ существует r(xi, xi)=1 тогда и только тогда, когда существует r(xi, xk)=1 и

r(xk, xi)=1. Такими отношениями являются “..>..”, “..<..”, “быть родителем”, “быть родственником” и т.п..

Знание этих свойств позволяет выделять классы отношений. Наиболее изученными являются классы эквиваленции, частичного и строгого порядка.