Отношение r. Бинарные отношения, функции, порядок

Лекция 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ÍA 2), то говорят, что r есть отношение на множестве A.

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

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

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

Пример 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)}. В данном примере D t={3; 5; 7} и R t= B ={2; 4; 6}.

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

Пример 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 ={a 1, a 2, …, an } и B ={b 1, b 2, …, 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) соответствующий ориентированный граф показан на рисунке.

https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,

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

,

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

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

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

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

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

. ,

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

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

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

rÍA 1´…´An ={(a 1, …, an )| a 1ÎA 1Ù … Ù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.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ÍA 2, которое имеет вид: 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?

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

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

	(a , b )Îr	(b , c )Îr	(a , c )	(a , c )Îr?

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

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

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

.

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

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

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

.

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

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

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

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

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

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

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

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

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

это отношение рефлексивно, т. к. для "x ΢ имеем x -x =0, и, следовательно, оно делится на m ;

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

это отношение транзитивно, т. к. если (x -y ) делится на m , то для некоторого целого t 1 имеем https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, отсюда , т. е. (x -z ) делится на m .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Рефлексивное транзитивное отношение называется отношением квазипорядка.
• Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности .
• Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка .
• Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка .
• Полное антисимметричное (для любых 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.[уточнить] В терминах отношений… … Википедия, А. И. Широков. Пособие представляет собой седьмую часть раздела «Основные теоретико-множественные конструкции» учебной дисциплины «Дискретная математика». В нем вводится в рассмотрение и анализируется такое… электронная книга

Определения

1. Бинарным отношением между элементами множеств А и В называется любое подмножество декартова произведения RÍA´B, RÍA´А.

2. Если А=В , то R – это бинарное отношение на A .

3. Обозначение: (x, y)ÎR Û xRy.

4. Область определения бинарного отношения R – это множество d R = {x : существует y такое, что (x, y)ÎR }.

5. Область значений бинарного отношения R – это множество r R = {y : существует x такое, что (x, y)ÎR }.

6. Дополнение бинарного отношения R между элементами А и В – это множество -R = (A´B) \ R .

7. Обратное отношение для бинарного отношенияR – это множество R -1 = {(y, x) : (x, y)ÎR} .

8. Произведение отношений R 1 ÍA´B и R 2 ÍB´C – это отношение R 1 × R 2 = {(x, y) : существует zÎB такое, что (x, z)ÎR 1 и (z, y)ÎR 2 }.

9. Отношение f называется функцией из А в В , если выполняется два условия:

а) d f = А , r f Í В

б) для всех x ,y 1 ,y 2 из того, что (x, y 1)Îf и (x, y 2)Îf следует y 1 =y 2 .

10. Отношение f называется функцией из А на В , если в первом пункте будет выполняться d f = А , r f = В .

11. Обозначение: (x, y)Îf Û y = f(x) .

12. Тождественная функция i A: A®A определяется так: i A (x) = x .

13. Функция f называется 1-1-функцией , если для любых x 1 , x 2 , y из того, что y = f(x 1) и y = f(x 2) следует x 1 =x 2 .

14. Функция f: A®B осуществляет взаимно однозначное соответствие между А и В , если d f = А , r f = В и f является 1-1-функцией.

15. Свойства бинарного отношения R на множестве А :

- рефлексивность: (x, x)ÎR для всех xÎA .

- иррефлексивность: (x, x)ÏR для всех xÎA .

- симметричность: (x, y)ÎR Þ (y, x)ÎR .

- антисимметричность: (x, y)ÎR и (y, x)ÎR Þ x=y .

- транзитивность: (x, y)ÎR и (y, z)ÎR Þ (x, z)ÎR .

- дихотомия: либо (x, y)ÎR , либо(y, x)ÎR для всехxÎA иyÎA .

16. Множества А 1 , A 2 , ..., А r из Р(А) образуют разбиение множества А , если

- А i ¹ Æ , i = 1 , ..., r ,

- A = A 1 ÈA 2 È...ÈA r ,

