2.3.3. НОНДИЗЪЮНКТИВНЫЕ ДЕКОМПОЗИЦИИ

В нондизъюнктивной декомпозиции входные переменные различных составляющих подфункций имеют несколько общих элементов. То есть если /(х) == (1(Л1), 2(2), gh{Ak)), где

и Ai = X и существуют t и /, i ф j, такие, что Аг[]А,фФ, то

эта декомпозиция является нондизъюнктивной. Комбинационная функция f(x) имеет простую нондизъюнктивную декомпозицию, если f{x) =z F{g(Ai), А2), где AiU А2 = Х и Л1 П =

= Л12=И=Ф.

Пусть Bi = i - А12 и B2 = 2 - Л12. Если i4i2=p, [fill - pl к (62! =Р2, то p-f pi-f р2 = п = \Х\. Для каждого из 2р значений Л12 можно построить карту декомпозиции с 2 строками и 2 столбцами. Чтобы /(х) имела простую нондизъюнктивную декомпозицию, каждая из этих карт должна определять простую дизъюнктивную декомпозицию.

Теорема 2.5, Комбинационная функция /(х) имеет простую нондизъюнктивную декомпозицию вида f(x)=F{gi{Ai), А2) тогда и только тогда, когда каждая из 2р карт, построенных для фиксированного значения Л12 = Л1 П Лг со строками, соответствующими Л2 - Л12, и столбцами, соответствующими Л1 - Л12, имеет не более двух отличающихся друг от друга строк или столбцов.

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

Пример 2.11. Пусть / = XiX2Xi -f 2X3X4 -f Х2Х3Х5 -f X2X3X4 -f H-X2X4X5. Для получения декомпозиции с Л1 = [xi, Х2Х3} и Л2 = - {Х2, Xi, Х5} построим карты декомпозиции для всех возможных комбинаций входов в множестве Л12 = Л1 П Л2 = {хг}- Карты декомпозиции для Х2 = О и Х2 = 1 показаны на рис. 2.26. Обозначим /(xj. О, Хз, Х4, Хб) через fo, а f(xi, 1, Х3, Х4, Х5) через fi. Пользуясь картами разложения, получим следующие декомпозиции для /о и /1:

fo{Xi, Хз, Х4, X5)=Fo{go(Xi, Хз), Х4, Xg),

где go = X3 и Fo = X5go + Xigo,

fl (Xi, Хз, Х4, Xs) = f 1 {gi (Xi, Хз), X4 X5),

где g, = Xi + Хз и f, = X4gi + ХлМг

По теореме разложения Шеннона

/ = J2fo(b 3, Х4, Х5) X2fi{Xi, Х3, Х4, Х5), Xif о = Х2 (%go + Xigo), Xzf 1 = X2 (X4g, -h X4ogl). (1)

Пусть g = X2g-o + X2gl = X2X3 + X2 (X, + X3),

X2g = X2 fego -f Xggi) = Xago, (2)

X2g = X2 (X2go -f Xzgi) == X2 (X2 -f go) (X2 + gl) = Мй- (3)

г

х, = 0

Рис. 2.26. Декомпозиционные карты функции в примере 2.11 для Х2-О и

Х2=\.

выше. Однако это связано с тщательным исследованием всех пересекающихся подмножеств множества всех входных переменных и в общем случае не всегда поддается расчету.

2.4. СПЕЦИАЛЬНЫЕ КЛАССЫ

КОМБИНАЦИОННЫХ ФУНКЦИИ

В этом разделе мы изучим некоторые классы комбинационных функций и их свойства. Каждый из этих классов обладает рядом специальных свойств или при определенных технологиях имеет простые реализации.

Аналогично Xzg - Xzgi и Xzi - xgi. (4)

Тогда с учетом выражений (2) -(4) получим

f = Xzfo + Xzh = х2 {Xgo + Xigo) + X2 {xgi + XXgi) = = X2 {he + Л:4#) + 4 {Xig -f X4X5g),

где

Декомпозиция имеет вид

fiXl, х2, Хз, Xi, X5) = F{g{Xi, Х2, Xg), Xg, Х4, Xg), где F = Х2Х5Я + X2X4g + X2X4g + X2X4X5g-

и g = X2X3 + X1X2 + X2X3.

Сложные нондизъюнктивные декомпозиции могут быть получены аналогично дизъюнктивному случаю, рассмотренному

Рис. 2.27. Карты Карнау функций: /(х Хг, Хз) (а), f (хз, Хг, х,) (б) н

f (х2, Хз, X,) (в).

ЦИИ f приводит к получению идентичной карты, или, что эквивалентно, замена всех переменных Хг на Xj, а Xj на х,- в булевом выражении функции приводит к получению идентичного выражения. Аналогично Xi Xj, если f{Xi, Х2, Xi, Xj,

. . . , Хп) == f{Xi, Х2, . . . , Xj, . . . , Хг, . . . , Хп)

Пример 2.12. Рассмотрим функцию f = -f XiXg + XiXs. Для этой функции Xi ~ Хз, что следует из взаимной замены переменных Xi и Хз в булевом выражении функции или из карт Карнау, изображенных на рис. 2.27, а и б. Однако Xi Ф Х2, так как взаимная замена этих переменных в булевом выражении функции f дает выражение Х\Х2Х3Х2Х3, не эквивалентное исходному. Несимметричность относительно переменных Xi и Х2 также следует из неидентичности карт Карнау, изображенных на рис. 2.27, а и е.

4 Зак. 841

2.4.1. СИММЕТРИЧНЫЕ ФУНКЦИИ

Симметричные функции [4] представляют собой интересный класс комбинационных функций, имеющий простые канонические реализации на базе устройств двустороннего действия, таких, как реле и контакты.

Функция f{xu Х2, Хп) называется симметричной относительно переменных Xi, Xj, обозначаемых Xi ~ Xj, если

f{Xi, Х2, . . . , Xi, . . . , Xj, . . . , Хп) = f {Xi, X2, . - . , Xj, . . . , Xi, . . . , X),

Т.е. взаимная замена переменных х,- и Xj на карте Карнау функ-

Лемма 2.1. Если для комбинационной функции f{xi,x2, ... Хп), если Xi ~ Xj и Xj ~ Xfe.To Xi ~ Хп, т. е. свойство симметрии транзитивно.

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

Функция f (Xi, х2, ..., Хп) называется полностью симметричной, если для каждой пары переменных Xi, Xj Xi ~ Xj или ~

~ Xj.

Для функции /, приведенной в примере 2.12, Xi и Xi Р

х2. Следовательно, эта функция не является полностью симметричной. Следующие леммы характеризуют класс полностью симметричных функций и симметричных логических операций.

Лемма 2.2. Функция f (Xi, Хг, .... х„) полностью симметрична тогда и только тогда, когда существует множество целых чисел {а\, 02, ..., йр}, О Gj п, такое, что f = 1 тогда и только тогда, когда точно а, переменных (х*, х*, ..., х*) равны 1 для /= 1, 2, ..р (где х*1 означает х,- или х,). Эта функция будет обозначаться следующим образом: 5 (х*, х*, ..., х*).

Доказательство. Предположим, что f есть полностью симметричная функция и имеет точку 1 с точно Oj переменными, равными I. Тогда /= 1, если любое множество точно Uj пере-кбенных равно 1 и любая пара переменных может быть взаимно заменена без изменения значения функции.

Аналогично если / = 1 для всех точек с точно Gj переменными (х*, X*, X*), равными 1 для /= 1, 2, р, то она полностью симметрична.

Лемма 2.3.

(а) Sa, а^, .... ар {Xl, Хг, . . ., Х„) -f Sfc b. .... (Xl, Хг, . . ., Хп) =

= Sc. .....(xi, Х2, ..., х„), где (ci, Сг, ..., Сй) =

= {ai, Сг, Gp}U{bb Ьг,

(б) Saj, 2.....йр {Хх, Хг, . . . , Х„) Sb, .....(Xl, Х2, ... х„) =

= 2.....Хг, ..., Хп), где (ci, Сг, ..., Сй} =

= {а 02, ..., йр} П {Ьх, Ьг, , Ь?}:

(в) Sa. а^. .... ар {.Хх, Хг, . . . , Х„) = Sj , .....(Xi, Хг, ..., х„),

где {Ьх, &г, bft} = {0, 1, }-{ !, г, р);

(г) Sa а,.....ар {Xl, Хг, . . ., Х„) = 5ь,. Ь^. .... bp (Xi, Хг, .... Хп),

где bi=n - ai, i=\,2,...,p.

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

С помощью теоремы разложения Шеннона любая комбинационная функция п переменных может быть представлена в виде

/ (Xi, Х2,..., Хп) = Xif (1, ЛГг. Хз, ..., х„) + x,f (О, Х2, Хз, ..., х„) (1)

= Хг/ (х 1, Хз, ..., х„) -f Хг/ (ь О, Хз, ..., х„). (2)

Если х,~Х2, то (1)=Х2/(1, Xi, Хз, x )-f

+ Хг/(0, Хи X х„) (3)

Так как (2)::(3), то f(Xi, 1, Хз, x ) = f(l, Xi, Хз, х„) и /(Хь О, Хз, х„) = /(0, Хь Хз, х„). Если f(Xi, 1, Хз, ...

x ) = f(l, Xi, Хз, Хп), то число точек 1 в обеих функциях должно быть одинаковым. Аналогично, если Xi ~ Хг, то f(l, Xi, Хз, Хп) и /(х,. О, Хд, Хп) должны иметь равное число точек 1. Отсюда вытекает необходимое, но не достаточное условие, формулируемое следующей леммой.

Лемма 2.4. Если функция /(хь Хг, Хп) имеет pi точек 1 при х, = 1 и qi точек 1 при Xj = О, то она является полностью симметричной, только если для всех i и j pi = Pj и qi = qj (для Xi ~ Xj) или Pi - qj и pj - qi (для Xj Xj).

Условие леммы 2.4 необходимо, но недостаточно для симметрии. Однако ее легко применять, что существенно облегчает анализ функции на симметричность. Следующую лемму можно использовать для сведения задачи анализа на симметричность функции п переменных к той же задаче для функции п- 1 переменных, что позволяет последовательно упрощать эту задачу.

Лемма 2.5. Функция /(xj, Х2, ..х„) полностью симметрична относительно переменных х*, х*, ..., х^ (где xt = x. или х.) тогда и только торда, когда и gi (xg, ..., х„) = f (1, Xj, ..., х„)

и g-p{x2.....Xn) - f{0,X2, х„) симметричны и дополнена

одинаковыми переменными т. е. g, = (х*, х*. ..., х*),

Szb.b.....fcp (К' К' О. где b=al+ для всех г, или

bi = ai- 1 для всех О-

Доказательство. Необходимость. Пусть ! [хи Х2, ..., х„) = = (1. 4> О- Тогда f(Xi, Xg, x ) = x,f(l,

4. > O + -i/(0, 2. . 0=>,gi(2. . )+-1г(- 2 --n)-Следовательно, g, (x,.....= S -, .... .p-, (4 <)

g,(x ...,x ) = S, ,... ,(x*, Если / = S, ..... X

X(x x;...,x;), To = ......(4 .<)

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

Другой упрощающий подход основан на следующей лемме.

Лемма 2.6. Для функции f{xi, Xi, Хп) а) Xi ~ Xz тогда и только тогда, когда /(О, 1, Xs, х^,..., Хп) =f (1. О- -з, х^,..., Хп), и б) Xl -~ Х2 тогда и только тогда, когда ДО, О, Хз, Х4, ..., х„) = = Д1, 1,Хз, Х4, ...,х„).

Доказательство, (а) По теореме разложения Шеннона имеем

f(Xi, Х2, X )=XiX2/(l, 1, Х з, X )-fX,X2f(I, О, Хз,...,Х„)-Ь

+ XiXzfiO, 1, Хз, . . . , Х„) -f XiX2/(0, О, Хз, . . . , Хп). Если Xl ~ Х2,

то взаимная замена Xi и Хг не приведет к изменению функции. Сделав это для правой части предыдущего уравнения, получим выражение Х1Х2Д1, 1, Хз, ... , х„)-f XiX2(l, О, Xg, .... х„)-f -f XiX2f(0, 1, Хз, Хп) -f XiX2f(0, О, Хз, Хп). Это выражение равно исходному, из которого оно было получено только в том случае, если f (О, 1, Хз, Х4, ..., х„) = /(1, О, Хз, Х4, ..., х„). (б). Предлагается выполнить в качестве упражнения.

Леммы 2.4-2.6 могут быть использованы для проведения анализа функций на симметричность следующим образом. Сначала с помощью леммы 2.4 определяются возможные симметричные переменные, а затем с помощью леммы 2.5 и/или 2.6 исходная задача сводится к более простым. Следует, однако, отметить, что после использования леммы 2.5 мы еще должны решать задачу определения симметрии двух функций (п- 1)-переменной, а после леммы 2.6 - только эквивалентности (но не симметрии) двух функций {п - 2)-переменных. Следовательно, лемма 2.6, на наш взгляд, является более полезной.

Пример 2.13. Пусть Дхь Х2, Хз, Х4) есть функция, точки 1 которой приведены в таблице на рис. 2.28. Если есть число 1-точек с Xi = 1, а 9i есть число 1-точек с Xj = О, то

