Теория множеств

M    x M  i I |  x E_i.
Семейство Ě называется дизъюнктным, если элементы этого семейства попарно не пересекаются, т.е. каждый элемент множества M принадлежит не более чем одному из множеств E_i: i,j I, ij  E_i   E_j=. (илл. на д. Венна)
Дизъюнктное покрытие Ě называется разбиением множества M.

5. 
   Пусть имеется множество M={1,2,3}. Тогда семейство {{1,2}, {2,3}, {3,1}} является покрытием, но не разбиением; семейство {{1},{2},{3}} – покрытием и разбиением, а семейство {{1},{2}} является дизъюнктным, но в то же время не является ни покрытием, ни разбиением.
   

Совокупность всех подмножеств множества M называется булеаном и обозначается P (M), или 2^M: 2^M = {A | A  M}.

6. 
   Пусть имеется множество M = {1,2,3}. Тогда булеаном для него будет являться семейство {,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
   

5. 
   Свойства операций над множествами
   

Пусть задан универсум U. Тогда A, B, C  U выполняются свойства:

1. 
   Идемпотентность
   

   A  A = A

   A  A = A

2. 
   Коммутативность
   

   A  B = B  A

   A  B = B  A

3. 
   Ассоциативность
   

   A  (B  C) = (A  B)  C

   A  (B  C) = (A  B)  C

4. 
   Дистрибутивность
   

   A  (B  C) = (A  B)  (A  C)

   A  (B  C) = (A  B)  (A  C)

5. 
   Операции с пустым множеством (свойства нуля)
   

   A   = A

   A   = 

6. 
   Операции с универсальным множеством (свойства единицы)
   

   A  U = U

   A  U = A

7. 
   Свойства дополнения
   

   Инволютивность:

   A A = U A A=

8. 
   Поглощение
   

   (A  B)  A = A

   (A  B)  A = A

9. 
   Двойственность (законы де Моргана)
   
10. 
    Выражение для разности
    

A \ B = A B

В справедливости перечисленных свойств легко убедиться, причем это можно сделать различными способами. Например, проверить каждое равенство по определению или же воспользоваться геометрическим представлением с помощью диаграмм Венна.
На основании свойств 1–10 можно получить новые свойства и равенства.

7. 
   Р азные способы определения симметрической разности. Доказать, что верно равенство (AB)\(AB)(A\B)(B\A).
   (A  B) \ (A  B)  ⁽¹⁰⁾ (A  B)  (AB)  ⁽⁹⁾ (A  B)  (A B)  ⁽⁴⁾ 
   ((A  B) A)  ((A  B) B)  ⁽⁴⁾ 
   ((A A)  (B A))  ((A B)  (B B))  ⁽⁷⁾ 
   (  (BA))  ((AB)  ) = ⁽⁵⁾ (BA)  (A B) = ⁽¹⁰⁾ (B \ A)  (A \ B).
   

1. 
   Контрольные вопросы
   

1. 
   Что означает запись А  В? В чем отличие от записи А  В?
   
2. 
   Пусть B = {1, 2, 3, 4}, A = {2, 4}. Какое из утверждений справедливо: А  В? B  A? А  В? B  A?
   
3. 
   Справедливо ли равенство |A| = |B|, если A = {a, b, c}, B = {2, 3, 5}?
   
4. 
   Чем отличается объединение множеств от их пересечения? Какое из них содержит больше элементов и почему?
   
5. 
   Как определяется симметрическая разность множеств?
   
6. 
   Пусть A = {1, 2, 3}, B = {2, 3, 4}. Определите результат следующих операций: 1) A  B; 2) A  B; 3) A \ B; 4) B \ A; 5) A Δ B ; 6) A  A; 7) A  A .
   
7. 
   Какую трудоемкость имеет алгоритм типа слияния множеств? Опишите этот алгоритм для определения операции разности множеств.
   
8. 
   Что такое разбиение множества и в чем его отличие от покрытия?
   
9. 
   Что из приведенных множеств будет являться разбиением множества A = {1, 2, 3, 4}: {{1}, {3,4}, {1,2}}, {{2}, {1,3}, {4}}, {{1,2,3},{4}}?
   
10. 
    Какое из приведенных множеств является булеаном множества A={a, b, c}: B = {{a}, {b,c}, {c}}, C = {, {a,b,c}, {b,c}, {a}, {b}, {c}, {a,b}, {a,c}}, D = {{a},{b},{c}}? Является ли что-то из перечисленного разбиением A?
    

3. 
   Отношения на множествах
   

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

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

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

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

8. 
   Для множества чисел А = {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ⁿ.

9. 
   Рассмотрим два множества: чисел 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, а сами элементы – клетки шахматной доски.
   
10. 
    Пусть имеются множества 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. Метод координат был введен в употребление Рене Декартом, отсюда и название «декартово произведение».
  

2. 
   Отношения
   

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-местным предикатом на множестве А.
Бинарное отношение можно задать указанием всех пар, для которых это отношение выполняется, или графически. Способы графического представления также могут быть различными. Рассмотрим варианты (см. рис.):

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

11. 
    Р ассмотрим множества 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}.
Дополнение отношения: 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}.

12. 
    Пусть на множестве 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₂}. Обратите внимание на последовательность записи множеств в их композиции!

13. 
    П усть A={1,2,3,4}, на множестве A определим два отношения: R₁ = {(x,y) | 2x  y} и R₂ = {(x,y) | x+3y кратно 2}. Найдем графические представления отношений R₁, R₂, R = R₂ ◦R₁
    Найдем области определения и области значений для всех отношений. (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 называется его композиция с самим собой. Rⁿ=R◦R◦…◦R.

3. 
   Свойства отношений
   

Теорема 1.1: Для любых бинарных отношений P, Q, R выполняются следующие свойства: