Глава 2. Бинарные отношения

2.1. Основные определения

Бинарные отношения используются для определения каких-либо взаимосвязей, которыми характеризуются пары элементов множества, т.е. если отношение Pопределено на множествеAB(PAB), то это значит, что в множествоPпопадут только те пары множестваAB, между элементами которых имеет место указанное отношение.

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

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

1. Бинарное отношение PAB, где A={a₁, a₂, …,a_n}, B={b₁, b₂, …,b_m} может быть задано (n,m)-матрицей(таблицей) (mстрок,nстолбцов), в которой элемент, стоящий на пере­сеченииi-й строки иj-го столбца, равен 1, если между элементамиa_iиb_jимеет место отношениеP, или 0 в противном случае.

Н

P	5	6	7	8	9
6	1	0	0	0	0
7	1	1	0	0	0
8	1	1	1	0	0

апример, отношениеP={(a,b) |aA,bBиa>b}, гдеA={6,7,8}, B={5,6,7,8,9} задано характеристическим свойством. Это же отношение может быть определено перечислениемP={(6,5), (7,5), (7,6), (8,5), (8,6), (8,7)} или матрицей отношения.

	2. Если PAB,AиB– числовые множества, то отношениеP можно изобразить какмножество точек на плоскости, где каждая точка представляет собой пару из множестваP.Например,P={(2,1), (1,2), (2,2), (3,2), (4,2), (1,3), (2,4)}, где A={1,2,3,4,5},B={1,2,3,4}.
	3. Если PAB, то отношениеPможно изобразить в виде диаграммы, состоящей из узлов и стрелок, при этом узлам взаимно однозначно соответствуют элементы множествA иB, а стрелка соединяет элементaс элементомbтолько в том случае, если (a, b)P. Например,P={(a,2), (a,3), (b,1), (c,1)}, A={a, b, c}, B={1, 2, 3}.
	4. Если PA^2, то бинарное отношение может быть заданов виде графа, вершины которого – элементы множества, а дуги направленные отaкbозначают, что (a, b)P. Например,P={(a, c), (c, a), (b, a), (b, b) , (a, d)}, гдеA={a,b,c,d}.

Способы задания 2–4 иногда называют графическими способами отображения бинарных отношений.

Пусть P– некоторое бинарное отношение.

Областью определенияPназывается множество

_P={x|(x,y)для некоторогоy}.

Областью значенийPназывается множество

_P={y|(x,y)для некоторогоx}.

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

Обратным кPотношениемназывается множество

P^–1={(y,x)|(x,y) }.

Композицией бинарных отношений P₁ABиP₂BCназывается множествоP₃=, гдеP₃ACиP₃={(x,y) |xA,yCи найдетсяzBтакой, что (x,z)P₁и (z,y)P₂}.

Образом множества XотносительноPназывается множество

P(X)={y|(x,y)для некоторогоxX}.

Множество P^‑1(Y)={x|(x,y)для некоторогоyY} называется прообразом множества YотносительноP.

Пример 14.Найти,,,,,для отношения:

.

1). Для доказательства равенства множеств необходимо доказать два включенияи.

а) По определению , но так как функция квадратного корня не определена для неположительных чисел, то

, т.е..

б) Покажем, что . Пусть, тогда значение выражения– число вещественное, поэтому можно утверждать, что найдетсяy, например, такой что. Таким образом, мы показали, что для элементаxвыполняется характеристика множества. Следовательно,.

Далее доказательства равенства множеств будем приводить в сокращенной форме.

2).

а) , так как функция квадратного корня принимает только положительные значения.

б) , так как найдетсяx, например, такой что(действительно,и при этом– число вещественное).

3).

4).

а) .

Пусть , тогда существует вещественныйz, такой чтои. Учитывая характеристику множестваP, дляx,y,zможно записатьи, поэтомуx обязательно неотрицательное число, а. Подставляяz из первого выражения во второе получаем. Следовательно,

.

б) , так как если парапринадлежит множеству, то найдетсяz, например, такой чтои. Следовательно,.

