В данном пункте мы вводим декартовы произведения, отношения, функции и графы. Изучаем свойства этих математических моделей и связи между ними. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

В данном пункте мы вводим декартовы произведения, отношения, функции и графы. Изучаем свойства этих математических моделей и связи между ними.



Декартово произведение и перечисление его элементов. Декартовым произведением множеств 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.

Рис. 1.2. Ориентированный граф бинарного отношения

В полученном ориентированном графе любая пара вершин соединяется не более чем одной стрелкой. Такие ориентированные графы называются простыми. Если не рассматривать направление стрелок, то мы приходим к следующему определению:

Определение 3. Простым (неориентированным) графом G=(V,E) называется пара, состоящая из множества V и множества E, состоящего из некоторых неупорядоченных пар { v1,v2 } элементов v1,v2 Î V таких, что v1¹v2. Эти пары называются ребрами, а элементы из Vвершинами.

Множество E определяет бинарное симметричное антирефлексивное отношение, состоящее из пар (v1,v2), для которых { v1,v2E. Вершины простого графа изображаются как точки, а ребра – как отрезки. На рис. 1.3 изображен простой граф с множеством вершин V= {1, 2, 3, 4} и множеством ребер E = {{1,2}, {1,3},{1,4}, {2,3}, {2,4}, {3, 4}}.
Рис. 1.3. Простой неориентированный граф K4

Операции над бинарными отношениями. Бинарным отношением между элементами множеств 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, akT равносильно существованию такого aj Î A, что (ai, ajR и (aj, akS, то коэффициент 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 с.)