Синтез по совершенной ДНФ
Пусть f≠0. Для каждого единичного набора α∈N_f строится элементарная конъюнкция ранга n, истинная только на α. Дизъюнкция всех таких конъюнкций есть СДНФ функции. Если буквально реализовать эту запись формулой и соответствующей π-схемой, получаются оценки
\(L(F_f)\le 2n\cdot |N_f|-1,\quad L(\Sigma_f)\le n|N_f|\). 1
Так как |N_f|≤2^n, отсюда для функций Шеннона следуют L^Φ(n)≤n·2^(n+1)−1 и L^π(n)≤n·2^n. Поскольку формулы являются частным случаем СФЭ, а π-схемы — частным случаем КС, эти же конструкции дают L^C(n)≤L^Φ(n) и L^K(n)≤L^π(n). Метод универсален для ненулевых функций, а f=0 реализуется отдельно.1
Улучшение с помощью контактного дерева
Контактное дерево порядка n одновременно реализует все 2^n элементарных конъюнкций в своих выходах, разделяя общие начальные фрагменты путей. Для конкретной f удаляют выходы, соответствующие наборам, не входящим в N_f, а остальные выходы отождествляют. После приведения получается π-схема
\(L(\Sigma_f)\le 2^n+|N_f|-2\). 1
Моделируя её формулой с поднятыми отрицаниями, получают \(L(F_f)\le 2^{n+1}+|N_f|-4\). При максимизации по f:
\(L^\pi (n)\le 2^{n+1}-2,\quad L^\Phi (n)\le 3\cdot 2^n-4\). 1
Как интерпретировать верхнюю оценку
Каждая такая граница сопровождается явной конструкцией схемы. Поэтому она гарантирует: для любой n-местной ФАЛ существует реализация не сложнее указанного числа. Но построенная схема не обязана быть минимальной для конкретной функции. После синтеза её можно дополнительно упрощать эквивалентными преобразованиями.