Формула включений и исключений

ï A È B ï = ï A ï + ï B ï – ï A Ç B ï

 

5. Декартово произведение множеств. Соответствие. Пустое соответствие, полное соответствие. Область определения, прообраз (Dom) соответствия. Область зна­чений, образ (Im) соответствия. Всюду определенные и сюръективные соответст­вия. Образ (im) и прообраз (coim) элемента. Соответствие как частично опреде­ленная многозначная функция. - декартово произведение (множество всех упорядоченных пар)

Соответствием между множествами А и В называется некоторое подмножество R их декартова произведения: . Если a Î A, b Î B и (a, b) Î R, то пишут также R (a, b) или aRb. Если R = Æ — пустое множество, то соответствие называется пустым, а если R = A ´ B, то соответствие на­зывается полным.

Пусть R Í A ´ B. Областью определения Dom R называется множество элементов a Î A, для каждого из которых найдется хотя бы один элемент b Î B такой, что aRb. Обла­стью значений, или образом, Im R соответствия R называется множество элементов b Î B, для каждого из которых найдется хотя бы один элемент a Î A такой, что aRb. Со­ответствие R называется всюду определенным, если Dom R = A, и сюръективным, если Im R = B.

Для каждого a Î A множество элементов b Î B таких, что aRb, называется образом a относительно R и обозначается im _R a. Прообразом элемента b Î B относительно R на­зывается множество элементов a Î A таких, что aRb; прообраз обозначается coim _R b.

Каждое соответствие однозначно определяет функцию a ® im _R a, которая отображает множество A в множество подмножеств B. Обратно, всякая функция f из множества A в множество подмножеств B определяет некоторое соответствие R (f): aR (f) b тогда и только тогда, когда b Î f (a). Указанные сопоставления взаимно однозначны, что по­зволяет рассматривать соответствия как частично определенные многозначные функ­ции.

 

6. Способы задания соответствий. Инволюция (обращение) соответствий. Объеди­нение, пересечение, дополнение, произведение соответствий.

Соответствием между множествами А и В называется некоторое подмножество R их декартова произведения: . Для конечных множеств A и B широко используются матричное и графовое представле­ния соответствия. Пусть A = { a ₁, a ₂,..., a_n }, B = { b ₁, b ₂,..., b_m } и R Í A х B. Соответствию R сопоставляется матрица размера n х m, строки которой помечены элементами из A, столбцы - элементами из B, а на пересечении строки a_i и столбца b_j стоит 1, если a_i R b_j , и 0 в противном случае. Например,

A = { a, b, c }, B = { x, y },

R = {(a, x), (a, y), (b, y), (c, x)}.

Каждая матрица подобного вида однозначно определяет соответствие между A и B.

При графовом представлении элементы множеств A и B изображаются точками на плоскости. Обычно эти точки обозначаются теми же символами, что и соответст­вующие элементы. Точки a и b соединяются направленной дугой от a к b, если aRb.

Инволюция (обращение соответствия): если R Í A x B, то инволюция R ^# состоит из та­ких пар (b, a), что (a, b) Î R. Иногда вместо R ^# пишут R ^-1. Ясно, что R ^## = R. Для бинарных отношений обычным образом определены теоретико-множественные операции объединения, пересечения и т.д. Дополнение соответствия: Произведение: Если R Í A x B, S Í B x C, то произведение состоит из таких пар (a, c), для которых найдется элемент b Î B такой, что (a, b) Î R, (b, c) Î S.

 

 

7. Функцио­нальные соответствия, их связь с графиками функций.

Соответствие называется функциональным (однозначным), если любому элементу множества соответствует единственный элемент множества . Соответствие называется инъективным, если оно является функциональным, и при этом каждый элемент множества имеет не более одного прообраза. Соответствие называется взаимнооднозначным (биективным), если любому элементу множества соответствует единственный элемент множества , и наоборот. Можно сказать также, что соответствие является взаимнооднозначным, если оно является полностью определённым, сюръективным, функциональным, и при этом каждый элемент множества имеет единственный прообраз.

Пример 1. а) Англо-русский словарь устанавливает соответствие между множествами слов русского и английского языка. Оно не является функциональным, так как почти каждому русскому слову соответствует несколько английских переводов; оно, также, не является, как правило, полностью определённым соответствием, так как всегда существуют английские слова, не включённые в данный словарь. Таким образом, это частичное соответствие. б) Соответствие между аргументами функции и значениями этой функции является функциональным. Однако оно не является взаимнооднозначным, так как каждому значению функции соответствуют два прообраза и . в) Соответствие между расположенными на шахматной доске фигурами и занимаемыми ими полями является взаимно однозначным.

 

8. Соответствие Галуа и его роль в проективном распознавании образов. Замкнутое подмножество.

Соответствием между множествами А и В называется некоторое подмножество R их декартова произведения: . Всякое соответствие R Í A ´ B устанавливает т.н. соответствие Галуа между подмножествами множества A и подмножествами множества B.

· Именно, если X Í A, то через G (X) обозначается пересечение Ç a Î Xim R a;

· Аналогично, для Y Í B вводится множество G^–1(Y)= Ç b Î Y coim R b.

· Пусть X * = G^–1 (G (X)), Y * = G(G^–1(Y)), тогда X Í X *, Y Í Y *;

Подмножество X Í A (Y Í B) называется замкнутым, если X = X * (Y = Y *). Соответствие Галуа устанавливает биективное соответствие между замкнутыми подмножествами в A и B.

 

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

Отношение -произвольное подмножество R множества Aⁿ всех кортежей (упорядоченных наборов) вида (a₁,..., a_n), где a₁,..., a_n -элементы некоторого множества A; в этом случае говорят, что R есть n -мерное отношение на A.

Двухмерные отношения называются бинарными. Если R - бинарное отношение, то вместо (a, b) Î R, часто пишут aRb. Пример. Бинарные отношения на множестве точек координатной плоскости.

Частным случаем понятия отношения является соответствие.

Пусть A = { a ₁, a ₂,..., a_n }, B = { b ₁, b ₂,..., b_m } и R Í A ╢ B. Соответствию R сопоставляется матрица размера n ╢ m, строки которой помечены элементами из A, столбцы - элемен­тами из B, а на пересечении строки a_i и столбца b_j стоит 1, если a_i R b_j , и 0 в противном случае. Например,

A = { a, b, c }, B = { x, y },

R = {(a, x), (a, y), (b, y), (c, x)}.

Тогда R сопоставляется матрица:

Каждая матрица подобного вида однозначно определяет соответствие между A и B. При графовом представлении элементы множеств A и B изображаются точками на плоскости. Обычно эти точки обозначаются теми же символами, что и соответст­вующие элементы. Точки a и b соединяются направленной дугой от a к b, если aRb.

Пусть R Í A ´ A. Соответствие R называется:

· рефлексивным, если для

· антирефлексивным (для )

· симметричным, если

· антисимметричным, если

· асимметричным, если R Ç R # = Æ;

· транзитивным, если

Отношение R называется:

a) эквивалентностью, если оно рефлексивно, симметрично и транзитивно

b) толерантностью, если оно рефлексивно и симметрично;

c) предпорядком, если оно рефлексивно и транзитивно;

d) порядком, если оно транзитивно и антисимметрично.