Бинарные отношения и их свойства реферат

Обновлено: 06.07.2024

Типичные примеры рефлексивных бинарных отношений. Понятие множества и его элементов. Операции над множествами: объединение, пересечение и разность. Декартово произведение множеств. Отношения функциональные, эквивалентности, порядка. Отношения степени n.

ВВЕДЕНИЕ

2. Слабая рефлексивность:

3. Сильная рефлексивность:

5. Слабая антирефлексивность:

6. Сильная антирефлексивность:

10. Сильная линейность:

11. Слабая линейность:

Рефлексивность, свойство бинарных (двуместных, двучленных) отношений, выражающее выполнимость их для пар объектов с совпадающими членами (так сказать, между объектом и его "зеркальным отражением"): отношение R называется рефлексивным, если для любого объекта х из области его определения выполняется xRx. Типичные и в наибольшей мереважные примеры рефлексивных отношений: отношения типа равенства (тождества, эквивалентности, подобия и т.п.: любой предмет равен самому себе) и отношения нестрогого порядка (любой предмет не меньше и не больше самого себя). Интуитивные представления о "равенстве" (эквивалентности, подобии и т.п.), очевидным образом наделяющие его свойствами симметричности и транзитивности, "вынуждают" и свойство Р., поскольку последнее свойство следует из первых двух. Поэтому многие употребительные в математике отношения, по определению Р. не обладающие, оказывается естественным доопределить таким образом, чтобы они становились рефлексивными, например, считать, что каждая прямая или плоскость параллельна самой себе, и т.п.

Глава 1. Элементы теории множеств

1.1 Множества

Наиболее простая структура данных, используемая в математике, имеет место в случае, когда между отдельными изолированными данными отсутствуют какие-либо взаимосвязи. Совокупность таких данных представляет собой множество. Понятие множества является неопределяемым понятием. Множество не обладает внутренней структурой. Множество можно представить себе как совокупность элементов, обладающих некоторым общим свойством. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:

Должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности.

Должно существовать правило, позволяющее отличать элементы друг от друга. (Это, в частности, означает, что множество не может содержать двух одинаковых элементов).

Множества обычно обозначаются заглавными латинскими буквами. Если элемент принадлежит множеству , то это обозначается:

Если каждый элемент множества является также и элементом множества , то говорят, что множество является подмножеством множества :

Подмножество множества называется собственным подмножеством, если

Используя понятие множества можно построить более сложные и содержательные объекты.

1.2 Операции над множествами

Основными операциями над множествами являются объединение, пересечение и разность.

Определение 1. Объединением двух множеств называется новое множество

Определение 2. Пересечением двух множеств называется новое множество

Определение 3. Разностью двух множеств называется новое множество

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

1.3 Декартово произведение множеств

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

Пусть и - множества. Выражение вида , где и , называется упорядоченной парой. Равенство вида означает, что и . В общем случае, можно рассматривать упорядоченную n-ку из элементов . Упорядоченные n-ки иначе называют наборы или кортежи.

Определение 4. Декартовым (прямым) произведением множеств называется множество упорядоченных n-ок (наборов, кортежей) вида

Определение 5. Степенью декартового произведения называется число множеств n, входящих в это декартово произведение.

Замечание. Если все множества одинаковы, то используют обозначение

1.4 Отношение

Определение 6. Подмножество декартового произведения множеств называется отношением степени n (n-арным отношением).

Определение 7. Мощность множества кортежей, входящих в отношение , называют мощностью отношения .

Замечание. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц. Сам термин "реляционное представление данных", впервые введенный Коддом [43], происходит от термина relation, понимаемом именно в смысле этого определения.

Т. к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых, все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей < (1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000) >можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.

В противоположность этому рассмотрим множество < (1), (1,2), (1, 2,3) >, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в , ни в , ни в . Из кортежей, входящих в это множество нельзя составить простую таблицу. Правда, можно считать это множество отношением степени 1 на множестве всех возможных числовых кортежей всех возможных степеней

но такая трактовка ничего нового, по сравнению с понятием подмножества, не дает.

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