- A i ÇA j = Æ , i ¹ j .

ПодмножестваА i , i = 1 , ..., r , называются блоками разбиения .

17. Эквивалентность на множестве А – это рефлексивное, транзитивное и симметричное отношение на А .

18. Класс эквивалентности элемента x по эквивалентности R – это множество [x] R ={y: (x, y)ÎR} .

19. Фактор множество A поR – это множество классов эквивалентности элементов множества А . Обозначение: A/R .

20. Классы эквивалентности (элементы фактор множества А/R ) образуют разбиение множества А. Обратно. Любому разбиению множества А соответствует отношение эквивалентности R , классы эквивалентности которого совпадают с блоками указанного разбиения. По-другому. Каждый элемент множества А попадает в некоторый класс эквивалентности из A/R . Классы эквивалентности либо не пересекаются, либо совпадают.

21. Предпорядок на множестве A – это рефлексивное и транзитивное отношение на А .

22. Частичный порядок на множестве A – это рефлексивное, транзитивное и антисимметричное отношение на А .

23. Линейный порядок на множестве A – это рефлексивное, транзитивное и антисимметричное отношение на А, удовлетворяющее свойству дихотомии.

Пример 1.

Пусть A={1 , 2 , 3} , B={a , b} . Выпишем декартово произведение: A´B = { (1 , a) , (1 , b) , (2 , a) , (2 , b) , (3 , a) , (3 , b) } . Возьмём любое подмножество этого декартова произведения: R = { (1 , a) , (1 , b) , (2 , b) } . Тогда R – это бинарное отношение на множествах A и B .

Будет ли это отношение являться функцией? Проверим выполнение двух условий 9a) и 9б). Область определения отношения R – это множество d R = {1, 2} ¹ {1, 2, 3} , то есть первое условие не выполняется, поэтому в R нужно добавить одну из пар: (3 , a) или (3 , b) . Если добавить обе пары, то не будет выполняться второе условие, так как a¹b . По этой же причине из R нужно выбросить одну из пар: (1 , a) или (1 , b) . Таким образом, отношение R¢ = { (1 , a) , (2 , b) , (3 , b) } является функцией. Заметим, что R¢ не является 1-1 функцией.

На заданных множествах A и В функциями также будут являться следующие отношения: { (1 , a) , (2 , a) , (3 , a) } , { (1 , a) , (2 , a) , (3 , b) } , { (1 , b) , (2 , b) , (3 , b) } и т.д.

Пример 2.

Пусть A={1 , 2 , 3} . Примером отношения на множестве A является R = { (1, 1), (2, 1), (2, 3) } . Примером функции на множестве A является f = { (1, 1), (2, 1), (3, 3) } .

Примеры решения задач

1. Найти d R ,r R ,R -1 ,R×R ,R×R -1 ,R -1 ×R для R = {(x, y) | x, y Î D и x+y£0} .

Если (x, y)ÎR , то x и y пробегают все действительные числа. Поэтому d R = r R = D.

Если(x, y)ÎR , тоx+y£0 , значит y+x£0 и(y, x)ÎR . Поэтому R -1 =R .

Для любых xÎD , yÎD возьмём z=-|max(x, y)|-1 , тогда x+z£0 и z+y£0 , т.е.(x, z)ÎR и(z, y)ÎR .ПоэтомуR×R = R×R -1 = R -1 ×R = D 2 .

2. Для каких бинарных отношений R справедливо R -1 = -R ?

Пусть RÍA´B . Возможны два случая:

(1) AÇB¹Æ . Возьмём xÎAÇB . Тогда (x, x)ÎR Û (x, x)ÎR -1 Û (x, x)Î-R Û (x, x)Î(A´B) \ R Û (x, x)ÏR . Противоречие.

(2) AÇB=Æ . Так как R -1 ÍB´A , а-RÍA´B , то R -1 = -R= Æ . Из R -1 = Æ следует, что R = Æ . Из -R = Æ следует, что R=A´B . Противоречие.

Поэтому если A¹Æ иB¹Æ , то таких отношений R не существует.

