ДМ_Конспект

6.Какое отношение называется n -арным, унарным, бинарным?

7.Что такое тождественное отношение, полное отношение, нулевое отношение?

8.Пусть A некоторое множество. Что означает запись A1 , A2 , A3 , An ?

9.Что является областью определения и областью значения отношения

R ?

10.Назовите способы задания отношений.

11.Какие из способов задания отношений применимы для n -арных отношений при n 2?

12.Перечислите операции, производимые над отношениями.

13.Дайте определение сечения отношения R по элементу xi .

14.Что такое фактор-множество множества Y по отношению R ?

15.Назовите специфические операции над отношениями.

16.Что такое композиция отношений?

17.Что такое симметризация отношений?

18.Какое отношение называется обратным?

ЛЕКЦИЯ 4 СВОЙСТВА БИНАРНЫХ ОТНОШЕНИЙ

4.1 Основные свойства бинарных отношений

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

отношений.
Пусть R бинарное отношение в множестве	X (R X X ) .

Определим общие свойства таких отношений, которые должны выполняться для всех (xi , x j ) R :

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

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

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

асимметричность;

антисимметричность;

транзитивность;

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

Определение. Отношение R X X называется рефлексивным, если (xi , xi ) принадлежит R для всех xi из X , т.е. оно всегда выполняется между

объектом и им самим ( xRx).

41

Для рефлексивного отношения все элементы матрицы на главной диагонали равны 1. Граф рефлексивного отношения содержит петли у всех вершин.

Определение.	Отношение R X X называется	антирефлексивным,
если R E ( E	тождественное отношение), т.е. может выполняться
только для несовпадающих объектов: из xi Rx j следует xi		x j .

Для антирефлексивного отношения все элементы матрицы на главной диагонали равны 0. Граф антирефлексивного отношения не содержит петель у вершин, нет дуг вида (xi , xi ) .

Примеры.

Отношение равенства («=»), отношение « » на множестве вещественных чисел, отношение «иметь общий делитель» на множестве целых чисел рефлексивны.

Отношение « » на множестве вещественных чисел, отношения «быть сыном», «быть старше» на множестве людей антирефлексивны.

Отношение «быть симметричным относительно оси X на множестве точек координатной плоскости» не является ни рефлексивным, ни антирефлексивным: точка плоскости симметрична сама себе, если она лежит на оси X , и несимметрична сама себе в противном случае.

Определение. Отношение R X X называется симметричным, если R R 1 , т.е. при выполнении соотношения xi Rx j выполняется и соотношение x j Rxi ( R выполняется либо в обе стороны, либо не выполняется вообще).

Симметричность отношения влечет и симметричность матрицы.

Для симметричного отношения вершины графа могут быть связаны только парами противоположно направленных дуг (ненаправленными ребрами).

Определение. Отношение R X X называется асимметричным, если R R 1 , т.е. из двух соотношений xi Rx j и x j Rxi по меньшей мере одно не выполняется. Если отношение асимметрично, то оно и антирефлексивно.

Матрица асимметричного отношения характеризуется тем, что у неѐ нулевые элементы на главной диагонали и нет ни одной пары единиц, стоящих на симметричных относительно главной диагонали местах (несимметричность матрицы).

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

Определение. Отношение R X X называется антисимметричным, если R R 1 E ( E тождественное отношение), т.е. оба соотношения xi Rx j

и x j Rxi выполняются одновременно только тогда, когда xi x j

42

Матрица антисимметричного отношения является несимметричной, но на главной диагонали могут находиться как 0, так и 1.

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

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

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

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

Определение. Отношение R X X называется R транзитивным, если R R R , т.е. из xi Rxj и x j Rxk следует xi Rxk .

В матрице транзитивного отношения для каждой пары единичных элементов, один из которых расположен в i -й строке и j -м столбце, а другой в

j -й строке и k -м столбце, обязательно существует единичный элемент,

расположенный в клетке на пересечении i -й строки и k -ого столбца (наличие единичных элементов на главной диагонали не нарушает транзитивности).

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

редукции.

Определение. Отношение R X X называется R антитранзитивным, если из xi Rxj и x j Rxk следует, что не выполняется xi Rxk .

Примеры. Отношения «равенство», «быть делителем», заданные на множестве целых чисел, и отношение «жить в одном городе», заданное на множестве людей являются транзитивными.