Действительно, каждому отношению можно поставить в соответствие некоторое логическое выражение , зависящее от n параметров (n-местный предикат) и определяющее, будет ли кортеж принадлежать отношению . Это логическое выражение называют предикатом отношения . Более точно, кортеж принадлежит отношению тогда и только тогда, когда предикат этого отношения принимает значение "истина". В свою очередь, каждый n-местный предикат задает некоторое n-арное отношение. Таким образом, существует взаимно однозначное соответствие между n-арными отношениями и n-местными предикатами.

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

2. Примеры отношений

2.1 Бинарные отношения (отношения степени 2)

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

2.1.1 Отношение эквивалентности

Определение 8. Отношение на множестве называется отношением эквивалентности, если оно обладает следующими свойствами:

для всех (рефлексивность)

Если , то (симметричность)

Если и , то (транзитивность)

Обычно отношение эквивалентности обозначают знаком или и говорят, что оно (отношение) задано на множестве (а не на ). Условия 1-3 в таких обозначениях выглядят более естественно:

для всех (рефлексивность)

Если , то (симметричность)

Если и , то (транзитивность)

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

Пример 1. Рассмотрим на множестве вещественных чисел отношение, заданное просто равенством чисел. Предикат такого отношения:

Условия 1-3, очевидно, выполняются, поэтому данное отношение является отношением эквивалентности. Каждый класс эквивалентности этого отношения состоит из одного числа.

Пример 2. Рассмотрим более сложное отношение эквивалентности. На множестве целых чисел зададим отношение "равенство по модулю n" следующим образом: два числа и равны по модулю n, если их остатки при делении на n равны. Например, по модулю 5 равны числа 2, 7, 12 и т.д.

Условия 1-3 легко проверяются, поэтому равенство по модулю является отношением эквивалентности. Предикат этого отношения имеет вид:

Классы эквивалентности этого отношения состоят из чисел, дающих при делении на n одинаковые остатки. Таких классов ровно n:

2.1.2 Отношения порядка

Определение 9. Отношение на множестве называется отношением порядка, если оно обладает следующими свойствами:

для всех (рефлексивность)

Если и , то (антисимметричность)

Если и , то (транзитивность)

Обычно отношение порядка обозначают знаком . Если для двух элементов и выполняется , то говорят, что "предшествует" . Как и для отношения эквивалентности, условия 1-3 в таких обозначениях выглядят более естественно:

для всех (рефлексивность)

Если и , то (антисимметричность)

Если и , то (транзитивность)

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

Предикат данного отношения есть просто утверждение .

Пример 4. Рассмотрим на множестве всех сотрудников некоторого предприятия отношение, задаваемое следующим образом: сотрудник предшествует сотруднику тогда и только тогда, когда выполняется одно из условий:

является начальником (не обязательно непосредственным)

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

2.1.3 Функциональное отношение

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

Если и , то (однозначность функции).

Обычно, функциональное отношение обозначают в виде функциональной зависимости - тогда и только тогда, когда . Функциональные отношения (подмножества декартового произведения!) называют иначе графиком функции или графиком функциональной зависимости.

Предикат функционального отношения есть просто выражение функциональной зависимости .

2.1.4 Еще пример бинарного отношения

Пример 5. Пусть множество есть следующее множество молодых людей: , причем известны следующие факты:

Вовочка любит Вовочку (эгоист).

Петя любит Машу (взаимно).

Маша любит Петю (взаимно).

Маша любит Машу (себя не забывает).

Лена любит Петю (несчастная любовь).

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

Способ 1. Перечисление фактов в виде произвольного текста (как это сделано выше).

Введем необходимые определения.

Определение 1.1 . Декартовым произведением множеств X и Y называется множество X xY всех упорядоченных пар (x , y ) таких, что x X , y Y .

Определение 1.2 . Соответствием между множествами X и Y (или соответствием из X в Y ) называется любое подмножество декартова произведения X xY . Если множества X и Y совпадают, то соответствие между множествами X и Y называют также бинарным отношением на множестве X .

Отметим, что обычно соответствия задаются не путем указания подмножества a декартова произведения X xY , а путем указания свойства пар (x , y ), принадлежащих этому подмножеству

a. Например, отношение a= <(4 , 4 ), (3 , 3 ), (2 , 2 ), (4 , 2 )> на множестве X = 4 , 3 , 2 > можно определить как свойство "Делится" на этом подмножестве целых чисел.

