Выяснить какими свойствами обладает бинарное отношение онлайн

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

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

Понравилось? Добавьте в закладки

Задачи с решениями о бинарных отношения онлайн

Задача 1. Определите свойства следующих отношений:
1. «прямая x пересекает прямую y» (на множестве прямых)
2. «число x больше числа y на 2» (на множестве натуральных чисел)
3. «число x делится на число y без остатка» (на множестве натуральных чисел)
4. «x – сестра y» (на множестве людей).

Задача 2. Проверить, является ли отношением эквивалентности на множестве всех прямых на плоскости отношение «непересекающихся прямых».

Задача 3. Найти область определения, область значений отношения Р. Является ли отношение Р рефлексивным, симметричным, антисимметричным, транзитивным.

Задача 4. Дано множество $А = { gt, lt, ge, le}$. Записать декартовое произведение $А times А$. Задать 2 бинарных отношения $R_1$ и $R_2$, мощность которых равна 3 и 4 соответственно. Найдите соответствующие замыкания обоих отношений. Изобразите ориентированные графы и запишите матрицы для отношений $R_1$ и $R_2$ и соответствующих замыканий. Вычислите $R_1^{-1}$, $R_2^{-1}$, $R_2 cdot R_1$. Изобразите соответствующие ориентированные графы и запишите соответствующие матрицы.

Задача 5. Отношение $R$ на множестве $Х ={a,b, c, d}$ задано матрицей.

Каковы свойства отношения $R$? Как выглядят матрицы отношений $R^{-1}$, $R cdot R$?

Задача 6. Дано множество $A = {1,2,3,4,5}$ и бинарное отношение $R subset A times A$:
Проверить, является ли $R$ отношением эквивалентности. Добавить минимальное возможное число пар, чтобы $R$ стало отношением эквивалентности. Найти разбиение $P$.

Задача 7. Доказать, что для любых бинарных отношений

$$(P_1 circ P_2)^{-1}=P_2^{-1} circ P_1^{-1}$$

Задача 8. Доказать истинность следующего утверждения: если $Р$ и $S$ – антисимметричны, то $P cap S$ – антисимметрично.

Задача 9.
Для заданных на множестве $А={1,2,3,4,5}$ бинарных отношений $rho$ и $tau$:
а) записать матрицы и построить графики;
б) найти композицию $rho circ tau$;
в) исследовать свойства отношений $rho$, $tau$ и $rho circ tau$ (рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность).

Задача 10. На множестве вещественных чисел $R$ задано бинарное отношение $a rho b$ $ Leftrightarrow a^2 + a = b^2 + b$. Докажите, что $rho$ – отношение эквивалентности. Сколько элементов в классе эквивалентности?

Задача 11. Для бинарного отношения $rho$ между элементами множеств $A = {1,2,3,4,5}$, $B = {{1}, {1,2}, {2,5}, {3}}$, $a rho X Leftrightarrow anotin X$ найдите область определения $D_rho$ и область значений $R_rho$?

Задача 12. Дано множество $X={1,2,3,6}$ и отношение $R={(x,y) | x,y in X, x – $ делитель $y}$. Показать, что отношение $R$ является отношением порядка. Построить диаграмму Хассе частично упорядоченного множества $(X, R)$. Существует ли в множестве $X$ наибольший и наименьший элементы? Существуют ли несравнимые элементы?

Решение задач об отношениях на заказ

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

Заказать решение задач по бинарным отношениям легко

Бинарные отношения: основные сведения

Бинарным отношением $R$ называется подмножество пар $(a,b)in R$ декартова произведения $Atimes B$, т. е. $R subseteq Atimes B$. При этом множество $A$ называют областью определения отношения $R$, множество $B$ – областью значений.

Записывается это так: $aRb$ (т. е. $a$ и $b$ находятся в отношении $R$, пара $(a,b)$ принадлежит отношению $R$).

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

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

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

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

Для бинарных отношений (также как и для множеств) задаются операции объединения, пересечения, разности, дополнения, а также обратное отношение и композиция отношений.

