Алгебра множеств

Алгеброй $$А$$ называется совокупность множества $$М$$ с заданными в нем операциями $$S: A=<M,S>$$, где $$М$$ - носитель, $$S$$ - сигнатура.

Алгеброй множеств $$A$$ называется совокупность булеана универсального множества с заданными в нем операциями:

$$A_k = < \beta(Е), S_M >,$$

где $$S_M$$ - множество операций: пересечение, объединение, дополнение, разность.

Законы алгебры множеств

Для операций объединения, пересечения и дополнения выполняются следующие законы:

коммутативности:$$А \cup В = В \cup А; А \cap В = В \cap А;$$

ассоциативности:$$А \cup ( B \cup C ) = ( A \cup B ) \cup C,$$ $$A \cap ( B \cap C ) = ( A \cap B ) \cap C;$$

дистрибутивности:

пересечения относительно объединения:$$A \cap ( B \cup C ) = ( A \cap B ) \cup ( A \cap C );$$

объединение относительно пересечения:$$A \cup ( B \cap C ) = ( A \cup B ) \cap ( A \cup C);$$

идемпотентности:$$A \cup A = A, A \cap A = A;$$

действия с универсальным и пустым множествами:$$A \cup \emptyset = A, A \cap \emptyset = \emptyset,$$ $$A \cup E = E, A \cap E = A;$$ $$A \cup \overline A = E, A \cap \overline A = \emptyset;$$

де Моргана:$$\overline {A \cap B} = \overline A \cup \overline B,$$ $$\overline {A \cup B} = \overline A \cap \overline B ;$$

двойного дополнения:$$\overline{\overline A} = A.$$

Доказательство законов можно выполнить графически или посредством последовательности утверждений типа "если $$Р$$, то $$Q$$ ", которое записывается как $$"P =>Q"$$.

Докажем закон дистрибутивности:

$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C).$$

Графическое доказательство состоит в построении диаграмм Эйлера-Венна для правой и левой частей (рис 2.1).

Доказательство

Если $$х \in A \cap (B \cup C) => x \in A$$ и $$x \in (B \cup C) => x \in A$$ и $$(x \in B \mbox{ или } x \in C) => (x \in A \mbox{ и } x \in B)$$ или $$( x \in A \mbox{ и } x \in C) => (x \in A \cap B)$$ или $$(x \in A \cap C) => x \in (A \cap B) \cup (A \cap C)$$.

(рис 2.1)

Таким образом, $$A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$$. Необходимо доказать включение в обратную сторону:

$$x \in ( A \cap B ) \cup ( A \cap C ) => (x \in A \cap B)$$ или $$(x \in A \cap C) =>$$

$$(x \in A { и } x \in B )$$ или $$( x \in A \mbox{ и } x \in C) => x \in A$$ и $$(x \in B \mbox{ или } x \in C) => x \in A$$ и $$x \in (B \cup C) => x \in A \cap (B \cup C)$$.

Следовательно, $$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$.

Докажем закон де Моргана

$$\overline {A \cap B} = \overline A \cup \overline B.$$

Графическая интерпретация представлена на рис 2.2.

(рис 2.2)

Рассмотрим графическую интерпретацию левой части закона де Моргана, в которой можно выделить три составные части (рис 2.3).

(рис 2.3) $$x \in \overline {A \cap B} \Rightarrow x \in (\overline A \cap B) \cup (A \cap \overline B ) \cup (\overline A \cap \overline B ) \Rightarrow$$

Используя закон идемпотентности $$\left[ х \cup х = х \right]} $$, получим:

$$x \in (\overline A \cap B) \cup ( \overline A \cap \overline B ) \cup (A \cap \overline B ) \cap ( \overline A \cap \overline B ) \Rightarrow$$ $$x \in ( (\overline A \cap B) \cup ( \overline A \cap \overline B ) ) \cup ( (A \cap \overline B ) \cup ( \overline A \cap \overline B ) ) \Rightarrow$$

по закону дистрибутивности

