Бинарное отношение на множестве примеры с решением. Бинарное отношение

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

1) рефлексивность;

2)симметричность;

3)транзитивность.

4)связанность.

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

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

Существуют отношения, не обладающие свойством рефлексивности, например, отношение перпендикулярности отрезков: ab, ba (нет ни одного отрезка, о котором можно сказать, что он перпендикулярен самому себе). Поэтому на графе данного отношения нет ни одной петли.

Не обладает свойством рефлексивности и отношение «длиннее» для отрезков, «больше на 2» для натуральных чисел и др.

Отношение R на множестве Х называется антирефлексивным , если для любого элемента из множества Х всегда ложно х Rх: .

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

Отношение R на множестве Х называется симметричным , если выполняется условие: из того, что элемент х находится в отношении с элементом y , следует, что и элемент y находится в отношении R с элементом х: xRyyRx .

Граф симметричного отношения обладает следующей особенностью: вместе с каждой стрелкой, идущей от х к y , граф содержит стрелку, идущую от y к х (рис. 35).

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

Существуют отношения, которые не обладают свойством симметричности.

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

Отношение R называют антисимметричным , если для любых элементов х и y из истинности xRy следует ложность yRx: : xRyyRx.

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

Существуют отношения, которые не обладают ни свойством симметричности, ни свойством антисимметричности.

Отношение R на множестве Х называют транзитивным, если из того, что элемент х находится в отношении R с элементом y, а элемент y находится в отношении R с элементом z , следует, что элемент х находится в отношении R с элементом z : xRy и yRz xRz.

Граф транзитивного отношения с каждой парой стрелок, идущих от х к y и от y к z , содержит стрелку, идущую от х к z.

Свойством транзитивности обладает и отношение «длиннее» на множестве отрезков: если отрезок а длиннее отрезка b , отрезок b длиннее отрезка с , то отрезок а длиннее отрезка с. Отношение «равенства» на множестве отрезков также обладает свойством транзитивности: (а= b, b=с)(а=с).

Существуют отношения, которые не обладают свойством транзитивности. Таким отношением является, например, отношение перпендикулярности: если отрезок а перпендикулярен отрезку b , а отрезок b перпендикулярен отрезку с , то отрезки а и с не перпендикулярны!

Существует еще одно свойство отношений, которое называется свойством связанности, а отношение, обладающее им, называют связанным.

Отношение R на множестве Х называется связанным, если для любых элементов х и y из данного множества выполняется условие: если х и y различны, то либо х находится в отношении R с элементом y , либо элемент y находится в отношении R с элементом х . С помощью символов это можно записать так: xy xRy или yRx.

Например, свойством связанности обладает отношение «больше» для натуральных чисел: для любых различных чисел х и y можно утверждать, либо x>y , либо y>x.

На графе связанного отношения любые две вершины соединены стрелкой. Справедливо и обратное утверждение.

Существуют отношения, которые не обладают свойством связанности. Таким отношением, например, является отношение делимости на множестве натуральных чисел: можно назвать такие числа х и y , что ни число х не является делителем числа y , ни число y не является делителем числа х (числа 17 и 11 , 3 и 10 и т.д.).

Рассмотрим несколько примеров. На множестве Х={1, 2, 4, 8, 12} задано отношение «число х кратно числу y ». Построим граф данного отношения и сформулируем его свойства.

Про отношение равенства дробей говорят, оно является отношением эквивалентности.

Отношение R на множестве Х называется отношением эквивалентности, если оно одновременно обладает свойством рефлексивности, симметричности и транзитивности.

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

В рассмотренном выше отношении «равенства дробей», множество Х разбилось на три подмножества: {; ; }, {; }, {}. Эти подмножества не пересекаются, а их объединение совпадает с множеством Х , т.е. имеем разбиение множества на классы.

Итак, если на множестве Х задано отношение эквивалентности, то оно порождает разбиение этого множества на попарно непересекающиеся подмножества - классы эквивалентности.

