На данной странице использованы формулировки и обозначения из [1] и [2] списка литературы

Основоположник теории множеств – немецкий математик Георг Кантор (1845-1918).

«Множество есть многое, мыслимое нами как единое». Множество – совокупность объектов (элементов множества) любой природы. Обозначение: $A$, $B$, …

Способы задания – описание свойств, перечисление элементов.

Два множества считаются равными, если они состоят из одних и тех же элементов.

Множество называется конечным, если число его элементов конечно, и бесконечным в противном случае.

Пустое множество – множество, не содержащее элементов. Обозначение: $\varnothing$.

Множество $B$ называется подмножеством множества $A$, если каждый элемент множества $B$ является в то же время элементом множества $A$. Повторяющиеся элементы считаются по одному разу. Обозначение: $B \subset A$.

Универсальное множество $I$ (часто, $E$) – множество всех элементов рассматриваемой природы.

Множество, состоящее из общих элементов нескольких множеств $A$, $B$, $C$, …, называется пересечением этих множеств или их произведением. Обозначение пересечения двух множеств $A$ и $B$: $AB$ или $A \cap B$.

Объединением (или суммой) нескольких множеств $A$, $B$, $C$, … называется множество, состоящее из тех и только тех элементов, которые входят хотя бы в одно из слагаемых множеств. Обозначение суммы двух множеств $A$ и $B$: $A+B$ или $A \cup B$.

Разностью двух множеств $A$ и $B$ называется множество, в которое входят все элементы множества $A$, не принадлежащие $B$. Обозначение: $A-B$ или $A \setminus B$.

В случае, когда $B$ является частью множества $A$, $A-B$ называют дополнением к множеству $B$ в $A$. Обозначение: $ B'_{A} $. Если множество $B$ рассматривается как подмножество универсального множества $I$, то вместо $B'_I$ пишут просто $B'$.

• $A \subset A$.
• Если $A \subset B$ и $B \subset A$, то $A=B$.
• Если $A \subset B$ и $B \subset C$, то $A \subset C$.
• $\varnothing \subset A$.
• $A \subset I$.
• $A+B=B+A$.
• $AB=BA$.
• $A+(B+C)=(A+B)+C$.
• $A(BC)=(AB)C$.
• $A+A=A$.
• $AA=A$.
• $A(B+C)=AB+AC$.
• $A+BC=(A+B)(A+C)$.
• $A+\varnothing=A$.
• $AI=A$.
• $A+I=I$.
• $A \varnothing = \varnothing$.
• Соотношение $A \subset B$ эквивалентно каждому из соотношений $A+B=B$, $AB=A$.
• $A+A'=I$.
• $AA'=\varnothing$.
• $\varnothing'=I$.
• $I'=\varnothing$.
• $(A')'=A$.
• Соотношение $A \subset B$ эквивалентно $B' \subset A'$.
• $(A+B)'=A'B'$.
• $(AB)'=A'+B'$.

«Соотношение двойственности»: замены $\subset$ и $\supset$, $\varnothing$ и $I$, $+$ и $\cdot$.

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

• $A+B=B+A$,
• $(A+B)+C=A+(B+C)$,
• $(A'+B')'+(A'+B)'=A$.

И определить действие умножения $AB$, соотношение включения $A \subset B$ и множества $I$, $\varnothing$ формулами

• $AB$ по определению равно $(A'+B')'$,
• $A \subset B$ по определению означает, что $A+B=B$,
• $I=A+A'$, $\varnothing=I'$.

Пусть $A=\{ a_1, a_2, \dots, a_k\}$, $B=\{ b_1, b_2, \dots, b_l\}$.

Прямое (декартово) произведение множеств $A$ и $B$:

$A \times B = \{(a_1, b_1), (a_1, b_2), \dots, (a_1, b_l), (a_2, b_1), \dots, (a_k, b_l)\}$.

Аналогично определяется прямое произведение любого конечного числа множеств.

см. [1] стр. 24-32. Далее представлена ОЧЕНЬ краткая «выжимка», которую можно рассматривать как опорный план; при отсутствии записей собственного конспекта и пропуске соответствующего аудиторного занятия для понимания материала необходимо ознакомиться с полным текстом книги, там же приведены доказательства.

Пусть дана совокупность элементов $ A, B, C, \dots $. Пусть для элементов этой системы определены три операции.

Операция дополнения, которая каждому элементу $ A $ ставит в соответствие элемент $ \widetilde{A} $, называемый дополнением элемента $ A $.

Операция объединения, ставящая в соответствие каждой паре элементов $ A $ и $ B$ элемент $A \cup B$, называемый объединением или суммой элементов $ A $ и $ B$.

Операция пересечения, ставящая в соответствие каждой паре элементов $ A $ и $ B$ элемент $ A \cap B$, называемый пересечением элементов $ A $ и $ B$.

Три перечисленные операции должны удовлетворять следующим аксиомам:

$a_1$) $ \widetilde{\widetilde{A}}= A$;

$a_2$) $A \cup B = B \cup A$;

