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

 
 

     Оглавление

     Введение…………………………………………………………………...2 стр.

     §1. Алгебры отношений………………………………………………...3-5 стр.

     §2. Свойства отношений. Теоремы………………………………..... 6-21 стр.

     §3. Примеры……………………………………………………….....22-25 стр.

     Заключение……………………………………………………………….26 стр.

     Литература.................................................................................................27 стр. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Введение 

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

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

     §1. Алгебры отношений

     Пусть А и В – некоторые множества  произвольные непустые множества.

       Декартовым произведением множества  А на множество В называется  множество А В. Элементами которого являются всевозможные пары (а, b), где первый элемент берется из множества А, а второй – из множества В. Две такие пары считаются равными, если у них совпадают и первые, и вторые элементы:

       (a, b) = (c, d): a = c d = d.

     Пример 1. Если А = и В = , то

     А В = .

     Несложными  рассуждениями устанавливается  справедливость следующих соотношений :

1.   (А В) С = (А С) (В С),

     А (В С) = (А В) (А С);

2.    (АВ)С = (АС) (В С),

     А(ВС) = (АВ)(А С);

3.    (А - В)С = (А С) – (В С),
4. А С D А В С D.

     Декартово произведение SS называется декартовым квадратом множества S.

     Бинарным  отношением между множествами А  и В называется всякое подмножество декартова произведения А В, т. е. любой элемент множества P(A B) всех подмножеств множества А В.

     Если  = m, = n, то декартово произведение А В будет состоять из mn различных пар.

     Бинарные  отношения будем обозначать строчными  греческими буквами. Если (, b) , то говорят, что элементы находится с элементом b в отношении .

     Среди всех отношений между множествами  А и В выделяются :

     пустое  отношение , оно не содержащее ни одной пары; универсальное отношение, содержащее все возможные пары, т. е. само декартово произведение А В. Для любого отношения P(А В) имеют место включения 

       А В.

     Есть  два удобных способа представления  отношений между элементами конечных множеств:

1. с помощью двоичных булевых матриц;
2. с помощью графов.

     Пусть А = , В = , А В. 

     Построим  матрицу М() размерности m n следующим образом. Строки этой матрицы пометим элементами множества А, расположенными в некотором фиксированном порядке, а столбцы аналогично пометим элементами множества В. Затем положим в качестве элементов матрицы М():

        =

     Здесь 0 и 1 – элементы двоичной булевой  алгебры . Таким образом, элемент    представляет собой логическое значение высказывания: «пара принадлежит отношению », или, что то же самое, «элемент находиться в отношении  с элементом b».

     Пример 2. Пусть А = и В = , и задано отношение .

     Тогда  =

     (считается,  что порядок элементов в А  и В задан при их перечислении).

     Очевидно, что различным отношениям между  множествами А и В соответствует  различные двоичные булевы матрицы. Подчеркнем, что порядок элементов  в А и В в этом случае раз  и навсегда фиксирован. Каждая двоичная булева mn – матрица М представляет в точности одно отношение (М) между А и В, именно:

     (М): = .

     Из  способа построения булевой матрицы  , соответствующей отношению , и отношения (М) по заданной двоичной булевой матрице М со строками и столбцами, нумерованными элементами двух конечных множеств, получаем:

     (М()) = ,  .

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

     §2. Свойства отношений. Теоремы.

     Теорема 1.1. Совокупность Р(А) всех бинарных отношений между множествами А и В, рассматривая вместе с теоретико - множественными операциями объединения, пересечения и дополнения и с выделенными пустым и универсальными отношениями , т. е. система (Р(А), ¯, , А) является булевой алгеброй.

     Теоретико – множественные операции над  отношениями естественно интерпретируются на языке двоичных булевых матриц.

     Пусть совокупность всех двоичных булевых - матриц. В этом множестве вводятся операции сложения +, пересечения и дополнения , определяемые соответственно поэлементными (в ) выполнением логических операций сложения, умножения и дополнения:

     := : ; := .

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

     Теорема 1.2. Пусть А и В – конечные множества, содержащие соответственно m и n элементов. Тогда отображение М: Р(), сопоставляющее каждому отношению соответствующую ему булеву матрицу, обладает следующими свойствами:

1. М()= М() = ,
2. М() = М() + М(),
3. М() = М() М(),
4. М() = ,
5. М() = 0
6. М(А В) = I,

     т. е. алгебры (Р(А В), , и ( 0, I) являются изоморфными булевыми алгебрами.

     Доказательство. 1) Это свойство становиться очевидным, если считать, что строки и столбцы  каждой булевой m - матрицы помечены соответственно элементами множества А и множества В, перечисленными в некотором фиксированном порядке:

А = , B = .

2)Покажем,  что в m – матрицах М() и М() + М() единицы расположены на одних и тех же местах (тогда на остальных позициях будут нули, и матрицы совпадают). Имеем:

      = 1 ()  
или () ) = 1 или = 1)

       + = 1

3. Здесь действуем по аналогии со случаем 2), учитывая свойства теоретико – множественной операции пересечения и операции пересечения булевых матриц:

      = 1

       = 1

4. К цели ведет следующая цепочка равносильных прдложений:

      = 1 0

       = 1 = 1.

 утверждений  5) и 6) очевидна.

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

     Пусть и . Произведением отношения

     на  отношение  называется отношением между множествами А и С, обозначаемое   и такое, что:

     (а,  с)  : (b )((, b) (b, c) ).

     Другими словами , вхождение пары (а, с) в отношение  равносильно существованию «посредника»  b B, с которым   находится в отношении и который сам находится с c в отношении .

     Умножение отношений можно проиллюстрировать с помощью

графов.

     Пример 3. Пусть отношение А В такое же, как в примере 10, а отношение А В, где С = , зададим списком принадлежащих ему пар: Тогда в отношение будут входить следующие пары (их элементы связывает двухзвенный путь – сначала по - дуге, а затем по - дуге):

       = .

 А. Тождественным отношением, или отношением равенства на А называется отношение А такое, что

         =  .

, состоит из всевозможных пар с одинаковыми элементами.

ому отношению на n- элементом множестве А соответствует тождественная (единичная) булева n m – матрица Е:

     :=

ножество  дуг графа () состоит из петель при каждой вершине.

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

     Теорема 1.3. 1) Умножение отношений ассоциативно: для любых , и

      = () ;

     2) тождественные отношения являются нейтральными элементами относительно умножения: для любого

      =             и     

     1) Формально в производимой цепочке  рассуждений используется ассоциативность  логической связки конъюнкции  и правила ее взаимодействия  с квантором существования (можно  просто следить за содержательным  смыслом переходов):

     ()

     ()(() c  

      

     .

     Таким образованием, отношения  и состоят из одних и тех же пар, и, следовательно, совпадают.

     2) Имея в виду, что (x, y) означает x=y и что (x, x) -тождественно истинное высказывание, получаем для :

       ()((, с) )

     .

     .

     множение  отношений тесно связано с  операцией умножения для двоичных булевых матриц. Пусть M и N - двоичные булевы матрицы соответственно размерности m и n. Их произведением называется матрица  

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

     Теорема 1.4. Если , где А, В, С – конечные множества, то имеем место равенство

     М()

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

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

       = 1