Хорошо известными примерами отношений из школьного курса математики являются:

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

Факт принадлежности кортежа (x , y ) соответствию a, часто обозначают с помощью так называемой инфиксной формы записи: x ay . Типичными примерами таких записей из курса математики являются: x > y , a = b , 8 4 , m ||l , a b и т. п.

Отношения могут задаваться формулами:

y = x 2 +5x - 6 или

задают бинарные отношения на множестве действительных чисел;

x + y = любовь,

задает бинарное отношение на множестве людей. Этому отношению принадлежит любая пара людей, между которыми существует любовь.

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

"Вася + Таня = любовь",

увековечивающие принадлежность конкретной пары (Вася, Таня) отношению "любовь".

Рассмотрим еще три формы представления бинарных отношений: матричное представление и два графических представления. В качестве носителя отношения для иллюстрирующих примеров будем использовать множество X = a , b , c , d , e >.

Вначале рассмотрим метод, восходящий к аналитической геометрии. Начертим пару взаимно перпендикулярных осей (OX - горизонтальная ось, а OY - вертикальная ось) и на каждой отметим точки, представляющие элементы множества X (рис. 1).

Рис. 1. Координатная сетка

Считая метки a , b , c , d , e координатами точек на горизонтальной и вертикальной осях, отметим на плоскости точки с координатами (x , y ) такими, что (x , y ) . На рисунке 2 изображено множество точек, соответствующее отношению a= <(a , b ), (a , c ), (b , d ), (c , e ), (e ,b ), (e , e )>.

Рис. 2. Бинарное отношение a

Другой широко распространенный способ представления отношений основан на использовании ориентированных графов. При таком представлении элементы множества X изображаются вершинами графа (точками плоскости), а элементы (x , y ) отношения a дугами (стрелками), соединяющими первую компоненту x отношения со второй компонентой y . Граф бинарного отношения a изображен на рисунке 3.

Рис. 3. Граф бинарного отношения

Для бинарных отношений, определенных на конечных множествах, часто используется матричный способ задания. Пусть на некотором конечном множестве X задано отношение a. Упорядочим каким-либо образом элементы множества X = x₁ , x₂ , . x_n > и определим матрицу отношения A = [a_ij ] следующим образом:

Таким образом, матрица отношения a, представленного графом на рисунке 3, имеет вид

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

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

Инверсия (обратное отношение) — это множество и обозначается, как
Композиция (суперпозиция) бинарных отношений и — это множество и обозначается, как .
Свойства бинарных отношений

2. Слабая рефлексивность:

3. Сильная рефлексивность:

5. Слабая антирефлексивность:

10. Сильная линейность:

11. Слабая линейность:

Рефлексивность, свойство бинарных (двуместных, двучленных) отношений, выражающее выполнимость их для пар объектов с совпадающими членами (так сказать, между объектом и его "зеркальным отражением"): отношение R называетсярефлексивным, если для любого объекта х из области его определения выполняется xRx. Типичные и наиболее важные примеры рефлексивных отношений: отношения типа равенства (тождества, эквивалентности, подобия и т.п.: любой предмет равен самому себе) и отношения нестрогого порядка (любой предмет не меньше и не больше самого себя). Интуитивные представления о "равенстве" (эквивалентности, подобии и т.п.), очевидным образомнаделяющие его свойствами симметричности и транзитивности, "вынуждают" и свойство Р., поскольку последнее свойство следует из первых двух.

Поэтому многие употребительные в математике отношения, по определению Р. не обладающие, оказывается естественным доопределить таким образом, чтобы они становились рефлексивными, например, считать, что каждая прямая или плоскость параллельна самой себе, и т.п.Глава 1. Элементы теории множеств

Наиболее простая структура данных, используемая в математике, имеет место в случае, когда между отдельными изолированными данными отсутствуют какие-либо взаимосвязи. Совокупность таких данных представляет собой множество. Понятие множества является неопределяемым понятием. Множество не обладает внутренней структурой. Множество можно представить себекак совокупность элементов, обладающих некоторым общим свойством. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия:
Должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности.
Должно существовать правило, позволяющее отличать.

Содержание работы