$a_3$) $(A \cup B) \cup C = A \cup (B \cup C)$;

$a_4$) $A \cap (B \cup C)=(A \cap B) \cup (A \cap C)$;

$a_5$) $A \cap (B \cup \widetilde{B}) = A$;

$a_6$) $\widetilde{A \cup B}= \widetilde{A} \cap \widetilde{B}$.

Система элементов, для которой определены операции дополнения, объединения и пересечения, удовлетворяющие аксиомам $a_1 - a_6$, называется булевой алгеброй (в честь Джорджа Буля, 1815-1864). Такие системы были рассмотрены в опубликованной в 1854 г. работе «Исследование законов мышления, на которых основаны математические теории логики и вероятностей» (ДО появления теории множеств!).

Аксиома $a_6$ обеспечивает выполнение во всякой булевой алгебре закона двойственности.

$a_6'$) $\widetilde{A \cap B} = \widetilde{A} \cup \widetilde{B}$;

$a_6''$) $ A \cup B= \widetilde{\widetilde{A} \cap \widetilde{B}}$;

$a_6'''$) $A \cap B = \widetilde{\widetilde{A} \cup \widetilde{B}}$.

$a_2'$) $A \cap B = B \cap A$;

$a_3'$) $A \cap (B \cap C) = (A \cap B) \cap C$;

$a_4'$) $A \cup (B \cap C)= (A \cup B) \cap (A \cup C)$;

$a_5'$) $A \cup (B \cap \widetilde{B} ) = A$.

Закон двойственности в булевых алгебрах: всякой теореме, выведенной из аксиом $a_1 - a_6$, отвечает двойственная ей теорема (получается из первоначальной путем перестановки символов $\cup$ и $\cap$.

Теорема 3. Для любого элемента $A$ булевой алгебры имеет место равенство $A \cup A =A$.

Теорема 3'. Для любого элемента $A$ булевой алгебры имеет место равенство $A \cap A =A$.

Элементы $E$ (единица) и $\varnothing$ (нуль) помогают определить следующие утверждения:

Теорема 4. Для любых двух элементов $B$ и $C$ булевой алгебры имеет место равенство $B \cup \widetilde{B} = C \cup \widetilde{C}$.

Теорема 4'. Для любых двух элементов $B$ и $C$ булевой алгебры имеет место равенство $B \cap \widetilde{B} = C \cap \widetilde{C}$.

$E=A \cup \widetilde{A}$, $\varnothing=A \cup \widetilde{A}$.

Дополнение к закону двойственности: Теорема 5. При переходе к двойственному утверждению символ $E$ надлежит заменить символом $\varnothing$, а символ $\varnothing$ – символом $E$.

Теорема 6. В булевой алгебре верны следующие соотношения: $A \cup E = E, A \cup \varnothing = A, \widetilde{E}=\varnothing, A \cup \widetilde{A}=E$.

Для определения отношений $\subseteq$ и $\supseteq$ помогут следующие результаты:

Теорема 7. Если $A \cup B = B$, то $A \cap B = A$.

Теорема 7'. Если $A \cap B = B$, то $A \cup B = A$.

По определению $A \subseteq B$ тогда и только тогда, когда $A \cup B = B$; $A \supseteq B$ тогда и только тогда, когда $A \cap B= B$.

Теорема 8. В двойственных утверждениях отношения $\subseteq$ и $\supseteq$ обмениваются местами.

Теорема 9. В булевой алгебре выполнены следующие соотношения:

(а) $A \subseteq A$;

(б) если $A \subseteq B$, то $B \supseteq A$;

(в) если $A \subseteq B$ и $A \supseteq B$, то $A=B$;

(г) если $A \subseteq B$ и $B \subseteq C$, то $A \subseteq C$;

(д) $A \subseteq E$;

(е) $A \subseteq A \cup B,$ $B \subseteq A \cup B$;

(ж) если $A \subseteq B$, то $A \cup B = B$;

(з) если $A \subseteq B$, то $\widetilde{A} \supseteq \widetilde{B}$.

Теорема 10. Если булева алгебра содержит более одного элемента, то элементы $E$ и $\varnothing$ различны, то есть $E \ne \varnothing$.

см. [1] стр. 32–43. Далее представлена ОЧЕНЬ краткая «выжимка», которую можно рассматривать как опорный план; при отсутствии записей собственного конспекта и пропуске соответствующего аудиторного занятия для понимания материала необходимо ознакомиться с полным текстом книги, там же приведены доказательства.

Булевы алгебры возникают не только в связи с теоретико-множественными операциями, но и в других случаях, поэтому для них принята другая терминология:

$$ \begin{array}{|l|l|} \hline \text{В алгебре множеств} & \text{В произвольной булевой алгебре} \\ \hline \text{объединение: } \cup & \text{сумма: } + \\ \hline \text{пересечение: } \cap & \text{произведение: } \times \text{или } \cdot \\ \hline \text{дополнение: } \widetilde{\phantom{aa} } & \text{дополнение: } \overline{\phantom{a} }\\ \hline \text{включение: } \subseteq \text{и } \supseteq & \text{неравенства: } \le \text{и } \ge \\ \hline \end{array}$$

Элементы булевой алгебры условились обозначать малыми латинскими буквами. Элементы, играющие в булевой алгебре роль пустого и универсального множеств, обозначаются соответственно через 0 и 1 и называются нулем и единицей этой алгебры.

Пример: для чисел 1, 2, 3, 5, 6, 10, 15, 30 определим «сложение», «умножение» и «дополнение» по следующим правилам:

1) $a+b = \text{НОК}(a,b)$;

2) $ab= \text{НОД}(a,b)$;

3) $\overline{a}=\dfrac{30}{a}$.

Построим булеву алгебру, содержащую два элемента. Эти элементы – нуль 0 и единица 1. Далее определим операции с помощью Теоремы 6 ( и ей двойственной).

Операция дополнения определяется следующей таблицей:

$$ \begin{array}{|c|c|} \hline a & \overline{a} \\ \hline 0 & 1\\ \hline 1 & 0 \\ \hline \end{array} $$

Операция сложения определяется следующей таблицей:

$$ \begin{array}{|c|c|c|} \hline + & 0 & 1 \\ \hline 0 & 0 & 1 \\ \hline 1 & 1 & 1 \\ \hline \end{array}$$

Операция умножения определяется следующей таблицей:

$$ \begin{array}{|c|c|c|} \hline \times & 0 & 1 \\ \hline 0 & 0 & 0 \\ \hline 1 & 0 & 1 \\ \hline \end{array}$$

Далее следует либо проверить выполнение аксиом, либо установить, что булева алгебра с двумя элементами действительно существует.

Математическая логика рассматривает взаимоотношения суждений. Суждение – всякое высказывание, относительно которого верно одно из двух: или оно истинно, или оно ложно. Суждения обозначаем малыми буквами латинского алфавита. Рассматриваемые суждения связаны с универсальным множеством – множеством тх объектов, относительно которых они высказываются. То подмножество универсального множества, для которого данное суждение истинно, называется множеством истинности этого суждения. (См. примеры из [1])

Суждение $p$ всегда ложно, когда множество истинности этого суждения пусто: $i(p)=\varnothing$. Суждение $p$ всегда истинно, когда его множество истинности совпадает с универсальным: $i(p)=E$.

Суждения $p$ и $p'$ называются равными, или эквивалентными, если $i(p)=i(p')$. В этом случае пишут $p=p'$.

В математической логике определены три операции, соответствующие в обычной речи «не», «или» и «и».

Отрицанием суждения $p$ называется суждение $\overline{p}$, истинное тогда и только тогда, когда $p$ ложно. Если $i(p)=P$, то $i(\overline{p})=\overline{P}=\overline{i(p)}$.

Дизъюнкцией двух суждений $p$ и $q$ называется суждение, истинное тогда и только тогда, когда истинно хотя бы одно из суждений $p$ или $q$. Дизъюнкция обозначается знаком $\vee$: $p \vee q$. Ясно, что $i(p \vee q) = i(p) \cup i(q)$.

Конъюнкцией двух суждений $p$ и $q$ называется суждение, истинное тогда и только тогда, когда истинны как $p$, так и $q$. Конъюнкция обозначается знаком $\wedge$: $p \wedge q$. Ясно, что $i(p \wedge q) = i(p) \cap i(q)$.

Отождествив каждое суждение с его множеством истинности (это можно сделать, поскольку суждения, имеющие одно и то же множество истинности, эквивалентны), убеждаемся в том, что все суждения, относящиеся к элементам одного и того же универсального множества, образуют булеву алгебру. Ее называют алгеброй логики.

$$ \begin{array}{|l|l|l|} \hline \text{Алгебра множеств} & \text{Булева алгебра} & \text{Алгебра логики} \\ \hline \text{объединение: } \cup & \text{сумма: } + & \text{дизъюнкция: } \vee\\ \hline \text{пересечение: } \cap & \text{произведение: } \times \text{или } \cdot & \text{конъюнкция: } \wedge \\ \hline \text{дополнение: } \widetilde{\phantom{aa} } & \text{дополнение: } \overline{\phantom{a} } & \text{отрицание: } \overline{\phantom{a} }\\ \hline \text{включение: } \subseteq \text{и } \supseteq & \text{неравенства: } \le \text{и } \ge & ?\\ \hline \end{array}$$

? – это не операция, это отношение между высказываниями.

Если суждение $q$ истинно всякий раз, когда истинно суждение $p$, то говорят, что из $p$ следует $q$, и пишут $p \Rightarrow q$. На языке множеств это означает, что $i(p) \supseteq i(q)$. Вместо знака ? в клетку таблицы нужно поместить

$$ \text{следование: } \Rightarrow .$$

Заметим, что если суждение $p$ всегда ложно, то при любом суждении $q$ имеет место отношение следования: $p \Rightarrow q$. Закон барона Мюнхаузена: из ложного суждения следует любое.