р, = 4 р2 = 4 рз = 3 р4 = 4 ?1 = 3 2 = 3 3 = 4 4 = 3

Из леммы 2.4 следует, что Xi может быть симметрично Х2 (так как pi = ps), но Xi 4X2 (так как pij-Qz). Аналогично Xi может быть симметрично Хз и Х4. Из леммы 2.6 следует, что если Xl ~ Х2, то /(О, 1, Хз, Х4) = /(1, О, Х3Х4). Точки 1 этих двух функций приведены ниже:

f(0, 1,хз, Х4) f(l,0, Хз, x.i)

110 0 1 о о

0 111 1 1 о

0 0 11 О О 1

1110 О о О

0 1 о 1 Р2 = 2 Рз = 1 Р4 == 1

1 О О 1 92 = 2 93 = 3 94 = 3

10 0 0

Рис. 2.28. Перечень точек 1 функ- Рнс. 2.29 Значения р^, q. для точек I ции в примере 2 13. функции /(1, хо, хз, Xi) в примера

2.13.

Применяя лемму 2.4, можно врщеть, что Х2Хз и ХзРхг, так как рзФРг и рзФЯ2- Таким образом, /(1, Х2, Хз, Xi) не является полностью симметричной и, следовательно, функция f{Xx, Х2, Хз, Xi) также не является полностью симметричной.