3. На множестве D действительных чисел определим отношение R следующим образом: (x, y)ÎR Û (x–y) – рациональное число. Доказать, что R есть эквивалентность.

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

Для любого xÎD x-x=0 – рациональное число. Потому (x, x)ÎR .

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

Если (x, y)ÎR , то x-y = . Тогдаy-x=-(x-y)=- – рациональное число. Поэтому (y, x)ÎR .

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

Если (x, y)ÎR , (y, z)ÎR , то x-y = и y-z = . Складывая эти два уравнения, получаем, что x-z = + – рациональное число. Поэтому (x, z)ÎR .

Следовательно, R – это эквивалентность.

4. Разбиение плоскости D 2 состоит из блоков, изображённых на рисунке а). Выписать отношение эквивалентности R , соответствующее этому разбиению, и классы эквивалентности.

Аналогичная задача для b) и c).

а) две точки эквивалентны, если лежат на прямой вида y=2x+b , где b – любое действительное число.

b) две точки (x 1 ,y 1) и (x 2 ,y 2) эквивалентны, если (целая часть x 1 равна целой части x 2 ) и (целая часть y 1 равна целой части y 2 ).

с) решить самостоятельно.

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

1. Доказать, что если f есть функция из A в B и g есть функция из B в C , то f×g есть функция из A в C .

2. Пусть A и B – конечные множества, состоящие из m и n элементов соответственно.

a) Сколько существует бинарных отношений между элементами множеств A и B ?

b) Сколько имеется функций из A в B ?

c) Сколько имеется 1-1 функций из A в B ?

d) При каких m и n существует взаимно-однозначное соответствие между A и B ?

3. Доказать, что f удовлетворяет условию f(AÇB)=f(A)Çf(B) для любых A и B тогда и только тогда, когда f есть 1-1 функция.

КОМБИНАТОРИКА

Произведение всех натуральных чисел от 1 до n обозначается:

n! = 1·2·3·…·(n-1)·n, 0! = 1

Пусть X={x 1 , x 2 , ..., x n } – это множество из n элементов, k £ n .

Размещение элементов из X объёма k – это упорядоченное подмножество из k элементов, принадлежащих X .

Количество размещений объёма k из n

= n k (знач мест)

Если на каждую i -ю из k позиций можно поставить один из q i элементов множества X, то количество таких размещений равно:

(q 1 , q 2 , ..., q n) = q 1 × q 2 × ... × q n

Количество размещений объёма k из n

= n (n - 1 )(n - 2 ) … (n - k + 1 )=

Перестановка элементов из X – это размещение элементов из X объёма n .

Количество перестановок из n различных элементов:

= P n = n!

Если n элементов содержат q i элементов i -го сорта, q 1 + q 2 + ... + q m = n и элементы одного сорта идентичны, то число перестановок равно:

P n (q 1 , q 2 , ..., q m) =

Сочетание элементов из X объёма k – это неупорядоченное подмножество из k элементов, принадлежащих X .

Сочетания, размещения и перестановки могут быть также с повторениями элементов множества X (неограниченными и ограниченными).

Количество сочетаний объёма k из n различных элементов без повторений:

Количество сочетаний объёма k из n различных элементов с неограниченными повторениями:

Бином Ньютона:

Свойства:

(2)

(4)

(5)

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

1. Правило суммы. Если объект А может быть выбран n способами, а объект B другими m способами, то выбор «либо А, либо В» может быть осуществлен n+m способами.
2. Правило произведения. Если объект А может быть выбран n способами и после каждого из таких выборов объект B в свою очередь может быть выбран m способами, то выбор «A и B» в указанном порядке может быть осуществлен n×m способами.

Задача-пример . Из 12 девушек и 10 юношей выбирают команду, состоящую из пяти человек. Сколькими способами можно выбрать эту команду так, чтобы в нее вошло не более трех юношей?