Так, мы установили, что отношению равенства на множестве
Х ={ ;; ; ; ; } соответствует разбиение этого множества на классы эквивалентности, каждый из которых состоит из равных между собой дробей.

Принцип разбиения множества на классы при помощи некоторого отношения эквивалентности является важным принципом математики. Почему?

Во-первых, эквивалентный - это значит равносильный, взаимозаменяемый. Поэтому элементы одного класса эквивалентности взаимозаменяемы. Так, дроби, оказавшиеся в одном классе эквивалентности {; ; }, неразличимы с точки зрения отношения равенства, и дробь может быть заменена другой, например . И эта замена не изменит результата вычислений.

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

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

Другим важным видом отношений являются отношения порядка. Рассмотрим задачу.На множестве Х ={3, 4, 5, 6, 7, 8, 9, 10 } задано отношение «иметь один и тот же остаток при делении на 3 ». Это отношение порождает разбиение множества Х на классы: в один попадут все числа, при делении которых на 3 получается в остатке 0 (это числа 3, 6, 9 ). Во второй - числа, при делении которых на 3 в остатке получается 1 (это числа 4, 7, 10 ). В третий попадут все числа, при делении которых на 3 в остатке получается 2 (это числа 5, 8 ). Действительно, полученные множества не пересекаются и их объединение совпадает с множеством Х . Следовательно, отношение «иметь один и тот же остаток при делении на 3 », заданное на множестве Х , является отношением эквивалентности.

Возьмем еще пример: множество учащихся класса можно упорядочить по росту или возрасту. Заметим, что это отношение обладает свойствами антисимметричности и транзитивности. Или всем известен порядок следования букв в алфавите. Его обеспечивает отношение «следует».

Отношение R на множестве Х называется отношением строгого порядка , если оно одновременно обладает свойствами антисимметричности и транзитивности. Например, отношение «х< y ».

Если же отношение обладает свойствами рефлексивности, антисимметричности и транзитивности, то такое оно будет являться отношением нестрогого порядка . Например, отношение «х y ».

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

Множество Х называется упорядоченным, если на нем задано отношение порядка.

Например, множество Х= {2, 8, 12, 32 } можно упорядочить при помощи отношения «меньше» (рис. 41), а можно это сделать при помощи отношения «кратно» (рис. 42). Но, являясь отношением порядка, отношения «меньше» и «кратно» упорядочивают множество натуральных чисел по-разному. Отношение «меньше» позволяет сравнивать два любых числа из множества Х , а отношение «кратно» таким свойством не обладает. Так, пара чисел 8 и 12 отношением «кратно» не связана: нельзя сказать, что 8 кратно 12 либо 12 кратно 8.

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

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

Унарные (одноместные) отношения отражают наличие какого-то одного признака R у элементов множества M (например, «быть красным» на множестве шаров в урне).

Бинарные (двуместные) отношения используются для определения взаимо

связей, которыми характеризуются пары элементов во множестве M .

Например, на множестве людей могут быть заданы следующие отношения: «жить в одном городе», «x работает под руководством y », «быть сыном», «быть старше» и т.д. на множестве чисел: «число a больше числа b », «число a является делителем числа b », «числа a и b дают одинаковый остаток при делении на 3».

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

Отношения между двумя объектами являются предметом исследования экономики, географии, биологии, физики, лингвистики, математики и других наук.

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

Бинарным отношением между множествами A и B называется подмножество R прямого произведения . В том случае, когда можно просто говорить об отношении R на A .

Пример 1 . Выпишите упорядоченные пары, принадлежащие бинарным отношениям R 1 и R 2 , заданными на множествах A и : , . Подмножество R 1 состоит из пар: . Подмножество .

Область определения R на есть множество всех элементов из A таких, что для некоторых элементов имеем . Иными словами область определения R есть множество всех первых координат упорядоченных пар из R .

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

В примере 1 для R 1 область определения: , множество значений - . Для R 2 область определения: , множество значений: .

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

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

Пример 5 . Пусть , .

