Похожие работы
|
Лабораторная работа Лабораторная работа Основы теории множеств - страница №2/7
Контрольные вопросы.
Индивидуальное задание
Лабораторная работа 3. Функции и отображения. Цель. Изучить понятие функции, изучить основные типы функций и операции над функциями. Краткие теоретические положения. 1. Упорядоченная пара объектов. Пусть даны множества и . Упорядоченной парой или кортежем двух неравных объектов с компонентами и называется величина , т.е. т.е. двухэлементное множество, состоящее из одноэлементного множества- синглета , содержащего первый элемент пары – объект и двухэлементного множества - т.е. неупорядоченной пары, отражающей состав кортежа. Объект называется второй компонентой кортежа. Если объекты и совпадают, т.е. выполняется соотношение тождественности , то по определению . В этом случае по определению первая и вторая компонента кортежа совпадает с указанным единственным объектом . Теорема.(Критерий равенства двух кортежей) Для кортежей имеет место равенство в том и только том случае, если выполняется система двух равенств: . Доказательство. Нужно различать два случая. 1) . В этом случае и при мы имеем равенство , которое невозможно, т.к. множество состоит только из одного объекта – синглета , а множество содержит также двух-элементное множество . Поэтому имеет место равенство и . Получаем равенство , откуда следует, что . Таким образом, в указанном частном случае имеем т.е. указанная система выполняется. Рассмотрим второй частный случай и равенство . В случае оно невозможно, как установлено перед этим. Поэтому , и мы получаем равенство . В этом равенстве синглеты и пары должны совпадать, отсюда имеем , что равносильно данной системе . Теорема доказана. 2. Декартово произведение двух множеств. Пусть даны два множества и . Декартовым произведением первого множества на второе называется множество всех упорядоченных пар , где и , т.е. . Изобразим данное множество: Изобразим данное множество на целочисленной решетке: 3. Функция. Пусть даны два множества и . Функцией из множества в множество называется подмножество декартового произведения множеств и , обладающее свойством . Данное свойство называется функциональным свойством и означает, что для каждого значения аргумента функция сопоставляет не более одного значения . Пример. Дано начальное и конечное множества функции, - функция из в . Найти значение функции . Решение. 1) Поиск: Ищем пару вида . Результат этапа 1:Такая пара найдена и притом только одна ; 2) Выборка: Из найденной пары извлекаем второй элемент, этот элемент будет искомым значением функции . Таким образом, получаем . Ответ: . Изобразить данную функцию на решетке . Решение. 4.Область определения и область значений функции. Пусть дана функция из множества в множество . Область определения данной функции – это множество . Область значений функции - это множество .Т.е. область определения функции – это множество первых компонент кортежей, входящих в состав функции, а область значений – это множество вторых компонент. Пример. Дано . Найти . Решение. Путем анализа исходных данных сразу получаем ответ . 5. Образ множества, прообраз множества, прообраз элемента при действии функции. Пусть дана функция и подмножество . Образом подмножества при действии функции называется множество . Т.е. образ подмножества при действии функции это множество вторых компонент кортежей функции, когда первые компоненты берутся из подмножества . Пусть - подмножество конечного множества функции . Его прообразом при действии функции называется множество . Т.е. прообраз подмножества при действии функции это множество первых компонент кортежей функции, когда вторые компоненты берутся из подмножества . Пусть дан элемент его прообразом при действии функции называется множество , т.е. прообраз одноэлементного множества при действии функции . Пример. Дано , . Найти . Решение. Исходя из определения и данного состава функции непосредственно выписываем ответ: . 6. Композиция и джойн функций. Пусть даны две функции и их композицией называется функция вида . Это определение можно пояснить следующей схематической диаграммой Таким образом, при композиции первой выполняется функция , т.е. первая справа. Имеют место следующие соотношения Композиция функций и может быть записана в виде джойна этих функций , где - операция джойна (т.е. операция соединения или конкатенации). Таким образом, при операции джойна первой выполняется функция первая слева. Пример. Даны функции , где универсум и . Построить композиции и джойны , выписать их кортежный состав и табличное представление. Решение. Получим сначала табличное представление этих функций. Имеем: ,
Находим . Имеем: . Находим значения функции на всех элементах ее области определения. Имеем: , . Таким образом, получили ответ по первой части задачи: ,
Из табличного получаем кортежное представление . Так как , автоматически получаем: ,
. Таким же способом находим ответ для второй части задачи. , . Т.е.
и . Для соответствующего джойна ответ получаем автоматически:
. 6. Отображения. Инъекция, сюръекция, биекция, свойства обратимости слева и справа. Функция для которой называется всюду определенной, обозначается или и называется также отображением. Тождественным отображением на множестве называется отображение , обладающее свойством ,т.е. это отображение оставляет каждый элемент области определения на месте. Пусть - функция и - подмножество ее области определения. Сужением функции на множество называется функция . Эта функция является отображением вида . Имеет место формула: . Пример. Дано . Найти сужение . Решение. Имеем: Ответ: . Функция называется продолжением функции , если выполняется включение . Отображение называется сюръективным или сюръекцией (отображением “на”, накрытием) если , т.е. если его образ совпадает со всем конечным множеством отображения. Это условие можно записать также в виде: , т.е. каждый элемент конечного множества является образом некоторого элемента начального множества отображения. Отображение называется инъективным или инъекцией, если выполняется свойство , т.е. разные переходят в разные. Отображение называется биективным или биекцией (взаимно- однозначным отображением, перестановкой) если оно одновременно сюръекция и инъекция. Пусть дано отображение . Отображение называется левым обратным к отображению если выполняется свойство . Отображение называется правым обратным к , если . Отображение называется обратным к отображению , если оно одновременно является правым обратным и левым обратным по отношению к , т.е. если выполняются свойства . Теорема 1. Пусть имеется отображение . Оно обладает левым обратным тогда и только тогда, когда отображение является инъекцией. При этом левое обратное находится по формуле: Отображение обладает правым обратным , если является сюръекцией, при этом обратное находится по формуле: Отображение обладает как левым обратным , так и правым обратным в том и только том случае, если - биекция. В этом случае левое и правое обратные отображения совпадают, определяются однозначно и их общее значение называется обратным (двусторонним) отображением к отображению .
Пример. Функция задана C++ программой: int f(int x) { if (x>5) return x*2; else if (3 else return x%2; } Найти значение . Решение. Для большей ясности действия указанной функции построим блок-схему алгоритма данной функции: Используя входные данные осуществим прохождение от точки входа то точки выхода блок-схемы. 1) - вход в схему; 2.Безусловный 1 переход на блок 2; 3) Проверка - нет, переход по дуге 2 на блок 3; 4) Проверка - нет, переход по дуге на исполнительный блок 5; 5) Операция . Результат : 6) Безусловный переход на блок 7: 7) Вывод данных . Итак, выполняя алгоритм данной функции по указанной блок-схеме получили ответ . Лабораторная работа 3. Функции и операции над ними. Цель. Изучить понятие функции и научиться решать типовые задачи по теме “функция”. Задание. Выполнить задания 1-5, записать решения, ответить на контрольные вопросы. Задание 1. Кортежное задание функции. Даны начальное и конечные множества , функция , найти область определения , область значений функции, получить табличное представление функции. Привести визуальное изображение функции в виде двудольного орграфа. Пример выполнения. Дано . Решение. Область определения функции - это множество первых компонент ее кортежей. Получаем . Область значений- это множество вторых координат ее кортежей. Получаем . Табличное представление функции - это таблица аргумент-значение для всех элементов области определения функции. Получаем таблицу:
Изображение: Индивидуальное задание 1.
Задание 2. Образ множества, прообраз множества, прообраз элемента. Дано: Множества , функция , подмножество , подмножество , элемент . Найти: Образ подмножества , т.е. подмножество , прообраз подмножества , т.е. множество , прообраз элемента , т.е. подмножество . следующая страница >> |
|