Решение . Условие «не более трех» означает, что в команду может входить либо 3 юноши, либо 2 юноши, либо 1 юноша, либо ни одного юноши. Таким образом, в задаче выделяются четыре различных случая. В соответствии с правилом сложения нужно подсчитать количества вариантов в каждом из этих случаев и сложить их.

Рассмотрим первый случай. Нужно подсчитать, сколькими способами можно выбрать из 12 девушек и 10 юношей команду, состоящую из 3х юношей и 2х девушек. Из 10 юношей можно выбрать 3х юношей способами. Для каждых трех выбранных юношей можно выбрать также способами 2х девушек из 12ти. Поэтому работает правило умножения и в первом случае число вариантов команд равно × .

Аналогично, во втором случае: × .

В третьем случае: × .

В четвертом случае: .

Окончательный ответ: × + × + × + .

Примеры решения задач

№1.17. n (n>2) человек садятся за круглый стол. Два размещения по местам будем считать совпадающим, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколько существует способов сесть за стол?

Решение.

Общее количество всевозможных рассадок равно числу перестановок из n элементов P n = n! Однако из этих рассадок нужно исключить совпадающие. Отношение соседства сохраняется при циклических перестановках (их n штук) и при симметрическом отражении (их также n штук):

Поэтому всего способов (делить, т.к. правило умножения)

№1.19. Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется хотя бы один туз?

Решение.

Всего способов вынуть 10 карт из колоды . Из них в случаях в выборке не окажется ни одного туза. Поэтому ответ – .

№1.20. Сколькими способами можно составить три пары из n шахматистов?

Решение .

Сначала выберем из n шахматистов 6 человек. Это можно сделать способами. Теперь каждую шестёрку будем разбивать на пары. Для этого поставим 6 шахматистов в ряд, считая, что они имеют имена: a, b, c, d, e, f. Это можно сделать 6! способами. Однако нам не важен порядок внутри каждой пары и порядок самих пар. Перестановок, в которых шахматисты меняются местами в парах 2 3 . Перестановок, в которых меняются местами пары 3!. Поэтому разбить на пары 6 шахматистов можно способами. Ответ .

№1.24. Сколько существует чисел от 0 до 10 n , в которые не входят две идущие друг за другом одинаковые цифры?

Решение.

Рассмотрим все n-значные числа. Первую цифру мы можем выбрать 9-ю способами. Чтобы вторая цифра была отлична от первой, то её также можно выбрать 9-ю способами. Количество таких n-значных чисел равно количеству размещений объёма n из 9 элементов с неограниченными повторениями, т.е. равна 9 n для n>1 и 10 для n=1.

Поэтому ответ 10+9 2 +9 3 +...+9 n . Число 10 n не подходит.

ТЕОРИЯ АЛГОРИТМОВ

· Пусть N – это множество натуральных чисел, включая нуль.

· В данном разделе курса будут рассматриваться функции многих переменных f n (x 1 , ..., x n), определенные на некотором множестве MÍN n c натуральными значениями, т.е. f n (x 1 , ..., x n)ÎN, x i ÎN для i=1, ..., n, или f n Í N n +1 .

· Функция f n (x 1 , ..., x n) называется всюду определенной, если её областью определения является N n ­ , т.е. для любого набора из n натуральных чисел существует натуральное число, являющееся значением функции f n .

· Простейшие всюду определенные функции:

1. s(x)=x+1 для любого x;

2. o(x)=0 для любого x;

3. I n m (x 1 , ..., x m , ..., x n)=x m .

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

· Оператор суперпозиции:

Функция h n (x 1 , ..., x n) получается из функций g m , f n 1 , ..., f n m с помощью оператора суперпозиции, если h n (x 1 , ..., x n) = g m (f n 1 (x 1 , ..., x n), ..., f n m (x 1 , ..., x n)).

· Оператор примитивной рекурсии:

Функция f n +1 (x 1 , ..., x n , y) получается из функций g n (x 1 , ..., x n) и h n +2 (x 1 , ..., x n , y, z) с помощью оператора примитивной рекурсии, если она может быть задана схемой примитивной рекурсии:

