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

Лекция 3.

п.3. Отношения на множествах. Свойства бинарных отношений.

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

Когда говорят о родстве двух людей, например, Сергей и Анна, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Сергей, Анна) отличается от других упорядоченных пар людей тем, что между Сергеем и Анной есть некое родство (кузина, отец и т. д.).

В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A´B) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S´K можно выделить большое подмножество упорядоченных пар (s, k), обладающих свойством: студент s слушает курс k. Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.

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

Определение 3.1. Бинарным (или двухместным) отношением r между множествами A и B называется произвольное подмножество A´B, т. е.

В частности, если A=B (то есть rÍA2), то говорят, что r есть отношение на множестве A.

Элементы a и b называются компонентами (или координатами) отношения r.

Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит: r, t, j, s, w и т. д.

Определение 3.2. Областью определения бинарного отношения r называется множество Dr={a | $ b, что arb} (левая часть). Областью значений бинарного отношения r называется множество Rr={b | $ a, что arb} (правая часть).

Пример 3.1. Пусть даны два множества A={1; 3; 5; 7} и B={2; 4; 6}. Отношение зададим следующим образом t={(x; y)ÎA´B | x+y=9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере Dt={3; 5; 7} и Rt= B={2; 4; 6}.

Пример 3.2. Отношение равенства на множестве действительных чисел есть множество r={(x; y) | x и y – действительные числа и x равно y}. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, Dr= Rr.

Пример 3.3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j={(x; y)ÎA´B | y – цена x} – отношение множеств A и B.

Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t={(x; y)ÎA´B | x+y=9}, а потом записано в виде t={(3; 6), (5;4), (7;2)}. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.

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

1) с помощью подходящего предиката;

2) множество упорядоченных пар;

3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом, точки же, изображающие элементы множеств, принято называть вершинами графа.

4) в виде матрицы: пусть A={a1, a2, …, an} и B={b1, b2, …, bm}, r – отношение на A´B. Матричным представлением r называется матрица M=[mij] размера n´m, определенная соотношениями

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

Пример 3.4. Пусть даны два множества A={1; 3; 5; 7}и B={2; 4; 6}. Отношение задано следующим образом t={(x; y) | x+y=9}. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.

Решение. 1) t={(3; 6), (5; 4), (7; 2)} – есть задание отношения как множества упорядоченных пар;

2) соответствующий ориентированный граф показан на рисунке.

3) в матричном представлении это отношение имеет вид

. ,

Пример 3.5. Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M:

где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.

Рассмотрим информационный обмен между устройствами mi и mj, которые находятся в отношении r, если из устройства mi поступает информация в устройство mj.

Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:

Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:

Матричное представление этого бинарного отношения имеет вид:

. ,

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

Введем обобщенное понятие отношения.

Определение 3.3. n-местное (n–арное) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей)

rÍA1´…´An={(a1, …, an)| a1ÎA1Ù … ÙanÎAn}

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

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

Далее мы будем рассматривать только двухместные (бинарные) отношения, при этом опуская слово «бинарные».

Определение 3.4. Пусть rÍA´B есть отношение на A´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A´B, которое определяется следующим образом:

r-1={(b, a) | (a, b)Îr}.

Определение 3.5. Пусть r ÍA´B есть отношение на A´B, а s ÍB´C – отношение на B´C. Композицией отношений s и r называется отношение t ÍA´C,которое определяется следующим образом:

t=s◦r= {(a, c)| $ b Î B, что (a, b)Îr и (b, c)Îs}.

Пример 3.6. Пусть , и C={,, !, d, à}. И пусть отношение r на A´B и отношение s на B´C заданы в виде:

r={(1, x), (1, y), (3, x)};

s={(x, ,), (x, !), (y, d), (y, à)}.

Найти r-1 и s◦r, r◦s.

Решение. 1) По определению r-1={(x, 1), (y, 1), (x, 3)};

