Краткое содержание: Параграф § 17 / Информатика 10 класс

Основные понятия теории множеств

Содержание раздела посвящено фундаменту теории множеств, которая в информатике и математике используется для упорядоченного хранения и обработки информации. Множество представляет собой совокупность объектов произвольной природы, рассматриваемых как единое целое. Объекты, входящие в множество, называются его элементами. Множества обозначаются заглавными буквами латинского алфавита (\( A \), \( B \), \( C \) и т.д.), а их элементы – строчными. Факт принадлежности элемента \( x \) множеству \( M \) обозначается как \( x \in M \), а непринадлежности – \( x \notin M \).

Существует несколько способов задания множеств:

• Перечисление всех элементов, например, \( M = \{ 1, 3, 5, 7, 9 \} \). Порядок элементов не важен, и каждый элемент указывается только один раз.
• Характеристическим свойством, описывающим общее свойство всех элементов множества.

Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается символом \( \emptyset \). Множества могут быть конечными (с ограниченным числом элементов) или бесконечными. Если все элементы множества \( P \) принадлежат множеству \( M \), то \( P \) является подмножеством \( M \), что записывается как \( P \subset M \). Само множество \( M \) всегда является своим подмножеством (\( M \subset M \)). Универсальное множество (\( U \)) – это самое большое множество, содержащее все возможные элементы, рассматриваемые в данном контексте.

Для наглядного представления множеств и связей между ними используются диаграммы Эйлера, где множества изображаются кругами (или другими замкнутыми линиями) внутри прямоугольника, который символизирует универсальное множество \( U \).

Операции над множествами

В теории множеств определены основные операции:

• Пересечение (\( \cap \)) двух множеств \( X \) и \( Y \) – это множество \( X \cap Y \), состоящее только из общих элементов этих множеств. Если множества не имеют общих элементов, их пересечение равно пустому множеству (\( X \cap Y = \emptyset \)).
• Объединение (\( \cup \)) двух множеств \( X \) и \( Y \) – это множество \( X \cup Y \), состоящее из всех элементов, которые принадлежат хотя бы одному из множеств \( X \) или \( Y \).
• Дополнение (\( \bar{P} \)) подмножества \( P \) до универсального множества \( U \) – это множество \( \bar{P} \), состоящее из всех элементов \( U \), которые не вошли в \( P \). Если \( M \) – подмножество \( U \), то его дополнение обозначается как \( \bar{M} \). Объединение множества с его дополнением равно универсальному множеству: \( M \cup \bar{M} = U \).

Мощность множества и принцип включений-исключений

Мощность конечного множества \( X \), обозначаемая \( |X| \), – это число его элементов. Для вычисления мощности объединения двух пересекающихся множеств \( X \) и \( Y \) применяется принцип включений-исключений:

\( |X \cup Y| = |X| + |Y| - |X \cap Y| \)

Эта формула позволяет получить правильный результат, так как элементы, входящие в пересечение \( X \cap Y \), были учтены дважды (один раз в \( |X| \) и один раз в \( |Y| \)) и поэтому должны быть вычтены один раз. Аналогичная формула для трех множеств \( X \), \( Y \), \( Z \) выглядит сложнее:

\( |X \cup Y \cup Z| = |X| + |Y| + |Z| - |X \cap Y| - |X \cap Z| - |Y \cap Z| + |X \cap Y \cap Z| \)

Принцип включений-исключений является ключевым инструментом для расчетов в задачах, связанных с группами объектов, обладающих различными пересекающимися свойствами, что часто встречается в комбинаторике и статистике.