5).

а) .

Пусть , тогда существует вещественныйz, такой чтои. Учитывая характеристики множествPиP^–1, дляx,y,zможно записать:,. Следовательно, величиныx иy должны быть равными и положительными, т.е..

б) , так как если парапринадлежит множеству, то найдетсяz, напримертакой, чтои. Следовательно,.

6).

а) .

Пусть , тогда существует вещественныйz, такой чтои. Учитывая характеристики множествP^–1иP, дляx,y,zможно записать:и. Следовательно,

.

б) , так как если пара, то найдетсяz, например,, такой чтои. Следовательно,.

Пример 15.Найти,,,,,для отношения

Все доказательства в этом примере приведем в сокращенном виде.

1) .

а) по определению;

б) , так как для произвольного натуральногоxможно подобратьy, например,y =x, такой, что.

2).

а) по определению;

б) , так как для произвольного, если взятьx =y.

3)

4)

а) и найдетсяz, такой, чтои

и найдется z, такой, что иzделится наx иyделится наz

и yделится наx.

,

5)

а) по определению;

б) и найдётся, который делится наи на

и найдётся , такой, что.

6)

а) по определению;



Пример 16.Найти относительно множестваP образ множестваX и прообраз множестваY, если:

а) ,X={2,3},;

б) ,

, .



б),

2.2. Специальные бинарные отношения

Специальнымназывается бинарное отношение на непустом множествеA, т.е. отношениеPA²,A.

Для любого множества Aопределимтождественноеотношениеid_A={(x,x)|xA} (id_Aтакже называютдиагональю) иуниверсальноеотношениеu_A=A²(u_Aтакже называютполнымотношением).

Таблица 1

Свойства специального бинарного отношения P, определенного на A²

Отношение обладает(+), не обладает (‑) свойством:		Определение		Особенности матрицы отношения	Графические особенности диаграммы
Рефлексив­ности	+		Если (x,x)P для всех xA	Все диагональные элементы равны 1	Содержит петли во всех узлах
	–		Если существует xA, такой, что (x,x)P	На диагонали есть хотя бы один 0	Имеется хотя бы один узел без петли
Иррефлексивности	+		Если (x,x)P для всех xA	Все диагональные элементы равны 0	Все узлы не имеют петель
	–		Если существует xA, такой, что (x,x)P	На диагонали есть хотя бы одна 1	Имеется хотя бы одна петля
Симметричности	+		Если для всех x,yA из того, что (x,y)P, следует, что (y,x)P	Матрица симметрична	Для каждой дуги, соединяющей два узла, есть также дуга, соединяющая эти узлы в обратном направлении
	–		Если существуют x,yA, такие, что (x,y)P, (y,x)P	Матрица не симметрична	Есть два узла, соединенные только одной дугой
Антисимметричности	+		Если для всех x,yA из того, что (x,y)P и (y,x)P, следует x=y	В матрице вне главной диагонали нет симметрично расположенных 1	Не существует двух различных узлов, связанных парой разнонаправленных дуг
	–		Если существуют x,yA, такие, что (x,y)P, (y,x)P, xy	Вне главной диагоналиесть хотя бы две, симметрично расположенные 1	Есть два узла, соединенные двумя разнонаправленными дугами

Окончание табл. 1

Отношение обладает(+), не обладает (‑) свойством:		Определение		Особенности матрицы отношения	Графические особенности диаграммы
Транзитивности	+		Если для всех x,y,zA из того, что (x, y)P и (y, z)P, следует, что (x,z)P.		Для любых двух дуг, таких, что одна направлена от a к b, а другая – от b к c, существует дуга, соединяющая a и c в направлении от a к c.
	–		Если существуют x,y,zA, такие, что (x, y)P, (y, z)P, (x,z)P		Существуют две дуги, такие, что одна направлена от a к b, а другая – от b к c, и при этом нет дуги от a к c.

