У т в е р ж д е н и е 21.3. Булева функция f (x) допускает параллельную разделительную декомпозицию вида (21.1) тогда и только тогда, когда она допускает двухблочные разделительные декомпозиции вида

f (x) = ϕ1(g1(z1), z2, … , zm); f (х) = ϕ2(z1, g2(z2), … , zm);

…

f (x) = ϕт(z1, z2, … , gm(zm)).

Пусть функция f (x) задана с помощью табл. 21.9. Эта таблица является картой декомпозиции для разбиения ({x1, x2, x3}, {x4, x5, x6}). Среди ее строк имеется только два различных значения, следовательно, заданная функция допускает декомпозицию вида

f(х) = ϕ1(g1(x1, x2, x3), x4, x5, x6),

аесли строки заменить одноименными столбцами, то убедимся, что существует суперпозиция

f(х) = ϕ2(x1, x2, x3, g2(x4, x5, x6)).

разделительную декомпозицию вида f (х) = ϕ(g1, g2). Определим функцию g1 как

g1(x1, x2, x3) = х1 х2 х1 х2 х3.

Тогда табл.21.10 будет задавать функциюϕ1. По этой таблице получим

136

g2(x4, x5, x6) = х6 х4 х5.

После соответствующего кодирования столбцов значениями переменной g2 будем иметь

ϕ(g1, g2) = g1 g2 g1 g2.

21.4. Неразделительная декомпозиция

При неразделительной декомпозиции множества аргументов Z1, Z2, … , Zm могут пересекаться. Рассмотрим двухблочную неразделительную декомпозицию

f (x) = ϕ(g(z1), z2),

где компонентами векторов z1 и z2 являются переменные из множеств Z1 и Z2 соответственно, причем

Z1 Z2 = X, Z1 ∩ Z2 ≠ .

Естественно, имеет смысл решать задачу такой декомпозиции только при

|Z1| < |X | и |Z2 | + 1 < |X |.

Особенностью карты декомпозиции для такой задачи является то, что некоторые ее элементы находятся на пересечении строки и столбца, в кодах которых одна и та же переменная (принадлежащая как Z1, так и Z 2) имеет противоположные значения. Значение функции для такого элемента не определено. Это можно представить как внесение новых аргументов, число которых равно |Z1 ∩ Z2 |. При этом каждый из них связан с каким-либо из заданных аргументов так, что он не может принимать неодинаковое с ним значение. Таким образом, данную задачу можно решить как задачу разделительной декомпозиции не полностью определенной булевой функции.

У т в е р ж д е н и е 21.4. Булева функция f (х) допускает двухблочную неразделительную декомпозицию вида f (x) = ϕ(g(z1), z2) тогда и только тогда,

137