Введение
1)Бинарные отношения
2)Свойства бинарного отношения
3)Инверсия и композиция бинарных отношений
4)Функциональные отношения
5)Виды функциональных отношений
6)Теорема
7)Доказательство

Файлы: 1 файл

Каирхан.docx

Министерство Образование и науки РК

Западно-Казахстанский Инженерно Гуманитарный Университет

Деканат Информатики и ВТ

Проверила: Жанысова А.Б

1)Бинарные отношения

2)Свойства бинарного отношения

3)Инверсия и композиция бинарных отношений

5)Виды функциональных отношений

Бинарные отношения

Бинарные отношения служат простым и удобным аппаратом для весьма широкого круга задач. Язык бинарных и n-арных отношений используется во многих прикладных (для математики) областях, например, таких как математическая лингвистика, математическая биология, математическая теория баз данных. Широкое использование языка бинарных отношений легко объясняется – геометрический аспект теории бинарных отношений есть попросту теория графов. Бинарным отношением, определенным на паре множеств X и Y, называется любое подмножество прямого произведения множеств X x Y.
Если x связан с y отношением R, то это обозначают как xRy или (x, y) R.
Бинарное отношение может задаваться своим множеством R=<(x,y)| xRy>.
Поскольку бинарные отношения являются множествами, то имеет смысл говорить о действиях над бинарными отношениями как над множествами, т.е. возможно найти объединение пересечение и разность бинарных отношений.

- бинарное отношение заданное с помощью характеристического свойства;
Пусть X = , Y = . Тогда множество R= <(a, 1), (b, 2), (c, 3), (d, 4)>является бинарным отношением, заданным на паре X×Y.

Область определения бинарного отношения R – это множество
X = .
Область значений бинарного отношения R – это множество Y = .
Хорошо известными примерами отношений из школьного курса математики являются:

Рассмотрим еще два графических представления бинарных отношений. В качестве носителя отношения для иллюстрирующих примеров будем использовать множество X = .
Вначале рассмотрим метод, восходящий к аналитической геометрии. Начертим пару взаимно перпендикулярных осей (OX – горизонтальная ось, а OY – вертикальная ось) и на каждой отметим точки, представляющие элементы множества X

Считая метки a, b, c, d, e координата ми точек на горизонтальной и вертикальной осях, отметим на плоскости точки с координатами (x, y). На рисунке 2 изображено множество точек, соответствующее отношению R= <(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)>.

Другой широко распространенный способ представления отношений основан на использовании ориентированных графов. При таком представлении элементы множества X изображаются вершинами графа (точками плоскости), а элементы (x, y) отношения R ребрами (стрелками), соединяющими первую компоненту xотношения со второй компонентой y. Граф бинарного отношения R изображен на рисунке.

Свойства бинарного отношения

Пусть задано бинарное отношение R на паре множеств X, Y. Бинарное отношение может обладать следующими свойствами, каждое из которых определяется своей аксиомой.

( x X) xRx или ( x X) (x, x) R
Граф рефлексивного бинарного отношения содержит петли около каждой вершины.

( x X) xRx или ( x X) (x, x) R
Граф антирефлексивного бинарного отношения не содержит ни одной петли.

( x, y X) xRy yRx или ( x, y X) (x, y) R (y, x) R
Граф симметричного бинарного отношения содержит только неориентированные ребра или петли. График симметричного отношения симметричен относительно биссектрисы I-III координатных углов.

( x, y X) xRy /\ yRx x=y или ( x, yмX) (x, y) R /\ (y, x) R x=y

( x, y, z X) xRy /\ yRz xRz или ( x, y, z X) (x, y) R /\ (y, z) R (x, z) R

(vx, y X) x≠y xRy \/ yRx или (vx, y X) x≠y v (x, y) R \/ (y, x) R
Примеры:

Бинарное отношение задано своим множеством, определите его свойства, постройте граф и график на множестве .

Проверим все свойства отношения

( x А) (x, x) R – это ложное высказывание
Можно привести контр пример, х=3, пара (3,3) не принадлежит множеству R. Бинарное отношение не является рефлексивным.

( x А) (x, x) R – это ложное высказывание
Можно привести контр пример, х=1, пара (1,1) принадлежит множеству R. Бинарное отношение не является антирефлексивным.

