Сложность ДНФ: минимальные и кратчайшие ДНФ, функции Шеннона

Сложность ДНФ измеряют различными функционалами. В курсе основными являются длина \(\lambda (A)\) — число элементарных конъюнкций, и ранг \(R(A)\) — суммарное число литералов во всех конъюнкциях. ДНФ, минимальная по длине, называется кратчайшей, а минимальная по рангу — минимальной.¹

Для произвольного функционала сложности ψ минимизация означает поиск эквивалентной ДНФ с наименьшим ψ. Функция Шеннона \(\psi (n)\) — максимальная среди всех ФАЛ n переменных минимальная ψ-сложность. Для длины и ранга в курсе получены \(\lambda(n)=2^{n-1}\) и \(R(n)=n\cdot 2^{n-1}\).¹

Что важно запомнить

Длина \(\lambda (A)\) — число конъюнктов ДНФ.
Ранг \(R(A)\) — сумма рангов её элементарных конъюнкций, то есть общее число вхождений литералов.
Кратчайшая ДНФ минимизирует длину.
Минимальная ДНФ в терминологии курса минимизирует ранг.
Функция Шеннона \(\psi (n)\) показывает худшую минимальную сложность среди всех ФАЛ n переменных.¹

Функционал сложности

Разные реализации одной булевой функции могут иметь разный размер. Чтобы говорить об оптимальности, на ДНФ задают неотрицательный функционал сложности ψ(A). В курсе предполагается естественная монотонность: удаление букв или целых элементарных конъюнкций не должно увеличивать сложность. Тогда ψ-минимальной называют ДНФ A, реализующую f и имеющую наименьшее значение ψ среди всех ДНФ этой функции.¹

Длина и ранг

Длина \(\lambda (A)\) — число элементарных конъюнкций в ДНФ. Ранг \(R(A)\) — сумма рангов всех входящих в неё конъюнкций, то есть суммарное число литералов. Поэтому две ДНФ одинаковой длины могут заметно различаться по рангу.

В принятой в курсе терминологии λ-минимальную ДНФ называют кратчайшей, а R-минимальную — просто минимальной. Это разные задачи оптимизации. Одна форма может иметь минимальное число конъюнктов, но не минимальное общее число литералов.¹

Функции Шеннона

Для каждой функции f рассматривают её минимальную ψ-сложность ψ(f). Затем переходят от одной функции к целому классу P2(n) всех ФАЛ n переменных и определяют

\(\psi (n) = \max \psi (f), f\in P_{2}(n)\).

Эта величина называется функцией Шеннона для выбранного функционала. Она отвечает на вопрос: насколько сложной в худшем случае может быть оптимальная ДНФ функции от n переменных. Для двух основных параметров лекционный курс даёт точные значения \(\lambda(n)=2^{n-1}\) и \(R(n)=n\cdot 2^{n-1}\). Нижняя граница достигается на существенных линейных функциях, единственная ДНФ которых является совершенной.¹

Типичные значения этих параметров и эффект Шеннона образуют отдельную тему курса и рассматриваются отдельно от базовых определений сложности.²

Пример простыми словами

Пусть A = x1x2 ∨ ¬x1x3. В ней две элементарные конъюнкции, поэтому λ(A)=2. В каждой конъюнкции по два литерала, поэтому R(A)=4. Если найдётся эквивалентная ДНФ из двух конъюнкций, но суммарно из трёх литералов, длина не уменьшится, а ранг уменьшится. Именно поэтому «кратчайшая» и «минимальная» не являются синонимами.

Частые ошибки

Путать длину и ранг ДНФ.
Использовать слова «минимальная» и «кратчайшая» как синонимы. В этом курсе они относятся к разным функционалам.
Считать ψ(n) сложностью конкретной функции. Это максимум минимальной сложности по всему классу P2(n).

Другие вопросы

Источники

1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 1, §7, лемма 7.1, МГУ, факультет ВМК
2 Курс «Основы кибернетики» для бакалавров направления 01400 «Прикладная математика и информатика» 2026–2027 уч. год, раздел 3, блок I, ВМК МГУ