Источник

Пусть $A$ и $B$ два конечных множества. Декартовым произведением множеств $A$ и $B$ называют множество $Atimes B,$состоящее из всех упорядоченных пар, где $ ain A, bin B. $

Бинарным отношением между элементами множества $A$ и $B$ называется любое подмножество $R$ множества $Atimes B$, то есть $ Rsubset Atimes B.$

По определению, бинарным отношением называется множество пар. Если R — бинарное отношение (т.е. множество пар), то говорят, что параметры $x$ и $y$ связаны бинарным отношением $R$, если пара $langle x,y rangle $ является элементом R, т.е. $langle x,y ranglein R. $

Высказывание: «предметы $x$ и $y$ связаны бинарным отношением $R$» записывают в виде $xRy.$Таким образом, $ xRyleftrightarrowlangle x,yranglein R.$

Если $Rsubset Atimes A $, то говорят, что бинарное отношение определено на множестве $A$.

Примеры бинарных отношений:

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

Областью определения бинарного отношения $R$ называется множество, состоящее из таких $x$, для которых $langle x,y ranglein R $ хотя бы для одного $y$.
Область определения бинарного отношения будем обозначать $ Re R$.
$Re R={ x|exists y(langle x,yranglein R)}$
Областью значений бинарного отношения $R$ называется множество, состоящее из таких $y$, для которых $langle x,y ranglein R $ хотя бы для одного $x$.
Область значений бинарного отношения будем обозначать $Im R$
$Im R={ y|exists x(langle x,yranglein R)}$

Инверсия (обратное отношение) $R$ — это множество ${langle x,yrangle |langle y,xranglein R}$ и обозначается, как ${R}^{-1}.$

Композиция (суперпозиция) бинарных отношений $R$ и $S$ — это множество ${langle x,yrangle |exists zlangle xSzwedge zRyrangle}$ и обозначается, как $Rcirc S$.

Бинарное отношение $R$ на некотором множестве $M$ может обладать различными свойствами, например:

Рефлексивность: $forall xin M(xRx)$
Антирефлексивность (иррефлексивность): $forall xin Mneg (xRx)$
Корефлексивность: $forall x,yin M(xRyRightarrow x=y)$
Симметричность: $forall x,yin M(xRyRightarrow yRx)$
Антисимметричность: $forall x,yin M(xRywedge yRxRightarrow x=y)$
Асимметричность: $forall x,yin M(xRyRightarrowneg (yRx))$. Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.
Транзитивность: $forall x,y,zin M(xRywedge yRzRightarrow xRz)$
Связность: $forall x,yin M(xneq yRightarrow xRylor yRx)$

Рефлексивное транзитивное отношение называется отношением квазипорядка
Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности
Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка
Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка
Полное антисимметричное (для любых $x, y$ выполняется $xRy$ или $yRx$) транзитивное отношение называется отношением линейного порядка

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

Пересечение. Пересечением двух бинарных отношений ($A$и $B$) является отношение, которое определяется пересечением соответствующих подмножеств. Очевидно, что отношение $Acap B$ выполнимо только в том случае, когда некоторые $x$ и $y$ связаны как первым, так и вторым отношением ($xAy$ и $xBy$).
Например, пересечением отношения «не меньше» и «не равно» является отношение «больше».
$ xAyLeftrightarrow xgeq y, xByLeftrightarrow xneq y$, тогда $Acap BLeftrightarrow x>y $
Объединение. Объединением двух бинарных отношений ($A$ и $B$) является отношение, которое определяется объединением соответствующих подмножеств. Отношение $Acup B$ выполнимо только в том случае, когда некоторые $x$ и $y$ связаны хотя бы одним из двух отношений хотя бы одно из отношений ($xAy$ или $xBy$).
Например, объединением отношения «больше» и отношения «равно» является отношение «больше, либо равно».
Включение. Обозначается $Asubseteq B$. Первое отношение включено во второе, если все те пары, для которых выполняется первое отношение, являются подмножеством пар, для которых выполняется второе отношение. Если $Asubseteq B$, то $Aneq B$. Если $Asubseteq B$, то, когда любые два элемента из множества, на котором выполняется отношение $A$, связаны этим отношением, они связаны отношением $B$.

