Бинарные отношения. Примеры бинарных отношений
Математика \ Специальные главы математики
Страницы работы
2 страницы (Word-файл)
Посмотреть все страницы
Скачать файл
Содержание работы
Бинарные отношения.
Пусть A и B – произвольные множества. Возьмем по одному элементу из каждого множества, a из A, b из B и запишем их так: <a, b> (сначала элемент первого множества, затем элемент второго множества – т.е. нам важен порядок, в котором берутся элементы). Такой объект будем называть упорядоченной парой. Равными будем считать только те пары, у которых элементы с одинаковыми номерами равны. <a, b> = <c, d>, если a = c и b = d. Очевидно, что если a ≠ b, то <a, b> ≠ <b, a>.
Декартовым
произведением произвольных множеств A и B (обозначается: AB)
называется множество, состоящее из всех возможных упорядоченных пар, первый
элемент которых принадлежит A, а второй принадлежит B.
Пример 5. Пусть A = {x, y} и B = {1, 2, 3}.
AB = {<x, 1>, <x, 2>, <x, 3>, <y, 1>, <y, 2>, <y, 3>}.
BA = {<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.
AA = A2 = {<x, x>, <x, y>, <y, x>, <y, y>}.
BB = B2 = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.
Бинарным отношением на множестве M называется множество некоторых упорядоченных пар элементов множества M. Если r – бинарное отношение и пара <x, y> принадлежит этому отношению, то пишут: <x, y> r или x r y. Очевидно, r Í M 2.
Пример 6.
Множество {<1, 2>, <2, 2>, <3, 4>, <5, 2>,
<2, 4>} является бинарным отношением на
множестве {1, 2, 3, 4, 5}.
Пример 7. Отношение ³ на множестве целых чисел является бинарным отношением. Это бесконечное множество упорядоченных пар вида <x, y>, где x ³ y, x и y – целые числа. Этому отношению принадлежат, например, пары <5, 3>, <2, 2>, <324, -23> и не принадлежат пары <5, 7>, <-3, 2>.
Пример 8. Отношение равенства на множестве A является бинарным отношением: IA = {<x, x> | x Î A}. IA называется диагональю множества A.
Поскольку бинарные отношения являются множествами, то к ним применимы операции объединения, пересечения, дополнения и разности.
Областью определения
Отношением, обратным к бинарному отношению r Í M2, называется бинарное отношение r-1 = {<y, x> | <x, y> Î r}.
Очевидно, что
D(r‑1) = R(r), R(r‑1) = D(r), r‑1 Í M2.
Композицией бинарных отношений r1 и r2, заданных на множестве M, называется бинарное отношение r2 o r1 = { <x, z> | существует y такое, что <x, y> Î r1 и <y, z> Í r2 }. Очевидно, что r2 o r1 Í M2.
Пример 9. Пусть бинарное отношение r задано на множестве M = {a, b, c, d}, r = {<a, b>, <a, c>, <c, c>, <c, d>}. Тогда D(r) = {a, c}, R(r) = {b, c, d}, r ‑1 = {<b, a>, <c, a>, <c, c>, <d, c>}, r o r = {<a, c>, <a, d>, <c, c>, <c, d>}, r‑1 o r = {<a, a>, <a, c>, <c, a>, <c, c>}, r o r‑1 = {<b, b>, <b, c>, <c, b>, <c, c>, <c, d>, <d, c>, <d, d>}.
Пусть r – бинарное отношение на множестве M.
Отношение r
называется рефлексивным, если x r x для любого x Î M. Отношение r называется симметричным, если вместе
с каждой парой <x, y>
оно содержит и пару <y, x>.
Отношение r называется транзитивным,
если из того, что x r y и y r z следует, что
x r z. Отношение r
называется антисимметричным, если оно не содержит одновременно пары <x, y> и <y, x> различных элементов x ¹ y
множества M.
Укажем критерии выполнения этих свойств.
Бинарное отношение r на множестве M рефлексивно тогда и только тогда, когда IM Í r.
Бинарное отношение r симметрично тогда и только тогда, когда r = r‑1.
Бинарное отношение r на множестве M антисимметрично тогда и только тогда, когда r Ç r‑1 = IM.
Бинарное отношение r транзитивно тогда и только тогда, когда r o r Í r.
Пример 10.
Отношение из примера 6 является антисимметричным, но не является симметричным,
рефлексивным и транзитивным.
Отношение из примера 7 является рефлексивным,
антисимметричным и транзитивным, но не является симметричным. Отношение IA обладает всеми четырьмя рассматриваемыми
свойствами. Отношения r‑1 o r и r o r‑1 являются симметричными,
транзитивными, но не являются антисимметричными и рефлексивными.
Отношением эквивалентности на множестве M называется транзитивное, симметричное и рефлексивное на М бинарное отношение.
Отношением частичного порядка на множестве М называется транзитивное, антисимметричное и рефлексивное на М бинарное отношение r.
Пример 11. Отношение из примера 7 является отношением частичного порядка. Отношение IA является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.
Похожие материалы
Информация о работе
Скачать файл
Выбери свой ВУЗ
- АлтГТУ 419
- АлтГУ 113
- АмПГУ 296
- АГТУ 267
- БИТТУ 794
- БГТУ «Военмех» 1191
- БГМУ 172
- БГТУ 603
- БГУ 155
- БГУИР 391
- БелГУТ 4908
- БГЭУ 963
- БНТУ 1070
- БТЭУ ПК 689
- БрГУ 179
- ВНТУ 120
- ВГУЭС 426
- ВлГУ 645
- ВМедА 611
- ВолгГТУ 235
- ВНУ им.
Даля 166 - ВЗФЭИ 245
- ВятГСХА 101
- ВятГГУ 139
- ВятГУ 559
- ГГДСК 171
- ГомГМК 501
- ГГМУ 1966
- ГГТУ им. Сухого 4467
- ГГУ им. Скорины 1590
- ГМА им. Макарова 299
- ДГПУ 159
- ДальГАУ 279
- ДВГГУ 134
- ДВГМУ 408
- ДВГТУ 936
- ДВГУПС 305
- ДВФУ 949
- ДонГТУ 498
- ДИТМ МНТУ 109
- ИвГМА 488
- ИГХТУ 131
- ИжГТУ 145
- КемГППК 171
- КемГУ 508
- КГМТУ 270
- КировАТ 147
- КГКСЭП 407
- КнАГТУ 2910
- КрасГАУ 345
- КрасГМУ 629
- КГПУ им. Астафьева 133
- КГТУ (СФУ) 567
- КГТЭИ (СФУ) 112
- КПК №2 177
- КубГТУ 138
- КубГУ 109
- КузГПА 182
- КузГТУ 789
- МГТУ им. Носова 369
- МГЭУ им. Сахарова 232
- МГЭК 249
- МГПУ 165
- МАИ 144
- МАДИ 151
- МГИУ 1179
- МГОУ 121
- МГСУ 331
- МГУ 273
- МГУКИ 101
- МГУПИ 225
- МГУПС (МИИТ) 637
- МГУТУ 122
- МТУСИ 179
- ХАИ 656
- ТПУ 455
- НИУ МЭИ 640
- НМСУ «Горный» 1701
- ХПИ 1534
- НТУУ «КПИ» 213
- НУК им. Макарова 543
- НВ 1001
- НГАВТ 362
- НГАУ 411
- НГМУ 665
- НГПУ 214
- НГТУ 4610
- НГУ 1993
- НГУЭУ 499
- НИИ 201
- ОмГТУ 302
- ОмГУПС 230
- СПбПК №4 115
- ПГУПС 2489
- ПГПУ им. Короленко 296
- ПНТУ им. Кондратюка 120
- РАНХиГС 190
- РОАТ МИИТ 608
- РТА 245
- РГГМУ 117
- РГПУ им. Герцена 123
- РГППУ 142
- РГСУ 162
- «МАТИ» — РГТУ 121
- РГУНиГ 260
- РЭУ им. Плеханова 123
- РГАТУ им. Соловьёва 219
- РязГМУ 125
- РГРТУ 666
- СамГТУ 131
- СПбГАСУ 315
- ИНЖЭКОН 328
- СПбГИПСР 136
- СПбГЛТУ им. Кирова 227
- СПбГМТУ 143
- СПбГПМУ 146
- СПбГПУ 1599
- СПбГТИ (ТУ) 293
- СПбГТУРП 236
- СПбГУ 578
- ГУАП 524
- СПбГУНиПТ 291
- СПбГУПТД 438
- СПбГУСЭ 226
- СПбГУТ 194
- СПГУТД 151
- СПбГУЭФ 145
- СПбГЭТУ «ЛЭТИ» 379
- ПИМаш 247
- НИУ ИТМО 531
- СГТУ им. Гагарина 114
- СахГУ 278
- СЗТУ 484
- СибАГС 249
- СибГАУ 462
- СибГИУ 1654
- СибГТУ 946
- СГУПС 1473
- СибГУТИ 2083
- СибУПК 377
- СФУ 2424
- СНАУ 567
- СумГУ 768
- ТРТУ 149
- ТОГУ 551
- ТГЭУ 325
- ТГУ (Томск) 276
- ТГПУ 181
- ТулГУ 553
- УкрГАЖТ 234
- УлГТУ 536
- УИПКПРО 123
- УрГПУ 195
- УГТУ-УПИ 758
- УГНТУ 570
- УГТУ 134
- ХГАЭП 138
- ХГАФК 110
- ХНАГХ 407
- ХНУВД 512
- ХНУ им. Каразина 305
- ХНУРЭ 325
- ХНЭУ 495
- ЦПУ 157
- ЧитГУ 220
- ЮУрГУ 309
Даля 166
Дегтярева 174
Макарова 543
Герцена 123
Гагарина 114
Каразина 305Примеры отношений.
КОРТЕЖИ И ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ. БИНАРНЫЕ ОТНОШЕНИЯ
КОРТЕЖИ И ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ. БИНАРНЫЕ ОТНОШЕНИЯ
В математике для обозначения связи между предметами или понятиями используют термин «отношение».
Понятие «отношение» будем рассматривать в рамках теории множеств.
Определение. | Пусть даны множества Х1, Х2,
… Хn. Кортежем длины n, составленным из элементов этих множеств, называется конечная упорядоченная последовательность этих элементов. , где — называется k-ой координатой. |
Кортежи длины два называют упорядоченными парами, длины три – упорядоченными тройками, длины четыре – упорядоченными четвертками, длины n – упорядоченными n-ками. Кортеж, не содержащий ни одной координаты, называется пустым.
Определение. | Два кортежа равны в том и только
том случае, когда они имеют одинаковую
длину и координаты, стоящие на местах
с одинаковыми номерами, равны. . |
Пример1.
, , .
Таблица 1. Основные отличия понятий кортежа и множества
№ п/п | Отличительные черты | Множества | Кортежи |
1 | Порядок | порядок не играет роли | порядок важен |
2 | Элементы | все элементы различны | элементы могут повторяться |
Определение. | Прямым (или декартовым) произведением двух множеств A и B называется множество упорядоченных пар, таких, что первый элемент каждой пары принадлежит множеству A, а второй – множеству В. . |
Пример2.
Пусть и , тогда
декартово произведение не обладает свойством коммутативности, т.е. . |
Определение. | Бинарным отношением на множества Х называется всякое подмножество декартового произведения . . |
Французский математик и философ
Рене Декарт впервые предложил координатное
представление точек плоскости в своей
работе «Рассуждение о методе, позволяющем
направлять свой разум и отыскивать
истину в науках» в 1637 году («Рассуждение
о методе» известно как источник знаменитой
фразы Je pense, donc je suis –«Я мыслю,
следовательно я существую»).
Это
исторически первый пример прямого
произведения.
Таким образом, бинарное отношение есть множество упорядоченных пар, и если пара x, y принадлежит , то это записывается следующим образом: x, y или, что то же самое, x y.
Рисунок 1. Способы задания бинарного отношения
Определение. | Областью определения бинарного отношения называется множество, состоящее из таких х, для которых x, y . . Областью значения бинарного отношения называется множество, состоящее из таких у, для которых x, y . . Областью задания бинарного отношения называется: . |
Пример3.
Пусть = {1, 3, 3, 3, 4, 2}.
Тогда D = {1, 3, 4}, R = {3, 2}, M = {1, 2, 3, 4}.
Так как бинарные отношения являются множествами, то все операции над множествами справедливы для отношений.
Пример4.
Пусть даны два бинарных отношения:
1 = {1, 2, 2, 3, 3, 4} и 2 = {1, 2, 1, 3, 2, 4}.
Объединение бинарных отношений: 1 2 = {1, 2, 1, 3, 2, 3, 2, 4, 3, 4}.
Пересечение бинарных отношений: 1 2 = {1, 2}.
Разность бинарных отношений: 1\ 2 = {2, 3, 3, 4}.
Определим еще две операции над бинарными отношениями.
Определение. | Отношение называется обратным к отношению , если |
Пример5.
Пусть дано бинарное отношение = {1, 2, 2, 3, 3, 4}.
Тогда –1= {2, 1, 3, 2, 4, 3}.
Определение. | Композицией двух отношений и называется отношение , где — внутреннее бинарное отношение1, — внешнее бинарное отношение. |
Пример6.
Пусть даны бинарные отношения:
и .
Тогда , значит, композиция не обладает свойством коммутативности.
Ознакомимся с основными свойствами бинарных отношений:
Свойства бинарных отношений:
|
Если бинарное отношение обладает свойством эквивалентности, то это дает возможность выделить классы эквивалентности.
Определение. | Классом эквивалентности, порожденным элементом xX, называется множество всех элементов y, для которых xy . |
Бинарные отношения в SET. В карточной игре SET полно… | Эми Лю |
Карточная игра SET полна математического потенциала (см. эту книгу по комбинаторике, вероятности и линейной алгебре в SET, эту статью, показывающую, что SET является NP-полной, и многое другое). Вы также можете использовать карточки SET, чтобы продемонстрировать концепцию отношений эквивалентности и строгих порядков.
Чтобы дать очень краткое изложение SET, игра состоит из карт, содержащих символы со следующими свойствами:
- Номер : каждая карта содержит 1, 2 или 3 символа
- Форма : каждый символ представляет собой овал, ромб или закорючку
- Цвет : каждый символ красный, зеленый или фиолетовый Заполнить : каждый символ пустой, заштрихованный или сплошной
Если разрешить N = {1, 2, 3}, S = {овал, ромб, волнистая линия}, C = {красный, зеленый, фиолетовый} и F = {пустой, заштрихованный, сплошной}, колода всех карт SET D можно определить как декартово произведение этих множеств N × S × C × F .
Затем мы можем использовать эти четыре свойства для определения отношений эквивалентности, которые разбивают D на классы эквивалентности. Например, вы можете сказать, что две карты связаны между собой, если они одного цвета или имеют одинаковую форму и т. д. Более формально вы могли бы написать:
Если вы выберете несколько карт из D , эти отношения будут разбейте эти карточки на небольшие группы так, чтобы каждая карточка находилась ровно в одной группе . В качестве примера вы можете взять следующие девять карт и увидеть два возможных способа их разделения:
Мы также можем определить строгие порядки на основе свойств карт SET. Свойство number является самым простым и работает так же, как традиционный оператор <, где 1 < 2 < 3. Заполнение также не так уж плохо, потому что мы можем сказать, что пусто < заштриховано < сплошно. Для цвета мы можем пойти по порядку радуги или энергии/частоте и сказать, что красный < зеленый < фиолетовый.
Я не могу придумать никакого естественного или «приятного» способа упорядочить фигуры в SET (Предложения?). Я остановился на «остроконечности» в том смысле, что овал < закорючка < ромб.
В SET вы пытаетесь найти группы из трех карт, чтобы все четыре свойства были одинаковыми или разными на трех картах. Например, они должны быть либо одного цвета, либо все разного цвета.
На самом деле вы можете думать об этом правиле в терминах цепей и антицепей.
Возьмите любой действительный НАБОР. Для каждого из отношений строгого порядка, определенных выше, этот SET должен образовывать либо цепочку (если все карты разные для этого свойства), либо антицепочку (если все карты одинаковы для этого свойства).
Некоторые интересные свойства цепей и антицепей, примененные к SET (мы будем рассматривать свойство цвета и соответствующее ему отношение строгого порядка, но те же идеи применимы и к другим отношениям):
- Если l длина наибольшей цепи в D , то можно разбить D на l антицепей. Длина самой длинной цепочки равна 3. Обратите внимание, что мы можем создать цепочку, состоящую из красной карты, зеленой карты и фиолетовой карты, потому что красный < зеленый < фиолетовый. Эта цепочка максимальна, потому что добавление еще одной карты приведет к повторению цвета, чего не может быть, потому что отношение асимметрично. Итак, мы можем разделить D на 3 антицепи — набор красных карт, зеленых карт и фиолетовых карт.
- Любая цепь и антицепь перекрываются не более чем на один элемент. Это имеет смысл, потому что у нас не может быть двух карт одновременно сравнимых (имеющих разный цвет) и несравнимых (имеющих одинаковый цвет).
Длина самой длинной цепочки равна 3. Обратите внимание, что мы можем создать цепочку, состоящую из красной карты, зеленой карты и фиолетовой карты, потому что красный < зеленый < фиолетовый. Эта цепочка максимальна, потому что добавление еще одной карты приведет к повторению цвета, чего не может быть, потому что отношение асимметрично. Итак, мы можем разделить D на 3 антицепи — набор красных карт, зеленых карт и фиолетовых карт.Я надеюсь, что это был интересный и увлекательный способ визуализации и понимания этих математических структур!
Вокруг бинарных отношений на множествах
Теория множеств
Жан-Пьер Меркс Оставить комментарий
Здесь мы рассматриваем бинарные отношения на множестве \(A\).
Напомним, что бинарное отношение \(R\) на \(A\) является подмножеством декартова произведения \(R \subseteq A \times A\). Утверждение \((x,y) \in R\) читается как \(x\) \(R\)-связано с \(y\) и также обозначается \(x R y \).
Некоторые важные свойства бинарного отношения \(R\):
- возвратный
- Для всех \(x \in A\) верно \(x R y\)
- иррефлексивный
- Для всех \(x \in A\) выполняется , а не \(x R y\)
- симметричный
- Для всех \(x,y \in A\) верно, что если \(x R y\), то \(y R x\)
- антисимметричный
- Для всех \(x,y\in A\), если \(x R y\) и \(y R x\), то \(x=y\)
- переходный
- Для всех \(x,y,z \in A\) верно, что если \(x R y\) и \(y R z\), то \(x R z\) 92 \, | \, \vert x – y \vert \le 1\}.\] Другими словами, \(x\) \(R\)-относится к \(y\) тогда и только тогда, когда относительное расстояние между \( x\) и \(y\) меньше \(1\) фута. \(R\) рефлексивен и симметричен, но не транзитивен как \(\vert 1 – 0 \vert \le 1\), \(\vert 2 – 1 \vert \le 1\), но \(\vert 2 – 0 \верт > 1\).
Отношение, которое является рефлексивным, антисимметричным и транзитивным, называется частичным порядком r. Давайте посмотрим, что рефлексивность, антисимметричность и транзитивность являются независимыми свойствами. 92 \, | \, x \le y \text{ и } \vert x-y \vert \le 1\}.\] \(R\) является рефлексивным и антисимметричным, поскольку \(\le\) является частичным порядком \(\mathbb R \). \(R\) не является транзитивным как \(0 R 1\) и \(1 R 2\), а \(0 R 2\) не выполняется.
Антисимметричный и транзитивный, но не рефлексивный
Определим на \(\mathbb N\) бинарное отношение \(R\) следующим образом: \(a R b \) тогда и только тогда, когда \(a\) четно и делит \(b\) . Если \(a R b\) и \(b R a\), \(a\) и \(b\) оба четны, а поскольку отношение делимости антисимметрично, \(R\) также антисимметрично. Для \(a,b,c\in\mathbbN\), если выполняются \(aRb\) и \(bRc\), \(a,b\) четны и \(a\) делит \ (c\) по транзитивности отношения делимости. Отсюда \(a Rc\), что доказывает транзитивность \(R\).
