Бинарные отношения — MT1102: Линейная алгебра (введение в математику) — Бизнес-информатика. Бинарные отношения. Примеры бинарных отношений

MT1102: Линейная алгебра (введение в математику)

Рассмотрим отношение «уважать», определенное на множестве всех людей %%M%%. Для полной информации о том, кто кого уважает, составим следующее множество %%R%%. Переберем все пары %%(a, b)%%, где %%a, b%% пробегают множество всех людей. Если %%a%% уважает %%b%%, то пару %%(a,b)%% отнесем к множеству %%R%%, иначе — нет.

Этот список полностью отражает отношение «уважать». Если нужно узнать, уважает ли человек %%a%% человека %%b%%, то просмотрим множество %%R%%. Если пара %%(a, b) in R%%, то заключаем, что %%a%% уважает %%b%%. В случае %%(a,b) notin R%% — %%a%% не уважает %%b%%.

Определение

Бинарным отношением, определенным на множестве %%M%%, называется произвольное подмножество %%R%% из декартового произведения %%M^2%%.

Рассмотрим отношение больше на множестве %%M = <1, 2>%%. Тогда

$$ M^2 = big <(1, 1), (1,2), (2,1), (2,2)big>$$ Из него выбирем все пары %%(a,b)%%, где %%a > b%%. Получим $$ R = big <(2,1)big>$$

Виды бинарных отношений

Рефлексивное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется рефлексивным, если для любого элемента %%a%% из %%M%%, выполняется условие %%a

a%%. $$ begin forall ain M

a text< или>\ forall ain M

1. Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше рефлексивным? Если да, то каждое число является больше самого себя, что неверно. Поэтому отношение больше не рефлексивно.
2. Рассмотрим отношение равно на множестве действительных чисел. Оно является рефлексивным, так как каждое действительное число равно самому себе.

Симметричное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется симметричным, если для любых двух элементов %%a, b%% из %%M%%, из условия %%a

b%% следует условие %%b

a text< или>\ forall a,bin M

(a,b) in R rightarrow (b,a) in R. end $$

1. Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше симметричным? Оно не является симметричным, так как если %%a > b%%, то условие %%b > a%% не выполняется. Поэтому отношение больше не симметрично.
2. Пусть %%R%% — отношение, определенное на множестве %%M = %%. При этом %%R = big< (a,b), (b,c), (a,a), (b,a), (c,b)big>%%. Для этого отношения имеем %%forall x,y in M

(x,y) in R rightarrow (y,x) in R%%. По определению %%R%% симметрично.

Транзитивное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется транзитивным, если для любых элементов %%a, b, c%% из %%M%%, из условий %%a

c%% следует условие %%a

c text< или>\ forall a,b,cin M

(a,b) in R land (b,c) in R rightarrow (a,c) in R. end $$

Рассмотрим отношение больше на множестве дейтсвительных чисел. Оно является транзитивным, так как для любых элементов выполняется условние %%forall a,b,cin M

a > b land b > c rightarrow a > c%%. Так, например, подставив вместо %%a, b%% и %%c%% числа %%2, 1%% и %%0%% соответственно, получим: если %%2 > 1%% и %%1 > 0%%, то %%2 > 0%% — верное утверждение (вспомните импликацию, из истины следует истина).

Антисимметричное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется антисимметричным, если для любых элементов %%a, b%% из %%M%%, из условий %%a

a%% следует условие %%a = b%%.

a rightarrow a = b text< или>\ forall a,bin M

(a,b) in R land (b,a) in R rightarrow a = b. end $$

Отношение больше или равно на множестве действительных чисел антисимметрично. Действительно, если %%a geq b%% и %%b geq a%%, %%a = b%%.

Эквивалентное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

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

Отношение частичного порядка

Бинарное отношение %%R%% на множестве %%M%% называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно.

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

Построение отрицаний

Пусть %%R%% — бинарное отношение на множестве %%M%%, и %%P%% — одно из следующих условий:

• отношение %%R%% рефлексивно,
• отношение %%R%% симметрично,
• отношение %%R%% транзитивно,
• отношение %%R%% антисимметрично.

Построим для каждого из них отрицание выполнения условия %%P%%.

Отрицание рефлексивности

По определению %%R%% рефлексивно, если каждый элемент множества %%M%% находится в отношении %%R%% к самому себе, то есть %%forall a in M

