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

Автор: Пользователь скрыл имя, 29 Ноября 2011 в 16:37, курсовая работа

Описание работы

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

Содержание

Введение…………………………………………………………………...2 стр.
§1. Алгебры отношений………………………………………………...3-5 стр.
§2. Свойства отношений. Теоремы………………………………..... 6-21 стр.
§3. Примеры……………………………………………………….....22-25 стр.
Заключение……………………………………………………………….26 стр.
Литература.................................................................................................27 стр.

Работа содержит 1 файл

на сайт.docx

— 86.01 Кб (Скачать)
 
 

     Оглавление

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

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

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

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

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

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

     Введение 

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

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

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

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

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

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

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

     А В = .

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

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

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

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

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

  1.    (А - В)С = (А С) – (В С),
  2. А С 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

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

          = 1

           = 1

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

          = 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

          

           

Информация о работе Алгебра бинарных отношений и отображений