( x, y А) (x, y) R (y, x) R – это ложное высказывание
Можно привести контр пример, х=1, y=2 пара (1,2) принадлежит множеству R, а пара (2, 1) не принадлежит множеству R. Бинарное отношение не является симметричным.

( x, y А) (x, y) R /\ (y, x) R x=y – это истинное высказывание
Контр пример подобрать невозможно. Бинарное отношение является антисимметричным.

( x, y, z А) (x, y) R /\ (y, z) R (x, z) R – это ложное высказывание
Можно привести контр пример, х=1, y=2, z=3 пара (1,2) принадлежит множеству R и пара (2,3) принадлежит множеству R, а пара (1, 3) не принадлежит множеству R. Бинарное отношение не является транзитивным.

( x, y A) x≠y (x, y) R \/ (y, x) R – это ложное высказывание
Можно привести контр пример, х=3, y=4, 3≠4 пара (3,4) не принадлежит множеству R и пара (4,3) не принадлежит множеству R. Бинарное отношение не является связанным.

Вывод: заданное бинарное отношение обладает только одним свойством антисимметричности.

Построим граф и график

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

Зададим бинарное отношение R своим множеством, перечислим все возможные пары (х,у), элементы которых удовлетворяют равенству .

Проверим все свойства отношения

( x А) x-2х=1 – это ложное высказывание
Можно привести контр пример, х=3, пара (3,3) не принадлежит множеству R. Бинарное отношение не является рефлексивным.

( x А) x-2х≠1 – это ложное высказывание
Можно привести контр пример, х=-1, пара (-1,-1) принадлежит множеству R. Бинарное отношение не является антирефлексивным.

( x, y А) x-2у=1 у-2х=1 – это ложное высказывание
Можно привести контр пример, х=1, y=0 пара (1,0) принадлежит множеству R, а пара (0, 1) не принадлежит множеству R. Бинарное отношение не является симметричным.

( x, y А) x-2у=1 /\ у-2х=1 x=y – это истинное высказывание
Контр пример подобрать невозможно. Бинарное отношение является антисимметричным.

( x, y, z А) x-2у=1 /\ у-2z=1 x-2z=1 – это ложное высказывание
Можно привести контр пример, х=3, y=1, z=0 пара (3,1) принадлежит множеству R и пара (1,0) принадлежит множеству R, а пара (3, 0) не принадлежит множеству R. Бинарное отношение не является транзитивным.

( x, y A) x≠y v (x, y) R \/ (y, x) R – это ложное высказывание
Можно привести контр пример, х=3, y=4, 3≠4 пара (3,4) не принадлежит множеству R и пара (4,3) не принадлежит множеству R. Бинарное отношение не является связанным.

Вывод: заданное бинарное отношение обладает только одним свойством антисимметричности.

Построим граф и график

Бинарное отношение определенно на множестве действительных чисел R, выясните, какими свойствами оно обладает и какими не обладает. Постройте график.

Проверим все свойства отношения

( x R) – очевидно, это истинное высказывание
Бинарное отношение является рефлексивным, свойство антирефлексивности проверять не имеет смысла.

( x, y R) – очевидно, это истинное высказывание
Бинарное отношение является симметричным, но свойство антисимметричности будем проверять.

( x, y А) /\ " x=y – это ложное высказывание
Можно привести контр пример, х=1, y=-1. Бинарное отношение не является антисимметричным.

( x, y, z R) /\ " – это истинное высказывание
Бинарное отношение является транзитивным.

( x, y R) x≠y \/ – это ложное высказывание
Можно привести контр пример, х=3, y=4, 3≠4 пара (3,4) не принадлежит множеству R и пара (4,3) не принадлежит множеству R. Бинарное отношение не является связанным.

Вывод: заданное бинарное отношение обладает свойствами рефлексивности, симметричности и транзитивности, такое отношение называется отношением эквиваленции.

Инверсия и композиция бинарных отношений

Инверсией бинарного отношения R, заданного на паре множеств Х,Y, называется бинарное отношение R-1=<(y,x)| (x,y) R>.
Иногда инверсию называют обратным отношением.

МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ

ЛУГАНСКОЙ НАРОДНОЙ РЕСПУБЛИКИ

Луганский Национальный Университет
имени Тараса Шевченко

