Известно, что схемная реализация булевой функции f(x) = f(x1, x2, ..., xn) существенно уп рощается, если ее можно представить в виде композиции f(x) = = g(h(u, w), w, v) двух функций g и И от меньшего числа переменных. При этом м и) U w v = x, u v = u w = w v = )O, и компо зиция нетривиальна, если |u| > 1и |v| > 0. Будем говорить, что в этом случае функция Дх) деком позируется по разбиению иЫу. В работах [1,2] было сформулировано необходимое и достаточ ное условие существования такой композиции для двухблочного разбиения и/г (когда |w| = O): коэффициенты дизъюнктивного разложения Шеннона функции Дх) по переменным множества идолжны принимать не более двух различных значений. В дальнейшем данное условие было обобщено на случай, когда |w| ≠ 0, оно должно выполняться раздельно для каждого коэффициента разложения функции Дх) по переменным множества IV [3,4]. Проверка условия путем перебора всехкоэффициентов разложения достаточно проста, но становится трудоемкой с ростом числа переменных п, поскольку число перебираемых коэффициентов зависит от и экспоненциально.
展开▼
机译：众所周知，如果可以表示为组合物f（x）= g（h（u， w），w，v）两个函数g且来自较少数量的变量。同时，m i）u w v = x，u v = u w = w =）o，并且组件是不动的，如果| U | > 1i | V | > 0.在这种情况下，函数dh）甲板在它的分区上摆姿势。在[1,2]中，对两个嵌段分区和/ g（当| w | = o）的这种组合物存在的必要和充分条件（当| = o）：DX的Shannon函数的分解分解的系数）在多个I的变量上，我不能超过两个不同的值。在未来，这种情况是广泛化的，以便在| W | ≠0，它应该单独执行DX函数的每个分解系数）在集合IV的变量中[3,4]。通过分解的分解的蛮力验证条件是非常简单的，但是随着变量P的数量增加而变得耗时，因为系数的系数的数量取决于和指数。
展开▼