Пусть R 1 задано на перечислением упорядоченных пар: . Бинарное отношение R 2 на множестве задано с помощью правила: упорядочена пара , если a делится на b . Тогда R 2 состоит из пар: .

Бинарные отношения, из примера 2, R 1 и R 2 изображены графически на рис. 6 и рис.7.

Рис. 6 Рис. 7

Чтобы изобразить бинарное отношение с помощью стрелок, слева изображаются точками элементы множества A , справа - множества B . Для каждой пары (a, b) , содержащейся в бинарном отношении R , проводится стрелка от a к b , . Графическое изображение бинарного отношения R 1 , приведенного в примере 6, показано на рис.8.

Рис.8

Бинарные отношения на конечных множествах могут быть заданы матрицами. Предположим, что задано бинарное отношение R между множествами A и B . , .

Строки матрицы нумеруются элементами множества A , а столбцы – элементами множества B . Ячейку матрицы, стоящую на пересечении i - ой строки и j - ого столбца принято обозначать через C ij , а заполняется она следующим образом:

Полученная матрица будет иметь размер .

Пример 6. Пусть задано множество . На множестве задайте списком и матрицей отношение R – «быть строго меньше».

Отношение R как множество содержит все пары элементов (a , b) из M такие, что .

Матрица отношения, построенная по вышеуказанным правилам, имеет следующий вид:

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

1. Бинарное отношение R на множестве называетсярефлексивным , если для любого элемента a из M пара (a, a) принадлежит R , т.е. имеет место для любого a из M :

Отношения «жить в одном городе», «учиться в одном вузе», «быть не больше» являются рефлексивными.

2. Бинарное отношение называется антирефлексивным ,если оно не обладает свойством рефлексивности для любых a :

Например, «быть больше», «быть младше» - это антирефлексивные отношения .

3. Бинарное отношение R называется симметричным , если для любых элементов a и b из M из того, что пара (a, b) принадлежит R , , вытекает, что пара (b, a) принадлежит R , т.е.

Симметрична параллельность прямых, т.к. если // , то // . Симметрично отношение «быть равным» на любом множестве или «быть взаимнопростым на N».

Отношение R симметрично тогда и только тогда, когда R=R -1

4. Если для несовпадающих элементов верно отношение , но ложно , то отношение антисимметрично . Можно сказать иначе:

Антисимметричными являются отношения «быть больше», «быть делителем на N», «быть младше».

5. Бинарное отношение R называется транзитивным , если для любых трех элементов из того, что пары (a, b) и (b, c) принадлежат R , следует, что пара (a, c) принадлежит R :

Транзитивны отношения : «быть больше», «быть параллельным», «быть равным» и др.

6. Бинарное отношение R антитранзитивно , если оно не обладает свойством транзитивности.

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

Т.к. бинарное отношение может быть задано не только прямым перечислением пар, но и матрицей, то целесообразно выяснить, какими признаками характеризуется матрица отношения R , если оно: 1) рефлексивно, 2) антирефлексивно, 3)симметрично, 4) антисимметрично, 5) транзитивно.

Пусть R задано на , .R либо выполняется в обе стороны, либо не выполняется вообще. Таким образом, если в матрице стоит единица на пересечении i - ой строки и j - ого столбца, т.е. C ij =1, то она должна стоять и на пересечении j - ой строки и i - ого столбца, т.е. C ji =1, и наоборот, если C ji =1, то C ij =1. Таким образом, матрица симметричного отношения симметрична относительно главной диагонали.

4. R антисимметрично, если из и следует: . Это означает, что в соответствующей матрице ни для каких i , j не выполняется C ij = C ji =1. Таким образом, в матрице антисимметричного отношения отсутствуют единицы, симметричные относительно главной диагонали .

5. Бинарное отношение R на непустом множестве A называется транзитивным если

Вышеприведенное условие должно выполняться для любых элементов матрицы. И, наоборот, если в матрице R имеется хотя бы один элемент C ij =1, для которого данное условие не выполняется, то R не транзитивно.

