Бинарные отношения дискретная математика: Репозиторий Самарского национального исследовательского университета имени академика С.П. Королёва: Недопустимый идентификатор

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

Рассмотрим специальные свойства бинарных отношений на множестве A.

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

1. Отношение  на AA называется рефлексивным, если (a,a) принадлежит  для всех a из A.

2. Отношение  называется антирефлексивным, если из (a,b) следует ab.

3. Отношение  симметрично, если для a и b, принадлежащих A, из (a,b) следует, что (b,a).

4. Отношение  называется антисимметричным, если для a и b из A, из принадлежности (a,b) и (b,a) отношению  следует, что a=b.

5. Отношение  транзитивно, если для a, b и c из A из того, что (a,b) и (b

,c), следует, что (a,c).

Пример ..

1. Отношения «=» и «£» являются рефлексивными отношениями на множестве N, но отношение «<» таковым не является.

2. Отношение «=» является симметричным, а «<» и «£» — нет.

3. Отношение на N «являются взаимно простыми» является симметричным.

4. Отношения «<», «£» и «=» являются транзитивными, а отношение  = {(a,b): a,b ÎN и b = a+1} – нет, так как 34 и 45, но не 35.

Как по матрице представления определить свойства бинарного отношения

1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.

.

2. Антирефлексивность: на главной диагонали все нули.

3. Симметричность: если .

4. Антисииметричность:

M_ij=1, i ≠j, M_ji=0

Матрицы бинарных отношений

Рассмотрим два конечных множества A ={a₁,a₂,…,a_m} и B={b₁,b₂,…,b_n} и бинарное отношение .

Определим матрицу размераm×n бинарного отношения Р по следующему правилу:

Полученная матрица содержит полную информацию о связях между элементами.Любая матрица, состоящая из 0 и 1, является матрицей некоторого бинарного отношения.

ПРИМЕР 1. Матрица бинарного отношения,A={1,2,3}, заданного на рисунке

имеет вид

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

1. Если тои , где сложение осуществляется по правилам 0+0=0, 1+1=0+1=1+0=1, а умножение – обычным способом.

Итак,

2. Матрица получается перемножением соответствующих элементов изи:.

3. Если , то , где умножение матриц производится по обычному правилу умножения матриц, но произведение и сумма элементов – по определённым в свойстве 1 правилам.

4. Матрица обратного отношения Р^-1 равна транспонированной матрице отношения Р: .

5. Если , то.

6. Матрица тождественного отношения id_A единична:

ПРИМЕР 2. Пусть — матрицы отношений P и Q. Тогда

ПРИМЕР 3.

Если , то

Рассмотрим свойства отношений на языке матриц.

Пусть Р – бинарное отношение на множестве .

Отношение Р:

• рефлексивно, если на главной диагонали матрицы отношения расположены только единицы;

• симметрично, если матрица симметрична относительно главной диагонали;

• антисимметрично, если в матрице все элементы вне главной диагонали являются нулевыми;

• транзитивно, если выполнено соотношение .

ПРИМЕР 4. Проверим, какими свойствами обладает отношение , А={1,2,3}, изображённое на рисунке.

Составим матрицу отношения Р:

Так как в матрице на главной диагонали имеются нулевые элементы, отношение Рне рефлексивно.

Несимметричность матрицы означает, что отношение Рне симметрично.

Для проверки антисимметричности вычислим матрицу .

Поскольку в полученной матрице все элементы, стоящие вне главной диагонали, нулевые, отношение Р антисимметрично.

Так как (проверьте!), то есть Р являетсятранзитивным отношением.

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

1.1 Понятие отношение.

Из определения «множество», которое было сформулировано Н. Бурбаки, ясно, что в теории множеств, главное и основное значение имеют отношения между элементами этого множества. Поэтому многие ученые в области математики и вычислительной техники используют алгебру отношений, чтобы усилить описательные возможности теоретико-множественного языка.

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

Философское понятие «отношение»  объединяет такие понятия,  как «соответствие», «отображение», «функция».

Соответствие между множествами D и F называется подмножество, которое можно записать в таком  виде, что обозначает подмножество пар. Такие отношения называются бинарными. В математической литературе встречается и другая запись бинарных отношений, например. Элемент «d» и элемент «f» — первая и вторая  координаты упорядоченной пары.