a%%. Тогда рассмотрим отрицание рефлексивности как истинное высказывание %%overline

a>%%. Используем равносильность %%overline equiv exists x overline %%. В нашем случае получаем %%forall a in M

a equiv exists ain M

Аналогично получаем и остальные отрицания. В итоге получаем следующие утверждения:

%%R%% не рефлексивно тогда и только тогда, когда

%%R%% не симметрично тогда и только тогда, когда

$$ exists a, b in M

%%R%% не транзитивно тогда и только тогда, когда

$$ exists a, b, c in M a

%%R%% не антисимметрично тогда и только тогда, когда

Свойства бинарных отношений. Бинарное отношение R (RÌA´A=A2), заданное на множестве А называется отношением тождества

Бинарное отношение R (RÌA´A=A 2 ), заданное на множестве А называется отношением тождества, если все его элементы (кортежи) имеет вид (а,а), где аÎА и обозначается id_A, т.е. . Пары, вида (а,а) называются диагональными, а отношение id_A называют диагональным. Вполне понятно, что матрица отношения тождества будет иметь вид единичной матрицы:

Очевидно, что для любого бинарного отношения R, определенного на множестве А, имеет место равенство: *R=R*id_A=R.

Бинарное отношение R, заданное на множестве А, называется рефлексивным, если id_AÍR, т.е. когда оно включает диагональ.

а. А – множество прямых на плоскости, на котором задано отношение R= «Прямая Х параллельная прямой Y».

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

b. А – множество студентов нашего вуза и на котором задано отношение Р= «студент S ровесник студенту V». Очевидно, что каждый ровесник сам себе, и поэтому (S,S)ÎP.

Бинарное отношение R, заданное на множестве А называется иррефлексивным, если aRa (или (а,а)Î R) не имеет смысла. Или тоже самое можно сформулировать как (а,а)Ï R.

а. На числовом множестве D задано отношение R=” 2 из аRb следует bRа (RÍR -1 ).

а. Прямая А перпендикулярна прямой В в плоскости Z.

b. Студент Х является соседом по парте студента Y.

(Заметим, что приведенные отношения не являются рефлексивными).

Ø Бинарное отношение R, заданное на множестве А называется, антисимметричным, если из и следует, что ( ).

а. Отношение включения для множества, т.е. отношение «множество А является подмножеством множества В». И если А Í В и В ÍА, то из аксиомы объемности следует, что А = В.

Ø Бинарное отношение R, заданное на множестве А называется транзитивным, если для любых a, b, c Î A из aRb и bRc следует aRc (R Í R 2 ).

а. Отношения подобия на множестве треугольников;

в. Отношение «быть ровесником», заданное на множестве студентов;

с. Отношение «быть больше (меньше)», заданное на множестве действительных чисел.

Ø Бинарное отношение R, заданное на множестве А называется отношением эквивалентности (или просто эквивалентностью), если для любых элементов a, b, c Î A выполняются следующие свойства:

– рефлексивность: aRa (id_A Í R);

– симметричность: aRb Þ bRa (R Í R -1 );

– транзитивность: aRb и bRc Þ aRc (R 2 Í R).

а. Отношение равенства “=” на любом множестве является отношением эквивалентности (рефлексивность: а=а; симметричность: a=bÞb=a; транзитивность: (a=b и b=c) Þ a=c).

