4. Диаграммы Эйлера – Венна.

Диаграммы Эйлера-Венна – геометрические представления множеств. Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U, а внутри его – кругов (или каких-нибудь других замкнутых фигур), представляющих множества. Фигуры должны пересекаться в наиболее общем случае, требуемом в задаче, и должны быть соответствующим образом обозначены. Точки, лежащие внутри различных областей диаграммы, могут рассматриваться как элементы соответствующих множеств. Имея построенную диаграмму, можно заштриховать определенные области для обозначения вновь образованных множеств.

Для наглядности логические высказывания изображают диаграммами Эйлера-Венна. Любое высказывание на диаграмме изображают кругом, а его отрицание - частью плоскости, находящейся вне круга.

Определение. Объединением множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В (рис. 1):

Определение. Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат одновременно как множеству А, так и множеству В (рис. 2):

Определение. Разностью множеств А и В называется множество всех тех и только тех элементов А, которые не содержатся в В (рис. 3):

Определение. Симметрической разностью множеств А и В называется множество элементов этих множеств, которые принадлежат либо только множеству А, либо только множеству В (рис. 4):

5. Булеан множества. Примеры. Мощность булеана конечного множества.

Напомним, что число элементов конечного множества называется мощностью множества и обозначается символом |A| или Card A

(от английского cardinality - мощность).

Определение :Множество всех подмножеств данного множества называют булеаном множества. Булеан обозначают символом

B(A).

Пример 1.5. Пусть A = { 1,2,3 }. Перечислить элементы булеана множества A.

B(A)={ ∅,{ 1 },{ 2 },{ 3},{ 1,2 },{ 1,3 },{ 2,3},{ 1,2,3 } }.

Пример 1.6. Пусть A = { 1,2,3,4,...,n }, т.е. |A | = n. Найдем мощность множества B(A).

Для определения CardB(A) воспользуемся биномиальными коэффициентами Cnk (число сочетаний из n по k)4. Перечислим по порядку, начиная с пустого множества, все подмножества множества A:

пустому подмножеству ∅ множества A поставим в соответствие число 1 = Cn0;

булеан содержит одноэлементные подмножества:

{ 1 }, { 2 }, { 3 }, ..., {n}.

Число одноэлементных подмножеств равно n = Cn1;

булеан содержит следующие двухэлементные подмножества:

{ 1,2 },{ 1,3 },{ 1,4 }, ј,{ 1,n },{ 2,3 },{ 2,4 }, ј,{ 2,n },

{ 3,4 },{ 3,5 }, ј,{ 3,n }, ј,{ n - 2,n - 1 },{ n - 2,n },{ n - 1,n}.

Количество двухэлементных подмножеств равно n(n - 1)2= Cn2 ;

продолжая этот подсчет, получим, что булеан содержит Cn3 трехэлементных подмножеств, Cn4 четырехэлементных подмножеств и так далее;

наконец, мы отметим, что булеан содержит Cnn - 1

(n - 1)-элементных подмножеств и одно n-элементное подмножество - само множество A, которому мы сопоставим биномиальный коэффициент Cnn = 1. В результате сумма всех биномиальных коэффициентов покажет нам количество элементов булеана B(A):

2n = (1 + 1)n = Cn0 + Cn1 + Cn2 + ... + Cnn - 1 +Cnn .

Таким образом, для любого множества A, если Card A = n, то Card B(A)=2n.