Одним из способов задания отношений является матричный способ. Примером может служить отношение обучающихся к знаниям по конкретной дисциплине, выраженных в оценках, которые они получили в течение определенного учебного семестра. Обозначим – множество обучающихся в учебной группе в количестве K человек, – множество оценок в количестве L, полученных учащимися за семестр (различают два вида оценок – удовлетворительных и неудовлетворительных), S – множество пар, которое ставит в соответствие каждого обучающегося оценкам, полученным за семестр. В этом случае учебный журнал можно представить как матрицу отношений, ставя на пересечении строк (пусть это будет фамилии учащихся) и столбцов (пусть это будет порядковый номер контрольного занятия, где всем обучающимся выставляются оценки) «1», если обучающийся имеет удовлетворительные знания и «0», если неудовлетворительные. Именно такое задание отношений называется матричным. Часто бинарные отношения задают не в виде матрицы отношений, а некоторых правил.

Другой способ задания бинарных отношений является графический, т.е. в виде графа. Здесь точками или вершинами задаются элементы множества, например, ребрами, т.е. линиями, которые соединяют эти вершины, множество отношений M. Эти графы можно назвать неориентированными. Если ребра обозначают стрелками, то их называют дугами, то  граф будет  принимать  вид ориентированного или, орграфа. Графы обычно изображаются в виде геометрических фигур. Иллюстрируются декомпозиция сложного отношения «взаимодействие учащихся в учебной группе», обозначим его T, на типовые отношения, которые возникают в процессе учебы в учебном заведении. Будет видно, что множество вершин имеют одну природу. И тогда говорят, что построены графы отношений на множестве D. Одной из характерных особенностей графа является отсутствие каких-либо отношений, связанных с учебной деятельностью учащегося.

Граф называют «графом Понтрягина — Куратовского». Он является неориентированным и его особенностью является то, что его ребра пересекаются и поэтому он называется неплоским. Помимо неплоских графов существуют плоские, а также двудольный орграф. Подобным графом можно истолковать, например, отношения преподавателя (Р) с обучающимися (N) на лекционных занятиях. Для этого необходимо вершину обозначить другой буквой, например Z и считать одноэлементным множеством. И говорят, что построен граф отношений от Р к N. Например, биграфом можно разъяснить и другие отношения преподавателя и обучающихся, например, на экзамене. Для этого необходимо поменять одинарные стрелки на двойные, что будет обозначать отношение диалога между преподавателем и учащимися. [2]

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

От графического представления отношений в виде графов легко перейти к матричному представлению. В теории графов различают два вида матричного представления графов – матрицами смежности и инцидентности.

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

Очевидно, что в случае матрица смежности равна нулю и единице, т.е. их элементы принимают значения «0» или «1» соответственно.

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

Тогда говорят, что, если вершина является концом ребра, то они инцидентны: вершина инцидентна ребру и обратно.

Одним из важных понятий в алгебре отношений является понятие «функциональное отношение». Оно определяется как отношение, если все его элементы или упорядоченные пары имеют различные первые координаты. Иначе, каждому элементу x из X такому, что соответствует один и только один элемент y из Y.

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

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

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

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

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

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

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

На произвольном множестве среди всех бинарных отношений и в зависимости от свойств можно выделить  несколько классов самых отношений.

Бинарное отношение на некотором множестве называют:

1) эквивалентностью, если оно рефлексивно, симметрично и транзитивно;

2) толерантностью, если оно рефлексивно и симметрично;

3) порядком (или частичным порядком), если оно рефлексивно, антисимметрично и транзитивно;

4) предпорядком (или квазипорядком), если оно рефлексивно и транзитивно;

5) строгим порядком, если оно иррефлексивно, антисимметрично и транзитивно;

6) строгим предпорядком, если оно иррефлексивно и транзитивно.

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

Приведем пример.

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

б. Бинарное отношение φ на множестве всех непустых подмножеств некоторого множества Z, для которого AB тогда и только тогда, когда  A⋂B≠∅, является толерантностью. Это отношение рефлексивно и симметрично, но не транзитивно. Действительно, из того, что A⋂B≠∅ и B⋂C≠∅, никак не следует, что A⋂C≠∅. Проиллюстрируем этот пример на рисунке.

 

 

 

 

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

Обычно это отношение называют просто естественным порядком. Поскольку в дискретной математике нам приходится иметь дело со многими порядками на нечисловых множествах, мы будем говорить „естественный числовой порядок», подчеркивая, что речь идет об отношении порядка на множестве действительных чисел (или об его ограничении на множества рациональных, целых или натуральных чисел).

