Разбиения и покрытия

Пусть Ě ={E_i} для i ϵ I – некоторое семейство непустых подмножеств множества M, E_i Í M. Тогда семейство Ě называется покрытием множества M, если каждый элемент множества M принадлежит хотя бы одному из E_i:

M Í  Û " x ϵ M $  i ϵ I |  x ϵ E_i.

Семейство Ě называется дизъюнктным, если элементы этого семейства попарно не пересекаются, т.е. каждый элемент множества M принадлежит не более чем одному из множеств E_i: " i,j ϵ I, i¹j Þ E_i  Ç E_j = Ø

Дизъюнктное покрытие Ě называется разбиением множества M.

Пример

Пусть имеется множество M={1,2,3}.

Тогда семейство {{1,2}, {2,3}, {3,1}} является покрытием, но не разбиением;

семейство {{1},{2},{3}} – покрытием и разбиением,

а семейство {{1},{2}} является дизъюнктным, но в то же время не является ни покрытием, ни разбиением.

2 Отношения и функции

Рассмотрение “жизненного”, точнее, “программистского”, примера. Пусть есть три множества: D – данных, P – программ и R – результатов. Для каждой программы возможны отношения: данные для этой программы, результаты работы этой программы, и т.п. Набору данных можно сопоставить множество программ, которые могут с этими данными работать, и множество результатов, которые могут быть получены после обработки этих данных, и т.п.

Перейдем к формализации понятия “отношения”.

2.1 Прямое произведение множеств

Упорядоченная последовательность, содержа-щая n элементов некоторого множества, называется набором из n элементов. Обычно набор, образованный последовательностью a₁, a₂,…, a_n обозначается (a₁, a₂,…, a_n). При малых n говорят о двойках элементов, тройках и т.д.

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

Пример. Для множества чисел А = {1, 2, 3, 4} можно рассмотреть тройки: (1, 2, 2), (3, 4, 1), (2, 1, 2), причем первая и последняя тройки различны, несмотря на их одинаковый состав.

Прямым (или декартовым) произведением множеств А₁, А₂, …, А_n называется множество всех упорядоченных наборов (x₁ ,x₂, … x_n) таких, что x_i ϵ A_i при "i = 1, 2, …, n. Декартово произведение обозначается А₁ ×  А₂ × …× А_n. Если одним из сомножителей является пустое множество, то и произведение является пустым множеством.

Степенью множества A называется его прямое произведение само на себя n раз; обозначается Aⁿ.

Пример

Рассмотрим два множества: чисел Q = {1, 2, 3, 4, 5, 6, 7, 8} и букв: P = {a, b, c, d, e, f, g, h}. Тогда если рассмотреть произведение P×Q, то оно будет иметь вид упорядоченных пар: (a,1), …, (a,8), (b,1), …, (b,8), …, (h,1), …, (h,8). Мощность такого произведения равна 8×8=64, а сами элементы – клетки шахматной доски.

Пример

Пусть имеются множества A={1,2}, B={2,3,4}. Тогда А ×  B = {(1,2), (1,3), (1,4), (2,2), (2,3), (2,4)}. Если рассмотреть A³ = {(1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2)}.

Точка на плоскости может быть задана упорядоченной парой координат, т.е. двумя точками на координатных осях. Т.о., R² = R×R. Метод координат был введен в употребление Рене Декартом, отсюда и название “декартово произведение”.

Отношения

N-местным отношением R или N-местным предикатом R на множествах А₁, …, А_n называется любое подмножество прямого произведения

А₁ × …× А_n: R Í  А₁×…×А_n.

Элементы a₁, a₂, …, a_n | a_i ϵ  A_i при "  i = 1, 2, …, n связаны отношением R тогда и только тогда, когда упорядоченный набор (a₁ ,a₂, … a_n) ϵ  R.

При N = 1 отношение R является подмножеством множества А₁ и называется унарным отношением или свойством.

Наиболее часто встречается двухместное отношение (N = 2), которое называется бинарным отношением R из множества А в множество В, или соответствием: это подмножество произведения множеств А и В: R Í А × B.

Е сли элементы a и b множеств А и В (a,b)ϵ R, то говорят, что они находятся в отношении R, для чего часто используется так называемая инфиксная форма записи: aRb. Если R Í  А × A (т.е. А=В), то R называется бинарным отношением на множестве А. Соответственно, отношение R Í Аⁿ называется N-местным предикатом на множестве А.

