лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4

• Название: Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
• Анкор: лекции по дм
• Дата: 08.02.2021
• Размер: 1.51 Mb.
• Имя файла: лекции.docx
• Тип: Документы; #174835
• страница: 10 из 40

Рефлексивное замыкание отношений

Пусть тождественное отношение Е состоит из упорядоченных пар самого себя – . Тогда R*=RE (R* – рефлексивное замыкание, а R – транзитивное замыкание).

Если R транзитивно и рефлексивно, то R*=R.

Пример. Используя R – отношение на N такое, что получим .

Алгоритм Уоршалла.

Вход: отношение, заданное матрицей R.

Выход: транзитивное замыкание отношения, заданное матрицей Т.

S := R

for i from 1 to n do

for j from 1 to n do

for k from 1 to n do

T[j, k] := S[j, k] V S[j, i] & S[i, k]

end for

end for

S := T

end for
Заметим, что нас не интересует число путей любой конкретной длины из вершины v_i в вершину v_j. Эта информация, получаемая в процессе вычисления степеней A, далее игнорируется. Для того, чтобы сократить объем вычислений, можно отказаться от получения указанной информации и использовать в вычислениях просто реализуемые булевские матричные операции, которые мы определим согласно.

Обозначим булевскую сумму C двух матриц A и B размера n*n как С=АВ, а булевское произведение – D=AB.

Элементы матриц C и D задаются соотношениями



Заметим, что элемент d_ij легко получается путем просмотра i-й строки матрицы A слева направо и одновременно j-го столбца матрицы B сверху вниз. Если k-й элемент в строке матрицы A и k-й элемент в столбце матрицы B равны 1 для какого-нибудь k, то d_ij=1. В противном случае d_ij=0.

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

Матрица смежностей, так же как и путевая матрица, является булевской матрицей. Заметим, что .

Единственная разница между A² и A⁽²⁾ заключается в том, что A⁽²⁾ является булевской матрицей и элемент на пересечении i-й строки и j-го столбца A⁽²⁾ равен 1 в том случае, когда существует по крайней мере один путь длины 2 из v_i в v_j. Аналогичное положение имеет место для A³ и A⁽³⁾ и в общем случае для A^r и A^(r) при любом целом положительном r. Из этих рассуждений ясно, что матрица достижимости P задается выражением



Например, если

то



Данный метод получения матрицы достижимости ориентированного графа называется алгоритмом Уоршалла (Warshall S.A. A Theorem on Boolean Matrices. - J.ACM, 1962, 9, pp.11-12).
Тема 5. Функции и отображения. Инъекция, сюръекция, биекция. Представление функций в ЭВМ. Операции. Свойства бинарных операций: ассоциативность, коммутативность, дистрибутивность слева и справа. Способы задания операций. Таблица Кэли.

Функции и отображения. Инъекция, сюръекция, биекция.

Понятие “функции” является одним из основополагающих в математике, в данном случае подразумевается прежде всего функции, отображающие одно конечное множество объектов в другое конечное множество, мы избегаем использование термина “отображение” и предпочитаем слово “функция” в расчете на постоянное сопоставление читателем математического понятия функции с понятием функции в языках программирования .

Определения 5.1. Говорят, что между множествами А и В определено соответствие Г, если задано некоторое произвольное подмножество декартового произведения .

Определения 5.2. Отображением множества А на множество В называется такое соответствие, которое каждому элементу сопоставляется по крайней мере один элемент . Тогда элемент b называется образом элемента а, a a – прообразом элемента b, или переменной, или аргументом.

Определения 5.3. Соответствие, при котором каждому аА сопоставляется один и только один элемент bB, , называется функциональным соответствием, или функцией из А в В, и обозначается следующим образом или .

Если b=f(a) , то а называют аргументом, а b – значением функции.

Замечание.

Вообще всякому отношению R из A в В можно сопоставить (тотальную) функцию (эта функция называется характеристической функцией отношения), полагая

Пусть , тогда

Область определения функции: .

Область значения функции: .

Определения 5.4.Если ,то функция называется тотальной, а если , то – частичной.

Определения 5.5. Суждением функции на множестве называется функция , определяемая следующим образом: .

Для тотальной функции .

Определения 5.6.Функция называется функцией n аргументов, или n-местной функцией.
Инъекция, сюръекция и биекция.

Пусть . Тогда функция является:

Инъективной, или инъекцией, если .

Сюръективной, или сюръекцией, если .

Биективной, или биекцией, если она инъективная и сюръективная.
Замечание.

Биективную функцию также называют взаимно однозначной.
Рис.5.1. иллюстрирует понятия отношения, функции, инъекции, сюръекции и биекции.



Рисунок 5.1.

Теорема.

Если – тотальная биекция ( ), то отношение (обратная функция) является биекцией.

Доказательство.

Поскольку – биекция, имеем

.

Покажем, что – функция.



Поскольку .

Тогда .

Покажем, что – инъекция. Пусть .

Тогда . Покажем от противного, что – сюръекция.

Пусть . Тогда . Обозначим этот элемент . Имеем: .
Индуцированная функция.

Пусть и пусть . Тогда множество

называется образом множества , а множество – прообразом множества . Заметим, что F является отношением из множества в множество .



Теорема.

Если – функция, то и – тоже функции
Замечание.

называется индуцированной функцией, а -переходам к прообразам.