г. На множестве натуральных чисел  зададим бинарное отношение , означающее, что  делит  ( является делителем ). Это отношение рефлексивно, поскольку любое число является делителем самого себя. Покажем антисимметричнсть. Пусть  делит  и в то же время  делит . Тогда найдется натуральное число , такое, что , и найдется , такое, что . Отсюда , что на множестве натуральных чисел возможно только при . Следовательно, . Покажем транзитивность. Если  делит , а  делит , то найдутся натуральные числа , такие, что  и . Отсюда имеем , т.е.  — делитель . Таким образом, «отношение делимости» на множестве  является отношением порядка.[4]

Если распространить отношение, то оно потеряет свои свойства асимметричности, только предпорядком. Например, 2 делится на –2 и –2 делится на 2, однако 2≠-2.

д. Рассмотрим множество  всех подмножеств множества . Покажем, что отношение включения  на множестве  есть порядок. Это отношение рефлексивно, так как для любого множества  справедливо включение . Поскольку для любых двух множеств  и  из  и следует, что , рассматриваемое отношение антисимметрично. Из определения включения вытекает, что если  и , то . Следовательно, отношение транзитивно.

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

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

 

 

Важнейшим в современной математике является отношения толерантности, предпорядка и эквивалентности. Можно сказать, что эквивалентность есть транзитивная толерантность или симметричный предпорядок. Порядок же есть антисимметричный предпорядок.

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

Отношение  называют рефлексивно-транзитивным замыканием бинарного отношения φ на соответствующем множестве.

Можно также обозначить , и тогда .

Отношение   является рефлексивным, так как . Докажем его транзитивность. Пусть для каких-то  выполняется  и . Докажем, что . Будем считать, что элементы  попарно различны (так как при  или  доказывать нечего). Тогда существуют последовательности

 и ,

такие, что  для каждого  и  для каждого .

В итоге получаем последовательность

, где ,

для всякого ,  для всякого , такую, что  для любого , то есть , что и требовалось доказать.

Определение. Бинарное  отношение А—>В называется отображением, или
функцией, из множества A в множество B , если оно всюду определено и для любого хА его образ R(x) есть одноэлементное множество.[5]

Рассмотрим пример отображения.  Формула у — sinx задает функцию sin: X —» Y, определенную
на множестве всех действительных чисел X и принимающую значения из
подмножества Y действительных чисел, определенного как интервал от -1
до 1 включительно. Формула + =1 определяет окружность единичного радиуса с центром
в начале прямоугольной системы координат. Однако зависимость у от x не
является функциональной из-за неоднозначности: подавляющему большинству значений переменной x соответствует не одно, а два значения переменной y= ± . Исключением являются только х = 1 и х = — 1. Кроме
того, данная зависимость определена не на всем множестве действительных
чисел, а только на замкнутом интервале от -1 до 1.

Большое значение в алгебре отношений имеют отображения. Различают отображения C в G, где каждый элемент имеет один и только один образ из G. Примером такого отображения может служить рассмотренный выше пример.

Говорят, что имеет место отображение C на G в том случае, если любой элемент из G есть образ  хотя бы одного элемента из G. Такое отображение получило название сюръекция, или другими словами накрытием.

Если для любых двух и более различных элементов из Х их образы также различны, то отображение f называется инъекцией.

Отображение, одновременно являющееся сюръекцией и инъекцией, называется биекцией или наложением. Принято говорить, что есть взаимно-однозначное отображение, а между элементами C и G имеется взаимно-однозначное соответствие.

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

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

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

Зададим множество — преподавателей, занятых в учебном процессе в определенный учебный день недели, множество аудиторий вуза, в которых проводятся занятия. Тогда инъективное отображение согласно расписанию занятий ставит в соответствие преподавателей и аудитории, в которых они должны проводить занятия.

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

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

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

 

 

 

 

 

Здесь дана определенная классификация бинарных отношений на множестве. В основе этой классификации лежат свойства отношений.

Бинарное отношение p на множестве  называют рефлексивным, если диагональ  множества  содержится в , т.е.  для любого элемента  множества .

Если же , то бинарное отношение  на множестве  называют иррефлексивным.

Указанные свойства бинарных отношений на множестве  называют рефлексивностью и иррефлексивностью.

Бинарные отношения равенства и подобия на множестве геометрических фигур рефлексивны: каждый треугольник равен и подобен самому себе. Действительно, рефлексивны все отношения равенства: равенство чисел, равенство векторов, равенство множеств и т.п. Также рефлексивными являются, например, бинарное отношение нестрогого неравенства на множестве действительных чисел, поскольку для любого числа a всегда a≤b и отношение  включения множеств, так как для любого множества A всегда A≤A. [2]

