Методы синтеза схем на основе ДНФ и верхние оценки сложности

Для ненулевой ФАЛ f самый прямой метод синтеза — реализовать её совершенную ДНФ. Если \(N_f\) — множество единичных наборов, существует формула \(F_f\) с \(L(F_f)\le 2n\cdot |N_f|-1\) и π-схема \(\Sigma_f\) с \(L(\Sigma_f)\le n|N_f|\). Нулевая функция реализуется отдельно формулой и π-схемой сложности 2. Отсюда следуют верхние оценки функций Шеннона \(L^\Phi(n)\le n\cdot 2^{n+1}-1\) и \(L^\pi(n)\le n\cdot 2^n\).1

Более экономная конструкция использует контактное дерево порядка n. Для f≠0 получаются \(L(\Sigma_f)\le 2^n+|N_f|-2\) и \(L(F_f)\le 2^{n+1}+|N_f|-4\), а значит \(L^\pi(n)\le 2^{n+1}-2\) и \(L^\Phi(n)\le 3\cdot 2^n-4\).1

Что важно запомнить
  • Моделирование СДНФ даёт \(L(F_f)\le 2n|N_f|-1\) и \(L(\Sigma_f)\le n|N_f|\).1
  • В худшем случае \(|N_f|\le 2^n\), поэтому \(L^\Phi(n)\le n\cdot 2^{n+1}-1\) и \(L^\pi(n)\le n\cdot 2^n\).
  • Контактное дерево улучшает оценки до \(L(\Sigma_f)\le 2^n+|N_f|-2\) и \(L(F_f)\le 2^{n+1}+|N_f|-4\).1
  • Следствие: \(L^\pi(n)\le 2^{n+1}-2\), \(L^\Phi(n)\le 3\cdot 2^n-4\).
  • Это конструктивные верхние оценки, а не утверждения о минимальности построенных схем.

Синтез по совершенной ДНФ

Пусть f≠0. Для каждого единичного набора \(\alpha\in N_f\) строится элементарная конъюнкция ранга n, истинная только на α. Дизъюнкция всех таких конъюнкций есть СДНФ функции. Если буквально реализовать эту запись формулой и соответствующей π-схемой, получаются оценки

\(L(F_f)\le 2n\cdot |N_f|-1,\quad L(\Sigma_f)\le n|N_f|\). 1

Так как \(|N_f|\le 2^n\), отсюда для функций Шеннона следуют \(L^\Phi(n)\le n\cdot 2^{n+1}-1\) и \(L^\pi(n)\le n\cdot 2^n\). Поскольку формулы являются частным случаем СФЭ, а π-схемы — частным случаем КС, эти же конструкции дают \(L^C(n)\le L^\Phi(n)\) и \(L^K(n)\le L^\pi(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-местной ФАЛ существует реализация не сложнее указанного числа. Но построенная схема не обязана быть минимальной для конкретной функции. После синтеза её можно дополнительно упрощать эквивалентными преобразованиями.

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

Если функция равна 1 лишь на небольшом числе наборов, прямое моделирование СДНФ может быть вполне экономным. Для функций с большим \(|N_f|\) контактное дерево выгоднее, потому что общие проверки переменных не повторяются независимо в каждом минтерме.

Частые ошибки
  • Путать 2n с \(2^n\). В первой оценке 2n — линейный множитель, а число возможных наборов равно \(2^n\).
  • Считать полученные оценки нижними или точными. Они доказаны конкретными методами синтеза и потому являются верхними.
  • Забывать условие f≠0 в формулировках лемм. Нулевая функция реализуется отдельно.

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

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 3, §1, леммы 1.1–1.2 и следствия, МГУ, факультет ВМК