Алгебра бинарных отношений и отображений

     Для

     Полагают  также:

     Унарная операция обращения определяется для  отношений следующим образом: для  обратным называется отношение такое что:

     (b, a)

     Матрица М() транспонирована по отношению к М()  (строки становятся столбцами, а столбцы строками), т.е. М(): = , а граф получается из графа обращением всех дуг.

     Теорема 1.5. Операция обращения отношений обладает следующими свойствами:

1. ,

     для всех ,

     Доказательство. Первое свойство очевидно, если обратиться к графовой интерпретации отношения.

     Второе  свойство доказывается следующими рассуждениями:

     ()

      &

      

     Следствием  теоремы 1.5 является равенство 

     Отметим некоторые связи умножения и  обращения отношений с теоретико-множественными операциями .

     Теорема 1.6. Для любых отношений и справедливы следующие утверждения:

2. ,
3. ;

     .

1. Используется дистрибутивность конъюнкции относительно дизъюнкции и взаимодействие квантора существования с дизъюнкцией;

     ( ) 
 
 

       
 

     

Вторая формула  в этом пункте доказывается вполне аналогично.

2. Вначале доказательство проводится как в случае 1):

     ( ) 
 

     (На этом этапе доказательства равносильность формул нарушается: наличие   с нужными свойствами не гарантирует существование элемента b, удовлетворяющего предыдущей формуле.) 
 
 

     

Итак, всякая пара, принадлежащая отношению 

     

3)Пусть Тогда для некоторого

     

b будет:  () Отсюда ()

     

. Соотношения 4) –  6) достаточно очевидны.

     

Бинарные отношения  между элементами одного множества называется однородным. При этом говорят, что является отношением в множестве S. В n – элементом множестве имеется различных отношений.

     

Совокупность  Р(SS) всех отношений в множестве S представляет собой алгебраическую структуру: кроме трех теоретико – множественных операций в Р(SS) можно выполнять еще умножение и обращение. Заметим, что в общем случае операция умножения отношений является лишь частичной – она определена далеко не всегда, а операция обращения, хотя и применима к любому отношению, имеет своим результатом отношение в общем случае между другими множествами.

     

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

     

Абстрактной алгеброй отношений называется алгебра (R, 0,1,)

     

Типа (2,2,2,1,1,0,0,0), где (R, 0,1) – булева алгебра, операция умножения

∘

, обращения   и выделенный дополнительный элемент e таковы, что выполняются следующие тождества:

     

Х.  

     

x

∘

(y

∘

z)= (x

∘

y)

∘

z

     

(закон ассоциативности для умножения),

     

XI.

     

x

∘

 e  = e

∘

x = x

     

(закон нейтральности элемента e),

     

XII.

     

x

∘

(yz) = (xy) (x

∘

z),  (xy)

∘

z = (x

∘

z)(y

∘

z)

     

(законы дистрибутивности умножения относительно объединения),

     

XIII. 

     

(законы инвалютивности для обращения),

     

XVI.

     

()

     

(закон Шредера).

     

Теорема 1.7. Система (Р(SS), ) является алгеброй отношений.

     

Доказательство. Согласна теореме 1.1 система

     

(Р(SS), ) – булева алгебра. Законы X, XI выполняются для однородных отношений вследствие теоремы 1.3. Тождества XII и XIV – это формулы 1) и 4) из теоремы 1.6. Остается убедиться в справедливости закона Шредера, т. е. доказать, что для любых отношений Р(SS) имеет место равенство () Предположим противное, т. е. что для некоторых отношений Р(SS) пересечение () тогда найдется пара ()SS такая, что () и () ). Из последнего соотношения следует существование элемента такого, что () и одновременно (b, c) Но так как и (), то (b, c) . Пришли к противоречию: отношения и не должны иметь общих пар по определению дополнения. Таким образом, предположение () привело к противоречию, и, следовательно, тождество XIV истинно для бинарных отношений на множестве S.

     

