Конспект: Множества и их спецификации (Дискретная математика)

Хорошо, вот конспект по дискретной математике, основанный на предоставленных вами изображениях. Я постарался сделать его максимально понятным и удобным для переписывания в тетрадь, используя только разрешенные форматы. *** Лекция 1. Множества и их спецификации Цель лекции: Систематизировать представления об универсальном языке теории множеств, ознакомиться с видами множеств, способами их задания и операциями над ними. Знания этой лекции станут начальным словарём для дальнейшего изучения дискретной математики. План лекции: 1. Введение в дискретную математику. 2. Взаимосвязь дискретной математики с другими науками. 3. Основные понятия теории множеств: множества, подмножества, язык теории множеств, операции над множествами. Введение Со школьной скамьи известно, что многие явления в окружающем мире можно описать с помощью понятий действительного числа и непрерывного трёхмерного пространства. Математические модели, связанные со свойствами непрерывности, изучают многие закономерности материального мира. Дискретная математика (или дискретный анализ) — это направление в математике, объединяющее её разделы, ранее сформированные как самостоятельные теории. К ним относятся: * теория множеств, * отношений, * комбинаторика, * теория графов, * кодирование, * автоматы. Дискретной математикой называют совокупность математических дисциплин, изучающих свойства абстрактных дискретных объектов, то есть свойства математических моделей объектов, процессов, зависимостей, существующих в реальном мире, которые оперируют в различных областях знаний. Дискретный анализ — это самостоятельный раздел современной математики, изучающий свойства различных структур, имеющих конечный характер. Математический аппарат дискретного анализа — это взаимосвязанная совокупность языка, моделей и методов математики, ориентированная на решение различных, в том числе инженерных задач. Он связан с характером исследуемых моделей: * отдельные элементы абстрактных множеств, * отдельные числа в различных системах счисления, * отдельные значения 0 и 1 (истина и ложь), * булевы функции и т.д. Деление математики на дискретную и классическую условно. Например, аппарат теории множеств и теории графов используется при изучении как дискретных, так и непрерывных объектов. Отдельные направления дискретной математики зародились в глубокой древности и развивались параллельно с классической математикой. Наиболее интенсивное развитие дискретная математика получила в последнее столетие. XXI век называют веком информатизации. Основной объём информации хранится в памяти ЭВМ. Применение ЭВМ для комплексной автоматизации информационной деятельности принципиально изменило характер взаимоотношений человека и машины. Стимулом для развития многих направлений дискретной математики явились запросы теоретической кибернетики, непосредственно связанной с развитием ЭВМ. Теоретическая кибернетика изучает разнообразные практические проблемы средствами дискретной математики: * растущий поток информации и проблемы её передачи, обработки и хранения привели к возникновению и развитию теории кодирования; * экономические задачи, задачи электротехники стимулировали создание и развитие теории графов; * связь релейно-контактных схем с формулами алгебры логики и их использование для описания функционирования автоматов дали начало развитию и применению математической логики и теории автоматов. Математическая логика в широком смысле изучает основания математики, принципы построения математических теорий. Дискретная математика изучает объекты, которые порой не имеют ни физической, ни числовой интерпретации. В классической математике характеристики реальных объектов можно представить в виде чисел, а закономерности — в виде соотношений. В отличие от реальных характеристик информационных объектов могут служить понятия «структура», «отношение», «связь». В последнее время раздел математики, называемый «Дискретный анализ», всё чаще вводится в программы подготовки не только математиков, инженеров, программистов, но даже юристов. Взаимосвязь дискретной математики с другими науками. Кибернетические области информатики используют в качестве аппарата язык как фундаментальной, так и прикладной математики. Кибернетика — наука об общих принципах управления в живых, неживых и искусственных системах. Методы, разрабатываемые дискретной математикой, часто используются в различных направлениях информатики. Теоретическая информатика использует математические методы для построения и изучения моделей обработки, передачи и использования информации. Объекты её изучения — дискретные множества. Достижения математической логики используются для анализа процессов переработки информации с помощью ЭВМ. Теория автоматов разрабатывает методы, с помощью которых можно на основе моделей логического типа изучать процессы, протекающие в самой машине во время её работы. Для работы на компьютере информацию представляют в дискретной форме, позволяющей переводить её в программы, понятные ЭВМ. Теория информации изучает вид тех форм, в которых информация представляется в компьютере. Формализация любой информации, реально существующей в живой и неживой природе, происходит через компьютерное моделирование. Системный анализ изучает структуру реальных объектов и даёт способы их формализованного описания. Общая теория систем как часть системного анализа изучает различные по характеру системы с общих позиций. Теория массового обслуживания изучает широкий класс моделей передачи и переработки информации в системах массового обслуживания (СМО). Наука семиотика исследует знаковые системы самой различной природы. Семиотика включает такие разделы, как синтактика (что связывает знак), семантика (что выражает знак), сигматика (что обозначает знак) и прагматика (что даёт знак). Имитационное моделирование — наука, в которой создаются и используются специальные приёмы воспроизведения процессов, протекающих в реальных объектах, в тех моделях этих объектов, которые реализуются в вычислительных машинах. Теория принятия решений изучает общие схемы, используемые при выборе решения из альтернативных возможностей (в условиях неопределённости). Теория игр изучает модели, в которых выбор происходит в условиях конфликта или противоборства. Математическое программирование рассматривает проблемы принятия оптимальных решений с помощью математического аппарата. Искусственный интеллект — одно из молодых и перспективных направлений информатики, появившееся во второй половине XX в. на базе вычислительной техники, математической логики, программирования, психологии, лингвистики и других отраслей знаний. Информационные системы применяются для анализа и прогнозирования потока информации, исследования способов её представления, хранения и извлечения. Актуальным является также создание информационно-поисковых систем, систем хранения, обработки передачи информации, в состав которых входят информационные базы данных, терминалы, средства связи. На знаниях законов логики базируются принципы алгоритмизации, которые лежат в основе программирования. Фундаментом всей вычислительной техники и автоматики является преобразование двоичных сигналов, анализ, проектирование и использование логических схем. Представление знаний — методы и приёмы формализации информации из различных областей знаний для их хранения, классификации, обобщения и применения при решении конкретных задач. Моделирование рассуждений — изучение и формализация различных умозаключений и их использование при решении задач средствами ЭВМ. Методы диалогового общения человека и машины. Специфика работы программистов заключается в том, что оппонентом в диалоге выступает компьютер. В процессе её обработки возникают два варианта диалогового общения: * ЭВМ самостоятельно задаёт вопросы по полученной информации согласно заложенной в неё программе; * компьютер задаёт вопросы, которые заложены заранее в заготовленную программистом модель беседы. В процессе диалогового общения программист должен знать виды вопросов и ответов для составления программы, владеть правилами построения точных, непротиворечивых, логически выстроенных и адекватных ситуациям формулировок. Объектом исследования дискретной математики являются дискретные множества — совокупность, набор некоторых элементов. *** Раздел 1. Множества и отношения При изучении этого раздела мы систематизируем имеющиеся со школы представления об универсальном языке теории множеств, познакомимся с видами множеств и отношений между ними, узнаем, как сравнивать конечные и бесконечные множества и как подсчитывать число их элементов. Этот раздел должен стать тем словарём, с помощью которого можно свободно изучать дальнейшие разделы дискретной математики. *** 1.1. Теория множеств 1.1.1. Множества. Подмножества. Язык теории множеств Множество — одно из основных понятий современной математики, с которым каждый человек знаком со школьной скамьи. Например, «множество решений уравнения или неравенства», «множество точек на плоскости», «множество действительных чисел» и т.д. — привычные словосочетания, не требующие дополнительных рассуждений и определений. Понятие множества относится к числу первоначальных, точно неопределяемых математических понятий. Оно может быть пояснено с помощью примеров. Таким образом, множество — это вполне определённая совокупность различных между собой предметов, понимаемая как единое целое. Предметы, составляющие множество, называются его элементами. Множества обозначаются обычно большими латинскими буквами: \(A, B, C, D, E, \dots\). А его элементы малыми прописными буквами. Если предмет \(a\) является элементом множества \(A\) (принадлежит множеству), то пишут \(a \in A\); иначе \(a \notin A\). Для обозначения множества служит пара фигурных скобок \(\{\dots\}\), внутри которых перечисляются элементы. Существуют три способа задания множества: 1. Перечисление (список). 2. Описание характеристических свойств объекта, входящих в это множество. 3. Порождающая процедура. 1. Перечислением задаются конечные множества. Например, если множество \(A\) конечно и состоит из элементов \(a_1, a_2, \dots, a_n\), то пишут: \(A = \{a_1, a_2, \dots, a_n\}\) \(B = \{\text{отл., хор., удовл., неудовл., не атт.}\}\) 2. В случаях, когда число элементов какого-либо множества \(A\) достаточно велико (или бесконечно), или эти элементы неизвестны, применяется запись вида: \(A = \{x \mid P(x)\}\), где символом \(P(x)\) обозначается характеристическое свойство элементов \(x\) множества \(A\). \(P(x)\) означает: «\(A\) есть множество таких элементов \(x\), которые обладают свойством \(P\)». Например, Запись \(C = \{x \mid x \in N, x < 7\}\) обозначает, что множество \(C\) составляют только те натуральные числа, которые меньше 7. \(D = \{x \mid x \in R, x^2 - 3x + 2 = 0\}\), \(D\) — множество действительных корней уравнения \(x^2 - 3x + 2 = 0\). 3. Порождающей процедурой называется способ получения элементов множества из уже полученных элементов. Например, \(A\) — множество всех целых чисел, являющихся степенями числа 2 может быть представлено порождающей процедурой, заданной двумя правилами (рекурсивными или индуктивными): а) \(1 \in A\) б) если \(x \in A\), то \(2 \cdot x \in A\). Для удобства рассуждений в теории множеств вводится пустое множество. Оно обозначается символом \(\emptyset\) или \(0\). Это множество не имеет элементов. Пустое множество играет роль нуля в операциях над множествами. Например, множество \(M\) целочисленных корней уравнения \(6x^2 - 5x + 1 = 0\) — пустое множество: \(M = \{x \mid 6x^2 - 5x + 1 = 0, x \in Z\} = \emptyset\). Рассмотрим теперь отношения вложения и равенства, определённые для множеств. Определение 1.1. Множество \(A\) называется **подмножеством** множества \(B\) (или \(A\) вложено в \(B\)), если каждый элемент множества \(A\) является элементом множества \(B\). При этом пишут \(A \subseteq B\). Пример. Пусть \(A = \{1, 2, 3, 4\}\), \(B = \{2, 4\}\), \(C = \{1, 5\}\), тогда \(B \subseteq A\), \(C \not\subseteq A\). Вспомним следующие обозначения для основных числовых множеств: * Множество натуральных чисел \(N = \{1, 2, 3, \dots\}\) * Множество целых чисел \(Z = \{\dots, -2, -1, 0, 1, 2, \dots\}\) * Множество рациональных чисел \(Q = \{\frac{m}{n} \mid m \in Z, n \in N\}\). Из школьного курса математики известно, что десятичная запись рационального числа есть бесконечная периодическая дробь. Например, \(\frac{1}{3} = 0.33\dots = 0.(3)\) \(\frac{5}{2} = 2.5 = 2.500\dots = 2.5(0)\) В дополнении к рациональным числам (т.е. периодическим десятичным дробям) рассмотрим множество всех бесконечных непериодических десятичных дробей. Такие дроби называют иррациональными числами: \(\pi = 3.14159\dots\) \(\sqrt{2} = 1.4142\dots\) Множество всех рациональных и иррациональных чисел называется множеством всех действительных (вещественных) чисел и обозначается \(R\). Очевидно, что \(N \subseteq Z \subseteq Q \subseteq R \subseteq C\), где \(C\) — множество комплексных чисел. Замечание 1.1. Пустое множество и само множество являются подмножествами для любого множества \(A\): \(\emptyset \subseteq A\), \(A \subseteq A\). Они называются **тривиальными подмножествами** множества. Подмножества, не совпадающие с тривиальными, называются **собственными**. Определение 1.2. Множество всех подмножеств множества \(A\) называется **булеаном** множества \(A\) и обозначается \(2^A\). Теорема 1.1. Если множество \(A\) состоит из \(n\) элементов, то множество \(2^A\) состоит из \(2^n\) элементов. Убедимся в справедливости этого утверждения на примере. Пусть \(A = \{1, 2, 3\}\), тогда \(2^A = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}\). Определение 1.3. Множества \(A\) и \(B\) называются **равными** (\(A=B\)), если они состоят из одних и тех же элементов. Имеет место Теорема 1.2. \(A = B\) тогда и только тогда, когда \(A \subseteq B\) и \(B \subseteq A\). Пример \(\{2, 4, 6\} = \{6, 2, 4\} = \{2, 4, 6\}\). Пример \(\{\{1, 2\}, \{1, 3\}\} \ne \{1, 2, 3\}\). Пример \(\{\{1, 2\}\} \ne \{1, 2\}\). Геометрическое представление множеств. Множества удобно изображать с помощью кругов Эйлера (диаграмм Эйлера-Венна). Большой прямоугольник — универсум, а круги или другие замкнутые фигуры внутри — множества. Точки внутри различных областей (штриховка) — элементы соответствующих множеств. Рис. 1.1. Иллюстрация кругами Эйлера: \(a\) — элемент \(a\) принадлежит множеству \(M\), элемент \(b\) не принадлежит множеству \(M\); \(K\) — подмножество \(K\) множества \(M\). *** 1.1.2. Операции над множествами Определение 1.4. **Объединением** \(A \cup B\) множеств \(A\) и \(B\) называется множество всех предметов, которые являются элементами множества \(A\), или элементами множества \(B\): \(A \cup B = \{x \mid x \in A \text{ или } x \in B\}\). Здесь подразумевается неисключающий смысл слова «или». Пример. \(\{1, 2, 3\} \cup \{1, 3, 4\} = \{1, 2, 3, 4\}\). Определение 1.5. **Пересечением** \(A \cap B\) множеств \(A\) и \(B\) называется множество предметов, являющихся элементами обоих множеств \(A\) и \(B\): \(A \cap B = \{x \mid x \in A \text{ и } x \in B\}\). Пример. \(\{1, 2, 3\} \cap \{1, 3, 4\} = \{1, 3\}\). Пусть все рассматриваемые в данной задаче множества являются подмножествами некоторого множества \(U\). В этом случае множество \(U\) называется **универсальным множеством** (для этой задачи). Основное свойство универсума — все рассматриваемые множества являются его подмножествами. В такой ситуации можно говорить о дополнении множества \(A\) из \(U\). Определение 1.6. **Дополнением** \(\overline{A}\) множества \(A\) называется множество всех элементов \(U\), не являющихся элементами множества \(A\): \(\overline{A} = \{x \mid x \in U, x \notin A\} = U \setminus A\). Пример. Пусть \(A = (2, 10)\), \(U = (-\infty, \infty)\). Тогда \(\overline{A} = (-\infty, 2] \cup [10, \infty)\). Определение 1.7. **Разностью** \(A \setminus B\) множеств \(A\) и \(B\) называется множество всех тех элементов множества \(A\), которые не являются элементами множества \(B\): \(A \setminus B = \{x \mid x \in A, x \notin B\}\). Заметим, что в определении разности \(A \setminus B\) не предполагается, что множество \(B\) является подмножеством множества \(A\) (\(B \not\subseteq A\)). Пример. \(Z \setminus N = \{x \mid x \in Z, x \le 0\}\). Пример. \(A = (-\infty, 5]\), \(B = (-\infty, 1]\), \(A \setminus B = (1, 5]\). Пример. \(A = (2, 10)\), \(B = (-3, 8)\), \(A \setminus B = [8, 10)\). Определение 1.8. **Декартовым произведением** множеств \(A\) и \(B\) называется множество \(A \times B\), определяемое равенством: \(A \times B = \{(a, b) \mid a \in A, b \in B\}\). Пример. \(A = (-1, 1)\), \(B = (0, 1)\). \(A \times B = \{(a, b) \mid -1 < a < 1, 0 < b < 1\}\). В тех случаях, когда \(A\) и \(B\) — числовые множества, декартово произведение \(A \times B\) удобно изображать точками плоскости в декартовой системе координат. В этом примере декартово произведение будет изображаться точками заштрихованного прямоугольника (без его границ). Пример. \(A = \{-1, 1, 2\}\), \(B = \{1, 2\}\). \(A \times B = \{(-1, 1), (-1, 2), (1, 1), (1, 2), (2, 1), (2, 2)\}\). В этом примере декартово произведение будет изображаться шестью точками. Определение 1.9. **Симметрической разностью** множеств \(A\) и \(B\) называется множество \(A \Delta B\), определяемое равенством: \(A \Delta B = \{x \mid (x \in A \text{ и } x \notin B) \text{ или } (x \in B \text{ и } x \notin A)\} = (A \setminus B) \cup (B \setminus A)\). Диаграммы Венна применяются для упрощения некоторых сложных выражений, связанных с множествами, с их помощью также можно проверить правильность рассуждений. Например, на диаграмме Венна хорошо иллюстрируются равенства: \((A \setminus B) \cup (A \cap B) = A\) \((A \setminus B) \cup B = A \cup B\) *** 1.1.3. Свойства операций над множествами Основные свойства операций объединения, пересечения и дополнения множеств устанавливаются в следующей теореме: Теорема 1.3. Для каждых из подмножеств \(A, B, C\) универсального множества \(U\) имеют место равенства: 1. \(A \cup B = B \cup A\), \(A \cap B = B \cap A\) — переместительный закон (коммутативность) для операций объединения и пересечения. Свойство справедливо для любого числа конечных множеств. 2. \((A \cup B) \cup C = A \cup (B \cup C)\), \((A \cap B) \cap C = A \cap (B \cap C)\) — сочетательный закон (ассоциативность) для операций объединения и пересечения. 3. \((A \cup B) \cap C = (A \cap C) \cup (B \cap C)\) — распределительный закон (дистрибутивность) пересечения относительно объединения множеств. \((A \cap B) \cup C = (A \cup C) \cap (B \cup C)\) — распределительный закон объединения относительно пересечения множеств. 4. \(A \cup \emptyset = A\), \(A \cup U = U\), \(A \cap \emptyset = \emptyset\), \(A \cap U = A\) — свойства тождества. 5. \(A \cup \overline{A} = U\), \(A \cap \overline{A} = \emptyset\) — свойства дополнения. 6. \(A \cup A = A\), \(A \cap A = A\) — законы идемпотентности. 7. \(A \cup (A \cap B) = A\), \(A \cap (A \cup B) = A\) — правила поглощения. 8. \(\overline{A \cup B} = \overline{A} \cap \overline{B}\), \(\overline{A \cap B} = \overline{A} \cup \overline{B}\) — законы де Моргана. 9. \(\overline{\overline{A}} = A\) — двойное дополнение. 10. \(\overline{\emptyset} = U\), \(\overline{U} = \emptyset\). 11. \((A \cup B) \cap (\overline{A} \cup \overline{B}) = A\), \((A \cap B) \cup (\overline{A} \cap \overline{B}) = A\) — правила склеивания. Каждое из равенств в приведённой теореме можно доказать исходя из утверждения: \(A = B\) тогда и только тогда, когда \(A \subseteq B\) и \(B \subseteq A\) (то есть необходимо доказать, что множества слева и справа от знака равенства совпадают всеми элементами). Пример. Доказать аналитически \(A \setminus B = A \cap \overline{B}\). а) \(x \in A \setminus B \Rightarrow (x \in A \text{ и } x \notin B) \Rightarrow (x \in A \text{ и } x \in \overline{B}) \Rightarrow x \in A \cap \overline{B}\). Следовательно, \(A \setminus B \subseteq A \cap \overline{B}\). б) \(x \in A \cap \overline{B} \Rightarrow (x \in A \text{ и } x \in \overline{B}) \Rightarrow (x \in A \text{ и } x \notin B) \Rightarrow x \in A \setminus B\). Следовательно, \(A \cap \overline{B} \subseteq A \setminus B\). Определение 1.10. Равенство, справедливое для всякого универсального множества и произвольных его подмножеств, называется **тождеством** или **законом теории множеств**. Пример. Доказать, что \(A \cup (B \setminus A) = A \cup B\). \(A \cup (B \setminus A) = A \cup (B \cap \overline{A}) = (A \cup B) \cap (A \cup \overline{A}) = (A \cup B) \cap U = A \cup B\). Пример. Упростить выражение \((A \cap B \cap C) \cup (\overline{A} \cap B \cap C) \cup \overline{B} \cap \overline{C}\). \((A \cap B \cap C) \cup (\overline{A} \cap B \cap C) \cup \overline{B} \cap \overline{C} = ((A \cup \overline{A}) \cap B \cap C) \cup \overline{B} \cap \overline{C} = (U \cap B \cap C) \cup \overline{B} \cap \overline{C} = (B \cap C) \cup \overline{B} \cap \overline{C} = U\). Замечание 1.2. Понятия объединения и пересечения множеств обобщаются на случай произвольного числа множеств: \(\bigcup_{i=1}^{n} A_i = \{x \mid x \in A_1 \text{ или } x \in A_2 \text{ или } \dots \text{ или } x \in A_n\}\) \(\bigcap_{i=1}^{n} A_i = \{x \mid x \in A_i \text{ для всех } i = 1, 2, \dots, n\}\) Замечание 1.3. В теории множеств имеет место принцип двойственности: для каждой теоремы, формулируемой в терминах \(\cup, \cap\) и дополнения множеств, теоремой также является двойственное ей предложение, т.е. предложение, полученное заменой \(\cup\) на \(\cap\), \(\cap\) на \(\cup\), \(\emptyset\) на \(U\) и \(U\) на \(\emptyset\). Например, имеет место тождество \((A \cup B) \cap (\overline{B} \cap A) = A\). По закону двойственности также справедливо равенство \((A \cap B) \cup (\overline{B} \cup A) = A\). *** 1.1.4. Мощность множества Определение 1.10. Множества \(A\) и \(B\) называются **равномощными** (эквивалентными), если между их элементами можно установить взаимно-однозначное соответствие. Очевидно, что для конечных множеств их равномощность означает равное количество элементов в этих множествах. Определение 1.11. Количество элементов в конечном множестве \(A\) называется его **мощностью** и обозначается \(|A|\). Определение 1.12. Множество \(A\) называется **счётным**, если можно установить взаимно-однозначное соответствие (нумерацию) между элементами этого множества и множества \(N\) натуральных чисел. Другими словами, множество счётно, если его элементы можно перенумеровать всеми натуральными числами. Пример. Множества натуральных чисел \(N\), \(2N\) (чётных натуральных чисел), множество нечётных чисел (соответствие \(n \leftrightarrow 2n-1\)), целых и рациональных чисел являются счётными. Например, для множества целых чисел можно установить следующую нумерацию: \(0, 1, -1, 2, -2, 3, -3, \dots\) (соответствие \(1 \leftrightarrow 0, 2 \leftrightarrow 1, 3 \leftrightarrow -1, 4 \leftrightarrow 2, 5 \leftrightarrow -2, \dots\); вообще \(n \leftrightarrow (n-1)/2\) для нечётных \(n\) и \(n \leftrightarrow -n/2\) для чётных \(n\)). Равномощны множества любых двух отрезков \([a, b]\) и \([c, d]\) (соответствие можно установить, например, с помощью центрального проектирования). Определение 1.13. Множество, эквивалентное множеству точек любого отрезка, называется **множеством мощности континуум**. Рассмотрим более подробно свойства счётных множеств и множеств мощности континуум. Счётные множества 1. Любое бесконечное подмножество \(B\) счётного множества \(A\) также счётно. Элементы \(B\) можно перенумеровать в порядке их следования в \(A\); так как \(B\) бесконечно, для нумерации будут использованы все натуральные числа. 2. Объединение конечной или счётной совокупности счётных множеств — счётное множество. Докажем последнее утверждение сначала для двух счётных множеств \(A = \{a_1, a_2, a_3, \dots\}\) и \(B = \{b_1, b_2, b_3, \dots\}\). Выпишем все элементы этих множеств в одну строчку \(a_1, b_1, a_2, b_2, a_3, b_3, \dots\) и сопоставим каждому элементу его номер в этой строчке (если \(A \cap B \ne \emptyset\), т.е. какой-то элемент входит и в \(A\), и в \(B\), он получает номер только в первый раз, а во второй раз пропускается). В результате будут пронумерованы все элементы множества \(A \cup B\), что доказывает его счётность. Также доказывается счётность объединения трёх, четырёх и вообще любого конечного числа счётных множеств. В случае счётного числа счётных множеств \(\{A_1, A_2, A_3, A_4, \dots\}\) способ нумерации может быть, например, таким: Нумерация начинается с элемента \(a_{11}\) и продолжается в направлении стрелок, повторяющиеся элементы при этом пропускаются. 3. Множество \(Q\) рациональных чисел счётно. Множество рациональных чисел (чисел вида \(p/q\), где \(p, q\) — целые числа, \(q \ne 0\)) можно представить как объединение счётного числа следующих счётных множеств: * множество \(Q_1\) всех целых чисел \(n = 0, \pm 1, \pm 2, \pm 3, \dots\); * множество \(Q_2\) всех дробей вида \(n/2\); * множество \(Q_3\) всех дробей вида \(n/3, \dots\); * множество \(Q_k\) всех дробей вида \(n/k, n = 0, \pm 1, \pm 2, \pm 3, \dots\); следовательно, оно счётно. Определение 1.14. Если для бесконечного множества невозможно установить взаимно-однозначное соответствие с множеством натуральных чисел, то оно **несчётно**. Например, множество \([0, 1]\) — всех действительных чисел \(x\), \(0 \le x \le 1\) является несчётным. Мощность множества \([0, 1]\) имеет мощность континуума. Теорема 1.5 (Кантор). Множество действительных чисел отрезка \([0, 1]\) не является счётным. Доказательство. Предположим противное, т.е. предположим, что существует следующая нумерация чисел этого отрезка: \(0, a_{11} a_{12} a_{13} \dots\) \(0, a_{21} a_{22} a_{23} \dots\) \(\dots\) \(0, a_{n1} a_{n2} a_{n3} \dots\) Рассмотрим число \(0, b_1 b_2 b_3 \dots\), где \(b_i \ne a_{ii}\). Это число не совпадает ни с одним из чисел, записанных выше. Полученное противоречие доказывает теорему. Определение 1.14. Говорят, что множество, равномощное отрезку \([0, 1]\), имеет **мощность континуума**. Такими множествами, например, являются множества чисел любого отрезка числовой оси и все множество \(R\) действительных чисел. Действительно, взаимно-однозначное соответствие чисел \(x \in [0, 1]\) и \(y \in R\) можно установить с помощью функции \(y = \text{tg} \pi (x - 1/2)\). Взаимно-однозначное соответствие между отрезками \([a, b]\) и \([0, 1]\) можно установить с помощью проектирования из некоторой точки \(O\). *** 1.1.5. Представление множеств в ЭВМ Представление множеств в ЭВМ подразумевает описание способа хранения информации о принадлежности элементов множеству и описание алгоритмов вычисления объединения, пересечения, дополнения и т.д. Рассмотрим один из способов такого представления. Пусть универсум \(U\) конечный и количество элементов в нём не превосходит разрядности ЭВМ: \(U = \{u_1, u_2, \dots, u_n\}\). Подмножество \(A\) универсума \(U\) представляется кодом \(A_2\): \[A_2[i] = \begin{cases} 1, & u_i \in A \\ 0, & u_i \notin A \end{cases}\] где \(A_2[i]\) — \(i\)-ый разряд кода \(A_2\). Пример. \(U = \{u_1, u_2, u_3, u_4\}\), \(A = \{u_3, u_4\}\), \(A_2 = (1100)\). Все подмножества некоторого множества можно генерировать последовательностью кодов, в которой каждый следующий код получается из предыдущего прибавлением единицы в двоичной системе счисления. Результат такого кодирования представлен в таблице ниже: | Код множества | Номер кода (\(N_A\)) | Множество | |---|---|---| | 00...00 | 0 | \(\emptyset\) | | 00...01 | 1 | \(\{u_1\}\) | | 00...10 | 2 | \(\{u_2\}\) | | 00...11 | 3 | \(\{u_1, u_2\}\) | | ... | ... | ... | | 11...11 | \(2^n-1\) | \(\{u_1, u_2, \dots, u_n\}\) | Номер \(N_A\) кода множества \(A\) в этой последовательности однозначно определяется самим кодом и является записью \(A_2\) в десятичной системе счисления: \(N_A = A_2[1] \cdot 2^0 + A_2[2] \cdot 2^1 + \dots + A_2[n] \cdot 2^{n-1}\). Количество кодов в этой последовательности равно \(2^n\) и, следовательно, мощность множества \(2^U\) всех подмножеств множества \(U\) также равна \(2^n\): \(|2^U| = 2^n\). Рассмотрим алгоритмы кодирования объединения, пересечения, дополнения множеств. Определение 1.15. **Логической суммой** (дизъюнкцией) и **логическим произведением** (конъюнкцией) булевых переменных \(x\) и \(y\) называются функции \(x \lor y\) и \(x \land y\), определяемые таблицей: | \(x\) | \(y\) | \(x \lor y\) | \(x \land y\) | |---|---|---|---| | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 0 | | 1 | 0 | 1 | 0 | | 1 | 1 | 1 | 1 | Код объединения множеств \(A\) и \(B\) получается поразрядным логическим сложением кодов \(A_2\) и \(B_2\): \((A \cup B)_2[i] = A_2[i] \lor B_2[i], i = \overline{1, n}\). Аналогично, код пересечения множеств \(A\) и \(B\) получается поразрядным логическим умножением кодов \(A_2\) и \(B_2\): \((A \cap B)_2[i] = A_2[i] \land B_2[i], i = \overline{1, n}\). Код дополнения множества \(A\) есть инверсия кода \(A_2\): \[\overline{A}_2[i] = \begin{cases} 0, & A_2[i]=1 \\ 1, & A_2[i]=0 \end{cases}, i = \overline{1, n}\] Пример. Пусть \(U = \{u_1, u_2, u_3, u_4\}\), \(A = \{u_1, u_4\}\), \(B = \{u_2, u_4\}\). Запишем коды множеств и их номера для \(A, B, A \cup B, A \cap B, \overline{B}\). \(A_2 = (1001)\), \(B_2 = (1010)\). \((A \cup B)_2 = (1011)\), \((A \cap B)_2 = (1000)\), \(\overline{B}_2 = (0101)\). \(N_A = 9\), \(N_B = 10\), \(N_{A \cup B} = 11\), \(N_{A \cap B} = 8\), \(N_{\overline{B}} = 5\). *** 1.1.6. Покрытие и разбиение Пусть \(M_1, M_2, \dots, M_k\) — подмножества множества \(M\). Определение 1.16. Набор множеств \(\{M_j\}_{j=1}^k\) называется **покрытием** множества \(M\), если \(M = \bigcup_{j=1}^k M_j\). Определение 1.16. **Покрытие** \(\{M_j\}_{j=1}^k\) множества \(M\) называется **разбиением**, если \(M_i \cap M_j = \emptyset\) при \(i \ne j\). Пример. Пусть \(M = \{1, 2, 3, 4\}\), \(M_1 = \{1, 4\}\), \(M_2 = \{2, 4\}\), \(M_3 = \{3, 4\}\). Тогда \(\{M_1, M_2, M_3\}\) — покрытие \(M\), так как \(M_1 \cup M_2 \cup M_3 = M\), но \(\{M_1, M_2, M_3\}\) не является разбиением \(M\), так как \(M_1 \cap M_2 = \{4\}\). Пример. Пусть \(M = \{1, 2, 3, 4\}\), \(M_1 = \{1, 2, 3\}\), \(M_2 = \{4\}\). Тогда \(\{M_1, M_2\}\) — покрытие \(M\), так как \(M = M_1 \cup M_2\), и \(\{M_1, M_2\}\) — разбиение \(M\), так как \(M_1 \cap M_2 = \emptyset\). *** 1.1.7. Характеристическая функция Пусть \(M\) — множество, \(M \subseteq U\), где \(U\) — универсальное множество. Определение 1.17. **Характеристической функцией** множества \(M\) называется функция \(h_M: U \to \{0, 1\}\) (отображает множество \(U\) в некоторое множество \(\{0, 1\}\)), равная 1 на элементах множества \(M\) и 0 на остальных элементах множества \(U\), которая: \[h_M(x) = \begin{cases} 1, & x \in M \\ 0, & x \notin M \end{cases}\] Свойства характеристических функций: 1. \(h_{A \cap B}(x) = h_A(x) \cdot h_B(x)\) 2. \(h_{\overline{A}}(x) = 1 - h_A(x)\) 3. \(|A| = \sum_{x \in U} h_A(x)\) Пример. Пусть \(A = \{2, 3, 5\}\), \(B = \{1, 3, 4, 6\}\), \(U = \{1, 2, 3, 4, 5, 6\}\). | \(x\) | 1 | 2 | 3 | 4 | 5 | 6 | |---|---|---|---|---|---|---| | \(h_A(x)\) | 0 | 1 | 1 | 0 | 1 | 0 | | \(h_B(x)\) | 1 | 0 | 1 | 1 | 0 | 1 | \(A \cap B = \{3\}\), \(\overline{A} = \{1, 4, 6\}\). *** 1.1.8. Формула включений и исключений Формула включений и исключений позволяет найти число элементов в объединении конечных множеств. Пусть \(M_1, M_2, \dots, M_k\) — конечные множества. При \(k=2\): \(|M_1 \cup M_2| = |M_1| + |M_2| - |M_1 \cap M_2|\). При \(k=3\): \(|M_1 \cup M_2 \cup M_3| = |M_1| + |M_2| + |M_3| - |M_1 \cap M_2| - |M_1 \cap M_3| - |M_2 \cap M_3| + |M_1 \cap M_2 \cap M_3|\). Общий случай. Теорема 1.6. Число элементов в объединении конечных множеств можно определить по формуле: \[\left|\bigcup_{i=1}^k M_i\right| = \sum_{i=1}^k |M_i| - \sum_{1 \le i < j \le k} |M_i \cap M_j| + \sum_{1 \le i < j < l \le k} |M_i \cap M_j \cap M_l| - \dots + (-1)^{k+1} |M_1 \cap M_2 \cap \dots \cap M_k|\] Доказательство. По закону двойного отрицания и закону де Моргана: \(\left|\bigcup_{i=1}^k M_i\right| = \left|\overline{\overline{\bigcup_{i=1}^k M_i}}\right| = \left|\overline{\bigcap_{i=1}^k \overline{M_i}}\right|\). Следовательно, \(\left|\bigcup_{i=1}^k M_i\right| = |U| - \left|\bigcap_{i=1}^k \overline{M_i}\right|\). По свойствам характеристической функции для произвольного \(x \in U\) имеем: \(h_{\overline{M_1} \cap \overline{M_2} \cap \dots \cap \overline{M_k}}(x) = h_{\overline{M_1}}(x) \cdot h_{\overline{M_2}}(x) \cdot \dots \cdot h_{\overline{M_k}}(x) = (1 - h_{M_1}(x))(1 - h_{M_2}(x))\dots(1 - h_{M_k}(x))\). Далее, \(\left|\bigcap_{i=1}^k \overline{M_i}\right| = \sum_{x \in U} h_{\overline{M_1} \cap \overline{M_2} \cap \dots \cap \overline{M_k}}(x) = \sum_{x \in U} (1 - h_{M_1}(x))(1 - h_{M_2}(x))\dots(1 - h_{M_k}(x))\). Раскрыв скобки и просуммировав по \(x \in U\) получим формулу включений и исключений. При \(k=3\): \(\sum_{x \in U} (1 - h_{M_1}(x))(1 - h_{M_2}(x))(1 - h_{M_3}(x)) = \sum_{x \in U} (1 - h_{M_1}(x) - h_{M_2}(x) + h_{M_1}(x)h_{M_2}(x))(1 - h_{M_3}(x)) = \dots\) \(\dots = |U| - |M_1| - |M_2| - |M_3| + |M_1 \cap M_2| + |M_1 \cap M_3| + |M_2 \cap M_3| - |M_1 \cap M_2 \cap M_3|\). Пример. Найти количество натуральных чисел от 1 до 100, не делящихся ни на одно из чисел 5, 11, 13. Пусть \(U = \{1, \dots, 100\}\), \(|U| = 100\). \(M_1\) — числа, делящиеся на 5. \(|M_1| = \lfloor 100/5 \rfloor = 20\). \(M_2\) — числа, делящиеся на 11. \(|M_2| = \lfloor 100/11 \rfloor = 9\). \(M_3\) — числа, делящиеся на 13. \(|M_3| = \lfloor 100/13 \rfloor = 7\). \(M_1 \cap M_2\) — числа, делящиеся на \(5 \cdot 11 = 55\). \(|M_1 \cap M_2| = \lfloor 100/55 \rfloor = 1\). \(M_1 \cap M_3\) — числа, делящиеся на \(5 \cdot 13 = 65\). \(|M_1 \cap M_3| = \lfloor 100/65 \rfloor = 1\). \(M_2 \cap M_3\) — числа, делящиеся на \(11 \cdot 13 = 143\). \(|M_2 \cap M_3| = \lfloor 100/143 \rfloor = 0\). \(M_1 \cap M_2 \cap M_3\) — числа, делящиеся на \(5 \cdot 11 \cdot 13 = 715\). \(|M_1 \cap M_2 \cap M_3| = \lfloor 100/715 \rfloor = 0\). Количество чисел, делящихся хотя бы на одно из 5, 11, 13: \(|M_1 \cup M_2 \cup M_3| = |M_1| + |M_2| + |M_3| - (|M_1 \cap M_2| + |M_1 \cap M_3| + |M_2 \cap M_3|) + |M_1 \cap M_2 \cap M_3|\) \(|M_1 \cup M_2 \cup M_3| = 20 + 9 + 7 - (1 + 1 + 0) + 0 = 36 - 2 = 34\). Количество чисел, не делящихся ни на одно из 5, 11, 13: \(|U| - |M_1 \cup M_2 \cup M_3| = 100 - 34 = 66\). *** Лекция 3. Отношения Пусть \(A\) и \(B\) — некоторые множества. Через \((a, b)\) будем обозначать **упорядоченную пару** элементов, где \(a \in A\), \(b \in B\). \((a, b) \ne (b, a)\) — порядок важен. \((a, b) \ne \{a, b\}\). Пример: \((3, 4) \ne (4, 3)\). \((1, 2) \ne \{1, 2\}\). Определение. **Прямым (декартовым) произведением** множеств \(A\) и \(B\) называется множество всех упорядоченных пар, в которых первый элемент \(\in\) множеству \(A\), а второй \(\in\) множеству \(B\): \(A \times B = \{(a, b) \mid a \in A, b \in B\}\). Пример 0. \(A = \{1, 2, 3\}\), \(B = \{\text{Д, А, О}\}\). \(A \times B = \{(1, Д), (1, А), (1, О), (2, Д), (2, А), (2, О), (3, Д), (3, А), (3, О)\}\). Пример 1. \(A = \{1, 2\}\), \(B = \{m, n, p\}\). \(A \times B = \{(1, m), (1, n), (1, p), (2, m), (2, n), (2, p)\}\). \(B \times A = \{(m, 1), (m, 2), (n, 1), (n, 2), (p, 1), (p, 2)\}\). Заметим, что \(A \times B \ne B \times A\). \(A \times A = \{(1, 1), (1, 2), (2, 1), (2, 2)\}\). Определение. **Степенью множества** \(A\) называется множество \(A^n\), полученное \(n\)-кратным декартовым произведением \(A\) на себя: \(A \times A \times \dots \times A = A^n\) (\(n\)-раз). Пример. Множество точек на \(n\)-мерном пространстве: \(R^2 = R \times R\), \(R^3 = R \times R \times R\). Теорема. Если \(A\) и \(B\) — конечные множества, то \(|A \times B| = |A| \cdot |B|\). Следствие. Если \(A\) — конечное множество, то \(|A^n| = |A|^n\). Определение. **Соответствием** между множествами \(A\) и \(B\) называется любое подмножество декартова произведения этих множеств \(R \subseteq A \times B\). Пример 1. \(A = \{1, 2, 3\}\), \(B = \{m, n, p\}\). \(R = \{(1, m), (2, p)\}\). Пример 3. \(B\) — множество студентов, \(A\) — множество групп. Тогда \(\{(x, y) \mid y \text{ является студентом } x\}\) является соответствием \(A\) и \(B\). Определение. **Отношением** (бинарным отношением) на множестве \(A\) называется любое подмножество \(A^2 = A \times A\). \(\rho \subseteq A \times A\). Пример. \(A = R\), \(\rho = \{(x, y) \in R \times R \mid x^2 + y^2 = 4\}\). Обозначение: \((x, y) \in \rho\) или \(x \rho y\). Элементы отношения являются парой \((x, y)\), элементы \(x\) и \(y\) связаны отношением. Пример 5. \(\rho = <\). \(2 < 5\), \