æf n+1 (x 1 , ..., x n , 0) = g n (x 1 , ..., x n),

èf n+1 (x 1 , ..., x n , y+1) = h n+2 (x 1 , ..., x n , y, f n+1 (x 1 , ..., x n , y)).

· Оператор минимизации:

Функция f n (x 1 , ..., x n) получается из функции g n +1 (x 1 , ..., x n , y) с помощью оператора минимизации и обозначается f n (x 1 , ..., x n)=my, если:

f n (x 1 , ..., x n) определено и равно y Û g n +1 (x 1 , ..., x n , 0), ..., g n +1 (x 1 , ..., x n , y-1) определены и не равны нулю, а g n +1 (x 1 , ..., x n , y)=0.

(Можно говорить также: «Функция f n (x 1 , ..., x n) равна минимальному значению y, при котором функция g n +1 обращается в нуль»)

· Примитивно рекурсивная функция (прф)

Функция f n +1 (x 1 , ..., x n , y) называется примитивно рекурсивной, если она может быть получена из простейших функций с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

Следует отметить, что все примитивно рекурсивные функции всюду определены.

· Частично рекурсивная функция (прф)

Функция f n +1 (x 1 , ..., x n , y) называется частично рекурсивной, если она может быть получена из простейших функций с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации.

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

Примеры решения задач

1. Доказать, что следующие функции являются примитивно рекурсивными.

Решение . Функция f(x) может быть получена с помощью n-кратного применения оператора суперпозиции к простейшей функции s(x).

Решение . Функция f(x) может быть задана следующей схемой примитивной рекурсии:

æf(x, 0) = x = I 1 1 (x),

èf(x, y+1) = x+y+1=f(x,y)+1=s(f(x,y))=s(I 3 3 (x,y,f(x,y))).

Здесь функция g(x) имеет вид g(x)= I 1 1 (x) и является, как и полагается, функцией одной переменной. А функция h(x,y,z) имеет вид h(x,y,z)=s(I 3 3 (x,y,z)) и является функцией трех переменных.

Заметим, что функции g(x) и h(x,y,z) являются прф, т.к. g(x) – третья простейшая функция, а h(x,y,z) может быть получена из простейших функций s(x) и I 3 3 (x,y,z) с помощью применения оператора суперпозиции.

Так как функцию f(x,y) можно получить с помощью оператора примитивной рекурсии из примитивно рекурсивных функций g(x) и h(x,y,z), то f(x,y) – прф.

Решение. Функция f(x) может быть задана следующей схемой примитивной рекурсии:

æf(x, 0) = 0 = o(x),

èf(x, y+1) = x(y+1)=xy+x=f(x,y)+x= I 3 3 (x,y,f(x,y)))+ I 3 1 (x,y,f(x,y))).

Так как функцию f(x,y) можно получить с помощью оператора примитивной рекурсии из примитивно рекурсивных функций g(x)=o(x) и h(x,y,z) = I 3 3 (x,y,z)) + I 3 1 (x,y,z)), то f(x,y) – прф.

2. Пусть g(x 1 , ..., x n ,y) примитивно рекурсивная функция. Доказать, что следующая функция примитивно рекурсивна:

Решение. Особенность этой функции заключается в том, что суммирование ведется по переменному числу слагаемых. Однако функция f n +1 может быть задана следующей схемой примитивной рекурсии:

æf(x 1 , ..., x n , 0) = g(x 1 , ..., x n ,0) – прф,

èf(x 1 , ..., x n , y+1) = = f(x 1 , ..., x n , y) + g(x 1 , ..., x n ,y+1) – сумма прф g и самой функции f.

3. Доказать, что следующая функция частично рекурсивна.

Решение. Покажем, что функция f(x,y) может быть получена с помощью оператора минимизации.

Пусть x³y, тогда f(x,y) определена и принимает некоторое значение: f(x,y) = x-y = z. Как вычислить z? Можно предложить следующий способ: начиная с нуля перебирать по порядку все значения z, пока не выполнится условие x-y=z, или x-y-z=0. Такое z обязательно найдется, т.к. x-y³0. Если же x-y<0, то ни какое натуральное z не подойдет.