Очевидно, для любого отношения $A varnothingsubseteq Asubseteq U$, где $varnothing$ — пустое, а $U$- полное отношение.

Приведём в пример два графических представления бинарных отношений на множстве $X = {a, b, c, d, e}.$
Первый способ тесно связан с аналитической геометрией. Пусть дана пара взаимно перпендикулярных осей ($Ox$ и $Oy$). На каждой оси нужно отметить точки которые являются элементами множества $X$.
Будем считать, что $a, b, c, d, e$ — координаты точек на горизонтальной и вертикальной осях. Теперь отметим на плоскости точки с координатами $(x, y)$. На рисунке изображена совокупность точек, соответствующих следующему отношению: $R={(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)}.$

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

Задача

Бинарное отношение $R$ задано на множестве $A={1,2,3,4}$, определить его свойства.
$R={(1,1),(1,2),(2,3),(2,2),(2,4)}$

Спойлер

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

Рефлексивность
$(forall xin A)langle x,xranglein R$ – это ложное высказывание.
Можно привести контрпример: $x=3$, пара $langle 3,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является рефлексивным.
Антирефлексивность
$(forall xin A)langle x,xranglenotin R$ – это ложное высказывание.
Можно привести контрпример: $x=1$, пара $langle 1,1rangle$ принадлежит множеству $R$. Бинарное отношение не является антирефлексивным.
Корефлексивность
$(forall x,yin A)langle x,yranglenotin R$ – это ложное высказывание.
Можно привести контрпример: $x=1,y=2$, пара $langle 1,2rangle$ принадлежит множеству $R$, но $xneq y$. Бинарное отношение не является антирефлексивным.
Симметричность
$ forall x,yin A (langle x,yranglein R): langle y,xranglein R$ – это ложное высказывание.
Можно привести контрпример, $x=1,y=2$ пара $langle 1,2rangle$ принадлежит множеству $R$, а пара $langle 2,1rangle$ не принадлежит множеству $R$. Бинарное отношение не является симметричным.
Антисимметричность
$forall x,yin A(xRywedge yRxRightarrow x=y)$ – это истинное высказывание
Контрпример подобрать невозможно. Бинарное отношение является антисимметричным.
Асимметричность
Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения и отношение не является антирефлексивным, отношение не является асимметричным.
Транзитивность
$forall x,y,zin A(xRywedge yRzRightarrow xRz)$– это ложное высказывание.
Можно привести контр пример, $x=1,y=2,z=3$ пара $langle 1,2rangle$ принадлежит множеству R и пара $langle 2,3rangle$ принадлежит множеству $R$, а пара $langle 1,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является транзитивным.
Связность
$forall x,yin A(xneq yRightarrow xRylor yRx)$ – это ложное высказывание.
Можно привести контрпример, $x=3,y=4$, $3neq 4$ пара $langle 3,4rangle$ не принадлежит множеству $R$ и пара $langle 4,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является связанным.

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

[свернуть]

Источники:

Галушкина, Марьямов, «Задачи и упражнения по дискретной математике», 2007 г., стр.51
С.В.Федоровский.Конспект лекций по математической логике
Кострикин А.В. , «Введение в алгебру», 1977, стр.134
А.И. Мальцев, «Алгебраические системы», 1970, стр.16-19

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

Вопросы для закрепления пройденного материала

Таблица лучших: Бинарные отношения

максимум из 15 баллов

Место	Имя	Записано	Баллы	Результат
Таблица загружается

Источник

У этого термина существуют и другие значения, см. Отношение.

Бина́рное (двухместное) отноше́ние (соответствие[1][2]) — отношение между двумя множествами и , то есть всякое подмножество декартова произведения этих множеств: [3]. Бинарное отношение на множестве — любое подмножество , такие бинарные отношения наиболее часто используются в математике, в частности, таковы равенство, неравенство, эквивалентность, отношение порядка.