Основы дискретной математики.

Понятие множества. Отношение между множествами.

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

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

· Должно существовать правило, по которому моно определить принадлежит ли элемент к данной совокупности.

· Должно существовать правило, по которому элементы можно отличить друг от друга.

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

· Перечисление элементов множества. - для конечных множеств.

· Указание характеристического свойства .

Пустым множеством – называется множество, не содержащее ни одного элемента (Ø).

Два множества называются равными, если они состоят из одних и тех же элементов. , A=B

Множество B называется подмножеством множества А ( , тогда и только тогда когда все элементы множества B принадлежат множеству A .

Например: , B =>

Свойство:

Примечание: обычно рассматривают подмножество одного и того е множества, которое называется универсальным (u). Универсальное множество содержит все элементы.

Операции над множествами.

A

B

1. Объединением 2-х множеств А и В называется такое множество, которому принадлежат элементы множества А или множества В (элементы хотя бы одного из множеств).

2.Пересечением 2-х множеств называется новое множество, состоящее из элементов, одновременно принадлежат и первому и второму множеству.

Н-р: , ,

Свойство: операции объединения и пересечения.

· Коммутативность.

· Ассоциативность. ;

· Дистрибутивный. ;

U

4.Дополнение . Если А – подмножество универсального множества U , то дополнением множества А до множества U (обозначается ) называется множество состоящее из тех элементов множества U , которые не принадлежат множеству А .

Бинарные отношения и их свойства.

Пусть А и В это множества производной природы, рассмотрим упорядоченную пару элементов (а, в) а ϵ А, в ϵ В можно рассматривать упорядоченные «энки».

(а 1 , а 2 , а 3 ,…а n) , где а 1 ϵ А 1 ; а 2 ϵ А 2 ; …; а n ϵ А n ;

Декартовым (прямым) произведением множеств А 1 , А 2 , …, А n , называется мн-во, которое состоит из упорядоченных n k вида .

Н-р: М = {1,2,3}

М× М= М 2 = {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.

Подмножества декартова произведения называется отношением степени n или энарным отношением. Если n =2, то рассматривают бинарные отношения. При чем говорят, что а 1 , а 2 находятся в бинарном отношении R , когда а 1 R а 2.

Бинарным отношением на множестве M называется подмножество прямого произведения множества n самого на себя.

М× М= М 2 = {(a, b )| a, b ϵ M } в предыдущем примере отношение меньше на множестве М порождает следующее множество: {(1,2);(1,3); (2,3)}

Бинарные отношения обладают различными свойствами в том числе:

· Рефлексивность: .

· Антирефлексивность (иррефлексивность): .

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

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

· Транзитивность: .

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

Виды отношений.

· Отношение эквивалентности;

· Отношение порядка.

v Рефлексивное транзитивное отношение называется отношением квазипорядка.

v Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.

v Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.

v Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.

Связанные определения

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

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

Виды отношений

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

Виды двухместных отношений

• Обратное отношение [уточнить ] (отношение, обратное к R) - это двухместное отношение, состоящее из пар элементов (у, х), полученных перестановкой пар элементов (х, у) данного отношения R. Обозначается: R −1 . Для данного отношения и обратного ему верно равенство: (R −1) −1 = R.
• Взаимо-обратные отношения (взаимообратные отношения) - отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого - областью значений другого.
• Рефлексивное отношение - двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого х этого множества элемент х на­ходится в отношении R к самому себе, то есть для любого элемента х этого множества имеет место xRx. Примеры рефлексивных отношений: равенство , одновременность , сходство.
• Антирефлексивное отношение (Иррефлексивное отношение, отметим, что также как антисимметричность не совпадает с несимметричностью иррефлексивность не совпадает с нерефлексивностью.) - двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого элемента х этого множества неверно, что оно находится в отношении R к самому себе (неверно, что xRx), то есть возможен случай, что элемент множества не находится в отно­шении R к самому себе. Примеры нерефлексвных отношений: «заботиться о», «развлекать», «нервировать».
• Транзитивное отношение - двухместное отношение R, оп­ределенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz следует xRz (xRy&yRzxRz). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
• Нетранзитивное отношение [уточнить ] - двухместное отношение R, оп­ределенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz ((xRy&yRzxRz)). Пример нетранзитивного отношения: «x отец y»
• Симметричное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых элементов х и у этого множества из того, что х находится к у в отношении R (xRy), следует, что и у находится в том же отношении к х (уRx). Примером симметричных отношений могут быть равенство (=), отношение эквивалентности , подобия , одновременности, некоторые отношения родства (например, отношение братства).
• Антисимметричное отношение - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy и xR −1 y следует х = у (то есть R и R −1 выполняются одновременно лишь для равных между собой членов).
• Асимметричное отношение [уточнить ] - двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy следует yRx. Пример: отношение «больше» (>) и «меньше» (<).
• Отношение эквивалентности (отношение тождества [уточнить ] , отношение типа равенства) - двухместное отношение R между предметами х и у в предметной области D, удовлетворяющее следующим аксиомам (условиям): Таким образом, отношение типа равенства является одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, обмениваемость товаров на рынке, подобие , одновременность . Пример отношения, которое удовлетворяет аксиоме (3), но не удовлетворяет аксиомам (1) и (2): «больше».
• Отношения порядка - отношения, обладающие только некоторыми из трёх свойств отношения эквивалентности. В частности, отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует «нестрогий» порядок. Отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») - «строгий» порядок.
• Функция - двухместное отношение R , определенное на некотором мно­жестве, отличающееся тем, что каждому значению x отно­шения xRy y . Пример: «y отец x ». Свойство функциональности отно­шения R записывается в виде аксиомы: (xRy и xRz )→(y ≡z ). Поскольку каждому значению x в выражениях xRy и xRz соответствует одно и то же значение, то y и z совпадут, окажутся одними и теми же. Функциональное отношение однозначно, поскольку каждому значению x отношения xRy соответствует лишь одно-единственное значение y , но не наоборот.
• Биекция (одно-однозначное отношение) - двухместное отношение R , определенное на некотором мно­жестве, отличающееся тем, что в нём каждому значению х соответствует единственное значение у , и каждому значению у соответствует единственное значение х . Одно-однозначное отношение является частным случаем однозначного отношения.
• Связанное отношение - это двухместное отношение R , определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов х и у из этого множества, одно из них находится в отношении R к другому (то есть выполнено одно из двух соотношений: xRy или yRx ). Пример: отношение «меньше» (<).

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

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

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

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

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

Если , то обратным отношением называется отношение , определённое на паре , и состоящее из тех пар , для которых . Например, .

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

Если , и , то произведение отношений не определено. Если же отношения рассматривать определённые на каком-то множестве , то такой ситуации не возникает.

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

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

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

Отметим, что аналоги последних двух тождеств для не имеют места.

Некоторые свойства отношения можно определить, используя операции над отношениями:

См. также

Литература

• А. И. Мальцев. Алгебраические системы. - М .: Наука, 1970.

Wikimedia Foundation . 2010 .

- двуместный предикат на заданном множестве. Под Б. о. иногда понимают подмножество множества упорядоченных пар (а, 6) элементов заданного множества А. Б. о. частный случай отношения. Пусть. Если, то говорят, что элемент находится в бинарном… … Математическая энциклопедия

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

отношение - ОТНОШЕНИЕ множество упорядоченных п ок индивидов (где п > 1), т.е. двоек, троек и т.д. Число п называется «местностью», или «арностью», О. и, соответственно, говорят о n местном (п арном) О. Так, например, двуместное О. называют… … Энциклопедия эпистемологии и философии науки

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

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

У этого термина существуют и другие значения, см. Отношение. Отношение в логике первого порядка двух и более аргументный предикат (многоместный предикат), двух и более предикатное свойство. Знак отношения: R.[уточнить] В терминах отношений… … Википедия, А. И. Широков. Пособие представляет собой седьмую часть раздела «Основные теоретико-множественные конструкции» учебной дисциплины «Дискретная математика». В нем вводится в рассмотрение и анализируется такое… электронная книга

Язык T-SQL в SQL Server базируется на стандартном языке SQL, основанном на реляционной модели, которая, в свою очередь, базируется на математических основаниях, таких как теория множеств и логика предикатов. В данной статье рассматривается фундаментальная тема из теории множеств: свойства отношений на множествах. Предлагаемые коды T-SQL читатели смогут использовать для проверки наличия определенных свойств тех или иных отношений. Но можно еще попробовать написать собственные версии сценариев (чтобы определить, обладает ли отношение конкретным свойством), прежде чем применять описанные в статье решения.

Множества и отношения

Георг Кантор, создатель теории множеств, определяет множество как «объединение в некое целое M совокупности определенных хорошо различимых объектов m нашего созерцания или мышления (которые будут называться элементами множества M)». Элементами множества могут быть объекты произвольной природы: люди, цифры и даже сами множества. Символы ∈ и ∉ обозначают, соответственно операторы, отражающие принадлежность (вхождение, членство) и непринадлежность элемента множеству. Так, запись x ∈ V означает, что x является элементом множества V, а запись x ∉ V - что x не является элементом V.

Бинарным отношением на множестве называется множество упорядоченных пар элементов исходного множества. Так, для множества элементов V = {a, b, c}, бинарным отношением R на данном множестве V будет произвольное подмножество множества всех упорядоченных пар декартова произведения V × V = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}. Отношение R = {(a, b), (b, c), (a, c)} является допустимым бинарным отношением на V. Можно сказать, что a соотносится с b посредством R. Предположим, что R = {(a, b), (b, c), (c, d)}. Такое R не является допустимым отношением на V, поскольку пара (c, d) не принадлежит декартову произведению V × V. Заметим, что порядок указания элементов, входящих во множество, не важен. Множество V может быть задано как {a, b, c} или как {b, a, c} и так далее. Однако порядок в упорядоченных парах, например в (a, b) бинарного отношения, важен; таким образом (a, b) ≠ (b, a).