Напротив, бинарное отношение на множестве действительных чисел, задаваемое строгим неравенством a<b, иррефлексивно, равно как и отношение  строгого включения множеств.

Не нужно путать иррефлексивное отношение с нерефлексивным, т.е. не являющимся рефлексивным, отношением. Иррефлексивное отношение нерефлексивно, но не всякое нерефлексивное отношение иррефлексивно. Иррефлексивному отношению на  не принадлежит ни один элемент диагонали , а нерефлексивное отношение может содержать некоторые (но не все!) элементы диагонали. На рисунке приведены примеры графиков иррефлексивного и нерефлексивного отношений (пунктиром указаны диагонали множеств).

 

 

                                                         

                                                                                            

                                                         

Бинарное отношение φ на множестве B называют:

1) симметричным, если для любых k,l  принадлежат А из kl следует lk

2) антисимметричным, если для любых k,l,принадлежащих B из одновременной справедливости kφl и lφk следует, что a=b.

Соответствующие свойства бинарных отношений на множестве  называют симметричностью и антисимметричностью.

График симметричного бинарного отношения на множестве  симметричен относительно диагонали. Это продемонстрировано на рисунке.

 

 

 

 

 

 

Теорема 1.1. Бинарное отношение φ на множестве B симметрично, если и только если бинарное отношение на множестве B, обратное к φ, совпадает с    φ: =φ. Проведем доказательство теоремы. Пусть
, то есть . В силу симметричности .Следовательно, . Аналогично доказывается включение 
.

Теперь пусть . Тогда  и . Из определения обратного отношения следует, что 
. А значит, φ — симметричное бинарное отношение.

Теорема 1. 2. Бинарное отношение φ на множестве B антисимметрично, если и только если .

Действительно, если ,то   и  (т.е.  ). Но из выполнения соотношений   и y ввиду антисимметричности  следует, что x=y, то есть .

Обратно, пусть  . Можно предположить, что  и , причем x≠y. Тогда  и , но 
. В данном случае получаем противоречие.

       Можно отметить, что для антисимметричного бинарного отношения на множестве  может иметь место равенство 

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

Приведем пример:

а. Пусть S — некоторое множество населенных пунктов. Можно задать на нем бинарное отношение достижимости:  если есть дорога, по которой можно доехать из D в пункт K, то из пункта D достижим пункт K.  Если из пункта D можно доехать до пункта K, а из K есть дорога до L,  следовательно, из D можно проехать в L, то отношение транзитивно,

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

в. Бинарное отношение неравенства на множестве действительных чисел не транзитивно, Следуя из того, что x≠y и y≠z, вовсе не следует, что x≠z , Аналогично, если x друг y, а y друг z, то  это  никак не означает, что x друг z.

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

Докажем следующее важное свойство транзитивного бинарного отношения.

Теорема 1.3. Бинарное отношение  на множестве  транзитивно тогда и только тогда, когда его квадрат содержится в нем, т.е. .

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

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

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

Бинарное отношение φ на множестве B называется плотным, если для любых (a,b)∊B, отличных друг от друга и таких, что aφb, найдется c, отличный и от a и от b, такой, что aφc и cφ,b.

Для любой пары элементов, связанных плотным отношением, всегда найдется такой  третий элемент, который находится между ними и связан с каждым из них тем же отношением. Значит, отношения неравенства как строгого, так и нестрогого, на множествах рациональных и действительных чисел плотны, но подобные отношения на множествах целых и натуральных чисел плотными не являются. Действительно, каковы бы ни были рациональные (или действительные) числа a и b, из того, что a<b, следует, что существует число c, отличное как от a, так и от b, такое, что a<c<b. Например, подходит число  c=(a+b)/3. Но для целых чисел k и k+1 такого «промежуточного» целого числа нет.

Если φ — плотное бинарное отношение на множестве B и для некоторых a,b∊B имеет место aφy, то найдется c∊B, такой, что  a≠c, b≠c и  aφ,c, c, cφ,b. В силу определения композиции отношений следует, что . Значит, из  следует , то есть . Итак, если φ плотно, то оно содержится в своем квадрате. Cтоит напомнить, что для транзитивного бинарного отношения . Значит, если бинарное отношение φ одновременно плотно и транзитивно, то оно будет равно квадрату этого бинарного отношения, т.е. φ=

 

 

 

 

Центр изучения дискретной математики

Отношения

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

