Статья Автор: Деникина Н.В., Деникин А.В.

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

Алгебра логики
⊕
 
Формы представления булевых функций
СДНФ · Полином Жегалкина · Карты Карно · BDD · WHT · Шеннон
📋
СДНФ и СКНФ
совершенные нормальные формы · «школьный» стандарт
Что это такое
 

Любую булеву функцию можно записать двумя «каноническими» способами, глядя на её таблицу истинности.

СДНФ

Смотрим на строки, где f = 1. Для каждой пишем конъюнкцию всех переменных (переменная отрицается, если в строке она = 0). Соединяем знаком ∨.

СКНФ

Смотрим на строки, где f = 0. Для каждой пишем дизъюнкцию всех переменных (без отрицания, если в строке она = 0). Соединяем знаком ∧.

Пример — функция «ИЛИ»: f = A ∨ B
 
A B f = A∨B → СДНФ → СКНФ
0 0 0 — (A ∨ B)
0 1 1 (¬A ∧ B) —
1 0 1 (A ∧ ¬B) —
1 1 1 (A ∧ B) —
СДНФ: (¬A ∧ B) ∨ (A ∧ ¬B) ∨ (A ∧ B)
СКНФ: (A ∨ B)
Плюсы и минусы
 
✓ Всегда существует ✓ Уникальна ✓ Легко строится ✗ Может быть огромной ✗ Неоптимальна

При n = 20 переменных СДНФ может содержать больше 500 тысяч конъюнкций — по одной на каждую единичную строку таблицы истинности.

⊕
Полином Жегалкина
алгебраическая нормальная форма (ANF) · только ⊕ и ∧
Иван Иванович Жегалкин (1869–1947) доказал, что любую булеву функцию можно записать как сумму (⊕) произведений (∧) переменных — без отрицаний вообще. Такая запись однозначна для каждой функции.
Общая запись
 
f(x₁,...,xₙ) = a₀ ⊕ a₁·x₁ ⊕ a₂·x₂ ⊕ ... ⊕ a₁₂·x₁∧x₂ ⊕ ... ⊕ a₁₂...ₙ·x₁∧...∧xₙ aᵢ ∈ {0, 1} — каждый член либо есть, либо его нет

Всего 2ⁿ коэффициентов. Полином однозначен для каждой функции.

Алгоритм построения — пример: f = A ⊕ B
 
1

Строим СДНФ

(¬A ∧ B) ∨ (A ∧ ¬B)
2

Заменяем ∨ на ⊕

(¬A ∧ B) ⊕ (A ∧ ¬B)
3

Заменяем отрицания: ¬X = X ⊕ 1

((A ⊕ 1) ∧ B) ⊕ (A ∧ (B ⊕ 1))
4

Раскрываем: X ∧ (Y ⊕ Z) = X∧Y ⊕ X∧Z

(A∧B ⊕ B) ⊕ (A∧B ⊕ A)
5

Убираем пары: X ⊕ X = 0

A ⊕ B ← готово! A∧B встречалось дважды и исчезло.
Линейные функции
 

Если в полиноме Жегалкина нет конъюнкций (нет слагаемых вида xᵢ∧xⱼ и выше), функция называется линейной.

Линейная: f = 1 ⊕ x₁ ⊕ x₃ ← нет ∧
Нелинейная: f = x₁ ⊕ x₁∧x₂ ← есть ∧
Важно для задачи про преобразователь Для 20 переменных коэффициентов a₀, a₁, ..., a₂₀ всего 21 штука, каждый 0 или 1. Итого линейных функций: 2²¹ − 1 = 2 097 151 (минус тождественный 0).
Криптография (AES, SHA) Теория кодирования Верификация схем
🗺️
Карты Карно
визуальная минимизация · проектирование схем
Идея
 

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

Ключевое правило Соседние клетки карты различаются ровно одной переменной (код Грея). Поэтому прямоугольник из 2ⁿ единиц = одна конъюнкция с «выпавшей» переменной.
Интерактивная карта (3 переменных: A, B, C)
 

Нажмите на клетку, чтобы поставить/убрать единицу — минимальная форма обновится автоматически.

  BC = 00 BC = 01 BC = 11 BC = 10
A = 0
A = 1
Минимальная дизъюнктивная форма: f = 0 (тождественный 0)
Попробуйте Включите клетки с C = 1 (столбцы BC=01 и BC=11) в обеих строках — получите f = C. Включите все 8 — f = 1.
Правила группировки
 
1

Размер группы — степень двойки

1, 2, 4, 8 клеток. Чем крупнее группа — тем короче конъюнкция.

2

Карта «заворачивается» как тор

Левый и правый края — соседи. Верхний и нижний — тоже.

3

Переменная исключается, если меняется в группе

Если в группе из 4 клеток A принимает и 0, и 1 — A из конъюнкции убирается.

🌳
BDD — бинарные диаграммы решений
Binary Decision Diagram · верификация и синтез схем
Что это такое
 

