Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
В данном пункте мы вводим декартовы произведения, отношения, функции и графы. Изучаем свойства этих математических моделей и связи между ними.
Декартово произведение и перечисление его элементов. Декартовым произведением множеств A и B называется множество, состоящее из упорядоченных пар: A ´ B ={(a, b): (a Î A) & (b Î B)}. Для множеств A1, …, An декартово произведение определяется по индукции
В случае произвольного множества индексов I декартово произведение семейства множеств { Ai } iÎI определяется как множество, состоящее из таких функций f: I ® Ai, что для всех iÎI верно f(i) Î Ai. Теорема 1. Пусть A и B – конечные множества. Тогда | A ´ B| = | A|×|B|. Доказательство. Пусть A={a1, …, am}, B={b1, …, bn}. Элементы декартового произведения можно расположить с помощью таблицы (a1,b1), (a1,b2), …, (a1,bn), (a2,b1), (a2,b2), …, (a2,bn), … (am,b1), (am,b2),…, (am,bn), состоящей из n столбцов, каждый из которых состоит из m элементов. Отсюда |A ´ B|=mn. Следствие 1. . Доказательство. C помощью индукции по n. Пусть формула верна для n. Тогда
Отношения. Пусть n³1 – положительное целое число и A1, …, An - произвольные множества. Отношением между элементами множеств A1, …, An или n-арным отношением называется произвольное подмножество . Бинарные отношения и функции. Бинарным отношением между элементами множеств A и B (или, коротко, между A и B) называется подмножество R Í A ´ B. Определение 1. Функцией или отображением называется тройка, состоящая из множеств A и B и подмножества fÍA´B (графика функции), удовлетворяющего следующим двум условиям 1. Для любого xÎA существует такой yÎf, что (x,y) Îf. 2. Если (x, y)Îf и (x, z) Îf, то y=z Легко видеть, что f Í A ´ B будет тогда и только определять функцию, когда для любого x Î A существует единственный y Î f, что (x, y) Î f. Этот y обозначим через f (x). Функция называется инъекцией, если для любых x, x’ Î A, такихчто x¹x’ имеет место f(x)¹f(x’). Функция называется сюръекцией, если для каждого y Î B существует такой x Î A, что f (x)= y. Если функция является инъекцией и сюръекцией, то она называется биекцией. Теорема 2. Для того, чтобы функция была биекцией, необходимо и достаточно существования такой функции , что fg=IdB и gf=IdA. Доказательство. Пусть f – биекция. В силу сюръективности f, для каждого y Î B можно выбрать элемент x Î A, для которого f (x)= y. В силу инъективности f, этот элемент будет единственным, и мы обозначим его через g (y)= x. Получим функцию . По построению функции g, имеют место равенства f (g (y))= y и g (f (x))= x. Значит, верно fg=IdB и gf=IdA. Обратное очевидно: если fg=IdB и gf=IdA, то f сюръекция в силу f (g (y))= y, для каждого y Î B. В этом случае из будет следовать , и значит . Следовательно f – инъекция. Отсюда вытекает, что f – биекция.
Образ и прообраз. Пусть – функция. Образом подмножества XÍA называется подмножество f(X) = {f(x): xÎX }Í B. Для YÍ B подмножество f- -1(Y)={xÎA: f(x)ÎY} называется прообразом подмножества Y. Отношения и графы. Бинарные отношения можно наглядно показать с помощью ориентированных графов. Определение 2. Ориентированным графом называется пара множеств (E,V) вместе с парой отображений s,t: E®V. Элементы множества V изображаются точками на плоскости и называются вершинами. Элементы из E называются направленными ребрами или стрелками. Каждый элемент eÎE изображается в виде стрелки (возможно, криволинейной), соединяющей вершину s(e) с вершиной t(e). Произвольному бинарному отношению R Í V ´ V соответствует ориентированный граф с вершинами v Î V, стрелками которого являются упорядоченные пары (u,v) ÎR. Отображения s,t: R®V определяются по формулам s(u,v)=u и t(u,v)=v. Пример 1. Пусть V={1,2,3,4}. Рассмотрим отношение R={(1,1), (1,3), (1.4), (2,2), (2,3), (2,4), (3,3), (4,4) }. Ему будет соответствовать ориентированный граф (рис. 1.2). Стрелками этого граф будут пары (i,j) ÎR.
В полученном ориентированном графе любая пара вершин соединяется не более чем одной стрелкой. Такие ориентированные графы называются простыми. Если не рассматривать направление стрелок, то мы приходим к следующему определению: Определение 3. Простым (неориентированным) графом G=(V,E) называется пара, состоящая из множества V и множества E, состоящего из некоторых неупорядоченных пар { v1,v2 } элементов v1,v2 Î V таких, что v1¹v2. Эти пары называются ребрами, а элементы из V – вершинами. Множество E определяет бинарное симметричное антирефлексивное отношение, состоящее из пар (v1,v2), для которых { v1,v2 }Î E. Вершины простого графа изображаются как точки, а ребра – как отрезки. На рис. 1.3 изображен простой граф с множеством вершин V= {1, 2, 3, 4} и множеством ребер E = {{1,2}, {1,3},{1,4}, {2,3}, {2,4}, {3, 4}}.
Операции над бинарными отношениями. Бинарным отношением между элементами множеств A и B называется произвольное подмножество R Í A´B. Запись aRb (при a Î A, b Î B) означает, что (a,b) Î R. Определены следующие операции над отношениями RÍ A´A: R -1={(a,b): (b,a)ÎR}, R° S={(a,b): ($ xÎA)(a,x)ÎR & (x,b)ÎR}, Rn=R°(Rn-1), . Пусть IdA = {(a,a): aÎA} – тождественное отношение. Отношение R Í X ´ X называется (1) рефлексивным, если (a,a)ÎR для всех a Î X, (2) антирефлексивным, если (a,a)ÏR для всех a Î X, (3) симметричным, если для всех a, b Î X верна импликация aRb ÞbRa, (4) антисимметричным, если aRb & bRa Þ a=b, (5) транзитивным, если для всех a, b, c Î X верна импликация aRb & bRc Þ aRc, (6) линейным, для всех a, b Î X верна импликация a¹b Þ aRb Ú bRa. Обозначим IdA через Id. Легко видеть, что имеет место следующее Предложение 1. Отношение R Í X´X (1) рефлексивно Û Id Í R, (2) антирефлексивно Û RÇId= Æ, (3) симметрично Û R = R-1, (4) антисимметрично Û R Ç R-1 Í Id, (5) транзитивно Û R°RÍ R, (6) линейно Û R ÈId È R-1 = X ´ X. Матрица бинарного отношения. Пусть A ={ a1, a2, …, am } и B ={ b1, b2, …, bn } – конечные множества. Матрицей бинарного отношения R Í A ´ B называется матрица с коэффициентами Пусть A – конечное множество, | A |= n и B = A. Рассмотрим алгоритм вычисления матрицы композиции T = R°S отношений R, S Í A ´ A. Обозначим коэффициенты матриц отношений R, S и T соответственно через rij, sij и tij. Поскольку свойство (ai, ak)Î T равносильно существованию такого aj Î A, что (ai, aj)Î R и (aj, ak)Î S, то коэффициент tik будет равен 1, если и только если существует такой индекс j, что rij =1 и sjk =1. В остальных случаях tik равен 0. Следовательно, tik = 1 тогда и только тогда, когда . Отсюда вытекает, что для нахождения матрицы композиции отношений нужно перемножить эти матрицы и в полученном произведении матриц ненулевые коэффициенты заменить на единицы. Следующий пример показывает, как этим способом вычисляется матрица композиции. Пример 2. Рассмотрим бинарное отношение на A={1,2,3}, равное R={(1,2),(2,3)}. Запишем матрицу отношения R. Согласно определению, она состоит из коэффициентов r12 =1, r23 =1и остальных rij = 0. Отсюда матрица отношения R равна . Найдем отношение R°R. С этой целью умножим матрицу отношения R на себя . Получаем матрицу отношения . Следовательно, R°R ={(1,2),(1,3),(2,3)}. Из предложения 1 вытекает Следствие 2. Если A = B, то отношение R на A (1) рефлексивно, если и только если все элементы главной диагонали матрицы отношения R равны 1, (2) антирефлексивно, если и только если все элементы главной диагонали матрицы отношения R равны 0, (3) симметрично, если и только если матрица отношения R симметрична, (4) транзитивно, если и только если каждый коэффициент матрицы отношения R°R не больше соответствующего коэффициента матрицы отношения R.
|
||||||||||
Последнее изменение этой страницы: 2017-01-19; просмотров: 290; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.210.107.64 (0.054 с.) |