2) Используя определение композиции двух отношений, получаем

s◦r={(1, ,), (1, !), (1, d), (1, à), (3, ,), (3, !)},

поскольку из (1, x)Îr и (x, ,)Îs следует (1, ,)Îs◦r;

из (1, x)Îr и (x, !)Îs следует (1, !)Îs◦r;

из (1, y)Îr и (y, d)Îs следует (1, d)Îs◦r;

…

из (3, x)Îr и (x, !)Îs следует (3, !)Îs◦r.

3) r◦s=Æ.

Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:

1) ;

2) ;

3) – ассоциативность композиции.

Доказательство. Свойство 1 очевидно.

Докажем свойство 2. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементов. Пусть (a; b) Î (s◦r)-1 Û (b; a) Î s◦r Û $ c такое, что (b; c) Î r и (c; a) Î s Û $ c такое, что (c; b) Î r-1 и (a; c) Î s-1 Û (a; b) Î r -1◦s -1.

Свойство 3 доказать самостоятельно.

■

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

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

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

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

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

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

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

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

Пример 3.7. Пусть A={1; 2; 3; 4; 5; 6}. На этом множестве задано отношение rÍA2, которое имеет вид: r={(1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)}. Какими свойствами обладает данное отношение?

Решение. 1) Это отношение рефлексивно, так как для каждого aÎA, (a; a)Îr.

2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.

3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:

Случай	(a, b)Îr	(b, a)	(b, a)Îr?
1	(1; 2)	(2; 1)	Да
2	(1; 4)	(4; 1)	Да
3	(2; 1)	(1; 2)	Да
…	…	…	…

4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.

5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.

Случай	(a, b)Îr	(b, c)Îr	(a, c)	(a, c)Îr?
1	(1; 2)	(2; 1)	(1; 1)	Да
2	(1; 2)	(2; 2)	(1; 2)	Да
3	(1; 2)	(2; 4)	(1; 4)	Да
4	(1; 4)	(4; 1)	(1; 1)	Да
5	(1; 4)	(4; 2)	(1; 2)	Да
…	…	…	…	…

Как по матрице представления

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

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

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

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

4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.

Операция «*» выполняется по следующему правилу: , где , .

5. Транзитивность: если . Операция «◦» выполняется по обычному правилу умножения, при этом надо учитывать: .

3.3 Отношение эквивалентности. Отношение частичного порядка.

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

Определение 3.6. Отношение r на A есть отношение эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности arb часто обозначается: a ~ b.

Пример 3.8. Отношение равенства на множестве целых чисел есть отношение эквивалентности.

Пример 3.9. Отношение «одного роста» есть отношение эквивалентности на множестве людей X.

Пример 3.1. Пусть ¢ – множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (mÎ¥) и запишем , если равны остатки этих чисел от деления их на m, т. е. разность (x–y) делится на m.

Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:

это отношение рефлексивно, т. к. для “xÎ¢ имеем x–x=0, и, следовательно, оно делится на m;

это отношение симметрично, т. к. если (x–y) делится на m, то и (y–x) тоже делится на m;

это отношение транзитивно, т. к. если (x–y) делится на m, то для некоторого целого t1 имеем , а если (y–z) делится на m, то для некоторого целого t2 имеем , отсюда , т. е. (x–z) делится на m.

Определение 3.7. Отношение r на A есть отношение частичного порядка, если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.

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

Пример 3.11. Отношение x£y на множестве действительных чисел есть отношение частичного порядка. ,

Пример 3.12. Во множестве подмножеств некоторого универсального множества U отношение AÍB есть отношение частичного порядка.

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

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

Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве A и определить наилучшие объекты.

Отношение предпочтения P, которое можно определить как «aPb, a, bÎA Û объект a не менее предпочтителен, чем объект b» является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a, то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.

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

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

Источник

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

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

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

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

Задача 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 баллов

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

Источник