BDD — ориентированный граф. Каждый узел — вопрос о переменной, листья — значения 0 или 1. Двигаясь по ветвям, приходим к значению функции.

Упрощённый вариант ROBDD: переменные идут в фиксированном порядке, одинаковые поддеревья склеиваются — граф становится компактнее.

Диаграмма для f = A ∧ B
 
A B B 0 0 1 A=0 A=1 B=0 B=1 B=0 B=1

Пунктир = ветка «нет» (0), сплошная = ветка «да» (1)

Чтение: A = 0 → сразу 0. A = 1 → смотрим B. B = 0 → 0, B = 1 → 1.
Почему это мощно
 

Функцию равенства двух 32-битных чисел (64 переменные, 2⁶⁴ строк в таблице) ROBDD представляет всего 65 узлами.

Реальные применения Intel и AMD используют BDD для верификации процессоров. Ошибка в процессоре стоит сотни миллионов долларов — поэтому проверяют формально, а не тестами.
Верификация процессоров Formal verification Model checking
〜
Преобразование Уолша–Адамара
аналог преобразования Фурье · криптоанализ
Идея
 

Преобразование Фурье раскладывает сигнал по синусам. WHT делает то же для булевых функций — раскладывает по линейным функциям, показывая «насколько нелинейна» функция.

Шаг 1. Перекодируем: 0 → +1, 1 → −1 Шаг 2. Считаем коэффициент для каждого вектора a: Ŵf(a) = Σ f̂(x) · (−1)^(a·x mod 2)
Числовой пример: f = A ∧ B
 
Исходная таблица f
A B f f̂ (±1)
0 0 0 +1
0 1 0 +1
1 0 0 +1
1 1 1 −1
Коэффициенты WHT
a Ŵf(a) Смысл
00 +2 «постоянная»
01 −1 корреляция с B
10 −1 корреляция с A
11 +1 корреляция с A⊕B
Нелинейность: NL(f) = 2^(n−1) − ½ · max|Ŵf(a)| = 1 Чем выше нелинейность — тем стойче шифр к линейному криптоанализу.
Идеальные функции Bent-функции имеют максимально возможную нелинейность и используются в разработке шифров (AES, DES).
✂️
Разложение Шеннона
рекурсивное разбиение · основа схемотехники
Теорема Шеннона (1938)
 

Клод Шеннон показал: любую функцию можно рекурсивно разбить по любой переменной.

f(x₁, x₂, ..., xₙ) = ¬x₁ ∧ f(0, x₂,...,xₙ) ← подфункция при x₁ = 0 ∨ x₁ ∧ f(1, x₂,...,xₙ) ← подфункция при x₁ = 1
Пример: f = A ∨ B ∨ C
 
f(A, B, C) = A ∨ B ∨ C
↙ разбиваем по A ↘
A = 0
f(0,B,C) = B∨C
 
A = 1
f(1,B,C) = 1
↙ разбиваем по B ↘
B = 0 → C
 
B = 1 → 1
Итог: f = ¬A ∧ (¬B ∧ C ∨ B) ∨ A
Мультиплексор = Шеннон в железе
 

Мультиплексор MUX 2→1 реализует ровно формулу Шеннона:

out = ¬sel ∧ A ∨ sel ∧ B

На этом принципе строятся LUT в FPGA — программируемых схемах. Каждая LUT — маленький мультиплексор с записанной таблицей истинности.

FPGA / LUT Синтез схем Символьное выполнение
⚖️
Сравнение всех форм
что выбрать и когда
Одна информация — разные взгляды
 
Таблица истинности (2ⁿ строк)
↓
Схемотехника
Криптография
Формальные методы
Криптоанализ
Таблица сравнения
 
Форма Операции Уникальна? Компактность Применение
СДНФ / СКНФ ∧ ∨ ¬ Да Плохая Обучение, базовый анализ
Минимальная форма ∧ ∨ ¬ Нет Хорошая Синтез схем, FPGA
Полином Жегалкина ⊕ ∧ Да Средняя Криптография, теория
ROBDD граф Да* Зависит от порядка Верификация, Model checking
WHT числовая Да 2ⁿ чисел Криптоанализ, нелинейность
Разложение Шеннона ∧ ∨ ¬ Нет Рекурсивная FPGA LUT, мультиплексоры

* ROBDD уникален при фиксированном порядке переменных.

Числа о булевых функциях
 
Всего функций от n переменных: 2^(2ⁿ) n = 4: 2^16 = 65 536 n = 20: 2^1 048 576 ≈ 10^315 652
Линейных функций от n переменных: 2^(n+1) n = 20: 2^21 = 2 097 152 Без тождественного 0: 2 097 151
Вывод Подавляющее большинство функций — нелинейные. Линейных — ничтожно мало. Именно поэтому «найти линейное приближение» — нетривиальная задача, которую решают WHT-коэффициенты.
Печать