$$x \in ( (\overline A \cap ( В \cup \overline B ) ) \cup (\overline В \cap (А \cup \overline А )) \Rightarrow x \in ( \overline А \cap Е ) \cup (\overline В \cap Е) \Rightarrow$$ $$х \in \overline A \cup \overline B.$$

Таким образом, $$\overline {A \cap B} \subseteq \overline A \cup \overline B$$.

Аналогично доказывается включение в обратную сторону:

$$x \in \overline A \cup \overline B \Rightarrow x \in \overline {Е \cap A \cap B} \Rightarrow x \in \overline {Е \cap A \cap Е \cap B} \Rightarrow x \in \overline {A \cap B}.$$

Следовательно,

$$\overline {A \cap B} = \overline A \cup \overline B.$$

Нахождение мощности объединения множеств

Мощность объединения двух множеств:

$$\left| А \cup В \right| = \left| A \right| + \left| B \right| - \left| А \cap В \right|$$ (рис 2.4).

(рис 2.4)

Мощность объединения трех множеств:

$$\left| А \cup В \cup С \right|= \left| A \right| + \left| B \right| + \left| C \right| - \left| А \cap В \right| - \left| А \cap С \right| - \left| В \cap С \right| + \left| А \cap В \cap С \right|$$ (рис 2.5).

(рис 2.5)

Доказательство:

$$\begin{array} \left| А \cup В \cup С | = \left| А \cup (В \cup С) \right| = \left| А \right| + \left| В \cup С \right| - \left| А \cap (В \cup С) \right| = \\ \left| A \right| + \left| B \right| + \left| C \right| - \left| В \cap С \right| - \left| (А \cap В) \cup (А \cap С) \right| = \\ \left| A \right| + \left| B \right| + \left| C \right| - \left| В \cap С \right| - \left| А \cap В \right| - \left| А \cap С \right| + \left| А \cap В \cap С \right|. \\ \end{array}$$

Мощность объединения $$n$$ множеств:

Теорема. $$А_1, А_2, ....... А_n$$ - некоторые множества, тогда мощность объединения $$n$$ множеств определяется по формуле

$$\begin{array} \left| А_1 \cup А_2 \cup .... \cup A_n | = \left| A_1 \right| + \left| A_2 \right| +...+\\ + \left| A_n \right| - \left[ \left| А_1 \cap А_2 \right| + \left| А_1 \cap А_3 \right| + ...+ \left| A_{n-1} \cap A_n \right| \right] + \\ \left[ \left| А_1 \cap А_2 \cap А_3 \right| + \left| А_1 \cap А_2 \cap А_4 \right| + ... + \left| A_{n-2} \cap А_{n-1} \cap А_n \right| \right] -...\\ + (-1)^{n-1} \left| А_1 \cap А_2 \cap....A_n \right| .\\ \end{array}$$

Правая часть этой формулы является суммой $$n$$ слагаемых, $$k$$ -е по порядку слагаемое имеет вид $$(-1)^{k-1} S_k (A_1, ....., A_n)$$, где $$S_k(A_1, A_2, ....., A_n)$$ есть сумма чисел мощностей $$\left| A_i1 \cap.... \cap A_lk \right|$$ по всем возможным пересечениям k разных множеств из множеств $$А_1, ....., А_n.$$

Пример. На потоке из 100 студентов 28 человек изучают английский язык, 30 человек - немецкий язык, 42 человека - французский язык. Причем 8 человек изучают два языка - английский и немецкий, 10 человек изучает английский и французский языки, 5 человек - немецкий и французский языки. 3 человека изучают все 3 языка. Сколько студентов не изучает ни один из перечисленных языков?

Пусть $$S$$ - множество студентов, $$\left| S \right| = 100$$ (студентов). $$А$$ - множество студентов, изучающих английский язык, $$\left| A \right| = 28$$ ; $$Н$$ - множество студентов, изучающих немецкий язык $$\left| H \right| = 30$$, $$Ф$$ - множество студентов, изучающих французский язык, $$\left| Ф \right| = 42$$.

Соответственно множества студентов, изучающих по 2 или 3 иностранных языка заданы следующим образом: $$\left| А \cap Н \right| = 8, \left| А \cap Ф \right| = 10, \left| H \cap Ф \right| = 5, \left| А \cap Н \cap Ф \right| = 3$$.

$$Y$$ - множество студентов, изучающих иностранные языки.

$$\left| Y \right| = \left| A \right| + \left| H \right| + \left| Ф \right| - \left| А \cap Н \right| - \left| А \cap Ф \right| - \left| Н \cap Ф \right| + \left| А \cap Н \cap Ф \right| = \\ 28 + 30 + 42 - 8 - 10 - 5 + 3 = 80$$

$$X$$ - множество студентов, не изучающих иностранный язык.

$$\left| X \right| = 100 - 80 = 20.$$

Векторы и прямые произведения

Векторы. Проекция вектора

Вектор (или кортеж) - это упорядоченный набор элементов. Например, $$(0; 1; 3)$$. Элементы вектора называются координатами или компонентами. Число координат - длина вектора (размерность).

Координаты вектора могут совпадать $$(0; 5; 4; 5)$$.

Два вектора равны, если они имеют одинаковую длину и равны соответствующие координаты: $$(а_1, а_2, ....., а_m)$$ и $$(b_1, b_2, ...., b_n)$$

$$m = n, a_1 = b_1, a_2 = b_2, ....., a_m = b_n .$$

Проекцией вектора $$V$$ на ось $$i$$ ( $$пр_i V$$ ) называется его i-я компонента. $$V = (a; b; c; d), пр_2 V = (b).$$

Проекцией вектора $$V = (a_1, a_2, ...., a_n)$$ на оси с номерами $$i_1, i_2,...., i_k$$ называется вектор $$(a_{i1}, a_{i2}, ...., a_{ik})$$ длины $$k: пр_{i1,..,ik} V$$.

Пример: $$V = \left\{ {(a; b; d); (c; b; d); (d; b; b)} \right\}$$,

$$пр_1 V = \left\{ {a, c, d} \right\},$$ $$пр_2 V = \left\{ {b} \right\},$$ $$пр_{2,3} V = \left\{ {(b,d); (b, b)} \right\}.$$

Прямое произведение

Прямым (декартовым) произведением множеств $$A$$ и $$B$$ ( $$A \times B$$ ) называется множество всех векторов $$(a; b)$$, таких, что $$a \in А, b \in В$$:

$$A \times B = \left\{ { x : x = (a; b), a \in А, b \in В} \right\}.$$

Если $$A = B$$, то $$A \times A = A^2 $$. Аналогично для нескольких множеств. Прямым произведением множества $$A_1 \times A_2 \times .... \times A_m$$ называется множество всех векторов длины $$m$$, таких, что $$a_1 \in А_1, a_2 \in А_2, ...., a_m \in A_m (a_1, a_2, ..., a_m) $$.

$$A_1 \times A_2 \times .... \times A_m = \left\{ {x: x=(a_1, a_2, ..., a_m), a_1 \in A_1, a_2 \in A_2, ..., a_m \in A_m} \right\}.$$

Примеры.

Множество $$R \times R=R^2$$ - множество точек плоскости, точнее пар вида $$(a, b)$$, где $$a, b \in R$$ и являются координатами.

$$A = \left\{ {a, b, c, d, e, f, g, h} \right\}, B = \left\{ {1, 2, .., 8} \right\}$$.

Тогда $$A \times B = \left\{ { (a; 1), (a; 2), ..., (d; 7), (d; 8), ... (h; 7), (h; 8)} \right\}$$ - множество всех 64 клеток шахматной доски.

$$A$$ - множество букв, символов, знаков препинания и т. д. Тогда элементы множества $$A^n$$ - слова длины $$n$$. Множество всех слов $$A^* = \cup A_i = A_1 \cup A_2 \cup A_3 \cup...; i \in N$$ составляет язык.

$$X = \left\{ {2, 3} \right\}, Y = \left\{ {a, b} \right\}. \\ X \times Y = \left\{ {(2; a), (2; b), (3; a), (3; b)} \right\}.\\ Y \times X = \left\{ {(a; 2), (a; 3), (b; 2), (b; 3)} \right\}$$.

Следовательно, $$X \times Y \ne Y \times X$$.

Теорема о мощности прямого произведения

Пусть $$A_1, A_2, ..., A_n$$ - конечные множества. Соответственно мощности этих множеств равны: $$\left| A_1 \right| = m_1, \left| A2 \right| = m_2, ..., \left| A_n \right| = m_n$$.

Тогда мощность прямого произведения $$n$$ множеств равна произведению мощностей соответствующих множеств, т.е. $$\left| A_1 \times A_2 \times A_3 \times ... \times A_n \right| = m_1 \cdot m_2 \cdot ... \cdot m_n$$.

Доказательство методом математической индукции.

Для $$n = 1$$ теорема тривиально верна. Предположим, что она верна и для $$n = k$$ и докажем ее справедливость для $$n = k+1$$.

По предположению $$\left| A_1 \times A_2 \times A_3 \times ... \times A_k \right| = m_1 m_2... m_k$$. Возьмем любой вектор $$(a_1, a_2, ... a_k)$$ из $$A_1 \times A_2 \times A_3 \times ... \times A_k $$ и припишем справа элемент $$a_{k+1} \in A_{k+1}$$. Это можно сделать $$m_{k+1}$$ способом, т. е. получим $$m_{k+1}$$ различных векторов из $$A_1 \times A_2 \times A_3 \times ... \times A_{k+1} $$.

Таким образом, из всех $$m_1 m_2 ... m_k$$ векторов приписыванием справа элемента из $$A_{k+1}$$ можно получить $$m_1 m_2 ... m_{k+1}$$ векторов, причем все они различны. Поэтому для $$n=k+1$$ теорема верна и, следовательно, верна для любых $$n$$.

Следствие: $$\left| A^n \right| = \left| A \right|^n$$