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

Декартово произведение и перечисление его элементов. Декартовым произведением множеств A и B называется множество, состоящее из упорядоченных пар: A ´ B ={(a, b): (a Î A) & (b Î B)}. Для множеств A₁, …, A_n декартово произведение определяется по индукции

В случае произвольного множества индексов I декартово произведение семейства множеств { A_i } _iÎI определяется как множество, состоящее из таких функций f: I ® A_i, что для всех iÎI верно f(i) Î A_i.

Теорема 1. Пусть A и B – конечные множества. Тогда | A ´ B| = | A|×|B|.

Доказательство. Пусть A={a₁, …, a_m}, B={b₁, …, b_n}. Элементы декартового произведения можно расположить с помощью таблицы

(a₁,b₁), (a₁,b₂), …, (a₁,b_n),

(a₂,b₁), (a₂,b₂), …, (a₂,b_n),

…

(a_m,b₁), (a_m,b₂),…, (a_m,b_n),

состоящей из n столбцов, каждый из которых состоит из m элементов. Отсюда |A ´ B|=mn.

Следствие 1. .

Доказательство. C помощью индукции по n. Пусть формула верна для n. Тогда

Отношения. Пусть n³1 – положительное целое число и A₁, …, A_n - произвольные множества. Отношением между элементами множеств A₁, …, A_n или 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=Id_B и gf=Id_A.

Доказательство. Пусть f – биекция. В силу сюръективности f, для каждого y Î B можно выбрать элемент x Î A, для которого f (x)= y. В силу инъективности f, этот элемент будет единственным, и мы обозначим его через g (y)= x. Получим функцию . По построению функции g, имеют место равенства f (g (y))= y и g (f (x))= x. Значит, верно fg=Id_B и gf=Id_A. Обратное очевидно: если fg=Id_B и gf=Id_A, то 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, состоящего из некоторых неупорядоченных пар { v₁,v₂ } элементов v₁,v₂ Î V таких, что v₁¹v₂. Эти пары называются ребрами, а элементы из V – вершинами.

Множество E определяет бинарное симметричное антирефлексивное отношение, состоящее из пар (v₁,v₂), для которых { v₁,v₂ }Î 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},

Rⁿ=R°(R^n-1),

.

Пусть Id_A = {(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.

Обозначим Id_A через 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 ={ a₁, a₂, …, a_m } и B ={ b₁, b₂, …, b_n } – конечные множества. Матрицей бинарного отношения R Í A ´ B называется матрица с коэффициентами

Пусть A – конечное множество, | A |= n и B = A. Рассмотрим алгоритм вычисления матрицы композиции T = R°S отношений R, S Í A ´ A. Обозначим коэффициенты матриц отношений R, S и T соответственно через r_ij, s_ij и t_ij. Поскольку свойство (a_i, a_k)Î T равносильно существованию такого a_j Î A, что (a_i, a_j)Î R и (a_j, a_k)Î S, то коэффициент t_ik будет равен 1, если и только если существует такой индекс j, что r_ij =1 и s_jk =1. В остальных случаях t_ik равен 0. Следовательно, t_ik = 1 тогда и только тогда, когда . Отсюда вытекает, что для нахождения матрицы композиции отношений нужно перемножить эти матрицы и в полученном произведении матриц ненулевые коэффициенты заменить на единицы. Следующий пример показывает, как этим способом вычисляется матрица композиции.

Пример 2. Рассмотрим бинарное отношение на A={1,2,3}, равное R={(1,2),(2,3)}. Запишем матрицу отношения R. Согласно определению, она состоит из коэффициентов r₁₂ =1, r₂₃ =1и остальных r_ij = 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.

Поиск по сайту: