Булевы функции, СДНФ и СКНФ

Изучаем функции, у которых и входы, и выход — нули и единицы; именно из них собран любой процессор.

Булева функция от n переменных — это функция, которая каждому набору из n нулей и единиц сопоставляет 0 или 1.

Зачем нужна булева алгебра

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

Что такое булева функция

Булева функция полностью задаётся таблицей истинности: для каждого из 2^n наборов входных значений указано, что функция выдаёт — 0 или 1. По сути это та же таблица, что и для логических формул, только теперь мы смотрим на неё как на функцию: вход — двоичный набор, выход — бит.

Сколько вообще существует булевых функций от n переменных? У таблицы 2^n строк, и в каждой выход может быть 0 или 1 независимо. По правилу произведения: 2^(2^n) функций. Для n = 2 это 2^4 = 16 функций, для n = 3 уже 2^8 = 256. Среди функций двух переменных — все знакомые связки: И, ИЛИ, импликация, xor, а также константы 0 и 1, штрих Шеффера (НЕ-И) и стрелка Пирса (НЕ-ИЛИ).

Как записать функцию формулой: СДНФ

Допустим, функция задана таблицей. Как получить для неё формулу? Самый прямой способ — совершенная дизъюнктивная нормальная форма (СДНФ). Рецепт:

1. Берём все строки таблицы, где функция равна 1.
2. Для каждой такой строки пишем конъюнкцию (И) всех переменных: переменную берём «как есть», если в строке она 1, и с отрицанием, если 0.
3. Соединяем все эти конъюнкции дизъюнкцией (ИЛИ).

Идея проста: каждая конъюнкция «срабатывает» (даёт 1) ровно на одной строке таблицы — на той, для которой составлена. Их «ИЛИ» даёт 1 в точности на нужных строках. Соберём СДНФ программно.

from itertools import product

# Функция f(a,b,c) = (a И b) ИЛИ (НЕ c)
def f(a, b, c):
    return (a and b) or (not c)

rows = []
print("a b c | f")
for a, b, c in product([0, 1], repeat=3):
    v = int(f(a, b, c))
    rows.append((a, b, c, v))
    print(f"{a} {b} {c} | {v}")

# Строим СДНФ: дизъюнкция конъюнкций по строкам, где f = 1
terms = []
for a, b, c, v in rows:
    if v == 1:
        lit = []
        lit.append("a" if a else "¬a")
        lit.append("b" if b else "¬b")
        lit.append("c" if c else "¬c")
        terms.append("(" + "∧".join(lit) + ")")
print("СДНФ:", " ∨ ".join(terms))

Вывод:

a b c | f
0 0 0 | 1
0 0 1 | 0
0 1 0 | 1
0 1 1 | 0
1 0 0 | 1
1 0 1 | 0
1 1 0 | 1
1 1 1 | 1
СДНФ: (¬a∧¬b∧¬c) ∨ (¬a∧b∧¬c) ∨ (a∧¬b∧¬c) ∨ (a∧b∧¬c) ∨ (a∧b∧c)

Программа взяла каждую строку с единицей и собрала для неё конъюнкцию, а потом соединила их через «ИЛИ». Получилась формула, которая в точности воспроизводит таблицу. Это универсальный факт: любую булеву функцию (кроме тождественного нуля) можно записать в СДНФ — то есть через И, ИЛИ, НЕ. Эта формула не самая короткая, но гарантированно правильная.

СКНФ — двойственный способ

Совершенная конъюнктивная нормальная форма (СКНФ) строится зеркально, по строкам, где функция равна 0:

1. Берём строки, где функция = 0.
2. Для каждой пишем дизъюнкцию (ИЛИ) переменных: переменную с отрицанием, если в строке она 1, и без отрицания, если 0 (всё наоборот относительно СДНФ).
3. Соединяем дизъюнкции конъюнкцией (И).

Здесь каждая дизъюнкция, наоборот, даёт 0 ровно на «своей» строке, а их «И» обнуляет функцию в точности там, где нужно. СДНФ удобна, когда единиц в таблице мало; СКНФ — когда мало нулей. Обе формы дают одну и ту же функцию, просто записанную разными «кирпичиками».

Зачем нужны нормальные формы

СДНФ и СКНФ — это канонические представления: у каждой функции они единственны. Это удобно для сравнения функций (равны ли две формулы — приведём обе к СДНФ и сравним), для синтеза логических схем (формула напрямую превращается в схему из вентилей) и для алгоритмов вроде SAT-решателей, которые работают с КНФ. Но за универсальность платят размером: СДНФ часто громоздка, поэтому следующий шаг — её минимизация.

P против NP: главная загадка информатики на примере графов

Контраст между эйлеровыми и гамильтоновыми путями — это окно в самую известную открытую проблему информатики, P против NP. Задачи класса P решаются «быстро» (за полиномиальное время) — как проверка эйлеровости по чётности степеней. Задачи класса NP — это те, где готовый ответ можно быстро проверить, даже если найти его трудно: дан маршрут — легко убедиться, что он гамильтонов, но найти такой маршрут с нуля, похоже, требует перебора.

Вопрос «равны ли P и NP» (то есть: верно ли, что всё легко проверяемое ещё и легко решаемо?) остаётся без ответа более полувека, и за его решение назначена премия в миллион долларов. Большинство учёных верит, что P ≠ NP — то есть для гамильтонова цикла, задачи коммивояжёра и сотен других NP-полных задач быстрого алгоритма не существует. Практический вывод для программиста: столкнувшись с NP-полной задачей, не нужно искать идеальный быстрый алгоритм (его, скорее всего, нет) — разумнее применять приближённые методы и эвристики. Теория графов даёт самые наглядные примеры этой фундаментальной границы вычислимого.

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

• Перепутать «как есть» и «с отрицанием». В СДНФ переменная берётся с отрицанием там, где в строке стоит 0. В СКНФ — наоборот. Эту инверсию легко спутать.
• Строить СДНФ по нулям (или СКНФ по единицам). СДНФ — по строкам с единицей, СКНФ — по строкам с нулём. Перепутаешь — получишь отрицание функции.
• Считать число функций как 2^n. Функций от n переменных 2^(2^n), а 2^n — это лишь число строк таблицы.

Итог

• Булева функция сопоставляет набору битов бит; задаётся таблицей истинности из 2^n строк.
• Функций от n переменных ровно 2^(2^n).
• СДНФ строят по строкам-единицам (И-термы, объединённые ИЛИ); СКНФ — по строкам-нулям (зеркально).
• Любая функция выразима через И, ИЛИ, НЕ; нормальные формы канонические, но не минимальные.