Дискретная математика бинарные отношения

Дискретная математика бинарные отношения

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

Обозначение: aRb (т. е. a и b находятся в отношении R ). /

Замечание: если A = B , то говорят, что R есть отношение на множестве A .

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

1. Списком (перечислением пар), для которых это отношение выполняется.

2. Матрицей. Бинарному отношению R ∈ A × A , где A = (a1 , a2 . an), соответствует квадратная матрица порядка n , в которой элемент cij, стоящий на пересечении i-й строки и j-го столбца, равен 1, если между ai и aj имеет место отношение R , или 0, если оно отсутствует:

Пусть R – отношение на множестве A, R ∈ A×A . Тогда отношение R:

рефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефлексивного отношения содержит только единицы);

антирефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефле сивного отношения содержит только нули);

симметрично, если Ɐ a , b ∈ A: a R b ⇒ b R a (матрица такого отношения симметрична относительно главной диагонали, т.е. cij cji);

транзитивно, если Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c (в матрице такого отношения должно выполняться условие: если в i-й строке стоит единица, например в j-ой координате (столбце) строки, т. е. cij = 1 , то всем единицам в j-ой строке (пусть этим единицам соответствуют k е координаты такие, что, cjk = 1 ) должны соответствовать единицы в i-й строке в тех же k-х координатах, т. е. cik = 1 (и, может быть, ещё и в других координатах).

Задача 3.1. Определите свойства отношения R – «быть делителем», заданного на множестве натуральных чисел.

рефлексивно, не антирефлексивно, так как любое число делит само себя без остатка: a/a = 1 для всех a∈N ;

не симметрично, антисимметрично, например, 2 делитель 4, но 4 не является делителем 2;

транзитивно,таккакесли b/a ∈ N и c/b ∈ N, то c/a = b/a ⋅ c/b ∈ N, например, если 6/3 = 2∈N и 18/6 = 3∈N, то 18/3 = 18/6⋅6/3 = 6∈N.

Задача 3.2. Определите свойства отношения R – «быть братом», заданного на множестве людей.
Решение.

не рефлексивно, антирефлексивно из-за очевидного отсутствия aRa для всех a;

не симметрично, так как в общем случае между братом a и сестрой b имеет место aRb , но не bRa ;

не антисимметрично, так как если a и b –братья, то aRb и bRa, но a≠b;

транзитивно, если называть братьями людей, имеющих общих родителей (отца и мать).

Задача 3.3. Определите свойства отношения R – «быть начальником», заданного на множестве элементов структуры

  • не рефлексивно, антирефлексивно, если в конкретной интерпретации не имеет смысла;
  • не симметрично, антисимметрично, так как для всех a≠b не выполняется одновременно aRb и bRa;
  • транзитивно, так как если a начальник b и b начальник c , то a начальник c .

Задачи для самостоятельного решения

Определите свойства отношения Ri , заданного на множестве Mi матрицей, если:

Читайте также:  Чем отличается ps4 slim от pro

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

Пусть R1, R1 есть отношения, заданные на множестве A .

универсальное отношение U: = <(a;b)/a ∈ A & b ∈ A>. ;

дополнение R1 U R1, где U = A × A;

тождественное отношение I : = <(a;a) / a ∈ A>;

обратное отношение R -1 1 : R -1 1 = <(a,b) : (b,a) ∈ R1>;

Определение. Степенью отношения R на множестве A называется его композиция с самим собой.

Обозначение:

Определение. Если R ⊂ A × B , то R º R -1 называется ядром отношения R .

Теорема 3.1. Пусть R ⊂ A × A – отношение, заданное на множестве A .

  1. R рефлексивно тогда и только тогда, (далее используется знак ⇔) когда I ⊂ R.
  2. R симметрично ⇔ R = R -1 .
  3. R транзитивно ⇔ R º R ⊂ R
  4. R антисимметрично ⇔ R ⌒ R -1 ⊂ I .
  5. R антирефлексивно ⇔ R ⌒ I = ∅ .

Задача 3.4. Пусть R — отношение между множествами <1,2,3>и <1,2,3,4>, заданное перечислением пар: R = <(1,1), (2,3), (2,4), (3,1), (3,4)>. Кроме того, S — отношение между множествами S = <(1,1), (1,2), (2,1), (3,1), (4,2)>. Вычислите R -1 , S -1 и S º R. Проверьте, что ( S º R) -1 = R -1 , S -1 .

Задача 3.5. Пусть R отношение «. родитель. », а S отношение «. брат. » на множестве всех людей. Дайте краткое словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 и R º R.

R -1 — отношение«. ребёнок. »;

S -1 — отношение«. брат или сестра. »;

R º S — отношение «. родитель. »;

S -1 º R -1 — отношение «. ребёнок. »

R º R — отношение «. бабушка или дедушка. »

Задачи для самостоятельного решения

1) Пусть R — отношение «. отец. », а S — отношение «. сестра. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , R º R.

2) Пусть R — отношение «. брат. », а S — отношение «. мать. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , S º S.

3) Пусть R — отношение «. дед. », а S — отношение «. сын. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

4) Пусть R — отношение «. дочь. », а S — отношение «. бабушка. » на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

5) Пусть R — отношение «. племянница. », а S — отношение «. отец. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

6) Пусть R — отношение «сестра. », а S — отношение «мать. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

7) Пусть R — отношение «. мать. », а S — отношение «. сестра. » на множе- стве всех людей. Дайте словесное описание отношениям:

Читайте также:  Свойства браузера в эксплорере

R -1 , S1, R º S, S1 º R1, S º S.

8) Пусть R — отношение «. сын. », а S — отношение «. дед. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

9) Пусть R — отношение «. сестра. », а S — отношение «. отец. » на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

10) Пусть R — отношение «. мать. », а S — отношение «. брат. » на множестве всех людей. Дайте словесное описание отношениям:

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

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

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

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

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

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

Задача 5. Отношение $R$ на множестве $Х =$ задано матрицей.
Каковы свойства отношения $R$? Как выглядят матрицы отношений $R^<-1>$, $R cdot R$?

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

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

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

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

Читайте также:  Как выровнять по ширине без больших пробелов

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

Задача 11. Для бинарного отношения $
ho$ между элементами множеств $A = <1,2,3,4,5>$, $B = <<1>, <1,2>, <2,5>, <3>>$, $a
ho X Leftrightarrow a
otin X$ найдите область определения $D_
ho$ и область значений $R_
ho$?

Задача 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$ декартова произведения $A imes B$, т. е. $R subseteq A imes B$. При этом множество $A$ называют областью определения отношения $R$, множество $B$ – областью значений.

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

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

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

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

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

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

Для того, чтобы оценить ресурс, необходимо авторизоваться.

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

Ссылка на основную публикацию
Дзен яндекс новости включить на телефоне бесплатно
Ни для кого не секрет, что пользоваться платформой Яндекс.Дзен можно не только с компьютера, но и с телефона. И я...
Гугл диск синхронизация папки
Если вы ещё не разобрались, как синхронизировать Гугл Диск с компьютером, то сейчас мы вас научим это делать. На самом...
Гугл карта орел панорама
Панорамы Орла на карте позволяют совершить виртуальный тур по улицам Орла: просмотреть дома, памятники, мосты и достопримечательности на панорамах Орла....
Диабло 1 моды на русском
Download Diablo 1 HD MOD - DOWNLOAD Diablo 1 HD MOD v1.045 Early Developer Alpha Polish Language Public Beta v1.045...
Adblock detector