Полные системы булевых функций

Выясняем, какого минимума операций достаточно, чтобы выразить вообще любую булеву функцию — и почему весь компьютер можно собрать из одного типа вентиля.

Система булевых функций полна (функционально полна), если через неё можно выразить любую булеву функцию.

Зачем это нужно

Когда инженер проектирует процессор, он не делает отдельный физический элемент для каждой из бесконечного множества функций. Он выбирает маленький базис — набор операций, из которых собирается всё остальное. Вопрос «какой минимальный набор достаточен» — это вопрос функциональной полноты. Ответ удивителен и красив: достаточно одной операции (НЕ-И или НЕ-ИЛИ), и из неё одной строится любая логика, а значит — весь компьютер. Это фундаментальный факт, объясняющий, почему реальные микросхемы массово делают на однотипных вентилях NAND.

Базовый набор: И, ИЛИ, НЕ

Мы уже знаем из урока про СДНФ: любая булева функция выразима через И, ИЛИ, НЕ — ведь СДНФ использует только их. Значит, система {И, ИЛИ, НЕ} функционально полна. Это наш отправной базис. Но можно ли меньше?

Да. По закону де Моргана a ∨ b = ¬(¬a ∧ ¬b) — «ИЛИ» выражается через «И» и «НЕ». Значит, {И, НЕ} уже полна, «ИЛИ» лишнее. Аналогично полна {ИЛИ, НЕ}. А можно ли обойтись вообще одной операцией?

Штрих Шеффера: одна операция правит всем

Штрих Шеффера (операция НЕ-И, англ. NAND) определяется как a | b = ¬(a ∧ b) — «не верно, что оба истинны». Поразительный факт: одной этой операции достаточно, чтобы выразить любую булеву функцию. Покажем, как из НЕ-И собираются базовые НЕ, И, ИЛИ:

НЕ: ¬a = a | a (НЕ-И числа с самим собой: ¬(a ∧ a) = ¬a).
И: a ∧ b = ¬(a | b) = (a | b) | (a | b) (взяли НЕ-И, затем отрицание через НЕ-И).
ИЛИ: a ∨ b = (a | a) | (b | b) (отрицаем оба, потом НЕ-И — по де Моргану получается ИЛИ).

Раз через НЕ-И выражаются И, ИЛИ, НЕ — а они полны — то и сам НЕ-И полон. Проверим эти построения кодом: соберём из одной функции nand все базовые операции и сверим таблицы.

from itertools import product

def nand(x, y):
    return int(not (x and y))     # единственный «кирпич» — НЕ-И

# Собираем базовые операции ТОЛЬКО из nand
NOT = lambda x: nand(x, x)
AND = lambda x, y: NOT(nand(x, y))
OR  = lambda x, y: nand(NOT(x), NOT(y))

print("НЕ:  ¬0 =", NOT(0), " ¬1 =", NOT(1))
print("И:   таблица =", [AND(a, b) for a, b in product([0, 1], repeat=2)])
print("ИЛИ: таблица =", [OR(a, b) for a, b in product([0, 1], repeat=2)])

# Проверяем, что собранные операции совпадают с настоящими
ok = all(AND(a, b) == (a and b) and OR(a, b) == (a or b)
         for a, b in product([0, 1], repeat=2))
print("Все операции воспроизведены из NAND:", ok)

Вывод:

НЕ:  ¬0 = 1  ¬1 = 0
И:   таблица = [0, 0, 0, 1]
ИЛИ: таблица = [0, 1, 1, 1]
Все операции воспроизведены из NAND: True

Из одной-единственной функции nand мы собрали НЕ, И и ИЛИ — и их таблицы точно совпали с настоящими. А раз эти три операции полны, значит, и весь арсенал булевых функций выразим через NAND. Именно поэтому в реальной микроэлектронике вентиль NAND — рабочая лошадка: однотипные элементы проще и дешевле производить, а собрать из них можно что угодно. Стрелка Пирса (НЕ-ИЛИ, NOR) обладает тем же свойством.

Теорема Поста: точный критерий полноты

Откуда заранее знать, полна система или нет, не выражая всё вручную? Ответ даёт теорема Поста. Эмиль Пост выделил пять специальных замкнутых классов булевых функций:

сохраняющие ноль (на нулевом наборе дают 0);
сохраняющие единицу (на единичном наборе дают 1);
самодвойственные;
монотонные;
линейные.

Теорема Поста: система функций полна тогда и только тогда, когда для каждого из этих пяти классов в системе найдётся функция, не входящая в этот класс. Иначе говоря, чтобы быть полной, система должна «пробивать» все пять классов сразу. Это удивительно конкретный критерий: вместо бесконечной проверки выразимости достаточно проверить пять свойств. Например, НЕ-И не сохраняет 0, не сохраняет 1, не самодвойственна, не монотонна и не линейна — пробивает все классы, поэтому одна-единственная образует полную систему.

Сумматор из вентилей: как из логики собирают арифметику

Доведём связь «формула → схема» до конца и соберём то, что лежит в основе любого процессора, — сумматор. Сложение двух битов a и b даёт два выходных бита: бит суммы и бит переноса. Их булевы функции мы уже умеем вывести из таблицы истинности: бит суммы равен a ⊕ b (исключающее ИЛИ — единица, когда биты разные), а бит переноса равен a ∧ b (перенос есть, только если оба равны 1). Это полусумматор.

def half_adder(a, b):
    summ = a ^ b        # бит суммы  = XOR
    carry = a & b       # бит переноса = AND
    return summ, carry

for a in (0, 1):
    for b in (0, 1):
        s, c = half_adder(a, b)
        print(f"{a} + {b}: сумма={s}, перенос={c}")

Вывод:

0 + 0: сумма=0, перенос=0
0 + 1: сумма=1, перенос=0
1 + 0: сумма=1, перенос=0
1 + 1: сумма=0, перенос=1

Видно: 1 + 1 даёт сумму 0 и перенос 1 — то есть «10» в двоичной системе, ровно как должно быть. Соединяя полусумматоры в цепочку (передавая перенос дальше), инженеры строят полные сумматоры на 8, 32, 64 бита. Минимизация булевых функций здесь напрямую экономит вентили в этих миллиардно повторяющихся блоках — поэтому она и важна. Так несколько простых логических операций складываются в арифметику настоящего компьютера.

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

Думать, что для полноты нужно много операций. Хватает одной (NAND или NOR). Минимализм здесь — не теоретическая экзотика, а основа реальной схемотехники.
Считать любую популярную систему полной. Например, {И, ИЛИ} без отрицания не полна: из них нельзя получить НЕ (обе монотонны — не пробивают класс монотонных).
Путать полноту с минимальностью. Система может быть полной, но избыточной (как {И, ИЛИ, НЕ}, где ИЛИ лишнее). Полнота — про «достаточно», минимальность — про «без лишнего».

Итог

Система полна, если через неё выразима любая булева функция.
{И, ИЛИ, НЕ} полна (СДНФ); достаточно даже {И, НЕ} или {ИЛИ, НЕ}.
Штрих Шеффера (НЕ-И) и стрелка Пирса (НЕ-ИЛИ) — каждая в одиночку образует полную систему; на NAND строят процессоры.
Теорема Поста: система полна ⟺ она пробивает все пять замкнутых классов Поста.