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