X,

Рис. 2.14. Карта для декомпозиций вида F(g{Ai), А2).

зицию в форме f(x) = F(g(Ai), А2) тогда и только тогда, когда карта декомпозиции для (Ль А2) содержит не больше двух различных столбцов (т.е. столбцов с неидентичным набором нулей и единиц).

Доказательство. Необходимость: предположим, что карта декомпозиции функции /(х) имеет три различных столбца, обозначенных как Cl, С2, С3. Если функция имеет декомпозицию в форме f - F{g{A\), А2) и если для двух столбцов и Cj

мые й достаточные условия получения с помощью этой карты простой дизъюнктивной декомпозиции на множестве переменных (Al, А2) формулируются теоремой 2.2.

Георел1й 2.2. Полностью определенная комбинационная функция f{xi, Х2, .... Хп) имеет простую дизъюнктивную декомпо-

Рис. 2.15. Декомпозиционная карта для примера 2.6.

только две комбинации различных столбцов, то существует простая дизъюнктивная декомпозиция / в форме f =

= F{g{XuX2,x3)Xi,x5).

Если g= 1 для столбцов 1001 (сверху вниз), то g-XiX2X3-\--\-X1X2. Карта на рис. 2.16, а получена путем объединения идентичных столбцов рис. 2.15. Эта карта дает следующую декомпозицию: F = gX5 + Х4Х5 -f gX5. Функция g определяется из карты на рис. 2.16,6, в которой g= 1 для столбцов, соответствующих столбцам карты на рис. 2.15 с комбинацией 1001, и g-= О для столбцов с комбинацией 1110. Следовательно, g = xiX2X3-i--{-Х1Х2. Реализация разложенной функции представлена на рис. 2.17.

g(Ci) =g(Cj), то Ci И Cj должны иметь идентичные наборы нулей и единиц. Следовательно, g{Ci) =fg(C2), (Сг) Фg{Cз,), g{Ci) ¥=g{C3). Но тогда g не может быть двоичной функцией, что противоречит условию.

Достаточность. Предположим, что имеются только два различных столбца Си Сг. Пусть g{Ai) определяется следующим образом: g{Ai) = 1 для всех столбцов, идентичных Сь g{Ai) = = 0 для всех столбцов, идентичных Сг (или наоборот). Можно получить карту, содержащую q -f 1 переменную, путем комбинации всех столбцов, идентичных С], в половине карты g=\, и всех столбцов, идентичных Сг, в половине карты g = 0. Преобразованная таким образом карта используется для нахождения F(giAi), Лг).

Пример 2.6. Рассмотрим карту декомпозиции функции f{xi, Х2, Хз, Xi, Хь), показанную на рис. 2.15. Так как имеются

а

Рис. 2.16. Упрощенная декомпозиционная карта для примера 2.6.

Карты декомпозиции на множествах переменных (Л1, Л2) могут быть также использованы для нахождения декомпозиций в форме F{Au giAz)). Такая декомпозиция существует, если

Xs-Xs-

Рис. 2.17. Декомпозиционная реализация f {xi, Х2, хз, xi, х^).

карта декомпозиций содержит две различные строки. Поэтому нет необходимости строить карты декомпозиции для (Ль Л2) и (Л2, Al). При такой интерпретации для функции п переменных существуют 2- - 1 возможные карты декомпозиции. Карты декомпозиции для и = 3 и п - 4 показаны на рис. 2.18.

Чтобы найти простую дизъюнктивную декомпозицию функции п-переменных, если она существует, можно применить теорему 2.2 к каждой из этих 2 - - 1 карт.

Если все столбцы карты декомпозиции идентичны, то функция не зависит от переменных множества Ль и декомпозиция является тривиальной. Если карта содержит два различных столбца, но комбинации цифр в них содержат либо все нули, либо все единицы, то функция не зависит от переменных множества Л2.

Рис 2.18. Декомпозиционные карты для функций трех переменных (а) ц четырех переменных (б).

б

Рис. 2.19. Декомпозиционные карты функции f {xi, хг, хз) для примера 2.7.

зует декомпозицию F{gi{x2, Хз), -i), где gi{x2, Хз) = Х2 +-з, а F(gu Xl) = Xigi-\- Xigi. Рис. 2.19, e характеризует декомпозицию F{g2lxi, Х2), Хз), где g2{xi, Х2) =Xi-j-X2, а F{g2, Хз) = = X3g2 + X3g2. Рис. 2.19,6 нарушает условия теоремы 2.2 и поэтому не характеризует простую дизъюнктивную декомпозицию.

Для не полностью определенных функций карта декомпозиции будет содержать неопределенные элементы, что требует модификации теоремы 2.2 применительно к этому случаю. Определим два столбца (строки) карты декомпозиции как совместимые (обозначаются через ), если неопределенные элементы можно расположить так, что столбцы (строки) станут идентичными. Если карта декомпозиции содержит три столбца и три строки, все пары которых несовместимы (обозначаются через -f), то простая дизъюнктивная декомпозиция функции не мо-жет быть получена путем разделения переменных, определен-

Специальный случай теоремы 2.2 получается при Ai = {х,} и А2 = Х - Ли Карта декомпозиции будет содержать только Два столбца, ведущих к разложению f(xi, Х2, Хп)-

= Xif{Xu Х2, .... Xii, 1, Xi+i, Хп) -i-XifiXu Xz, Xiu О,

Лг+i, Хп), известному как теорема разложения Шеннона. Такое разложение всегда возможно, и мы не будем на нем останавливаться.