Связанные определения[править | править код]

Свойства отношений[править | править код]

Бинарное отношение на некотором множестве может обладать различными свойствами, например:

рефлексивность: ,
антирефлексивность (иррефлексивность): ,
корефлексивность: ,
симметричность: ,
антисимметричность: ,
асимметричность: ,
транзитивность: ,
евклидовость: ,
полнота (или связность[4]): ,
связность (или слабая связность[4]): ,
трихотомия: верно ровно одно из трех утверждений: , или .

Виды отношений[править | править код]

Виды бинарных отношений[править | править код]

Обратное отношение[уточнить] (отношение, обратное к ) — это двухместное отношение, состоящее из пар элементов , полученных перестановкой пар элементов данного отношения . Обозначается: . Для данного отношения и обратного ему верно равенство: .
Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
Рефлексивное отношение — двухместное отношение , определённое на некотором множестве и отличающееся тем, что для любого этого множества элемент находится в отношении к самому себе, то есть для любого элемента этого множества имеет место . Примеры рефлексивных отношений: равенство, одновременность, сходство.
Антирефлексивное отношение (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любого элемента этого множества неверно, что оно находится в отношении к самому себе (неверно, что ).
Транзитивное отношение — двухместное отношение , определённое на некотором множестве и отличающееся тем, что для любых из и следует (). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
Нетранзитивное отношение[уточнить] — двухместное отношение , определённое на некотором множестве и отличающееся тем, что для любых этого множества из и не следует (). Пример нетранзитивного отношения: «x отец y»
Симметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых элементов и этого множества из того, что находится к в отношении , следует, что и находится в том же отношении к — . Примером симметричных отношений могут быть равенство, отношение эквивалентности, подобие, одновременность.
Антисимметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых и из и следует (то есть и выполняются одновременно лишь для равных между собой членов).
Асимметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых и из следует . Пример: отношения «больше» (>) и «меньше» (<).
Отношение эквивалентности — бинарное отношение между объектами и , являющееся одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, подобие, одновременность.
Отношение порядка — отношение, обладающие только некоторыми из трёх свойств отношения эквивалентности: отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует нестрогий порядок, а отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — строгий порядок.
Функция одного переменного — бинарное отношение , определённое на некотором множестве, отличающееся тем, что каждому значению отношения соответствует лишь единственное значение . Свойство функциональности отношения записывается в виде аксиомы: .
Биекция (взаимно-однозначное отношение) — бинарное отношение , определённое на некотором множестве, отличающееся тем, что в нём каждому значению соответствует единственное значение , и каждому значению соответствует единственное значение .

Операции над отношениями[править | править код]

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

,
,
.

Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.

Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрогого порядка, а их пересечение пусто.

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

Пусть , . Композицией (или произведением) отношений и называется отношение такое, что:

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

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

Имеют место следующие тождества:

Аналоги последних двух тождеств для пересечения отношений не имеют места.

Примечания[править | править код]

↑ Цаленко М. Ш. Соответствие // Математическая энциклопедия. — 1985. — Т. 5 (Слу-Я). — С. 77.
↑ Соответствие. Большая российская энциклопедия.
↑ Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 47-48. — 320 с. — ISBN 5-02-014644-7.
↑ 1 2 Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48)

Литература[править | править код]

Мальцев, А. И. Алгебраические системы. — М.: Наука, 1970. — 392 с. — 17 500 экз.

Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и коллективные решения. — М.: Учебники Высшей школы экономики, 2006. — 300 с.

Пухначев Ю. В., Попов Ю. П. Кн. 1: Множества, отображения, отношения, последовательности, ряды, функции, свойства функций, дифференциальное и интегральное исчисление, функции многих переменных // Математика без формул. — Изд. 6-е, испр. — М.: URSS, 2017. — 231 с. — ISBN 978-5-9710-3871-9.

Источник