== Множества == На данной странице **использованы формулировки и обозначения из [1] и [2]** ((users:yashma:share:books| списка литературы)) === Основные понятия === Основоположник теории множеств -- немецкий математик Георг Кантор (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$. Закон барона Мюнхаузена: из ложного суждения следует любое.