Лекция № 3. Отношения и их свойства.

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

Определение.Подмножествоназываетсяместным (мерным) отношением на множестве А. Говорят, что элементынаходятся в отношении, если.

Одноместное (одномерное) отношение – это просто некоторое подмножество А. Такие отношения называют признаками. Говорят, что обладает признаком, еслии. Свойства одноместных отношений – это свойства подмножеств А, поэтому для случаятермин “отношения” употребляется редко.

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

Пример 1.Бинарные отношения на множестве.

а) Отношение “” выполняется для пари не выполняется для пары.

б) Отношение “иметь общий делитель, не равный единице” выполняется для пар и не выполняется для пар.

в) Отношение “быть делителем” выполняется для пар и не выполняется для пар.

Пример 2. Бинарные отношения на множестве точек координатной плоскости.

а) Отношение “быть равноудалёнными от начала координат” выполнятся для пар точек и, но не выполнятся для пары точеки.

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

в) Отношение “быть удалёнными на разное расстояние от начала координат” выполняется для всех точек, для которых не выполняется отношение, описанное в пункте “б”.

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

Строго говоря, само отношение и его сужение- это разные отношения, с разными областями определения. Однако, по умолчанию, если не возникает явных разночтений, эта разница не учитывается. Например, вполне можно говорить об отношении “быть делителем”, не уточняя, задано оно на множествеили на каком-нибудь его подмножестве.

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

Пример 3.Для конечного множестваматрицы отношений из примера 1 (а – в) приведены в следующих таблицах.

а)

	1	2	3	4	5	6
1	1	1	1	1	1	1
2	0	1	1	1	1	1
3	0	0	1	1	1	1
4	0	0	0	1	1	1
5	0	0	0	0	1	1
6	0	0	0	0	0	1

б)

	1	2	3	4	5	6
1	0	0	0	0	0	0
2	0	1	0	1	0	1
3	0	0	1	0	0	1
4	0	1	0	1	0	1
5	0	0	0	0	1	0
6	0	1	1	1	0	1

в)

	1	2	3	4	5	6
1	1	1	1	1	1	1
2	0	1	0	1	0	1
3	0	0	1	0	0	1
4	0	0	0	1	0	0
5	0	0	0	0	1	0
6	0	0	0	0	0	1

Поскольку отношения на множестве А задаются подмножествами А², для отношений можно определить те же операции, что и для множеств. Например, отношение“”является объединением отношений“<” и “=”.

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

Непосредственно из определения следует, что . Например, для отношения “” обратным является отношение “”.

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

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

Главная диагональ матрицы рефлексивного отношения содержит только единицы.

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

Главная диагональ матрицы рефлексивного отношения содержит только нули.

Например, отношения “” и “иметь общий делитель” являются рефлексивными. Отношения “” и “иметь сына” являются антирефлексивными. Отношение “быть симметричным относительно оси абсцисс” не является ни рефлексивным, ни антирефлексивным: точка плоскости симметрична сама себе, если лежит на этой оси, и не симметрична себе, если не лежит на ней.

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

Матрица симметричного отношения симметрична относительно главной диагонали: для любых.

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

Отношение “быть симметричным относительно оси абсцисс” является симметричным: если первая точка симметрична второй относительно этой оси, то и вторая точка симметрична первой. Отношение “” является антисимметричным. Действительно, еслии, это означает, что.

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

Определение.Отношениеназываетсятранзитивным, если для любыхиз отношенийиследует.

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

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

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

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

Если отношение транзитивно, то, очевидно,(и наоборот). Например, отношение “быть делителем” транзитивно для любой цепочки элементов и само является транзитивным замыканием этого отношения.

Если отношение не транзитивно, то.

Например, транзитивным замыканием отношения “быть сыном” является отношение “быть прямым потомком”, включающее в себя понятия “быть сыном”, “быть внуком”, “быть правнуком” и так далее.

Назад, в начало конспекта.