Программист записал бы это так:

unsigned int f(x,y)

while((x-y-z)!=0) z++;

То же самое можно записать и в терминах оператора минимизации:

f(x, y)=mz[|x–y–z|=0]

Модуль необходим для того, чтобы функция g(x,y,z)=|x–y–z| была определена, даже если x–y<0. Заметим, что g(x,y,z)=|x–y–z| является примитивно рекурсивной, т.к. может быть получена с помощью конечного числа применений оператора суперпозиции к простейшим функциям.

a) нигде не определённая функция (т.е. функция с пустой областью определения) ;

b)

c)

Определения

• 1. Бинарным отношением между элементами множеств А и В называется любое подмножество декартова произведения RAB, RAА.
• 2. Если А=В, то R - это бинарное отношение на A.
• 3. Обозначение: (x, y)R xRy.
• 4. Область определения бинарного отношения R - это множество R = {x: существует y такое, что (x, y)R}.
• 5. Область значений бинарного отношения R - это множество R = {y: существует x такое, что (x, y)R}.
• 6. Дополнение бинарного отношения R между элементами А и В - это множество R = (AB) R.
• 7. Обратное отношение для бинарного отношения R - это множество R1 = {(y, x) : (x, y)R}.
• 8. Произведение отношений R1AB и R2BC - это отношение R1 R2 = {(x, y) : существует zB такое, что (x, z)R1 и (z, y)R2}.
• 9. Отношение f называется функцией из А в В, если выполняется два условия:
  • а) f = А, f В
  • б) для всех x, y1, y2 из того, что (x, y1)f и (x, y2)f следует y1=y2.
• 10. Отношение f называется функцией из А на В, если в первом пункте будет выполняться f = А, f = В.
• 11. Обозначение: (x, y)f y = f(x).
• 12. Тождественная функция iA: AA определяется так: iA(x) = x.
• 13. Функция f называется 1-1-функцией, если для любых x1, x2, y из того, что y = f(x1) и y = f(x2) следует x1=x2.
• 14. Функция f: AB осуществляет взаимно однозначное соответствие между А и В, если f = А, f = В и f является 1-1-функцией.
• 15. Свойства бинарного отношения R на множестве А:
  • - рефлексивность: (x, x)R для всех xA.
  • - иррефлексивность: (x, x)R для всех xA.
  • - симметричность: (x, y)R (y, x)R.
  • - антисимметричность: (x, y)R и (y, x)R x=y.
  • - транзитивность: (x, y)R и (y, z)R (x, z)R.
  • - дихотомия: либо (x, y)R, либо (y, x)R для всех xA и yA.
• 16. Множества А1, A2, ..., Аr из Р(А) образуют разбиение множества А, если
• - Аi , i = 1, ..., r,
• - A = A1A2...Ar,
• - AiAj = , i j.

Подмножества Аi , i = 1, ..., r, называются блоками разбиения.

• 17. Эквивалентность на множестве А - это рефлексивное, транзитивное и симметричное отношение на А.
• 18. Класс эквивалентности элемента x по эквивалентности R - это множество [x]R={y: (x, y)R}.
• 19. Фактор множество A по R - это множество классов эквивалентности элементов множества А. Обозначение: A/R.
• 20. Классы эквивалентности (элементы фактор множества А/R) образуют разбиение множества А. Обратно. Любому разбиению множества А соответствует отношение эквивалентности R, классы эквивалентности которого совпадают с блоками указанного разбиения. По-другому. Каждый элемент множества А попадает в некоторый класс эквивалентности из A/R. Классы эквивалентности либо не пересекаются, либо совпадают.
• 21. Предпорядок на множестве A - это рефлексивное и транзитивное отношение на А.
• 22. Частичный порядок на множестве A - это рефлексивное, транзитивное и антисимметричное отношение на А.
• 23. Линейный порядок на множестве A - это рефлексивное, транзитивное и антисимметричное отношение на А, удовлетворяющее свойству дихотомии.