Отношение «быть сыном» на множестве людей является антитранзитивным.

4.2 Классы бинарных отношений

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

Отношение эквивалентности представляет собой экспликацию (перевод интуитивных представлений в ранг строгих математических понятий) таких

43

X на этого

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

Определение. Бинарное отношение в множестве X называется отношением эквивалентности (обозначается ~), если для него выполняются следующие свойства:

рефлексивность ( x ~ x );

симметричность (если x ~ y , то y ~ x );

транзитивность (из ) x ~ y и y ~ z следует x ~ z . Примеры отношений эквивалентности:

«проживать в одном доме » в множестве людей;

«подобие треугольников» в множестве всех треугольников на плоскости;

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

определяет признак,	который допускает разбиение множества X на
непересекающиеся	подмножества	X i ,	называемые	классами

эквивалентности. Наоборот, всякое разбиение множества непересекающиеся подмножества определяет между элементами множества некоторое отношение эквивалентности.

Теорема 4.1

Если на множестве X задано отношение эквивалентности, то это отношение задает разбиение множества и это разбиение единственно.

Все элементы, принадлежащие некоторому	классу	X i разбиения
{X1 , X 2 , ..., X n } множества X , связаны между	собой	отношением

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

Подмножество из X , содержащее по одному и только одному элементу из каждого класса некоторого разбиения, называют системой представителей соответствующего отношения эквивалентности. Множество всех классов разбиения множества X , определяемого отношением эквивалентности R , образует фактор-множество X \ R .

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

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

44

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

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

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

Пример Для отношения эквивалентности, заданного классами

эквивалентности		X1 {x1, x2 , x3};			X 2	{x4 , x6};			X3 {x6 , x7 , x8 , x9}, матрица
будет иметь вид
		x1	x2	x3	x4		x5	x6	x7	x8	x9
	x1	1	1	1
	x2	1	1	1
	x3	1	1	1
	x4				1		1
	x5				1		1
	x6							1	1	1	1
	x7							1	1	1	1
	x8							1	1	1	1
	x9							1	1	1	1

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

45

x2

x6 x6

x1 x3

x8 x7

x4

Рисунок 4.1 Граф отношения эквивалентности

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

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

Отношение порядка в общем случае обозначается .

Определение

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

Определение

Отношение R в множестве X называется отношением частичного (нестрогого) порядка, если для любых x, y, z из X выполняются свойства:

	рефлексивности ( x x );
	антисимметричности (из x y и y x следует x y );
	транзитивности (если x y и y z , то x z ).

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

Определение

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

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

Отношением частичного порядка в множестве целых чисел является отношение «быть делителем» (очевидно, что не все пары элементов из множества целых чисел находятся в данном отношении)

Булеан B( X ) , т.е. множество всех подмножеств некоторого множества

X , является частично упорядоченным множеством с отношением теоретикомножественного включения , как отношения частичного порядка.

46

Определение

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

Пример. Пусть T множество положительных делителей числа 30, а R есть отношение частичного порядка ( m n ), если m делит n нацело. Целые числа 5 и 15 сравнимы, поскольку 5 делит 15 нацело, а 5 и 6 несравнимы.

Определение

Частичный порядок называется линейным (полным) порядком, если любые два элемента x и y из множества X сравнимы, т.е. x y и y x .

Определение

Множество X , на котором задано отношение частичного порядка R и для которого любые два элемента этого множества сравнимы, называется

линейно упорядоченным, полностью упорядоченным или цепью.

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

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

Любое частично упорядоченное множество наглядно можно представить в виде схемы, которая называется диаграммой Хассе. Каждый элемент x X на плоскости изображается точкой, и любую пару точек, соответствующих элементам x X и y X , соединяют стрелкой, идущей из точки x в точку y ,

тогда и только тогда, когда (x y) , (x y) , и не существует z X такого, что (x y z) , и элемент z отличается и от x , и от y .

Пример. Пусть A {0,1, 2, 3, 4, 5} линейно упорядоченное множество с

обычным отношением порядка на множестве натуральных чисел, не превосходящих пяти. Элементы этого отношения упорядочены обычным отношением частичного порядка .

Его диаграмма Хассе изображена на рис. 4.2.

47

5

4

3

2

1

0

Рисунок 4.2 Диаграмма Хассе

