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

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

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

Очевидно, что каждое отношение r=(x_i, x_j) или r=(x₁, x₂,..,x_n) есть кортеж, а их множество есть подмножество X² или Xⁿ, т.е.

R={(x_i, x_j)| x_i, x_jÎX}ÍX² или R={(x₁, x₂,..,x_n)| x_iÎX}ÍXⁿ.

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

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

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

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

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

                                        1, если (x_i,x_j)ÎR;

                              r_ij=    

0, если (x_i,x_j)ÏR.

Например, таблица на с.15 представляет также отношение r₂(x_i, x_j) для предиката Р₂(x₁, x₂):- ”x_i и x_j имеют общий делитель”.

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

r: X®X или r: X^n-1®X.

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

r^-1: X¬X или r^-1: X ¬(X₁ÄX₂Ä..ÄX_n-1).

В этом случае R^-1={(x, x)|xÎX}ÍX² или R^-1={(x, x₁, x₂,..x_n-1)| x_iÎX}ÍXⁿ.

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

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

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

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

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

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

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

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

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

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

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