Пример 2.14. Рассмотрим функцию f, точки 1 которой показаны в таблице на рис. 2.30.

Рис. 2.30. Значения р., для точек 1 функции в примере 2.14.

Из леммы 2.4 следует, что Xi может быть симметричной Х2, Хз, Xi. Используя лемму 2.6 для проверки симметричности функций Xl и X2{xi - Х2), найдем, что 1-точки обеих подфункций f(0,0,X3,X4) и 1,X3,X4) равны (хз, 4) = (О, 1), (1,0). Таким образом, Xl ~ Х2. Аналогичным образом легко показать, что Xl ~ Хз и Xl ~ Xi. Следовательно, f = 5,ч.г,...., (л^ь , Хз, Х4).

Так как множества 1-точек не идентичны, Xi-ix и функция не является полностью симметричной.

Тот же результат может быть получен и с помощью леммы 2.5. Если бы / была полностью симметрична, то f(0, Х2, ...

Хп) и f(l, Х2, Хп) должны быть полностью симметричны. Точки 1 функции f(l, Х2, Хз, Xi) приведены на рис. 2.29.

Xi Х2 Хз Xi Xi Хз Xi

В первой точке 1 исходной таблицы ни одна из четырех переменных (xi, ic2, Xs, Х4) не равна 1, в следующих четырех 1-точках равны 1 по одной из этих переменных, в последних четырех 1-точках, равны 1 по три из этих четырех переменных. Следовательно, f = So, 1,з{Хи Х2, Хз, Х4).

Другой метод анализа функции на полную симметричность дает следующая теорема [5].

Теорема 2.6. Для функции f(xi, Х2, Хп) xi ~ х, для всех i, j, I тогда и только тогда, когда удовлетворяются сле-

дующие два условия:

(1) f{Xu Х2, Хп-и Хп) = !{Хи Х2, Хп, Хп-\),

(2) f{xu Х2, Хп-и Хп) = f{X2, Хз, Хп-1, Хи Хп).

Доказательство. Необходимость. Если условие (1) не удовлетворяется, то Хп-1 Хп- Перестановка входов условия (2) получается путем взаимной замены двух переменных. Так как Xi Xj для всех /, /, 1 i, 1 п, то условие (2) выполняется.

Достаточность. Пусть функции Pi{f) и Pzif) получены перестановкой входов в соответствии с условиями (1) и (2) теоремы. Так как Pi{f) = f и Pzif) = f, то эти перестановки могут выполняться для Pi и Рг повторно в любой последовательности без изменения функции. При выполнении соответствующей последовательности перестановок Pi и Рг может быть взаимно изменена любая пара переменных Хг и Xj. Следовательно,

f{Xi, Х2, . . . , Xi, . . . , Xj, . . . , Хп) = f{Xi, Х2, . . . , Xj, . . . , Xi, ...

..., Xn) к Xi Xj для всех i, j, 1 i, j n.

Эта теорема полезна для нахождения симметричных функций в недополненном множестве переменных. Для функции f в примере 2.14 f(xi, хг, х^, Хз) ф f{Xu Х2, Хз, х^), что вытекает из перестановки столбцов 3 и 4 на рис. 2.30, и, следовательно, условие (1) теоремы 2.6 не выполняется. Чтобы выяснить, является ли функция полностью симметричной, нужно определить, могут ли быть удовлетворены условия теоремы путем дополнения некоторых входных переменных. Чтобы показать, что функция в примере 2.14 является полностью симметричной, можно представить ее как функцию переменных хи Х2, Хз и X4 и применить теорему 2.6.

Каноническая контактная цепь для реализации любой симметричной функции показана на рис. 2.31 [2]. С каждым контактом ассоциируется переменная, управляющая размыканием и замыканием контакта, как было описано в разд. 1.2. Любая точка цепи имеет значение 1 тогда и только тогда, когда существует путь, связывающий эту точку с точкой В на рис. 2.31, вдоль которого все контакты замкнуты. Так как функция ИЛИ может быть реализована контактной цепью параллельным соединением контактов, любая симметричная функция Sa, .....а

реализуется соединением друг с другом точек, обозначенных

Jhi i-j--oS .tlXi,Xz---x )

Xn-i Xf]

Jh-II- Hn hj--о5 (х^,Х2----Х„)

i 1 1 1

Xs Xe Xj

Xg Xif Xg Xg

H -H I-f--о 52fa;j,i2- -x)

Xz Xjj 35

Jhsz h-Jhjh -Xnl-j-oSi(Xi,Xz--x )

Xi Xz Xs Xl, x .i x

Рис. 2.31. Реализация симметричных функций контактными цепями.

Н^2 1-Ня:з

Рис. 2.32. Реализация функции S],2 (л; Хг, Хз) контактной цепью.

Sap Sa,..., Sop. Ha рис. 2.32 показана реализация Si 2(a:i, Хг, Xg). Такие канонические реализации симметричных функций могут быть выполнены с помощью контактных и других двунаправленных устройств, таких, как полевые МОП-транзисторы.

2.4.2. ЮНАТНЫЕ ФУНКЦИИ

Важным свойством комбинационных функций является юнат-ность [10]. Пусть XiXj представляют собой точки в п-кубе, определенном переменными (xi, Xg, ..., Для функции f {х^ Х.2, х„) f(Xi)f(Xi), если f{Xi) = /(ху) или f (х,-) = 1, а /(х,)=0. Говорят, что функция f положительна относительно переменной Х{, если для всех 2 возможных комбинаций значений оставшихся п - 1 переменных

fiX\,x2.....Xj-i, 1, +

> f (Xi, x2, Xi-i, 0, Xi + i, Xn).

Аналогично функция f отрицательна относительно переменной Xi, если

/(Xi, Хп, Xi-i, О, Xi+u х„)>

(Xi, X2, . . ., Xj-i, 1, X£4.i, . . ., X,j).

Лемма 2.7. Полностью определенная комбинационная функция f(xi, Х2, х„) положительна относительно переменной Xj в том и только в том случае, если ни одно из выражений минимальной суммы произведений этой функции не содержит литерала Xi. Аналогично U отрицательна относительно переменной Хг в том и ТОЛЬКО В ТОМ случае, если ни одно из выражений минимальной суммы произведений этой функции не содержит литерала Xi.

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

Говорят, что функция f(xi, Хг, х„) положительная, если она положительна относительно всех переменных Хг. Аналогично функция, отрицательная относительно всех своих переменных, называется отрицательной. Функция f (Х], Хг, ..., х„) называется юнатной, если для каждой х, 2, п, f или положительна, или отрицательна относительно переменной Xj.

Пусть Xj = (ai, Са, aj и x, = (bi, bg, Ю- Тогда XiXf, если Ukb/i для всех к, lin. Следовательно, для положительной функции f (х,) f (х/), если х,- Х;.

Аналогично для отрицательной функции /(XiXf(xy), если

Х,>Х;.