• наборы людей, связанных отношением «отец»
• сотрудников, связанных с компаниями отношением «работодатель»
• целых чисел, связанных с другими целыми числами отношением «делится на»
• (. ..и многие другие примеры)

Более формально: пусть $A$ и $B$ — множества. Бинарное отношение от $A$ до $B$ является подмножеством $A \times B$.

Следовательно, бинарное отношение $R$ — это просто набор упорядоченных пар. Мы пишем $aRb$ для обозначения $(a,b) \in R$ и $a \cancel{R} b$ для обозначения $(a,b) \notin R$. Когда $(a,b) \in R$, мы говорим, что «$a$ связано с $b$ посредством $R$».

Такие отношения являются бинарными, поскольку $A \times B$ состоит из пар. В общем, у нас могут быть отношения, которые являются подмножествами $A \times B \times C \times \cdots$, чтобы дать нам $n$-арное отношение. Мы сосредоточимся на бинарном случае.

Например, пусть $A$ — набор студентов в Карлтоне, а $B$ — набор курсов в Карлтоне. Пусть $R$ будет отношением «зачислен в», так что $(a,b) \in R$ (то есть $aRb$), если студент $a$ зачислен на курс $b$.

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

Иногда существуют отношения между множеством $A$ и самим собой: подмножество $A \times A$. В этом случае мы говорим, что отношение находится на множестве $A$.

Вот еще несколько примеров отношений:

