Законы алгебры множеств, мощность и декартово произведение

Собираем «алгебру множеств»: тождества, законы де Моргана, булеан размера 2 в степени n и декартово произведение.

Декартово произведение A × B — множество всех упорядоченных пар (a, b), где a ∈ A и b ∈ B.

Зачем нужны законы множеств

Операции над множествами подчиняются законам, очень похожим на школьную алгебру: есть свои «коммутативность», «скобки раскрываются», есть аналог формулы для «минуса перед скобкой». Зная их, можно упрощать сложные выражения с фильтрами и условиями, не перебирая элементы. А декартово произведение — это фундамент, на котором мы построим отношения, функции и таблицы баз данных. Без него не будет следующего раздела.

Основные законы алгебры множеств

Вот ядро тождеств. Все они доказываются одинаково — через «элемент принадлежит левой части тогда и только тогда, когда принадлежит правой».

Особенно важны законы де Моргана: «дополнение объединения — это пересечение дополнений, и наоборот». Словами: «не (A или B)» = «не A и не B». Эти же законы дословно повторятся в логике («не (p или q) = не p и не q») и в булевой алгебре. Это один и тот же закон в трёх костюмах.

Как доказать тождество «на пальцах»

Докажем дистрибутивность A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). Возьмём произвольный элемент x и проследим обе стороны:

• x ∈ A ∩ (B ∪ C) означает: x в A, И x в (B или C). То есть «x в A» и («x в B» или «x в C»).
• По дистрибутивности логического «и» относительно «или» это то же самое, что: («x в A и в B») или («x в A и в C»).
• А это и есть x ∈ (A ∩ B) ∪ (A ∩ C).

Раз каждый элемент левой части лежит в правой и обратно — множества равны. Заметь: доказательство про множества свелось к свойству логических связок. Так всегда: алгебра множеств — это «надетая» на множества логика.

Булеан: множество всех подмножеств

Булеан (или степенное множество) P(A) — это множество всех подмножеств множества A, включая пустое и само A. Например, для A = {a, b}:

P(A) = { ∅, {a}, {b}, {a, b} } — четыре подмножества.

Ключевой факт: если в множестве n элементов, то у него ровно 2 в степени n подмножеств. Интуиция простая: формируя подмножество, для каждого из n элементов мы принимаем независимое решение «взять или не взять» — два варианта на каждый элемент, итого 2·2·...·2 = 2^n комбинаций. Это первый мостик к комбинаторике: подмножества — это двоичные строки длины n.

Декартово произведение

В отличие от объединения, декартово произведение строит не элементы, а пары. A × B — множество всех упорядоченных пар (a, b), где первый элемент из A, второй из B. Здесь порядок важен: (1, 2) ≠ (2, 1).

Главная формула: |A × B| = |A| · |B|. Для каждого из |A| вариантов первого элемента есть |B| вариантов второго — перемножаем. Декартово произведение — это математическая модель «таблицы»: строки из A, столбцы из B, и пара (a, b) — клетка на их пересечении. Именно так устроены таблицы в базах данных и координаты на плоскости (R × R — это вся плоскость).

Проверяем всё машиной

Соберём три проверки: число подмножеств = 2^n, размер декартова произведения = произведению, и закон де Моргана на случайных множествах.

from itertools import chain, combinations, product
import random

def powerset(s):
    s = list(s)
    return list(chain.from_iterable(combinations(s, r) for r in range(len(s) + 1)))

A = {'a', 'b', 'c'}
ps = powerset(A)
print("Подмножеств у {a,b,c}:", len(ps), "= 2^3 =", 2 ** 3)

# Декартово произведение
X, Y = {1, 2, 3}, {'x', 'y'}
pairs = [(a, b) for a in sorted(X) for b in sorted(Y)]
print("|X × Y| =", len(pairs), "= |X|*|Y| =", len(X) * len(Y))
print("Пары:", pairs)

# Закон де Моргана на 1000 случайных тройках множеств
U = set(range(8))
ok = True
random.seed(1)
for _ in range(1000):
    a = set(random.sample(range(8), random.randint(0, 8)))
    b = set(random.sample(range(8), random.randint(0, 8)))
    # дополнение(a ∪ b) == дополнение(a) ∩ дополнение(b)
    if (U - (a | b)) != ((U - a) & (U - b)):
        ok = False
print("Закон де Моргана выполнен на 1000 проверок:", ok)

Вывод:

Подмножеств у {a,b,c}: 8 = 2^3 = 8
|X × Y| = 6 = |X|*|Y| = 6
Пары: [(1, 'x'), (1, 'y'), (2, 'x'), (2, 'y'), (3, 'x'), (3, 'y')]
Закон де Моргана выполнен на 1000 проверок: True

Машина за нас перебрала тысячу случайных конфигураций и ни разу не нашла нарушения де Моргана. Это, конечно, не доказательство (доказательство мы привели выше словами), но отличная проверка, что мы ничего не напутали в формулировке.

Битовые множества: как операции живут в процессоре

Операции над множествами — это не абстракция: процессор выполняет их одной командой. Если универсум невелик (скажем, не больше 64 элементов), множество удобно хранить как битовую маску — целое число, где i-й бит равен 1, если элемент i в множестве. Тогда:

• объединение A ∪ B — это побитовое ИЛИ (A | B);
• пересечение A ∩ B — побитовое И (A & B);
• симметрическая разность A △ B — побитовое исключающее ИЛИ (A ^ B).

Это совпадение обозначений в Python (|, &, ^ работают и для set, и для битов) не случайно — за ним стоит одна и та же булева логика. Битовые множества невероятно быстры и компактны, поэтому их используют в шахматных движках (доска — это 64 бита), в планировщиках, в алгоритмах на подмножествах. Так теория множеств напрямую превращается в высокопроизводительный код.

Типичные ошибки

• Терять степень в булеане. Подмножеств у n-элементного множества 2^n, а не n^2 и не 2n. Для 10 элементов это уже 1024.
• Забывать порядок в парах. В декартовом произведении (a, b) и (b, a) — разные элементы.
• Применять де Моргана наполовину. Меняется не только операция (∪ на ∩), но и каждый член берётся под дополнение. «Дополнение(A ∪ B) = Ā ∩ B̄», а не «Ā ∩ B».

Итог

• Операции множеств подчиняются законам (коммутативность, дистрибутивность, де Моргана), которые доказываются через логику.
• Булеан P(A) содержит все подмножества; их ровно 2^n.
• Декартово произведение даёт пары; |A × B| = |A| · |B|; порядок в паре важен.
• Эти идеи — фундамент для отношений, функций и комбинаторики.