Дизъюнктивно-универсальное множество G⊆P₂(m) порядка m и ранга p — такое множество ФАЛ, что любую g∈P₂(m) можно представить как дизъюнкцию p функций из G: \(g=g_{1}\lor \ldots \lor g_p\)
Стандартное ДУМ строят по разбиению куба \(B^m\) на p частей. Для каждой части берут функции, которые равны нулю вне неё. Тогда произвольная g раскладывается на свои ограничения по компонентам разбиения. ДУМ позволяет заменить реализацию всех возможных m-местных функций общей реализацией значительно меньшего набора строительных
Что важно запомнить
- Порядок ДУМ m — число переменных функций из G.
- Ранг p — число функций из G, дизъюнкцией которых представляется произвольная
- При разбиении \(\Pi=(\pi_{1},\ldots,\pi_p)\) можно взять \(g_i=\psi_i\cdot g\), где \(\psi_i\) — характеристическая функция \(\pi_i\).
- Тогда \(g=g_{1}\lor \ldots \lor g_p\), а каждый \(g_i\) поддерживается только на своей части
- Если максимальная мощность части равна s, стандартная конструкция даёт \(|G|\le p\cdot 2^s\).
- ДУМ является инструментом компактного синтеза, а не функционально полным базисом в обычном смысле.
Определение
Множество G⊆P₂(m) называется дизъюнктивно-универсальным множеством порядка m и ранга p, если для любой m-местной ФАЛ g существуют \(g_{1},\ldots,g_p\in G\) такие, что \(g=g_{1}\lor \ldots \lor g_p\). Важен именно ограниченный набор готовых функций G, из которого можно собирать любую функцию
Стандартная конструкция по разбиению куба
Пусть \(\Pi=(\pi_{1},\ldots,\pi_p)\) разбивает \(B^m\), а \(\psi_i\) является характеристической функцией \(\pi_i\). Для каждой части \(\pi_i\) рассматривают множество G(i) функций, равных нулю вне \(\pi_i\). Тогда для произвольной g можно положить \(g_i=\psi_i\cdot g\). Функция \(g_i\) совпадает с g на \(\pi_i\) и равна нулю вне неё, поэтому \(g=g_{1}\lor \ldots \lor g_p\). Объединение G(1)∪…∪G(p) является
Если каждая часть содержит не более s наборов, то число возможных функций на одной части не превосходит \(2^s\), и получается оценка \(|G|\le p\cdot 2^s\). В стандартном ДУМ высота s и ранг p подбираются так, чтобы это множество было достаточно малым для общей реализации в схеме.
Зачем ДУМ нужно в синтезе
В методе Лупанова большое семейство кофакторов не реализуют независимо. Каждый кофактор сначала раскладывают в дизъюнкцию небольшого числа функций из одного ДУМ. Сами функции G реализуются один раз и затем многократно используются. Так уменьшается цена универсального блока по сравнению с методом
Пример простыми словами
Если куб \(B^m\) разбить на две части π₁ и π₂, любую функцию g можно разделить на два фрагмента: g₁ совпадает с g на π₁ и равна нулю на π₂, а g₂ устроена наоборот. Тогда g=g₁∨g₂. ДУМ обобщает эту идею на p частей и заранее собирает все возможные локальные фрагменты.
Частые ошибки
- Путать порядок m и ранг p. Это разные параметры ДУМ.
- Считать ДУМ обычным функционально полным базисом. Требование здесь специальное: представление дизъюнкцией ограниченного числа функций из G.
- Полагать, что части разбиения должны быть гранями куба. В определении достаточно разбиения на множества наборов.
- Реализовывать каждую исходную функцию независимо и тем самым терять смысл универсального набора G.
