Разложение функции и суперпозиция схем
Если функцию можно представить как \(g(h_{1}(x),\ldots,h_r(x))\), естественный метод синтеза состоит из двух уровней: сначала строятся схемы для \(h_i\), затем их выходы подключаются к входам схемы, реализующей g. Эта структурная операция называется суперпозицией. В общем определении Σ=Σ″(Σ′) получается объединением двух схем и присоединением части входов Σ″ к выходам Σ′.1
Суперпозиция называется правильной, если итоговая схема реализует ожидаемую подстановку F″(F′). Она называется корректной, если, кроме того, в вершинах итоговой схемы, соответствующих выходам Σ′, сохраняются те же функции, что были там до соединения. Корректность важна, когда результат внутренней подсхемы нужно одновременно использовать и в других композициях.
Почему с контактными схемами возникает проблема
В КС соединение полюсов меняет граф достижимости. После склейки могут появиться новые пути, которые проходят через обе исходные схемы несколько иначе, чем предполагает обычная подстановка функций. Поэтому для стыковки матрицы проводимости удовлетворяют только
\(F\ge F'\cdot F''\)
в булевой матричной арифметике. Дополнительные единицы в F соответствуют паразитным путям.1
Разделительные контактные схемы
КС разделительна по входам, если функция проводимости между любыми двумя различными входами равна 0. Аналогично определяется разделительность по выходам. Например, вентильная звезда является разделительной по входам, а контактное дерево может служить разделительной по выходам конструкцией.1
Лемма Шеннона
Лемма 3.1 утверждает: если Σ является стыковкой Σ″(Σ′), то \(F\ge F'\cdot F''\), а \(F=F'\cdot F''\), если Σ″ разделительна по входам или Σ′ разделительна по выходам.1
Именно разделительность запрещает паразитным проводящим путям переходить между различными точками стыковки. Поэтому функциональная суперпозиция снова точно совпадает с графовой. Последовательное соединение двухполюсных КС корректно всегда. Параллельное соединение в общем случае реализует нужную дизъюнкцию, то есть является правильным, но может не сохранять внутренние выходные функции и потому не обязано быть корректным.