Теория множеств и алгебра логики
Привет! Сегодня мы погрузимся в фундаментальные концепции, на которых построен весь цифровой мир. Множества — это не просто абстрактная математика, это язык, на котором разговаривают все компьютерные системы. Готов разобраться, как это работает? Поехали!
Множества в цифровом мире — это не просто математика, а основа того, как компьютеры организуют, фильтруют и обрабатывают всю информацию вокруг нас.
§ 17. Некоторые сведения из теории множеств
17.1. Понятие множества — или как компьютер видит мир
Давай начнём с простого вопроса: как твой смартфон понимает, кому показать твою историю в Instagram, а кому — нет? Как Spotify формирует плейлист "только для тебя"? Как поисковик Google за доли секунды находит именно то, что тебе нужно, среди миллиардов страниц?
Ответ кроется в фундаментальной математической концепции — множествах. Это не просто абстракция из учебника, это буквально язык, на котором разговаривают все цифровые системы.
💡 Определение
Множество — это совокупность объектов произвольной природы, которая рассматривается как единое целое.
Представь себе:
- Твой список подписок на YouTube — это множество каналов
- Все треки в твоём плейлисте — множество песен
- Друзья в соцсетях — множество пользователей
- Все возможные IPv4-адреса в интернете — множество из примерно 4,3 миллиарда элементов
Каждое приложение на твоём телефоне работает с множествами: пользователи, контент, настройки — всё это организовано в структуры данных, основанные на теории множеств.
Как задавать множества: два подхода
1. Перечисление элементов
Самый очевидный способ — просто перечислить всё, что входит в множество:
M = {1, 3, 5, 7, 9}Важно понимать: порядок не имеет значения. M = {3, 1, 5, 9, 7} — это то же самое множество. Представь хэштеги под постом в Instagram — неважно, в каком порядке ты их написал, пост всё равно найдут по любому из них.
2. Характеристическое свойство
Более мощный способ — описать правило, по которому определяется, входит ли элемент в множество. Например, множество M можно описать как "все натуральные однозначные нечётные числа".
Как ты думаешь, почему этот способ круче для программирования? Потому что это, по сути, функция-фильтр!
// Вот как бы это выглядело в коде:
const M = numbers.filter(n => n > 0 && n < 10 && n % 2 !== 0);🔤 Обозначения
- 5 ∈ M — "число 5 принадлежит множеству M" (символ ∈ — знак принадлежности)
- 4 ∉ M — "число 4 НЕ принадлежит множеству M"
Мощность множества и пустое множество
Мощность множества (обозначается |M|) — это количество его элементов. Для нашего множества M: |M| = 5.
Интересный момент: множество может быть:
- Конечным — например, множество всех пользователей TikTok на данный момент (хотя и огромное, но конечное)
- Бесконечным — например, множество всех возможных паролей из латинских букв и цифр (теоретически бесконечно)
- Пустым (обозначается ∅) — множество, не содержащее ни одного элемента. Например, множество пользователей младше 0 лет
Подмножества — фильтры и категории
Из элементов множества M можно составить новое множество, например P = {1, 3, 5}.
Если каждый элемент множества P принадлежит множеству M, то P есть подмножество M: P ⊂ M.
Подмножества работают как фильтры в приложениях: из всех фотографий (универсальное множество) выбираются только те, где ты отмечен (подмножество).
📋 Важные свойства
- Само множество M является своим подмножеством: M ⊂ M
- Пустое множество является подмножеством любого множества: ∅ ⊂ M
Универсальное множество — контекст всего
Универсальное множество U — это "самое большое" множество в рамках конкретной задачи, содержащее все возможные элементы.
Например:
- Если A — множество чётных чисел, B — множество натуральных чисел, C — множество чисел, кратных пяти, то универсальным множеством будет множество всех целых чисел.
- В контексте соцсети универсальное множество — это все зарегистрированные пользователи платформы.
Для наглядного изображения множеств используются круги Эйлера — геометрическое представление, где точки внутри круга соответствуют элементам множества.
17.2. Операции над множествами — логика цифровых фильтров
Теперь самое интересное: что можно делать с множествами? Оказывается, над ними можно производить операции, похожие на арифметические, но гораздо мощнее для работы с информацией.
Пересечение (∩) — "И то, И другое"
💡 Определение
Пересечением двух множеств X и Y называется множество их общих элементов: X ∩ Y.
Пересечение множеств — это основа всех фильтров: показать посты, которые И от друзей, И с определённым хэштегом.
🔍 Пример из жизни
Представь, что:
X = {ш, к, о, л, а} — множество букв в слове "школа"
Y = {у, р, о, к} — множество букв в слове "урок"Общие буквы (пересечение):
X ∩ Y = {к, о}💻 Как это работает в реальности
- Поиск в Spotify: песни, которые И в жанре "рок", И выпущены после 2020 года
- Фильтр товаров на маркетплейсе: товары, которые И в нужной категории, И в нужном ценовом диапазоне
- Алгоритм рекомендаций: пользователи, которые И подписаны на тебя, И живут в твоём городе
📌 Особые случаи
- Если множества не имеют общих элементов: M ∩ X = ∅ (пустое множество)
- Пересечение множества с самим собой: M ∩ M = M
- Если P ⊂ M, то M ∩ P = P
Объединение (∪) — "ИЛИ то, ИЛИ другое"
💡 Определение
Объединением двух множеств X и Y называется множество, состоящее из всех элементов этих множеств (без повторений): X ∪ Y.
Для наших примеров:
X ∪ Y = {ш, к, о, л, а, у, р} — все буквы из обоих слов💻 Применение в цифровом мире
- Результаты поиска в Google: страницы, содержащие ИЛИ первое ключевое слово, ИЛИ второе
- Уведомления в мессенджере: сообщения ИЛИ от важных контактов, ИЛИ с упоминанием твоего имени
- Playlist в музыкальном сервисе: треки ИЛИ из одного альбома, ИЛИ из другого
🤔 Интересный вопрос для размышления
Возможно ли равенство A ∪ B = A ∩ B? В каком случае это может произойти?
Показать ответ
Это возможно только когда A = B, то есть множества полностью совпадают.
Дополнение — "всё КРОМЕ этого"
💡 Определение
Дополнением P до M (обозначается P̅) называется множество, состоящее из тех элементов M, которые НЕ вошли в P.
Важное условие: эта операция имеет смысл только когда P ⊂ M.
Пример:
Если M = {1, 3, 5, 7, 9}, а P = {1, 3, 5}
то дополнение P̅ = {7, 9}
Операция дополнения — это основа блокировок и исключений: "показать все уведомления, КРОМЕ рекламных".
⚡ Особенно важно дополнение до универсального множества
B̅ (дополнение B до U)
Свойство: B ∪ B̅ = U — объединение множества с его дополнением даёт универсальное множество.
💻 Где это используется
- Чёрные списки в мессенджерах: "все пользователи КРОМЕ заблокированных"
- Фильтры контента: "все посты КРОМЕ уже просмотренных"
- Настройки приватности: "все друзья КРОМЕ ограниченных"
17.3. Мощность множества — считаем правильно
💡 Определение
Мощность конечного множества |X| — это число его элементов.
Казалось бы, что может быть проще? Но когда мы начинаем комбинировать множества, возникают интересные вопросы.
Простой случай: непересекающиеся множества
Если множества M и X не имеют общих элементов, то:
|M ∪ X| = |M| + |X|Например: |M| = 5, |X| = 5, тогда |M ∪ X| = 10.
Сложный случай: пересекающиеся множества
А что если множества пересекаются? Давай разберём:
X = {ш, к, о, л, а}, |X| = 5
Y = {у, р, о, к}, |Y| = 4
X ∪ Y = {ш, к, о, л, а, у, р}, |X ∪ Y| = 7Если бы мы просто сложили 5 + 4 = 9, мы бы дважды посчитали общие элементы {к, о}!
📐 Правильная формула
|X ∪ Y| = |X| + |Y| - |X ∩ Y|Для нашего примера: 7 = 5 + 4 - 2 ✓
Принцип включений-исключений — магия комбинаторики
Это мощнейший инструмент для подсчёта элементов в сложных системах.
💡 Определение
Принцип включений-исключений — формула, позволяющая вычислить мощность объединения (пересечения) множеств, если известны их мощности и мощности всех их пересечений.
📐 Для трёх множеств
|X ∪ Y ∪ Z| = |X| + |Y| + |Z| - |X ∩ Y| - |X ∩ Z| - |Y ∩ Z| + |X ∩ Y ∩ Z|Логика такая:
- Складываем все множества
- Вычитаем парные пересечения (убираем двойной счёт)
- Добавляем тройное пересечение (компенсируем излишнее вычитание)
Принцип включений-исключений помогает точно подсчитать пользователей с несколькими интересами или фильтрами — основа аналитики в любом приложении.
📐 Аналогичные формулы для пересечения
|X ∩ Y| = |X| + |Y| - |X ∪ Y|
|X ∩ Y ∩ Z| = |X| + |Y| + |Z| - |X ∪ Y| - |X ∪ Z| - |Y ∪ Z| + |X ∪ Y ∪ Z|Практический кейс: зимний лагерь
📝 Условие
В лагерь едут 100 старшеклассников. Данные по видам спорта:
- Сноуборд умеют: 30 человек
- Лыжи умеют: 28 человек
- Коньки умеют: 42 человека
- Сноуборд И лыжи: 8 человек
- Лыжи И коньки: 10 человек
- Сноуборд И коньки: 5 человек
- Все три вида: 3 человека
Вопрос: Сколько ребят не умеет ни один из этих видов спорта?
💡 Решение
Обозначим: S — сноубордисты, L — лыжники, K — любители коньков.
Применяем формулу включений-исключений:
|S ∪ L ∪ K| = 30 + 28 + 42 - 8 - 10 - 5 + 3 = 80Это количество ребят, умеющих хотя бы что-то. Значит, не умеют ничего:
100 - 80 = 20 человек💻 Где это применяется в IT
- Аналитика пользователей: сколько людей используют хотя бы одну из функций приложения
- A/B тестирование: подсчёт уникальных пользователей, видевших разные версии
- Таргетированная реклама: охват аудитории с учётом пересечений интересов
📌 Ключевые выводы
Давайте подведём итоги и поймём, что мы узнали о теории множеств:
🤔 Проверь себя
Проверь, насколько хорошо ты усвоил материал!
1. Задача на понимание операций
Пусть X — множество натуральных чисел, делящихся на 2, а Y — множество натуральных чисел, делящихся на 3.
- a) Что представляет собой X ∩ Y?
- b) Можешь описать X ∪ Y словами?
- c) Какое наименьшее число входит в X ∩ Y?
Показать подсказку
- a) Числа, делящиеся и на 2, и на 3 — то есть на 6
- b) Числа, делящиеся на 2 или на 3 (или на оба)
- c) Наименьшее такое число — 6
2. Пусть множество X — это множество натуральных чисел, делящихся нацело на 18, а Y — множество натуральных чисел, делящихся нацело на 14. Укажите наименьшее число, входящее в пересечение и в объединение этих множеств.
Показать подсказку
Для пересечения нужно найти НОК(18, 14). Для объединения — наименьшее из чисел, делящихся на 18 или на 14.
3. Реальная жизнь: анализ соцсетей
Представь: у тебя 38 одноклассников. Обществознание в качестве экзамена выбрали 21 человек, причём:
- 3 из них выбрали ещё и информатику
- 6 выбрали ещё и физику
- 1 выбрал все три предмета
- Всего информатику выбрали 13 учеников
- Из выбравших информатику 5 указали два предмета в анкете
Вопрос: Сколько человек выбрали физику?
Показать подсказку
Нарисуй диаграмму Эйлера с тремя кругами и заполни все зоны пересечений, начиная с центральной (все три предмета).
4. Мысленный эксперимент: фильтр для музыкального сервиса
Ты разрабатываешь фильтр для музыкального стримингового сервиса. Пользователь хочет найти треки, которые:
- ИЛИ выпущены после 2020 года
- ИЛИ имеют более 1 млн прослушиваний
- НО при этом НЕ в жанре "поп"
Задание: Опиши эту логику через операции над множествами. Какие множества тебе нужны? Какие операции?
5. В первую смену в лагере «Дубки» отдыхали: 30 отличников, 28 победителей олимпиад и 42 спортсмена. При этом 10 человек были и отличниками, и победителями олимпиад, 5 — отличниками и спортсменами, 8 — спортсменами и победителями олимпиад, 3 — и отличниками, и спортсменами, и победителями олимпиад. Сколько ребят отдыхало в лагере?
Показать подсказку
Используй формулу включений-исключений для трёх множеств.
6. Задача со звёздочкой ⭐
Из 100 человек 85 знают английский, 80 — испанский, 75 — немецкий. Сколько человек заведомо знают все три языка?
Показать подсказку для размышления
Это задача "на худший случай". Представь, что мы хотим минимизировать количество полиглотов. Как распределить знания языков, чтобы как можно меньше людей знали все три?
Попробуй рассуждать так: сколько людей НЕ знают каждый из языков? Какое максимальное количество людей может не знать хотя бы один язык?
7. Пусть A, B и C — некоторые множества, обозначенные кругами, U — универсальное множество. С помощью операций объединения, пересечения и дополнения до универсального множества выразите различные области диаграммы Эйлера.
Представь диаграмму с тремя пересекающимися кругами. Попробуй выразить:
- Только область A (без B и C)
- Область, принадлежащую хотя бы двум множествам
- Область вне всех трёх множеств
🎯 Практические задания
Попробуй применить полученные знания на практике!
💻 Задание 1: Реализация на JavaScript
Создай три массива в JavaScript и реализуй операции пересечения и объединения:
const users_instagram = ['alice', 'bob', 'charlie', 'diana'];
const users_tiktok = ['bob', 'diana', 'elena', 'frank'];
const users_youtube = ['charlie', 'diana', 'frank', 'george'];
// Реализуй функции:
// 1. Найди пользователей во ВСЕХ трёх соцсетях
// 2. Найди пользователей хотя бы в ОДНОЙ соцсети
// 3. Найди пользователей ТОЛЬКО в Instagram🔍 Задание 2: SQL-запросы
Представь базу данных интернет-магазина. Как бы ты написал SQL-запрос для поиска товаров, которые:
- В категории "Электроника" И стоят меньше 10000 руб
- Имеют рейтинг > 4.5 ИЛИ количество отзывов > 100
- НЕ распроданы И НЕ сняты с производства
Какие операции над множествами здесь используются?
📊 Задание 3: Анализ данных
В твоей школе провели опрос о любимых предметах среди 120 учеников:
- Математику любят 65 человек
- Информатику любят 58 человек
- Физику любят 47 человек
- Математику И информатику — 32
- Математику И физику — 28
- Информатику И физику — 21
- Все три предмета — 15
Вопросы:
- Сколько учеников любят хотя бы один из этих предметов?
- Сколько не любят ни один из них?
- Сколько любят ровно один предмет?
🎮 Задание 4: Игровая механика
Ты разрабатываешь RPG-игру. У игрока есть:
- Множество изученных заклинаний
- Множество доступных квестов
- Множество открытых локаций
Придумай игровую механику, которая использует:
- Пересечение множеств (например, квесты, для которых нужны определённые заклинания)
- Объединение (доступный контент)
- Дополнение (что ещё предстоит открыть)