В качестве более реального примера бинарного отношения рассмотрим множество F членов семьи: {Ицик, Микки, Инна, Мила, Габи}. Микки - брат-близнец Ицика, Инна - его старшая сестра, Мила - мама, а Габи - отец. Примером отношения R на множестве F будет: «является братом». Элементы этого отношения суть {(Ицик, Микки), (Микки, Ицик), (Ицик, Инна), (Микки, Инна)}. Отмечаем, что упорядоченная пара (Ицик, Инна) появляется в R, а пара (Инна, Ицик) - нет. Хотя Ицик - брат Инны, она ему братом не приходится.

Свойства отношений на множествах

Теперь, когда мы освежили наши представления о множествах и отношениях, приступим к теме статьи - свойствам отношений на множествах. В качестве данных для примера обратимся к кодам листинга 1, чтобы создать таблицы V и R. V будет представлять множество, а R - бинарное отношение на нем. Используйте код листинга 2 для создания процедуры ClearTables, с помощью которой сможете очистить от записей обе эти таблицы перед их заполнением новыми образцами данных. Наконец, используйте коды листингов 3, 4 и 5 для наполнения таблиц V и R различными наборами данных для тестирования (будем их называть примерами данных 1, 2 и 3 соответственно).

Рефлексивность. Отношение R на множестве V является рефлексивным, если для любого элемента v множества V, v ∈ V, следует, что (v, v) ∈ R, то есть пара (v, v) всегда принадлежит R. А отношение R на V не рефлексивно, если найдется такой элемент v ∈ V, что пара (v, v) ∉ R. Вновь рассмотрим пример множества F - членов моей семьи.

