-
Операции над множествами: объединение, пересечение, относительное дополнение, симметрическая разность, абсолютное дополнение. Значение диаграмм Эйлера.
• Объединением множеств A и B называется множество A∪B, все элементы которого являются элементами множества A или B: A∪B = {x | x∈A ∨ x∈B}.
• Пересечением множеств A и B называется множество A∩B, элементы которого являются элементами обоих множеств A и B: A∩B = { x | x∈A & x∈B}. Выполняются включения A∩B ⊆ A ⊆ A∪B и A∩B ⊆ B ⊆A∪B. Говорят, что два множества не пересекаются, если их пересечение – пустое множество.
• Относительным дополнением множества A до множества X называется множество X\A всех тех элементов множества X, которые не принадлежат множеству A: X\A = {x | x∈X & x∉A}. (также называют разностью множеств X и A)
• Симметрической разностью множеств A и B называется множество A÷B = (A\B) ∪ (B\A).
• Когда фиксирован универсум U абсолютным дополнением множества A называется множество всех тех элементов x, которые не принадлежат множеству A: A = { x | x∈U & x∉ A}.
• Заметим, что A = U\A. Часто вместо A будем писать ¬A или A’.
• Первым стал использовать теперь общепринятые обозначения операций над множествами Джузеппе Пеано (1888 г.).
• Для наглядного представления отношений между подмножествами какого-либо универсума используются диаграммы Эйлера. В этом случае множества обозначают областями на плоскости и внутри этих областей условно располагают элементы множества.
• Часто все множества на диаграмме размещают внутри квадрата, который представляет собой универсум U.
• Если элемент принадлежит более чем одному множеству, то на диаграмме области, отвечающие таким множествам, должны перекрываться, чтобы общий элемент мог одновременно находиться в соответствующих областях.
• Здесь не имеет значения относительный размер кругов либо других замкнутых областей, но лишь их взаимное расположение.
• Безусловно, такие диаграммы могут играть в логике лишь ту роль, что чертежи в геометрии: они иллюстрируют, помогают представить и доказать, но сами ничего не доказывают.
-
Основные булевы тождества для операций над множествами. Как их доказывать.
• Объединение, пересечение и дополнение обычно называются булевскими операциями, составленные из множеств с их помощью выражения – булевыми выражениями, значение такого выражения – булевой комбинацией входящих в него множеств, а равенство двух булевых выражений – булевыми тождествами.
Теорема 4. Для любых подмножеств A, B и C универсума U выполняются следующие основные булевы тождества:
10 A\B = A ∩¬B
Докажем тождество A∪(B∩C) = (A∪B)∩(A∪C) . Сначала покажем, что A∪(B∩C) ⊆ (A∪B)∩(A∪C). Действительно, если x∈A∪(B∩C), то x∈A или x∈B∩C. Если x∈A, то x∈A∪B и x∈A∪C. Следовательно, x∈(A∪B)∩(A∪C). Если x∈B∩C, то x∈B и x∈C. Отсюда x∈A∪B и x∈A∪C, а значит, x∈(A∪B)∩(A∪C). Теперь покажем, что (A∪B)∩(A∪C)⊆A∪(B∩C). Если x∈(A∪B)∩(A∪C), то x∈A∪B и x∈A∪C. Следовательно, x∈A или x∈B и x∈C, т.е. x∈B∩C. Отсюда x∈A∪(B∩C). Более короткое доказательство A∪(B∩C) = (A∪B)∩(A∪C) получается, если использовать логические равносильности. Имеем A∪(B∩C) = {x | x∈A∪(B∩C)} = (по определению объединения и пересечения множеств) {x | x∈A ∨ (x∈B & x∈C)} = (дистрибутивность ∨ относительно &) {x | (x∈A ∨ x∈B) & (x∈A ∨ x∈C)}= (A∪B)∩(A∪C).
• Докажем тождество ¬(A∪B) = ¬A∩¬B . Пусть x∈¬(A∪B). Тогда x∈U и x∉A∪B. Следовательно, x∉A и x∉B. Отсюда x∈¬A и x∈¬B, а значит, x∈¬A∩¬B. Итак, ¬(A∪B)⊆¬A∩¬B. Пусть теперь, x∈¬A∩¬B. Тогда x∈¬A и x∈¬B. Следовательно, x∈U и x∉A и x∉B. Значит, x∉ A∪B, т.е. x∈¬(A∪B). Итак, ¬A∩¬B ⊆ ¬(A∪B).
• Второй способ доказательства. Имеем ¬(A∪B) = {x | x∈ ¬(A∪B)}= (по определению дополнения и объединения) { x | x∈U& ¬ ( x∈A ∨ x∈B)} =
(закон де Моргана для ∨) { x | x∈U& ¬( x∈A) & ¬( x∈B)} = (определение дополнения) { x | x∈¬A& x∈¬B} = ¬A∩¬B. Остальные тождества доказываются аналогично. Справедливость этих тождеств можно наглядно проиллюстрировать с помощью диаграмм Эйлера, но это, конечно, не является доказательством. С другой стороны, диаграмму вполне можно использовать, чтобы на частном примере опровергнуть какое- нибудь общее утверждение. Основные равносильности логики высказываний и основные тождества алгебры множеств выражаются одними и теми же законами.
Это не случайно: и алгебра высказываний, и алгебра множеств – это различные варианты математической структуры, называемой булевой алгеброй.
Теорема 5. Предложения о произвольных множествах A и B попарно эквивалентны:
1) A⊆B;
2) A∩B = A;
3) A∪B = B.
Доказательство. Докажем, что из первого предложения следует второе. Действительно, так как A∩B ⊆ A, то достаточно показать, что в этом случае A ⊆ A∩B. Но если x∈A, то x∈B, так как A⊆B, и, следовательно, x∈A∩B. Докажем, что из второго предложения следует третье. Так как A∩B = A, то A∪B = (A∩B)∪B. По закону поглощения (см. тождество 9) B∪(A∩B) = B. Отсюда, используя закон коммутативности, получаем A∪B = B. Докажем, что из третьего предложения следует первое. Так как A⊆ A∪B, а по условию третьего предложения A∪B = B, то A⊆B