Инъекция, сюрьекция, биекция.

Функция f: A ® B называется инъективной или инъекцией, если разным значениям функции соответствуют разные аргументы. То есть b = f (a ₁) & b = f (a ₂) Þ a ₁= a ₂.

Пример. Пусть X=[-1,1], Y=[-1,1] и f: X ® Y. В соответствии с данным определением y = x – это инъекция, а y =| x | - нет.

Функция f: A ® B называется сюръективной или сюръекцией, если область ее изменения совпадает со всем множеством B.

" b ÎB $ a ÎA | b = f (a).

Пример. Пусть X=[-1,1], Y=[-1,1] и f: X ® Y. В соответствии с данным определением y = x – это сюръекция, а y =| x | - нет.

Функция f: A ® B называется биективной или биекцией, если она инъективна и сюръективна.

В только что рассмотренном примере y = x – это биекция, а y =| x | - нет.

 

 

8. Бинарные отношения. Основные определения и способы задания отношений. Обратное отношение. Композиция отношений.

Если мы хотим определить такое понятие, как отношение, мы должны, прежде всего, ввести такое понятие, как упорядоченная пара.

Схема для иллюстрации понятия композиции отношений.

Различие между неупорядоченной парой элементов { a, b } и упорядоченной парой (a, b) обычно поясняют на примере сравнения двух пар элементов. Две неупорядоченные пары { a, b }={ c, d }, если a = b & c = d Ú a = c & b = d. Для упорядоченных пар (a, b)=(c, d) «a = b &c= d. То есть, в общем случае, для упорядоченных пар (a, b)¹(b, a). Иногда употребляют и такую запись: R =(a, b)={ a,{ a, b }}. Нетрудно догадаться, что существование множества { a, b } зависит от того, какое мы выберем a. Если a, b – числа, то мы можем описать множество упорядоченных пар в виде графика, откладывая по оси абсцисс значения a, по оси ординат значения b, для которых существует R =(a, b).

Упорядоченную пару R называют двухместным или бинарным отношением. Упорядоченный набор из n элементов (a ₁, …, a_n) называют n -местным отношением или кортежем.

Элементы для формирования упорядоченных наборов мы можем выбирать как из одного множества, так и из разных. При построении графиков, которые отображают бинарные отношения между множествами действительных чисел X и Y, мы используем так называемую декартову систему координат.

Прямым (декартовым) произведением двух множеств A и B называется множество упорядоченных пар (a, b), в которых a Î A и b Î B: A ´ B ={(a, b)| a Î A & b Î B }.

Степенью множества A называется его прямое произведение само на себя: Aⁿ = A ´…´ A – всего n раз.

Пользуясь введенным понятием прямого произведения, можно определить бинарное отношение как подмножество прямого произведения A´B: R = a r b ={(a,b)Î R | R Ì A ´ B }.

Запись a r b обозначает отношение между элементами a и b в общем виде, а запись (a,b) обозначает конкретную упорядоченную пару элементов, то есть один элемент отношения.

Если у нас задан некоторый универсум U, то мы можем рассматривать понятия принадлежности (Î), включения (Ì), и равенства (=), как отношения на B(U) – множестве всех подмножеств универсума U.

Способы задания отношений. Если отношение содержит небольшое количество пар (или наборов), его можно задать, как и множество, перечислением. Бинарные отношения, как уже говорилось, могут быть заданы в виде графиков, если A, B – числовые множества. В общем случае отношения могут быть заданы в виде таблиц или графов. В реляционных базах данных понятие «кортеж» соответствует записи в таблице, а поля таблицы с именами A, B, C,…, из которых берутся элементы записи, образуют прямое произведение множеств A ´ B ´ C ´….

Основные понятия, связанные с понятием бинарного отношения.

Пусть R = a r b ={(a,b)Î R | R Ì A ´ B }. Тогда существуют:

обратное отношение R ^-1={(b,a)|(a,b)Î R };

дополнение отношения ù R ={(a,b)|(a,b)Ï R }=(A ´ B)\ R;

тождественное отношение I ={(a,a)| a Î A };

однородное отношение: U_R ={(a,b)|aÎA&bÎA}.

Композиция отношений.

Пусть заданы два бинарных отношения: R ₁Ì A ´ B и R ₂Ì B ´ C (говорят так: отношение из A в B и отношение из B в C).

Композицией отношений R ₁ и R ₂ называется отношение R из A в C:

R = R ₁ o R ₂ ={(a, c)| a Î A & c Î C & $ b Î B: (a, b) Î R ₁ & (b, c) Î R ₂}.

Пример. Пусть A - множество студентов ФПК, B – множество специальностей, С – множество учебных курсов, изучаемых на этих специальностях. Нам нужно определить, какие дисциплины будет изучать каждый конкретный студент ФПК (что будет включать его приложение к диплому).

Здесь R ₁Ì A ´ B – «студент a Î A получает специальность b Î B», R ₂Ì B ´ C – «на специальности b Î В изучается дисциплина c Î C». Искомое отношение R – «студент a Î A изучает дисциплину cÎ C» есть композиция отношений R = R ₁° R ₂. То есть, чтобы студент a Î A изучал дисциплину c Î C нужно, чтобы он учился на специальности b Î B, что соответствует отношению a r b, и на этой специальности изучалась данная дисциплина c Î C, что соответствует отношению b r c. Значит, для решения задачи нам нужно выяснить, для каких пар (a,b) имеются пары (b,c), и из этих пар составить новые пары (a,c), взяв первый элемент из пары (a,b), а второй элемент – из пары (b,c).

Графически операцию композиции можно проиллюстрировать на следующей схеме.

В этой графической схеме каждой упорядоченной паре элементов (a,b) и (b,c) сопоставлены стрелки из множества А в множество B и из множества B в множество C соответственно. Искомым парам (a,c) соответствуют возможные переходы по стрелкам из множества A в множество C.

Теперь составим бинарные таблицы R ₁ и R ₂ для представленных данной схемой отношений. Элементы этих таблиц r_ij(1) и r_jk(2) соответствуют отношениям (a_i, b_j) и (b_j, c_k). Первая таблица будет содержать | A | строк и | B | столбцов, вторая - | B | строк и | C | столбцов. Для нашего примера таблицы будут иметь вид:

 

 

 

R ₁

 

R ₂

 

Одновременное существование отношений r_{ij (1)} и r_{jk (2)} соответствует логическому произведению (конъюнкции) элементов таблицы r_{ij (1)} × r_{ij (2)}, и значение каждого элемента r_ik итоговой таблицы R будет зависеть от того, принимает ли хотя бы одна из этих элементарных конъюнкций значение «1», что соответствует логическому сложению (дизъюнкции). Для нашего примера r ₁₁=(r ₁₁₍₁₎ ×Ú r ₂₁₍₁₎ Ú r ₃₁₍₁₎ Ú r ₄₁₍₁₎)×(r ₁₁Ú r ₁₂₍₂₎ Ú r ₁₃₍₂₎ Ú r ₁₄₍₂₎ Ú r ₁₅₍₂₎ Ú r ₁₆₍₂₎), и так далее. То есть при i =1,…,| A |, j =1,…,|B|, k =1,…,| C | мы имеем: R = R ₁ o R ₂ = R ₁× R ₂, где R ₁× R ₂ - логическое перемножение матриц.

Степенью отношения Rⁿ называется композиция отношения R n раз с самим собой.

Ядром отношения R Ì A ´ B называется композиция R *= R o R ^-1. Ядро отношения является отношением на A.

 

9.Однородные (универсальные) отношения. Примеры универсальных отношений. Свойства однородных отношений (рефлексивность, симметричность, транзитивность). Отношение эквивалентности и отношение порядка.

однородным отношением - отношение R = a r b ={(a,b)| a Î A & b Î A }.

однородное отношение – это отношение R Ì A ². Однородные бинарные отношения – важный тип отношений для многих приложений информатики и других разделов дискретной математики, для задач теории графов. Ребра любого графа задают однородное бинарное отношение на множестве его вершин V. Множество точек на плоскости с заданной системой координат (X,Y) – это тоже однородное бинарное отношение, где A – множество действительных чисел.

Свойства однородных отношений.