Отношение «иметь одинаковый возраст с» на F, очевидным образом, рефлексивно. Элементами отношения будут следующие пары: {(Ицик, Ицик), (Ицик, Микки), (Микки, Микки), (Микки, Ицик), (Инна, Инна), (Мила, Мила), (Габи, Габи)}.

Приступим к написанию T-SQL запроса к таблицам V и R (представляющим множество и отношение на этом множестве), проверяющего, обладает ли R свойством рефлексивности:

SELECT
CASE
WHEN EXISTS
(SELECT v, v FROM dbo.V
EXCEPT
SELECT r1, r2 FROM dbo.R)
THEN "Нет"
ELSE "Да",
END AS reflexive

Первый подзапрос в операции EXCEPT возвращает набор всех упорядоченных пар (v, v) для всех строк таблицы V. Второй подзапрос возвращает набор упорядоченных пар (r1, r2) - всех строк таблицы R. Операция EXCEPT, таким образом, вернет все упорядоченные пары, встречающиеся в первом и отсутствующие во втором наборе. Предикат EXISTS нужен для проверки существования хотя бы одной записи в результирующем наборе. Если найдется хотя бы одна такая запись, то выражение CASE возвратит нам «Нет» (нет рефлексивности), но и «Да» - в противном случае (есть рефлексивность).