Курсовая работа на тему:

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

Студентка 2 курса

Доцент Давыскиба О.В.

РАЗДЕЛ 1. ПОНЯТИЕ И СВОЙСТВА БИНАРНЫХ ОТНОШЕНИЙ…………….…………4

1.2 Свойства бинарных отношений ………………………………………………….………………4

1.3. Основные операции над бинарными отношениями ……………………………………….…6

1.4 Теоремы об известных алгебрах отношений………………………………………………..….8

РАЗДЕЛ 2. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ОПЕРАЦИЙ НАД МНОЖЕСТВАМИ …………………………………………………………………………..……13

2.1 Понятие декартова произведения множеств…………………………………………….……13

2.2 Примеры декартова произведение множеств………………………………………………. 15

2.3 Представление бинарных отношений графами и матрицами……………………………….15

Список использованной литературы……………………………………………………………21

Понятие множества является одним из основных понятий математики и поэтому не определяется через другие.

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

Бинарные отношения служат простым и удобным аппаратом для весьма широкого круга задач. Язык бинарных отношений используется во многих прикладных (для математики) областях, например, таких как математическая лингвистика, математическая биология, математическая теория баз данных. Широкое использование языка бинарных отношений легко объясняется – геометрический аспект теории бинарных отношений есть попросту теория графов.

РАЗДЕЛ 1. ПОНЯТИЕ И СВОЙСТВА БИНАРНЫХ ОТНОШЕНИЙ

1.1 Понятие бинарных отношений

Бинарные операции важны в алгебре и, к тому же эта тема достаточно исследована. Сложение и умножение чисел, сложение и умножение матриц, сложение векторов в векторном линейном пространстве могут служить примерами таких операций.

Если является подмножеством можно сказать, что эти два множества находятся в некотором отношении друг с другом.

Определение бинарного отношения:

Для любых двух множеств и всякое подмножество называется бинарным отношением между и . [6, стр 47]

1.2. Свойства бинарных отношений

Свойства бинарных отношений на множестве :

Асимметричность: . Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.

Рефлексивное транзитивное отношение называется отношением квазипорядка

Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности

Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка

Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка

Полное антисимметричное (для любых выполняется или ) транзитивное отношение называется отношением линейного порядка

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

Бинарное отношение задано на множестве , определить его свойства.

Проверим все свойства отношения:

Рефлексивность
– это ложное высказывание.
Можно привести контрпример: , пара не принадлежит множеству . Бинарное отношение не является рефлексивным.

Антирефлексивность
– это ложное высказывание.
Можно привести контрпример: , пара принадлежит множеству . Бинарное отношение не является антирефлексивным.

Корефлексивность
– это ложное высказывание.
Можно привести контрпример: , пара принадлежит множеству , но . Бинарное отношение не является антирефлексивным.

Симметричность
– это ложное высказывание.
Можно привести контрпример, пара принадлежит множеству , а пара не принадлежит множеству . Бинарное отношение не является симметричным.

Антисимметричность
– это истинное высказывание
Контрпример подобрать невозможно. Бинарное отношение является антисимметричным.

Асимметричность
Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения и отношение не является антирефлексивным, отношение не является асимметричным.

Транзитивность
– это ложное высказывание.
Можно привести контр пример, пара принадлежит множеству R и пара принадлежит множеству , а пара не принадлежит множеству . Бинарное отношение не является транзитивным.

Связность
– это ложное высказывание.
Можно привести контрпример, , пара не принадлежит множеству и пара не принадлежит множеству . Бинарное отношение не является связанным.

Вывод: заданное бинарное отношение обладает только одним свойством антисимметричности.

1.3 Основные операции над бинарными отношениями

Объединением множеств A и B называется множество элементов, принадлежащих по крайней мере одному из данных множеств (т. е. либо A, либо B, либо одновременно и A и B). Обозначают и читают "объединение A и B". .

Пример: Пусть даны два множества и тогда их объединением называется множество содержащее в себе все элементы исходных множеств :

Пересечением множеств A и B называется множество элементов, принадлежащих одновременно и A и B. Обозначают и читают "пересечение A и B"

Пример: Пусть даны два множества и , тогда их пересечением называется множество , которому принадлежат те и только те элементы, которые одновременно принадлежат двум множествам:

