- •Введение
- •Предисловие
- •1. Теория множеств
- •1.1. Понятие множества
- •1.2. Операции над множествами
- •1.3. Основные тождества алгебры множеств
- •1.4. Кортежи и декартово произведение множеств
- •1.5. Бинарные отношения. Свойства отношений
- •1.6. Соответствия. Отображения. Функции
- •Вопросы для самопроверки
- •2. Элементы комбинаторики
- •Вопросы для самопроверки
- •3. Логические операции
- •3.1. Основные понятия
- •3.2. Простейшие связки (операции)
- •3.3. Другие связки (операции)
- •3.4. Основные законы, определяющие свойства введенных логических операций.
- •4. Булевы функции
- •4.1. Основные понятия
- •4.2. Свойства элементарных булевых функций
- •4.3. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний
- •4.4. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
- •Задачи по теме «Булевы функции.»
- •Вопросы для самопроверки
- •5. Теория графов
- •5.1. Ориентированные графы
- •5.2. Неориентированные графы
- •5.3. Матричное задание ориентированных графов
- •5.4. Матричное задание неориентированных графов
- •5.5. Изоморфизм графов
- •5.6. Операции над графами
- •5.7. Пути, контуры, маршруты, цепи, циклы
- •5.8. Расстояние в графах
- •5.9. Связность в неориентированных графах
- •5.10. Связность в ориентированных графах
- •5.11. Эйлеровы графы
- •5.12. Гамильтоновы графы
- •5.13. Деревья
- •5.14. Остовные деревья
- •5.15 Взвешенные графы. Экстремальные остовы графов
- •5.16 Поиск кратчайшего пути между вершинами. Алгоритм Дейкстры
- •5.17 Раскраска графов. Раскраска вершин графа
- •Вопросы для самопроверки
- •Библиографический список
- •Оглавление
- •Подписано к изданию «8» октября 2014.
- •394026 Воронеж, Московский просп., 14
1.6. Соответствия. Отображения. Функции
Если для каждого элемента указан элемент , то говорят, что между множествами X и Y установлено соответствие Г, состоящее из множества упорядоченных пар (x,y), таких, что и y Y : Г .
Образом элемента x при соответствии Г называется множество Im(x) элементов , соответствующих элементу x.
Прообразом элемента y при соответствии Г называется множество Coim(y) элементов x, переводящихся соответствием в элемент y.
Множество прообразов создают область определения X (область отправления соответствия), а множество образов образуют область значений Y (область прибытия соответствия).
Для каждого соответствия существует обратное соответствие , которое любому y Y сопоставляет x X, причем ={(y,x) (x,y) }.
Частным случаем соответствия является однозначное отображение , которое каждому элементу х Х сопоставляет единственный элемент у Y . При отображении соответствие между х и у записывается в виде у = (x), a само отображение определяет запись : X Y, при этом Х называется областью определения отображения, Y – областью значений. Говорят, что отображает Х на Y.
Многозначное отображение возникает, если некоторым значениям х Х соответствует более чем один элемент.
Если Х – область определения, а Y – область значений отображения , то Если отображает Х на Y и Y Z , то говорят о композиции отображений.
Рассмотрим свойства отображений.
Отображение : X Y называется сюрьективным, или сюръекцией, если любой y Y есть образ по крайней мере одного х Х.
Пример 1.8. Отображение : {1, 2, 3, 4} {у , у , y } с условиями , не является сюрьективным (не все y имеют прообразы).
Отображение : X Y называется инъективным, или инъекцией, если каждый элемент y Y имеет хотя бы один прообраз х Х либо вообще не имеет прообраза.
Пример 1.9. Пусть Х = {1, 2, 3}, Y = {у , у , y , }, Отображение : инъективно, если , , . Все значения x имеют образы.
Если отображение одновременно является сюръективным и инъективным, то оно называется биективным отображением или биекцией.
Пример 1.10. Пусть Х={1, 2,3}, Y={у , у , y }. Отображение биективно, если , , .
При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества, при этом определено обратное отображение, которое обладает тем же свойством. Поэтому биективное отображение называют ещё взаимно-однозначным отображением (соответствием). Биективное отображение определяет взаимно однозначное соответствие между множествами Х и Y, которые считаются эквивалентными (равномощными).
Если для каждого х, такого что (х,у) f, имеется единственный образ, то соответствие называется функциональным и определяет функцию f на множестве Х со значениями в множестве Y.
Подмножество называется функцией, если для каждого элемента найдется не более одного элемента , такого, что . Если для каждого элемента имеется один элемент вида , то функция называется полностью определенной. Множество образует область определения функции , множество область значений функции . Часто вместо записи используется запись . При этом элемент называется аргументом или переменной, а у - значением функции, функцией или образом элемента х при отображении .
Функция вида называется n-местной функцией. В этом случае принято считать , что функция имеет n аргументов: .
Функция называется инъективной, если для любых из и следует, что (все x имеют свои y).
Функция f называется сюръективной, если для любого элемента существует элемент такой, что у = f (х) (все y имеют свои x).
Функция f называется биективной, если f одновременно сюръективна и инъективна.
Если существует биективная функция f, то говорят, что f осуществляет взаимно - однозначное соответствие между множествами и .
Если функция f задает отображение , a функция g задает отображение , то функция F, соответствующая отображению и определенная для каждого формулой , называется композицией функций f и g или сложной функцией. Например, композицией отображения и отображения является отображение .
Если функция f задает отображение , совокупность всевозможных упорядоченных пар вида , образует функцию, которая называется обратной функцией для функции f и обозначается . Обратная функция ставит в соответствие каждому элементу у его прообраз (y). Заметим, что для того, чтобы являлась функцией, достаточно, чтобы функция f была инъективной.
Пример 1.11. Функция инъективна при отображении , но не сюрьективна (не все y имеют соответствующие значения аргументов);
Функция биективна.
К специальным отображениям относятся понятия оператора и функционала.