Бинарное отношение можно задать указанием всех пар, для которых это отношение выполняется, или графически. Способы графического представления также могут быть различными. Рассмотрим варианты (см. рис.):

Основу графического представления бинарного отношения составляет прямоугольная система координат, где по одной оси отмечаются точки (a), представляющие элементы множества А, а по другой – точки (b), представляющие элементы множества В. Тогда точки с координатами (a,b) обозначают элементы декартова произведения.

На той же прямоугольной системе координат отношения для любой пары (a,b) показаны стрелками из a в b.

Множества A и B показаны точками на параллельных линиях, а отношения между ними – стрелками, направленными от a к b.

Пример

Рассмотрим множества

A={1,2,3,4,5,6}, B={1,2,3}.

Определим на этих множествах отношение

RÍA×B: R={(x,y) | x делится на y}.

R можно представить графически так, как это показано на последнем рисунке. Кроме того, можно задать это же отношение множеством упорядоченных пар: {(1,1), (2,1), (2,2), (3,1), (3,3),(4,1), (4,2), (5,1), (6,1), (6,2), (6,3)}, которые соответствуют тем же точкам на плоскости.

Определим несколько отношений, необходимых при рассмотрении множеств.

Пусть R есть отношение на множестве A: R Í А× A, a,b Î  A. Тогда:

Обратное отношение: R^–1 = {(b,a) | (a,b) Î  R}.

Дополнение отношения:   = {(a,b) | (a,b)Ï R}.

Тождественное отношение, или диагональ:

I_А = {(a,a) | a Î  A}.

Универсальное (или полное) отношение: U_A = {(a,b) | a Î  A и b Î  A}.

Свяжем с каждым бинарным отношением R между множествами A и B два множества – область определения δ_R и множество (или область) значений ρ_R. Они определяются следующим образом:

δ _R = {xÎ A| y Î B | (x,y) Î R },

ρ _R = {yÎB| (x,y)ÎR для некоторого xÎA}.

Пример. Пусть на множестве A = {1,2,3,4,5} задано отношение R:

R={(x,y)|остаток от деления y на x равен 1}.

Тогда R={(5,1),(4,1),(3,1),(2,1),(2,3),(3,4),(2,5),(4,5)}, δ_R = {2,3,4,5}, ρ_R = {1,3,4,5}.

Образом множества X относительно предиката R называется множество R(X) = {y | (x,y)Î R для некоторого xÎX}

Пример. Пусть имеются множества A, B, C и отношения R₁ Í A×B, R₂ ÍB×C. Определим отношение RÍA×C следующим образом: оно действует из A в B посредством R₁, а затем из B в C посредством R₂. Такое отношение называется составным (композицией), или произведением отношений и обозначается R = R₂◦R₁: R = {(x,y) | $  z Î  B, для которого выполнено (x,z)ÎR₁, (z,y)ÎR₂}. Обратите внимание на последовательность записи множеств в их композиции!

Пример. Пусть A={1,2,3,4}, на множестве A определим два отношения: R₁ = {(x,y) | 2× x ≤  y} и R₂ = {(x,y) | x+3× y кратно 2}. Найдем графические представления отношений R₁, R₂, R = R2 ◦R1

Найдем области определения и области значений для всех отношений.

δ (R₁)={1,2}, ρ (R₁)={2,3,4},

δ(R₂)={1,2,3,4}, (R₂)={1,2,3,4},

δ(R)={1,2}, ρ(R)={1,2,3,4}.

Если записать эти же отношения в виде пар, то получим: R₁ = {(1,2), (1,3), (1,4), (2,4)} и R₂ = {(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)}. Тогда композиция отношений

R: (1,2),(2,2)Þ (1,2); (1,2),(2,4)Þ(1,4) и т.п. R =R₁◦R₂={(1,2),(1,4),(1,1),(1,3),(1,2),(1,4),(2,2), (2,4)}. Устранив повторяющиеся элементы, получим:

R = {(1,2), (1,4), (1,1), (1,3), (2,2), (2,4)}.

Пусть R – бинарное отношение на множестве A.

Степенью отношения R на множестве A называется его композиция с самим собой.

Rn=R◦R◦…◦R,

где R повторяется n раз.