1. Рефлексивность: " a Î A имеет место отношение (a, a). То есть отношение (a, b) всегда существует при a=b. Свойство рефлексивности означает, что I Ì R.

2. Антирефлексивность: " a Î A имеет место ù(a, a). То есть отношение (a, b) не существует ни при каких a=b. Если для каких-то a=b отношение существует, а для каких-то нет, то следует говорить, что отношение просто не рефлексивно.

Примеры рефлексивных отношений на множестве точек плоскости X ´ Y:

1) R ={(x, y) | x = y };

2) R ={(x, y) | | y |<| x |+1};

3) R ={(x, y) | x + y =2 k, k =1,2,…, n }.

3. Симметричность: " a,b ÎA (a, b)ÎRÞ (b, a)ÎR. Свойство симметричности означает, что R^-1ÌR.

Симметричными отношениями на множестве точек плоскости X ´ Y являются отношения 1) и 3) из приведенных выше.

4. Антисимметричность: " a,b ÎA, a¹b, (a, b)ÎR Þ (b, a)ÏR. То есть условие симметричности не выполняется ни при каких a,b. Простейший пример антисимметричного отношения на X ´ Y – строгое неравенство x < y.

Если для каких-то a¹b симметричность выполняется, а для каких-то нет, то следует говорить, что отношение R просто не симметрично. Примером такого отношения является отношение 2).

5. Транзитивность. " a,b,c ÎA (a, b)ÎR& (b, c)ÎR Þ (a, c)ÎR. Очень важное свойство отношений.

Свойство транзитивности можно записать через степень отношения (композицию отношения с самим собой): R² =R ° R Ì R.

Антитранзитивность обычно не рассматривают, хотя можно и ее определить так же, как в первых двух случаях.

Примеры транзитивных отношений:

1) все три примера, приведенных выше;

2) x<y (в том числе и нестрогое неравенство);

3) отношение вложенности на B(U): пусть A,B,C Ì U. Если A Ì B & B Ì C Þ A Ì C.

6. Полнота (линейность): " a,b ÎA, a¹b Þ (a, b)ÎRÚ (b,a)ÎR. Полнота отношения означает, что R È R^-1 È I = U_R.

Свойство полноты, вообще говоря, довольно редкое. Пример полного отношения - неравенство x£y.

Отношения эквивалентности и отношения порядка.

Определение 1. Если однородное отношение RÌA²:

1) рефлексивно, 2)симметрично, 3) транзитивно

то оно называется отношением эквивалентности. Отношение эквивалентности часто обозначается «º», как и операция эквивалентности в логике. Множество элементов aÎA, для которых выполняется отношение эквивалентности R, называется классом эквивалентности. Класс эквивалентности будем обозначать [x]_º:

[x]_º = {y | yÎA & yºx}.

Из рассмотренных выше примеров отношениями эквивалентности являются примеры 1) и 3).

Примером отношения эквивалентности на B(U) может служить отношение равномощности множеств: |A|=|B|. То есть все подмножества из U одинаковой мощности образуют класс эквивалентности.

Определееие 2. Если однородное отношение RÌA²:

1) антисимметрично, 2) транзитивно,

то оно называется отношением порядка. Если отношение при этом еще и антирефлексивно, то это отношение строгого порядка. Отношение нестрогого порядка может быть как рефлексивным, так и просто не рефлексивным.Для обозначения отношения порядка можно использовать обычный знак неравенства.Если отношение порядка не обладает свойством полноты (линейности), то обычно говорят об отношении ча стичного порядка. В задачах дискретной математики и информатики чаще всего встречается именно этот тип отношений.

Если на множестве А определено отношение частичного порядка, то оно называется частично упорядоченным. Множество, на котором определено отношение полного порядка, называется вполне упорядоченным. Например, числовые множества – это вполне упорядоченные множества.

Теорема. На всяком конечном, непустом, частично упорядоченном множестве существует минимальный элемент y | " x¹y y<x.

Вполне упорядоченное множество содержит только один минимальный элемент, на частично упорядоченном множестве их может быть несколько. Булеан B(U), - это вполне упорядоченное множество относительно отношения вложенности (Í). Минимальным элементом в этом случае является пустое множество Æ.