Для специальных бинарных отношений определены свойства рефлексивности, иррефлексивности, симметричности, антисимметричности, транзитивности. Их смысл поясняет таблица (см. таблицу 1 на стр. 34).

Отношение Pназываетсяэквивалентностью, если оно является рефлексивным, симметричным и транзитивным. Отношение эквивалентности разбивает множествоA, на котором оно задано, на непересекающиеся подмножества так, что элементы одного и того же подмножества находятся в отношении P, а между элементами из разных подмножеств отношениеPне выполняется. В таком случае говорят, что отношениеPзадаетразбиение на множестве A, илисистему классов эквивалентностипо отношениюP. В то же время любое разбиение множестваAна классы определяет некоторое отношение эквивалентности, а именно, отношение «входить в один и тот же класс данного разбиения». Например, отношением эквивалентности является отношение равносильности на множестве формул, описывающих элементарные функции (формулы равносильны, если они задают одну и ту же функцию, например,) [8].

Отношением нестрогого порядка (илинестрогим порядком) называют бинарное отношение на множестве, если оно рефлексивно, антисимметрично, транзитивно, иотношением строгого порядка (строгим порядком), если оно иррефлексивно, антисимметрично, транзитивно. Оба эти отношения называютсяотношениями порядка. Например, отношения «быть не выше» на множестве людей, отношение «» на множестве чисел – нестрогий порядок; отношения «быть моложе» – строгий порядок.

Элементы сравнимы по отношению PнаA, еслиили. МножествоA, на котором задано отношение порядка, может быть:

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

б) частично упорядоченным множеством, в противном случае. При этом говорят, что отношениеPзадает на множествеAчастичный порядок. Например, отношение «быть начальником» задает на множестве сотрудников организации частичный порядок, так как, например, для пары сотрудников одного отдела данное отношение не выполняется: они не сравнимы по данному отношению.

Пример 17.ПустьPA², где A={1, 2, 3}. Тогда:

P={(1,1), (2,2), (3,3), (1,2), (2,1)} – рефлексивно, симметрично, транзитивно, следовательно,P – отношение эквивалентности;

P={(1,2), (2,3), (1,3)} – иррефлексивно, антисимметрично, транзитивно, следовательно,P – отношение строгого порядка;

P={(1,1), (2,3), (3,1)} – антисимметрично;

P={(2,1), (1,2)} – иррефлексивно, симметрично;

P=A²– эквивалентность.

Пример 18.ПустьL– множество людей. Тогда:

–эквивалентность;

–отношение строгого порядка;

–отношение нестрогого порядка;

–не обладает никакими свойствами.

Отметим, что в примерах 17 и 18 указаны все выполняющиеся свойства.

Пример 19. Доказать, что если отношенияPи Sсимметричны, то симметричны и отношения,,.

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

Пусть произвольная пара бинарного отношения, т.е.. Тогда из определения операции объединения следует, что «»:

1. . По условию задачиPсимметричное отношение, поэтому из того, чтоследует, что.

2. Аналогично, в случае если пара оказалась элементном множестваS, то исходя из симметричности отношенияS, можно утверждать, что.

Таким образом, взяв произвольную пару множества, мы показали, что в одном из множествPилиS, а значит, в множестве, будет присутствовать пара, что и требовалось доказать.

Доказательство того, что отношения ,симметричны, запишем в сокращенной форме:

.



Пример 20.Доказать, что если отношениеPсимметрично и антисимметрично одновременно, то оно транзитивно.

Структура доказательства транзитивности имеет вид:

«Если и, ……, то».

Пусть и. Так какP симметрично, то

По условию известно, что P антисимметричное отношение, поэтому парыимогут одновременно принадлежать множеству, только если, следовательно, наличие одновременно свойств симметричности и антисимметричности означает, что множествоPсостоит только из элементов вида. Для того, чтобы множествоPбыло не транзитивно, должно выполняться условие. С учетом того, что множествоPсостоит только из элементов диагонали, условие не транзитивности примет вид(y=x,z=y). Значит,P не может быть не транзитивным, что и требовалось доказать.