Алгебру отношений  образует любой набор отношений  в некотором фиксированном множестве, замкнутый относительно теоретико  – множественных операций, умножения  и обращения и содержащий пустое, универсальное и тождественное  отношения на этом множестве. Все  такие алгебры отношений называются конкретными алгебрами отношений. К сожалению, не всякая абстрактная  алгебра отношений изоморфна  подходящей конкретной.

     

Из теорем 1.2 и 1.4 следует, что и двоичные булевы матрицы размерности nn образуют алгебру отношений, она изоморфна алгебре всех отношений на некотором фиксированном n- элементом множестве. Именно, имеет место

     

Теорема 1.8.  Алгебра ( , +,) является алгеброй отношений.

     

Теорема  1.9. Для любых отношений следующие утверждения:

1. 5. =
   8. ;

        

   козательство. Сразу  отметим как вполне очевидные  свойства 1), 4), 7), 8), 10).

        

   Логическая структура  доказательства формулы 2) такая же, как при доказательстве формулы 1) из теоремы 1.5:

        

   b ()()

        

   ()) 
   

        

     или

        

    

        

    (b или bb

   • Множества и состоят из одних и тех же элементов, и, следовательно, совпадают.

        

   Логическая схема  доказательства свойства 3) та же. Что и в случае 2) теоремы 1.4.

        

   Бинарное отношение  называется 1- полным, если =А и 2- полным, если = В. В матричной интерпретации 1- полнота для означает, что в матрице М() нет нулевых строк, а 2- полнота равносильна отсутствию в М() нулевых столбцов. В графе 1- полного отношения из каждой вершины исходит по крайней мере одна дуга, а 2-полнота по графу проверяется наличием в каждой вершине входящей дуги. Отношение, одновременно 1-   и 2- полное, называется полным.

        

   Отношение  , по определению, однозначно, если для любого содержит не более одного элемента, другими словами, если тождественно истинна следующая формула (при х,):

        

   (x, ) (x, ) .

        

   Однозначное 1- полное отношение  между множествами А и В называется отображением множества А в множество В или функцией, заданной на А и принимающий значение в В. В этом случае  применяется запись

        

   Отношение тогда и только тогда будет отображением, когда каждый срез его состоит в точности из одного элемента. Этот элемент называется образом элемента a и обозначается через , т. е. применяется обычная функциональная символика.

        

   Для поэлементного  задания отображения используют запись вида a, например, x или .

        

   Отношение называется обратно однозначным, если однозначно обратное ему отношение тождественной истинности формулы

        

   () ()

        

   Однозначность конечного отношения  распознается по матрице наличием в каждой ее строке не более одной единицы. Аналогично обратная однозначность для равносильна наличию не более одной единицы в каждом столбце матрицы .

        

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

        

   Если  - отображение, то в каждой строке матрицы стоит точно одна единица, а из каждой вершины графа исходит точно одна дуга.

        

   Говорят, что  взаимно однозначно, если оно однозначно и обратно однозначно.

        

   Взаимно однозначное  отображение  называют вложением множества А в множество В. Употребляют также термины: инъективное отображение, инъекция. Наложение множества А на множество В – это 2- полное отображение . Синонимами наложения являются: отображение А на В, сюръективное отображение, сюръекция.

        

   Полное взаимно  однозначное отношение  между множествами А и В называется взаимно однозначным соответствием между А и В; принята также терминология- биективное отображение, биекция. Матрица для конечного биективного отображения является квадратной перестановочной матрицей: в каждой строке и в каждом столбце ее стоит точно одна единица.

        

   Язык алгебры  отношений позволяет по-новому увидеть  смысл введенных понятий.

        

   Именно, имеет  место

        

   Теорема 1.10. Пусть . Каждая из следующих формул равносильна указываемому для нее свойству:

        

   1)              (1-полнота),

        

   2)              (2-полната),

        

   3)              (однозначность)

        

   4)             (обратная однозначность),

        

   5) ) = (биективность).

        

   Доказательство.

   1. В графовой интерпретации 1- полнота означает, что из каждой вершины исходит по крайней мере одна - дуга. Возвращаясь по этой же дуге, т. е. проходя по - дуге, получаем, что каждая пара () входит а произведение  , и значит, .
   2. Доказывается аналогично.
   3. Определение однозначности может быть записано в следующем виде:

        (x, ) (x, ) , или

                                                             (,) ,

        что и означает включение  .

   4. Доказывается аналогично 3).
   5. Биективность – это одновременное выполнение свойств 1) – 4). Если (1-полнота) и )   (обратная однозначность), то ) как множества, состоящие из одних и тех же элементов. Аналогично из 2) и 3) следует равенство

        

   Доказательство. Если - отображения, то

        

   . Тогда  и, значит, однозначно. Аналогично доказывается сохранение свойств инъективности, сюръективности и биективности при умножении.

        

   Совокупность  всех отображений множества А  в множество В обозначим через  F(A). Следующий результат показывает, что свойства инъективности и сюръективности тесно связаны с некоторыми специальными уравнениями для отображений.

        

   Теорема 1.11. Если f – отображение множества А в множество В, то:

   1. уравнение f ∘ x= разрешимо в F( A тогда и только тогда, когда f инъективно;
   2. уравнение x∘ f = разрешимо в F( A тогда и только тогда, когда f сюръективно.

        

   Отображения непустого  множества S в себя называются его преобразованиями. Из теоремы 1.10 видно, что F(S S) =

        

   Совокупность  полных взаимно однозначных преобразований множества S обозначим через К(). Из теоремы 1.10 получаем:

        

   К( = .

        

   Согласно из теоремы 1.10 множество F(S S) замкнуто относительно умножения. Очевидно,  что . Множество К(замкнуто не только относительно умножения, но и относительно обращения. Поэтому элементы множества К ( называются обратными преобразования множества S.

        

   Следующий результат  находит многочленные применения.

        

   Теорема 1.12. Для преобразования  f конечного множества S следующие условия равносильны:

   1. f отображает S на S (т.е. f сюръективно);
   2. f взаимно однозначно (т.е. f инъективно);
   3. f обратимо (т.е. f биективно).

        

   Доказательство. Если множество S имеет n элементов, то граф , соответствующий преобразованию  f , имеет n вершин и n дуг: из каждой вершины исходит точно одна дуга.

        

   Из 1) следует 2). Пусть f  отображает S на S. Если f не взаимно однозначно, то в имеется вершина, в которую входят как минимум две дуги. Получается, что n дуг имеют больше чем n концов – приходим к противоречию.

        

   Из 2) следует 3). Если f взаимно однозначно, то в каждую вершину входит самое большее одна дуга. Это означает, что n  дуг графа имеют точно n  различных концов. Следовательно, в каждую вершину графа входит дуга, т.е. f

        

   Отображает S на S.

        

   Из 3) следует 1) и 2). Обратимые преобразования множества  S взаимно однозначны и отображают S на S.

        

   Примеры отображений  n на множестве натуральных чисел показывают, что для преобразований независимы, так что в отличие от теоремы 1.6 теорема 1.7 не является теоремой алгебры отношений.

        

   Конструкция декартова  произведения может быть обобщена и  на большее, чем 2, число множеств. Именно для n пологаем:

        

     (рекурсивная формула).

        

   Если , то говорят о n-й декартовой степени множества А и пишут: .

        

   Элементы декартового произведения записываются в виде (), где , и называются упорядоченными n- системами.

        

   По определению, при  n получаем:

        

   ( = ((), .

        

   Отсюда следует, что две упорядоченные n- ки равны тогда и только тогда, когда у них равны соответствующие компоненты.

        

   Пусть n 1. Под n-арным отношением между множествами понимают всякое подмножество декартова произведения ,  т.е. любой элемент множества P() всех подмножеств множества .

        

   Теорема 1.13. Совокупность P() всех n-арных (n 1) отношений между множествами , рассматриваемая вместе с теоретико - множественными операциями объединения, пересечения и дополнения, а также вместе с выделенным пустым и универсальным отношениями, является булевой алгеброй.

        

   Понятие проекций бинарного отношения обобщается на случай произвольного n- арного (n 1) отношения следующим образом. Если 1- некоторые числа из множества, то   называется отношение (при )

        

   P:= .

        

   При n=2 и k= 1  получаются первая и вторая проекции бинарного отношения. 
    
    
    
    
   

        

     
   

        

       
    
   

   §3. Примеры.

        

   Задача  1. Докажите следующее равенство:

        

                         (Α ∩ Β )× (Κ ∩ Μ ) = (Α  × Κ ) ∩ (Β × Μ ) .

        

           Решение. Равенство двух множеств  мы докажем с помощью двух

        

   включений, объединив  их одной записью. Заметим, что элементами

        

   множеств в  данном случае являются упорядоченные  пары точек. Итак, пусть

        

   (x, y )

   ∈

   (Α ∩ Β  )× (Κ ∩ Μ )

   ⇔

   x

   ∈

   (Α ∩ Β  ), y

   ∈

   (Κ ∩ Μ  )

   ⇔

        

   ⇔

   x

   ∈

    Α, x

   ∈

    Β , y

   ∈

    Κ , y

   ∈

    Μ 

   ⇔

   x

   ∈

    Α, y

   ∈

    Κ , x

   ∈

    Β , y

   ∈

    Μ 

   ⇔

        

   ⇔

   (x, y )

   ∈

    Α × Κ  , (x, y )

   ∈

    Β × Μ 

   ⇔

   (x, y )

   ∈

   (Α × Κ ) ∩ (Β × Μ ) . 
   

        

        Задача 2. Докажите, что для любых непустых множеств Α , Β , Κ из

        

   равенства (Α  × Β )

   ∪

   (Β × Α ) = Κ × Κ следует, что Α = Β = Κ .

        

   Решение. Для  доказательства данного утверждения  установим два

        

   равенства Α = Κ  и Β = Κ .

        

    Для произвольных x

   ∈

    Α и y

   ∈

    Β

        

   (x , y )

   ∈

    Α × Β 

   ⇒

   ( x , y )

   ∈

    Κ × Κ 

   ⇒

   x

   ∈

    Κ , y

   ∈

    Κ 

   ⇒

    Α 

   ⊆

    Κ , Β 

   ⊆

    Κ .

        

    С другой стороны, для произвольного x

   ∈

    Κ(x, x )

   ∈

    Κ × Κ 

   ⇒

   (x, x )

   ∈

    Α × Β  или (x, x )

   ∈

    Β × Α 

   ⇒

   x

   ∈

   Α и x

   ∈

   Β

   ⇒

    Κ 

   ⊆

    Α и Κ 

   ⊆

    Β .

        

      Таким  образом, Α = Β = Κ .

        

    Задача 3.       На множестве Α = {5,6,7,8,9,10,11,12,13,14,15} задано

        

   бинарное отношение  ρ = {(x, y ) : x делится на y}. Нарисуйте  граф данного

        

   бинарного отношения.

        

   Решение. Расположим на плоскости точки множества  Α . Точки

        

   x, y

   ∈

    Α , для  которых пара (x, y )

   ∈

    ρ , соединим  стрелкой, направленной от

        

   x к y . Пары (x, x )

   ∈

    ρ изобразим  петлей вокруг точки x . Результатом  такого

        

   построения будет  граф

        

       5        6          7           8       9

        

     10      11        12         13        14

        

    Задача 4. Для следующего бинарного отношения, определенного на

        

   множестве R , найдите  область определения, область значений и нарисуйте

        

   декартову диаграмму

        

                                         { ρ = (x, y ) : x 2 = y . }

        

         Решение. В соответствии с определением

        

                           D ρ = {x

   ∈

   R :

   ∃

   y (x, y )

   ∈

    ρ } = R .

        

                          R ρ = {y

   ∈

   Υ :

   ∃

   x     (x , y )

   ∈

    ρ } = R +

   ∪

   0   .

        

      Декартова диаграмма для данного бинарного отношения имеет вид

        

                                   y     x

        

      Задача 5. Для каждого из следующих бинарных отношений выясните,

        

   какими свойствами (рефлексивность, симметричность, антисимметричность,

        

   транзитивность) оно обладает и какими не обладает.

        

   1)     ρ = {(1,2 ), (2,1), (1,1), (1,3), (3,2 ), (3,3)} на множестве  Χ = { ,2,3};

        

                                                                            1

        

   2)     ρ = {(x, y ) : x − y

   ∈

    Ζ } на множестве  Χ = R ;

        

   3)     ρ = {(x, y ) : 2 x = 3 y} на множестве Χ  = Ζ ;

        

   4)     ρ = {(x, y ) : x

   ⊆

   y} на множестве  Χ = Ρ (Ζ ) .

        

   Решение.

        

   1)    Данное  отношение не является рефлексивным, поскольку для точки

        

   2

   ∈

    Χ пара (2,2 )

   ∉

    ρ ; не является  симметричным, поскольку, например, пара

        

   (1,3)

   ∈

    ρ , а пара (3,1)

   ∉

    ρ ; не является  антисимметричным, поскольку,

        

   например, пары (1,2) и (2,1) принадлежат ρ , но 1 ≠ 2 ; не является

        

   транзитивным, поскольку, например (3,2 )

   ∈

    ρ , (2,1)

   ∈

    ρ , а (3,1)

   ∉

    ρ .

        

   2)    Данное  отношение является рефлексивным, поскольку для любой

        

   точки x

   ∈

   R разность x −  x = 0

   ∈

    Ζ , т.е. (x, x )

   ∈

   R ; является  симметричным,

        

   поскольку принадлежность любой пары (x, y ) отношению ρ означает

        

   x − y = k

   ∈

    Ζ , но тогда  y − x = −k 

   ∈

    Ζ , т.е.  пара ( y, x )

   ∈

    ρ ; не является антисиммеричным, поскольку, например, пары (1.2,3.2 )

   ∈

    ρ и (3.2,1.2 )

   ∈

    ρ ,

        

   но 3.2 ≠ 1.2 ; является транзитивным, поскольку для любых x, y, z

   ∈

   R

        

   принадлежность  пар (x, y ) и ( y, z ) отношению ρ означает x − y = k

   ∈

    Ζ и

        

   y − z = n

   ∈

    Ζ , но тогда  x − z = k + n

   ∈

    Ζ , т.е. (x, z )

   ∈

    ρ .

        

   3)       Данное отношение не является  рефлексивным, поскольку из всех  пар

        

   (x, x ), x

   ∈

    Ζ только  пара (0,0)

   ∈

    ρ , ведь  для всех остальных x

   ∈

    Ζ не

        

   выполнено равенство 2 x = 3x ; не является симметричным, поскольку,

        

   например, пара (3,2 )

   ∈

    ρ ( 2

   ⋅

   3 = 3

   ⋅

   2 ), а пара (2,3)

   ∉

    ρ ( 2

   ⋅

   2 ≠ 3

   ⋅

   3 ); является

        

   антисимметричным, поскольку для любых пар (x, y )

   ∈

    ρ , ( y, x )

   ∈

    ρ

        

   одновременно  выполняются равенства 2 x = 3 y и 2 y = 3x , т.е. 9 x = 4 x и

        

   4 y = 9 y , но это  может быть только в том  случае, если x = y = 0 ; не является

        

   транзитивным, поскольку, например, пара (9,6 )

   ∈

    ρ ( 2

   ⋅

   9 = 3

   ⋅

   6 ), пара

        

   (6,4)

   ∈

    ρ ( 2

   ⋅

   6 = 3

   ⋅

   4 ), но пара (9,4)

   ∉

    ρ ( 2

   ⋅

   9 ≠ 3

   ⋅

   4 ).

        

   4)       Данное отношение не является  рефлексивным, поскольку для

        

   ∅

    

   ∈

    Ρ (Ζ ) пересечение 

   ∅

    ∩ 

   ∅

   =

   ∅

   , т.е. (

   ∅

   ,

   ∅

   )

   ∉

    ρ ; является  симметричным,

        

   поскольку принадлежность любой пары (x, y ) отношению ρ означает

        

   x ∩ y ≠ 

   ∅

   , но тогда  y ∩ x ≠ 

   ∅

   , т.е. пара ( y, x )

   ∈

    ρ ; не является

        

   транзитивным,            поскольку,        например,            пара    ({1,2}, {2,3})

   ∈

    ρ

        

   ( { ,2}∩ {2,3} = {2} ≠ 

   ∅

   ) и пара ({2,3}, {3,6,7})

   ∈

    ρ ( {2,3}∩  {3,6,7} = {3} ≠ 

   ∅

   ), но

        

     1 пара ({ ,2}, {3,6,7})

   ∉

    ρ , так  как { ,2}∩ {3,6,7} =

   ∅

   . 
    
   

        

   Задача  6. Пусть Χ - произвольное множество, обозначим символом

        

     отношение на множестве  Χ вида

        

   = {(x, y ) : x = y} = {(x, x ) : x

   ∈

    Χ }.

        

   Докажите, что  для любого бинарного отношения  ρ между элементами

        

   множеств Α  и Β выполняются равенства:

        

                                  ρ = ρ ρ = ρ .

        

          Решение.

        

     ρ = {(x, y )

   ∈

    Α × Β  :

   ∃

   z

   ∈

    Β (x, z )

   ∈

    ρ , (z , y )

   ∈

    Ι Β } =

        

   = {(x, y )

   ∈

    Α × Β  :

   ∃

   z

   ∈

    Β (x, z )

   ∈

    ρ , z = y} = {(x, y )

   ∈

    Α × Β  : (x, y )

   ∈

    ρ } = ρ ;

        

   ρ οΙ Α = {(x, y )

   ∈

    Α × Β  :

   ∃

   z

   ∈

    Α (x, z )

   ∈

    Ι Α , (z , y )

   ∈

    ρ } =

        

   = {(x, y )

   ∈

    Α × Β  :

   ∃

   z

   ∈

    Α x = z , (z , y )

   ∈

    ρ } = {(x, y )

   ∈

    Α × Β  : (x, y )

   ∈

    ρ } = ρ . 
    
    
    
    
    
    
    
    
    
    
    
    
   

        

   Заключение 
   

        

    

   В данной курсовой работе были рассмотрены понятия  декартово произведения множеств и  бинарного отношения, показаны их взаимосвязь  с матрицами и графами, основные операции над бинарными отношениями, доказаны  их свойства и проанализированы классификации бинарных отношений  на основе свойств этих операций. Доказаны теоремы об известных алгебрах отношений. А так же приведены примеры  с решениями 
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
   

        

   Список  литературы:

   1. Богомолов, А.М., Салий, В.Н. Алгебраические основы теории дискретных систем. –М.: Наука, 1997,.с.30-49
   2. Куликов, Л.Я. Москаленко А.И., Фомин А.А. Сборник задач по алгебре и теории чисел. –М.: Просвещение, 1993, с.22-26