Взгляните на три примера наборов данных в листингах 3, 4 и 5 и попытайтесь определить без запуска запроса, в каких из них отношение будет рефлексивным. Ответы даются далее в тексте статьи.

Иррефлексивнось. Отношение R на множестве V называется иррефлексивным (не путать с нерефлексивностью), если для каждого элемента v ∈ V следует, что (v, v) ∉ R. Отношение не иррефлексивно, если найдется элемент v ∈ V, для которого (v, v) ∈ R. Примером иррефлексивного отношения на множестве F членов моей семьи служит отношение «быть родителем», так как никакой человек не может быть родителем самому себе. Членами этого отношения на F будут следующие пары: {(Мила, Ицик), (Мила, Микки), (Мила, Инна), (Габи, Ицик), (Габи, Микки), (Габи, Инна)}.

Следующий запрос является проверочным - будет ли отношение R на V иррефлексивным:

SELECT
CASE
WHEN EXISTS
(SELECT * FROM dbo.R
WHERE r1 = r2)
THEN "Нет"
ELSE "Да"
END AS irreflexive

Внешние ключи в определении таблицы R были введены для обеспечения того, что лишь элементы V смогут составить атрибуты r1 и r2 записи R. Таким образом, остается только проверить, нет ли в R записей с совпадающими атрибутами r1 и r2. Если такая запись найдется, отношение R не иррефлексивно, если записи нет, оно иррефлексивно.

Симметричность. Отношение R на множестве V называется симметричным, если вместе с (r1, r2) ∈ R всегда выполняется и (r2, r1) ∈ R. Отношение не симметрично, если найдется некоторая пара (r1, r2) ∈ R, для которой (r2, r1) ∉ R. На множестве F членов семьи Бен-Ган отношение «является братом или сестрой (is a sibling of)» будет примером симметричного отношения. Парами этого отношения будут следующие наборы: {(Ицик, Микки), (Ицик, Инна), (Микки, Ицик), (Микки, Инна), (Инна, Ицик), (Инна, Микки)}.

Следующий запрос является проверочным - будет ли отношение R на V симметричным:

SELECT
CASE
WHEN EXISTS
(SELECT r1, r2 FROM dbo.R
EXCEPT
SELECT r2, r1 FROM dbo.R)
THEN "Нет"
ELSE "Да"
END AS symmetric

Код запроса использует операцию EXCEPT. Первый подзапрос операции EXCEPT возвращает набор упорядоченных пар (r1, r2) - записей таблицы R, а второй - набор упорядоченных пар (r2, r1) по каждой записи R. Если отношение R на множестве V не симметрично, то операция EXCEPT вернет непустой результирующий набор, а предикат EXISTS, соответственно, значение TRUE и, наконец, выражение CASE вернет «Нет».