b.Отношение R= <(1, 1), (1, 2), (1, 3), (2, 2), (2, 2), (2, 1), (2, 3), (3, 3), (3, 2), (3, 1)>является отношением эквивалентности, так как оно рефлексивно: “(а)<(a, a) Î R>; симметрично: (a, b) R (b, a) ÎR; транзитивно: ((a, b) и (b, c) ÎR Þ (a, c) Î R, где a, b –числа, принимающие значения 1, 2, 3. Например, транзитивность (1, 2) Î R и (2, 3) Î R влечет (1, 3) Î R. Отметим, что в этом примере R=R -1 .

с. Отношение “быть на одном курсе” на множестве студентов факультета;

d. Отношение “иметь одинаковый остаток при делении на 3” на множестве

e. Отношение параллельности на множестве прямых плоскости.

d. Отношение подобия на множестве треугольников и т.п.

Считается, что термин “отношение эквивалентности” применяется только в случае, если выполняются следующие три условия:

Ø Каждый элемент эквивалентен самому себе;

Ø Высказывание, что два элемента являются эквивалентными, не требует уточнения, какой из элементов рассматривается первым, а какой вторым;

Ø Два элемента, эквивалентные третьему, эквивалентны между собой.

Для обозначения эквивалентности иногда применяют символ ”

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

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

Лемма: «Всякое отношение эквивалентности, определенное на множестве А, задает разбиение множества на классы».

Пусть на множестве А задано отношение эквивалентности «

». Выполним следующее построение. Выберем элемент а₁ÎА и образуем класс (подмножество А) А₁, состоящий из элемента а₁ и всех элементов, эквивалентных а₁; затем выберем элемент а₂ÏА₁ и образуем класс А₂, состоящий из а₂ и всех элементов, эквивалентных а₂ и т.д. получится система классов А₁, А₂….(возможно бесконечная) такая, что любой элемент из А входит в один класс. Вполне очевидно, что полученная система классов обладает свойствами:

Ø А_i=А;

Ø

Ø .

Построенное разбиение, т.е. система классов, называется системой классов эквивалентности по отношению R.

С другой стороны, любое разбиение А на классы определяет некоторое отношение эквивалентности, а именно, отношение “входить в один и тот же класс данного разбиения”, что утверждается следующей леммой:

Лемма: «Всякое разбиение множества А на классы задает на множестве А отношение эквивалентности»

Пусть a, b Î A и aRb Û a и b лежат в одном классе разбиения. Тогда для любого а Î К aRa, т.е данное отношение рефлексивно.

Пусть К – некоторый класс разбиения, и a, b Î К. Тогда и b, a Î K, т.е. aRb Þ bRa, что доказывает симметричность отношения элементов данного класса.

Из aRb и bRc следует, что a, b, c Î K. Следовательно aRc что доказывает транзитивность отношения элементов данного класса.

Таким образом доказано, что элементы, определяющие класс разбиения, связаны отношением эквивалентности.

Пример. Разбиение множества натуральных чисел N= <1, 2, ….>по отношению “иметь общий остаток от деления на 7” состоит из 7 бесконечных (счетных) классов: первый класс – <0, 7, 14, 21,….>(остаток 0), второй класс – <1, 8, 15, 22,…>(остаток 1), третий класс – <2, 9, 16,….>(остаток 2) ……, седьмой класс – <6, 13, 20, 27,….>(остаток 6).

Пример 5. Отношение “проживание в одном доме” в множестве жителей России образует разбиение населения России.

Множество классов эквивалентности множества А образует фактормножество множества А по отношению эквивалентности и обозначается А|

Системой представителей некоторого отношения эквивалентности

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

Пример. Пусть на плоскости определена декартова система координат и координаты обозначаются через х и у. Будем говорить, что две точки М₁ и М₂ эквивалентны, если их абсциссы равны: М₁

Класс эквивалентности – прямая, параллельная оси ординат. Фактормножества образованы прямыми на плоскости, параллельными оси ординат. Система представителей может определена точками, лежащими на оси абсцисс, т.е. точками с координатами (х, 0), хÎR.

Другими примерами отношения эквивалентности могут служить равенство и подобие фигур, логические утверждения, выражаемые с помощью оборотов “иметь такое же”, “быть таким же”.

46.175.165.49 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

Курсовая работа “Алгебра бинарных отношений и отображений”

Курсовая работа “Алгебра бинарных отношений и отображений”

Просмотр содержимого документа
«Курсовая работа “Алгебра бинарных отношений и отображений”»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Математический смысл слова «множество» отличается от того, как оно используется в обычной речи, где его связывают с большим количеством предметов. В математике этого не требуется. Здесь рассматривают множество, состоящее из одного объекта, и множество, не содержащее ни одного объекта.

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

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

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

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

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

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

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

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

Рассмотрим понятие «отношение» в общем случае. Пусть – некоторое непустое множество. Декартовым квадратом множества назовем множество (или ), элементами которого являются всевозможные упорядоченные пары , где пробегают множество . Если – подмножество множества , то будем говорить, что является отношением на множестве .

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

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

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

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

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

Источники:

http://it.rfei.ru/course/~QVDa/~chapter-3/~lesson-3-binary-relation
http://studopedia.ru/12_90510_svoystva-binarnih-otnosheniy.html
http://multiurok.ru/files/kursovaia-rabota-alghiebra-binarnykh-otnoshienii-i.html