Разностью множеств A и B называется множество элементов, принадлежащих A и не принадлежащих B. Обозначают A\B и читают "разность A и B".

Пример: Пусть даны два множества и , тогда их разностью называется множество , содержащее в себе элементы , но не : [ 2, стр 7-10]

Свойства основных операций над бинарными отношениями

Пусть — произвольные множества, тогда:

1. Операция объединение множеств коммутативна:

2. Операция объединение множеств ассоциативна:

3. Операция пересечение множеств коммутативна:

4. Операция пересечения множеств ассоциативна:

11. Симметрическая разность коммутативна:

12. Симметрическая разность ассоциативна:

1.4 Теоремы об известных алгебрах отношений

Теорема 1.3. Пусть A,B,C – подмножества унивеpсума U .Тогда спpаведливы следующие равенства:

1 a) A ∪B = B ∪A; b) A ∩B = B ∩A;

2 a) A ∪ (B ∪ C) = (A ∪B) ∪ C;

b) A ∩ (B ∩ C) = (A ∩B) ∩ C;

3 a) A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C);

b) A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C);

4 a) A ∪∅ = A; b) A ∩ U = A;

Д о к а з а т е л ь с т в о . Доказательство этих равенств опирается на определения операций над множествами, свойства логических операций и на доказательство

двустороннего включения множеств:

A = B ⇐⇒ A ⊆ B ∧B ⊆ A.

Докажем некоторые из этих равенств.

3.a) → ∀x x ∈ A ∪ (B ∩ C) =⇒ определение ∪

x ∈ A ∨ x ∈ (B ∩ C) =⇒ определение ∩

x ∈ A ∨ (x ∈ B ∧ x ∈ C) =⇒ дистрибутивность ∨

(x ∈ A ∨ x ∈ B) ∧ (x ∈ A ∨ x ∈ C) =⇒ определение ∪

(x ∈ A ∪B) ∧ (x ∈ A ∪ C) =⇒ определение ∩

x ∈ (A ∪B) ∩ (A ∪ C) =⇒ A ∪ (B ∩ C) ⊆ (A ∪B) ∩ (A ∪ C)

(из того, что x ∈ A∪ (B ∩C) следует, что x ∈ (A∪B)∩ (A∪C);

значит A ∪ (B ∩ C) ⊆ (A ∪B) ∩ (A ∪ C)).

← ∀x x ∈ (A ∪B) ∩ (A ∪ C) =⇒ определение ∩

x ∈ (A ∪B) ∧ x ∈ (A ∪ C) =⇒ определение ∪

(x ∈ A ∨ x ∈ B) ∧ (x ∈ A ∨ x ∈ C) =⇒ дистрибутивность ∨

x ∈ A ∨ (x ∈ B ∧ x ∈ C) =⇒ определение ∩

x ∈ A ∨ x ∈ (B ∩ C) =⇒ определение ∪

x ∈ A ∪ (B ∩ C) =⇒ (A ∪B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C)

(из того, что x ∈ (A∪B)∩ (A∪C) следует, что x ∈ A∪ (B ∩C);

значит (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C) ). Оба включения и доказывают равенство.

Равенства 4a) и 4b) также доказываются с использованием свойств логических операций. Здесь F – произвольная логическая формула.

4 a) → x ∈ A ∪∅ =⇒ определение ∪

x ∈ A ∨ x ∈ ∅ =⇒ x ∈ ∅ = 0, F ∨ 0 = F

← x ∈ A =⇒ x ∈ ∅ = 0, F ∨ 0 = F

x ∈ A ∨ x ∈ ∅ =⇒ определение ∪

x ∈ A ∪ ∅ =⇒ A ⊆ A ∪ ∅. Оба включения доказывают равенство.

4b) → x ∈ A ∩ U =⇒ определение ∩

x ∈ A ∧ x ∈ U =⇒ x ∈ U = 1, F ∧ 1 = F

← x ∈ A =⇒ x ∈ U = 1, F ∧ 1 = F

x ∈ A ∧ x ∈ U =⇒ определение ∩

x ∈ A ∩ U =⇒ A ⊆ A ∩ U .

Оба включения доказывают равенство множеств. Другие равенства доказываются по таким же схемам.

