вить в виде Ki,j{\) {Xp\/Xp)-Ki,i{v) = Xp-Ki,j{v)VXpKi,j(v) = Ki(v) VKj(v). Очевидно, что полученные минтермы Ki{v) и Kj(v) являются соседними, так как они различаются только одним первичным термом ХрР(Хр и Хр). Отсюда следует правило минимизации: дизъюнкцию двух соседних минтермов можно заменить одним контермом, не зависящим от одной переменной.

Пусть контерм п переменных /(«,j(v) не зависит от двух переменных Хр и Хд (г!>2). Тогда можно записать, что K(,j(v) = (дср\/ VXp)(xq\/Xg)K,,j(y) = XpXg-Ki.j(v)\/XpXt-Ki.i(v)\/XpXg-Ki,j{>)\/ \/Xf,XgKi,j(v)=Ki(v)VKT{v)VKBiv)\/KiM- Из этих соотиошеиий видно, что каждый из четырех полученных минтермов имеет среди остальных по два соседних. Отсюда следует правило минимизации: дизъюнкцию четырех минтермов, каждый из которых имеет среди остальных по два соседних, можно заменить одним контермом, не зависящим от двух переменных, причем исключаются те переменные, которые входят в минтермы как с инверсией, так и без инверсии.

Пример. Было показано, что контерм Ki,i=Xi {п=3), т. е. контерм не зависит от двух переменных Хз н х. Тогда легко показать, что А:,,7 (V) = ( *j V ) ( 4 V Х2) -Kij (V) = 3 4 «5 V ХзЧ h V

Vs х% х, V «2 «1 = /Cl (V) V Кз <v) V Kb (V) V К, (V), где каждый минтерм имеет по два соседних.

Продолжив рассуждения дальше, можно установить общее правило минимизации: одним контермом п переменных Ки{\), не зависящим от m переменных {т<.п), можно заменить дизъюнкцию 2™ минтермов, если каждый из них имеет по m соседних мвнтер-мов среди остальных 2"*-1 минтермов.

Если контерм Kij{\) не зависит от т переменных, то принято говорить, что он покрывает 2™ минтермов. На этом свойстве кон-термов и осиовывается минимизация функций f{v), заданных в СДНФ, которая в соответствии с выражением (1-38) представляет собой дизъюнкцию некоторого числа минтермов К{у. f{v)= Vi {J-

Заменяя дизъюнкцию 2™ (m = 0, 1, я) минтермов (2°=1 в случаях, когда какие-либо минтермы не имеют ни Одного соседнего минтерма) соответствующими контермами Kt,j(v), функцию можно представить в виде дизъюнкции некоторого числа контермов, покрывающих все минтермы Kt, входящие в СДНФ функции:

f(.)-y Kiji). (1.51)

Такая форма представления функций называется дизъюнктивной нормальной формой (ДНФ). Если ДНФ содержит минимально возможное число первичных термов х , то она называется минимальной ДНФ (МДНФ). Следует отметить, что любые правила минимизации сводятся к сформулированному общему правилу, в то время как алгоритмы (методы) минимизации могут сильно различаться между собой.

На основании идемнотеитных законов один и тот же минтм Kiiv), входящей в СДНФ, может использоваться нескольио раз

для образования различных контермов Ki,j(v), так как К,- = /С(\7

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

Пример. Пусть задана СДНФ функции трех переменных Дv) = = K3{v)\/K5M\/K(i{v)VKj{v)=X3X2Xi\/Х3Х2Х1 V ХзХ2Х1 \у Х3Х2Х1. Здесь для получения МДНФ минте рм K7(v)=X3X2Xi необходимо использовать три раза: f(v) = (xaXaiVfi) V(«32«iy*34i:2J:i) V

.V(-«3«2«iVW2A;i) = XiXiiX} V «3)V«3:iU2VJC2) V X3Xa(XtVxi) = = X2Xi\/X3Xi\yX3X,.

Уже из этого элементарного примера видно, сколь сложно использовать аналитический метод минимизации и»-за трудоемкости работы по отысканию соседних минтермов (задача еще более усложняется при наличии в СДНФ группы, состоящей из 2"" миитермов при т>1, которые можно заменять одним контермом).

Рассмотрим теперь методику получения МНФ в других базисах. Для этой цели наиболее удобно использовать закон двойственности, который обладает замечательным свойством: при преобразовании любого логичеекого выражения на основании закона двойственности ни число первичных термов Хр", ни общее число операций дизъюнкции и конъюнкции, входящих в исходное логическое выражение, не изменяется.

Пусть получева МДНФ некоторой функции /(v). Используя закон двойного отрицания и закон двойственности, получаем

/ (V) = v {( , (V) = П Ktj (V). (1.52)

Это соотнощеиие и дает МНФ функции f(v) в базисе И - НЕ, . так как для ее реализации требуются только операции И - НЕ. Запишем МНФ в базисе И-НЕ функции трех переменных, МДНФ

которой была найдена: f{v)-XiXi\/X3Xi\/X3X2=X2Xi-X3Xi-x3x2.

Получение минимальной конъюнктивной нормальной формы (МКНФ) функции /(у) легко сводится к получению МДНФ ни-версиой функции / (v> и преобразованию ее с помощью закона двойственности:

/(v)= v Kijiv); (1.53)

(./)

Mv> = П Ktj (V) = TlMijiv), (1.54)

где Mj,j -дизъюнктивные термы (1.50).

Пример. Пусть требуется найтн МКНФ функции трех переменных f(v), значения которой равны О только в точках Vo, Vi и v4. Совершенная ДН инверсной функции /(v)=/Co(v)V КЛуУ\/, yKi{v)=X3x2Xi\yx3X2Xi\yx3X2Xi. Используя минтерм o(v) =гзД1:2а;1 дважды, легко показать, что МДНФ (1.53) инверсной функции f{v)=x2X1X3X2. Тогда МКНФ функции f(v) получается с помощью закона двойственности /(v) =дс2Дсг\/*з."С2= (."гУ*!).(зХ/г).

Рис. 1.1

в базисе ИЛИ - НЕ МНФ функции v) может быть получена непосредственно из МКНФ (1.54) с помощью закона двойного отрицания и закона двойственности

/(v)= y\Mij(v) v Mij (V).

(1.55)

Найдем МНФ в базнсе ИЛИ-НЕ для функции /(v), рассмотренной в предыдущем примере:

f(\) - {x2\/Xi) (ХгУХг) ==х2\/х1\/Хз\/Хг.

Таким образом, получение МКНФ и МНФ в базисах И - НЕ и ИЛИ -НЁ функции /(v) всегда можно свести к получению МДНФ либо функции /(v), либо ее инверсии f(v).

Диаграммы Вейча. Онн представляют собой один из табличных способов задания функций и состоят из клеток, каждая из которых соответствует определенной точке Vi области определения функций. Диаграммы Вейча для функции п переменных состоят из 2" клеток, которые можно пронумеровать с помощью чисел ( = 0, 1, 2"-1. Чтобы с помощью диаграммы Вейча задать функцию f{x), необходимо в каждую клетку с номером i занести значение функции /(Vi) = ==ai = 0 или 1, которое оно принимает в точке Vj.

Рассмотрим диаграммы Вейча для функций трех переменных (г! = 3). Так как 2 = 2з=8, то диаграмма Вейча состоит из восьми клеток (рис. 1.1). Каждой стороне диаграммы Вейча соответствует своя переменная Хр (р=1, 2, 3), причем одной половине стороны

соответствует первичный терм x"j=xp=Xp, а другой - первичный терм xJ=xp=Xp . Поэтому каждой клетке будет соответствовать совокупность первичных термов х, 4% i. а номер данной клетки будет определяться числом ( = 36261 (рис. 1.1, а).

Любой миитерм Ki (v) представляет собой функцию, равную I только в одной точке Vi области определения, поэтому иа диаграмме Вейча он представляется единицей, стоящей только в одной клет-. ке с номером i. Например, иа рис. 1!1,б показана диаграмма Вейча для минтерма К2{)=х1х1х° = ххх. На рис. 1.1,6, в, г использованы упрощенные обозначения сторон диаграммы Вейча, полностью соответствующие обозначениям на рис. 1.1, а (одна половина сторон соответствует Хр, а другая -дср). Клетке с номером 1=2 соответствует на основании принятых обозначений совокупность первичных термов хз, х2 и Xi, конъюнкция которых и представляет собой миитерм /c2(v). Таким образом, можно сказать, что каждой клетке с номером i соответствует минтерм Ki(v). Две клет*