Бинарные отношения Бинарным отношением между элементами множеств А и В называется любое подмножество R A B. Если множества A и B совпадают А=В, то R называют.

Презентация:



Advertisements
Похожие презентации
1 Конечные и бесконечные множества Конечное множество- множество, состоящее из конечного числа элементов. Бесконечное множество – непустое множество, не.
Advertisements

1 Свойства отношений R 1 содержится в R 2 (R 1 R 2 ), если любая пара (x, y), которая принадлежит отношению R 1 также принадлежит и отношению R 2 Рефлексивность.
Метод Квайна-МакКласки. Выпишем наборы, на которых функция принимает единичное значение.
Негатранзитивность отношений Транзитивное замыкание Транзитивным замыканием отношения R называется бинарное отношение такое, что x R y тогда и только тогда,
Бинарные отношения. Транзитивное замыкание Для произвольного отношения A можно найти минимальное транзитивное отношение a такое, что ab. Минимальность.
1 Понятие множества Понятие множества является одним из наиболее общих и наиболее важных математических понятий. Множества обозначают прописными латинскими.
БИНАРНЫЕ ОТНОШЕНИЯ Преподаватель О.В. Козлова ГАПОУ КК«НКСЭ»
1 Кубенский А.А. Дискретная математика Глава 1. Множества и отношения Отношения Декартово произведение множеств: A B = { (a, b) | a A, b B } B A.
2. Соответствия Соответствие между множествами А и В определяется заданным правилом, согласно которому элементам одного множества сопоставляются элементы.
Лекция 5. Отношения на множестве © Гусева И.Н., кафедра СМиРЯ, КГУ, 2010.
1 1. Множества Понятие множества. Логические символы Под множеством понимают совокупность определенных и отличных друг от друга объектов, объединенных.
ФУНКЦИОНАЛЬНЫЙ АНАЛИЗ Составила: М.П. Филиппова доцент кафедры высшей математики ИМИ СВФУ.
Функции и отображения Отображения. N-местные функции. Понятие образов и прообразов элементов. Свойства функций: инъекция, сюръекция и биекция. Обратные.
Лекция 1 Основные понятия ст.преп Касекеева А.Б..
1. Основные понятия теории графов 1. Основные понятия теории графов 2. Степень вершины Введение 5. Ориентированные графы 6. Изоморфизм графов 7. Плоские.
Элементы общей алгебры Подгруппа, кольцо, поле, тело, решетка.
Элементы теории множеств. Понятие множества Множество - это совокупность определенных различаемых объектов, причем таких, что для каждого можно установить,
Логика предикатовЛогика предикатовЛогика предикатов расчленяет элементарное высказывание на субъект (буквально - подлежащее, хотя оно и может играть роль.
ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ. Множества Для любых объектов м множество этих объектов обозначается через. Следует отметить, что объект а и множество {а} -
Элементы общей алгебры Группа, кольцо, поле, тело, решетка.
Транксрипт:

Бинарные отношения Бинарным отношением между элементами множеств А и В называется любое подмножество R A B. Если множества A и B совпадают А=В, то R называют бинарным отношением на множестве А. (однородное отношение) Если (x, y) R, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R. n-местным (n-арным) отношением, заданным на множествах M 1, M 2,…, M n, называется подмножество прямого произведения этих множеств. Иногда понятие отношения определяется только для частного случая M=M 1 =M 2 =…=M n.

Примеры Отношение a= {(4, 4), (3, 3), (2, 2), (4, 2)} на множестве X = {4, 3, 2} можно определить как свойство "Делится" на этом подмножестве целых чисел. Из школьного курса На множестве целых чисел Z отношения "делится", "делит", "равно", "больше", "меньше", "взаимно просты"; на множестве прямых пространства отношения "параллельны", "взаимно перпендикулярны", "скрещиваются", "пересекаются", "совпадают"; на множестве окружностей плоскости "пересекаются", "касаются", "концентричны".

Пример Пусть A=B=R, пара (x, y) является точкой вещественной плоскости. Тогда бинарное отношение R 1 = { (x, y) | x 2 + y 2 1 } определяет замкнутый круг единичного радиуса с центром в точке (0,0) на плоскости, отношение R 2 = { (x, y) | x y } полуплоскость, а отношение R 3 = { (x, y) | |x-y| 1 } полосу.

Способы задания Перечисление всех пар из базового множества А и базового множества В A={a 1,a 2 } B={b 1,b 2,b 3 }, ={(a 1, b 1 ), (a 1,b 3 ), (a 2, b 1 )} Отношения могут задаваться формулами: формулы y = x 2 +5x - 6 или x + y < 5 задают бинарные отношения на множестве действительных чисел; формула x + y = любовь, задает бинарное отношение на множестве людей.

Графический метод задания a= {(a, d), (a, c), (b, b), (c, a), (e,d), (e, a)}

Графовое представление Граф - фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть x i, а наличие дуги, соединяющей вершины x i и x j, означает, что (x i,x j ) R. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка. А={(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}

Матричная форма задания Пусть на некотором конечном множестве X задано отношение А. Упорядочим каким-либо образом элементы множества X = {x 1, x 2,..., x n } и определим матрицу отношения A = [a ij ] следующим образом:

Определения Диагональ множества A A, т.е. множество ={(x,x) | x A}, называется единичным бинарным отношением или отношением равенства в A. Областью определения бинарного отношения R называется множество R={ x A | y B, (x, y) R }. Областью значений бинарного отношения R называется множество R={ y B | x A, (x, y) R }. Образом множества X относительно отношения R называется множество R(X) = { y B | x X, (x, y) R }; прообразом X относительно R называется R -1(X).

Операции над бинарными отношениями Пересечение двух бинарных отношений R 1 и R 2 - это отношение R 1 R 2 = { (x, y) | (x, y) R 1 и (x, y) R 2 }. = > Объединение двух бинарных отношений R 1 и R 2 - это отношение R 1 R 2 = { (x, y) | (x, y) R 1 или (x, y) R 2 }. Разностью отношений R 1 и R 2 называется такое отношение, что: R 1 \R 2 = { (x, y) | (x, y) R 1 и (x, y) R 2 } Дополнение к отношению R={ (x, y) | (x, y) (A A)\R}.

Обратное отношение R –1 = { (x, y) | (y, x) R}.

Композиция отношений Двойственное отношение R d = Композиция (суперпозиция) отношений R=R 1 oR 2 содержит пару (x, y) тогда и только тогда, когда существует такое z A, что (x, z) R 1 и (z, y) R 2.

Свойства отношений R 1 содержится в R 2 (R 1 R 2 ), если любая пара (x, y), которая принадлежит отношению R 1 также принадлежит и отношению R 2 Рефлексивность xM (xRx) Антирефлексивность xM ¬(xRx)

Рефлексивность отношений Обозначим через Ix отношение на множестве X, состоящее из пар вида (a, a), где a X: Ix = {(a, a)| a X}. Отношение Ix обычно называют диагональю множества X или отношением тождества на X. Очевидно, что отношение R на множестве X рефлексивно, если диагональ Ix является подмножеством множества a: Ix R. Отношение антирефлексивно, если диагональ Ix и отношение R не имеют ни одного общего элемента: Ix R = Ø.

Свойства отношений Симметричность xRy yRx или R=R -1

Свойства отношений Антисимметричность Пусть А - множество людей в данной очереди. Отношение R "не стоять за кем-то в очереди" будет антисимметричным. Пусть х=ВАСЯ, а y=ИВАНОВ. Тот факт, что (x, y) R означает, что "ВАСЯ не стоит в очереди за ИВАНОВЫМ", (y, x) R - "ИВАНОВ не стоит за ВАСЕЙ". Очевидно, что одновременное выполнение обоих включений может быть, только если ВАСЯ и есть ИВАНОВ, т.е. x = y. Отношение " " также антисимметрично: если x y и y x, то x=y. Асимметричность Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.

Свойства отношений Для любого отношения R вводятся понятия симметричной части отношения R s = R R -1 и асимметричной части отношения R a = R \ R s. Если отношение R симметрично, то R= R s, если отношение R асимметрично, то R= R a. Примеры. Если R - " ", то R -1 - " ". Транзитивность отношений

Нетранзитивное отношение Отношение R, определенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz. Пример нетранзитивного отношения: «x отец y» Нетранзитивным является отношение " ". Пусть x=2, y=3, z=2, тогда справедливо x y и y z, но x=z, т.е. (x, z) R.

Негатранзитивность отношений (x,y) R и (y, z) R (x, z) R В графе негатранзитивного отношения отсутствие дуг от х к у и от у к z приводит к отсутствию дуги от х к z. Отношения R 1 - ">" и R 2 - " " негатранзитивны, так как отношения R 1 доп - " ", R 2 доп - "=" транзитивны. Возможно одновременное выполнение свойств транзитивности и негатранзитивности. Например, отношение R 1 одновременно транзитивно и негатранзитивно, а R 2, как известно, транзитивным не является.

Свойства бинарных отношений Полнота (x, y) X либо xRy либо yRx, либо и то и другое одновременно – полносвязное или связное отношение Ацикличность Отношение R называется ацикличным, если из наличия какого-либо пути между вершинами соответствующего графа следует отсутствие обратной дуги (обратного пути) между этими вершинами (в графе отсутствуют любые циклы ). n x 1 Rx 2 x 2 Rx 3 x 3 Rx 4 … x n-1 Rx n но не наоборот.

Композиция транзитивного отношения Справедлива теорема: Для любого отношения транзитивное замыкание равно пересечению всех транзитивных отношений, включающих в качестве подмножества. Композиция транзитивного отношения – транзитивное отношение. Отношение R1 называется транзитивным относительно отношения R2, если: из (x, y) R1 и (y, x) R2 следует, что (x, z) R1; из (x, y) R2 и (y, x) R1 следует, что (x, z) R1.

Связи между бинарными отношениями Отношение R симметрично тогда и только тогда, когда R = R -1. Если R рефлексивно, то R d антирефлексивно, если R антирефлексивно, то R d рефлексивно. Отношение R слабо полно тогда и только тогда, когда R d антисимметрично. Отношение R асимметрично тогда и только тогда, когда R d полно.

Отношения эквивалентности (подобия, равносильности) Отношение R на множестве A 2 называется отношением эквивалентности, если оно обладает следующими свойствами: рефлексивность симметричность транзитивность Обозначается =,, ~,

Отношение эквивалентности х x для всех x A (рефлексивность) Если x y, то y x (симметричность) Если x y и y z, то x z (транзитивность)

Примеры отношение тождества I X = {(a, a)|a X} на непустом множестве X; отношение параллельности на множестве прямых плоскости; отношение подобия на множестве фигур плоскости; отношение равносильности на множестве уравнений; отношение "иметь одинаковые остатки при делении на фиксированное натуральное число m" на множестве целых чисел. Это отношение в математике называют отношением сравнимости по модулю m и обозначают ab (mod m); отношение "принадлежать одному виду" на множестве животных; отношение "быть родственниками" на множестве людей; отношение "быть одного роста" на множестве людей; отношение "жить в одном доме" на множестве людей.

Классы экввалентности Система непустых подмножеств {M 1, M 2, …} множества M называется разбиением этого множества, если M = M 1 M 2 … и при ij M i M j =Ø. Сами множества M 1, M 2, … называются при этом классами данного разбиения.

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

Пример 1

Пример 2 а и b равны по модулю n, если их остатки при делении на n равны. Например по модулю 5 равны 2, 7, 12 … [0] = {0, n, 2n, …} [1] = {1, n+1, 2n+1, …} … [n-1] = {n-1, n+n-1, 2n+n-1, …}

Класс эквивалентности Классом эквивалентности C(a) элемента a называется подмножество элементов, эквивалентных a. Из вышеприведённого определения немедленно следует, что, если и bC(a), то C(a) = C(b).

Теорема Отношение эквивалентности, заданное между элементами базового множества Х, определяет разбиение множества Х на непересекающиеся классы эквивалентности базового множества

Фактор-множество Получающееся при этом множество классов называется фактор- множеством {c k }.или X / ˜.

Теорема Два класса эквивалентности либо совпадают, либо не пересекаются. Доказательство. Пусть A и B - два класса эквивалентности из X. Допустим, что они пересекаются и c - общий элемент, то есть c A, c B. Если x - произвольный элемент из A, то x ~ c. Поскольку c B, то и x B. Таким образом, A B. Аналогично доказывается, что B A. Итак, A = B. Теорема доказана

Представитель класса Как уже отмечалось, каждый элемент а из множества X полностью определяет класс эквивалентности, его содержащий, который далее обозначается символом ã, так что а ã (и ã =, если и только если а = y). Элемент а называется представителем класса A, если а A.