• Пусть $A = \{1,2,3,4\}$. Какие упорядоченные пары входят в отношение $R = \{ (a,b) \;|\; a \text{ делит } b \}$? $$ R = \{ (1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (3 ,4) \} $$ Это можно представить несколькими способами:

• Ниже приведены соотношения на $\mathbb{Z}$:
  • $R_1 = \{ (a,b) \;|\; а\ле б\}$
  • $R_2 = \{ (a,b) \;|\; а \gt б \}$
  • $R_3 = \{ (a,b) \;|\; a = b \text{ или } a = -b \}$
  • $R_4 = \{ (a,b) \;|\; а = б \}$
  • $R_5 = \{ (a,b) \;|\; а = b+1 \}$
  • $R_6 = \{ (a,b) \;|\; а+б \ле 3 \}$
  У нас есть:
  • $(1,1) \in R_1,R_3,R_4,R_6$
  • $(1,2) \in R_1,R_6$
  • $(2,1) \in R_2,R_5,R_6$
  • $(1,-1) \in R_2,R_3,R_6$
  • $(2,2) \in R_1,R_3,R_4$

Свойства отношений

Отношения могут иметь несколько свойств, которые помогают их классифицировать.

• Рефлексивность : отношение $R$ на множестве $A$ является рефлексивным , если $(a,a) \in R$ для всех $a \in A$.

  Например, если $A = \{1,2,3,4\}$, то:

  • $R_1 = \{ {\bf(1,1)},(1,2),{\bf(2,2)},(2,3),{\bf(3,3)},( 3,1),{\bf(4,4)} \}$ рефлексивно
  • $R_2 = \{ (1,2),(2,3),(3,4) \}$ не рефлексивно, так как $(1,1) \notin R_2$
  • $R_3 = \{ (1,1),(2,2)(3,3),(1,4) \}$ не рефлексивно, так как $(4,4) \notin R_3$

  В качестве другого примера, отношение «делит» является рефлексивным, поскольку $a = 1a$ для любого целого числа $a$

• Симметрия : отношение $R$ на множестве $A$ называется симметричным , если $(a,b) \in R \rightarrow (b,a) \in R$ для всех $a,b \in A $
• Антисимметрия : отношение $R$ на множестве $A$ называется антисимметричный , если $((a,b) \in R \wedge (b,a) \in R) \rightarrow (a=b)$ для всех $a,b \in A$.

  Примечание: симметрия и антисимметрия , а не взаимоисключающие: отношение может иметь одно, оба или ни одно из них. Рассмотрим следующие соотношения на $\{1,2,3,4\}$:

  • $R_1 = \{ (1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4) \}$
    • несимметричный: $(3,4) \in R_1$, но $(4,3) \notin R_1$
    • не антисимметрично: $(2,1), (1,2) \in R_1$, но $1 \neq 2$
  • $R_2 = \{ (1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1) \}$
    • симметричный
    • не антисимметрично: $(2,1), (1,2) \in R_2$, но $1 \neq 2
  • $R_3 = \{ (2,1),(3,1),(3,2),(4,1),(4,2),(4,3) \}$
    • несимметричный: $(2,1) \in R_3$, но $(1,2) \notin R_3$
    • антисимметричный
  • $R_4 = \{ (1,1),(2,2) \}$
    • симметричный
    • антисимметричный
• Транзитивность : отношение $R$ на множестве $A$ называется транзитивным , если для всех $a,b,c \in A$, $$((a,b) \in R \wedge (b,c) \in R) \rightarrow (a,c) \in R$$

  Например, все следующие отношения на $\mathbb{Z}$ транзитивны:

  • $\{ (а,б) \;|\; а\ле б\}$
  • $\{ (а,б) \;|\; а \gt б \}$
  • $\{ (а,б) \;|\; a = b \text{ или } a = -b \}$
  • $\{ (а,б) \;|\; а = б \}$

  , тогда как следующие не являются:

  • $\{ (а,б) \;|\; а=b+1 \}$
  • $\{ (а,б) \;|\; а+б \ле 3 \}$

  Отношение «делит» также транзитивно. Предположим, что $a|b$ и $b|c$. Тогда $b=ka$ и $c=lb$ для целых чисел $k$ и $l$. Следовательно, $c = lb = (lk)a$, поэтому $a|c$.

Объединение взаимосвязей

Отношения — это наборы, поэтому их можно комбинировать так же, как и наборы.

• Пусть $A = \{1,2,3\}, B = \{ 1,2,3,4 \}$ и определим отношения $R_1 = \{(1,1),(2,2),( 3,3)\}$ и $R_2 = \{ (1,1),(1,2),(1,3),(1,4) \}$ от $A$ до $B$ можно комбинировать следующим образом:
  • $R_1 \cup R_2 = \{ (1,1),(1,2),(1,3),(1,4),(2,2),(2,3)\}$
  • $R_1 \cap R_2 = \{ (1,1) \}$
  • $R_1 \setminus R_2 = \{ (2,2),(3,3) \}$
  • $R_2 \setminus R_1 = \{ (1,2),(1,3),(1,4) \}$
• Пусть $R_1 = \{ (a,b) \;|\; a \lt b\}$ и $R_2 = \{ (a,b) \;|\; a \gt b \}$ — отношения, определенные на $\mathbb{R}$.
  • $R_1 \cup R_2 = \{(a,b) \;|\; a \lt b \text{ или } a \gt b\} = \{ (a,b) \;|\; а \neq б\}$
  • $R_1 \cap R_2 = \{(a,b) \;|\; a \lt b \text{ и } a \gt b\} = \emptyset$
  • $R_1 \setminus R_2 = R_1$
  • $R_2 \setminus R_1 = R_2$

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

Пусть $R$ отношение множества $A$ к множеству $B$. Пусть $S$ — отношение множества $B$ к множеству $C$. Композиция $R$ и $S$ — это отношение, состоящее из упорядоченных пар $(a,c)$, где $a \in A$, $c \in C$ и существует элемент $b \in B $ такие, что $(a,b) \in R$ и $(b,c) \in S$. Обозначим это отношение через $S \circ R$.

Например, если у нас есть отношение $R$ из множества $\{1,2,3\}$ к множеству $\{1,2,3,4\}$ и отношение $S$ из множества $\{1,2,3,4\}$ множества $\{1,2,3,4\}$ на множество $\{0,1,2\}$, определяемое следующим образом:

• $R = \{ (1,1),(1,4),(2,3),(3,1),(3,4) \}$
• $S = \{ (1,0),(2,0),(3,1),(3,2),(4,1) \}$

тогда $S \circ R = \{ (1,0),(1,1),(2,1),(2,2),(3,0),(3,1) \}$.

Один особый случай композиции имеет место, когда вы составляете отношение с самим собой. Например, пусть $R = \{ (a,b) \;|\; a \text{ является родителем } b \}$, который должен быть определен на множестве всех людей. Тогда $R \circ R$ — это множество упорядоченных пар $(a,c)$ таких, что существует человек $b$ такой, что $a$ — родитель $b$, а $b$ — родитель $ c$, \т. е. $a$ является прародителем $c$. 9{k+1} \subseteq R$.

Рефлексивное замыкание

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

Как добавить элементы к нашему отношению, чтобы гарантировать свойство? В идеале мы хотели бы добавить как можно меньше новых элементов, чтобы сохранить «значение» исходного отношения.

Сначала рассмотрим рефлексивность отношения. Это называется рефлекторной застежкой 9.0018 . Предположим, у нас есть отношение $R$ на множестве $A$ и мы хотим сделать его рефлексивным. Нам нужно убедиться, что $(a,a)$ находится в отношении для всех $a \in A$. Мы также не хотим добавлять ничего лишнего.

Определить $\Delta = \{ (a,a) \;|\; а\в А\}$. Рефлексивное замыкание $R$ есть $R \cup \Delta$.

Например, рефлексивное замыкание $R = \{ (a,b) \;|\; a \lt b \}$ на множестве целых чисел есть отношение

$$R \cup \Delta = \{ (a,b) \;|\; a \lt b \} \cup \{ (a,a) \;|\; a \in \mathbb{Z} \} = \{ (a,b) \;|\; а \ле б \}$$ 9{-1} = \{ (а,б) \;|\; a \lt b \} \cup \{ (b,a) \;|\; a \gt b \} = \{ (a,b) \;|\; а \neq б \}$$

Транзитивное замыкание

Рассмотрим $R = \{ (1,3),(1,4),(2,1),(3,2) \}$ на $A = \{1,2,3, 4\}$. Это не транзитивное отношение: в нем отсутствуют $\{(1,2),(2,3),(2,4),(3,1) \}$. Попробуем добавить их и назвать новое отношение $R’$:

. $$R’ = \{ (1,3),(1,4),(2,1),(3,2),(1,2),(2,3),(2,4),( 3,1) \}$$

К сожалению, это отношение все же не транзитивно: $(3,1) \in R’$ и $(1,4) \in R’$, а $(3,4) \notin R’$. Кажется, нам нужно будет еще немного поработать.

Напомним, что если составить $R$ из самого себя, то мы получим элементы $(a,c)$, где $(a,b) \in R$ и $(b,c) \in R$ для некоторого $ б$. Эти элементы нужны нам для транзитивности, поэтому добавьте их в $R$. Как мы видели выше, этого может быть недостаточно, поэтому повторяем это.

Сколько раз мы повторяем? Это то же самое, что спросить, сколько промежуточных элементов мы могли бы найти. Так как существует $|A|$ возможных промежуточных элементов, нам может понадобиться сделать до $|A|$ композиций.

Следовательно, транзитивное замыкание $R$ над множеством $A$ равно 93$ (поскольку $|A| = 3$): $\{ (1,1),(1,2),(1,3),(2,2),(3,1),(3,2 ),(3,3) \}$

Оказывается, мы можем посмотреть на это по-другому, если посмотрим на матричное представление. Для заданных матричных представлений $M_R$ и $M_S$ для отношений $R$ и $S$ матричное представление $S \circ R$ есть $M_R \odot M_S$, где $\odot$ обозначает соединений операция. Эта операция идентична умножению матриц, но любые ненулевые элементы просто записываются как единицы.

Матричное представление $R$ в предыдущем примере: $$ M_R = \begin{bmatrix} 1 и 0 и 1 \\ 0 и 1 и 0 \\ 1 и 1 и 0 \\ \end{bmatrix} $$ 92} \odot M_R = \begin{bmatrix} 1 и 1 и 1 \\ 0 и 1 и 0 \\ 1 и 1 и 1 \\ \end{bmatrix} $$

