Решётки и булевы алгебры

Решётка

Частично упорядоченное множество L — решётка, если для любых двух элементов a, b существуют:

sup{a,b} = a∨b (объединение, наименьшая верхняя грань)
inf{a,b} = a∧b (пересечение, наибольшая нижняя грань)

Примеры: (2^A, ⊆) — решётка подмножеств. (ℕ, |) — решётка по делимости: a∨b = НОК(a,b), a∧b = НОД(a,b). Подпространства векторного пространства.

Булева алгебра

Дистрибутивная дополненная решётка: выполняются дистрибутивные законы a∧(b∨c) = (a∧b)∨(a∧c) и дополнение aᶜ такое, что a∧aᶜ = 0, a∨aᶜ = 1.

Теорема Стоуна: Каждая конечная булева алгебра изоморфна алгебре подмножеств некоторого конечного множества. Размер — степень двойки.

Булевы функции

Функция f: {0,1}ⁿ → {0,1}. Задаётся таблицей истинности (2ⁿ строк).

Основные: NOT(x) = 1−x; AND(x,y) = min(x,y) = x·y; OR(x,y) = max(x,y) = x+y−xy; XOR = x⊕y = (x+y) mod 2.

NAND = NOT AND: самодостаточный базис — из одного NAND можно выразить все функции.

Все булевы функции = 2^{2^n} (очень быстро растёт: для n=3 уже 256 функций).

Алгебра Хантингтона и решёточные тождества

Булева алгебра — это алгебра с двумя бинарными операциями (∧, ∨), унарной (¬) и двумя константами (0, 1), удовлетворяющими постулатам Хантингтона: коммутативность, дистрибутивность ∧ над ∨ и ∨ над ∧, закон дополнения. Из этих аксиом выводятся все остальные тождества: идемпотентность (x∧x=x), поглощение (x∧(x∨y)=x), двойное отрицание (¬¬x=x), законы де Моргана.

Дистрибутивность — ключевое отличие булевой алгебры от общих решёток: не каждая решётка дистрибутивна. Пример недистрибутивных решёток: M₅ (ромб с тремя элементами на среднем уровне) и N₅ (пятиэлементная решётка в форме пятиугольника). Теорема Биркгофа: решётка дистрибутивна тогда и только тогда, когда не содержит подрешётки, изоморфной M₅ или N₅.

Минимизация булевых функций: практика

Задача минимизации — найти эквивалентную формулу с минимальным числом литералов (переменных и их отрицаний). Это прямо влияет на стоимость производства схем: меньше вентилей → меньше площадь чипа → дешевле производство.

Карта Карно (1953) — двумерная таблица, где соседние клетки отличаются ровно одним литералом (код Грея). Группируя клетки с единицами в прямоугольники размером степень двойки, находим простые импликанты. Метод работает для функций до 5-6 переменных визуально.

Метод Куайна-Маккласки (1956) — табличный алгоритм, эквивалентный картам Карно, но пригодный для любого числа переменных. Работает в два этапа: нахождение всех простых импликант (минтермы, отличающиеся на один бит, сливаются); выбор покрытия минимальным числом импликант. Сложность — NP-трудная задача в общем случае.

Применения булевой алгебры в САПР и верификации

В системах САПР (системах автоматизированного проектирования) синтез цифровых схем — это задача поиска схемы минимального размера, реализующей заданную булеву функцию. Современные инструменты (Synopsys Design Compiler, Cadence Genus) используют эвристики, основанные на алгебраических преобразованиях булевых формул.

Формальная верификация использует булевы методы для доказательства корректности схем. BDD (Binary Decision Diagram, Брайант, 1986) — канонический граф для булевых функций. BDD позволяет проверять эквивалентность двух схем за полиномиальное время, что критично при проверке процессорных ядер. Метод SAT-решателей (Boolean Satisfiability) — поиск входа, при котором функция равна 1 — является основой формальной верификации программного обеспечения и аппаратуры.

Конечные поля и коды Рида-Соломона

Конечное поле GF(pⁿ) — поле из pⁿ элементов. GF(2ⁿ) используется в криптографии (AES работает в GF(2⁸)) и теории кодирования. Элементы GF(2⁸): полиномы степени ≤ 7 над GF(2), с умножением по модулю неприводимого полинома степени 8.

Коды Рида-Соломона (RS-коды) — коды с исправлением ошибок над конечными полями. RS(n, k) над GF(q) кодирует k символов в n > k. Может исправить до (n−k)/2 ошибок и (n−k) стираний. Применяется в DVD/Blu-Ray, QR-кодах, спутниковой связи. Алгоритм декодирования использует интерполяцию Лагранжа в конечном поле.

Булева сложность схем

Схемная сложность функции f: {0,1}ⁿ → {0,1} — минимальное число вентилей AND/OR/NOT для вычисления f. Большинство функций требуют экспоненциальных схем, но конкретных нижних оценок для естественных функций получить трудно. Это одна из центральных открытых проблем Computer Science. Теорема Шеннона: случайная n-переменная булева функция с высокой вероятностью требует схему размера Θ(2ⁿ/n).

BDD и символическое представление булевых функций

Binary Decision Diagram (BDD): направленный ациклический граф, компактно представляющий булеву функцию. Ordered BDD (OBDD): переменные встречаются в фиксированном порядке — нормальная форма. Редуцированный OBDD (ROBDD): канонический. Операции (AND, OR, NOT) за O(|BDD₁|·|BDD₂|). Применяется в верификации аппаратного обеспечения (model checking). Некоторые функции имеют экспоненциальный BDD при любом порядке переменных.

Численный пример: минимизация булевой функции

Задача: Минимизировать f(a,b,c) с таблицей истинности: f=1 при (a,b,c)∈{(0,0,1),(0,1,1),(1,0,1),(1,1,1)}.

Шаг 1: f=1 тогда и только тогда, когда c=1, при любых a,b. Всего 4 единичных минтерма из 8.

Шаг 2: Карта Карно (3 переменных): столбец c=1 полностью заполнен единицами — одна группа из 4.

Шаг 3: Группировка 4 клеток соответствует литералу c (ни a, ни b не меняют значения f). Минимальная DNF: f = c.

Шаг 4: BDD для f = c: граф из одного внутреннего узла «c» с двумя листьями (0 и 1) — размер BDD равен 1 вентилю, тогда как DNF из 4 минтермов потребует 4 AND + 3 OR = 7 вентилей. Оптимизация через BDD сократила схему в 7 раз.