Рассмотрим отношения нестрогого и строгого порядка.

Определение

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

Определение

Отношение R в множестве X называется отношением строгого порядка (его принято обозначать символом < ), если оно:

антирефлексивно (если x y , то x y );

асимметрично (если x y , то не верно y x )

транзитивно (если x y и y z , то x z ).

Это отношение не является частичным порядком, т.к. не удовлетворяет условию рефлексивности x x .

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

Отношение строгого порядка характерно для различного рода иерархий с подчинением одного объекта другому (или другим)

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

главная диагональ матрицы этого отношения заполнена единицами (свойство рефлексивности);

ни один единичный элемент не имеет симметричного себе элемента относительно главной диагонали (свойство антисимметричности);

наличие единиц на пересечении i -го столбца и j -й строки, и единицы

на пересечении j -го столбца и k -й строки, влечет за собой наличие единицы на пересечении i -го столбца и k -й строки (свойство транзитивности).

48

Матрица отношения строгого порядка отличается тем, что все элементы главной диагонали нулевые (свойство антирефлексивности).

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

Граф строгого порядка отличается тем, что в нем отсутствуют петли.

4.2.3 Отношение толерантности

Определение

Отношение толерантности на множестве X удовлетворяет свойствам:

рефлексивности ( x x );

симметричности (из x y следует y x );

антитранзитивности .

Для этого отношения, в отличие от эквивалентности, транзитивность не обязательна, и значит, эквивалентность есть частный случай толерантности.

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

Пример.

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

На множестве кортежей (векторов) x (x1, x2 ,...,xn ) толерантность можно

задать различными способами, например, обусловить наличие в паре кортежей хотя бы одной общей компоненты xi . Компонентами кортежа могут быть

любые объекты. Если они принимают целочисленное значение от 0 до m 1, то кортеж можно рассматривать как n -разрядное число, записанное в позиционной системе счисления с основанием m

Пример. Кортеж x (7, 0, 4, 9, 2) соответствует десятичному числу 70492.

количество всех таких кортежей, очевидно, равно mn .

При m 2 имеем двоичный кортеж, его компоненты принимают значения 0 или 1. Для каждого x (x1 , x2 , ..., xn ) существует только один не толерантный

ему кортеж (1 x1 ,1 x2 ,...,1 xn ) .

Пример. Двоичный кортеж можно трактовать также как содержимое n - разрядного регистра вычислительной машины. Состояние машины определяется содержимым всех его регистров, т.е. множеством двоичных кортежей. Если два состояния машины различаются содержимым некоторого

49

ограниченного числа регистров, то говорят, что эти состояния толерантны, а машину называют толерантным автоматом.

4.3 Контрольные вопросы и задания

1.Перечислите основные свойства отношений.

2.Что такое рефлексивность отношения?

3.Какое отношение является антирефлексивным?

4.Какое отношение является симметричным?

5.Какое отношение является асимметричным?

6.Какое отношение является антисимметричным?

7.Какое отношение является транзитивным?

8.Какое отношение в множестве X называется отношением эквивалентности?

9.Какое отношение в множестве X называется отношением нестрогого порядка?

10.Какое отношение в множестве X называется отношением строгого

порядка?

11.Какое отношение называется функциональным?

ЛЕКЦИЯ 5 ФУНКЦИОНАЛЬНЫЕ ОТНОШЕНИЯ. ЭЛЕМЕНТЫ

РЕЛЯЦИОННОЙ АЛГЕБРЫ

5.1 Функциональные отношения

Определение

Отношение F X Y называется функциональным, если его элементы (упорядоченные пары (x, y) ) имеют различные первые координаты, т.е. каждому x X либо соответствует только один элемент y Y , такой, что xF y , либо такого элемента y вообще не существует.

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

Элементам	x X , не	входящим в область определения функционального
отношения	DO (F ) , соответствует нулевой столбец в матрице и изолированная
вершина в графе функционального отношения.
Пример. Пусть		заданы множества	X {x1 , x2 , x3 , x4 , x5 , x6 } и

Y {y1 , y2 , y3}. Отношение A {(x1 , y1 ), (x2 , y2 ), (x3 , y1 ), (x5 , y3 ), (x6 , y1 )} является функциональным. В матрице данного отношения четвертый столбец нулевой, а его граф содержит изолированную вершину.

50