Теперь мы объединим эти матрицы, выполнив логическое ИЛИ каждой записи: $$ \begin{bmatrix} 1 и 0 и 1 \\ 0 и 1 и 0 \\ 1 и 1 и 0 \\ \end{bmatrix} \ ви \begin{bматрица} 1 и 1 и 1 \\ 0 и 1 и 0 \\ 1 и 1 и 1 \\ \end{bmatrix} \ ви \begin{bматрица} 1 и 1 и 1 \\ 0 и 1 и 0 \\ 1 и 1 и 1 \\ \end{bmatrix} знак равно \begin{bматрица} 1 и 1 и 1 \\ 0 и 1 и 0 \\ 1 и 1 и 1 \\ \end{bmatrix} $$

Как и следовало ожидать, это матричное представление $\{ (1,1),(1,2),(1,3),(2,2),(3,1),(3,2 ),(3,3) \}$; тот же ответ, который мы вычислили ранее.

Транзитивные отношения — определение, примеры, свойства

Транзитивные отношения — это бинарные отношения, определенные на множестве таким образом, что если первый элемент связан со вторым элементом, а второй элемент связан с третьим элементом множества, тогда первый элемент должен быть связан с третьим элементом. Например, если для трех элементов a, b, c множества A, если a = b и b = c, то a = c. Здесь равенство ‘=’ является транзитивным отношением. В дискретной математике в основном существует три типа отношений, а именно рефлексивные, симметричные и транзитивные отношения среди многих других.

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