Если отношение симметрично, то выражение CASE даст «Да».

Асимметричность. Отношение R на множестве V асимметрично (не следует путать это свойство с несимметричностью), если для каждого набора (r1, r2) ∈ R, в котором r1 ≠ r2, справедливо, что (r2, r1) ∉ R. Примером асимметричного отношения на множестве F членов семьи автора будет отношение «являться родителем», которое было описано выше. В качестве упражнения постарайтесь придумать пример отношения на непустом множестве, которое одновременно является симметричным и асимметричным. Проверьте пример данных в этой статье в качестве решения.

SELECT
CASE
WHEN EXISTS
(SELECT r1, r2 FROM dbo.R WHERE r1 r2
INTERSECT
SELECT r2, r1 FROM dbo.R WHERE r1 r2)
THEN "Нет"
ELSE "Да"
END AS asymmetric

В коде используется операция INTERSECT. Первый подзапрос в этой операции возвращает упорядоченную пару (r1, r2) для каждой записи таблицы R, в которой r1 r2.

Второй подзапрос операции INTERSECT возвращает упорядоченную пару (r2, r1) для каждой записи таблицы R, в которой r1 r2. Если в результирующий набор (результат пересечения этих множеств) входит хотя бы одна запись, это будет означать, что R не асимметрично; в противном случае R асимметрично.

Транзитивность. Отношение R на множестве V является транзитивным, если из включений (a, b) ∈ R и (b, c) ∈ R, всегда вытекает, что и (a, c) ∈ R. Примером транзитивного отношения на множестве членов семьи F будет отношение «является братом или сестрой», которое было рассмотрено выше.

Приведенный ниже код проверяет транзитивность отношения R:

SELECT
CASE
WHEN EXISTS
(SELECT *
FROM dbo.R AS RA
INNER JOIN dbo.R AS RB
ON RA.r2 = RB.r1
LEFT OUTER JOIN dbo.R AS RC
ON RA.r1 = RC.r1 AND RB.r2 = RC.r2
WHERE RC.r1 IS NULL)
THEN "Нет"
ELSE "Да"
END AS transitive

В коде, во‑первых, используется внутренняя связь (inner join) между двумя экземплярами R, для того чтобы отбирать лишь те строки, в которых r2 в первом экземпляре совпадает с r1 на втором экземпляре. Во‑вторых, в коде применяется левая внешняя связь (left outer join) с третьим экземпляром таблицы R, в соответствии с которой r1 первого экземпляра R совпадает с r1 третьего экземпляра, а r2 второго экземпляра совпадает с r2 третьего. Если существует хотя бы одна результирующая строка во внутреннем подзапросе (условие отбора для третьего экземпляра: r1 есть Null), это означает, что отношение не транзитивно; в противном случае отношение R транзитивно.

Отношение эквивалентности. Отно­ше­нием эквивалентности является такое отношение, которое одновременно обладает свойствами рефлексивности, симметричности и транзитивности. Можно использовать запросы, предложенные выше для раздельной проверки наличия каждого свойства: если отношение обладает всеми тремя, то следует заключить, что имеет место отношение эквивалентности. Кроме того, вы можете использовать коды листинга 6 для проверки всех свойств отношения R на множестве V, которые ранее обсуждались в статье, в том числе проверку свойства быть отношением эквивалентности. Если провести прогонку листинга 6 для примеров данных 1, 2 и 3 (полученных на основе листингов 3, 4 и 5 соответственно), то получатся результаты, приведенные в таблицах 1, 2 и 3 соответственно.

Возвращаясь к основам T-SQL

Таким образом, мы рассмотрели фундаментальную тему из математической теории множеств: свойства отношений на множествах. Я предложил проверочные коды T-SQL для контроля свойств некоторого отношения, представленного таблицей R (упорядоченных пар элементов), на множестве элементов, представленных таблицей V.

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

Ицик Бен-Ган ([email protected]) - преподаватель и консультант, автор книг по T-SQL, имеет звание SQL Server MVP