Ирина Эланс

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

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

Оглавление

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

А В = .

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

(А В) С = (А С) (В С),

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

(АВ)С = (АС) (В С),

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

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

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

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

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

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

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

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

А В.

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

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

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

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

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

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

Тогда =

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

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

(М): = .

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

(М()) = , .

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

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

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

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

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

:= : ; := .

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

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

М()= М() = ,
М() = М() + М(),
М() = М() М(),
М() = ,
М() = 0
М(А В) = I,

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

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

А = , B = .

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

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

+ = 1

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

= 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

Для

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

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

(b, a)

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

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

для всех ,

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

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

()

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

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

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

,
;

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

( )

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

Вначале доказательство проводится как в случае 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 таковы, что выполняются следующие тождества:

Х.

∘

z)= (x

∘

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

XI.

∘

e = e

∘

x = x

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

XII.

∘

(yz) = (xy) (x

∘

z), (xy)

∘

z = (x

∘

z)(y

∘

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

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. Для любых отношений следующие утверждения:

4. =
7. ;
козательство. Сразу отметим как вполне очевидные свойства 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. Определение однозначности может быть записано в следующем виде:
1. Доказывается аналогично 3).
2. Биективность – это одновременное выполнение свойств 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

Алгебра бинарных отношений и отображений 📙 Курсовая → 🆔 6269