Пусть A={1, 2, 3}, B={a, b}. Выпишем декартово произведение: AB = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }. Возьмём любое подмножество этого декартова произведения: R = { (1, a), (1, b), (2, b) }. Тогда R - это бинарное отношение на множествах A и B.

Будет ли это отношение являться функцией? Проверим выполнение двух условий 9a) и 9б). Область определения отношения R - это множество R = {1, 2} {1, 2, 3}, то есть первое условие не выполняется, поэтому в R нужно добавить одну из пар: (3, a) или (3, b). Если добавить обе пары, то не будет выполняться второе условие, так как ab. По этой же причине из R нужно выбросить одну из пар: (1, a) или (1, b). Таким образом, отношение R = { (1, a), (2, b), (3, b) } является функцией. Заметим, что R не является 1-1 функцией.

На заданных множествах A и В функциями также будут являться следующие отношения: { (1, a), (2, a), (3, a) }, { (1, a), (2, a), (3, b) }, { (1, b), (2, b), (3, b) } и т.д.

Пусть A={1, 2, 3}. Примером отношения на множестве A является R = { (1, 1), (2, 1), (2, 3) }. Примером функции на множестве A является f = { (1, 1), (2, 1), (3, 3) }.

Примеры решения задач

1. Найти R, R, R1, RR, RR1, R1R для R = {(x, y) | x, y D и x+y0}.

Если (x, y)R, то x и y пробегают все действительные числа. Поэтому R = R = D.

Если (x, y)R, то x+y0, значит y+x0 и (y, x)R. Поэтому R1=R.

Для любых xD, yD возьмём z=-|max(x, y)|-1, тогда x+z0 и z+y0, т.е. (x, z)R и (z, y)R. Поэтому RR = RR1 = R1R = D2.

2. Для каких бинарных отношений R справедливо R1= R?

Пусть RAB. Возможны два случая:

• (1) AB. Возьмём xAB. Тогда (x, x)R (x, x)R1 (x, x)R (x, x)(AB) R (x, x)R. Противоречие.
• (2) AB=. Так как R1BA, а RAB, то R1= R= . Из R1 = следует, что R = . Из R = следует, что R=AB. Противоречие.

Поэтому если A и B, то таких отношений R не существует.

3. На множестве D действительных чисел определим отношение R следующим образом: (x, y)R (x-y) - рациональное число. Доказать, что R есть эквивалентность.

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

Для любого xD x-x=0 - рациональное число. Потому (x, x)R.

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

Если (x, y)R, то x-y = . Тогда y-x=-(x-y)=- - рациональное число. Поэтому (y, x)R.

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

Если (x, y)R, (y, z)R, то x-y = и y-z =. Складывая эти два уравнения, получаем, что x-z = + - рациональное число. Поэтому (x, z)R.

Следовательно, R - это эквивалентность.

4. Разбиение плоскости D2 состоит из блоков, изображённых на рисунке а). Выписать отношение эквивалентности R, соответствующее этому разбиению, и классы эквивалентности.

Аналогичная задача для b) и c).

а) две точки эквивалентны, если лежат на прямой вида y=2x+b, где b - любое действительное число.

b) две точки (x1,y1) и (x2,y2) эквивалентны, если (целая часть x1 равна целой части x2) и (целая часть y1 равна целой части y2).

с) решить самостоятельно.

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

• 1. Доказать, что если f есть функция из A в B и g есть функция из B в C, то fg есть функция из A в C.
• 2. Пусть A и B - конечные множества, состоящие из m и n элементов соответственно.

Сколько существует бинарных отношений между элементами множеств A и B?

Сколько имеется функций из A в B?

Сколько имеется 1-1 функций из A в B?

При каких m и n существует взаимно-однозначное соответствие между A и B?

3. Доказать, что f удовлетворяет условию f(AB)=f(A)f(B) для любых A и B тогда и только тогда, когда f есть 1-1 функция.

Язык 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