Пример 2.7. Рассмотрим функцию f(xi, Xz, Хз) = х 1X2X3-\-+ л:,Хз--хгХз. Эта функция представляется в виде трех карт декомпозиции, показанных на рис. 2.19. Рис. 2.19, а характери-

j x,

Рис. 2.20. Декомпозиционная карта Рис 2.21. Полностью определенная для частично определенной функции. декомпозиционная карта.

стимы. Систематическая процедура определения существования такого разделения будет описана в гл. 3 (процедура 3.2).

Пример 2.8. Из карты декомпозиции функции /(Xj, Х2, Хз, Х4), показанной на рис. 2.20, следует, что Ci Сд, С] С4 и Сг i-Ci. Поэтому функция f не

имеет простой дизъюнктивной де- i---,

композиции вида F{g(X3, Х4), Xi, Х2). Однако неопределенные элементы могут быть определены так, чтобы строка Г] стала идентичной строке Гз, а строка гг - строке Г4 (рис. 2.21). Это приводит к декомпозиции f~F(g(xu л'г).

Рис. 2 22. Упрощенная декомпозиционная карта.

Хз, Х4). Упрощение карты за счет объединения идентичных строк приводит к карте, приведенной на рис. 2.22, и функции F = =gX3Xi-{-gX3Xi+gX3X4, где g=XiX2+XiX2 (если g= 1 для п, гз).

Если п велико, то нахождение простой дизъюнктивной декомпозиции связано с трудоемкими вычислениями, так как процесс включает полный поиск.

2.3.2. СЛОЖНЫЕ ДИЗЪЮНКТИВНЫЕ ДЕКОМПОЗИЦИИ

Дизъюнктивная композиция, не являющаяся простой (т. е. Имеющая более одной подфункции), называется сложной дизъюнктивной декомпозицией [1,3, 7].

НОГО картой декомпозиции. Простая дизъюнктивная декомпозиция может быть получена, если множество строк (столбцов) можно разделить на два непересекающихся подмножества, таких, что все элементы каждого подмножества попарно совме-

Можно показать, что сложная дизъюнктивная декомпозиция представляет собой развитие простой. Итеративная дизъюнктивная декомпозиция представляется в следующей общей форме:

f (X) = F te (... gb {gi {Ад, Az) Лз), ...), Л J

и основана на повторной декомпозиции исходной простой дизъюнктивной декомпозиции по переменным Ль Az, ..., Ат-и Am-

Множественная дизъюнктивная декомпозиция имеет вид f{x) = F[gi{Ai), gziAz), .... gm{Am)]. Связь между сложными и простыми дизъюнктивными декомпозициями дается следующими теоремами.

Теорема 2.3. Для данной комбинационной функции f{x) существует множественная дизъюнктивная декомпозиция /(х) = = P[giiAi), gzAz) .... gm{Am)] тогда и только тогда, когда существуют простые дизъюнктивные декомпозиции вида

f(x)-F,[g,(Л,), Az, Лз.....ЛJ,

f{)=f2[g2{Az),Ai,A3,..., AJ,

f{x)=Fm[gm{Am), Ль Az, Л„ ,].

Доказательство. Приведено в [3].

Теорема 2.4. Для данной комбинационной функции f{x) существует интеративная дизъюнктивная декомпозиция Дх) = = F{gm{... g3{g2{gi{Ai)), Az), Лз), Л, ) тогда и только тогда, когда существует простая дизъюнктивная декомпозиция вида

простая дизъюнктивная декомпозиция gm

И простая дизъюнктивная декомпозиция и т. д.

Доказательство. Предлагается выполнить самостоятельно.

Пример 2.9. Пусть f = XiXzXi + XxXzXzXi -f ХъХа -f XiXzX -p Ч- -1:2:4. Из карты разложения, показанной на рис. 2.23, а, получим простую дизъюнктивную декомпозицию

f = F{gi{Xu Xz, х^), Xi),

где

gl=Xi-\-XxXz-\-XiXz

и

F = eiXi-\-gxXi.

Теперь рассмотрим функцию gi = -Vs-f XiXg-f 3132- Из карты, приведенной на рис. 2.23,6, получим простую дизъюнктивную

Рис. 2.23 Декомпозиционные карты комбинационной функции (а) и подфункции декомпозиции (б).

Рис. 2.24. Реализация итератианой дизъюнктивной декомпозии.

94 Глава 2 декомпозицию

где

g2 = XiX2 + X1X2 И Fl = g2 + Х3.

Эти две простые дизъюнктивные декомпозиции дают вместе итеративную дизъюнктивную декомпозицию / = = P{Pi{g2{Xi, Х2), Хз)Х4), показанную на рис. 2.24.

Рис. 2.25 Декомпозиционная карта функции в примере 2.10.

Пример 2.10. Пусть / == XiXzAs + Х1Х2Х4 + XiXgXg-f X1X2X4. Карта декомпозиции, показанная на рис. 2.25, имеет две различные строки и два различных столбца и, следовательно, дает следующие две декомпозиции функции /:

где

где и

f = Fi(giixu Х2), Хз, Х4),

ёЛХи X2)=XiX2-fXiX2, Fligu Хз, Х4) = giXg + giX4,

/=2 fete, Xi), Xl, X2), §2 = 3 + 4, F2 = g2XlX2 + g2XiX2.

В соответствии с теоремой 2.3 существует множественная дизъюнктивная декомпозиция

/2 = [gl {Xi, Х2), g2 {Хз, Xi)].

функция F может быть определена путем графического представления f как функции gi на карте Карнау. В рассматриваемом примере F = gx-gz-