1.	Что такое транзитивные отношения?
2.	Определения, относящиеся к транзитивным отношениям
3.	Примеры переходных отношений
4.	Свойства переходных отношений
5.	Часто задаваемые вопросы о транзитивных отношениях

Что такое транзитивные отношения?

Транзитивные отношения — это бинарные отношения в теории множеств, которые определены на множестве A таким образом, что если a связано с b, а b связано с c, то элемент a должен быть связан с элементом c, для a, b, c в множестве А. Чтобы понять это, давайте рассмотрим пример транзитивных отношений. Определить отношение R на множестве целых чисел Z как aRb тогда и только тогда, когда a > b. Теперь предположим, что для целых чисел a, b, c в Z, aRb и bRc ⇒ a > b и b > c. Мы знаем, что для целых чисел всякий раз, когда a > b и b > c, мы имеем a > c, что означает, что a связано с c, то есть aRc. Следовательно, R — транзитивное отношение.

Transitive Relations Definition

Бинарное отношение R, определенное на множестве A, называется транзитивным отношением для всех a, b, c в A, если a R b и b R c, то a R c, т. е. если a связано с b, а b связано с c, то a должно быть связано с c. Математически это можно записать так: отношение R, определенное на множестве A, является транзитивным отношением для всех a, b, c ∈ A, если (a, b) ∈ R и (b, c) ∈ R, то (a, c) ∈ R.

Приведем некоторые определения отношений, относящихся к транзитивным отношениям:

• Антитранзитивное отношение — Бинарное отношение R, определенное на множестве A, является антитранзитивным отношением для a, b, c в A, если (a, b) ∈ R и (b, c) ∈ R, то это всегда означает, что (a, c) ∈ R не выполняется.
• Интранзитивное отношение — Бинарное отношение R, определенное на множестве A, является нетранзитивным отношением для некоторых a, b, c в A, если (a, b) ∈ R и (b, c) ∈ R, но (a, c) ∉
р.

Примеры переходных отношений

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

• ‘является подмножеством’ является транзитивным отношением, определенным на множестве множеств множества. Если A является подмножеством B, а B является подмножеством C, то A является подмножеством C.
• «Является биологическим братом или сестрой» — это переходное отношение, например, если один человек А является биологическим братом или сестрой другого человека В, а В является биологическим братом или сестрой С, то А является биологическим родным братом С.
• «Меньше чем» — это транзитивное отношение, определенное для набора чисел. Если a < b и b < c, то a < c.
• «Равно (=)» — это транзитивное отношение, определенное на множестве чисел. Если а = b и b = с, то а = с.
• «конгруэнтно» — это транзитивное отношение, определенное на множестве треугольников. Если треугольник 1 равен треугольнику 2, а треугольник 2 равен треугольнику 3, то треугольник 1 равен треугольнику 3.

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

Давайте рассмотрим некоторые свойства транзитивных отношений:

• Обратное транзитивному отношению является транзитивным отношением. Например, как мы обсуждали выше, «меньше, чем» является транзитивным отношением, тогда и обратное «больше, чем» также является транзитивным отношением.
• Объединение двух транзитивных отношений не обязательно должно быть транзитивным. Например, предположим, что R и S являются транзитивными отношениями, такими что (x, y) находится в R, и (y, z) находится в S, но (x, z) не находится ни в одном из них.
• Пересечение двух транзитивных отношений является транзитивным отношением. Например, «больше или равно» и «равно» являются транзитивными отношениями, а их отношение пересечения — «равно», которое является транзитивным отношением.
• Транзитивное отношение является асимметричным отношением тогда и только тогда, когда оно иррефлексивно.

Важные замечания по транзитивным отношениям

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

Связанные темы по транзитивным отношениям

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

Часто задаваемые вопросы о транзитивных отношениях

Что такое транзитивные отношения в теории множеств?

Транзитивные отношения — это бинарные отношения в теории множеств, которые определены на множестве B таким образом, что элемент a должен быть связан с элементом c, если a связан с b и b связан с c, для a, b, c в B.

Что такое рефлексивные, симметричные и транзитивные отношения?

• Бинарное отношение R, определенное на множестве A, называется рефлексивным, если для каждого элемента a ∈ A выполняется aRa, т. е. (a, a) ∈ R.
• Бинарное отношение R, определенное на множестве A, называется симметричным тогда и только тогда, когда для элементов a, b ∈ A, имеем aRb, то есть (a, b) ∈ R, то мы должны иметь bRa, то есть (b, a) ∈ R.

  No related posts.