Лекция 11 (1018865)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция 11. Отношения.

1. Отношения

1.1. Основные понятия отношений

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

Для начала введём понятие прямого (декартового) произведения множеств.

Прямым (декартовым) произведением множеств и ( ) называется множество всех векторов , таких, что :

Если , то . Аналогично для нескольких множеств. Прямым произведением множества называется множество всех векторов длины , таких, что .

Пример.

Множество - множество точек плоскости, точнее пар вида , где и являются координатами.

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

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

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

Тогда .

В явном виде

Для любого множества определим тождественное отношение и универсальное отношение следующим образом:

Таким образом, . Так как , то является отношением на и называется пустым отношением.

Пусть отношение определено в соответствии с изображением на рис. 1. Свяжем с каждым бинарным отношением между и - область определения и область значений . Они определяются следующим образом.

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

Рис.1.

Пусть - бинарное отношение. Определим обратное отношение следующим образом:

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

1.2. Графические представления отношений

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

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

Координатный метод

Пусть дано множество и отношения:

тождественное , универсальное и некоторое отношение .

Координатный метод относится к традиционной аналитической геометрии (рис. 2).

Рис. 2.

Линейно-координатный метод

Для преодоления недостатка предыдущего метода можно опустить точки и соединить стрелкой и , когда принадлежат отношению. Иллюстрация предыдущего примера линейно-координатным методом показана на рис. 3.

Рис.3.

Линейный метод

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

Рис. 4.

Графовый метод

Элементы множества, на котором строится отношение, представлены вершинами графа, а сами отношения - дугами графа (рис. 5). Так как точки в областях и одни и те же, их можно объединить.

Рис.5.

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

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

Пусть - отношение на множестве .

Тогда

а) рефлексивно, если для ;

б) симметрично, если влечет ;

в) транзитивно, если и влечет ;

г) антисимметрично, если и влекут .

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

Рис. 6.

В семье, состоящей из двух братьев и и сестры , имеем ситуацию: отношение не симметрично, так как , но не ; не антисимметрично, так как и , хотя и и различны.

В более общей ситуации мы можем интерпретировать рассмотренные выше характеристики отношений путем построения диаграмм:

a) отношение рефлексивно тогда и только тогда, когда для каждого узла на диаграмме существует стрелка-петля;

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

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

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

Рис. 7.

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

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

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

Пример 2. Отношение, определяемое на множестве всех программ

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

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

Бинарное отношение R на множестве X называется отношением порядка, если имеют место

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

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

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

- Рефлексивно: .

Напротив, отношение строгого порядка

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

Обычно отношение строгого порядка обозначается знаком <, а отношение нестрогого порядка — знаком .

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

- Полнота: .

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

Рефлексивное, транзитивное, антисимметричное отношение называется частичным порядком. А рефлексивное, транзитивное (но не обязательно антисимметричное!) отношение называется квазипорядком (или предпорядком).

2.3. Функции

Подмножество называется функцией, если для каждого элемента , найдется не более одного элемента такого, что ;

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

Множество образует область определения функции , множество - область значения функции . Часто вместо записи используют запись ; при этом называют аргументом или переменной, а - значением функции.

Пример. (рис. 8).

Рис.8.

Функция является отображением, если область ее определения совпадает с , т. е. . Отображение на множество называют трансформацией (преобразованием).

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций