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

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

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

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

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

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

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

Длина и ранг

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

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

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

Для каждой функции f рассматривают её минимальную \(\psi\)-сложность \(\psi (f)\). Затем переходят от одной функции к целому классу \(P_{2}(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 \(= x_{1}x_{2} \vee \neg x_{1}x_{3}\). В ней две элементарные конъюнкции, поэтому \(\lambda (A)=2\). В каждой конъюнкции по два литерала, поэтому \(R(A)=4\). Если найдётся эквивалентная ДНФ из двух конъюнкций, но суммарно из трёх литералов, длина не уменьшится, а ранг уменьшится. Именно поэтому «кратчайшая» и «минимальная» не являются синонимами.

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

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

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

Источники

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