Пеpейдем тепеpь к булевой алгебpе. В качестве пpимитивов этой теоpии pассматpивают:

• множество B = и его элементы – носитель алгебры;

• бинаpные опеpации + (операция сложения) и · (операция умножения; знак · будем, как правило, опускать), относительно котоpых множество B замкнуто, то есть pезультатом этих опеpаций является всегда некотоpый элемент из множества В.

• унаpная опеpация − (по аналогии с операцией дополнения множеств назовем эту операцию дополнением), относительно котоpой множество B замкнуто;

• особые элементы 0 и 1, пpинадлежащие B. Особенность этих элементов заключается в том, что в то вpемя как символы a, b, c могут обозначать любые элементы из B, символы 0 и 1 обозначают только сами себя.

Порядок выполнения операций регламентируется приоритетами операций (в убывающем порядке): −, ·,+. Порядок можно изменить с помощью скобок.

Аксиомы булевой алгебpы имеют следующий вид:

1.a) a+ b = b+ a; b) ab = ba;

2.a) a+ (b+ c) = (a+ b) + c; b) a(bc) = (ab)c

3.a) a+ (bc) = (a+ b)(a+ c); b) a(b+ c) = (ab) + (ac);

4.a) a+0= a; b) a1 = a;

Теорема 1.4 (Пpинцип двойственности). Если T – теоpема в булевой алгебpе, то двойственное ей высказывание также является теоpемой.

Теорема 1.5 В булевой алгебpе B для всех ∀a, b, c ∈ B

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

a+ a = (a+ a)1 (аксиома 4b)

= (a+ a)(a+ ) (аксиома 5a)

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

a + 1 = a+ (a+ ) (аксиома 5a)

= (a+ a) + (аксиома 2a)

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

a+ (ab) = (a1) + (ab) (аксиома 4b)

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

aa = (aa) + 0(аксиома 4a)

= (aa) + () (аксиома 5b)

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

a 0 = a() (аксиома 5b)

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

a(a+ b) = (a+ 0)(a+ b) (аксиома 4a)

= a+ (0b) (аксиома 3a)

= a+ (b0) (аксиома 1b)

= a+ 0 (теоpема 1.5.5)

Теорема 1.6 В булевой алгебpе для каждого a ∈ B если a+ b =1 и ab =0, то b = a.

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

b = b + 0 (аксиома 4a)

= (b+ a)(b+ ) (аксиома 3a)

= (a+ b)( + b) (аксиома 1a)

=1 ( + b) (условие теоpемы)

= (a+ )( + b) (аксиома 5a)

= ( + a)( + b) (аксиома 1a)

= +0 (условие теоpемы)

Теорема 1.7 В булевой алгебpе для всех a () = a.

Д о к а з а т е л ь с т в о . В соответствии с аксиомами 5a и 5b

В соответствии с теоpемой 1.6 имеем a = ().

Теорема 1.8 В булевой алгебpе = 1, = 0.

Д о к а з а т е л ь с т в о . По теоpеме 1.5 имеем 0 + 1 = 1.

По аксиоме 4б имеем 0·1 = 0 В соответствии с теоpемой 1.6 имеем 1 = .

РАЗДЕЛ 2. ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ

2.1 Понятие декартова произведение множеств

Декартовым произведением множеств А и В называется множество всех пар, первая компонента которых принадлежит множеству А, а вторая компонента принадлежит множеству В.

Декартово произведение множеств А и В обозначают А. Используя это обозначение, определение произведения можно записать так:

х; у)  х  и у  .

Так как декартовы произведения А и ВА состоят из различных элементов, то операция нахождения декартова произведения множеств свойством коммутативности не обладает.

Аналогично рассуждая, можно доказать, что для этой операции не выполняется и свойство ассоциативности.

Но она дистрибутивна относительно объединения и вычитания множеств, т.е. для любых множеств А, В и С выполняются равенства:

  С    С    С,  \   С    С \   С.

Наглядно представление декартово произведение множеств.

1. Если множества А и В конечны и содержат небольшое число элементов, то можно изобразить декартово произведение этих множеств при помощи таблицы или графа.

Пример Декартово произведение множеств А = 1; 2; 3 и В = 3; 5 можно представить так, как показано на рисунках 1 и 2

Читайте также: