Решение составим сокращенные таблицы истинности обеих формул
 Скачать 1.5 Mb.
|
|
Практическое занятие № 8 Отображения Пример №1. Даны отображения (числовые функции) ƒ и g. Найдите область определения и область значений отображений. Определите, являются ли они инъективными, сюръективными или биективными в найденных областях. Найдите композицию , , обратные (слева и справа) отображения: , , , . Для заданных множеств найдите , , , .. Найдите также неподвижные точки отображений. и , и . Решение: область определения отображения f– это множество таких значений х, для которых имеется вещественное число у такое, что . И, так как для любого вещественного числа х найдется число у с указанным свойством, то – множество всех вещественных чисел. Аналогично, область определения отображения . Область значений отображения f – это множество всех образов элемен тов . Тем самым, . А область значений отобра жения g – это множество всех вещественных чисел, т.е. . Отображение gявляется инъективным, поскольку для каждого , имеется ровно один (или каждый образ имеет ровно один прооб раз). Отображение f инъективным не является, т.к. для некоторых у, имеется более одного прообраза, например: для прообразами будут и . Отображение gявляется сюръективным, поскольку для каждого , имеется хотя бы один (или каждый образ имеет хотя бы один прообраз). Отображение f также является сюръективным, т.к. для каждого , имеется хотя бы один такой, что . Так как gодновременно инъективно и сюръективно, то оно является биективным отображением. Найдем композицию отображений: , . Отображение f обратимо справа, как сюръекция. И , где . Из выражения найдем x. Тогда и , где . При этом, – тождественное отображение при . Отображение g обратимо как слева, так и справа, как биекция. И , где y любое. Из выражения следует: И при этом: и – тождественные отображения. По свойствам композиции , где , поэтому Аналогично, , где , Найдем неподвижные точки. По определению это такие х, что: и . Таким образом, . Отсюда и т. к. дискрими нант , то – две неподвижные точки f(x). Из следует, что и – неподвижная точка . Пример №2. Найти композицию соответствий и множества B,C, если известно множество , законы и , . Решение: По определению композиция это: , в свою очередь, композиция законов это: . Значит, для нахождения композиции графиков нужно в график R вместо переменной x подставить график . Для получения значений элементов множества В, нужно применить закон G к элементам множества . Получение значений элементов множества С возможно двумя способами: первый – применить закон R к элементам множества ; второй – применить композицию графиков ко множеству . Результаты двух спосо бов совпадают. Все компоненты найдены и композиция соответствий бу дет иметь вид: Задания для самостоятельного выполнения: 1. Даны отображения (числовые функции) ƒ и g. Найдите область определения и область значений отображений. Определите, являются ли они инъективными, сюрьективными или биективными в найденных областях. Найдите композицию , обратные (слева и справа) отображения: . Для заданных множеств найдите . Найдите также неподвижные точки отображений: a. b. c. e. f. g. h. I j k. l. m. n. o. q. r. s. t. u. p. 2. Найти композицию соответствий S Г и множества B,C. a. b. c. d. e. f. g. h. i. j. k. l. m. n. o. p. q. r. s. t. Практическое занятие № 9, 10 Графы Пример №1. Дан граф T: Задать данный граф матрицей смежности и инцидентности. Решение: Матрица инцидентности – это прямоугольная матрица, число строк которой равно числу вершин, количество столбцов – числу дуг (ребер) графа. На пересечении строки и столбца ставится 1, если вершина является началом дуги, -1 – если концом дуги, 0 – если вершина и дуга не инцидентны.
Матрица смежности – это квадратная матрица, размер которой определяется числом вершин в графе. На пересечении строки и столбца ставится 1, если вершины инцидентны и 0 в противном случае.
Пример №2. Для данного графа (см. пример №1) вычислить хроматическое число h(T). Решение:
Минимальное покрытие столбцов строками является множество {E1, E2, E5}. Следовательно, хроматическое число графа h(T)=3 Пример №3. По заданной матрице смежности определить число маршрутов длины 3 между любой парой вершин в графе:
Восстановить маршрут из вершины С в вершину А. Решение: Вычислим последовательно степени матрицы S. Из полученной матрицы S3 следует, что имеется два (A-A)-маршрута длины 3, четыре (B-A)-маршрута длины 3, один (C-A)-маршрут длины 3, три (D-A)-маршрута длины 3, т.е. число в (i, j) ячейке определяет количество маршрутов длины 3 из i-ой вершины в j-ую вершину. Восстановим (C-A)-маршрут: элемент , равный единице, был получен в результате умножения элементов и , в свою очередь элемент получился путем умножения и . Тем самым, в формировании элемента участвовали элементы , и матрицы смежности, поэтому (C-A)-маршрут есть последовательность вершин (C, B, D, A). Пример №4. По заданной матрице определить сильные компоненты связности графа:
Решение:Максимальная степень, в которую надо возвести матрицу смежность для определения сильных компонент связности равна диаметру графа. Для данного графа диаметр равен 3. Возведём матрицу смежности в 3 степень: Компоненте сильной связности в матрице достижимости соответствует подматрица максимального размера, каждый элемент которой не равен 0. В данной матрице можно выделить три подматрицы:, (2), (2). Это значит, что граф, описанный матрицей смежности имеет три сильные компоненты: {A, B, C}, {D}, {E}. |